Computing spectra is a central problem in computational mathematics with an abundance of applications throughout the sciences. However, in many applications gaining an approximation of the spectrum is not enough. Often it is vital to determine geometric features of spectra such as Lebesgue measure, capacity or fractal dimensions, different types of spectral radii and numerical ranges, or to detect gaps in essential spectra and the corresponding failure of the finite section method. Despite new results on computing spectra and the substantial interest in these geometric problems, there remain no general methods able to compute such geometric features of spectra of infinite-dimensional operators. We provide the first algorithms for the computation of many of these long-standing problems (including the above). As demonstrated with computational examples, the new algorithms yield a library of new methods. Recent progress in computational spectral problems in infinite dimensions has led to the solvability complexity index (SCI) hierarchy, which classifies the difficulty of computational problems. These results reveal that infinite-dimensional spectral problems yield an intricate infinite classification theory determining which spectral problems can be solved and with which type of algorithm. This is very much related to S. Smale’s comprehensive program on the foundations of computational mathematics initiated in the 1980s. We classify the computation of geometric features of spectra in the SCI hierarchy, allowing us to precisely determine the boundaries of what computers can achieve (in any model of computation) and prove that our algorithms are optimal. We also provide a new universal technique for establishing lower bounds in the SCI hierarchy, which both greatly simplifies previous SCI arguments and allows new, formerly unattainable, classifications.
Notes
Communicated by Felipe Cucker.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
This paper resolves open computational spectral problems related to geometric features of spectra of operators. In other words, we consider the following problem:
Are there algorithms that given a bounded1 operator \(A\in {\mathcal {B}}(l^2({\mathbb {N}}))\), approximate key geometric features (e.g. spectral gaps, notions of sizes and capacity, measures, topological features such as fractal dimensions, etc.) of the set \(\textrm{Sp}(A)\) from a matrix representation of A?
To answer this question, we use the newly established solvability complexity index (SCI) hierarchy [18, 51, 91], a classification tool that determines the boundaries of what is computationally possible. Classifying spectral problems and providing a library of optimal algorithms2 remains largely uncharted territory in the foundations of computational mathematics. In exploring this territory, there will, necessarily, have to be many different types of algorithms, as different structures on the various classes of operators and different spectral properties require different techniques.
Advertisement
A famous example of the above question is the almost Mathieu operator on \(l^2({\mathbb {Z}})\) (see Sect. 4.4):
which induces the Hofstadter butterfly [92]. The almost Mathieu operator plays an important role in physics [104], arising in the study of the quantum Hall effect [160], and has become a laboratory for exploring the spectral properties of ergodic Schrödinger operators [95]. When \(\alpha \) is irrational, the Lebesgue measure of the spectrum is \(4\left| 1-\left| \lambda \right| \right| \). This formula was conjectured based on the numerical work of Aubry and André [8] and became one of B. Simon’s problems for the twenty-first century [146]. It was later proven by Avila and Krikorian [11]. Similarly, M. Kac’s “Ten Martini Problem”, that the spectrum is a Cantor set for all irrational \(\alpha \) and \(\lambda >0\), was conjectured by Azbel [13] and also became one of B. Simon’s problems. This problem attracted a host of numerical and analytical work (see the summary in [104]), before being proven by Avila and Jitomirskaya [9]. In both of these examples, we see a crucial interplay between computation, conjecture, and mathematical proof. The above geometric features of spectra play an important role in the physics of the underlying quantum system [90, 99, 100, 147]. The almost Mathieu operator is by no means unique in this regard, and there is a growing literature on computational studies of geometric features of spectra in diverse areas of physics [14, 68, 83, 94, 103, 106, 110, 120, 125, 133, 138, 139, 156, 161].
However, there is a current lack of rigorous computational theory and convergence analysis, and no known algorithms can tackle general cases. Moreover, the foundations of computation (i.e. what is and what is not computationally possible) for computing geometric features of spectra are almost entirely unexplored. We solve these open problems and others by providing algorithms that compute geometric features of spectra and by classifying the computational problems in the SCI hierarchy.
1.1 The SCI Hierarchy
The SCI hierarchy has recently been used to resolve the problem of computing spectra of general bounded operators in infinite dimensions [18, 91] and is now being used to explore the foundations of computation in many diverse areas of mathematics [2, 15, 16, 19‐23, 30, 52, 53, 55, 57, 59, 60, 64, 140, 141, 166].3 Whilst for some classes of operators one can compute spectra with error control [54, 60, 64], a potentially surprising consequence is that, for general operators, one needs several successive limits to compute the spectrum. Since traditional approaches are dominated by techniques based on one limit, this explains why many computational spectral problems remain unsolved and opens the door to an infinite classification theory. Moreover, this phenomenon is not just restricted to spectral problems but is shared by other areas of computational mathematics. An example is S. Smale’s problem of root-finding of polynomials with rational maps [149], which also requires several successive limits as established by McMullen [115, 116] and Doyle and McMullen [70]. These results can be expressed in terms of the SCI hierarchy [18], which generalises Smale’s seminal work [148, 150] with Blum et al. [28, 29, 66], and his program on the foundations of scientific computing and the existence of algorithms. Many other problems in the foundations of computations, such as the work by Weinberger [167], can also be viewed in the context of the SCI hierarchy.
The SCI hierarchy is further motivated by computer-assisted proofs. Computer-assisted proofs are rapidly becoming an essential part of modern mathematics [86] and, perhaps surprisingly, non-computable problems can be used in computer-assisted proofs. Examples include the recent proof of Kepler’s conjecture (Hilbert’s 18th problem) [87, 88] on optimal packings of 3-spheres, led by T. Hales, and the Dirac–Schwinger conjecture on the asymptotic behaviour of ground states of certain Schrödinger operators, proven in a series of papers by Fefferman and Seco [72‐80]. Both of these proofs rely on computing non-computable problems. This apparent paradox can be explained by the SCI hierarchy (the \(\Sigma ^A_1\) and \(\Pi _1^A\) classes described below become available for computer-assisted proofs); Hales, Fefferman and Seco implicitly prove \(\Sigma ^A_1\) classifications in the SCI hierarchy in their papers. Some of the problems we consider also lie in \(\Sigma ^A_1\cup \Pi _1^A\), meaning that they can be used for computer-assisted proofs.
Advertisement
1.2 The Problems Addressed in this Paper
The algorithms we provide are sharp in the SCI hierarchy, meaning that they realise the boundaries of what computers can achieve. Table 1 provides a summary of the main SCI classifications of this paper. The main theorems are contained in Sect. 3, including further motivations and classifications for different classes of operators. We provide resolutions to the following problems:
(i)
Computing spectral radii, essential spectral radii, polynomial operator norms and capacity of spectra. The spectral radius is perhaps the most basic geometric property of spectra and arises in stability analysis. We show that computing the spectral radius is high up in the SCI hierarchy for non-normal operators. In fact, it has the same classification in the SCI hierarchy for general bounded operators as that of computing the spectrum itself. Classifications are given for different types of operators (e.g. known column decay, control on resolvent norms) and also for the essential spectral radius. In many cases, the problem of computing polynomial operator norms is easier in the sense of SCI hierarchy. We also consider the problem of computing the logarithmic capacity of the spectrum, following the work of Halmos [89], which has applications in orthogonal polynomials, approximation theory and when studying the convergence of Krylov methods (see, for example, the work of Nevanlinna [121‐123] and Miekkala and Nevanlinna [117]).
(ii)
Computing essential numerical ranges, gaps in essential spectra, and determining whether spectral pollution occurs on sets. We provide classification results for the essential numerical range, which also hold in the case of unbounded operators. In connection with computing spectra, there has been a substantial effort in studying the finite section method and locating gaps in essential spectra of operators (see the discussion in Sect. 3.4). When using the finite section method to approximate spectra of self-adjoint operators, spurious eigenvalues, known as spectral pollution, can occur anywhere within these gaps. Paradoxically, we show that determining if spectral pollution occurs on a given set is strictly harder in the sense of the SCI hierarchy than computing the spectrum itself. Hence, computing a failure flag for the finite section method is, in a certain sense, strictly harder than solving the original problem for which it was designed. Moreover, we establish the SCI of detecting gaps in essential spectra of self-adjoint operators, a problem that arises in areas such as perturbation theory and defect models.
(iii)
Computing Lebesgue measure of spectra and pseudospectra, and determining if the spectrum is Lebesgue null. An important property of the spectrum is its Lebesgue measure, with recent progress in the field of Schrödinger operators with random or almost periodic potentials [9, 11, 12, 17, 135]. If the spectrum of an operator is Lebesgue null; then, this implies the absence of absolutely continuous spectra,4 which is related to transport properties if the operator represents a Hamiltonian. Whilst results are known for specific one-dimensional examples such as the almost Mathieu operator [11] or the Fibonacci Hamiltonian [154], very little is known in the general case or higher dimensions. This is reflected by the difficulty of performing rigorous numerical studies, despite many examples studied in the physics literature (see the references in [10, 24, 147]). We provide the first algorithms for computing the Lebesgue measure of spectra and pseudospectra, and determining whether the spectrum is Lebesgue null, for many different classes of operators.
(iv)
Computing fractal dimensions of spectra. Fractal dimensions of spectra are important in many applications. For example, in quantum mechanics, they lead to upper bounds on the spreading of wavepackets and are related to time-dependent quantities associated with wave functions [90, 99, 100]. Fractal spectra appear in a wide variety of contexts, such as exciting new results in multilayer materials (e.g. bilayer graphene) [68, 83, 94, 133], strained materials [120, 139] or quasicrystals [14, 103, 106, 156]. Another well-studied area where fractal spectral properties appear is optics [125, 138], following the analytical and numerical work of Berry and coauthors [25‐27]. Despite the physical importance of fractal dimensions, analytical results are known only for a limited number of specific models. Moreover, there are currently no algorithms for computing fractal dimensions of spectra for general operators, or even tridiagonal self-adjoint operators. We provide the first algorithms for computing the box-counting and Hausdorff dimensions of spectra for many different classes of operators.
1.3 Contributions to the SCI Hierarchy Itself
Our final contribution is a new tool to prove lower bounds (impossibility results) in the SCI hierarchy. This is crucial for some of the classifications of the above problems and holds regardless of the model of computation. We show that for a certain special class of combinatorial problems, the SCI hierarchy is equivalent to the Baire hierarchy from descriptive set theory. (This equivalence does not hold in general.) By embedding these combinatorial problems into spectral problems,5 we provide the first technique for dealing with problems that have SCI greater than three and also greatly simplify the proofs of results lower down in the SCI hierarchy. However, it should be stressed that this is not a paper on descriptive set theory or mathematical logic. Our discussion is entirely self-contained and written for a wide audience from a primarily computational background.
1.4 Outline of Paper
In Sect. 2, we provide a brief summary of the SCI hierarchy and define the classes of operators for the interpretation of Table 1 and the main results. A detailed discussion of the SCI hierarchy is delayed until Sect. 5.1. In Sect. 3, we summarise our main results on the classification of computational spectral problems. Computational examples are then given in Sect. 4. For example, we provide numerical evidence that a portion of the spectrum of the graphical Laplacian on an infinite Penrose tile is Lebesgue null and fractal, with a fractal dimension of approximately 0.8, and that the whole spectrum has a logarithmic capacity of approximately 2.26. Mathematical preliminaries, including definitions of the SCI hierarchy and the new tool to provide lower bounds in the SCI hierarchy, are presented in Sect. 5. Proofs of our results are given in Sects. 6–9. To make the paper self-contained, we include a short appendix on the results/algorithms of [64], which are used in some of our proofs. Pseudocode for many of the new algorithms is provided in “Appendix B”.
Table 1
Summary of the main results for the readable information \(\Lambda _1\) consisting of matrix values
Description of problem
SCI hierarchy classification
Theorem
Computing the spectral radius.
Varies. e.g. Normal operators: \(\in \Sigma _1^A\), \(\not \in \Delta _1^G\)
The main theorems contain classifications for different classes of operators (see Table 3 for the operator classes)
2 Essentials of the SCI Hierarchy and Preliminary Definitions
2.1 A Brief Introduction to the SCI Hierarchy
2.1.1 Description of the SCI Hierarchy
First, we define a computational problem. The basic objects of a computational problem are:
\(\Omega \), called the domain,
\(\Lambda \), a set of complex-valued functions on \(\Omega \), called the evaluation set,
\(({\mathcal {M}},d)\), a metric space,
\(\Xi :\Omega \rightarrow {\mathcal {M}}\) the problem function.
The set \(\Omega \) is the set of objects that give rise to our computational problems, the goal being to compute the problem function \(\Xi : \Omega \rightarrow {\mathcal {M}}\). The set \(\Lambda \) is the collection of functions that provide us with the information we are allowed to read as input to the algorithm. This leads to the following definition:
Definition 2.1
(Computational problem) Given a domain \(\Omega \); an evaluation set \(\Lambda \), such that for any \(A_1, A_2 \in \Omega \), \(A_1 = A_2\) if and only if \(f(A_1) = f(A_2)\) for all \(f \in \Lambda \); a metric space \({\mathcal {M}}\); and a problem function \(\Xi :\Omega \rightarrow {\mathcal {M}}\), we call the collection \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\) a computational problem.
The definition of a computational problem is deliberately general. The SCI of a computational problem is the smallest number of successive limits needed to compute the solution to the problem. We call a corresponding suitably indexed family of algorithms a ‘tower of algorithms’. In addition, we will use finer notions of error control. For example, consider the case that \(({\mathcal {M}},d)\) is the space of non-empty compact subsets of \({\mathbb {C}}\), equipped with the Hausdorff metric. Then, the SCI hierarchy [18, 51] can be described as follows.
The SCI hierarchy Given a collection \({\mathcal {C}}\) of computational problems,
(i)
\(\Delta ^{\alpha }_0 = \Pi ^{\alpha }_0 = \Sigma ^{\alpha }_0\) is the set of problems that can be computed in finite time (the SCI \(=0\)). In other words, \(\exists \) an algorithm \(\Gamma \) such that \(\Gamma (A)=\Xi (A), \forall A\in \Omega \).
(ii)
\(\Delta ^{\alpha }_1\) is the set of problems that can be computed using one limit (the SCI \(=1\)) with control of the error, i.e. \(\exists \) a sequence of algorithms \(\{\Gamma _n\}\) such that \(d(\Gamma _n(A), \Xi (A)) \le 2^{-n}, \, \forall A \in \Omega \).
(iii)
\(\Sigma ^{\alpha }_1\): We have \(\Delta ^{\alpha }_1 \subset \Sigma ^{\alpha }_1 \subset \Delta ^{\alpha }_2 \) and \(\Sigma ^{\alpha }_1\) is the set of problems for which \(\exists \) a sequence of algorithms \(\{\Gamma _n\}\) such that \(\forall A \in \Omega \) we have \(\Gamma _n(A) \rightarrow \Xi (A)\) as \(n \rightarrow \infty \). Moreover, \(\sup _{z\in \Gamma _n(A)}\textrm{dist}(z,\Xi (A))\le 2^{-n}\), where \(\textrm{dist}(x,S)\) denotes the Euclidean distance of x to S.
(iv)
\(\Pi ^{\alpha }_1\): We have \(\Delta ^{\alpha }_1 \subset \Pi ^{\alpha }_1 \subset \Delta ^{\alpha }_2 \) and \(\Pi ^{\alpha }_1\) is the set of problems for which \(\exists \) a sequence of algorithms \(\{\Gamma _n\}\) such that \(\forall A \in \Omega \) we have \(\Gamma _n(A) \rightarrow \Xi (A)\) as \(n \rightarrow \infty \). Moreover, \(\sup _{z\in \Xi (A)}\textrm{dist}(z,\Gamma _n(A))\le 2^{-n}\).
(v)
\(\Delta ^{\alpha }_2\) is the set of problems that can be computed using one limit (SCI \(=1\)) without error control, i.e. \(\exists \) a sequence of algorithms \(\{\Gamma _n\}\) such that \(\lim _{n\rightarrow \infty }\Gamma _n(A) = \Xi (A), \, \forall A \in \Omega \).
(vi)
\(\Delta ^{\alpha }_{m+1}\), for \(m \in {\mathbb {N}}\), is the set of problems that can be computed by using m successive limits, (SCI \(\le m\)), i.e. \(\exists \) a family of algorithms \(\{\Gamma _{n_m, \ldots , n_1}\}\) such that
\(\Sigma ^{\alpha }_{m}\) is the set of problems in \(\Delta ^{\alpha }_{m+1}\) such that, letting \(\Gamma _{n_m}(A)=\lim _{n_{m-1} \rightarrow \infty }\cdots \lim _{n_1\rightarrow \infty }\Gamma _{n_m,\ldots , n_1}(A)\), \(\sup _{z\in \Gamma _{n_m}(A)}\textrm{dist}(z,\Xi (A))\le 2^{-n_m}\). In other words, computing the mth limit is a \(\Sigma ^{\alpha }_1\) problem.
(viii)
\(\Pi ^{\alpha }_{m}\) is the set of problems in \(\Delta ^{\alpha }_{m+1}\) such that \(\sup _{z\in \Xi (A)}\textrm{dist}(z,\Gamma _{n_m}(A))\le 2^{-n_m}\). In other words, computing the mth limit is a \(\Pi ^{\alpha }_1\) problem.
Schematically, the SCI hierarchy can be viewed in the following way:
A visual demonstration of these classes is shown in Fig. 1. For the description for decision problems, see Sect. 5.1. The \(\Sigma _1^{\alpha }\) and \(\Pi _1^{\alpha }\) classes become crucial in computer-assisted proofs (see below).
Fig. 1
Meaning of \(\Sigma _1\) and \(\Pi _1\) convergence for a problem function \(\Xi \) computed in the Hausdorff metric. The red areas represent \(\Xi (A)\), whereas the green areas represent the output of the algorithm \(\Gamma _n(A)\). \(\Sigma _1\) convergence means convergence as \(n\rightarrow \infty \) but each point in the output \(\Gamma _n(A)\) is at most distance \(2^{-n}\) from \(\Xi (A)\). Similarly, in the case of \(\Pi _1\), we have convergence as \(n\rightarrow \infty \) but any point in \(\Xi (A)\) is at most distance \(2^{-n}\) from \(\Gamma _n(A)\) (Color figure online)
×
×
Remark 2.2
(Computability, not complexity) It is important to note that (despite its name) the SCI hierarchy is a hierarchy for classifying computability, not complexity. Most computational spectral problems of interest are \(\notin \Delta _1\) in the SCI hierarchy, and complexity theory only makes sense for problems in \(\Delta _1\). Hence, it is impossible to build a complexity theory for most infinite-dimensional spectral problems. The scientific community computes with non-computable problems (\(\notin \Delta _1\)) on a daily basis (e.g. in quantum mechanics). This also happens in high-profile computer-assisted proofs (see below). \(\square \)
2.1.2 The Model of Computation \(\alpha \)
The \(\alpha \) in the superscript indicates the model of computation, which is described in Sect. 5.1. For \(\alpha = G\), the underlying algorithm is general (see Definition 5.1) and can use any tools at its disposal. The reader may think of a Blum–Shub–Smale (BSS) machine or a Turing machine with access to any oracle, although a general algorithm is even more powerful. However, for \(\alpha = A\) this means that only arithmetic operations and comparisons are allowed. In particular, if rational inputs are considered, the algorithm is a Turing machine, and in the case of real inputs, a BSS machine. Hence, a result of the form
$$\begin{aligned} \notin \Delta _k^G \text { is stronger than } \notin \Delta _k^A. \end{aligned}$$
Indeed, a \(\notin \Delta _k^G\) result is universal and holds for any model of computation. Moreover,
$$\begin{aligned} \in \Delta _k^A \text { is stronger than } \in \Delta _k^G, \end{aligned}$$
and similarly for the \(\Pi _k\) and \(\Sigma _k\) classes. In this paper, we prove lower bounds for \(\alpha = G\) and upper bounds for \(\alpha = A\), thus obtaining the strongest results. Remark 5.12 discusses further how the model of computation is of less importance in infinite dimensions.
2.1.3 Computer-Assisted Proofs
The class of problems \(\Delta _1^A\) are precisely those that are computable according to Turing’s definition of computability (i.e. there exists an algorithm such that for any \(\epsilon > 0\) the algorithm can produce an \(\epsilon \)-accurate output). However, most infinite-dimensional spectral problems are \(\notin \Delta _1^A.\) The simplest example is the problem of computing spectra of infinite diagonal matrices. Very few interesting infinite-dimensional spectral problems are actually in \(\Delta _1^A\), and most of the literature on spectral computations provides algorithms that yield \(\Delta _2^A\) classification results. Such algorithms converge, but may not provide error control. In many cases, error control is impossible.
Problems not in \(\Delta _1^A\) are a daily occurrence in the sciences due to suggestive numerical simulations or evidence based on experiments. However, in the field of computer-assisted proofs, this is not possible, since only \(100\%\) rigour is accepted. Nevertheless, there are many examples of famous conjectures that have been proven using computational problems that do not lie in \(\Delta _1^A\). For example, the proof of Kepler’s conjecture (Hilbert’s 18th problem) [87, 88] relies on decision problems that are not in \(\Delta _1^A\) [15]. Another example is C. Fefferman and L. Seco’s proof of the Dirac–Schwinger conjecture on the asymptotics of ground states of certain Schrödinger operators [72‐80]. The reason for this apparent paradox is that the \(\Sigma ^A_1\) and \(\Pi ^A_1\) classes are larger than \(\Delta ^A_1\), but can still be used in computer-assisted proofs. Both of the above examples implicitly prove \(\Sigma ^A_1\) classifications. For example, suppose we have a computational spectral problem that lies in \(\Sigma ^A_1\). This means that there is an algorithm that will converge and never provide incorrect output, up to a user-specified error bound. Thus, conjectures about operators never having spectra in a certain area (a common problem in stability analysis, for example) could be disproved by a computer-assisted proof. Recent results using computer-assisted proofs in spectral theory include [33, 111].
2.2 Evaluation Sets and Domains
Throughout this paper, unless otherwise specified, A will be a bounded operator acting on the canonical Hilbert space \(l^2({\mathbb {N}})\) (we define \(\Omega _{\textrm{B}}:={\mathcal {B}}(l^2({\mathbb {N}}))\)), and realised as a matrix with respect to the canonical basis. However, the results of this paper extend to general separable Hilbert spaces \({\mathcal {H}}\) through a choice of orthonormal basis \(e_1,e_2,\ldots \) if one can compute the matrix values of the operators with respect to this basis (see the discussion of the evaluation sets below). For example, we can treat operators naturally defined on lattices such as \({\mathbb {Z}}^d\), or more generally on graphs. Such operators are abundant in mathematical physics. Below we give the evaluation sets and classes of operators treated in this paper. For convenience, this information is summarised in Tables 2 and 3.
Table 2
Summary of evaluation sets used in this paper
Evaluation set
Information available to algorithm
Meaning
\(\Lambda _1\)
\(f^1_{i,j}: A\mapsto \langle Ae_j,e_i\rangle \) for \(i,j\in {\mathbb {N}}\)
Matrix entries of A
\(\Lambda _2\)
\(f^1_{i,j}: A\mapsto \langle Ae_j,e_i\rangle \) for \(i,j\in {\mathbb {N}}\)
Matrix entries of A, \(A^*A\), and \(AA^*\)
\(f^2_{i,j}: A\mapsto \langle Ae_j,Ae_i\rangle \) for \(i,j\in {\mathbb {N}}\)
\(f^3_{i,j}: A\mapsto \langle A^*e_j,A^*e_i\rangle \) for \(i,j\in {\mathbb {N}}\)
Table 3
Summary of classes of operators treated in this paper
Note that all considered classes lie in \(\Omega _\textrm{B}\), and that \(\Omega _\textrm{D}\subset \Omega _\textrm{SA}\subset \Omega _\textrm{N}\), \(\Omega _\textrm{D}\subset \Omega _f\), and \(\Omega _\textrm{N}\subset \Omega _{g:x\mapsto x}\)
2.2.1 Evaluation Sets
We consider two natural sets of information that our algorithms can read. The first, \(\Lambda _1\), provides the entries of the matrix representation of A with respect to the canonical basis \(\{e_i\}_{i\in {\mathbb {N}}}\):
The second, \(\Lambda _2\), appends \(\Lambda _1\) with the entries of the matrix representations of \(A^*A\) and \(AA^*\) with respect to the canonical basis \(\{e_i\}_{i\in {\mathbb {N}}}\):
We include \(\Lambda _2\) since it is natural for problems posed in variational form, and can often be evaluated through numerical integration. When considering classes with functions f (and \(\{c_n\}\)) and g as in (2.1) and (2.2) below, we will add these to the relevant evaluation set (evaluating g at rational points) and with an abuse of notation still use the notation \(\Lambda _i\). A small selection of the problems also require additional information, such as when testing if a set intersects a spectral set, but any changes to \(\Lambda _i\) will be pointed out where appropriate.
2.2.2 Classes of Operators
Let \(\Omega _\textrm{N}\) denote the class of normal operators in \(\Omega _{\textrm{B}}\), \(\Omega _{\textrm{SA}}\) denote the class of self-adjoint operators in \(\Omega _\textrm{N}\), and \(\Omega _\textrm{D}\) denote the class of self-adjoint diagonal operators in \(\Omega _{\textrm{SA}}\). For \(f:{\mathbb {N}}\rightarrow {\mathbb {N}}\), \(f(n)\ge n+1\) define
where \(P_m\) is the orthogonal projection onto \(\textrm{span}\{e_1,\ldots , e_m\}\). Given such an f, we assume access to an estimate \(D_{f,n}(A) \le c_n(A)\in {\mathbb {Q}}_{\ge 0}\), where \(c_n \rightarrow 0\) as \(n \rightarrow \infty \). We let \(\Omega _f\) denote the class of bounded operators with known function f and \(\{c_n\}\).6 As a special case, if we know our matrix is sparse with finitely many nonzero entries in each column and row (and we know the positions of the nonzero entries) then we know an f with \(c_n=0\). Let \(g:{\mathbb {R}}_{+}\rightarrow {\mathbb {R}}_{+}\) be a strictly increasing, continuous function that vanishes only at 0 with \(\lim _{x\rightarrow \infty }g(x)=\infty \). Let \(\Omega _g\) be the class of bounded operators with
for \(z\in {\mathbb {C}}\), where \(R(z,A)=(A-zI)^{-1}\). A simple compactness argument shows that such a g always exists for any given \(A\in \Omega _{\textrm{B}}\). However, the classification of spectral problems in the SCI hierarchy generally depends on whether one knows an estimate for g or not. For example, in the self-adjoint and normal cases, \(g(x) = x\) is the trivial choice of g. Operators with \(g(x) = x\) are known as \(G_1\) and include the well-studied class of hyponormal operators (operators with \(A^*A-AA^*\ge 0\)) [136]. A common assumption is that
for some constant C, which is equivalent to \(A\in \Omega _g\) with \(g(x)=x/C\). For example, if A is similar to a normal operator with a similarity transformation S that has bounded condition number \(\kappa (S)\), we can take \(C=\kappa (S)\). Other examples with nonlinear g include perturbations of self-adjoint operators [84, e.g. Theorem 7.7.1]. More generally, one can view the function g as a measure of stability of the spectrum of A through the formula
where \(\textrm{Sp}_{\epsilon }(A)\) denotes the (\(\epsilon \)-)pseudospectrum of A [162]. The function g is held fixed for a given class \(\Omega _g\) and a smaller g leads to a larger class of operators \(\Omega _g\).
3 Main Results: The Foundations of Computing Geometric Features of Spectra
Our results classify computing geometric features of spectra in the SCI hierarchy. In other words, we are concerned with the foundations of computation for geometric features of spectra. There are two aspects of this classification: proving impossibility results (lower bounds), where we make use of the tools developed in Sect. 5 and Theorem 5.19, and proving upper bounds through the construction of algorithms. This ensures that our algorithms realise the boundary of what computers can achieve in spectral computations. We have included routines for some of the main algorithms in “Appendix B” and computational examples in Sect. 4.
Remark 3.1
(Bounding the operator norm) The proofs of lower bounds make clear that all classifications still hold if we replace the respective sub-class \(\Omega \subset \Omega _{\textrm{B}}\) by the restriction to operators in \(\Omega \) having operator norm at most \(M\in {\mathbb {R}}_{>0}\), adding such a value M (constant function) to the evaluation set \(\Lambda \).\(\square \)
Remark 3.2
(Computing the resolvent norm) Some of the algorithms are built on the local approximation of the functions (or similar functions) defined by
The functions \(\gamma _{n}\) converge to the resolvent norm \(\Vert R(z,A)\Vert ^{-1}\) uniformly on compact subsets of \({\mathbb {C}}\) from above as \(n\rightarrow \infty \). This idea was crucial in [60, 64] to compute spectra with \(\Sigma _1^A\) error control for a large class of operators. A theme of some of our proofs, especially those concerning Lebesgue measure and fractal dimensions, is the extension of these ideas to compute geometric properties of the spectrum.\(\square \)
3.1 Spectral Radii
We begin with a very simple geometric feature of the spectrum. The spectral radius, r(A), of a bounded operator A is the supremum of the absolute values of members of the spectrum, which is attained. Spectral radii commonly appear in applications involving stability analysis. We set \(\Xi _r(A):=r(A)\) and make the following initial observations:
(i)
One can easily show that the computational problem of the operator norm of any \(A\in \Omega _{\textrm{B}}\) lies in \(\Sigma _1^A\). Hence, since \(r(A)\le \left\| A\right\| \), we can easily get an upper bound for \(\Xi _r(A)\) in one limit. Of course, if A is not normal, this upper bound may not agree with \(\Xi _r(A)\).
(ii)
If an operator lies in \(\Omega _g\) with \(g(x)=x\), then the convex hull of the spectrum is equal to the closure of the numerical range (recall that the numerical range is \(\{\langle Ax,x\rangle :\Vert x\Vert =1\}\)) [131]. Such operators are known as convexoid and the problem of computing \(\Xi _r(A)\) for such operators lies in \(\Sigma _1^A\).
(iii)
In light of Gelfand’s famous formula \(\Xi _r(A)=\lim _{n\rightarrow \infty }\Vert A^n\Vert ^{\frac{1}{n}}\), one might expect that the computation of \(\Xi _r(A)\) is strictly easier in the sense of the SCI hierarchy than that of the spectrum.
The following shows that the intuition in (iii) is misguided in general and only occurs if an operator is convexoid as in (ii). Computing \(\Xi _r(A)\) is just as hard as computing the spectrum for the class \(\Omega _{\textrm{B}}\). Controlling the resolvent via a function g as in (2.2) makes the problem easier in the sense of SCI hierarchy than the general class \(\Omega _{\textrm{B}}\), but is not sufficient to reduce the SCI of the problem to 1.
Theorem 3.3
Let \(g:{\mathbb {R}}_{+}\rightarrow {\mathbb {R}}_{+}\) be a strictly increasing, continuous function that vanishes only at 0 with \(\lim _{x\rightarrow \infty }g(x)=\infty \). In addition, suppose that \(g(x)\le (1-\delta )x\) for some \(\delta \in (0,1)\). Then:
The \(\Pi _2^A\) algorithm for \(\{\Xi _r,\Omega _f\}\) does not need a null sequence \(\{c_n\}\) bounding the dispersion, \(D_{f,n}(A)\le c_n\), to be sharp in the SCI hierarchy since this is absorbed in the first limit.\(\square \)
Remark 3.5
The proofs of the lower bounds in Theorem 3.3 for \(\Omega _g\) require g with the stated additional property and \(\delta >0\). In particular, the lower bound does not cover the smaller class of \(G_1\) operators.\(\square \)
3.2 Essential Spectral Radii
Next, we consider the essential spectral radius. Define the essential spectrum of \(A\in \Omega _{\textrm{B}}\) as
where \(\Omega _K\) denotes the class of compact operators. The essential spectral radius, \(\Xi _{er}(A)\), is simply the supremum of the absolute values over \(\textrm{Sp}_{\textrm{ess}}(A)\).
Theorem 3.6
We have the following classifications for \(i=1,2\):
Given a polynomial p of degree at least two,7 we consider the problem of computing \(\Xi _{r,p}=\Vert p(A)\Vert \) and the capacity of the spectrum defined by
A theorem of Halmos shows that this definition of capacity agrees with the usual potential-theoretic definition of capacity of the set \(\textrm{Sp}(A)\) [89]. Roughly speaking, the capacity measures the ability of \(\textrm{Sp}(A)\) to hold electrical charge. We will also see some other measures of size in Sects. 3.5 and 3.6. The capacity of the spectrum is of particular interest in Krylov methods where, for instance, it is related to the speed of convergence8 [117, 119, 121‐123]. The capacity is also an important object in local spectral theory [1, 105, 119], and related work [48, 124] includes methods for computing the polynomially convex hull of an operator. The following theorem provides the relevant SCI classifications.
Theorem 3.7
We have the following classifications for \(i=1,2\) and \({{\hat{\Omega }}}=\Omega _\textrm{D}\) or \(\Omega _f\):
The proof shows these problems have the same classifications for \(\Omega _\textrm{SA}\) as \(\Omega _\textrm{N}\). Somewhat surprising is the result that the computation of \(\Vert p(A)\Vert \) requires two successive limits for self-adjoint operators. The proof shows that one reason for this is spectral pollution associated with finite section methods.
3.4 Essential Numerical Range, Gaps in Essential Spectra and Detecting Failure of Finite Section
We now consider geometric features of spectra that are related to the finite section method, the most intensely studied computational method of approximating spectra [35, 36, 40, 41].9 The basic form of the finite section method approximates the spectrum of A by \(\textrm{Sp}(P_nA|_{P_n{\mathcal {H}}})\), where \(\{P_m\}\) is a sequence of finite-dimensional projections converging strongly to the identity as \(m\rightarrow \infty \). The computation is often done with finite element, finite difference or spectral methods by discretising the operator on a suitable finite-dimensional space [31, 32, 47, 50, 102, 108, 137, 168]. Even when A is self-adjoint, spurious eigenvalues, that have nothing to do with \(\textrm{Sp}(A)\), can accumulate anywhere within gaps of the essential spectrum as \(n\rightarrow \infty \).10 This is known as spectral pollution. More precisely, the essential numerical range of \(A\in \Omega _{\textrm{B}}\) is defined as
where \(W(A)=\{\langle Ax,x\rangle :\Vert x\Vert =1\}\) is the usual numerical range.11 We recall the following two theorems.
Theorem 3.8
(Pokrzywa [132]) Let \(A \in {\mathcal {B}}({\mathcal {H}})\) and let \(\{P_n\}\) be a sequence of finite-dimensional projections converging strongly to the identity. Suppose that \(S \subset W_e(A).\) Then there exists a sequence \(\{Q_n\}\) of finite-dimensional projections such that \(P_n < Q_n\) (so \(Q_n \rightarrow I\) strongly) and
where \(d_{\textrm{H}}\) denotes the Hausdorff distance.
Theorem 3.9
(Pokrzywa [132]) Let \(A \in {\mathcal {B}}({\mathcal {H}})\) and let \(\{P_n\}\) be a sequence of finite-dimensional projections converging strongly to the identity. If \(\lambda \notin W_e(A)\), then \(\lambda \in \textrm{Sp}(A)\) if and only if
Theorems 3.8 and 3.9 show that spectral pollution is confined to the essential numerical range and can be arbitrarily bad in \(W_e(A)\backslash \textrm{Sp}(A)\).12 For self-adjoint operators, the gaps in the essential spectrum correspond exactly to \(W_e(A)\backslash \textrm{Sp}(A)\). As a result, there has been considerable attention towards methods that detect gaps in essential spectra and eigenvalues within these gaps [31, 49, 108, 144], as well as studying the precise nature of spectral pollution [107, 112, 113, 137].
A consequence of the main result of this section, Theorem 3.10, is that detecting these gaps is strictly harder in the sense of the SCI hierarchy than computing the spectrum for self-adjoint operators (which was classified in [18, 60, 64]). We define the problem function \(\Xi _{we}(A)=W_e(A)\). For a given non-empty open set U in \({\mathbb {F}}\) (with \({\mathbb {F}}\) being \({\mathbb {C}}\) or \({\mathbb {R}}\)), let \(\Xi _{poll}^{{\mathbb {F}}}\) be the decision problem
\(\Xi _{poll}^{{\mathbb {F}}}\) decides whether spectral pollution can occur on the closed set \({\overline{U}}\). For the self-adjoint case and \({\mathbb {F}}={\mathbb {R}}\), this is equivalent to asking whether there exists a point in the open set U that also lies in a gap of the essential spectrum. To incorporate U into \(\Lambda _i\), we allow access to a countable number of open balls \(\{U_m\}_{m\in {\mathbb {N}}}\) whose union is U. If \({\mathbb {F}}={\mathbb {R}}\), then each \(U_m\) is of the form \((a_m,b_m)\) with \(a_m,b_m\in {\mathbb {Q}}\cup \{\pm \infty \}\). If \({\mathbb {F}}={\mathbb {C}}\), then each \(U_m\) is equal to \(D_{r_m}(z_m)\) (the open ball of radius \(r_m\) centred at \(z_m\)) with \(r_m\in \mathbb {Q_+}\cup \{\infty \}\) and \(z_m\in {\mathbb {Q}}+i{\mathbb {Q}}\). We add pointwise evaluations of the relevant sequences \(\{(a_m,b_m)\}\) or \(\{(r_m,z_m)\}\) to \(\Lambda _i\).
Theorem 3.10
(Computation of essential numerical range and whether spectral pollution can occur on a set) Let \(\Omega =\Omega _\textrm{N},\Omega _\textrm{SA}\) or \(\Omega _{\textrm{B}}\) and let \(i=1,2\). Then
(Computing spectra is easier than algorithmically determining whether spectral pollution can occur on a set) One can show that \(\{\textrm{Sp}(\cdot ),\Omega _\textrm{SA},\Lambda _1\}\in \Sigma _2^A\) and \(\{\textrm{Sp}(\cdot ),\Omega _\textrm{SA},\Lambda _2\}\in \Sigma _1^A\). Hence determining \(\Xi _{poll}^{\mathbb {R}}\) is strictly harder than the spectral computational problem and requires two additional successive limits if \(\Lambda =\Lambda _2\). Even in the general case, \(\{\textrm{Sp}(\cdot ),\Omega _{\textrm{B}},\Lambda _2\}\in \Pi _2^A\) and hence the spectral problem is strictly easier in the sense of SCI hierarchy. The proofs also make clear that we get the same classification of \(\Xi _{poll}^{{\mathbb {F}}}\) for other classes such as \(\Omega _\textrm{N}\), \(\Omega _g\) etc.\(\square \)
Remark 3.12
(Unbounded operators) In Sect. 7.1, we show that computing the essential numerical range for closed unbounded operators T on \(l^2({\mathbb {N}})\) (under the condition that the linear span of the canonical basis forms a core of T) also lies in \(\Pi _2^A\). The definition of the essential numerical range for such operators was recently given in [34]. This paper showed that \(W_e(T)\) consists precisely of the essential spectrum of T together with all possible spectral pollution that may arise by applying projection methods to approximate the spectrum of T, thus generalising Theorems 3.8 and 3.9. A computational example is given in Sect. 4.2.\(\square \)
3.5 Lebesgue Measure of Spectra
A basic property of the set \(\textrm{Sp}(A)\), also connected to physical applications, is its Lebesgue measure. Well-studied operators such as the almost Mathieu operator at critical coupling [11] or the Fibonacci Hamiltonian [154] have spectra with Lebesgue measure zero. Following [8], there have been many further numerical studies [157‐159]. For further examples of operators with numerical approximations of the Lebesgue measure, see the references in [10, 24, 147]. Numerical studies typically look at periodic approximates [134], and computing the Lebesgue measure of periodic approximates of tridiagonal operators lies in \(\Delta _1^A\). The tools we develop are more general and do not assume such structure. Verification of our algorithms for the almost Mathieu operator is presented in Sect. 4.4.
The Lebesgue measure on \({\mathbb {C}}\) will be denoted by \(\textrm{Leb}\). When considering classes of self-adjoint operators, we use the Lebesgue measure on \({\mathbb {R}}\) denoted by \(\textrm{Leb}_{{\mathbb {R}}}\). We also define
whose closure is \(\textrm{Sp}_\epsilon (A)\). For a class \(\Omega \subset \Omega _{\textrm{B}}\), there are three questions we answer in this section:
(1)
Given \(A\in \Omega \), can we compute \(\textrm{Leb}(\textrm{Sp}(A))\)?
(2)
Given \(A\in \Omega \) and \(\epsilon >0\), can we compute \(\textrm{Leb}(\widehat{\textrm{Sp}}_{\epsilon }(A))\)?13
(3)
Given \(A\in \Omega \), can we determine whether \(\textrm{Leb}(\textrm{Sp}(A))=0\)?
For the first two questions, we consider the metric space \(([0,\infty ),d)\) with the Euclidean metric. For question three, we consider the discrete metric on \(\{0,1\}\), where 1 is interpreted as “Yes”, and 0 as “No”. We denote the above problem functions by \(\Xi _1^{L},\Xi _2^{L}\) and \(\Xi _3^{L}\), respectively. In analogy to computing spectra and pseudospectra, \(\Xi _2^L\) is the easiest to compute and can be done in one limit for a large class of operators. It also follows from the dominated convergence theorem that
The algorithm constructed in the proof of Theorem 3.13 is local and can be adapted to find the Lebesgue measure of \(\textrm{Sp}(A)\) intersected with any compact interval or cube in one or two dimensions, respectively. Moreover, when considering \(\Omega _f\), we do not need the sequence \(\{c_n\}\), and the algorithm can be restricted to \({\mathbb {R}}\), where it converges to \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(A)\cap {\mathbb {R}})\). Our results also hold when considering bounded diagonal operators (dropping the restriction of self-adjointness) and using \(\textrm{Leb}\) instead of \(\textrm{Leb}_{{\mathbb {R}}}\).
We now turn to the SCI classification of \(\textrm{Leb}(\widehat{\textrm{Sp}}_{\epsilon }(A))\), which is useful since it provides a route to computing \(\textrm{Leb}(\textrm{Sp}(A))\) for any \(A\in \Omega _{\textrm{B}}\) via (3.3). This is a similar state of affairs to the computation of the spectrum itself—one can approximate the spectrum via pseudospectra.
Theorem 3.14
(Lebesgue measure of pseudospectra) Given the above set-up, we have the following classifications
Why is \(\Xi _2^L\) easier to compute than \(\Xi _1^L\)? Heuristically, the pseudospectrum is less refined than the spectrum, making the measure easier to approximate. Another viewpoint is the continuity points of the maps \(\Xi _1^L\) and \(\Xi _2^L\). For simplicity, consider these maps restricted to \(\Omega _\textrm{D}\) and equip these diagonal operators with the operator norm topology. The following shows that \(\Xi _2^L\) is more stable than \(\Xi _1^L\), explaining why it is easier to approximate. Again, this is the same state of affairs as comparing \(\textrm{Sp}(A)\) and \(\textrm{Sp}_{\epsilon }(A)\) as sets.
Proposition 3.15
In the above set-up, the following hold:
(1)
\(\Xi _1^L\) is continuous at \(A\in \Omega _\textrm{D}\) if and only if \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(A))=0\).
(2)
\(\Xi _2^L\) is continuous at all \(A\in \Omega _\textrm{D}\).
Finally, when computing \(\Xi _3^L\), we let \(({\mathcal {M}},d)\) be the set \(\{0,1\}\) endowed with the discrete topology and consider the problem function
It is straightforward to build a family of algorithms that converge in three successive limits for this problem using the algorithm constructed in Theorem 3.13 and its monotonicity. The next theorem shows that this is optimal, even for the set of diagonal self-adjoint bounded operators. This demonstrates how hard it is to solve decision problems about the spectrum with finite amounts of information, particularly when the problems involve an object that ignores countable sets, such as the Lebesgue measure.
Theorem 3.16
(Is the spectrum Lebesgue null?) Given the above set-up, we have the following classifications
These are the first examples of computational spectral problems that require four successive limits to compute in the SCI hierarchy. To prove this, we need some tools from descriptive set theory in Sect. 5. Note that we prove the lower bounds for general algorithms, so regardless of the model of computation.\(\square \)
3.6 Fractal Dimensions of Spectra
When considering operators from physical models, such as Schrödinger operators in quantum mechanics, fractal dimensions of spectra are related to important phenomena, such as the spreading of an initially localised wavepacket [101]. Further applications and numerical studies are already discussed in Sect. 1. However, estimating the fractal dimension is extremely difficult. This can be explained by the SCI hierarchy—the \(\textrm{SCI}>1\), even for computing the box-counting dimension, the most basic definition of fractal dimension. The Hausdorff dimension is even worse and has \(\text {SCI}\ge 3\). In this section, we exclusively treat self-adjoint operators and hence seek fractal dimensions of \(\textrm{Sp}(A)\subset {\mathbb {R}}\).14
Box-Counting Dimension: Let F be a bounded set in \({\mathbb {R}}\) and let \(N_{\delta }(F)\) be the number of closed intervals of length \(\delta >0\) required to cover F. We define the upper and lower box-counting dimensions as
When \(\overline{\textrm{dim}}_B(F)=\underline{\textrm{dim}}_B(F)\), we can replace the \(\liminf \) and \(\limsup \) by \(\lim \), and the common value is the box-counting dimension \(\textrm{dim}_B(F)\), an example of a fractal dimension. A possible drawback of the box-counting dimension is its lack of countable stability. For example, \(\textrm{dim}_B(\{0,1,1/2,1/3,\ldots \})=1/2\). Let \(\Omega _{f}^{BD}\) be the class of self-adjoint operators in \(\Omega _f\) (see (2.1)) whose upper and lower box-counting dimensions of the spectrum agree. Let \(\Omega _{\textrm{SA}}^{BD}\) be the class of self-adjoint operators whose upper and lower box-counting dimensions of the spectrum agree, and denote by \(\Omega _{\textrm{D}}^{BD}\) the class of diagonal operators in \(\Omega _{\textrm{SA}}^{BD}\).
Hausdorff Dimension: A more complicated, yet robust notion of fractal dimension is related to the Hausdorff measure [71, 114]. Let \(F\subset {\mathbb {R}}^n\) be a bounded Borel set and let \({\mathcal {C}}_{\delta }(F)\) denote the class of (countable) \(\delta \)-covers15 of F. One first defines the quantities (for \(d\ge 0\))
There is a unique \(d'=\textrm{dim}_{H}(F)\ge 0\), the Hausdorff dimension of F, such that \({\mathcal {H}}^{d}(F)=0\) for \(d>d'\) and \({\mathcal {H}}^{d}(F)=\infty \) for \(d<d'\). One can prove that
(When \(\underline{\textrm{dim}}_B(\textrm{Sp}(A))\ne \overline{\textrm{dim}}_B(\textrm{Sp}(A))\))The algorithms for \(\Xi _B\) also converge without the assumption that the upper and lower box-counting dimensions of \(\textrm{Sp}(A)\) agree, to a quantity \(\Gamma (A)\) with
One of the properties that makes the Hausdorff dimension harder to compute than the box-counting dimension is its countable stability, meaning that if F is countable then \(\textrm{dim}_H(F)=0\).\(\square \)
Remark 3.20
Some of our results have interpretations for real bounded sequences. Given such a sequence \(\{a_i\}_{i\in {\mathbb {N}}}\subset {\mathbb {R}}\), we can ask the same questions about \(\overline{\{a_1,a_2,\ldots \}}\) as we have asked about the spectrum. We can embed these problems as spectral problems for the class \(\Omega _\textrm{D}\) of bounded self-adjoint diagonal operators by simply considering diagonal operators with entries \(\{a_1,a_2,\ldots \}\). Theorems 3.13, 3.16 and 3.18 immediately then give the classifications. With regard to fractal dimensions, the key problem is to try and relate the amount of data that has been seen to the resolution obtained from the data (as highlighted in the computational example below). Once we have the framework of the SCI, we can immediately see why the problem is so difficult—the computational problem requires three successive limits for the Hausdorff dimension.\(\square \)
Finally, the following lemma is used in the construction of the tower of algorithms for computing the Hausdorff dimension but is interesting in its own right so is listed here.
Lemma 3.21
Let \((a,b)\subset {\mathbb {R}}\) be a finite open interval and let \(A\in \Omega _f\cap \Omega _\textrm{SA}\). Then determining whether \( \textrm{Sp}(A)\cap (a,b)\ne \emptyset \) using \(\Lambda _i\) is a problem with \(\textrm{SCI}_A=1\). Furthermore, we can design an algorithm that halts if and only the answer is “Yes”, that is, the problem lies in \(\Sigma ^A_1\). Similarly, the problem lies in \(\Sigma _2^A\) when considering \(\Omega _\textrm{SA}\) with \(\Lambda _1\) (or \(\Sigma _1^A\) when we allow access to \(\Lambda _2\)).
4 Computational Examples
In this section, we demonstrate that the SCI-sharp algorithms constructed in this paper can be efficiently implemented for large-scale computations. Moreover, the algorithms have desirable convergence properties, converging monotonically or being eventually constant, as captured by the \(\Sigma /\Pi \) classification. Generically, this monotonicity holds in all of the successive limits, and not just the final limit; many of the towers of algorithms undergo oscillation phenomena where each subsequent limit is monotone but in the opposite sense/direction than the limit beforehand. We can take advantage of this when analysing the algorithms numerically. The algorithms also highlight suitable information that lowers the SCI classification to \(\Sigma _1/\Pi _1\). Other advantages of the algorithms based on approximating the resolvent norm include locality, numerical stability and speed/parallelisation. In the examples that follow, we remind the reader what each parameter \(n_k\) intuitively does in the relevant algorithm and simplified routines for many of the algorithms can be found in “Appendix B”. Finally, we point the reader to Remark 5.12—all of the algorithms can be implemented rigorously using arithmetic operations over the rationals or with methods such as interval arithmetic.
4.1 Spectral Radius
We begin with the spectral radius and consider the upper-triangular non-normal operator on \(l^2({\mathbb {Z}})\) defined by its action on the canonical basis via
In this case, the operator norm of A is 2 and the approximation of the spectrum by finite section is \(\{0\}\). Hence, to compute the spectral radius, one must resort to the techniques used in our algorithms based on rectangular truncations. Recall that the SCI classification for computing the spectral radius of such operators (where the dispersion is known) is \(\Pi _2^A\) (see Theorem 3.3 for further classifications). The first parameter, \(n_1\), controls the size of the rectangular truncation16 (as well as the grid resolution), whereas the second, \(n_2\), controls the resolvent norm cut-off (\(\epsilon =1/n_2\)).
Figure 2 (left) shows the output of \(\Gamma _{n_2,n_1}(A)\) for computing the spectral radius. We see the expected monotonicity; \(\Gamma _{n_2,n_1}(A)\) is increasing in \(n_1\) but decreasing in \(n_2\). It appears that \(\lim _{n_1\rightarrow \infty }\Gamma _{10^2,n_1}(A)\approx \lim _{n_1\rightarrow \infty }\Gamma _{10^3,n_1}(A)\approx 1.4149\). The fact that these two values for different \(n_2\) are similar suggests that we have reached convergence. Though, of course, the proof that the problem does not lie in \(\Delta _2^G\) shows that we can never apply a choice of subsequences to gain convergence in one limit over the whole class \(\Omega _f\). Nevertheless, the approximate value of 1.4149 is confirmed in Fig. 2 (right) where we have shown pseudospectra, computed using the algorithm in [64].
Fig. 2
Left: Output of the algorithm for computing the spectral radius. Right: Pseudospectrum computed using the method of [64] (the colour scale corresponds to the resolvent norm \(\Vert (A-zI)^{-1}\Vert \)) which provides error control. We have shown the output of \(\Gamma _{10^3,10^4}(A)\) via the green dashed circle (Color figure online)
×
4.2 Essential Numerical Range
To demonstrate the algorithm for computing the essential numerical range, we first consider the Laurent operator \(A_0\) acting on \(l^2({\mathbb {Z}})\) with the symbol
In this case, \(\textrm{Sp}(A_0)=\textrm{Sp}_{\textrm{ess}}(A_0)=\{a(z):|z|=1\}\). We consider the operator \(A=A_0+E\) where the compact perturbation E is given by
Recall that the SCI classification for computing the essential numerical range is \(\Pi _2^A\) (see Theorem 3.10). The first parameter, \(n_1\), controls the size of the truncation, whereas the second, \(n_2\), controls how far along the matrix the truncations \((I-P_{n_2})P_{n_1+n_2}A|_{P_{n_1+n_2}(I-P_{n_2}){\mathcal {H}}}\) are taken with respect to the canonical basis.
Fig. 3
Left: The boundaries \(\partial W(A)\) and \(\partial \Gamma _{2\times 10^4,500}(A)\). We have also shown the essential spectrum of A (whose convex hull, in this example, corresponds to \(W_e(A)\)) and the output of finite section for a \(200\times 200\) truncation. Right: Pseudospectrum computed using the method of [64] (the colour scale corresponds to the resolvent norm \(\Vert (A-zI)^{-1}\Vert \)) which provides error control. This confirms that eigenvalues, computed using finite section, outside \(\partial \Gamma _{2\times 10^4,500}(A)\) are accurate and, in this example, indicates that the other eigenvalues correspond to spectral pollution (Color figure online)
×
Figure 3 (left) shows the output of the algorithm \(\Gamma _{n_2,n_1}(A)\) to compute the essential numerical range for \(n_2=20{,}000\) and \(n_1=500\). We show the boundary \(\partial \Gamma _{n_2,n_1}(A)\) since the essential numerical range is convex. In this example, \(W_\textrm{e}(A)\) is the convex hull of \(\textrm{Sp}_{\textrm{ess}}(A_0)\), which allows us to verify the output of the algorithm. We also show 200 eigenvalues of finite section (computed using extended precision to avoid numerical instabilities associated with non-normal truncations), the majority of which are due to truncation and provide an example of spectral pollution. This is confirmed when we compare to the pseudospectrum, also shown in Fig. 3 (right), computed using the algorithm in [64]. However, eigenvalues outside \(W_\textrm{e}(A)\) correspond to true eigenvalues of A (see Theorem 3.9).
The algorithm can also be extended to unbounded operators, as outlined in Sect. 7.1. For example, we consider the complex Schrödinger operator
By using a Gabor basis, we can represent T as a closed operator on \(l^2({\mathbb {N}})\) such that the linear span of the canonical basis (corresponding to the Gabor basis) forms a core. This allows us to use Corollary 7.5, where we can compute the matrix elements (corresponding to inner products with the basis functions) with error control using quadrature. Figure 4 shows the output for \(n_2=10^4\) and various \(n_1\). We see the expected monotonicity as \(n_1\) increases and the output for \(n_1=2000\) has converged to visible accuracy in the plot.
Fig. 4
The output of the algorithm for computing the essential numerical range of closed operators, applied to the complex Schrödinger operator T in (4.1)
×
4.3 Capacity
We now consider a transport Hamiltonian on a Penrose tile for which few analytical results are known. Quasicrystals were discovered in 1982 by Shechtman [145] who was awarded the Nobel prize in 2011 for his discovery. Over the past 30 years, there has been considerable interest in their often exotic properties [67, 151]. The Penrose tile is the standard two-dimensional model [69, 165], and a finite portion of the tiling is shown in Fig. 5 (left). However, unlike one-dimensional models, very little is known about the spectral properties of two-dimensional quasicrystals. Let G be the graph consisting of the vertices, V(G), of the Penrose tiling and E(G) the set of edges. If there is an edge connecting two vertices x and y, we write \(x \sim y\). The (negative) Laplacian, H, acts on \(\psi \in l^2(V(G)) \cong l^{2}({\mathbb {N}})\) by
By choosing a suitable ordering of the vertices, we can represent H as an operator acting on \(l^2({\mathbb {N}})\) of bounded dispersion with \(f(n)-n\sim {\mathcal {O}}(\sqrt{n})\). Recall that the SCI classification for computing the capacity of the spectrum of such operators is \(\Pi _2^A\) (see Theorem 3.7 for further classifications). The first parameter, \(n_1\), controls the size of the truncation used to test if intervals intersect the spectrum via Lemma 3.21, whereas the second, \(n_2\), controls the spacings of the interval coverings (which have width \(2^{-n_2}\)). In this example, we used the conformal mapping method of [109] to accurately and rapidly compute the capacity of finite unions of intervals in \({\mathbb {R}}\) (see also Remark 6.4).
Figure 5 (right) shows the output of \(\Gamma _{n_2,n_1}(H)\), and we see the expected monotonicity; the output is increasing in \(n_1\) but decreasing in \(n_2\). By comparing the outputs for \(n_1=10^4\) and \(n_1=10^5\), it appears we have convergence up to around \(n_2=8\). This suggests an upper bound (since the output is non-increasing in \(n_2\)) of approximately 2.26 for the capacity of \(\textrm{Sp}(H)\) (\(\textrm{Sp}(H)\) is shown in Fig. 6).
Fig. 5
Left: Finite portion of the Penrose tiling showing a fivefold rotational symmetry. Right: Output of the algorithm for computing the capacity of \(\textrm{Sp}(H)\), where H is the operator in (4.2)
×
4.4 Lebesgue Measure
First, we consider the almost Mathieu operator, which is related to a wealth of mathematical and physical problems such as the Ten Martini Problem [9]. The operator acts on \(l^2({\mathbb {Z}})\) via
The choice of \(\lambda =1\) was studied in Hofstadter’s classic paper [92], giving rise to the famous Hofstadter butterfly. In this case, the Hamiltonian represents a crystal electron in a uniform magnetic field and the spectrum can be interpreted as the allowed energies of the system. For irrational \(\alpha \), we have [11]
and we consider the case \(\alpha =(\sqrt{5}-1)/2\). Recall that the SCI classification for computing the Lebesgue measure of the spectrum of such operators (where the dispersion is known) is \(\Pi _2^A\), whereas the SCI classification of computing the Lebesgue measure of the pseudospectrum is \(\Sigma _1^A\) (see Theorems 3.13, 3.14 and 3.16 for the further classifications). For computing the Lebesgue measure of the spectrum, the first parameter, \(n_1\), controls the size of the truncation used to compute the approximation of the resolvent norm, whereas the second, \(n_2\), controls the grid refinement (the spacings are \(2^{-n_2}\)). For the pseudospectrum, \(n_1\) controls the size of the truncations and the grid spacings.
Figure 6 (left) shows the output of the algorithms computing \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(H_{\alpha }))\) (LebSpec) and also \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}_{\epsilon }(H_{\alpha }))\) (LebPseudoSpec) for a range of values of \(\epsilon \). We chose values of \(n_1=10^4\) and a grid spacing of 1/128 (\(n_2=7\)). One can clearly see that the estimates for \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}_{\epsilon }(H_{\alpha }))\) are decreasing to the true value of \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(H_{\alpha }))\), which is well approximated by LebSpec.
Next, we consider the operator H in (4.2), for which the Lebesgue measure of \(\textrm{Sp}(H)\) is unknown. We set \(n_1=10^5\) and look at the average estimated error of the output via DistSpec (see “Appendix A”). This was of the order \(10^{-3}\), so we consider grid refinements of spacing \(1/32, 1/64,\ldots ,1/1024\) corresponding to \(n_2=5, 6,\ldots ,10\). Figure 6 (right) shows the output as a cumulative Lebesgue measure, that is, an estimate of \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(A)\cap (-\infty ,x])\) for a given x, along with the computed spectrum (for a grid spacing of \(10^{-5}\)). The figure provides strong evidence that the part of the spectrum closest to 0 is resolved by the algorithm and has Lebesgue measure zero. We shall see more evidence for this in Sect. 4.5.
Fig. 6
Left: Output of the algorithm LebSpec to compute \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(H_{\alpha }))\) as well as the algorithm LebPseudoSpec for \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}_{\epsilon }(H_{\alpha }))\) (which converges to \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(H_{\alpha }))\) as \(\epsilon \downarrow 0\)). These were computed using \(n_1=10^4\) and \(n_2=7\). Right: Estimates for \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(H)\cap (-\infty ,x])\), where H is the Laplacian on a Penrose tiling in (4.2), obtained by letting \(n_1=10^5\) and selecting different \(n_2\). The estimate above \(-3\) appears to be well resolved, suggesting a region of Lebesgue measure 0
×
4.5 Fractal Dimension
For this example, we again consider the operator H in (4.2), for which the fractal dimension of \(\textrm{Sp}(H)\) is unknown. In Fig. 7, we plot \(N_{1/n_2}({\tilde{\Gamma }}_{10^5}(H)\cap [-3,\infty ))\) against \(n_2\) (recall that \(N_\delta (\)F) is the number of closed intervals of length \(\delta > 0\) required to cover F). This corresponds to a rectangular truncation with \(n_1=10^5\) columns. Recall that \({\tilde{\Gamma }}_{n}\) denotes the algorithm that converges to the spectrum with error control, in particular avoiding spectral pollution (see “Appendix A”). We also show a linear fit of slope 0.8. The error control provided by the algorithm \({\tilde{\Gamma }}_{n}\) allows us to deduce the region where the fit holds, corresponding to a reliable resolution of the spectrum (this is at least as large as the region shown in the plot). In other words, we can ensure that \(n_2\) is not too large so that the spacings of the coverings are not smaller than the numerically resolved spectrum. As expected, when \(n_2\) is too large we see the effect of the grid spacing and the unresolved spectrum (by choosing larger \(n_1\), we can take \(n_2\) larger). The figure suggests that the spectrum above \(-3\) is fractal with box-counting dimension \(\approx 0.8\) and hence has Lebesgue measure zero, in agreement with the findings in Fig. 6.
Figure 7 also shows what happens when one performs the same experiment but with a finite section replacing \({\tilde{\Gamma }}_{n}\) (now using a square \(10^5\times 10^5\) truncation). There are two noticeable features. First, for small \(n_2\), using a finite section produces an overestimate of the size of the covering and the corresponding slope of the graph due to spectral pollution. In other words, finite section prevents us from detecting the fractal spectrum. Second, the covering estimate via finite section breaks down at smaller \(n_2\) and it is impossible to predict suitable values of \(n_2\) so that the spacings of the coverings do not go beyond the resolution of the computed spectrum. Together, these issues highlight why the finite section method is unsuitable in general17 for approximating fractal dimensions and why the new algorithms in this paper (which are proven to converge) are needed.
Fig. 7
A plot of \(N_{1/n_2}({\tilde{\Gamma }}_{10^5}(H)\cap [-3,\infty ))\) against \(n_2\). We found a scaling region with estimated box-counting dimension \(\approx 0.80\). Note that for large \(n_2\gtrsim 5000\), scalings are not resolved by \({\tilde{\Gamma }}_{10^5}\) (we can predict when this happens using the \(\Sigma _1^A\) property of \({\tilde{\Gamma }}_{n}\)). We have also shown the approximation using finite sections (square \(10^5\times 10^5\) matrix truncations), as a dashed line, which overestimate the size of coverings, cannot detect the fractal structure, and break down for smaller \(n_2\)
×
5 Mathematical Preliminaries and Combinatorial Problems in the SCI Hierarchy
In this section, we begin by providing formal definitions of the SCI hierarchy. We then link the SCI hierarchy, in a certain specific case, to the Baire hierarchy on a suitable topological space. As well as being interesting in its own right, this provides a useful method of providing canonical problems high up in the SCI hierarchy. In particular, the results we prove hold for towers of general algorithms (see Definition 5.1) without the restrictions of arithmetic operations or notions of recursivity etc. This will be used extensively in the proofs of lower bounds for spectral problems that have \(\textrm{SCI}>2\), where we typically reduce the problems discussed here to the given spectral problem. It should be stressed that such links to existing hierarchies only exist in special cases when \(\Omega \) and \({\mathcal {M}}\) are particularly well-behaved. Even when such a link does exist, the induced topology on \(\Omega \) is often too complicated, unnatural or strong to be useful from a computational viewpoint. We also take the view that, for problems of scientific interest, the mappings \(\Lambda \) and metric space \({\mathcal {M}}\) are often given to us apriori from the corresponding applications and are typically not compatible with topological viewpoints of computation.
5.1 The SCI Hierarchy
We begin by defining the solvability complexity index (SCI) hierarchy, allowing us to show that our algorithms realise the boundary of what computers can achieve. We have already presented the definition of a computational problem \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\) in §2.1. Recall that the goal is to find algorithms that approximate the function \(\Xi \). More generally, the main pillar of our framework is the concept of a tower of algorithms, which is needed to describe problems that need several successive limits in the computation. However, first one needs the definition of a general algorithm.
Definition 5.1
(General Algorithm) Given a computational problem \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\), a general algorithm is a mapping \(\Gamma :\Omega \rightarrow {\mathcal {M}}\) such that for each \(A\in \Omega \)
(i)
there exists a (non-empty) finite subset of evaluations \(\Lambda _\Gamma (A) \subset \Lambda \),
(ii)
the action of \(\,\Gamma \) on A only depends on \(\{A_f\}_{f \in \Lambda _\Gamma (A)}\) where \(A_f:= f(A),\)
(iii)
for every \(B\in \Omega \) such that \(B_f=A_f\) for every \(f\in \Lambda _\Gamma (A)\), it holds that \(\Lambda _\Gamma (B)=\Lambda _\Gamma (A)\).
The definition of a general algorithm is more general than the definition of a Turing machine [164] or a BSS machine [28]. A general algorithm has no restrictions on the operations allowed. The only restriction is that it can only take a finite amount of information, though it is allowed to adaptively choose the finite amount of information it reads depending on the input. Condition (iii) ensures that the algorithm consistently reads the information. With a definition of a general algorithm, we can define the concept of towers of algorithms.
Definition 5.2
(Tower of Algorithms) Given a computational problem \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\), a tower of algorithms of height k for \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\) is a family of sequences of functions
where \(n_k,\ldots ,n_1 \in {\mathbb {N}}\) and the functions \(\Gamma _{n_k, \ldots , n_1}\) at the lowest level of the tower are general algorithms in the sense of Definition 5.1. Moreover, for every \(A \in \Omega \),
In addition to a general tower of algorithms, we focus on arithmetic towers.
Definition 5.3
(Arithmetic Tower) Given a computational problem \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\), where \(\Lambda \) is countable, we define the following: An arithmetic tower of algorithms of height k for \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\) is a tower of algorithms where the lowest functions \(\Gamma = \Gamma _{n_k, \ldots , n_1}:\Omega \rightarrow {\mathcal {M}}\) satisfy the following: For each \(A\in \Omega \) the mapping \((n_k, \ldots , n_1) \mapsto \Gamma _{n_k, \ldots , n_1}(A) = \Gamma _{n_k, \ldots , n_1}(\{A_f\}_{f \in \Lambda })\) is recursive, and \(\Gamma _{n_k, \ldots , n_1}(A)\) is a finite string of complex numbers that can be identified with an element in \({\mathcal {M}}\). For arithmetic towers, we let \(\alpha = A\).
Remark 5.4
By recursive we mean the following. If \(f(A) \in {\mathbb {Q}}\) (or \({\mathbb {Q}}+i{\mathbb {Q}}\)) for all \(f \in \Lambda \), \(A \in \Omega \), and \(\Lambda \) is countable, then \(\Gamma _{n_k, \ldots , n_1}(\{A_f\}_{f \in \Lambda })\) can be executed by a Turing machine [164], that takes \((n_k, \ldots , n_1)\) as input, and that has an oracle tape consisting of \(\{A_f\}_{f \in \Lambda }\). If \(f(A) \in {\mathbb {R}}\) (or \({\mathbb {C}}\)) for all \(f \in \Lambda \), then \(\Gamma _{n_k, \ldots , n_1}(\{A_f\}_{f \in \Lambda })\) can be executed by a BSS machine [28] that takes \((n_k, \ldots , n_1)\), as input, and that has an oracle that can access any \(A_f\) for \(f \in \Lambda \).\(\square \)
Given the definitions above we can now define the key concept, namely the solvability complexity index:
Definition 5.5
(Solvability Complexity Index) A computational problem \(\{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}\) is said to have solvability complexity index \(\textrm{SCI}(\Xi ,\Omega ,{\mathcal {M}},\Lambda )_{\alpha } = k\), with respect to a tower of algorithms of type \(\alpha \), if k is the smallest integer for which there exists a tower of algorithms of type \(\alpha \) of height k. If no such tower exists, then \(\textrm{SCI}(\Xi ,\Omega ,{\mathcal {M}},\Lambda )_{\alpha } = \infty .\) If there exists a tower \(\{\Gamma _n\}_{n\in {\mathbb {N}}}\) of type \(\alpha \) and height one such that \(\Xi = \Gamma _{n_1}\) for some \(n_1 < \infty \), then we define \(\textrm{SCI}(\Xi ,\Omega ,{\mathcal {M}},\Lambda )_{\alpha } = 0\). The type \(\alpha \) may be General, or Arithmetic, denoted, respectively, G and A. We may sometimes write \(\textrm{SCI}(\Xi ,\Omega )_{\alpha }\) to simplify notation when \({\mathcal {M}}\) and \(\Lambda \) are obvious.
We will let \(\textrm{SCI}(\Xi ,\Omega )_{\textrm{A}}\) and \(\textrm{SCI}(\Xi ,\Omega )_{\textrm{G}}\) denote the SCI with respect to an arithmetic tower and a general tower, respectively. Note that a general tower means just a tower of algorithms as in Definition 5.2, where there are no restrictions on the mathematical operations. Thus, clearly \(\textrm{SCI}(\Xi ,\Omega )_{\textrm{A}} \ge \textrm{SCI}(\Xi ,\Omega )_{\textrm{G}}\). The definition of the SCI immediately induces the SCI hierarchy:
Definition 5.6
(The Solvability Complexity Index Hierarchy) Consider a collection \({\mathcal {C}}\) of computational problems and let \({\mathcal {T}}\) be the collection of all towers of algorithms of type \(\alpha \) for the computational problems in \({\mathcal {C}}\). Define
When there is additional structure on the metric space, such as in the spectral case when one considers the Attouch–Wets or the Hausdorff metric, one can extend the SCI hierarchy. For non-empty closed sets, we consider the Attouch–Wets metric defined by
for \(C_1,C_2\in \textrm{Cl}({\mathbb {C}}),\) where \(\textrm{Cl}({\mathbb {C}})\) denotes the set of closed non-empty subsets of \({\mathbb {C}}\). This generalises the familiar Hausdorff metric to unbounded closed sets and corresponds to local uniform converge on compact subsets of \({\mathbb {C}}\).
Definition 5.7
(The SCI Hierarchy (Attouch–Wets/Hausdorff metric)) Given the set-up in Definition 5.6, and suppose in addition that \(({\mathcal {M}},d)\) has the Attouch–Wets or the Hausdorff metric induced by another metric space \(({\mathcal {M}}^{\prime },d')\), define, for \(m \in {\mathbb {N}}\),
where \(\mathop {\subset }_{{\mathcal {M}}^{\prime }}\) means inclusion in the metric space \({\mathcal {M}}^{\prime }\), and \(\{X_{n}(A)\}\) is a sequence where \(X_n(A) \in {\mathcal {M}}\) depends on A. Moreover,
where d can be either \(d_{\textrm{H}}\) or \(d_{\textrm{AW}}\).
Note that to build a \(\Sigma _1\) algorithm, it is enough (by taking subsequences of n) to construct \(\Gamma _n(A)\) such that \(\Gamma _{n}(A) \subset {\mathcal {N}}_{E_n(A)}(\Xi (A))\) with some computable \(E_n(A)\) that converges to zero. The same idea can be applied to the real line with the usual metric, or \(\{0,1\}\) with the discrete metric (we interpret 1 as “Yes”).
Definition 5.8
(The SCI Hierarchy (totally ordered set)) Given the set-up in Definition 5.6 and suppose in addition that \({\mathcal {M}}\) is a totally ordered set. Define
(\(\Delta ^{\alpha }_1\subsetneq \Sigma ^{\alpha }_1 \subsetneq \Delta ^{\alpha }_2\)) Note that the inclusions are strict. For example, if \(\Omega _K\) consists of the set of compact infinite matrices acting on \(l^2({\mathbb {N}})\) and \(\Xi (A)=\textrm{Sp}(A)\) (the spectrum of A) then \(\{\Xi , \Omega _K\} \in \Delta ^{\alpha }_2\) but not in \( \Sigma _1^\alpha \cup \Pi _1^\alpha \) for \(\alpha \) representing either towers of arithmetical or general type (see [18] for a proof). Moreover, as was demonstrated in [64], if \(\tilde{\Omega }\) is the set of discrete Schrödinger operators on \(l^2({\mathbb {Z}})\), then \(\{\Xi , {{\tilde{\Omega }}}\} \in \Sigma ^{\alpha }_1\) but not in \(\Delta ^{\alpha }_1\).\(\square \)
Suppose we are given a computational problem \(\{\Xi , \Omega , {\mathcal {M}}, \Lambda \}\), and that \(\Lambda = \{f_j\}_{j \in \beta }\), where \(\beta \) is some index set that can be finite or infinite. Obtaining \(f_j\) may be a computational task on its own, which is exactly the problem in most areas of computational mathematics. In particular, for \(A \in \Omega \), \(f_j(A)\) could be the number \(e^{\frac{\pi }{j} i }\) for example. Hence, we cannot access \(f_j(A)\), but rather \(f_{j,n}(A)\) where \(f_{j,n}(A) \rightarrow f_{j}(A)\) as \(n \rightarrow \infty \). Or, just as for problems that are high up in the SCI hierarchy, it could be that we need several successive limits, in particular one may need mappings \(f_{j,n_m,\ldots , n_1}: \Omega \rightarrow {\mathbb {D}} + i{\mathbb {D}}\), where \({\mathbb {D}}\) denotes the dyadic rational numbers, such that
In particular, we may view the problem of obtaining \(f_j(A)\) as a problem in the SCI hierarchy, where \(\Delta _1\) classification would correspond to the existence of mappings \(f_{j,n}: \Omega \rightarrow {\mathbb {D}} + i {\mathbb {D}}\) such that
This idea is formalised in the following definition.
Definition 5.10
(\(\Delta _{m}\)-information) Let \(\{\Xi , \Omega , {\mathcal {M}}, \Lambda \}\) be a computational problem. For \(m \in {\mathbb {N}}\), we say that \(\Lambda \) has \(\Delta _{m+1}\)-information if each \(f_j \in \Lambda \) is not available, however, there are mappings \(f_{j,n_m,\ldots , n_1}: \Omega \rightarrow {\mathbb {D}} + i {\mathbb {D}}\) such that (5.2) holds. Similarly, for \(m = 0\) there are mappings \(f_{j,n}: \Omega \rightarrow {\mathbb {D}} + i {\mathbb {D}}\) such that (5.3) holds. Finally, if \(k \in {\mathbb {N}}\) and \({{\hat{\Lambda }}}\) is a collection of such functions described above such that \(\Lambda \) has \(\Delta _k\)-information, we say that \({{\hat{\Lambda }}}\) provides \(\Delta _k\)-information for \(\Lambda \). Moreover, we denote the family of all such \({{\hat{\Lambda }}}\) by \({\mathcal {L}}^k(\Lambda )\).
We want algorithms that can handle all computational problems \(\{\Xi ,\Omega ,{\mathcal {M}},{{\hat{\Lambda }}}\}\) when \({{\hat{\Lambda }}} \in {\mathcal {L}}^m(\Lambda )\). To formalise this, we define a computational problem with \(\Delta _m\)-information.
Definition 5.11
(Computational problem with\(\Delta _m\)-information) Given \(m \in {\mathbb {N}}\) with \(m>1\), a computational problem where \(\Lambda \) has \(\Delta _m\)-information is denoted by \( \{\Xi ,\Omega ,{\mathcal {M}},\Lambda \}^{\Delta _m}:= \{{{\tilde{\Xi }}},{{\tilde{\Omega }}},{\mathcal {M}},{{\tilde{\Lambda }}}\}, \) where
Moreover, \({{\tilde{\Xi }}}({{\tilde{A}}}) = \Xi (A)\), and we have \(\tilde{\Lambda }= \{{{\tilde{f}}}_{j,n_{m-1},\ldots , n_1}\}_{j,n_{m-1},\ldots , n_1 \in \beta \times {\mathbb {N}}^{m-1}}\) where \(\tilde{f}_{j,n_{m-1},\ldots , n_1}({{\tilde{A}}}) = f_{j,n_{m-1},\ldots , n_1}(A)\). Note that \({{\tilde{\Xi }}}\) is well-defined by Definition 2.1 of a computational problem. Similarly, we define \(\Delta _1\)-information using (5.3).
The SCI and the SCI hierarchy, given \(\Delta _m\)-information, are then defined in the standard obvious way.
Remark 5.12
(Classifications in this paper) For the problems considered in this paper, the SCI classifications do not change if we consider arithmetic towers with \(\Delta _1\)-information. This is easy to see through Church’s thesis and an analysis of the stability of our algorithms. For example, when the input is rational we have been careful to restrict all relevant operations to \({\mathbb {Q}}\) rather than \({\mathbb {R}}\), and errors incurred from \(\Delta _1\)-information can be removed in the first limit. Explicitly, for the algorithms based on DistSpec (see “Appendix A”) it is possible to carry out an error analysis. We can also bound numerical errors (e.g. using interval arithmetic [163]) and incorporate this uncertainty for the estimation of \(\left\| R(z,A)\right\| ^{-1}\) to gain the same classification of our problems. Similarly, for other algorithms based on similar functions. In other words, for the results of this paper, it does not matter which model of computation one uses for a definition of ‘algorithm’. From a classification point of view, they are equivalent for these spectral problems. This leads to rigorous \(\Sigma _k^\alpha \) or \(\Pi _k^\alpha \) type error control suitable for verifiable numerics. In particular, for \(\Sigma _1^{\alpha }\) or \(\Pi _1^{\alpha }\) towers of algorithms, this could be useful for computer-assisted proofs.\(\square \)
5.2 Recalling Some Results from Descriptive Set Theory
We briefly recall the definition of the Borel hierarchy as well as some well-known theorems from descriptive set theory. It is beyond the scope of this paper to provide an extensive discussion of descriptive set theory, but we refer the reader to [98, Chapter 2] for an excellent introduction that covers the main ideas.
Let X be a metric space and define
$$\begin{aligned} \Sigma _1^0(X)=\{U\subset X:U\text { is open}\},\quad \Pi _1^0(X)=\sim \Sigma _1^0(X)=\{F\subset X:F\text { is closed}\}, \end{aligned}$$
where for a class \({\mathcal {U}}\), \(\sim {\mathcal {U}}\) denotes the class of complements (in X) of elements of \({\mathcal {U}}\). Inductively define
The full Borel hierarchy extends to all \(\xi <\omega _1\) (\(\omega _1\) being the first uncountable ordinal) by transfinite induction but we do not need this here.
Definition 5.13
Given a class of subsets, \({\mathcal {U}}\), of a metric space X and given another metric space Y, we say that the function \(f:X\rightarrow Y\) is \({\mathcal {U}}\)-measurable if \(f^{-1}(U)\in {\mathcal {U}}\) for every open set \(U\subset Y\).
Given metric spaces X and Y, the Baire hierarchy is defined as follows. A function \(f:X\rightarrow Y\) is of Baire class 1, written \(f\in {\mathcal {B}}_1\), if it is \(\Sigma _2^0(X)\)-measurable. For \(1<\xi <\omega _1\), a function \(f:X\rightarrow Y\) is of Baire class \(\xi \), written \(f\in {\mathcal {B}}_\xi \), if it is the pointwise limit of a sequence of functions \(f_n\) in \({\mathcal {B}}_{\xi _n}\) with \(\xi _n<\xi \). The following Theorem is well-known [98, Section 24] and provides a useful link between the Borel and Baire hierarchies.
Theorem 5.14
(Lebesgue, Hausdorff, Banach) Let X, Y be metric spaces with Y separable and \(1\le \xi <\omega _1\). Then, \(f\in {\mathcal {B}}_\xi \) if and only if it is \(\Sigma _{\xi +1}^0(X)\) measurable. Furthermore, if X is zero-dimensional (Hausdorff with a basis of clopen sets) and \(f\in {\mathcal {B}}_1\), then f is the pointwise limit of a sequence of continuous functions.
The assumption that X is zero-dimensional in the last statement is important. Without any assumptions, the final statement of the theorem is false, as is easily seen by considering \(X={\mathbb {R}}\). Examples of zero-dimensional spaces include products of the discrete space \(\{0,1\}\) or the Cantor space. Any such space is necessarily totally disconnected, meaning that the connected components in the space are the one-point sets (the converse is true for locally compact Hausdorff spaces). Our primary interest will be when Y is equal to \(\{0,1\}\) or [0, 1], both with their natural topologies.
5.3 Linking the SCI Hierarchy to the Baire Hierarchy in a Special Case
Definition 5.15
Given the triple \(\{\Omega ,{\mathcal {M}},\Lambda \}\), a class of algorithms \({\mathcal {A}}\) is closed under search with respect to \(\{\Omega ,{\mathcal {M}},\Lambda \}\) if whenever
(1)
\({\mathcal {I}}\) is an index set,
(2)
\(\{n_i\}_{i\in {\mathcal {I}}}\) a family of natural numbers,
\(\{U_{i,l}\}_{i\in {\mathcal {I}},l\le n_i}\) family of basic open sets in \({\mathcal {M}}\) with \(\cup _{i\in {\mathcal {I}}}\cap _{l\le n_i}\Gamma _{i,l}^{-1}(U_{i,l})=\Omega ,\)
(5)
\(\{c_i\}_{i\in {\mathcal {I}}}\) a family of points in some arbitrary dense subset of \({\mathcal {M}}\),
then there is some \(\Gamma \in {\mathcal {A}}\) such that for every \(x\in \Omega \) there exists some \(i\in {\mathcal {I}}\) with \(\Gamma (x)=c_i\) and for all \(l\le n_i\) we have \(\Gamma _{i,l}(x)\in U_{i,l}\).
Proposition 5.16
Suppose that \({\mathcal {A}}\) is closed under search with respect to \(\{\Omega ,{\mathcal {M}},\Lambda \}\), then there exists a topology \({\mathcal {T}}\) on \(\Omega \) such that \(\Delta _1^{{\mathcal {A}}}\) is precisely the set of continuous functions from \((\Omega ,{\mathcal {T}})\) to \({\mathcal {M}}\).
Proof
Let \({\mathcal {T}}\) be the topology generated by \(\{\Gamma ^{-1}(B):\Gamma \in {\mathcal {A}},B\subset {\mathcal {M}}\text { basic open}\}\). Any \(\Gamma \in {\mathcal {A}}\) is continuous with respect to this topology. Uniform limits of continuous functions into metric spaces are also continuous, and hence any function in \(\Delta _1^{{\mathcal {A}}}\) is continuous with respect to \({\mathcal {T}}\).
For the other direction, suppose that \(f: (\Omega ,{\mathcal {T}})\rightarrow {\mathcal {M}}\) is continuous. Choose \(\{c_i\}_{i\in {\mathcal {I}}}\subset {\mathcal {M}}\) such that \({\mathcal {M}}\subset \cup _{i\in {\mathcal {I}}}D(c_i,2^{-n})\). Continuity of f implies that \(f^{-1}(D(c_i,2^{-n}))\) are open. This implies that there is an index set \({\mathcal {J}}\), natural numbers \(\{n_{i,j}\}_{j\in {\mathcal {J}}}\), a family \(\{\Gamma _{i,j,l}\}_{i\in {\mathcal {I}},j\in {\mathcal {J}},l\le n_{i,j}}\) (in \({\mathcal {A}}\)) and a family of basic open sets \(\{U_{i,j,l}\}_{i\in {\mathcal {I}},j\in {\mathcal {J}},l\le n_{i,j}}\) with the property that
Since \({\mathcal {A}}\) is closed under search, there exists \(f_n\in {\mathcal {A}}\) such that for every \(x\in \Omega \) there exists some \(i\in {\mathcal {I}}\) and \(j\in {\mathcal {J}}\) with \(f_n(x)=c_i\) and for all \(l\le n_{i,j}\), \(x\in \Gamma ^{-1}_{i,j,l}(U_{i,j,l}).\) But this implies that \(d(f_n(x),f(x))< 2^{-n}\). Since n was arbitrary, we have \(f\in \Delta _1^{{\mathcal {A}}}\). \(\square \)
The generated topology can be very perverse and not every class of algorithms is closed under search. However, we do have the following useful theorem when \(\Omega \) (and \(\Lambda \)) is a particularly simple discrete space.
Theorem 5.17
Suppose that \(\Omega =\{0,1\}^{{\mathbb {N}}}=\{\{a_i\}_{i\in {\mathbb {N}}}:a_i\in \{0,1\}\}\) with the set of evaluation functions \(\Lambda \) equal to the set of pointwise evaluations \(\{\lambda _{j}(a):=a_j:j\in {\mathbb {N}}\}\) and let \({\mathcal {M}}\) be an arbitrary separable metric space with at least two separated points. Endow \(\Omega \) with the product topology, \(\tilde{{\mathcal {T}}}\), induced by the discrete topology on \(\{0,1\}\) and consider the Baire hierarchy, \(\{{\mathcal {B}}_{\xi }((\Omega ,\tilde{{\mathcal {T}}}),{\mathcal {M}})={\mathcal {B}}_{\xi }\}_{\xi <\omega _1}\), of functions \(f:\Omega \rightarrow {\mathcal {M}}\). Then for any problem function \(\Xi :\Omega \rightarrow {\mathcal {M}}\) and \(m\in {\mathbb {N}}\),
In other words, the SCI corresponds to the Baire hierarchy index.
Remark 5.18
The proof shows that we can replace \(\Omega \) by \(\{0,1\}^{{\mathbb {N}}\times {\mathbb {N}}}\) or any other such product space (induced by a discrete topology) of the form \(A^B\) with A, B countable, with \(\Lambda \) the corresponding component-wise evaluations, as long as \({\mathcal {M}}\) has at least \(\left| A\right| \) jointly separated points and is separable.\(\square \)
Proof
First we show that general algorithms are closed under search and that the topology \({\mathcal {T}}\) in Proposition 5.16 is equal to the product topology \(\tilde{{\mathcal {T}}}\). Without loss of generality, we can assume that \({\mathcal {I}}\) is well-ordered by \(\prec \). Given \(x\in \Omega \), let \(k\in {\mathbb {N}}\) be minimal such that there exists \(i\in {\mathcal {I}}\) with \(x\in \cap _{l\le n_i}\Gamma ^{-1}_{i,l}(U_{i,l})\) and \(\Lambda _{\Gamma _{i,l}}(x)\subset \{\lambda _j:j\le k\}\) for \(l\le n_i\). Let \(i_0\) be the \(\prec \)-least witness for k and then define \(\Gamma (x)=c_{i_0}\). The well-ordering of \({\mathcal {I}}\) implies that \(\Gamma \) is a general algorithm, and it clearly satisfies the requirements in the definition of closed under search. Note that this part of the proof only uses countability of \(\Lambda \).
To equate the topologies, suppose that \(\Gamma \in \Delta _0^G\) is a general algorithm. For each \(a\in \Omega ,\)\(\Lambda _{\Gamma }(a)\) is finite and we can assume without loss of generality that it is equal to \(\{\lambda _j:j\le I(a)\}\) for some finite I(a). In particular, there exists an open set \(U_a\) such that any \(b\in U_a\) has \(\lambda _j(b)=\lambda _j(a)\) for \(j\le I(a)\) and hence \(\Gamma (b)=\Gamma (a)\). Then for any open set \(B\subset {\mathcal {M}}\)
is open. Hence each \(\Gamma \) is continuous with respect to the product topology on \(\Omega \). It follows that \({\mathcal {T}}\subset \tilde{{\mathcal {T}}}\). To prove the converse, we must show that each projection map \(\lambda _j\) is continuous with respect to \({\mathcal {T}}\). Let \(x_1,x_2\) be separated points in \({\mathcal {M}}\) and consider \(f:\{0,1\}\rightarrow {\mathcal {M}}\) with \(f(0)=x_1\) and \(f(1)=x_2\). Then the composition \(f\circ \lambda _j\) is a general algorithm and hence continuous with respect to \({\mathcal {T}}\). But this implies that \(\lambda _j\) is continuous. It follows from Proposition 5.16 that \(\{\Xi ,\Omega ,\Lambda \}\in \Delta ^G_{1}\) if and only if \(\Xi \) is continuous.
Now the space \((\Omega ,{\mathcal {T}})\) is zero-dimensional and \({\mathcal {M}}\) is separable, hence by Theorem 5.14, any element of \({\mathcal {B}}_1\) is a limit of continuous functions. The converse holds in greater generality. It follows that \(\Xi \in {\mathcal {B}}_m\) if and only if there are \(f_{n_m,\ldots ,n_1}\in \Delta ^G_{1}\) with
so that \(\{\Xi ,\Omega ,\Lambda \}\in \Delta ^G_{m+1}\). Conversely if \(\{\Xi ,\Omega ,\Lambda \}\in \Delta ^G_{m+1}\) with tower of algorithms \(\{\Gamma _{n_{m},\ldots ,n_1}\}\), then since each general algorithm is continuous, (5.5) holds with \(f_{n_m,\ldots ,n_1}(a)=\Gamma _{n_{m},\ldots ,n_1}\). \(\square \)
5.4 Combinatorial Problems High up in the SCI Hierarchy
We can now combine the results of the previous two subsections and obtain combinatorial problems high up in the SCI hierarchy. Let \(k\in {\mathbb {N}}_{\ge 2}\) and let \(\Omega _k\) denote the collection of all infinite arrays \(\{a_{m_1,\ldots ,m_k}\}_{m_1,\ldots ,m_k\in {\mathbb {N}}}\) with entries \(a_{m_1,\ldots ,m_k}\in \{0,1\}\). As usual, \(\Lambda _k\) is the set of component-wise evaluations/projections. Consider the formulas
where \(\forall ^{\infty }\) means “for all but a finite number of”. In words, P decides whether the corresponding matrix has a column with infinitely many 1’s, whereas Q decides whether the matrix has only finitely many columns with only finitely many 1’s. For \(R=P\) or Q, consider the problem function for \(a\in \Omega _k\)
Let \({\mathcal {M}}\) be either \(\{0,1\}\) with the discrete metric or [0, 1] with the usual metric and consider the above problems \(\{\Xi _k,\Omega _k,{\mathcal {M}},\Lambda _k\}\). For \(k\in {\mathbb {N}}_{\ge 2}\) and \(R=P\) or Q,
In other words, we can solve the problem via a height \(k+1\) arithmetic tower, but it is impossible to do so with a height k general tower.
Remark 5.20
Note that we allow both discrete and continuous spaces \({\mathcal {M}}\), which will be important for our reduction arguments when proving lower bounds for classifications of spectral problems for non-discrete \({\mathcal {M}}\). The lower bound is a strong result in the sense that it holds regardless of the model of computation. In other words, it is the intrinsic combinatorial complexity of the problems that make the problems hard.\(\square \)
Proof
We deal with the case of \(R=P\) since the case of \(R=Q\) is completely analogous. It is easy to see that \(\{\Xi _{k,P},\Omega _{k},{\mathcal {M}},\Lambda _k\}\in \Delta _{k+2}^A\). First consider the case \(k=2\) and set
where \(\chi _C\) denotes the indicator function of a set C. This is the decision problem that decides whether there exists a column with index at most \(n_3\) such that there are at least \(n_2\) 1’s in the first \(n_1\) rows. This is clearly an arithmetic tower and it is straightforward to show that this converges to \(\Xi _{2,P}\) in \({\mathcal {M}}\) (in either of the \(\{0,1\}\) and [0, 1] cases). For \(k>2\), we simply alternate taking products (which corresponds to minima in this case) and maxima. Explicitly, we set
Again, this is an arithmetic tower and it is straightforward to show that this converges to \(\Xi _{k,P}\) in \({\mathcal {M}}\). It also holds that \(\{\Xi _{k,P},\Omega _{k},{\mathcal {M}},\Lambda _k\}\in \Sigma _{k+1}^A\) if k is even and \(\{\Xi _{k,P},\Omega _{k},{\mathcal {M}},\Lambda _k\}\in \Pi _{k+1}^A\) if k is odd (not to be confused with the notation for the Borel hierarchy).
Recall the topology \({\mathcal {T}}\) on \(\Omega _k\) from Theorem 5.17. For the lower bound, we note that P is \(\Sigma _3^0\) complete (in the literature it is known as the problem “\(S_3\)”, see for example [98, Section 23]). Since \((\Omega _{k},{\mathcal {T}})\) is zero-dimensional, a theorem of Wadge implies that this means that P is the indicator function of a set, also denoted by P, which lies in \(\Sigma _3^0(\Omega _k)\) but not \(\Pi _3^0(\Omega _k)\). It also follows that \(\Xi _{k,P}\) is \(\Sigma _{k+1}^0(\Omega _k)\) complete if k is even and \(\Pi _{k+1}^0(\Omega _k)\) complete otherwise. Now suppose for a contradiction that \(\{\Xi _{k,P},\Omega _{k},{\mathcal {M}},\Lambda _k\}\in \Delta _{k+1}^G\). But then Theorem 5.17 implies that \(\Xi _{k,P}\in {\mathcal {B}}_k(\Omega _k,{\mathcal {M}})\) and hence by Theorem 5.14, \(\Xi _{k,P}\) is \(\Sigma _{k+1}^0(\Omega _k)\) measurable. \(\Xi _{k,P}\) is the indicator function of a set, which we denote by \(\Xi _{k,P}\) with an abuse of notation, which is either \(\Sigma _{k+1}^0(\Omega _k)\) or \(\Pi _{k+1}^0(\Omega _k)\) complete depending on the parity of k. But 0 and 1 are separated in \({\mathcal {M}}\) and hence since \(\Xi _{k,P}\) is \(\Sigma _{k+1}^0(\Omega _k)\) measurable, \(\Xi _{k,P}\) and its complement both lie in \(\Sigma _{k+1}^0(\Omega _k)\). It follows that \(\Xi _{k,P}\in \Sigma _{k+1}^0(\Omega _k)\cap \Pi _{k+1}^0(\Omega _k)\), contradicting the stated completeness. \(\square \)
For our applications to spectral problems, we will use \({\tilde{\Omega }}\) to denote \(\Omega _k\) and consider
Theorem 5.19 holds for a much wider class of decision problems, but these four are the only ones we shall use in the sequel. The decision problems \({{\tilde{\Xi }}}_1\) and \({{\tilde{\Xi }}}_2\) were shown to have \(\textrm{SCI}_G=3\) in [18], but only with regard to the discrete space \({\mathcal {M}}=\{0,1\}\) and the proof used a somewhat complicated Baire category argument. Theorem 5.19 is much more general, can be extended to arbitrarily large SCI, and has a much slicker proof, making clear a beautiful connection with the Baire hierarchy for well-behaved \(\Omega \).
Here we prove the theorems found in Sects. 3.1–3.3. First, we briefly recall \(\Sigma _1^A\) algorithms for spectral problems presented in [64], that are sharp in the SCI hierarchy. The algorithms constructed in [64] are shown as pseudocode in “Appendix A”, where we also refer the reader to a more detailed account. The following was proven in [64] and was generalised in [60] to unbounded operators:
Theorem 6.1
For each \(\Omega _f\) and \(\Omega _f\cap \Omega _g\), consider the family \(\Lambda \) consisting of \(\Lambda _1\), together with pointwise evaluation of \(f,\{c_n\}\) (and evaluation of g at rational points if considering \(\Omega _f\cap \Omega _g\)). The algorithms presented in “Appendix A” achieve \(\Sigma _1^A\) error control. In particular the following classification holds:
We now turn to the proof of Theorem 3.3, dealing first with the evaluation set \(\Lambda _1\). Suppose that \(\{{\tilde{\Gamma }}_{n_k,\ldots ,n_1}\}\) is a \(\Pi ^A_k\) tower of algorithms to compute the spectrum of a class of operators, where the output is a finite set for each \(n_1,\ldots ,n_k\). It is then clear that
provides a \(\Pi ^A_k\) tower of algorithms for the spectral radius. Strictly speaking, the above may not be an arithmetic tower owing to the absolute value. But it can be approximated to arbitrary precision (from above say), the error of which can be absorbed in the first limit. In what follows, we always assume this is done without further comment. Similarly if \(\{{\tilde{\Gamma }}_{n_k,\ldots ,n_1}\}\) provides a \(\Sigma ^A_k\) tower of algorithms for the spectrum (and outputs a finite set for each \(n_1,\ldots ,n_k\)),
provides a \(\Sigma ^A_k\) tower of algorithms for the spectral radius. If we only have a height k tower with no \(\Sigma _k\) or \(\Pi _k\) type error control for the spectrum, then taking the supremum of absolute values shows that we get a height k tower for the spectral radius.
The fact that \(\{\Xi _r,\Omega _\textrm{D}\} \in \Sigma ^A_1\), \(\{\Xi _r,\Omega _f\cap \Omega _g\} \in \Sigma ^A_1\), \(\{\Xi _r,\Omega _g\} \in \Sigma ^A_2\), \(\{\Xi _r,\Omega _f\} \in \Pi ^A_2\) and \(\{\Xi _r,\Omega _{\textrm{B}}\} \in \Pi ^A_3\) hence follow from Theorems 6.1 and the results of [18]. It is clear that \(\{\Xi _r,\Omega _\textrm{D}\}\notin \Delta ^G_1\) and this also shows that \(\{\Xi _r,\Omega _\textrm{N}\}\notin \Delta ^G_1\) and \(\{\Xi _r,\Omega _f\cap \Omega _g\}\notin \Delta ^G_1\). Hence, we must show the positive result that \(\{\Xi _r,\Omega _\textrm{N}\} \in \Sigma ^A_1\) and prove the lower bounds \(\{\Xi _r,\Omega _g\}\notin \Delta ^G_2\), \(\{\Xi _r,\Omega _f\}\notin \Delta ^G_2\) and \(\{\Xi _r,\Omega _{\textrm{B}}\}\notin \Delta ^G_3\).
Proof of Theorem3.3for\(\Lambda _1\) Throughout this proof, we use the evaluation set \(\Lambda _1\), which we drop from the notation for convenience.
Step 1\(\{\Xi _r,\Omega _\textrm{N}\} \in \Sigma ^A_1\). Recall that the spectral radius of a normal operator \(A\in \Omega _{\textrm{B}}\) is equal to its operator norm. Consider the finite section matrices \(P_nAP_n\in {\mathbb {C}}^{n\times n}\). It is straightforward to show that
The norm \(\left\| P_nAP_n\right\| \) is the square root of the largest eigenvalue of the semi-positive definite self-adjoint matrix \((P_nAP_n)^*(P_nAP_n)\). This can be estimated from below to an accuracy of 1/n using Corollary 6.9 of [60], which then yields a \(\Sigma _1^A\) algorithm for \(\{\Xi _r,\Omega _\textrm{N}\}\).
Step 2\(\{\Xi _r,\Omega _g\}\notin \Delta ^G_2\). Recall that we assumed the existence of a \(\delta \in (0,1)\) such that \(g(x)\le (1-\delta )x\). Let \(\epsilon >0\), then it is easy to see that the matrices
have norm bounded by \(1+\epsilon +\epsilon ^2\) and are clearly inverse of each other. Choose \(\epsilon \) small such that \((1+\epsilon +\epsilon ^2)^2\le 1/(1-\delta )\). If \(B\in {\mathbb {C}}^{2\times 2}\) is normal, it follows that \({\hat{B}}:=S_{+}(\epsilon )BS_{-}(\epsilon )\) lies in \(\Omega _g\) and has the same spectrum as B. We choose
The crucial property of \({\hat{B}}\) is that the first entry \(1+\epsilon ^2\) is strictly greater in magnitude than the two eigenvalues \((1\pm \sqrt{1+4\epsilon ^2})/2\).
Now suppose for a contradiction that a height one tower, \(\{\Gamma _n\}\), solves the problem. We will gain a contradiction by showing that \(\Gamma _n(A)\) does not converge for an operator of the form,
where we only consider \(l_k\ge 3\). Each \(A_m\) is unitarily equivalent to the matrix \({\hat{B}}\oplus 0\in {\mathbb {C}}^{m\times m}\) and has spectrum equal to \(\{0,(1\pm \sqrt{1+4\epsilon ^2})/2\}\). Any A of the above form is unitarily equivalent to a direct sum of an infinite number of \({\hat{B}}\)’s and the zero operator and hence lies in \(\Omega _g\). Now suppose that \(l_1,\ldots ,l_k\) have been chosen and consider the operator
The spectrum of \(B_k\) is \(\{0,(1\pm \sqrt{1+4\epsilon ^2})/2,1+\epsilon ^2\}\), and hence, there exists \(\eta >0\) and \(n(k)\ge k\) such that \(\Gamma _{n(k)}(B_k)>(1+\sqrt{1+4\epsilon ^2})/2+\eta \). But \(\Gamma _{n(k)}(B_k)\) can only depend on the evaluations of the matrix entries \(\{B_k\}_{ij}=\langle B_ke_j,e_i \rangle \) with \(i,j\le N(B_k,n(k))\) (as well as evaluations of the function g) into account. If we choose \(l_{k+1}>N(B_k,n(k))\) then by the assumptions in Definition 5.1, \(\Gamma _{n(k)}(A)=\Gamma _{n(k)}(B_k)>(1+\sqrt{1+4\epsilon ^2})/2+\eta \). But \(\Gamma _n(A)\) must converge to \((1+\sqrt{1+4\epsilon ^2})/2\), a contradiction.
Step 3\(\{\Xi _r,\Omega _f\}\notin \Delta ^G_2\). Suppose for a contradiction that a height one tower, \(\{\Gamma _n\}\), solves the problem. We will gain a contradiction by showing that \(\Gamma _n(A)\) does not converge for an operator of the form
where we assume that \(l_r\ge r\) to ensure that the spectrum of A is equal to the unit disc \(B_1(0)\). Note that the function \(f(n)=n+1\) will do for the bounded dispersion with \(c_n=0\). Now suppose that \(l_1,\ldots ,l_k\) have been chosen and consider the operator
The spectrum of \(B_k\) is \(\{0\}\) and hence there exist \(n(k)\ge k\) such that \(\Gamma _{n(k)}(B_k)<1/4\). But \(\Gamma _{n(k)}(B_k)\) can only depend on the evaluations of the matrix entries \(\{B_k\}_{ij}=\langle B_ke_j,e_i \rangle \) with \(i,j\le N(B_k,n(k))\) (as well as evaluations of the function f) into account. If we choose \(l_{k+1}>N(B_k,n(k))\), then by the assumptions in Definition 5.1, \(\Gamma _{n(k)}(A)=\Gamma _{n(k)}(B_k)<1/4\). But \(\Gamma _n(A)\) must converge to 1, a contradiction.
Step 4\(\{\Xi _r,\Omega _{\textrm{B}}\}\notin \Delta ^G_3\). Suppose for a contradiction that \(\{\Gamma _{n_2,n_1}\}\) is a height two (general) tower and without loss of generality, assume it to be nonnegative. We use the results of Sect. 5. Let \(({\mathcal {M}},d)\) be the space [0, 1] with the usual metric (note in particular this is not discrete so we use Remark 5.20), let \({{\tilde{\Omega }}}\) denote the collection of all infinite matrices \(\{a_{i,j}\}_{i,j\in {\mathbb {N}}}\) with entries \(a_{i,j}\in \{0,1\}\) and recall the problem function
$$\begin{aligned} {{\tilde{\Xi }}}_1(\{a_{i,j}\}):\text { Does }\{a_{i,j}\}\text { have a column containing infinitely many nonzero entries?} \end{aligned}$$
Theorem 5.19 in Sect. 5 shows that \(\textrm{SCI}({{\tilde{\Xi }}}_1,{{\tilde{\Omega }}})_{G} = 3\). We will gain a contradiction by using the supposed height two tower to solve \(\{{{\tilde{\Xi }}}_1,{{\tilde{\Omega }}}\}\).
Without loss of generality, identify \(\Omega _{\textrm{B}}\) with \({\mathcal {B}}(X)\) where \(X=\bigoplus _{j=1}^{\infty }X_j\) in the \(l^2\)-sense with \(X_j=l^2({\mathbb {N}})\). Now let \(\{a_{i,j}\}\in {{\tilde{\Omega }}}\) and define \(B_j\in {\mathcal {B}}(X_j)\) with the matrix representation
Let \({\mathcal {I}}_j\) be the index set of all i where \(a_{i,j}=1\). \(B_j\) acts as a unilateral shift on \(\overline{\textrm{span}}\{e_k:k\in {\mathcal {I}}_j\}\) and the identity on its orthogonal complement. It follows that
where \(I_j\) denotes the identity operator on \({\mathbb {C}}^{j\times j}\), then \(\mathrm {Sp(A)}=\overline{\cup _{j=1}^\infty \textrm{Sp}(B_j)}-\frac{1}{2}\).
We then set \({\tilde{\Gamma }}_{n_2,n_1}(\{a_{i,j}\})=\min \{\max \{\Gamma _{n_2,n_1}(A)-1/2,0\},1\}\). It is clear that this defines a generalised algorithm mapping into [0, 1]. In particular, given N we can evaluate \(\{A_{k,l}:k,l\le N\}\) using only finitely many evaluations of \(\{a_{i,j}\}\), where we can use a bijection between canonical bases of \(l^2({\mathbb {N}})\) and \(\bigoplus _{j=1}^{\infty }X_j\) to view A as acting on \(l^2({\mathbb {N}})\). But then \(\{{{\tilde{\Gamma }}}_{n_2,n_1}\}\) provides a height two tower for \(\{{{\tilde{\Xi }}}_1,{{\tilde{\Omega }}}\}\), a contradiction. \(\square \)
Remark 6.2
The algorithm in step 1 of the above proof works for any operator whose operator norm is equal to its spectral radius. If, instead, the operator is spectraloid, meaning the spectral radius is equal to the numerical radius
then a similar argument will hold by estimating \(w(P_nAP_n)\). To do this, we need a way of computing w(A) to a given accuracy using finitely many arithmetic operations and comparisons (e.g. Lemma 7.1 below).\(\square \)
Proof of Theorem3.3for\(\Lambda _2\) Here we prove the changes for \(\Xi _r\) when we consider the evaluation set \(\Lambda _2\). It is clear that the classifications in \(\Sigma _1^A\) do not change. It is also easy to use the algorithm in Theorem 6.1 (now using \(\Lambda _2\) to collapse the first limit and approximate \(\gamma _n\)—see “Appendix A”) to prove \(\{\Xi _r,\Omega _g,\Lambda _2\}\in \Sigma _1^A\). Similarly we can use the algorithm for the spectrum of operators in \(\Omega _f\) for \(\Omega _{\textrm{B}}\) using \(\Lambda _2\) to collapse the first limit and hence \(\{\Xi _r,\Omega _{\textrm{B}},\Lambda _2\}\in \Pi _2^A\). Since \(\Omega _f\subset \Omega _{\textrm{B}}\), it follows that we only need to prove \(\{\Xi _r,\Omega _f,\Lambda _2\}\not \in \Delta _2^G\). This can be proven using exactly the same example and a similar argument to step 3 of the proof of Theorem 3.3 (hence omitted). \(\square \)
Proof of Theorem 3.6
We begin by proving the results for \(\Lambda _1\). For the lower bounds, it is enough to show that \(\{\Xi _{er},\Omega _\textrm{D},\Lambda _1\}\not \in \Delta _2^G\) and \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\not \in \Delta _3^G\). For the upper bounds, we must show that \(\{\Xi _{er},\Omega _f,\Lambda _1\}\in \Pi _2^A\), \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\in \Pi _3^A\) and \(\{\Xi _{er},\Omega _\textrm{N},\Lambda _1\}\in \Pi _2^A\). The lower bounds for \(\Lambda _2\) follow from \(\{\Xi _{er},\Omega _\textrm{D},\Lambda _1\}\not \in \Delta _2^G\) and for the upper bounds it is enough to prove \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _2\}\in \Pi _2^A\).
Step 1\(\{\Xi _{er},\Omega _\textrm{D},\Lambda _1\}\not \in \Delta _2^G\). This is the same argument as in step 3 of the proof of Theorem 3.3; however, now we replace \(A_m\) by \(A_m=\textrm{diag}\{1,1,\ldots ,1\}\in {\mathbb {C}}^{m\times m}\) and use the fact that \(\Xi _{er}(B_k)=0\). It follows that given the proposed height one tower \(\{\Gamma _n\}\) and the constructed A, \(\Xi _{er}(A)=1\) but \(\Gamma _{n(k)}(A)<1/4\), the required contradiction.
Step 2\(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\not \in \Delta _3^G\). This is the same argument as step 4 of the proof of Theorem 3.3.
Step 3\(\{\Xi _{er},\Omega _f,\Lambda _1\}\in \Pi _2^A\), \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\in \Pi _3^A\) and \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _2\}\in \Pi _2^A\). \(\{\Xi _{er},\Omega _f,\Lambda _1\}\in \Pi _2^A\) follows immediately from the existence of a \(\Pi _2^A\) tower of algorithms for the essential spectrum of operators in \(\Omega _f\) proven in [18]. The output of this tower is a finite collection of rectangles with complex rational vertices; hence, we can gain an approximation of the maximum absolute value over this output to any given precision. This can be used to construct a \(\Pi _2^A\) tower for \(\{\Xi _{er},\Omega _f,\Lambda _1\}\). Similarly, \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\in \Pi _3^A\) follows from the \(\Pi _3^A\) tower of algorithms for \(\{\textrm{Sp}_{\textrm{ess}},\Omega _{\textrm{B}},\Lambda _1\}\) constructed in [18]. Finally, we can use \(\Lambda _2\) to collapse the first limit of the algorithm for the essential spectrum in [18], giving a \(\Pi _2^A\) algorithm, and this can be used to show \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _2\}\in \Pi _2^A\).
Step 4\(\{\Xi _{er},\Omega _\textrm{N},\Lambda _1\}\in \Pi _2^A\). A \(\Pi _2^A\) tower is constructed in the proof of Theorem 3.10 for the essential numerical range, \(W_e(A)\), of normal operators (using \(\Lambda _1\)), and this outputs a finite collection of points. For normal operators A, \(W_e(A)\) is the convex hull of the essential spectrum and hence \(\sup _{z\in W_e(A)}\left| z\right| \) is equal to \(\Xi _{er}(A)\). Hence, a \(\Pi _2^A\) tower for \(\{\Xi _{er},\Omega _\textrm{N},\Lambda _1\}\) follows by taking the maximum absolute value over the tower for \(W_e(A)\). \(\square \)
Proof of Theorem 3.7
Note that given a height k arithmetical tower \(\{{{\widehat{\Gamma }}}_{n_k,\ldots ,n_1}(\cdot ,p)\}\) for \(\Xi _{r,p}\) and a class \(\Omega '\), we can build a \(\Pi _{k+1}^A\) tower for \(\{\Xi _{cap},\Omega '\}\) as follows. Let \(p_1,p_2,\ldots \) be an enumeration of the monic polynomials with rational coefficients and \({{\tilde{\Gamma }}}_{n_k,\ldots ,n_1}(\cdot ,p)\) be an approximation to \(|{{\widehat{\Gamma }}}_{n_k,\ldots ,n_1}(\cdot ,p)|^{1/\textrm{deg}(p)}\) to accuracy \(1/n_1\) using finitely many arithmetic operations and comparisons. Define
The fact that this is a convergent \(\Pi _{k+1}^A\) tower is clear. This, together with inclusions of the considered classes of operators, means that to prove the positive results we only need to prove \(\{\Xi _{r,p},\Omega _f,\Lambda _1\}\in \Sigma _1^A\), \(\{\Xi _{r,p},\Omega _{\textrm{B}},\Lambda _1\}\in \Sigma _2^A\) and \(\{\Xi _{r,p},\Omega _{\textrm{B}},\Lambda _2\}\in \Sigma _1^A\). Likewise, for the negative results we only need to prove \(\{\Xi _{cap},\Omega _{\textrm{D}},\Lambda _2\}\not \in \Delta ^G_2\) (the fact that \(\{\Xi _{r,p},\Omega _{\textrm{D}},\Lambda _2\}\not \in \Delta ^G_1\) is obvious), \(\{\Xi _{cap},\Omega _{\textrm{N}},\Lambda _1\}\not \in \Delta ^G_3\) and \(\{\Xi _{r,p},\Omega _{\textrm{N}},\Lambda _2\}\not \in \Delta ^G_2\). We shall prove these results with \(\Omega _{\textrm{N}}\) replaced by the class of self-adjoint bounded operators denoted by \(\Omega _{\textrm{SA}}\).
Step 1\(\{\Xi _{r,p},\Omega _f,\Lambda _1\}\in \Sigma _1^A\). The function f and sequence \(\{c_n\}\) allow us to compute the matrix elements of p(A) for any \(A\in \Omega _f\) and polynomial p to arbitrary accuracy. We can then use the same argument as step 1 of the proof of Theorem 3.3, approximating \(\Vert P_np(A)P_n\Vert \) instead of \(\left\| P_nAP_n\right\| \).
Step 2\(\{\Xi _{r,p},\Omega _{\textrm{B}},\Lambda _1\}\in \Sigma _2^A\) and \(\{\Xi _{r,p},\Omega _{\textrm{B}},\Lambda _2\}\in \Sigma _1^A\). For the first result, we note that
and let \(\Gamma _{n,m}(A,p)\) be an approximation of \(\Vert P_np(P_{m}AP_m)P_n\Vert \) to accuracy 1/m, which can be computed in finitely many arithmetic operations and comparisons. To prove \(\{\Xi _{r,p},\Omega _{\textrm{B}},\Lambda _2\}\in \Sigma _1^A\), for any given \(A\in \Omega _{\textrm{B}}\) we can use \(\Lambda _2\) to compute a function \(f_A\) and sequence \(\{c_n(A)\}\) bounding the dispersion such that \(A\in \Omega ^{f_A}\) and use step 1.
Step 3\(\{\Xi _{cap},\Omega _\textrm{SA},\Lambda _1\}\notin \Delta ^G_3\). Suppose for a contradiction that \(\{\Gamma _{n_2,n_1}\}\) is a height two (general) tower for the problem and without loss of generality, assume it to be nonnegative. Our strategy will be as in the proof of Theorem 3.3 (recall also the results of Sect. 5). Let \(({\mathcal {M}},d)\) be the space [0, 1] with the usual metric (note in particular this is not discrete so we use remark 5.20), let \({\tilde{\Omega }}\) denote the collection of all infinite matrices \(\{a_{i,j}\}_{i,j\in {\mathbb {N}}}\) with entries \(a_{i,j}\in \{0,1\}\) and consider the problem function
$$\begin{aligned} {\tilde{\Xi }}_2(\{a_{i,j}\}):\text { Does }\{a_{i,j}\}\text { have (only) finitely many columns with (only) finitely many 1's?} \end{aligned}$$
Recall that it is shown in Sect. 5 that \(\textrm{SCI}({\tilde{\Xi }}_2,{\tilde{\Omega }})_{G} = 3\). We will gain a contradiction by using the supposed height two tower to solve \(\{{\tilde{\Xi }}_2,{\tilde{\Omega }}\}\). Without loss of generality, identify \(\Omega _\textrm{SA}\) with self-adjoint operators in \({\mathcal {B}}(X)\) where \(X=\bigoplus _{j=1}^{\infty }X_j\) in the \(l^2\)-sense with \(X_j=l^2({\mathbb {N}})\). To proceed, we need the following elementary lemma, which will be useful in constructing examples of spectral pollution.
Lemma 6.3
Let \(z_1,z_2,\ldots ,z_k\in [-1,1]\) and let \(a_{j}=\sqrt{1-z_j^2}\) (say positive square root). Then, the symmetric matrix
These blocks have eigenvalues \(\{-1,1\}\). \(\square \)
Now choose a sequence of rational numbers \(\{z_j\}_{j\in {\mathbb {N}}}\in [-1,1]\) that is also dense in \([-1,1]\) and let \(B_j=B(z_1,\ldots ,z_j)\). For each column of a given \(\{a_{i,j}\}\in {{\tilde{\Omega }}}\), let the infinite matrix \(C^{(j)}\) be defined as follows. If \(k,l<j+1\) then \(C^{(j)}_{kl}=z_{k}\delta _{k,l}\). Let r(i) denote the row of the ith one of the column \(\{a_{i,j}\}_{i\in {\mathbb {N}}}\) (with \(r(i)=\infty \) if \(\sum _{m}a_{m,j}<i\) and \(r(0)=0\)). If \(r(i)<\infty \) then for \(k\le l\) define
and extend \(C^{(j)}_{kl}\) below the diagonal to a symmetric matrix. The key property of this matrix is that if the column \(\{a_{i,j}\}_{i\in {\mathbb {N}}}\) has infinitely many 1 s, then its is unitarily equivalent to an infinite direct sum of infinitely many \(B_j\) together with the zero operator acting on some subspace (whose dimension is equal to the number of zeros in the column). In this case \(\textrm{Sp}(C^{(j)})=\{-1,1,0\}\) or \(\{-1,1\}\). On the other hand, if \(\{a_{i,j}\}_{i\in {\mathbb {N}}}\) has finitely many 1 s, then \(C^{(j)}\) is unitarily equivalent the direct sum of a finite number of \(B_j\), the diagonal operator \(\textrm{diag}\{z_1,\ldots ,z_k\}\) and the zero operator acting on some subspace. In this case \(\{z_1,\ldots ,z_j\}\subset \textrm{Sp}(C^{(j)})\). Let \(A=\bigoplus _{j=1}^{\infty }C^{(j)}\), then it is clear that if \({{\tilde{\Xi }}}_2(\{a_{i,j}\})=1\), then \(\textrm{Sp}(A)\) is a finite set, otherwise it is the entire interval \([-1,1]\).
Now we use the following facts for bounded self-adjoint operators A. If \(\textrm{Sp}(A)\) is a finite set then \(\Xi _{cap}(A)=0\), whereas if \(\textrm{Sp}(A)=[-1,1]\) then \(\Xi _{cap}(A)=1/2\) (this can be proven easily using the minimal \(l^\infty \) norm property of monic Chebyshev polynomials). We then define \({\tilde{\Gamma }}_{n_2,n_1}(\{a_{i,j}\})=\min \{\max \{1-2\Gamma _{n_2,n_1}(A),0\},1\}\). It is clear that this defines a generalised algorithm. In particular, given N we can evaluate \(\{A_{k,l}:k,l\le N\}\) using only finitely many evaluations of \(\{a_{i,j}\}\), where we can use a bijection between canonical bases of \(l^2({\mathbb {N}})\) and \(\bigoplus _{j=1}^{\infty }X_j\) to view A as acting on \(l^2({\mathbb {N}})\). We also have the convergence \(\lim _{n_2\rightarrow \infty }\lim _{n_1\rightarrow \infty }{\tilde{\Gamma }}_{n_2,n_1}(\{a_{i,j}\})={{\tilde{\Xi }}}_2(\{a_{i,j}\})\), a contradiction.
Step 4\(\{\Xi _{cap},\Omega _{\textrm{D}},\Lambda _2\}\not \in \Delta ^G_2\). This is the same argument as in step 3 of the proof of Theorem 3.3. However, we now replace \(A_m\) by \(A_m=\textrm{diag}\{d_1,d_2,\ldots ,d_m\}\in {\mathbb {C}}^{m\times m}\), where \(\{d_m\}\) is a dense subsequence of \([-1,1]\), and use the fact that \(\Xi _{cap}(B_k)=0\). It follows that given the proposed height one tower \(\{\Gamma _n\}\) and the constructed A, \(\Xi _{cap}(A)=1/2\) but \(\Gamma _{n(k)}(A)<1/4\), the required contradiction.
Step 5\(\{\Xi _{r,p},\Omega _{\textrm{SA}},\Lambda _2\}\not \in \Delta ^G_2\). Recall that we are given some polynomial p of degree at least two. We assume without loss of generality that the zeros of p are \(\pm 1\) and \(\left| p(0)\right| >1\) (the more general case is similar). The argument is similar to step 3 of the proof of Theorem 3.3, but we spell it out since it uses Lemma 6.3. Suppose for a contradiction that a height one tower, \(\{\Gamma _n\}\), solves the problem. We will gain a contradiction by showing that \(\Gamma _n(A)\) does not converge for an operator of the form,
We assume that \(l_r\ge r\) to ensure that the spectrum of A is equal to \(\{-1,1\}\) and hence \(\Xi _{r,p}(A)=0\). Now suppose that \(l_1,\ldots ,l_k\) have been chosen and consider the operator
$$\begin{aligned} B_k=B(z_1)\oplus \cdots \oplus B(z_1,\ldots ,z_{l_k})\oplus C. \end{aligned}$$
The spectrum of \(B_k\) is \([-1,1]\) so that \(\Xi _{r,p}(B_k)>1\) and hence there exists \(n(k)\ge k\) such that \(\Gamma _{n(k)}(B_k)>1/4\). But \(\Gamma _{n(k)}(B_k)\) can only depend on the evaluations of the matrix entries \(\{B_k\}_{ij}=\langle B_ke_j,e_i \rangle \) with \(i,j\le N(B_k,n(k))\) (as well as evaluations of the function f) into account. If we choose \(l_{k+1}>N(B_k,n(k))\) then by the assumptions in Definition 5.1, \(\Gamma _{n(k)}(A)=\Gamma _{n(k)}(B_k)>1/4\). But \(\Gamma _n(A)\) must converge to 0, a contradiction. \(\square \)
Remark 6.4
(Efficiently computing the capacity) Listing the monic polynomials with rational coefficients in the above proof is very inefficient. In practice, it is much better to split the domain of interest into intervals (or squares if in the complex plane, but we stick to the self-adjoint case in the following discussion). Suppose that each interval has dyadic endpoints and a diameter of \(2^{-n_2}\) and that our operator is self-adjoint with known bounded dispersion. One can then apply Lemma 3.21 (denoting the index of that tower by \(n_1\)) to obtain an interval covering of the spectrum which will converge as \(n_1\rightarrow \infty \), modulo the possibility of isolated points of the spectrum located at the endpoints of the intervals. Since the capacity of a compact set is unaltered by adding finitely many points, we do not have to worry about the endpoints—the limit of the capacity of this covering as \(n_1\rightarrow \infty \) will be the capacity of a covering of the spectrum. As \(n_2\rightarrow \infty \), we can use the fact that capacity is right-continuous as a set function (for compact sets \(E_n,E\) with \(E_n\downarrow E\), one has \(\textrm{cap}(E_n)\downarrow \textrm{cap}(E)\)) to obtain a \(\Pi _2^A\) algorithm. The point of this is that it reduces the computation of the resulting tower \(\{\Gamma _{n_2,n_1}\}\) to computing the capacity of finite unions of disjoint closed intervals in \({\mathbb {R}}\). In our computational examples, we made use of the method in [109], which uses conformal mappings and can deal with thousands of intervals.\(\square \)
Proof of Theorem3.10for\(\Xi _{we}\) For the lower bounds, it is enough to note that \(\{\Xi _{we},\Omega _\textrm{D},\Lambda _2\}\not \in \Delta _2^G\) by the same argument as step 1 of the proof of Theorem 3.6. The construction is exactly the same but yields \(d_{\textrm{H}}(\Gamma _{n(k)}(A),\{0\})\le 1/2\), whereas \(\Xi _{we}(A)=[0,1]\). Hence, the proposed height one tower cannot converge. To construct a \(\Pi _2^A\) tower for general operators, we need the following Lemma:
Lemma 7.1
Let \(B\in {\mathbb {C}}^{n\times n}\) and \(\epsilon >0\). Then using finitely many arithmetic operations and comparisons, we can compute points \(z_1,\ldots ,z_k\in {\mathbb {Q}}+i{\mathbb {Q}}\) such that
Recall from step 1 of the proof of Theorem 3.3 that we can compute an upper bound \(M\in {\mathbb {Q}}_+\) for \(\Vert B\Vert \) in finitely many arithmetic operations and comparisons. Now choose points \(x_1,\ldots ,x_k\in {\mathbb {Q}}^n\), each of norm at most 1, such that \(d_{\textrm{H}}(\{x_1,\ldots ,x_k\},\{x\in {\mathbb {C}}^n:\Vert x\Vert =1\})<\epsilon /(3M)\). These can be computed in finitely many arithmetic operations and comparisons using generalised polar coordinates and approximations of trigonometric identities. It follows that
We then let each \(z_j\in {\mathbb {Q}}+i{\mathbb {Q}}\) be a \(\epsilon /4\) approximation of \(\langle Bx_j,x_j\rangle \), which can be computed in finitely many arithmetic operations and comparisons. \(\square \)
Remark 7.2
(Efficient computation) In practice, there are much more efficient methods of computation. For example, the method of Johnson [96], reduces the computation of W(A) for \(A\in {\mathbb {C}}^{n\times n}\) to a series of \(n\times n\) Hermitian eigenvalue problems.\(\square \)
It is well known that for \(A\in \Omega _{\textrm{B}}\),
Given A, let \(\Gamma _{n_2,n_1}(A)\) be a finite collection of points produced by the algorithm in Lemma 7.1 applied to \(B=(I-P_{n_2})P_{n_1+n_2+1}A|_{P_{n_1+n_2+1}(I-P_{n_2}){\mathcal {H}}}\) and \(\epsilon =1/n_1\). The above limits show that \(\{\Gamma _{n_2,n_1}\}\) provides a \(\Pi _2^A\) tower for \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\). \(\square \)
Proof of Theorem3.10for\(\Xi _{poll}^{{\mathbb {F}}}\) We will prove that \(\{\Xi _{poll}^{{\mathbb {R}}},\Omega _\textrm{D},\Lambda _i\}\not \in \Delta ^G_3\) and \(\{\Xi _{poll}^{{\mathbb {C}}},\Omega _{\textrm{B}},\Lambda _1\}\in \Sigma ^A_3\). The construction of towers for \(\Xi _{poll}^{{\mathbb {R}}}\) is similar, as are the arguments for lower bounds.
Step 1\(\{\Xi _{poll}^{{\mathbb {C}}},\Omega _{\textrm{B}},\Lambda _1\}\in \Sigma ^A_3\). Let \(\{{{\tilde{\Gamma }}}_{n_2,n_1}\}\) be the \(\Pi _2^A\) tower for \(\{\Xi _{er},\Omega _{\textrm{B}},\Lambda _1\}\) constructed above. Recall the definition
and that this can be approximated to any given accuracy in finitely many arithmetic operations and comparisons (see also “Appendix A”). We assume that we approximate from below to an accuracy of \(1/n_1\) and call this approximation \(\tilde{\gamma }_{n_2,n_1}\). The function \(\gamma _{n_2,n_1}(z;A)\) is Lipschitz continuous with Lipschitz constant bounded by 1. Define the set
where \(U_{m}\) are the approximations to the open set U. By taking squares of distances to ball centres, we can decide whether a point \(z\in {\mathbb {Q}}+i{\mathbb {Q}}\) has \(\textrm{dist}(z,V_{n_1})<\eta \) for any given \(\eta \in {\mathbb {Q}}_+\). Let \(\Upsilon _{n_2,n_1}(A,U)\) be the finite collection of all \(z\in {{\tilde{\Gamma }}}_{n_2,n_1}(A)\) with \(\textrm{dist}(z,V_{n_1})<1/n_2-1/n_1\). If \(\Upsilon _{n_2,n_1}(A,U)\) is empty then set \(Q_{n_2,n_1}(A,U)=0\), otherwise set
The above remarks show that this can be computed using finitely many arithmetic operations and comparisons.
Let \(W_{n_2}=\overline{W((I-P_{n_2})A|_{(I-P_{n_2}){\mathcal {H}}})}\) and \(W_{n_2,n_1}=W((I-P_{n_2})P_{n_1+n_2+1}A|_{P_{n_1+n_2+1}(I-P_{n_2}){\mathcal {H}}})\). We claim that the set \(\Upsilon _{n_2,n_1}(A,U)\) converges to
as \(n_1\rightarrow \infty \), meaning also if \(\Upsilon _{n_2}(A,U)\) is empty then \(\Upsilon _{n_2,n_1}(A,U)\) is empty for large \(n_1\). If \(z\in \Upsilon _{n_2,n_1}(A,U)\), then there exists \({\hat{z}}\in W_{n_2,n_1}\subset W_{n_2}\) with \(\left| z-{\hat{z}}\right| \le 1/{n_1}\). Since
it follows that \(\textrm{dist}({\hat{z}},{\overline{U}})<{1}/{n_2}\) and hence \(\Upsilon _{n_2}(A,U)\) is non-empty. So to prove convergence, we only need to deal with the case \(\Upsilon _{n_2}(A,U)\ne \emptyset \). The above argument also shows that any limit point of a subsequence \(z_{m(j)}\in \Upsilon _{n_2,m(j)}(A,U)\) must lie in \(\Upsilon _{n_2}(A,U)\). Hence to prove the claim, we need to only prove that for any \(z\in \Upsilon _{n_2}(A,U)\), there exists \(z_{n_1}\) that are contained in \(\Upsilon _{n_2,n_1}(A,U)\) for large \(n_1\) and converge to z.
Let \(z\in W_{n_2} \) with \(\textrm{dist}(z,{\overline{U}})<{1}/{n_2}\), then there exists \(\epsilon >0\) and \(j>0\) such that \(\textrm{dist}(z,U_j)<{1}/{n_2}-\epsilon \). There also exists \(z_{n_1}\in {{\tilde{\Gamma }}}_{n_2,n_1}(A)\) with \(z_{n_1}\rightarrow z\). It must hold for \(n_1>j\) that
This last quantity is smaller than \(1/n_2-1/n_1\) for large \(n_1\) and hence \(z_{n_1}\in \Upsilon _{n_2,n_1}(A,U)\) for large \(n_1\). It follows for any \(z\in \Upsilon _{n_2}(A,U)\), there exists \(z_{n_1}\) that are contained in \(\Upsilon _{n_2,n_1}(A,U)\) for large \(n_1\) and converge to z.
where we recall that \(\gamma _{n_2}(z;A)=\min \{\sigma _{\textrm{inf}}((A-zI){|_{P_{n_2}{\mathcal {H}}}}),\sigma _{\textrm{inf}}((A^*-{\bar{z}}I){|_{P_{n_2}{\mathcal {H}}}})\}.\) If \(z\in \Upsilon _{n_2,n_1}(A,U)\), then the above shows that there exists \({\hat{z}}\in \Upsilon _{n_2}(A,U)\) with \(\left| z-{\hat{z}}\right| \le 1/{n_1}\). It follows that
where we have used the bound on the Lipschitz constant and the fact that \(\gamma _{n_2,n_1}\) converge up to \(\gamma _{n_2}\) (and uniformly on compact subsets of \({\mathbb {C}}\)). It follows that \(Q_{n_2,n_1}(A,U)\le Q_{n_2}(A,U)\) and this also covers the case that \(\Upsilon _{n_2}(A,U)=\emptyset \) if we define the supremum over the empty set to be 0. The set convergence proven above and uniform convergence of \({{\tilde{\gamma }}}_{n_2,n_1}\) implies that \(Q_{n_2,n_1}(A,U)\) converges to \(Q_{n_2}(A,U)\). It is also clear that the \(\Upsilon _{n_2}(A,U)\) are nested and converge down to \(W_e(A)\cap {\overline{U}}\) since \(W_{n_2}\) converges down to \(W_{e}(A)\). The functions \(\gamma _{n_2}\) also converge down to
where ± denotes one of the right or left limits (it is possible to have either). Now if \(\Xi _{poll}^{{\mathbb {C}}}(A,U)=0\), then \(\Gamma _{n_3}(A,U)=0\) for all \(n_3\). But if \(\Xi _{poll}^{{\mathbb {C}}}(A,U)=1\), then for large \(n_3\), \(\Gamma _{n_3}(A,U)=1\). Moreover, in this latter case, \(\Gamma _{n_3}(A,U)=1\) signifies the existence of \(z\in W_e(A)\cap {\overline{U}}\) with \(\gamma (z;A)>0\) and hence \(z\not \in \textrm{Sp}(A)\). Hence, \(\{\Gamma _{n_3,n_2,n_1}\}\) provides a \(\Sigma _3^A\) tower.
Step 2\(\{\Xi _{poll}^{{\mathbb {R}}},\Omega _{\textrm{D}},\Lambda _2\}\not \in \Delta ^G_3\). We will argue for the case that \(U=U_1={\mathbb {R}}\) and the restricted case is similar. Assume for a contradiction that this is false and that \(\{{\widehat{\Gamma }}_{n_2,n_1}\}\) is a general height two tower for \(\{\Xi _{poll}^{{\mathbb {R}}},\Omega _{\textrm{D}},\Lambda _2\}\). We follow the same strategy as the proof of Theorem 3.3 step 4 (recall also the results of Sect. 5). Let \(({\mathcal {M}},d)\) be discrete space \(\{0,1\}\) and \({{\tilde{\Omega }}}\) denote the collection of all infinite matrices \(\{a_{i,j}\}_{i,j\in {\mathbb {N}}}\) with entries \(a_{i,j}\in \{0,1\}\) and consider the problem function
$$\begin{aligned} {{\tilde{\Xi }}}_1(\{a_{i,j}\}):\text { Does }\{a_{i,j}\}\text { have a column containing infinitely many nonzero entries?} \end{aligned}$$
For \(j\in {\mathbb {N}}\), let \(\{b_{i,j}\}_{i\in {\mathbb {N}}}\) be a dense subset of \(I_j:=[1-1/2^{2j-1},1-1/{2^{2j}}]\). Given a matrix \(\{a_{i,j}\}_{i,j\in {\mathbb {N}}}\in {{\tilde{\Omega }}}\), construct a matrix \(\{c_{i,j}\}_{i,j\in {\mathbb {N}}}\) by letting \(c_{i,j}=a_{i,j}b_{r(i,j),j}\) where
The algorithm \({\widehat{\Gamma }}_{n_2,n_1}\) thus translates to an algorithm \(\Gamma '_{n_2,n_1}\) for \(\{{{\tilde{\Xi }}}_1,{{\tilde{\Omega }}}\}\). Namely, set \(\Gamma '_{n_2,n_1}(\{a_{i,j}\}_{i\in {\mathbb {N}}})={\widehat{\Gamma }}_{n_2,n_1}(A)\). The fact that \(\phi \) is a bijection shows that the lowest level \(\Gamma '_{n_2,n_1}\) are generalised algorithms (and are consistent). In particular, given N, we can find \(\{A_{i,j}:i,j\le N\}\) using finitely many evaluations of the matrix values \(\{c_{k,l}\}\) (the same is true for \(A^*A\) and \(AA^*\) since the operator is diagonal). But for any given \(c_{k,l}\) we can evaluate this entry using only finitely many evaluations of the matrix values \(\{a_{m,n}\}\) by the construction of r. Finally, note that
$$\begin{aligned} \textrm{Sp}(A)=\{1\}\cup \left( \bigcup _{j:\{a_{i,j}\}_{i\in {\mathbb {N}}}\text { has infinitely many 1s}}I_j\right) \cup Q, \end{aligned}$$
where Q lies in the discrete spectrum. The intervals \(I_j\) are also separated. It follows that there is a gap in the essential spectrum if and only if there exists a column \(\{a_{i,j}\}_{i\in {\mathbb {N}}}\) with infinitely many 1 s. Otherwise the essential spectrum is \(\{1\}\). It follows that \(\tilde{\Xi }(\{a_{i,j}\})=\Xi _{poll}^{{\mathbb {R}}}(A,{\mathbb {R}})\), and hence, we get a contradiction. \(\square \)
7.1 Essential Numerical Range for Unbounded Operators
The essential numerical range (see (3.1)) was first introduced for a bounded operator A in [152], as the closure of the numerical range of the image of A in the Calkin algebra:
Other equivalent characterisations were then given in [82]. The unbounded case is significantly different from the bounded case, and definitions that are equivalent in the bounded case may yield very different sets in the unbounded case. The definition for unbounded operators appeared in [34] and required the development of several new ideas and tools. In this section, we let \(\Omega _{{\mathcal {C}}}\) denote the set of closed operators T with domain \({\mathcal {D}}(T)\subset l^2({\mathbb {N}})\) such that the linear span of the canonical basis forms a core of T. This latter condition ensures that we can use the usual matrix representation of the operator T and hence the evaluation functions \(\Lambda _1\). We follow [34] and define
In [34], it was shown that for any \(T\in \Omega _{{\mathcal {C}}}\), \(W_e(T)\) consists precisely of the essential spectrum of T together with all possible spectral pollution that may arise by applying projection methods to find the spectrum of T numerically. This result therefore generalises Theorems 3.8 and 3.9. The set \(W_e(T)\) is closed and convex, but, unlike the case when T is bounded, \(W_e(T)\) may be empty. We first need two simple lemmas.
Lemma 7.3
Let \(T\in \Omega _{{\mathcal {C}}}\), then \(W(P_nT|_{P_n{\mathcal {H}}})\uparrow \overline{W(T)}\) in the Attouch–Wets topology as \(n\rightarrow \infty \).
and that the sets \(W(P_nT|_{P_n{\mathcal {H}}})\) are increasing with n. Now let \(\lambda \in \overline{W(T)}\) be arbitrary. It is enough to show that there exists \(\lambda _n\in W(P_nT|_{P_n{\mathcal {H}}})\) such that \(\lambda _n\rightarrow \lambda \) as \(n\rightarrow \infty \). By assumption, there exists \(x_n\in {\mathcal {D}}(T)\) such that \(\Vert x_n\Vert =1\) and \(\lim _{n\rightarrow \infty }\langle Tx_n,x_n\rangle =\lambda \). Since the linear span of the canonical basis forms a core of T, we can assume without loss of generality that each \(x_n\) has finite support with respect to the canonical basis. By taking subsequences if necessary, we may assume that \(P_nx_n=x_n\) and hence \(\langle Tx_n,x_n\rangle \in W(P_nT|_{P_n{\mathcal {H}}})\). The result now follows. \(\square \)
Lemma 7.4
Let \(T\in \Omega _{{\mathcal {C}}}\). If \(W_e(T)\ne \emptyset \), then \(\overline{W((I-P_n)T|_{(I-P_n){\mathcal {H}}})}\downarrow W_{e}(T)\) in the Attouch–Wets topology as \(n\rightarrow \infty \). If \(W_e(T)=\emptyset \), then for any compact set K, \(K\cap \overline{W((I-P_n)T|_{(I-P_n){\mathcal {H}}})}=\emptyset \) for large n.
Proof
We clearly have that \(\overline{W((I-P_n)T|_{(I-P_n){\mathcal {H}}})}\) are non-empty and decreasing in n. It is enough to show the following two results:
(1)
If \(\lambda \in W_e(T)\), then \(\lambda \in \overline{W((I-P_n)T|_{(I-P_n){\mathcal {H}}})}\) for all n.
(2)
If \(\lambda \notin W_e(T)\), then \(\liminf _{n\rightarrow \infty } \textrm{dist}(\lambda ,\overline{W((I-P_n)T|_{(I-P_n){\mathcal {H}}})})>0\).
We first prove (1), so assume that \(\lambda \in W_e(T)\). Then, since the linear span of the canonical basis functions form a core of T, we can assume that there exists \(x_n\) with \(\Vert x_n\Vert =1\) such that each \(x_n\) has finite support with respect to the canonical basis, \(x_n\xrightarrow {w}0\) and \(\lim _{n\rightarrow \infty }\langle Tx_n,x_n\rangle =\lambda \). It follows that for any fixed m, \(\lim _{n\rightarrow \infty }P_mx_n=0\) and hence \(\lambda \in \overline{W((I-P_m)T|_{(I-P_m){\mathcal {H}}})}\).
Finally, to see (2), suppose that this were false for some \(\lambda \notin W_e(T)\). We may then choose \(\lambda _n\in \overline{W((I-P_n)T|_{(I-P_n){\mathcal {H}}})}\) such that \(\liminf _{n\rightarrow \infty } |\lambda -\lambda _n|=0\). By taking subsequences if necessary, we may assume that \(\lambda _n\rightarrow \lambda \) and that there exists \(x_n\) with \(\Vert x_n\Vert =1\), \(P_{n}x_n=0\) and \(|\langle Tx_n,x_n\rangle -\lambda _n|\rightarrow 0\). But this implies that \(x_n\xrightarrow {w}0\) and \(\lim _{n\rightarrow \infty }\langle Tx_n,x_n\rangle =\lambda \). Therefore, \(\lambda \in W_e(T)\), the required contradiction. \(\square \)
We have the following corollary, which shows that the SCI classification of computing \(W_e(T)\) for \(T\in \Omega _{{\mathcal {C}}}\) remains \(\Pi _2^A\) (one can make this precise by adding the empty set to the Attouch–Wets topology, but we omit the details).
Corollary 7.5
There exists a height two tower of arithmetic algorithms \(\{\Gamma _{n_2,n_1}\}\), using \(\Lambda _1\) (the matrix values with respect to the canonical basis) and \(\Delta _1-\)information (see Definition 5.11), such that for any \(T\in \Omega _{{\mathcal {C}}}\), the following hold with respect to the Attouch–Wets topology:
\(\Gamma _{n_2,n_1}(T)\uparrow \Gamma _{n_2}(T)\subset \overline{W(T)}\) as \(n_1\rightarrow \infty \).
If \(W_e(T)\ne \emptyset \), then \(\Gamma _{n_2}(T)\downarrow W_{e}(T)\) as \(n_2\rightarrow \infty \). If \(W_e(T)=\emptyset \), then for any compact set K, \(K\cap \Gamma _{n_2}(T)=\emptyset \) for large \(n_2\).
Proof
We simply let \(\Gamma _{n_2,n_1}(T)\) be an approximation of
that can be computed in finitely many arithmetic operations and comparisons, even when using inexact input (see Definition 5.11 and Remark 5.12), using the arguments in Sect. 7. The results now follow from Lemmas 7.3 and 7.4. \(\square \)
8 Proofs Concerning Lebesgue Measure
We use the function \(\texttt {DistSpec}\) in “Appendix A”. For ease of notation, we suppress the dispersion function f in calling \(\texttt {DistSpec}\), but assume that we know \(\{c_n\}\) with \(D_{f,n}(A)\le c_n\) and \(c_n\rightarrow 0\) as \(n\rightarrow \infty \). However, the proof of convergence also works when using \(c_n=0\) (which does not necessarily bound \(D_{f,n}(A)\)). The key observation is the following:
Observation: If \(A\in \Omega _f\), then the function \(F_n(z):=\texttt {DistSpec}(A,n,z,f(n))+c_n\) converges uniformly to \(\left\| R(z,A)\right\| ^{-1}\) from above on compact subsets of \({\mathbb {C}}\). By taking successive minima, we can assume without loss of generality that \(F_n\) is non-increasing in n.
The other ingredient needed is the following proposition
Proposition 8.1
Given a finite union of disks in the complex plane, the Lebesgue measure of their intersection with the interior of a rectangle can be computed within arbitrary precision, using finitely many arithmetical operations and comparisons on the centres and radii of the discs, as well as the position of the rectangle.
Proof
Without loss of generality, we assume that the rectangle is \(\{x+iy:x,y\in [0,1]\}\). Consider dividing the rectangle into \(n^2\) subrectangles using the division of [0, 1] into n equal intervals. Given such a subrectangle, we can easily test via a finite number of arithmetic operations and comparisons whether the centre is in the union of the circles. Let r(n) denote the number of subrectangles whose centre lies in the union. Then, since the boundary of the union of the circles has measure zero, it is easy to see that \(r(n)/n^2\) converges to the desired Lebesgue measure. Moreover, we can bound the number of subrectangles that intersect the boundary of any of the circles, and this can be used to obtain any desired precision. \(\square \)
Proof of Theorem 3.13
Step 1\(\{\Xi _1^L,\Omega _f,\Lambda _i\},\{\Xi _1^L,\Omega _\textrm{D},\Lambda _i\}\in \Pi ^A_2\). It is enough to consider \(\Lambda _1\). We will estimate \(\textrm{Leb}(\textrm{Sp}(A))\) by estimating the Lebesgue measure of the resolvent set on the closed square \([-C,C]^2\), where \(\left\| A\right\| \le C\). We do not assume C is known. For \(n_1,n_2\in {\mathbb {N}}\), let
Letting B(x, r) and D(x, r) denote the closed and open balls of radius r around x, respectively,18 in \({\mathbb {C}}\) (or \({\mathbb {R}}\) where appropriate), we define
Note that \(\textrm{Leb}(U(n_1,n_2,A))\) can be computed up to arbitrary predetermined precision using only arithmetic operations and comparisons by Proposition 8.1. Using this, we can define
where, without loss of generality, we assume that we have computed the exact value of the Lebesgue measure (since we can absorb this error in the first limit). \(\Gamma _{n_2,n_1}\) are arithmetical algorithms using the fact that \(\texttt {DistSpec}\) is and the above proposition. The only non-trivial part is convergence. The algorithm is summarised in the routine LebSpec in § B.3.
We now show that the algorithm LebSpec converges and realises the \(\Pi _2^A\) classification. There exists a compact set K such that \(\left\| R(z,A)\right\| ^{-1}> 1\) on \(K^c\) and without loss of generality we can make C larger, \(C\in {\mathbb {N}}\) and take \(K=[-C,C]^2\). For \(n_1\ge C\)
Clearly, \(\textrm{Leb}(K(n_2,A))=\textrm{Leb}(V(n_2,A))\) since the sets differ by a finite collection of circular arcs or points (recall we defined the open ball of radius zero to be the empty set). Hence, we must show that
and hence we get \(V(n_2,A)\subset \rho _{C}(A)\). Since \(\rho _C(A)\) is relatively open, a simple density argument using the continuity of \(\left\| R(z,A)\right\| ^{-1}\) yields \(V(n_2,A)\uparrow \rho _{C}(A)\) as \(n_2\rightarrow \infty \) since the grid refines itself. So we get
This proves the convergence and also shows that \(\Gamma _{n_2}(A)\downarrow \Xi _1^L(A)\), thus yielding the \(\Pi _2^A\) classification. The same argument works in the one-dimensional case when considering self-adjoint operators \(\Omega _{\textrm{D}}\) and \(\textrm{Leb}_{{\mathbb {R}}}\). We simply restrict everything to the real line and consider the interval \([-C,C]\) rather than a square.
Step 2\(\{\Xi _1^L,\Omega _f,\Lambda _i\},\{\Xi _1^L,\Omega _\textrm{D},\Lambda _i\}\notin \Delta ^G_2\). It is enough to consider \(\Lambda _2\). We will only show that \(\textrm{SCI}(\Xi _1^L,\Omega _\textrm{D},\Lambda _2)_{G} \ge 2\) for which we use \(\textrm{Leb}_{{\mathbb {R}}}\) and the two-dimensional case is similar. Suppose for a contradiction that there exists a height one tower \(\{\Gamma _n\}\), then \(\Lambda _{\Gamma _n}(A)\) is finite for each \(A\in \Omega _\textrm{D}\). Hence, for every A and n there exists a finite number \(N(A,n)\in {\mathbb {N}}\) such that the evaluations from \(\Lambda _{\Gamma _n}(A)\) only take the matrix entries \(A_{ij} = \left\langle Ae_j, e_i\right\rangle \) with \(i,j\le N(A,n)\) into account.
Pick any sequence \(a_1,a_2,\ldots \) that is dense in the unit interval [0, 1]. Consider the matrix operators \(A_m=\textrm{diag}\{a_1,a_2,\ldots ,a_m\}\in {\mathbb {C}}^{m\times m}\), \(B_m=\textrm{diag}\{0,0,\ldots ,0\}\in {\mathbb {C}}^{m\times m}\) and \(C=\textrm{diag}\{0,0,\ldots \}\). Set \(A=\bigoplus _{m=1}^{\infty }(B_{k_m}\oplus A_{k_m})\), where we choose an increasing sequence \(k_m\) inductively as follows. Set \(k_1=1\) and suppose that \(k_1,\ldots ,k_m\) have been chosen. \(\textrm{Sp}(B_{k_1}\oplus A_{k_1}\oplus \cdots \oplus B_{k_m}\oplus A_{k_m}\oplus C)=\{0,a_1,a_2,\ldots ,a_{k_m}\}\) and hence \(\textrm{Leb}(\textrm{Sp}(B_{k_1}\oplus A_{k_1}\oplus \cdots \oplus B_{k_m}\oplus A_{k_m}\oplus C))=0\) so there exists some \(n_m\ge m\) such that if \(n\ge n_m\) then
Now let \(k_{m+1}\ge \max \{N(B_{k_1}\oplus A_{k_1}\oplus \cdots \oplus B_{k_m}\oplus A_{k_m}\oplus C,n_m),k_m+1\}\). Any evaluation function \(f_{i,j}\in \Lambda \) is simply the \((i,j)^{\textrm{th}}\) matrix entry and hence by construction
for all \(f_{i,j}\in \Lambda _{\Gamma _{n_m}}(B_{k_1}\oplus A_{k_1}\oplus \cdots \oplus B_{k_m}\oplus A_{k_m}\oplus C)\). By assumption (iii) in Definition 5.1, it follows that \(\Lambda _{\Gamma _{n_m}}(B_{k_1}\oplus A_{k_1}\oplus \cdots \oplus B_{k_m}\oplus A_{k_m}\oplus C)=\Lambda _{\Gamma _{n_m}}(A)\) and hence by assumption (ii) in the same definition that \(\Gamma _{n_m}(A)=\Gamma _{n_m}(B_{k_1}\oplus A_{k_1}\oplus \cdots \oplus B_{k_m}\oplus A_{k_m}\oplus C)\le 1/2\). But \(\lim _{n\rightarrow \infty }(\Gamma _n(A))=\textrm{Leb}(\overline{\{0,a_1,a_2,\ldots \}})=1\), a contradiction.
Step 3\(\{\Xi _1^L,\Omega ,\Lambda _1\}\in \Pi ^A_3\) for \(\Omega =\Omega _{\textrm{B}},\Omega _\textrm{SA}\), \(\Omega _\textrm{N}\) or \(\Omega _g\). We will deal with the case of \(\Omega _{\textrm{B}}\). The cases of \(\Omega _\textrm{N}\) and \(\Omega _g\) then follow via \(\Omega _{\textrm{N}}\subset \Omega _{g}\subset \Omega _{\textrm{B}}\) and the one-dimensional Lebesgue measure case for \(\Omega _\textrm{SA}\) is similar. A careful analysis of the proof in step 1 yields that
\(\Gamma _{n_2,n_1}(A)\) converges to \(\Gamma _{n_2}(A)\) from below as \(n_1\rightarrow \infty \).
\(\Gamma _{n_2}(A)\) converges to \(\textrm{Leb}(\textrm{Sp}(A))\) monotonically from above as \(n_2\rightarrow \infty \).
We can ensure that the first limit converges from below by always slightly overestimating the Lebesgue measure of \(U(n_1,n_2)\) (with error converging to zero) and using Proposition 8.1. These observations will be used later to answer question 3. We do not need to know \(c_n\) for the above proof to work, but we will need it for the first of the above facts. A slight alteration of the proof/algorithm by inserting an additional successive limit deals with the general case.
where \(\sigma _{\textrm{inf}}\) denotes the injection modulus/smallest singular value (see also “Appendix A”). One can show that \(\gamma _{n,m}\) converges uniformly on compact subsets to
as \(m\rightarrow \infty \) and that this converges uniformly down to \(\left\| R(z,A)\right\| ^{-1}\) on compact subsets as \(n\rightarrow \infty \) [91]. With a slight abuse of notation, we can approximate \(\gamma _{n,m}(z;A)\) to within 1/m by \(\texttt {DistSpec}(A,n,z,m)\) (where the spacing of the search routine is 1/m, see also “Appendix A”) so that this converges uniformly on compact subsets to \(\gamma _{n}(z;A)\). In exactly the same manner as before, define
The stated uniform convergence means that the argument in step 1 carries through and we have a height three tower, realising the \(\Pi ^A_3\) classification.
Step 4\(\{\Xi _1^L,\Omega _\textrm{SA},\Lambda _1\}\notin \Delta ^G_3\). The proof is exactly the same argument as the proof of step 3 of Theorem 3.7. However, in this case to gain the contradiction, we then define \({\tilde{\Gamma }}_{n_2,n_1}(\{a_{i,j}\})=\min \{\max \{1-\Gamma _{n_2,n_1}(A)/2,0\},1\}\) where \(\{\Gamma _{n_2,n_1}\}\) is the supposed height two tower for \(\{\Xi _1^L,\Omega _\textrm{SA},\Lambda _1\}\).
Step 5\(\{\Xi _1^L,\Omega ,\Lambda _1\}\notin \Delta ^G_3\) for \(\Omega =\Omega _{\textrm{B}},\Omega _{\textrm{N}}\), or \(\Omega _g\). Since \(\Omega _\textrm{N}\subset \Omega _g\subset \Omega _{\textrm{B}}\), we only need to deal with \(\Omega _\textrm{N}\). We can use a similar argument as in step 4, but now replacing each \(C^{(j)}\) by
where \(h_1,h_2,\ldots \) is a dense sequence in [0, 1], and these operators act on \(X_j=\bigoplus _{k=1}^j l^2({\mathbb {N}})\). This ensures that the spectrum of the operator yields a positive two-dimensional Lebesgue measure if and only if \({{\tilde{\Xi }}}_2(\{a_{i,j}\})=0\). The rest of the argument is entirely analogous.
Step 6\(\Delta ^G_2 \not \ni \{\Xi _1^L,\Omega ,\Lambda _2\}\in \Pi ^A_2\) for \(\Omega =\Omega _{\textrm{B}},\Omega _\textrm{SA}\), \(\Omega _\textrm{N}\) or \(\Omega _g\). The impossibility result follows by considering diagonal operators. For the existence of \(\Pi ^A_2\) algorithms, we can use the construction in step 3, but the knowledge of matrix values of \(A^*A\) allows us to skip the first limit and approximate \(\gamma _n\) directly. \(\square \)
Proposition 8.1 shows that, without loss of generality, we can assume \(\Gamma _n(A)\) can be computed exactly using finitely many arithmetic operations and comparisons. The algorithm is presented in the LebPseudoSpec routine in § B.3 and the following shows that this algorithm is sharp in the SCI hierarchy.
Suppose that \(F_n(z)<\epsilon \) and that \(\left| w\right| <\epsilon -F_n(z)\). If \(z\in \textrm{Sp}(A)\), then clearly
It follows that \(\cup _{z\in E_n}D(z,\max \{0,\epsilon -F_n(z)\})\) is in \(\widehat{\textrm{Sp}}_{\epsilon }(A)\) and hence that \(\Gamma _{n}(A)\le \Xi _2^L(A)\). Without loss of generality by taking successive maxima, we can assume that \(\Gamma _{n}(A)\) is increasing. Together, these will yield the \(\Sigma ^A_1\) classification once convergence is shown. Using the uniform convergence of \(F_n\) and density of \(1/n({\mathbb {Z}}+i{\mathbb {Z}})\cap [-n,n]^2\), we see that pointwise convergence holds:
where \(\chi _E\) denotes the indicator function of a set E. It follows by the dominated convergence theorem that \(\Gamma _n(A)\rightarrow \textrm{Leb}(\widehat{\textrm{Sp}}_{\epsilon }(A))\). The proof for \(\Omega _{\textrm{D}}\) is similar by restricting everything to the real line.
Step 2\(\{\Xi _2^L,\Omega ,\Lambda _1\}\in \Sigma _2^A\) for \(\Omega =\Omega _{\textrm{B}},\Omega _\textrm{SA}\), \(\Omega _\textrm{N}\) or \(\Omega _g\). To prove this, we simply replace \(F_{n_1}\) by the functions \(\gamma _{n_2,n_1}\) and set
Step 3\(\{\Xi _2^L,\Omega ,\Lambda _2\}\in \Sigma _1^A\) for \(\Omega =\Omega _{\textrm{B}},\Omega _\textrm{SA}\), \(\Omega _\textrm{N}\) or \(\Omega _g\). The knowledge of matrix values of \(A^*A\) allows us to skip the first limit in the construction of step 2 and approximate \(\gamma _n\) directly. \(\square \)
Proof of Proposition 3.15
We begin with the proof of 1. Suppose \(A\in \Omega _\textrm{D}\) has \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(A))=0\) and let \(A_n\in \Omega _\textrm{D}\) be such that \(\left\| A-A_n\right\| \rightarrow 0\) as \(n\rightarrow \infty \). This implies that \(\textrm{Sp}(A_n)\rightarrow \textrm{Sp}(A)\) since all our operators are normal. To prove that \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(A_n))\rightarrow 0\), it is enough to prove that
where \(F_n=\textrm{Sp}(A)\cup (\cup _{m\ge n}\textrm{Sp}(A_m))\). But \(F_n\) decreases to \(\textrm{Sp}(A)\) and is bounded in measure, so (8.1) holds. For the converse, let \(\textrm{Leb}_{{\mathbb {R}}}(\textrm{Sp}(A))>0\). Without loss of generality, assume that all of A’s entries lie in [0, 1]. Let \({\mathbb {D}}_n\) denote the set \(\{j/2^n\}_{j=1}^n\) and consider the map \( \phi _n:x\hookrightarrow 2^{-n}\left\lceil x2^n\right\rceil \) on [0, 1]. Let \(A_n\) be the diagonal operator obtained by applying \(\phi _n\) to each of A’s entries. We clearly have that \(\left\| A-A_n\right\| \rightarrow 0\) as \(n\rightarrow \infty \) but note that \(\textrm{Sp}(A_n)\) is finite so has Lebesgue measure 0. Hence \(\Xi _1^L\) is discontinuous at A.
To prove 2, note that for \(A\in \Omega _\textrm{D}\), \(\textrm{Leb}_{{\mathbb {R}}}(S_{\epsilon }(A))=0\). Let \(A_n\in \Omega _\textrm{D}\) have \(\left\| A-A_n\right\| \rightarrow 0\). Then given some \(0<\delta <\epsilon \) it holds for large n that \( \textrm{Sp}_{\epsilon -\delta }(A)\subset \textrm{Sp}_{\epsilon }(A_n)\subset \textrm{Sp}_{\epsilon +\delta }(A) \) and hence that
Now let \(\delta \downarrow 0\) and use the fact that \(\Xi _2^L\) is continuous in \(\epsilon \). \(\square \)
Finally, we deal with the question of determining whether the Lebesgue measure is zero. Recall that for this problem, \(({\mathcal {M}},d)\) denotes the set \(\{0,1\}\) endowed with the discrete topology and we consider the problem function
We will show that \(\{\Xi _3^L,\Omega _f,\Lambda _1\}\in \Pi _3^A\) and \(\{\Xi _3^L,\Omega _\textrm{D},\Lambda _2\}\notin \Delta _3^G\). The analogous statements \(\{\Xi _3^L,\Omega _\textrm{D},\Lambda _1\}\in \Pi _3^A\) and \(\{\Xi _3^L,\Omega _f,\Lambda _2\}\notin \Delta _3^G \) follow from similar arguments.
The lower bound argument can also be used when considering \(\Lambda _2\) and \(\Omega =\Omega _{\textrm{B}},\Omega _\textrm{SA}\), \(\Omega _\textrm{N}\) or \(\Omega _g\). We will also prove the lower bound \(\{\Xi _3^L,\Omega _\textrm{SA},\Lambda _1\}\notin \Delta _4^G\). The remaining lower bounds for \(\Lambda _1\) follow from a similar argument and construction as in step 5 of the proof of Theorem 3.13 to ensure we are dealing with two-dimensional Lebesgue measure. Finally, we prove that \(\{\Xi _3^L,\Omega _{\textrm{B}},\Lambda _1\}\in \Pi _4^A\). The upper bounds for \(\Omega =\Omega _\textrm{SA}\), \(\Omega _\textrm{N}\) or \(\Omega _g\) and \(\Lambda _1\) follow an almost identical argument. When considering \(\Lambda _2\), we can collapse the first limit in the same manner as we did for solving \(\Xi _1^L\).
Step 1\(\{\Xi _3^L,\Omega _f,\Lambda _1\}\in \Pi _3^A\). First we use the algorithm used to compute \(\Xi _1^L\) in Theorem 3.13, which we shall denote by \({\widetilde{\Gamma }}\), to build a height 3 tower for \(\{\Xi _3^L,\Omega _f\}\). As above, \(\Omega _f\) denotes the set of bounded operators with the usual assumption of bounded dispersion (now with known bounds \(c_n\)). Recall that we observed
\({\widetilde{\Gamma }}_{n_2,n_1}(A)\) converges to \({\widetilde{\Gamma }}_{n_2}(A)\) from below as \(n_1\rightarrow \infty \).
\({\widetilde{\Gamma }}_{n_2}(A)\) converges to \(\textrm{Leb}(\textrm{Sp}(A))\) monotonically from above as \(n_2\rightarrow \infty \).
We can alter our algorithms, by taking maxima, so that we can assume without loss of generality that \({\widetilde{\Gamma }}_{n_2,n_1}(A)\) converges to \({\widetilde{\Gamma }}_{n_2}(A)\)monotonically from below as \(n_1\rightarrow \infty \). Now let
It is also clear that the answer to the question is “No” if \(\Gamma _{n_3}(A)=0\), which yields the \(\Pi _3^A\) classification.
Step 2\(\{\Xi _3^L,\Omega _\textrm{D},\Lambda _1\}\notin \Delta _3^G\). Assume for a contradiction that this is false and \(\{{\widehat{\Gamma }}_{n_2,n_1}\}\) is a general height two tower for \(\{\Xi _3^L,\Omega _\textrm{D}\}\). Let \(({\mathcal {M}},d)\) be discrete space \(\{0,1\}\) and \({{\tilde{\Omega }}}\) denote the collection of all infinite matrices \(\{a_{i,j}\}_{i,j\in {\mathbb {N}}}\) with entries \(a_{i,j}\in \{0,1\}\) and consider the problem function
$$\begin{aligned} {{\tilde{\Xi }}}_1(\{a_{i,j}\}):\text { Does }\{a_{i,j}\}\text { have a column containing infinitely many nonzero entries?} \end{aligned}$$
For \(j\in {\mathbb {N}}\), let \(\{b_{i,j}\}_{i\in {\mathbb {N}}}\) be a dense subset of \(I_j:=[1-1/2^{j-1},1-1/{2^j}]\). Given a matrix \(\{a_{i,j}\}_{i,j\in {\mathbb {N}}}\in {{\tilde{\Omega }}}\), construct a matrix \(\{c_{i,j}\}_{i,j\in {\mathbb {N}}}\) by letting \(c_{i,j}=a_{i,j}b_{r(i,j),j}\) where
The algorithm \({\widehat{\Gamma }}_{n_2,n_1}\) thus translates to an algorithm \(\Gamma '_{n_2,n_1}\) for \(\{{{\tilde{\Xi }}}_1,{{\tilde{\Omega }}}\}\). Namely, set \(\Gamma '_{n_2,n_1}(\{a_{i,j}\}_{i\in {\mathbb {N}}})={\widehat{\Gamma }}_{n_2,n_1}(A)\). The fact that \(\phi \) is a bijection shows that the lowest level \(\Gamma '_{n_2,n_1}\) are generalised algorithms (and are consistent). In particular, given N, we can find \(\{A_{i,j}:i,j\le N\}\) using finitely many evaluations of the matrix values \(\{c_{k,l}\}\). But for any given \(c_{k,l}\), we can evaluate this entry using only finitely many evaluations of the matrix values \(\{a_{m,n}\}\) by the construction of r. Finally note that
$$\begin{aligned} \textrm{Sp}(A)=\left( \bigcup _{j:\sum _ia_{i,j}=\infty }I_j\right) \cup Q, \end{aligned}$$
It follows that \({{\tilde{\Xi }}}_1(\{a_{i,j}\})=\Xi _3^L(A)\), and hence, we get a contradiction.
Step 3\(\{\Xi _3^L,\Omega _\textrm{SA},\Lambda _1\}\notin \Delta _4^G\). Suppose for a contradiction that \(\{\Gamma _{n_3,n_2,n_1}\}\) is a height three tower of general algorithms for the problem \(\{\Xi _3^L,\Omega _\textrm{SA},\Lambda _1\}\). Let \(({\mathcal {M}},d)\) be the space \(\{0,1\}\) with the discrete metric, let \({\tilde{\Omega }}\) denote the collection of all infinite arrays \(\{a_{m,i,j}\}_{m,i,j\in {\mathbb {N}}}\) with entries \(a_{m,i,j}\in \{0,1\}\) and consider the problem function
$$\begin{aligned} \begin{aligned} {\tilde{\Xi }}_4(\{a_{m,i,j}\}):\text { For every { m}, does }\{a_{m,i,j}\}_{i,j}&\text { have (only) finitely many columns}\\&\quad \quad \quad \quad \quad \quad \quad \text {with (only) finitely many 1's?} \end{aligned} \end{aligned}$$
Recall that it is shown in Sect. 5 that \(\textrm{SCI}({\tilde{\Xi }}_4,{\tilde{\Omega }})_{G} = 4\). We will gain a contradiction by using the supposed height three tower to solve \(\{{\tilde{\Xi }}_4,{\tilde{\Omega }}\}\).
The construction follows step 3 of the proof of Theorem 3.7 closely. For fixed m, recall the construction of the operator \(A_m:=A(\{a_{m,i,j}\}_{i,j})\) from that proof, the key property being that if \(\{a_{m,i,j}\}_{i,j}\) has (only) finitely many columns with (only) finitely many 1’s then \(\textrm{Sp}(A_m)\) is a finite subset of \([-1,1]\), otherwise it is the whole interval \([-1,1]\). Now consider the intervals \(I_m=[1-2^{m-1},1-2^{m}]\) and affine maps, \(\alpha _m\), that act as a bijection from \([-1,1]\) to \(I_m\). Without loss of generality, identify \(\Omega _\textrm{SA}\) with self-adjoint operators in \({\mathcal {B}}(X)\) where \(X=\bigoplus _{i=1}^{\infty }\bigoplus _{j=1}^{\infty }X_{i,j}\) in the \(l^2\)-sense with \(X_{i,j}=l^2({\mathbb {N}})\). We then consider the operator
defines a general tower using the relevant pointwise evaluation functions of the array \(\{a_{m,i,j}\}_{m,i,j}\). If it holds that \({\tilde{\Xi }}_4(\{a_{m,i,j}\})=1\), then \(\textrm{Sp}(T(\{a_{m,i,j}\}_{m,i,j}))\) is countable and hence \(\Xi _3^L(T(\{a_{m,i,j}\}_{m,i,j}))=1\). On the other hand, if \({\tilde{\Xi }}_4(\{a_{m,i,j}\})=0\), then there exists m with \(\textrm{Sp}(A_m)=[-1,1]\), and hence, \(I_m\subset \textrm{Sp}(T(\{a_{m,i,j}\}_{m,i,j}))\) so that \(\Xi _3^L(T(\{a_{m,i,j}\}_{m,i,j}))=0\). It follows that \(\{{{\tilde{\Gamma }}}_{n_3,n_2,n_1}\}\) provides a height three tower for \(\{{\tilde{\Xi }}_4,{\tilde{\Omega }}\}\), a contradiction.
Step 4\(\{\Xi _3^L,\Omega _{\textrm{B}},\Lambda _1\}\in \Pi _4^A\). Recall the tower of algorithms to solve \(\{\Xi _1^L,\Omega _{\textrm{B}},\Lambda _1\}\) and denote it by \({\widetilde{\Gamma }}\). Our strategy will be the same as in step 1 but with an additional successive limit. It is easy to show that
\({\widetilde{\Gamma }}_{n_3,n_2,n_1}(A)\) converges to \({\widetilde{\Gamma }}_{n_3,n_2}(A)\) from above as \(n_1\rightarrow \infty \).
\({\widetilde{\Gamma }}_{n_3,n_2}(A)\) converges to \({\widetilde{\Gamma }}_{n_3}(A)\) from below as \(n_2\rightarrow \infty \).
\({\widetilde{\Gamma }}_{n_3}(A)\) converges to \(\textrm{Leb}(\textrm{Sp}(A))\) from above as \(n_3\rightarrow \infty \).
Again, by taking successive maxima or minima where appropriate, we can assume that all of these are monotonic. Now let
Note that \(\chi _{[0,1/n_4]}\) is left continuous on \([0,\infty )\) with right limits. Hence by the assumed monotonicity and arguments as in step 1, it is easy to see that
It is also clear that the answer to the question is “No” if \(\Gamma _{n_4}(A)=0\), which yields the \(\Pi _4^A\) classification. \(\square \)
9 Proofs Concerning Fractal Dimensions
We begin with the box-counting dimension. For the construction of towers of algorithms, it is useful to use a slightly different but equivalent [71] definition of the upper and lower box-counting dimensions. Let \(F\subset {\mathbb {R}}\) be bounded and \(N'_\delta (F)\) denote the number of \(\delta \)-mesh intervals that intersect F. A \(\delta \)-mesh interval is an interval of the form \([m\delta ,(m+1)\delta ]\) for \(m\in {\mathbb {Z}}\). Then
Since \(\Omega _{BD}^\textrm{D}\subset \Omega ^{BD}_f\subset \Omega ^{BD}_{\textrm{SA}}\), it is enough to prove that \(\{\Xi _B,\Omega ^{BD}_f,\Lambda _1\}\in \Pi _2^A\), \(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _2\}\in \Pi _2^A\), \(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _1\}\in \Pi _3^A\), \(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _1\}\not \in \Delta _3^A\) and \(\{\Xi _B,\Omega ^{BD}_\textrm{D},\Lambda _2\}\not \in \Delta _2^A\).
Step 1\(\{\Xi _B,\Omega ^{BD}_f,\Lambda _1\}\in \Pi _2^A\). Recall the existence of a height one tower, \(\{{{\tilde{\Gamma }}}_n\}\), using \(\Lambda _1\) for \(\textrm{Sp}(A)\), \(A\in \Omega ^{BD}_f\) from “Appendix A”. Furthermore, \({{\tilde{\Gamma }}}_n(A)\) outputs a finite collection \(\{z_{1,n},\ldots ,z_{k_n,n}\}\subset {\mathbb {Q}}\) such that \(\textrm{dist}(z_{j,n},\textrm{Sp}(A))\le 2^{-n}\). Define the intervals
and let \({\mathcal {I}}_{m}\) denote the collection of all \(2^{-m}\)-mesh intervals. Let \(\Upsilon _{m,n}(A)\) be any union of finitely many such mesh intervals with minimal length \(\left| \Upsilon _{m,n}(A)\right| \) (“length” being the number of intervals \(\in {\mathcal {I}}_{m}\) that make up \(\Upsilon _{m,n}(A)\)) such that
There may be more than one such collection, so we can gain a deterministic algorithm by enumerating each \({\mathcal {I}}_{m}\) and choosing the first such collection in this enumeration. It is then clear that \(\left| \Upsilon _{m,n}(A)\right| \) is increasing in n. Furthermore, to determine \(\Upsilon _{m,n}(A)\), there are only finitely many intervals in \({\mathcal {I}}_{m}\) to consider, namely those that have non-empty intersection with at least one \(I_{j,l}\) with \(1\le l\le n,1\le j\le k_l\). It follows that \(\Upsilon _{m,n}(A)\) and hence \(\left| \Upsilon _{m,n}(A)\right| \) can be computed in finitely may arithmetic operations and comparisons using \(\Lambda _1\).
Suppose that \(I=[a,b]\in {\mathcal {I}}_{m}\) has \((a,b)\cap \textrm{Sp}(A)\ne \emptyset \). Then for large n there exists \(z_{j,n}\in I\) such that \(I_{j,n}\subset I\) and hence \(I\subset \Upsilon _{m,n}(A)\) for large n. If \(z\in \textrm{Sp}(A)\cap 2^{-m}{\mathbb {Z}}\), then a similar argument shows that \(z\subset \Upsilon _{m,n}(A)\) for large n. Since \(\textrm{Sp}(A)\) is bounded and \(\textrm{Sp}(A)\cap 2^{-m}{\mathbb {Z}}\) finite, it follows that \(\textrm{Sp}(A)\subset \Upsilon _{m,n}(A)\) for large n and hence
Let \(W_m(A)\) be the union of all intervals in \({\mathcal {I}}_m\) that intersect \(\textrm{Sp}(A)\). It is clear that \(W_m(A)\cap I_{j,l}\ne \emptyset \) for \(1\le l\le n,1\le j\le k_l\), and hence, \(\left| \Upsilon _{m,n}(A)\right| \le N'_{2^{-m}}(\textrm{Sp}(A))\). It follows that \(\lim _{n\rightarrow \infty }\left| \Upsilon _{m,n}(A)\right| =\delta _{m}(A)\) exists with
Hence, by the assumption that the box-counting dimension exists, we have constructed a \(\Pi _2^A\) tower.
Step 2\(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _2\}\in \Pi _2^A\) and \(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _1\}\in \Pi _3^A\). The first of these is exactly as in step 1, using \(\Lambda _2\) to construct the relevant \(\Sigma _1^A\) tower for the spectrum. The proof that \(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _1\}\in \Pi _3^A\) uses a height two tower, \(\{{{\tilde{\Gamma }}}_{n_2,n_1}\}\), using \(\Lambda _1\) for \(\textrm{Sp}(A)\), \(A\in \Omega _{\textrm{SA}}^{BD}\) (or any self-adjoint A) constructed in [18]. This tower has the property that each \({{\tilde{\Gamma }}}_{n_2,n_1}(A)\) is a finite subset of \({\mathbb {Q}}\) and, for fixed \(n_2\), is constant for large \(n_1\). Moreover, if \(z\in \lim _{n_1\rightarrow \infty }{{\tilde{\Gamma }}}_{n_2,n_1}(A)\), then \(\textrm{dist}(z,\textrm{Sp}(A))\le 2^{-n_2}\). It follows that we can use the same construction as step 1 with an additional limit at the start to reach the finite set \(\lim _{n_1\rightarrow \infty }{{\tilde{\Gamma }}}_{n_2,n_1}(A)\).
Step 3\(\{\Xi _B,\Omega ^{BD}_\textrm{D},\Lambda _2\}\not \in \Delta _2^A\). This is exactly the same argument as step 2 of the proof of Theorem 3.13 with Lebesgue measure replaced by box-counting dimension.
Step 4\(\{\Xi _B,\Omega _{\textrm{SA}}^{BD},\Lambda _1\}\not \in \Delta _3^A\). This is exactly the same argument as step 4 of the proof of Theorem 3.13 with Lebesgue measure replaced by box-counting dimension. \(\square \)
We now turn to the Hausdorff dimension. Recall Lemma 3.21 on the problem of determining whether \(\textrm{Sp}(A)\cap (a,b)\ne \emptyset \).
Proof of Lemma 3.21
We start with the class \(\Omega _f\cap \Omega _\textrm{SA}\). We can interpret this problem as a decision problem and the following algorithm as one that halts on output “Yes”. Let \(c=(a+b)/2\) and \(\delta =(b-a)/2\), then the idea is to simply test whether \(\texttt {DistSpec}(A,n,c,f(n))+c_n<\delta \). If the answer is yes, then we output “Yes”, otherwise we output “No” and increase n by one. Note that \(\textrm{Sp}(A)\cap (a,b)\ne \emptyset \) if and only if \(\left\| R(c,A)\right\| ^{-1}<\delta \) and hence as \(\texttt {DistSpec}(A,n,c,f(n))+c_n\) converges down to \(\left\| R(c,A)\right\| ^{-1}\) we see that this provides a convergent algorithm. For \(\Omega _\textrm{SA}\), we require an additional successive limit by replacing \(\texttt {DistSpec}(A,n,c,f(n))+c_n\) with the function \(\gamma _{n_2,n_1}(z;A)\). If we have access to \(\Lambda _2\), then this can be avoided in the usual way. \(\square \)
To build our algorithm for the Hausdorff dimension, we use an alternative, equivalent definition for compact sets. We consider the case of subsets of \({\mathbb {R}}\). Let \(\rho _k\) denote the set of all closed binary intervals of the form \( [2^{-k}m,2^{-k}(m+1)], m\in {\mathbb {Z}}. \) Set
The following can be found in [81] (Theorem 3.13):
Theorem 9.1
Let F be a bounded subset of \({\mathbb {R}}\). Then, there exists a unique \(d'=\textrm{dim}_{H'}(F)\) such that \(\tilde{{\mathcal {H}}}^{d}(F)=0\) for \(d>d'\) and \(\tilde{{\mathcal {H}}}^{d}(F)=\infty \) for \(d<d'\). Furthermore, \(d'=\textrm{dim}_H({\overline{F}})\).
Denoting the dyadic rationals by \({\mathbb {D}}\), we shall compute \(\textrm{dim}_H(\textrm{Sp}(A))\) via approximating the above applied to \(F=\textrm{Sp}(A)\cap {\mathbb {D}}^c\) and using Lemma 3.21.
Proof of Theorem 3.18 for Hausdorff dimension
It is enough to prove the lower bounds \(\{\Xi _H,\Omega _\textrm{D},\Lambda _2\}\notin \Delta ^G_3\), \(\{\Xi _H,\Omega _\textrm{SA},\Lambda _1\}\notin \Delta ^G_4\) and construct the towers of algorithms for the inclusions \(\{\Xi _H,\Omega _f\cap \Omega _\textrm{SA},\Lambda _1\}\in \Sigma ^A_3\), \(\{\Xi _H,\Omega _\textrm{SA},\Lambda _1\}\in \Sigma _4^A\) and \(\{\Xi _H,\Omega _\textrm{SA},\Lambda _2\}\in \Sigma _3^A\).
Step 1\(\{\Xi _H,\Omega _\textrm{D},\Lambda _2\}\notin \Delta ^G_3\). Suppose for a contradiction that a height two tower, \(\{\Gamma _{n_2,n_1}\}\), exists for \(\{\Xi _H,\Omega _\textrm{D}\}\) (taking values in [0, 1] without loss of generality). We repeat the argument in the proof of Theorem 3.16. Consider the same problem
$$\begin{aligned} {{\tilde{\Xi }}}_1(\{a_{i,j}\}):\text { Does }\{a_{i,j}\}\text { have a column containing infinitely many nonzero entries?} \end{aligned}$$
However, now we consider the above mapping to [0, 1] with the usual metric. We consider the same operator \( A=\textrm{diag}(c_{\phi (1)},c_{\phi (2)},c_{\phi (3)},\ldots ) \) with
$$\begin{aligned} \textrm{Sp}(A)=\left( \bigcup _{j:\sum _{i}a_{i,j}=\infty }I_j\right) \cup Q, \end{aligned}$$
where Q is at most countable. We use the fact that the Hausdorff dimension satisfies
and that \(\textrm{dim}_H(Q)=0\) for any countable Q to note that \(\Xi _H(A)={{\tilde{\Xi }}}_1(\{a_{i,j}\})\). We set \({\tilde{\Gamma }}_{n_2,n_1}(\{a_{i,j}\}_{i,j})=\Gamma _{n_2,n_1}(A)\) to provide a height two tower for \({{\tilde{\Xi }}}_1\). But this contradicts Theorem 5.19.
Step 2\(\{\Xi _H,\Omega _\textrm{SA},\Lambda _1\}\notin \Delta ^G_4\). Suppose for a contradiction that \(\{\Gamma _{n_3,n_2,n_1}\}\) is a height three tower of general algorithms for the problem \(\{\Xi _H,\Omega _\textrm{SA},\Lambda _1\}\) (taking values in [0, 1] without loss of generality). Let \(({\mathcal {M}},d)\) be the space [0, 1] with the usual metric, let \({\tilde{\Omega }}\) denote the collection of all infinite arrays \(\{a_{m,i,j}\}_{m,i,j\in {\mathbb {N}}}\) with entries \(a_{m,i,j}\in \{0,1\}\) and consider the problem function
$$\begin{aligned} \begin{aligned}&{\tilde{\Xi }}_4(\{a_{m,i,j}\}):\text { For every { m}, does }\{a_{m,i,j}\}_{i,j}\text { have (only) finitely many columns}\\&\quad \text {with (only) finitely many 1's?} \end{aligned} \end{aligned}$$
Recall that it is shown in Sect. 5 that \(\textrm{SCI}({\tilde{\Xi }}_4,{\tilde{\Omega }})_{G} = 4\). We will gain a contradiction by using the supposed height three tower to solve \(\{{\tilde{\Xi }}_4,{\tilde{\Omega }}\}\). We use the same construction as in step 3 of the proof of Theorem 3.16. If \({\tilde{\Xi }}_4(\{a_{m,i,j}\})=1\), then \(\textrm{Sp}(T(\{a_{m,i,j}\}_{m,i,j}))\) is countable, and hence, \(\Xi _H(T(\{a_{m,i,j}\}_{m,i,j}))=0\). On the other hand, if \({\tilde{\Xi }}_4(\{a_{m,i,j}\})=0\), then there exists m with \(\textrm{Sp}(A_m)=[-1,1]\) and hence \(I_m\subset \textrm{Sp}(T(\{a_{m,i,j}\}_{m,i,j}))\) so that \(\Xi _H(T(\{a_{m,i,j}\}_{m,i,j}))=1\). It follows that \({{\tilde{\Gamma }}}_{n_3,n_2,n_1}(\{a_{m,i,j}\}_{m,i,j})=1-\Gamma _{n_3,n_2,n_1}(T(\{a_{m,i,j}\}_{m,i,j}))\) provides a height three tower for \(\{{\tilde{\Xi }}_4,{\tilde{\Omega }}\}\), a contradiction.
Step 3\(\{\Xi _H,\Omega _f\cap \Omega _\textrm{SA},\Lambda _1\}\in \Sigma _3^A\). To construct a height three tower for \(A\in \Omega _f\cap \Omega _\textrm{SA}\), if \(n_2<n_3\) set \(\Gamma _{n_3,n_2,n_1}(A)=0\). Otherwise, consider the set
where \(S_{n_1,n_2}(A)\) is the union of all \(S\in \rho _{n_2}\) with \(S\subset [-n_1,n_1]\) and such that the algorithm discussed in Lemma 3.21 outputs “Yes” for the interior of S and input parameter \(n_1\). We then define
If \(S_{n_1,n_2}(A)\) is empty, then we interpret the infinum as 0. There are only finitely many sets to check and hence the infinum is a minimisation problem over finitely many coverings (see § B.4 for a discussion of efficient implementation). It follows that \(h_{n_3,n_2,n_1}(A,d)\) defines a general algorithm computable in finitely many arithmetic operations and comparisons. Furthermore, it is easy to see that
and \({\mathbb {D}}_k:=1/{2^k}\cdot {\mathbb {Z}}\) denotes the dyadic rationals of resolution k. We now use the property that \({\mathcal {A}}_k(F)\) consists of collections of finite coverings. As \(n_2\rightarrow \infty \), \(h_{n_3,n_2}(A,d)\) is non-increasing (since we take infinum over a larger class of coverings and the sets \(\textrm{Sp}(A)\cap {\mathbb {D}}_{n_2}^c\) decrease) and hence converges to some number. Clearly
for all l. For a fixed A and d, \(h_{n_3}(A,d)\) is non-decreasing in \(n_3\) and hence converges to a function of d, h(A, d) (possibly taking infinite values). Furthermore,
Since the set \(\textrm{Sp}(A)\cap {\mathbb {D}}\) is countable, its Hausdorff dimension is zero. Using sub-additivity of Hausdorff dimension and Theorem 9.1,
The fact that \(h_{n_3}\) is non-decreasing in \(n_3\), the set \(\{1/2^{n_3},2/2^{n_3},\ldots ,1\}\) refines itself, and the stated monotonicity collectively shows that convergence is monotonic from below, and hence, we get the \(\Sigma _3^A\) classification.
Step 4\(\{\Xi _H,\Omega _\textrm{SA},\Lambda _1\}\in \Sigma _4^A\) and \(\{\Xi _H,\Omega _\textrm{SA},\Lambda _2\}\in \Sigma _3^A\). The first of these can be proven as in step 3 by replacing \((n_1,n_2,n_3)\) by \((n_2,n_3,n_4)\) and the set \(S_{n_2,n_1}(A)\) by the set \(S_{n_3,n_2,n_1}(A)\) given by the union of all \(S\in \rho _{n_3}\) with \(S\subset [-n_2,n_2]\) and such that the \(\Sigma _2^A\) tower of algorithms discussed in Lemma 3.21 outputs “Yes” for the interior of S and input parameters \((n_2,n_1)\). To prove \(\{\Xi _H,\Omega _\textrm{SA},\Lambda _2\}\in \Sigma _3^A\), we use exactly the same construction as in step 3 now using the \(\Sigma _1^A\) algorithm (which uses \(\Lambda _2\)) given by Lemma 3.21. \(\square \)
Acknowledgements
This work was supported by EPSRC Grant EP/L016516/1. I am grateful to Arno Pauly for discussions regarding Definition 5.15 and its use in Proposition 5.16. Finally, I would like to thank Mohamed Nasser for generously sharing the code from [109] for the computation of the capacity of finite unions of intervals.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
We describe the SCI-sharp \(\Sigma _1^A\) algorithms in [64] and [60], that are used in some of our proofs. In this section, we consider the problem functions \(\Xi _1(A)=\textrm{Sp}(A)\) and \(\Xi _2(A)=\textrm{Sp}_{\epsilon }(A)\), taking values in the space of non-empty compact subsets of \({\mathbb {C}}\) equipped with Hausdorff metric. The definitions of the classes \(\Omega _g\) and \(\Omega _f\) can be found in Sect. 2. As written, the outputs of the algorithms below may be empty for small n (and hence not lie in the correct metric space). This does not affect the classifications and can be avoided by computing successive \(\Gamma _n(A)\) and outputting \(\Gamma _{m(n)}(A)\) where \(m(n)\ge n\) is minimal with \(\Gamma _{m(n)}(A)\ne \emptyset \).
The methods in [64] and [60] use the function f to approximate the function
where \(P_m\) denotes the orthogonal projection onto the linear span of the first m basis vectors and \(\sigma _{\textrm{inf}}\) denotes the injection modulus. As \(n\rightarrow \infty \), the functions \(\gamma _n\) converge uniformly on compact subsets down to the continuous function \(\gamma (z;A)=\left\| R(z,A)\right\| ^{-1}\), which we interpret as zero if the resolvent \(R(z,A)=(A-zI)^{-1}\) does not exist as a bounded operator. The function f and sequence \(\{c_n\}\) allow us to approximate \(\gamma _n\) to any given precision. To use this to compute the spectrum, we need some control on how the resolvent norm diverges near the spectrum and this is provided by the function g satisfying (2.2). At various points in this paper, we have also made use of the related functions
These can be computed from the rectangular matrices \(P_m(A-zI)P_n,P_m(A-zI)^*P_n\) and converge uniformly on compact subsets of \({\mathbb {C}}\) to \(\gamma _n\) as \(m\rightarrow \infty \).
×
Throughout, we use that DistSpec requires only finitely many arithmetic operations and comparisons, as proven in [60] (one can perform the IsPosDef routine using incomplete Cholesky decompositions). Furthermore, as outlined in Remark 5.12, we can make all of the algorithms in this paper and those in this appendix work using \(\Delta _1\)-information and restricting to arithmetical operations over the rationals.
×
×
Appendix B. Examples of Computational Routines
We provide short and simplified routines for some of the algorithms in this paper. For example, we have ignored issues like the rigorous approximation of the function \(\gamma _{n,m}\) in (A.2) using arithmetical operations. For brevity, we stick to one domain \(\Omega \) and the evaluation set \(\Lambda _1\) (matrix values) for each problem function \(\Xi \). In each case, we have chosen the non-trivial \(\Omega \) with the simplest algorithm. For the different algorithms for different classes of operators, see the proofs. In general, different classes of operators and evaluation sets have different SCI classifications and different algorithms for the same problem function.
B.1. Spectral Radii, Capacity and Operator Norms
For the problem functions in Sects. 3.1–3.3, we consider \(\Omega _f\) (see (2.1)) and \(\Omega _f\cap \Omega _{\textrm{SA}}\) for computing the capacity of the spectrum.
×
×
×
×
B.2. Essential Numerical Range, Gaps in Essential Spectra and Detecting Algorithm Failure for Finite Section
For the problems in Sect. 3.4, we consider \(\Omega _\textrm{B}\).
×
×
B.3. Lebesgue Measure
For the problems in Sect. 3.5, we consider \(\Omega _f\).
×
×
×
B.4. Fractal Dimensions
For the problems in Sect. 3.6, we consider \(\Omega _f^{BD}\) for the box-counting dimension and \(\Omega _f\cap \Omega _{\textrm{SA}}\) for the Hausdorff dimension.
For related work on practical infinite-dimensional numerical linear algebra, see [63, 85, 93, 126‐130, 166], and for rigorous data-driven algorithms for spectral properties of Koopman operators (operators on infinite-dimensional spaces that globally linearise nonlinear dynamical systems), see [56, 58, 65].
We fix the polynomial p for the strongest possible negative results. However, the existence of the towers of algorithms also holds when considering the polynomial p itself as an input.
This is an idealisation since the capacity studies operator norms while true Krylov processes look at p(A)x with one or several vectors x. However, from local spectral theory (e.g. [118]) it follows that, generically, the asymptotic speeds are the same.
Arveson [3‐7] and Brown [42‐44] pioneered spectral computations from the point of view of \(C^*\)-algebras, both for the general spectral computation problem and for Schrödinger operators. This combination can be traced back to the work of Böttcher and Silberman [39]. Arveson also considered spectral computation in terms of densities, which is related to Szegö’s work [155] on finite section approximations.
In the non-normal case, it is possible for finite sections to not capture all of the spectrum—parts of the spectrum may be unattainable. This is distinct from spectral pollution. Theorem 3.8 says that, up to a different choice of projections, this can be avoided on \(W_e(A)\).
We consider the computation of \(\textrm{Leb}(\widehat{\textrm{Sp}}_{\epsilon }(A))\) instead of \(\textrm{Leb}({\textrm{Sp}}_{\epsilon }(A))\) since it is not clear that the level sets
always have Lebesgue measure zero (this is currently an open problem for general bounded operators). This situation is analogous to the case of approximating the pseudospectra of bounded operators, where one uses the crucial property that pseudospectra cannot jump—the resolvent norm cannot be constant on open subsets of \({\mathbb {C}}\backslash \textrm{Sp}(A)\) for a bounded operator A acting on a separable Hilbert space [143]. The question of whether the sets in (3.2) are Lebesgue null is the measure theoretic equivalent. Note, however, that it is straightforward to show that \(S_{\epsilon }(A)\) is null for \(A\in \Omega _{\textrm{N}}\) through the formula \(\Vert R(z,A)\Vert ^{-1}=\textrm{dist}(z,\textrm{Sp}(A))\).
The proofs for general self-adjoint operators can be adapted with an additional successive limit and the use of two-dimensional covering boxes to treat the class of general bounded operators. Some care is needed to deal with the boundaries of covering boxes for the Hausdorff dimension, but we omit the details.
