# Computing the spectrum and pseudospectrum of infinite-volume operators from
local patches

Paul Hege, Massimo Moscolari, Stefan Teufel

###### Abstract

We show how the spectrum of normal discrete short-range infinite-volume
operators can be approximated with two-sided error control using only data
from finite-sized local patches. As a corollary, we prove the computability of
the spectrum of such infinite-volume operators with the additional property of
finite local complexity and provide an explicit algorithm. Such operators
appear in many applications, e.g. as discretizations of differential operators
on unbounded domains or as so-called tight-binding Hamiltonians in solid state
physics. For a large class of such operators, our result allows for the first
time to establish computationally also the absence of spectrum, i.e. the
existence and the size of spectral gaps. We extend our results to the
$\varepsilon$-pseudospectrum of non-normal operators, proving that also the
pseudospectrum of such operators is computable.

###### Contents

  1. 1 Introduction
  2. 2 Definitions of computational problems
    1. 2.1 The pseudospectrum
    2. 2.2 Proof strategy
    3. 2.3 Examples
    4. 2.4 Random operators
  3. 3 Reduction to finite range operators
    1. 3.1 Normal case
    2. 3.2 Non-normal case
  4. 4 The pseudospectral inclusion bound
    1. 4.1 Formulation of the pseudospectral inclusion bound
    2. 4.2 Computability of the pseudospectral inclusion bound
  5. 5 Spectral gap bound
    1. 5.1 Construction of $n$-disjoint grids
    2. 5.2 Proof of Theorem 1
  6. 6 Computability of $\rho_{H}$
  7. 7 Computability of the spectrum for normal operators
  8. 8 Computability of the pseudospectrum
    1. 8.1 Approximating the pseudospectrum
    2. 8.2 The computational algorithm
    3. 8.3 Proof that the algorithm terminates
  9. A Elementary lemmas
  10. B Definition of BSS algorithms
  11. C Evaluation functions for flc operators

##  1 Introduction

The computation of spectra of linear operators is a fundamental problem that
has been studied at various levels of generality. For finite-dimensional
matrices, the theorem of Abel and Ruffini shows that there is no closed-form
solution [1, 86], but the eigenvalues can be approximated numerically [99, 50,
88]. The approximation error can be bounded using statements such as the
Gershgorin and Bauer-Fike theorems [49, 6, 93], and there are also algorithms
that compute validated intervals for the eigenvalues, thus providing rigorous
error control [102, 103, 104].

Operators on infinite-dimensional spaces are usually studied by restriction to
a finite-dimensional subspace. Rigorous upper bounds on the eigenvalues can be
derived from finite-dimensional approximations using the Rayleigh-Ritz method
[85, 83]. A number of methods have been proposed over the years to compute
complementary lower bounds on the eigenvalues [100, 63, 101, 7, 8, 9, 17, 18,
41]. These methods usually assume that the spectrum in a certain energy window
consists of a finite number of eigenvalues [83]. Thus, they are applicable for
example to differential operators on compact domains. For this setting, e.g.
finite element methods with error control are available [30, 29, 79, 60].

In this paper, we consider the problem of computing spectra with rigorous and
explicit error control for short-range infinite volume operators, a class of
operators for which the known methods do not apply and which are at the same
time very relevant for applications. We say that a bounded operator $H$ on a
separable Hilbert space $\mathcal{H}$ is a short-range infinite volume
operator, if there is a basis $(e_{x})_{x\in\Gamma}$ indexed by a uniformly
discrete subset $\Gamma\subset\mathbb{R}^{n}$ for some $n\in\mathbb{N}$, such
that the matrix elements $H_{xy}:=\langle e_{x},He_{y}\rangle$ of $H$ fulfill
the short-range condition

$\displaystyle|H_{xy}|\leq C\frac{1}{d(x,y)^{n+\varepsilon}}$

for some $C$, $\varepsilon>0$ and all $x,y\in\Gamma$. Here $d$ denotes the
maximum distance on $\mathbb{R}^{n}$, cf. (8). Important examples of such
short-range infinite volume operators are discretizations of differential
operators on infinite domains and so-called tight-binding models from solid
state physics. In Section 2.3 we briefly discuss examples of operators arising
from applications for which computability of the spectrum was not previously
known and to which our algorithm can be applied.

Since there is an extensive mathematical literature dealing with the spectral
problem for infinite volume operators, we will briefly comment on some recent
results. The easiest method to implement is probably the finite section
method, which is not only widely used in practice, but has also been studied
theoretically from various perspectives [4, 28, 32, 74, 75, 31]. The finite
section $H_{\Lambda}$ of $H$ on a finite subset $\Lambda\subset\Gamma$ is just
the square matrix $(H_{xy})_{x,y\in\Lambda}$. For certain classes of
operators, sequences of finite sections can be found such that their spectra
are provably convergent. However, the occurrence of spectral pollution at the
boundaries makes it difficult to achieve good error control for general
operators using finite sections [42, 73].

Another popular approach to computing the spectrum of infinite-volume
operators with strong error control is based on approximating aperiodic
operators by periodic ones, e.g. [16, 15, 33]. Bounding the approximation
error of such periodic approximations has motivated a number of results
proving the Lipschitz or Hölder continuity of the spectrum in the coefficients
for a large class of operators connected to dynamical systems [21, 14].
Because there are easily computable bounds on the Lipschitz constants, these
continuity results can be used to provide error control for the convergence of
the approximant spectra in Hausdorff distance.

To make practical use of these bounds, however, suitable periodic
approximations are required. To use the Lipschitz continuity of the spectrum,
the periodic approximant has to have the same set of local patches as the
infinite-volume operator at a certain scale. While the existence of such
periodic approximations for substitution systems is increasingly well-
understood in one dimension [12, 38, 94] the situation in higher dimensions is
more complex and under active investigation [13, 5]. In both cases, there are
important examples of operators that cannot be approximated periodically, such
as the jump potential in one dimension, or the two-dimensional Penrose tiling,
for which the local matching rules force an aperiodic pattern [82]. Therefore,
while the dynamical systems method provides strong error control, it requires
the construction of periodic approximants, which is not always possible and
for which no general algorithm is known.

A different way to compute spectra is the recently proposed method of uneven
sections [36, 33], in which the operator $H$ is approximated by a rectangular
matrix $(H_{xy})_{x\in\Lambda^{\prime},y\in\Lambda}$ for some finite
$\Lambda\subset\Lambda^{\prime}\subset\Gamma$. In addition to effectively
reducing spectral pollution compared to the finite section method, this method
also provides one-sided error control [36].

A central object in the following discussions is the so-called lower norm
function

$\displaystyle\rho_{H}(\lambda)=\begin{cases}\big{\lVert}(H-\lambda)^{-1}\big{\rVert}^{-1}&\text{for
}\lambda\notin\operatorname{Spec}(H)\\\ 0&\text{otherwise}\,.\end{cases}$ (1)

For normal operators $H$ it satisfies
$\rho_{\lambda}(H)=d(\lambda,\operatorname{Spec}(H))$ and for general
operators it can serve as a defintion of the $\varepsilon$-pseudospectrum, cf.
(11).

The method from [36] implies (cf. Theorem 22 below) that for every patch size
$L>0$ and center point $x\in\mathbb{R}^{n}$ the smallest singular value
$\varepsilon_{L,\lambda,x}\geq 0$ of the rectangular matrix $(H_{yz})_{y\in
B_{L+m}(x),z\in B_{L}(x)}$ satisfies

$\displaystyle\rho_{H}(\lambda)\leq\varepsilon_{L,\lambda,x}\,$ (2)

and thus, for normal $H$, also

$\displaystyle
d(\lambda,\operatorname{Spec}(H))\leq\varepsilon_{L,\lambda,x}\,.$ (3)

Here $B_{L}(x)\subset\mathbb{R}^{n}$ denotes the hypercube around $x$ with
side length $2L$ and $m$ is a fixed finite number.

This form of error control is only one-sided, however, as there is no lower
bound for $\rho_{H}(\lambda)$. In fact, the authors of [36] prove that no
algorithm giving a lower bound on $\rho_{H}(\lambda)$ can exist as long as the
operator is given solely by its matrix elements [52]. The impossibility of a
lower bound implies that only the existence of spectrum in a certain interval
can be shown, while the absence of spectrum (a spectral gap) can not be
rigorously established in this general setting. This also implies that it is
not possible to give a bound on the Hausdorff distance to the infinite-volume
spectrum, as for example in the periodic approximation approach of [16, 15].

However, for many applications involving infinite volume operators the
existence and size of spectral gaps is of central improtance. In a previous
paper, we have shown that the no-go theorem which rules out a lower bound on
$\rho_{H}(\lambda)$ can be circumvented in most cases of physical interest,
and have given a practical algorithm to compute validated spectral gaps of an
infinite-volume system by considering all subsystems of a given size [57]. In
the present work, we expand on this by giving a general algorithm to compute
the spectrum of operators with finite local complexity (flc) with full error
control. The primary insight making this possible is that for finite range
operators knowledge of the infimum of $\varepsilon_{L,\lambda,x}$ over _all
centers_ $x\in\mathbb{R}^{n}$ is sufficient to provide a quantitative lower
bound on $\rho_{H}(\lambda)$. More precisely, for

$\displaystyle\varepsilon_{L,\lambda}:=\inf_{x\in\mathbb{R}^{n}}\varepsilon_{L,\lambda,x}\,,$

we prove the following theorem.

######  Theorem 1.

Let $H$ be a discrete operator with finite range $m>0$. Then for every
$\lambda\in\mathbb{C}$ and $L>m$ it holds that

$\displaystyle\rho_{H}(\lambda)\;\geq\;\varepsilon_{L,\lambda}\sqrt{1-\delta_{L}}-\|H-\lambda\|\sqrt{\delta_{L}}\,,$
(4)

where
$\varepsilon_{L,\lambda}:=\inf_{x\in\mathbb{R}^{n}}\varepsilon_{L,\lambda,x}$,
with $\varepsilon_{L,\lambda,x}$ defined in (24), and

$\displaystyle\delta_{L}:=\frac{n}{\left\lfloor L/m\right\rfloor}\,.$ (5)

The practical significance of Theorem 1 lies in the observation that for flc
operators, the infimum $\varepsilon_{L,\lambda}$ can be computed by evaluating
$\varepsilon_{L,\lambda,x}$ for a finite number of suitably chosen centres
$x\in\mathbb{R}^{n}$. We show that combining (2) and (4) then leads to a
general algorithm for computing the spectrum of flc operators with error
control. That is, given any short-range, discrete, normal, flc operator $H$
and $k\in\mathbb{N}$, our algorithm computes an approximation
$\Gamma_{k}(H)\subseteq\mathbb{C}$ such that

$\displaystyle d_{\mathrm{H}}(\operatorname{Spec}(H),\Gamma_{k}(H))\leq
2^{-k}\,,$ (6)

where $d_{\mathrm{H}}$ is the Hausdorff distance on subsets of $\mathbb{C}$.
Thus the algorithm is able to compute the spectrum of flc infinite-volume
operators to any given precision in Hausdorff distance.

For non-normal operators, we can use Theorem 1 to show the computability of
the $\varepsilon$-pseudospectrum [71, 98, 58, 96]
$\operatorname{Spec}_{\varepsilon}(H)$. Again, we provide an algorithm which
computes for any $\varepsilon>0$ an approximation $\Gamma_{k}(H,\varepsilon)$
such that

$\displaystyle
d_{H}(\operatorname{Spec}_{\varepsilon}(H),\Gamma_{k}(H,\varepsilon))\leq
2^{-k}\,.$ (7)

The existence of algorithms fulfilling (6) and (7) should be viewed in the
context of previous results about the computability of the general infinite-
dimensional spectral problem [52]. In extending the theory of computability
from discrete computations to analytical and numerical problems [97, 27, 26],
the solvability complexity index (SCI) is a very useful classification of
computational problems by the number of limits required for their solution
[52]. The spectral problem for operators on infinite-dimensional spaces has
been a particular focus of investigation for determining the SCI [43, 53, 54,
35, 55, 23, 34, 87].

If a general infinite-volume operator is given by its matrix entries, it has
been shown that it is impossible to compute the spectrum with error control
[36]. But it is possible to compute the spectrum via a series of convergent
estimates (without error control), which places the general spectral problem
for self-adjoint operators in the ${\rm SCI}=1$ class, which require one limit
to solve [52]. The precise SCI has also been determined for many spectral
problems differing in the conditions placed on $H$ [22]. The possibility of
one-sided error control by an upper bound on the distance to spectrum has also
inspired an intermediate SCI class $\Sigma_{1}$ that is in between the classes
$\Delta_{1}$ and $\Delta_{2}$, the classes of SCI $=1$ with and without error
control, respectively [35, 22].

The authors of this no-go theorem have stressed, however, that the SCI of a
given computation can be lowered through additional structure and conditions
on the general problem [22]. This is precisely what we achieve here by
introducing the structure of finite local complexity. It turns out that by
adding this requirement, the spectrum becomes computable and the flc spectral
problem is therefore in class $\Delta_{1}$ (full error control), instead of
the class $\Delta_{2}$ (SCI $=1$) or $\Sigma_{1}$ (one-sided error control),
which contains the general spectral problem. This lowering of the SCI is
especially interesting in light of the fact the flc is a rather general
condition that is fulfilled by most operators that occur in practice.

##  2 Definitions of computational problems

To prove the computability of the spectrum for operators of finite local
complexity, we require a clear notion of computational problems and their
solvability. Following [22], we define a computational problem by the
following data:

######  Definition 2.

A computational problem is a tuple $(\Omega,\Lambda,(\mathcal{M},d),\Xi)$,
where

  * •

$\Omega$ is a set (the “set of problems”);

  * •

$\Lambda$ is a family of functions $\Lambda=(f_{i})_{i\in\mathcal{I}}$,
indexed by a countable set $\mathcal{I}$, where each $f_{i}$ is a function
$f_{i}:\Omega\to\mathbb{R}$ (the “evaluation functions”);

  * •

$(\mathcal{M},d)$ is a metric space (the metric space of “possible
solutions”);

  * •

$\Xi$ is a function $\Omega\to\mathcal{M}$ (the “problem function”).

In this definition, the set $\Omega$ is the set of concrete problems that an
algorithm has to be able to solve. For spectral problems, this would
correspond to a certain set of operators. The exact solution of the problem is
given by the function $\Xi$, which takes values in the metric space
$(\mathcal{M},d)$. For the spectral case, we would choose
$\Xi(A)=\operatorname{Spec}(A)$ for any $A\in\Omega$, and $\mathcal{M}$ would
be the power set of $\mathbb{C}$. Because we approximate the spectrum and
pseudospectrum in Hausdorff distance, we equip $\mathcal{M}$ with the
Hausdorff distance $d_{H}$. The functions $f_{i}\in\Lambda$, finally, define
how the algorithm can get information about the concrete problem. For the
spectral problem as defined in [36], for example, the evaluation functions
would return the matrix elements of the operator in a certain basis, for
example. We would like to stress that the choice of evaluation functions
$f_{i}\in\Lambda$ can be decisive for the solvability or unsolvability of a
computational problem.

Computational problems can be solved by algorithms. The solvability of course
depends on what kinds of computations one allows the algorithm to perform (for
example, whether only algebraic or more general computations are allowed)
[22]. Unless otherwise noted, in the following we will understand
computability to refer to algorithms that can be executed by BSS machines [27,
26], a classical framework for computations with real numbers. In Appendix B,
we describe our model of computation in more detail, including what it means
for the BSS algorithm to sequentially access information about the
computational problem via the evaluation functions $f_{i}\in\Lambda$.

In this paper, we consider the spectral and pseudospectral problem with the
additional structure of finite local complexity (flc). We can thus circumvent
the impossibility result of [36] by using a restricted set $\Omega$. But the
resulting class of flc operators is still very general, and can accomodate
many if not most physical situations, including all examples from [36]. We
show that the spectral problem becomes computable when considering operators
of finite local complexity. In addition to restricting the problem set
$\Omega$, the set of evaluation functions $\Lambda$ must be augmented in order
to allow the algorithm to make use of the flc structure.

######  Definition 3.

A subset $\Gamma\subseteq\mathbb{R}^{n}$ is called uniformly discrete if there
exists a constant $q>0$ such that $d(x,y)>q$ for all $x,y\in\Gamma$ with
$x\neq y$.

In the above definition, and for the rest of this paper, we define the
distance $d(x,y)$ on $\mathbb{R}^{n}$ as the maximum distance

$\displaystyle
d((x_{1},\dots,x_{n}),(y_{1},\dots,y_{n}))=\max_{k=1,\dots,n}|x_{k}-y_{k}|\,.$
(8)

We also define $B_{r}(x)$, for $x\in\mathbb{R}^{n}$ and $r>0$, as the open
ball using this distance; that is, the set $B_{r}(x)$ is a hypercube with side
length $2r$ centered at $x$.

######  Definition 4.

We define a discrete operator $H$ in dimension $n\in\mathbb{N}$ as a bounded
operator on a separable Hilbert space $\mathcal{H}$, together with an
orthonormal basis $(e_{i})_{i\in\Gamma}$ indexed by a uniformly discrete
subset $\Gamma\subset\mathbb{R}^{n}$. We define the matrix elements at points
$x,y\in\Gamma$ as $H_{xy}=\langle e_{x},He_{y}\rangle$.

In the following, we will always represent discrete operators $H$ with respect
to the special basis $(e_{i})_{i\in\Gamma}$ and use the basis isomorphism to
identify $\mathcal{H}$ with $\ell^{2}(\Gamma)$. Furthermore, for any
$x\in\mathbb{R}^{n}$ and $L>0$, the finite dimensional subspace
$\mathcal{H}_{B_{L}(x)}\subset\mathcal{H}$ is defined by
$\mathcal{H}_{B_{L}(x)}:=\mathrm{span}\\{e_{x}\,|\,x\in B_{L}(x)\\}$, and the
orthogonal projection onto $\mathcal{H}_{B_{L}(x)}$ is denoted by
$\mathbf{1}_{B_{L}(x)}$.

We now define our two main conditions on $H$, short-range and finite local
complexity.

######  Definition 5.

Let $H$ be a discrete operator in dimension $n$. Then $H$ is called short-
range if there exist $C$ and $\varepsilon>0$ such that

$\displaystyle|H_{xy}|\leq C\,d(x,y)^{-(n+\varepsilon)}\,.$

for all $x,y\in\Gamma$. $H$ is said to have finite range if there is a number
$m>0$ (the maximal hopping length) such that $H_{xy}=0$ whenever $d(x,y)>m$.

The condition of finite local complexity is usually defined for point sets
[68, 69, 70, 24]. Very succintly, a uniformly discrete set
$\Gamma\subset\mathbb{R}^{n}$ is defined to have flc iff $\Gamma-\Gamma$ is
discrete. This turns out to be equivalent to the set of finite patches
$\\{\Gamma\cap B_{L}(x)\,|\,x\in\Gamma\\}$, falling into finitely many
equivalence classes under translation [24] for each $L>0$. To extend this
concept to operators, we require that there are finitely many equivalence
classes on which, additionally, the operator $H$ acts in the same way, which
we define precisely as follows.

######  Definition 6.

A discrete operator $H$ is said to have equivalent action on two subsets
$A,B\subseteq\Gamma$ if there is a $t\in\mathbb{R}^{n}$ such that $B=t+A$ and
if there exist $U(z)\in S^{1}\subseteq\mathbb{C}$ for every $z\in A$ such that
for any $a_{1},a_{2}\in A$ we have

$\displaystyle H_{b_{1}b_{2}}=U(a_{1})H_{a_{1}a_{2}}U(a_{2})^{*}\,,$

where $b_{1}=a_{1}+t,b_{2}=a_{2}+t$.

######  Remark 7.

It is clear that for any operator $H$, equivalent action of $H$ defines an
equivalence relation on subsets of $\Gamma$. The complex phases $U(a_{1})$ and
$U(a_{2})$ can often be set to unity, but they are necessary as gauge
transformations for certain operators, in particular for discrete Schrödinger
operators with magnetic fields.

######  Definition 8.

A discrete operator $H$ is said to have finite local complexity if for any
$L>0$, the set $\\{\,\Gamma\cap B_{L}(x)\,|\,x\in\mathbb{R}^{n}\,\\}$ is
contained in finitely many equivalence classes with respect to equivalent
action of $H$.

######  Remark 9.

More explicitly, $H$ has finite local complexity if for any $L>0$ there are
finitely many $x_{1},\dots,x_{s}\in\mathbb{R}^{n}$ such that for any
$y\in\mathbb{R}^{n}$, there is a $k\in\\{1,\dots,s\\}$ such that $H$ has
equivalent action on $\Gamma\cap B_{L}(y)$ and $\Gamma\cap B_{L}(x_{k})$.

We now define the spectral and pseudospectral problems for operators of finite
local complexity. The main goal of this paper is to show that these problems
are solvable with error control. We will consider the spectral problem only
for normal operators. The spectral problem for non-normal operators is
intractable because the spectrum of non-normal operators is not Hausdorff-
continuous in the matrix entries, even for flc operators [96]. Instead, we
show the that the $\varepsilon$-pseudospectrum is computable for non-normal
operators, for all $\varepsilon>0$.

To define the spectral problem for operators of finite local complexity, some
work has to be done to define suitable evaluation functions which will allow
the algorithm to make use of the flc structure. There are multiple ways to do
this; for example, it would be sufficient to give the algorithm access to the
repetitivity function, which gives a radius in which all patches of size $L$
occur [24]. However, to stay closer to the way actual implementations are
likely to operate, we here define the evaluation so as to allow the algorithm
to enumerate all local patches of a given size and to access the matrix
elements and site locations for any given patch. It is expected that for
concrete applications, special-purpose algorithms for the enumeration of local
patches will be used. We have demonstrated this for the case of cut-and-
project quasicrystals in [57, 56]. Because the exact definition of the
evaluation functions is a bit tedious, it is given in Appendix C. We now
define the flc version of the spectral computational problem as follows.

######  Definition 10.

The _flc spectral problem_ is the computational problem
$(\Omega,\Lambda,(\mathcal{M},d_{H}),\Xi)$, where

  * •

$\Omega$ is the set of normal discrete operators with finite local complexity
and short-range;

  * •

$\Lambda$ is a family of functions $(f_{i})_{i\in\mathcal{I}}$ satisfying
Conditions 35 in Appendix C;

  * •

$\mathcal{M}$ comprises all compact subsets of $\mathbb{C}$, and $d_{H}$ is
the Hausdorff distance;

  * •

$\Xi$ is the function which assigns to every operator $H$ its spectrum,
$\Xi(H)=\operatorname{Spec}(H)$.

One of the main results in this paper is that the flc spectral problem is
solvable with error control in Hausdorff distance.

######  Theorem 11.

Let $(\Omega,\Lambda,(\mathcal{M},d_{H}),\Xi)$ be the _flc_ spectral problem.
Then for every $k\in\mathbb{N}$ there exists a Blum-Shub-Smale (BSS) algorithm
$\Gamma_{k}:\Omega\to\mathcal{M}$, using the family of evaluation functions
$\Lambda$, such that

$\displaystyle d_{H}(\Gamma_{k}(H),\Xi(H))\leq 2^{-k}$

for all $H\in\Omega$.

The proof of this Theorem is given in Sections 6 and 7.

###  2.1 The pseudospectrum

For non-normal operators, we cannot compute the spectrum itself, but it is
still possible to compute the $\varepsilon$-pseudospectrum for
$\varepsilon>0$. The pseudospectrum may be defined in terms of the lower norm
function $\rho_{H}:\mathbb{C}\to\mathbb{R}_{+}$ [77], which is defined as

$\displaystyle\rho_{H}(\lambda)=\begin{cases}\big{\lVert}(H-\lambda)^{-1}\big{\rVert}^{-1}&\text{for
}\lambda\notin\operatorname{Spec}(H)\\\ 0&\text{otherwise}\,.\end{cases}$ (9)

The lower norm function is not a norm, but it can be given a variational
definition that is similar to the operator norm:

$\displaystyle\rho_{H}(\lambda)=\inf_{\psi\in\mathcal{H}\setminus\\{0\\}}\frac{\lVert(H-\lambda)\psi\rVert}{\lVert\psi\rVert}\,.$
(10)

Moreover, $\rho_{H}$ is Lipschitz continuous with Lipschitz constant $1$ (see,
for example, [76], Lemma 2.1). The $\varepsilon$-pseudospectrum is defined as
the closed $\varepsilon$-sublevel set of $\rho_{H}$:

$\displaystyle\operatorname{Spec}_{\varepsilon}(H):=\\{z\in\mathbb{C}\;|\;\rho_{H}(z)\leq\varepsilon\\}\,.$
(11)

Some authors also define the pseudospectrum as the open set
$\operatorname{Spec}_{\varepsilon}^{\circ}(H)=\\{z\in\mathbb{C}\;|\;\rho_{H}(z)<\varepsilon\\}$,
using a strict inequality. This has no influence on the computability,
however, because $\operatorname{Spec}_{\varepsilon}(H)$ is the closure of
$\operatorname{Spec}_{\varepsilon}^{\circ}(H)$ [96], and thus
$\operatorname{Spec}_{\varepsilon}(H)$ and
$\operatorname{Spec}_{\varepsilon}^{\circ}(H)$ have Hausdorff distance zero.
Consequently, any algorithm computing $\operatorname{Spec}_{\varepsilon}(H)$
with error control, according to Equation (7), also computes
$\operatorname{Spec}_{\varepsilon}^{\circ}(H)$ in this sense and vice versa.

For normal operators, we have

$\displaystyle\rho_{H}(\lambda)=d(\lambda,\operatorname{Spec}(H))\,,$ (12)

thus the $\varepsilon$-pseudospectrum of a normal operator $H$ is just the
$\varepsilon$-fattenig of its spectrum. For non-normal operators, we still
have

$\displaystyle\rho_{H}(\lambda)\leq d(\lambda,\operatorname{Spec}(H))\,.$

Thus the $\varepsilon$-pseudospectrum always contains the
$\varepsilon$-fattening of $\operatorname{Spec}(H)$. A computational problem
for the $\varepsilon$-pseudospectrum can be defined similarly as for the
spectrum:

######  Definition 12.

The _flc pseudospectral problem_ is the computational problem $(\Omega_{\rm
ps},\Lambda_{\rm ps},(\mathcal{M},d_{H}),\Xi_{\rm ps})$, where

  * •

$\Omega_{\rm ps}$ is the set of all tuples $(H,\varepsilon)$, where $H$ is a
discrete operator with finite local complexity and short-range (but not
necessarily normal), and $\varepsilon>0$;

  * •

$\Lambda_{\rm ps}$ consists of the same evaulation functions of Definition 10,
applied to $H$, and one additional evaluation function which returns
$\varepsilon$;

  * •

$(\mathcal{M},d_{H})$ is as in Definition 10;

  * •

$\Xi_{\rm ps}(H,\varepsilon)=\operatorname{Spec}_{\varepsilon}(H)$.

The following theorem states that the $\varepsilon$-pseudospectrum, for
$\varepsilon>0$, is computable with error control, just like the spectrum for
normal operators.

######  Theorem 13.

Let $(\Omega_{\rm ps},\Lambda_{\rm ps},(\mathcal{M},d),\Xi_{\rm ps})$ be the
flc pseudospectral problem. Then for every $k\in\mathbb{N}$ there exists a
Blum-Shub-Smale (BSS) algorithm $\Gamma_{k}:\Omega_{\rm ps}\to\mathcal{M}$,
using the family of evaluation functions $\Lambda_{ps}$, such that

$\displaystyle d(\Gamma_{k}(H,\varepsilon),\Xi_{\rm ps}(H,\varepsilon))\leq
2^{-k}$

for all $H\in\Omega_{\rm ps}$.

The proof of Theorem 13 is given in Section 8.

Figure 1: Exact computation of the $\varepsilon$-pseudospectrum of a non-
Hermitian Hamiltonian with a cut-and-project potential for $\varepsilon=0.5$.
The Hamiltonian is defined by $H\psi(n)=-\psi(n-1)+V(n)\psi(n)-\psi(n+1)$. The
chosen potential has the form $V(n)=(1+i)\mathbf{1}(\alpha n<1/\alpha)$, where
we chose $\alpha=1.66$ (For $\alpha=(1+\sqrt{5})/2$, this construction gives
the Fibonacci quasicrystal, but we chose $\alpha=1.66$ because it creates a
less uniform potential leading to a slower convergence and thus a more
pronounced effect of increasing $L$ in the pictures.). The left and right
column show the same computation with $L=20$ and $L=300$, respectively. The
uppermost row shows the lower, spectral gap bound on $\rho_{H}$, while the row
below shows the upper bound on $\rho_{H}$ from [36]. If the lower bound is
positive, the associated point is known to be in the complement of the
pseudospectrum; if the upper bound is negative, the point is known to be
inside the pseudospectrum. This gives a decomposition of the plane into three
sets $R,U,$ and $S$ of points, where it is known that
$S\subseteq\operatorname{Spec}_{\varepsilon}(H)$, that
$R\cap\operatorname{Spec}_{\varepsilon}(H)=\varnothing$, and no statement can
be made about $U$. This is very similar to the sets $S_{\tau}$, $R_{\tau}$ and
$U_{\tau}$ in Section 8, except that here we have fixed $L$ instead of $\tau$
and we do not vary the spacing of the grid on which
$\tilde{\rho}_{H}(\lambda,\tau)$ is evaluated.

######  Remark 14.

The computation of the (pseudo-) spectrum in systems of finite local
complexity can be performed practically by our method. In [57], we have
already described an algorithm to prove spectral gaps using an edge state
criterion on finite patches. For this we used Dirichlet boundary conditions
and computed an edge state criterion to provably avoid spectral pollution.
While this method could be used to prove the computability of the spectrum
[56], here we instead use the method of uneven sections [36], which enables us
to give a unified treatment of the computation of the spectrum and
pseudospectrum. Although it is not as efficient as the Dirichlet-based method
of [57] for higher-dimensional system, we can use this approach to compute gap
bounds for the $\varepsilon$-pseudospectrum. Figure 1 shows a computation of
the spectral inclusion and spectral gap bounds for the pseudospectrum of a
non-Hermitian Hamiltonian with Fibonacci-like potential [48, 40, 61].

###  2.2 Proof strategy

Our proof of Theorems 11 and 13 is based on the spectral detectability result,
Theorem 1. We have formulated Theorem 1 for finite-range as opposed to short-
range operators because this simplifies the statement considerably. In Section
3, we show that the computational spectral and pseudospectral problems for
short-range flc operators can be reduced to that for finite range operators.

In Section 4, we recall the upper bound $\varepsilon_{L,\lambda,x}$ on
$\rho_{H}(\lambda)$ from [36], adapted to our setting and finite range
interactions. The corresponding lower bound on $\rho_{H}(\lambda)$ that as
formulated in Theorem 1 is our most important novel contribution. The proof is
given in Section 5 and combines the method of uneven sections with the new
notion of $n$-disjoint subsets. In Section 6, we apply Theorem 1 to show that
$\rho_{H}(\lambda)$ is computable at every $\lambda\in\mathbb{C}$.

In Section 7, we show how to apply the computability of $\rho_{H}(\lambda)$ at
any $\lambda\in\mathbb{C}$ to show the computability of the spectrum (Theorem
11). The computability of the $\varepsilon$-pseudospectrum (Theorem 13) is
shown in Section 8.

###  2.3 Examples

Infinite-volume operators which are discrete and of finite local complexity,
as described in Definitions 4, 5, and 8, occur frequently in physics. For
example, a so-called discrete Schrödinger operator on
$\ell^{2}(\mathbb{Z}^{n})$ [64, 95, 72] is of the form

$\displaystyle(H\psi)(x)=(2n+V(x))\psi(x)\;-\sum_{\begin{subarray}{c}y\in\mathbb{Z}^{n}\\\
d(x,y)=1\end{subarray}}\psi(y)$

and can be obtained as the discretization of a Schrödinger operator on
$\mathbb{R}^{n}$. Here the function $V:\mathbb{Z}^{n}\to\mathbb{R}$ is called
the potential. Despite its simple structure, the spectral problem for discrete
Schrödinger operators is an area of active research [44, 84, 78].

The spectrum of a discrete Schrödinger operator with periodic potential $V(x)$
can be computed using the Bloch-Floquet transform. In this case, the spectrum
consists of finitely many intervals separated by so called gaps. A more
general class of operators is obtained when $V(x)$ is defined via a
substitution rule. Such operators are of high interest in mathematical physics
due to their connection to quasicrystals. For example, $V(x)$ may be the
Fibonacci potential [66, 40, 61] or the Thue-Morse sequence [19]. Important
mathematical questions about these operators concern the nature and fractal
dimension of their spectrum [92, 37] and the gap labelling [20, 65].

Despite many results on the fractal nature of the spectrum, for numerical
investigation the spectrum is usually approximated by reverting to periodic
approximants [39]. While good error bounds on the spectrum of such
approximations exist [11, 16] and can be computed in concrete cases, their
application requires specialized analysis to find suitable periodic
approximations and compute the constants in the bound [10]. In contrast, our
method only requires the enumeration of local patches of a given size, and
therefore provides the first immediately applicable algorithm to compute the
spectrum of discrete Schrödinger operators with potentials given by
substitution rules.

The Schrödinger operator can also be discretized when a magnetic field is
present. In the case of a constant magnetic field in a two-dimensional square
lattice, this leads to the Hofstadter model [59, 89], which is famous for the
self-similar, fractal structure of its spectrum as a function of the magnetic
field (Hofstadter butterfly). The spectrum of the Hofstater model is usually
approximated using periodic approximations; however, this is only possible for
rational fluxes [59]. For general fluxes, our method is to our knowledge the
first that allows computing the spectrum with error control to arbitrary
precision in the infinite Hofstadter model.

The Hofstadter model has also been investigated on quasiperiodic lattices like
Ammann-Beenker and Rauzy tilings, which lead to a butterfly structure that
depends on the quasiperiodicity [66, 46, 62, 47, 45]. Our method is the first
to allow computing the spectrum of such systems with error control, which we
have also implemented for concrete examples in [57].

A different generalization is to consider Schrödinger operators on arbitrary
graphs [91, 67]. Because we do not presuppose that our operators are defined
on a grid, or the existence of a groupoid structure as in [16], our algorithm
can be readily applied to any Schrödinger operator on arbitrary geometrically
embedded infinite graphs as long as their local structure is known.

###  2.4 Random operators

Our method can also be applied to random operators, which play an important
role in physics as models of noise and impurities [3, 51, 2]. For example,
choosing $\Gamma=\mathbb{Z}^{n}$, a random operator may be defined as a weakly
measurable function defined on a probability space
$(\Omega,\mathcal{A},\mathbb{P})$ which assigns to every $\omega\in\Omega$ a
bounded operator $H_{\omega}$ acting on the common Hilbert space
$\mathcal{H}$. If the action $T$ of the translation group $\mathbb{Z}^{n}$ on
$\Omega$ is measure preserving and ergodic, and such that $H_{T_{x}\omega}$ is
unitarily equivalent to $H_{\omega}$ for every $x\in\mathbb{Z}^{n}$, then it
can be shown that the spectrum $\operatorname{Spec}(H_{\omega})$ is almost
surely constant [2].

For ergodic random operators, the almost sure spectrum can be computed using
our method by enumerating all local patches that occur in $H_{\omega}$ with
non-zero proabability. The ergodicity implies that all such patches occur with
probability one. We can thus compute the almost sure spectrum of random
operators in a completely deterministic manner, without sampling random
potentials, by enumerating all possible local patches. This procedure would
have to be optimized for practical use however, because the number of local
patches grows exponentially in $L$ for most random models.

##  3 Reduction to finite range operators

In the problem statements in Definitions 10 and 12, we have assumed $H$ to be
of short range, meaning that its matrix elements $H_{xy}$ decay with a
sufficient power of the distance $d(x,y)$. The statements needed for the
computation of the spectrum and pseudospectrum, however, are much easier to
prove if we assume $H$ to have finite range. In this section, we show that if
we can compute the spectrum for operators of finite range, we can extend this
to short-range operators by simply cutting of the operator $H$ at a
sufficiently large hopping length.

Let $H$ be a discrete operator on $\mathcal{H}$, and let $m>0$. Then we define
the trimmed operator $G^{m}$ by its matrix elements

$\displaystyle G_{xy}^{m}=\begin{cases}H_{xy}&\text{for }d(x,y)\leq m\,,\\\
0&\text{otherwise}\,.\end{cases}$ (13)

The trimmed operator $G^{m}$, which is also an operator on $\mathcal{H}$,
always has finite range $m$.

As a first step, we show that $G^{m}\to H$ converges in norm for short-range
operators $H$. We can prove this using the Schur test, which provides a bound
on the operator norm of a linear operator based on its matrix elements [90]. A
convenient formulation of the Schur test for discrete operators is the
following Proposition [2, Proposition 10.6]:

######  Proposition 15.

Let $B$ be a discrete operator on $\Gamma$ satisfying

$\displaystyle\lVert B\rVert_{1,1}$
$\displaystyle:=\sup_{y\in\Gamma}\,\sum_{x\in\Gamma}\,|B_{xy}|<\infty\,,$
$\displaystyle\lVert B\rVert_{\infty,\infty}$
$\displaystyle:=\sup_{x\in\Gamma}\,\sum_{y\in\Gamma}\,|B_{xy}|<\infty\,.$

Then $B$ is bounded by $\lVert B\rVert\leq\sqrt{\lVert B\rVert_{1,1}\lVert
B\rVert_{\infty,\infty}}$.

We will also need the following bound of the sum of
$d(x,y)^{-(n+\varepsilon)}$, when summing only over points with a given
minimum distance $m$ from $x$.

######  Lemma 16.

Let $\varepsilon>0$ and $\Gamma$ be a subset of $\mathbb{R}^{n}$ which is
uniformly discrete with distance $l$. Then there is a constant $C$, depending
only on $n$ and $l$, such that

$\displaystyle\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}d(x,y)^{-(n+\varepsilon)}\;\leq\;C\cdot\frac{1}{m^{\varepsilon}}\,.$
(14)

Furthermore, the constant $C$ can be computed by a BSS algorithm from
$n,\varepsilon$ and $l$.

The proof of this lemma is given in Appendix A. We can now combine Lemma 16
with Proposition 15 to prove the norm convergence $G^{m}\to H$.

######  Lemma 17.

Let $H$ be a short-range discrete operator. Then for every $\delta>0$, there
exists an $m>0$ such that

$\displaystyle\lVert H-G^{m}\rVert\leq\delta\,.$ (15)

The number $m$ is a computable function of $\delta,$ the dimension $n$, and
the decay constant $C$ of Definition 5.

###### Proof.

Let $B^{m}=H-G^{m}$. The entries of $B^{m}$ fulfill the opposite relation to
(13):

$\displaystyle B^{m}_{xy}=\begin{cases}H_{xy}&\text{for }d(x,y)>m\,,\\\
0&\text{otherwise}\,.\end{cases}$

By the short-range property of $H$, there is a constant $C>0$ such that

$\displaystyle|H_{xy}|\leq Cd(x,y)^{-(n+\varepsilon)}$

for all $x,y\in\Gamma$. For any $x\in\Gamma$, we can therefore bound

$\displaystyle\sum_{y\in\Gamma}|B_{xy}^{m}|=\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}|H_{xy}|\leq C\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}d(x,y)^{-(n+\varepsilon)}\,.$

By Lemma 16, there is a constant $C_{2}>0$, which obviously does not depend on
$H$, such that this sum is bounded by

$\displaystyle\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}|H_{xy}|\leq C\cdot
C_{2}\cdot\frac{1}{m^{\varepsilon}}\,.$

The same bound clearly applies when summing over $x$. In the language of
Proposition 15, this means that

$\displaystyle\lVert B\rVert_{1,1}\leq C\cdot
C_{2}\cdot\frac{1}{m^{2}}\quad\text{and}\quad\lVert
B\rVert_{\infty,\infty}\leq C\cdot C_{2}\cdot\frac{1}{m^{\varepsilon}}\,.$

Therefore Proposition 15 bounds the operator norm of $B^{m}$ by

$\displaystyle\lVert H-G^{m}\rVert=\lVert B^{m}\rVert\leq C\cdot
C_{2}\cdot\frac{1}{m^{\varepsilon}}\,.$

It follows that Equation (15) is fulfilled for any $m\geq\left(\frac{C\cdot
C_{2}}{\delta}\right)^{1/\varepsilon}$, proving the Lemma. It is also clear
that a suitable $m$ can be computed by a BSS algorithm, since it is given by a
simple formula in $C,C_{2}$ and $\delta$. ∎

Having shown the convergence $G^{m}\to H$ in norm, we can now proceed to show
how the spectrum of any short-range operator $H$ may be computed from that of
a suitable trimming $G^{m}$. This is quite simple in the normal case, but
somewhat more involved for non-normal operators.

###  3.1 Normal case

Lemma 17 is sufficient to reduce the computational problem for short-range
operators to that for finite range operators. Define the finite range flc
spectral problem as tuples $(\Omega\,\cap\,\Omega_{\rm
fr},\Lambda\cup\Lambda_{\rm fr},(\mathcal{M},d_{H}),\Xi)$ and the finite range
flc pseudospectral problem as $(\Omega_{\rm ps}\cap\Omega_{\rm
fr},\Lambda_{\rm ps}\cup\Lambda_{\rm fr},(\mathcal{M},d_{H}),\Xi_{\rm ps})$,
where $\Omega_{\rm fr}$ is the set of all operators with finite range and
$\Lambda_{\rm fr}$ contains just one additional evaluation function that
associates to any finite-range operator $H$ the minimal $m$ such that
$H_{xy}=0$ whenever $d(x,y)>m$. Then we have the following proposition:

######  Proposition 18.

If the finite range _flc_ spectral problem $(\Omega\,\cap\,\Omega_{\rm
fr},\Lambda\cup\Lambda_{\rm fr},(\mathcal{M},d_{H}),\Xi)$ is solvable, then so
is the short-range _flc_ spectral problem
$(\Omega,\Lambda,(\mathcal{M},d_{H}),\Xi)$.

###### Proof.

Suppose that the finite range _flc_ spectral problem is solvable. To solve the
short-range _flc_ spectral problem, let $H\in\Omega$ be given, and let
$k\in\mathbb{N}$ be arbitrary. Then by Lemma 17, we can find a cutoff distance
$m$ such that $\lVert H-G^{m}\rVert\leq 2^{-(k+1)}$. Because we have a
solution of the finite range _flc_ spectral problem, we can then apply that
solution to the finite range operator $G^{m}$ to produce an approximation $A$
to the spectrum of $G^{m}$ such that

$\displaystyle d_{H}(A,\operatorname{Spec}(H))<2^{-(k+1)}\,.$

But because $\lVert H-G^{m}\rVert\leq 2^{-(k+1)}$, we also have

$\displaystyle d_{H}(\operatorname{Spec}(H),\operatorname{Spec}(G^{m}))\leq
2^{-(k+1)}\,.$

The triangle inequality then implies that $d_{H}(A,\operatorname{Spec}(H))\leq
2^{-k}$. Thus, we can always compute a set $A$ such that
$d_{H}(A,\operatorname{Spec}(H))\leq 2^{-k}$, solving the short-range flc
spectral problem. ∎

###  3.2 Non-normal case

For normal operators, we have used that a perturbation of size $\delta$ only
changes the spectrum by at most $\delta$ in Hausdorff distance in order to
prove that the spectral problem can be reduced to the case of finite range.
For non-normal operators, however, a small perturbation can cause arbitrarily
large changes in the $\varepsilon$-pseudospectrum. However, we still have for
any perturbation $R$ of norm $\lVert R\rVert\leq\tau<\varepsilon$ the
inclusions

$\operatorname{Spec}_{\varepsilon-\tau}(H)\subseteq\operatorname{Spec}_{\varepsilon}(H+R)\subseteq\operatorname{Spec}_{\varepsilon+\tau}(H)\,.$
(16)

Equation (16) follows immediately from the following equivalent
characterization of the $\varepsilon$-pseudospectrum as union of perturbed
spectra [96, Equation 4.4]:

$\displaystyle\operatorname{Spec}_{\varepsilon}(H)=\bigcup_{\begin{subarray}{c}B\in\mathcal{L(H)}\\\
\lVert B\rVert\leq\varepsilon\end{subarray}}\operatorname{Spec}(H+B)\,.$

To show that the inclusions (16) are sufficient to bound the pseudospectrum of
$H+R$ arbitrarily well, we need the following lemma, which shows the
continuity of the $\varepsilon$-pseudospectrum in the level $\varepsilon$.

######  Lemma 19.

Let $H$ be a bounded operator and $\varepsilon>0$. Then for every $\delta>0$,
there exists a $\tau>0$ so that

$\displaystyle
d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau}(H),\operatorname{Spec}_{\varepsilon+\tau}(H))\leq\delta\,.$
(17)

In other words, the function
$\varepsilon\to\operatorname{Spec}_{\varepsilon}(H)$ is continuous in
$\varepsilon$ if the codomain is equipped with the Hausdorff distance.

###### Proof.

Because $\operatorname{Spec}_{\varepsilon-\tau}(H)$ is a subset of
$\operatorname{Spec}_{\varepsilon+\tau}(H)$, the Hausdorff distance is just

$\displaystyle
d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau}(H),\operatorname{Spec}_{\varepsilon+\tau}(H))=\sup_{x\in\operatorname{Spec}_{\varepsilon+\tau}(H)}d(x,\operatorname{Spec}_{\varepsilon-\tau}(H))\,.$

Equation (17) is therefore fulfilled if and only if for every
$x\in\operatorname{Spec}_{\varepsilon+\tau}(H)$, there is a
$y\in\operatorname{Spec}_{\varepsilon-\tau}(H)$ with $|x-y|<\delta$.

Suppose for the sake of contradition that there is no $\tau>0$ fulfilling the
conditions of the Lemma. Then for every $\tau_{j}=1/j$, $j\in
J_{\varepsilon,\delta}:=\\{n\in\mathbb{N}\,|\,n\geq\max\\{\left\lceil\frac{2}{\varepsilon}\right\rceil,\left\lceil\frac{2}{\delta}\right\rceil\\}\\}$,
we can find an $x_{j}\in\operatorname{Spec}_{\varepsilon+1/j}(H)$ such that

$\displaystyle
B_{\delta}(x_{j})\cap\operatorname{Spec}_{\varepsilon-1/j}(H)=\varnothing\,.$
(18)

Because all the $x_{j}$ are contained in
$\operatorname{Spec}_{\varepsilon+1}(H)$, which is a compact set (see [96],
Theorem 2.4), the sequence $(x_{j})_{j\in J_{\varepsilon,\delta}}$ has a
convergent subsequence. Without loss of generality, we can assume that $x_{j}$
converges, say to $x_{*}\in\mathbb{C}$, and that $|x_{j}-x_{*}|<1/j.$ The
latter then implies $|x_{j}-x_{*}|<\delta/2$ for all $j\in
J_{\varepsilon,\delta}$. Combined with (18), this implies that

$\displaystyle
B_{\delta/2}(x_{*})\cap\operatorname{Spec}_{\varepsilon-1/j}(H)=\varnothing$
(19)

for all $j\in J_{\varepsilon,\delta}$. Since all sets
$\operatorname{Spec}_{\varepsilon+1/j}(H)$ are closed sets, we also have that

$\displaystyle x_{*}\in\operatorname{Spec}_{\varepsilon+1/j}(H)$ (20)

for all $j\in J_{\varepsilon,\delta}$. In terms of the function $\rho_{H}$,
condition (20) means that

$\displaystyle\rho_{H}(x_{*})\leq\varepsilon+1/j$

for all for all $j\in J_{\varepsilon,\delta}$, while condition (19) is
equivalent to

$\displaystyle\rho_{H}(z)>\varepsilon-1/j$

for all $z\in B_{\delta/2}(x_{*})$ and all for all $j\in
J_{\varepsilon,\delta}$. Taking $j\to\infty$, we conclude that $x_{*}$ must be
a strict local minimum of $\rho_{H}$ and thus a strict local maximum of
$\rho_{H}^{-1}$. This is impossible, however, because $\rho_{H}^{-1}$ is
subharmonic and therefore fulfills a maximum principle [96, Theorem 4.2]. ∎

Lemma 19 will also be useful to prove the computability of the pseudospectrum
for finite range operators in Section 8. Here we use it to prove that the
computation of the pseudospectrum can be reduced to the case of finite range
operators instead of short-range ones using the inclusions (16).

######  Proposition 20.

If the finite range _flc_ pseudospectral problem $(\Omega_{\rm
ps}\cap\Omega_{\rm fr},\Lambda_{\rm ps}\cup\Lambda_{\rm
fr},(\mathcal{M},d),\Xi_{\rm ps})$ is solvable, then the short-range problem
$(\Omega_{\rm ps},\Lambda_{\rm ps},(\mathcal{M},d),\Xi_{\rm ps})$ is solvable.

###### Proof.

Assume that the finite range problem is solvable. Let
$(H,\varepsilon)\in\Omega_{\rm ps}\cap\Omega_{\rm fr}$ be a concrete short-
range spectral problem and fix the allowed margin of error $\delta:=2^{-k}$.
In order to approximate the $\varepsilon$-pseudospectrum of $H$, we proceed as
follows: Iterate over $\tau=1,\frac{1}{2},\frac{1}{4},\dots$. For each $\tau$,
trim $H$ to an operator $G^{m}$ such that $\lVert H-G^{m}\rVert\leq\tau$. A
cut-off length $m$ fulfilling that inequality can be found in a computable way
by Lemma 17. We have assumed that the finite range problem has a solution, so
we can now apply that solution to construct subsets $A$ and $B$ such that

$\displaystyle
d_{\mathrm{H}}(A,\operatorname{Spec}_{\varepsilon-\tau}(G^{m}))\leq\delta/6\phantom{\,.}$
(21) $\displaystyle
d_{\mathrm{H}}(B,\operatorname{Spec}_{\varepsilon+\tau}(G^{m}))\leq\delta/6\,.$
(22)

Then, if we have $d_{\mathrm{H}}(A,B)\leq\delta/2$, we terminate with $A$ as
our approximation to $\operatorname{Spec}_{\varepsilon}(H)$, otherwise we
continue with the next $\tau$ in our sequence.

Now if the algorithm terminates because the condition
$d_{\mathrm{H}}(A,B)\leq\delta/2$ is fulfilled, then the result $A$ will be an
approximation of $\operatorname{Spec}_{\varepsilon}(H)$ with Hausdorff
distance less than $\delta$. We can show this using the triangle inequality
and the inclusions (16) as follows:

$\displaystyle d_{\mathrm{H}}(A,\operatorname{Spec}_{\varepsilon}(H))$
$\displaystyle\leq
d_{\mathrm{H}}(A,\operatorname{Spec}_{\varepsilon-\tau}(G^{m}))+d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau}(G^{m}),\operatorname{Spec}_{\varepsilon}(H))$
$\displaystyle\leq
d_{\mathrm{H}}(A,\operatorname{Spec}_{\varepsilon-\tau}(G^{m}))+d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau}(G^{m}),\operatorname{Spec}_{\varepsilon+\tau}(G^{m}))$
$\displaystyle\leq
d_{\mathrm{H}}(A,\operatorname{Spec}_{\varepsilon-\tau}(G^{m}))+d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau}(G^{m}),A)$
$\displaystyle\phantom{\leq}+d_{\mathrm{H}}(A,B)+d_{\mathrm{H}}(B,\operatorname{Spec}_{\varepsilon+\tau}(G^{m}))$
$\displaystyle\leq 3\tfrac{\delta}{6}+\tfrac{\delta}{2}=\delta\,.$

In the last step, we have combined the cut-off bounds (21) and (22) with the
condition $d_{H}(A,B)$.

It remains to show that the described algorithm does always terminate. That
is, we need to show that the condition $d_{\mathrm{H}}(A,B)\leq\delta/2$ will
be fulfilled for $\tau$ small enough and $A,B$ as above. According to Lemma 19
there exists a $\tau^{\prime}>0$ such that

$\displaystyle
d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau^{\prime}}(H),\operatorname{Spec}_{\varepsilon+\tau^{\prime}}(H))\leq\delta/6\,.$

This does not imply a way of computing $\tau^{\prime}$, but because our
algorithm descends to arbitrarily small $\tau$, it will eventually come to a
$\tau$ such that $\tau<\tau^{\prime}/2$. Assuming this, the algorithm will
then choose $G^{m}$ such that $\lVert G^{m}-H\rVert<\tau$, and we can use (16)
to conclude

$\displaystyle\operatorname{Spec}_{\varepsilon-\tau^{\prime}}(H)\subseteq\operatorname{Spec}_{\varepsilon-\tau}(G^{m})\subseteq\operatorname{Spec}_{\varepsilon}(H)\subseteq\operatorname{Spec}_{\varepsilon+\tau}(G^{m})\subseteq\operatorname{Spec}_{\varepsilon+\tau^{\prime}}(H)\,,$
(23)

where we have used $2\tau<\tau^{\prime}$. We can now apply Lemma 33 twice to
the inclusions in (23) to see that

$\displaystyle
d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon+\tau}(G^{m}),\operatorname{Spec}_{\varepsilon-\tau}(G^{m}))$
$\displaystyle\leq
d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon+\tau}(G^{m}),\operatorname{Spec}_{\varepsilon-\tau^{\prime}}(H))$
$\displaystyle\leq
d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau^{\prime}}(H),\operatorname{Spec}_{\varepsilon+\tau^{\prime}}(H))$
$\displaystyle\leq\delta/6\,.$

It then follows from (21) and (22) that

$\displaystyle d_{\mathrm{H}}(A,B)$ $\displaystyle\leq
d_{\mathrm{H}}(A,\operatorname{Spec}_{\varepsilon-\tau}(G^{m}))+d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon-\tau}(G^{m}),\operatorname{Spec}_{\varepsilon+\tau}(G^{m}))+d_{\mathrm{H}}(\operatorname{Spec}_{\varepsilon+\tau}(G^{m}),B)$
$\displaystyle\leq 3\frac{\delta}{6}=\delta/2\,.$

We have thus shown that the algorithm terminates at the latest when $\tau$
becomes smaller than $\tau^{\prime}/2$. ∎

We have thus established the reduction of the spectral and pseudospectral
problems to finite range operators. In the rest of the paper, we restrict
ourselves to finite range operators when describing how to solve the _flc_
spectral and pseudospectral problems, since by Propositions 18 and 20, the
same algorithms can then also be applied to the short-range _flc_ problems by
using a suitable cut-off.

##  4 The pseudospectral inclusion bound

In this section, we formulate and prove the pseudospectral inclusion bound
from [36] for our setting. Moreover, we also show that the bound is
computable.

###  4.1 Formulation of the pseudospectral inclusion bound

A bound showing the inclusion of a complex number in the
$\varepsilon$-pseudospectrum for a certain $\varepsilon$, or in other words an
upper bound on $\rho_{H}$, has been described in [36]. In the following we
describe the bound using the singular value decomposition (SVD) of a
rectangular matrix $A$, while in [36], the eigenvalues of $A^{T}A$ are used,
which are just the squares of the singular values of $A$.

######  Definition 21.

Let $H$ be a discrete operator with finite range $m$, let $x\in\mathbb{R}^{n}$
be any point and $L>0$, $\lambda\in\mathbb{C}$. The uneven section for these
data is the linear operator

$\displaystyle
Q_{L,\lambda,x}:\mathcal{H}_{B_{L}(x)}\to\mathcal{H}_{B_{L+m}(x)}$
$\displaystyle
Q_{L,\lambda,x}(\psi)=\mathbf{1}_{B_{L+m}(x)}(H-\lambda)\mathbf{1}_{B_{L}(x)}\psi\,.$

Recall that $\mathcal{H}_{B_{L}(x)}:=\mathrm{span}\\{e_{y}\,|\,y\in
B_{L}(x)\cap\Gamma\\}$ and $\mathbf{1}_{B_{L}(x)}$ denotes the orthogonal
projection onto $\mathcal{H}_{B_{L}(x)}$. Because $\Gamma$ is uniformly
discrete, $\mathcal{H}_{B_{L}(x)}$ and $\mathcal{H}_{B_{L+m}(x)}$ are finite
dimensional, so that $Q_{L,\lambda,x}$ can be respresented as a rectangular
matrix.

######  Theorem 22.

Let $H$ be a discrete operator with finite range $m>0$, and let
$\lambda\in\mathbb{R}$, $L>0$, and $x\in\mathbb{R}^{n}$ be arbitrary. Let

$\displaystyle\varepsilon_{L,\lambda,x}=s_{1}(Q_{L,\lambda,x})$ (24)

be the smallest singular value of $Q_{L,\lambda,x}$. Then $\lambda$ is
contained in the $\varepsilon_{L,\lambda,x}$-pseudospectrum of $H$:

$\displaystyle\rho_{H}(\lambda)\leq\varepsilon_{L,\lambda,x}\,.$ (25)

###### Proof.

The singular value decomposition (SVD) of $Q_{L,\lambda,x}$ decomposes
$Q_{L,\lambda,x}$ as a product

$\displaystyle Q_{L,\lambda,x}=USV^{*}$

where $U$ and $V$ are unitary and $S$ is a rectangular diagonal matrix. We can
also write this matrix product as

$\displaystyle Q_{L,\lambda,x}=\sum_{i=1}^{n}|u_{i}\rangle s_{i}\langle
v_{i}|$

where $(u_{i})_{i=1,\dots,n}$ are the first $n$ columns of $U$,
$(v_{i})_{i=1,\dots,n}$ are the columns of $V$, and $(s_{i})_{i=1,\dots,n}$
are the diagonal elements of $S$. We assume that the $(s_{i})_{i=1,\dots,n}$
are sorted in ascending order so that $s_{1}=\varepsilon_{L,\lambda,x}$.

Then $v_{1}$, considered as a vector in $\mathcal{H}$ via the canonical
inclusion $\iota:\mathcal{H}_{B_{L}(x)}\to\mathcal{H}$, is an
$\varepsilon_{L,\lambda,x}$-quasimode for $H$. Indeed, we have

$\displaystyle(H-\lambda)v_{1}$
$\displaystyle=(H-\lambda)\mathbf{1}_{B_{L}(x)}v_{1}$ (since $v_{1}$ is
supported on $B_{L}(x)$)
$\displaystyle=\mathbf{1}_{B_{L+m}(x)}(H-\lambda)\mathbf{1}_{B_{L}(x)}v_{1}$
(by the finite range of $H$) $\displaystyle=Q_{L,\lambda,x}v_{1}$
$\displaystyle=s_{1}u_{1}$

and therefore $\lVert(H-\lambda)v_{1}\rVert=s_{1}\lVert u_{1}\rVert=s_{1}$. We
conclude that $\lVert(H-\lambda)v_{1}\rVert\leq
s_{1}=\varepsilon_{L,\lambda,x}$, and thus $v_{1}$ is an
$\varepsilon_{L,\lambda,x}$-quasimode, which implies
$\lambda\in\operatorname{Spec}_{\varepsilon_{L,\lambda,x}}(H)$ by definition
of the pseudospectrum [96]. ∎

For normal operators, Equation (25) corresponds to an upper bound on the
distance to the spectrum of $H$.

###  4.2 Computability of the pseudospectral inclusion bound

In order to derive statements about computability from the existence of the
pseudospectral inclusion bound, we need to relate it to our model of
computation and show that the bound is actually computable from our problem
definition. The following Lemma shows the computability of
$\varepsilon_{L,\lambda,x}$ for a fixed $x\in\mathbb{R}^{n}$. We recall that a
short review on BSS algorithms is given in Appendix B.

######  Lemma 23.

For every $k\in\mathbb{N}$ and $\varepsilon>0$ there exists a BSS algorithm
$\Gamma_{\varepsilon,k}$ such that
$\Gamma_{\varepsilon,k}(Q_{L,\lambda,x})\in\mathbb{R}$ and

$\displaystyle
d(\Gamma_{\varepsilon,k}(Q_{L,\lambda,x}),\varepsilon_{L,\lambda,x})\leq
2^{-k}\,.$ (26)

###### Proof.

First, let us note that in [36] the authors describe a method for
approximating $\varepsilon_{L,\lambda,x}$ using finitely many arithmetic
operations. In short, to compute a bound on the distance to the spectrum using
Proposition 22, one can use that $\varepsilon_{L,\lambda,x}$ is the square
root of the smallest eigenvalue of $Q_{L,\lambda,x}^{T}Q_{L,\lambda,x}$. This
implies that, for any $t\in\mathbb{R}$,

$\displaystyle t<\varepsilon_{L,\lambda,x}\quad\Leftrightarrow\quad
Q_{L,\lambda,x}^{T}Q_{L,\lambda,x}-t^{2}\text{ is positive definite.}$

Whether a symmetric matrix is positive definite can be decided using finitely
many rational computations using the Cholesky decomposition. Recall that the
Cholesky decomposition is a method of factorizig positive semidefinite
matrices $A$ in the form $L^{*}L$, where $L$ is a lower triangular matrix. If
the matrix is not positive semidefinite, this will lead to the square root of
a negativ number being computed in the algorithm. Thus, we can approximate
$\varepsilon_{L,\lambda,x}$ with finitely many operations.

In view of this, the formulation of the BSS method $\Gamma_{\varepsilon,k}$ is
simple because for every $t$, testing whether $t<\varepsilon_{L,\lambda,x}$ is
computable using a finite number of additions, multiplications and divisions.
To define $\Gamma_{\varepsilon,k}$, let $S=\\{2^{-j}\,|\,j\in\mathbb{N}\\}$.
The algorithm $\Gamma_{\varepsilon,k}$ can then simply check for each $t\in S$
successively whether $Q_{L,\lambda,x}^{T}Q_{L,\lambda,x}-t^{2}$ is positive
definite or not, terminating with the smallest $t\in S$ for which this is not
the case. (Since $\varepsilon_{L,\lambda,x}$ is a real number, there must
certainly be a $t\in S$ with $t\geq\varepsilon_{L,\lambda,x}$.) We take this
$t$ as the result of the BSS algorithm $\Gamma_{\varepsilon,k}$. Since
$t-1/k<\varepsilon_{L,\lambda,x}\leq t$, we know that
$|t-\varepsilon_{L,\lambda,k}|<\varepsilon$, proving that (26) is satisfied. ∎

##  5 Spectral gap bound

Figure 2: In dimension $n=2$, the sets $A_{1}$ to $A_{3}$, which are defined
as the edges of three overlapping grids, form a $2$-disjoint grid, meaning
that every intersection of three of the sets is empty. In general, we need
$(n+1)$ grids in $n$ dimensions to construct a similar set out of boxes. A
decomposition like this can be used to show the dectability of bulk
$\varepsilon$-quasimodes.

It was proven in [36] that the pseudospectral inclusion bound
$\varepsilon_{L,\lambda,x}$ always converges to $\rho_{H}(\lambda)$ as
$L\to\infty$, at least for normal, short-range operators. However, the
convergence is not uniform in the operator $H$, and thus cannot be used to
provide a lower bound on $\rho_{H}(\lambda)$. As described in the
introduction, we can work around this by instead using
$\varepsilon_{L,\lambda}$, which is defined as the infimum of
$\varepsilon_{L,\lambda,x}$ over all $x\in\mathbb{R}^{n}$. In this section, we
prove Theorem 1, which is restated below for convenience.

See 1

Theorem 1 is a general statement about the locality of the (pseudo-)spectrum.
It says that any (pseudo-)spectrum of can be detected in some local patch of a
size $L$, where $L$ can be explicitly determined from the following data: the
range $m$ of $H$, an upper bound on the norm of $\|H-\lambda\|$, and the
desired accuracy. We will show in Corollary 28 how this statement can be used
to compute $\rho_{H}(\lambda)$ to any desired accuracy for _flc_ operators.

To prove Theorem 1, we tile the space $\mathbb{R}^{n}$ with disjoint boxes
$\\{B_{L+m}(x)\,|\,x\in Z\\}$, where $Z$ is some discrete subset of
$\mathbb{R}^{n}$. For the boxes to be disjoint, $Z$ must be uniformly discrete
with length $2(L+m)$. In each of the boxes, we can then compute
$\varepsilon_{L,\lambda,x}$ to approximate $\rho_{H}(\lambda)$.

However, this simple decomposition approach might fail for quasimodes of $H$
that have a large part of their $\ell^{2}$ mass concentrated in the edges of
the boxes $B_{L+m}(x)\backslash B_{L}(x)$. Such states $\psi$ can be
quasimodes of the infinite-volume operator $H$, while none of their
restrictions $\psi_{B_{L}(x)}$ for $x\in Z$ are quasimodes.

We overcome this problem by considering several overlapping disjoint
decompositions of $\mathbb{R}^{n}$ into boxes, corresponding to different
uniformly discrete subsets $Z_{i}\subseteq\mathbb{R}^{n}$. It is possible to
choose a set of such overlapping decompositions in such a way that no
quasimode $\psi$ can have a large part of its $\ell^{2}$ mass near the edges
for every decomposition. An example with three overlapping decompositions is
shown in Figure 2. Because, in that figure, no point is in the edges of all
three decompositions simultaneously, no state $\psi$ can have more that $2/3$
of its $\ell^{2}$ mass concentrated in the colored edges for all three grids.

To implement this approach in general, we will first, in Section 5.1, give the
exact condition which the overlapping decompositions have to fulfill to
guarantee that at least one of the decompositions has low $\ell^{2}$ mass in
the edges for any $\psi\in H$. We will also show how to construct
decompositions of $\mathbb{R}^{n}$ which fulfill this condition, and detail
how the mass in the edges can be lowered arbitrarily by increasing $L$. In
Section 5.2, we then apply this result to prove Theorem 1, by showing that if
the $\ell^{2}$ mass of a quasimode $\psi$ in the edges of a decomposition is
small enough, the restriction of this bulk quasimode to one of the $B_{L}(x)$
must again be a quasimode. This then implies that the bounds
$\varepsilon_{L,\lambda,x}$ can be used to bound $\rho_{H}(\lambda)$ from
below, as in inequality (4).

###  5.1 Construction of $n$-disjoint grids

We will now construct a set of $r$ $n$-dimensional grids, similar to the one
shown in Figure 2, such that no function $\psi$ can have a large part of its
mass concentrated in all the $r$ grids simultaneously.

We start by defining the notion of $n$-disjoint sets.

######  Definition 24.

A set $(A_{i})_{i=1,\dots,r}$ of subsets $A_{i}\subseteq\mathbb{R}^{n}$ is
called $n$_-disjoint_ if every point $x\in\mathbb{R}^{n}$ is contained in at
most $n$ of the sets.

As one can see from Figure 2, the tree grids $A_{1}$, $A_{2}$ and $A_{3}$ are
$2$-disjoint: even though they have nonempty pairwise intersections, the
intersection of all three is empty. The next Lemma shows that any set of grid-
shaped sets is actually $n$-disjoint.

######  Lemma 25.

Let $n\in\mathbb{N}$ and $r\in\mathbb{N}$. Let $(J_{i})_{i=1,\dots,r}$ be a
set of mutually disjoint subsets of $\mathbb{R}$. Define

$A_{i}:=\bigcup_{j=1}^{n}\left(\mathbb{R}^{j-1}\times
J_{i}\times\mathbb{R}^{n-j}\right)\subset\mathbb{R}^{n}\,.$ (27)

Then the sets $A_{i}$, $i\in\\{1,\ldots,r\\}$ are $n$-disjoint.

###### Proof.

For any point $p\in\mathbb{R}^{n}$ to be in $A_{i}$, at least one of its $n$
coordinates must lie in $J_{i}$, but then that coordinate cannot lie in any
other $J_{j}$. Thus, $p$ can lie in at most $n$ different $A_{i}$. ∎

If $r$, the number of subsets, is large enough, $n$-disjointness is already
sufficient to bound the minimum of the $\ell^{2}$ masses in any $A_{i}$, which
is shown in the following Lemma. To simplify notation, in the following we
denote by $\lVert\psi\rVert_{X}=\lVert\psi\mathbf{1}_{X\cap\Gamma}\rVert$ the
$\ell^{2}$ mass of $\psi$ in $X$, for any subset $X\subseteq\mathbb{R}^{n}$.

######  Lemma 26.

Let $(A_{i})_{i=1,\dots,r}$ be a set of $r$ subsets of $\mathbb{R}^{n}$ which
are $n$-disjoint. Then for any $\psi\in\mathcal{H}$ there exists an
$i\in\\{1,\dots,r\\}$ such that

$\displaystyle\lVert\psi\rVert_{A_{i}}^{2}\leq\frac{n}{r}\lVert\psi\rVert^{2}\,.$

###### Proof.

Consider what happens if we take the sum over all
$\lVert\psi\rVert_{A_{i}}^{2}$, for $1\leq i\leq r$. Each squared norm can be
written as a sum over points in $\Gamma$:

$\displaystyle\sum_{i=1}^{r}\lVert\psi\rVert_{A_{i}}^{2}=\sum_{i=1}^{n}\sum_{x\in\Gamma\cap
A_{i}}|\psi(x)|^{2}\,.$

Because the $A_{i}$ are $n$-disjoint, every $x\in\Gamma$ is contained in at
most $n$ of the sets $A_{i}$. Thus, every term $|\psi(x)|^{2}$, for
$x\in\Gamma$, occurs at most $n$ times in the above double sum. Thus we have

$\displaystyle\sum_{i=1}^{r}\lVert\psi\rVert_{A_{i}}^{2}\leq\sum_{x\in\Gamma}n|\psi(x)|^{2}=n\lVert\psi\rVert^{2}\,.$

Dividing this inequality by $r$, we obtain that the average of all the
$\lVert\psi\rVert^{2}_{A_{i}}$ is at most $\frac{n}{r}\lVert\psi\rVert^{2}$.
Because at least one of the numbers must be smaller or equal to the average,
there is an $i\in\\{1,\dots,r\\}$ such that

$\displaystyle\lVert\psi\rVert_{A_{i}}^{2}\leq\frac{n}{r}\lVert\psi\rVert^{2}\,.\qed$

For our purposes we use grid-shaped sets, as the ones in (27), that form a
regular mesh in $\mathbb{R}^{n}$. Moreover, we also need to control the
”thickness” of the grid. Let us be more explicit. Consider $r\in\mathbb{N}$,
$L>0$ and $m>0$. For every $i\in\\{1,\dots,r\\}$ we define the set

$J_{i}:=[-m,m]+2(L+m)\left(\mathbb{Z}+\frac{i}{r}+\frac{1}{2}\right)\subset\mathbb{R}\,.$
(28)

If $L>(r-1)m$, the sets $J_{i}$, with $i=1,\dots,r$, are mutually disjoint,
thus, by using (27), we get a set of $n$-disjoint sets
$(A_{i})_{i=1,\dots,r}$. Furthermore, the mesh formed by each of the $A_{i}$,
namely $A_{i}^{c}$, is just the union of the boxes $B_{L}(x)$ with centers

$\displaystyle x\in
Z_{i}:=2(L+m)\left(\mathbb{Z}^{n}+\frac{i}{r}(1,1,\dots,1)\right).$ (29)

In other words, we have

$\displaystyle A_{i}^{c}=\bigcup_{x\in Z_{i}}B_{L}(x)\,.$ (30)

###  5.2 Proof of Theorem 1

Let $L$, $M$, $m$, and $n$ be given, and define

$r:=\left\lfloor\frac{L}{m}\right\rfloor.$

Consider the set of $r$ sets $(J)_{i=1,\dots,r}$ defined in (28). Since $L\geq
rm>(r-1)m$, the sets $(A_{i})_{i=1,\dots,r}$ defined in (27) are $n$-disjoint.
It then follows from Lemma 26 that for any $\psi\in\mathcal{H}$, there exists
an $i\in\\{1,\dots,r\\}$ such that

$\displaystyle\lVert\psi_{A_{i}}\rVert^{2}\leq\frac{n}{r}\lVert\psi\rVert^{2}\,.$

Hence, for the orthogonal decomposition

$\displaystyle\psi=\mathbf{1}_{A_{i}}\psi+\mathbf{1}_{A_{i}^{c}}\psi=:\psi_{A_{i}}+\psi_{A_{i}^{c}}$

and writing $\delta_{L}:=n/r$, we have

$\displaystyle\lVert\psi_{A_{i}}\rVert^{2}\leq\delta_{L}\lVert\psi\rVert^{2}\quad\mbox{and}\quad\lVert\psi_{A_{i}^{c}}\rVert^{2}{\geq(1-\delta_{L})}\lVert\psi\rVert^{2}\,.$
(31)

The inverse triangle inequality implies

$\displaystyle\lVert(H-\lambda)\psi\rVert\geq\lVert(H-\lambda)\psi_{A_{i}^{c}}\rVert-\lVert(H-\lambda)\psi_{A_{i}}\rVert\,.$
(32)

For the $A_{i}$ term, we find with (31) that

$\displaystyle\lVert(H-\lambda)\psi_{A_{i}}\rVert\leq\|H-\lambda\|\lVert\psi_{A_{i}}\rVert\leq\sqrt{\delta_{L}}\|H-\lambda\|\lVert\psi\rVert\,.$
(33)

To obtain a lower bound for the $A_{i}^{c}$ term, we note that the
decomposition

$\displaystyle A_{i}^{c}=\bigcup_{x\in Z_{i}}B_{L}(x)\,,$

described in (30) is disjoint and hence

$\displaystyle(H-\lambda)\psi_{A_{i}^{c}}=\sum_{x\in
Z_{i}}(H-\lambda)\psi_{B_{L}(x)}\,.$

For each $x\in Z_{i}$, we have by definition

$\displaystyle\lVert(H-\lambda)\psi_{B_{L}(x)}\rVert=\lVert
Q_{L,\lambda,x}\psi_{B_{L}(x)}\rVert\geq\varepsilon_{L,\lambda,x}\lVert\psi_{B_{L}(x)}\rVert\geq\varepsilon_{L,\lambda}\lVert\psi_{B_{L}(x)}\rVert\,.$
(34)

Because $H$ has finite range $m$, every vector $(H-\lambda)\psi_{B_{L}(x)}$ is
supported in $B_{L+m}(x)$. Because the sets $Z_{i}$ are uniformly discrete
with distance $2(L+m)$, the hypercubes $B_{L+m}(x)$ for $x\in Z_{i}$ are
pairwise disjoint. Hence, by summing Equation (34) over all $x\in Z_{i}$, and
combining it with (31), we obtain that

$\displaystyle\lVert(H-\lambda)\psi_{A_{i}^{c}}\rVert\geq\varepsilon_{L,\lambda}\lVert\psi_{A_{i}^{c}}\rVert\geq\varepsilon_{L,\lambda}\sqrt{1-\delta_{L}}\lVert\psi\rVert\,.$
(35)

Now, we can insert the bounds (35) and (33) into the inverse triangle
inequality (32), and obtain

$\displaystyle\lVert(H-\lambda)\psi\rVert\geq\left(\varepsilon_{L,\lambda}\sqrt{1-\delta_{L}}-\|H-\lambda\|\sqrt{\delta_{L}}\right)\lVert\psi\rVert\,.$
(36)

Recalling the definition of the lower norm function (10), this proves the
theorem.

##  6 Computability of $\rho_{H}$

In this section, we show that the lower norm function $\rho_{H}(\lambda)$ can
be computed with error control, for any _flc_ operator $H$ and
$\lambda\in\mathbb{C}$. We prove this by combining Theorem 1 and Theorem 22.
We will need the following Lemma:

######  Lemma 27.

Let $H$ be a finite range discrete operator. For any fixed
$\lambda\in\mathbb{C}$, the value of $\varepsilon_{L,\lambda}$ is
nonincreasing in $L$. Similarly, for any fixed $\lambda\in\mathbb{C}$ and
$x\in\mathbb{R}^{n}$, the value of $\varepsilon_{L,\lambda,x}$ is
nonincreasing in $L$.

The proof of Lemma 27 is given in Appendix A. The computability of
$\rho_{H}(\lambda)$ is encapsulated in the following Corollary, which shows
the existence of a computable approximation $\tilde{\rho}_{H}(\lambda,\tau)$
with guaranteed error control.

######  Corollary 28.

Let $H$ be any _flc_ discrete operator with finite range $m$. Define the
function

$\tilde{\rho}_{H}(\lambda,\tau):=\varepsilon_{L_{H}(\tau),\lambda}\,,$ (37)

using the quantities $\varepsilon_{L,\lambda}$ from Theorem 1, for any
$\lambda\in\mathbb{C}$ and $\tau>0$. Here the function $L_{H}(\tau)$
determines a patch size sufficient to approximate $\rho_{H}(\cdot)$ to
precision $\tau$. Its value at any given $\tau>0$ can be computed from $H$ via
the evaluation functions $\Lambda$ of Definition 10 by a BSS algorithm. Then
the function $\tilde{\rho}_{H}(\lambda,\tau)$ fulfills

$\displaystyle|\rho_{H}(\lambda)-\tilde{\rho}_{H}(\lambda,\tau)|\leq\tau\,.$
(38)

for any $\lambda\in\mathbb{C},\tau>0$.

######  Remark 29.

Because $\tilde{\rho}_{H}(\lambda,\tau)$ can be computed from $H$ via the
evaluation functions $\Lambda$ of Definition 10 by a BSS algorithm, the
function $\tilde{\rho}(\lambda,\tau)$ is also computable in this sense.

###### Proof of Corollarly 28.

Recall from Theorems 1 and 22 that, for any $L>m$, we have

$\displaystyle\varepsilon_{L,\lambda}\sqrt{1-\delta_{L}}-M\sqrt{\delta}_{L}\leq\rho_{H}(\lambda)\leq\varepsilon_{L,\lambda}\,,$
(39)

where $\delta_{L}$ is defined as

$\delta_{L}=\frac{n}{\left\lfloor L/m\right\rfloor}\,,$

and $M:=\lVert H-\lambda\rVert$.

We write the difference between upper and lower bounds in formula (39) using
the function

$\displaystyle
f(\varepsilon,\delta)=\varepsilon(1-\sqrt{1-\delta})+M\sqrt{\delta}\,.$ (40)

for general $\varepsilon>0$ and $\delta\in(0,1)$. Then formula (39) implies
that

$\displaystyle|\varepsilon_{L,\lambda}-\rho_{H}(\lambda)|<f(\varepsilon_{L,\lambda},\delta_{L})$
(41)

for all $L>m$.

As a first step, set $L_{0}=m+1$ and compute
$\varepsilon_{0}=\varepsilon_{L_{0},\lambda}$. Lemma 23 shows that computing
$\varepsilon_{0}$ is possible using a BSS algorithm from the evaluation
functions $\Lambda$ of Definition 10. Then by Lemma 27, we have

$\displaystyle f(\varepsilon_{L,\lambda},\delta_{L})\leq
f(\varepsilon_{0},\delta_{L})$ (42)

for all $L\geq L_{0}$, because $\varepsilon_{L,\lambda}\leq\varepsilon_{0}$,
and $f(\varepsilon,d)$ is increasing in $\varepsilon$.

Now for any $\tau>0$, because $f(\varepsilon,\delta)$ is increasing in
$\delta$ for $\delta\in(0,1)$ and $\lim_{\delta\to 0}f(\varepsilon,\delta)=0$,
a value $\delta_{\tau}^{\prime}>0$ can be computed, for example using the
bisection method, such that

$\displaystyle f(\varepsilon_{0},\delta^{\prime}_{\tau})<\tau\,.$ (43)

We now choose our value of $L_{H}(\tau)$ such that

$\displaystyle L_{H}(\tau)>\max(L_{0},m\lceil
n/\delta^{\prime}_{\tau}\rceil)\,.$ (44)

This definition of $L_{H}(\tau)$ fulfills the computability requirements
because the right hand side of the inequality is computable. Furthermore, we
have $\delta_{L_{H}(\tau)}\leq\delta^{\prime}_{\tau}$. Then, by using (41),
(42) and (43), we get

$\displaystyle\left|\varepsilon_{L_{H}(\tau),\lambda}-\rho_{H}(\lambda)\right|$
$\displaystyle<f(\varepsilon_{L_{H}(\tau),\lambda},\delta_{L_{H}(\tau)})\leq
f(\varepsilon_{L_{H}(\tau),\lambda},\delta^{\prime}_{\tau})\leq
f(\varepsilon_{0},\delta^{\prime}_{\tau})<\tau\,,$

thus (38) holds. ∎

Our algorithms for computing the spectrum and $\varepsilon$-pseudospectrum of
flc operators $H$ will be based on approximating $\rho_{H}(\lambda)$ at
different points $\lambda\in\mathbb{C}$. In fact, the computability of
approximations $\tilde{\rho}_{H}(\lambda,\tau)$ fulfilling (38) are all that
we use about the operator $H$ in showing the computability of the (pseudo-)
spectrum. The same methods could therefore also be applied to show the
computability of the (pseudo-) spectrum with Hausdorff error control for any
other class of operators where the lower norm function $\rho_{H}(\lambda)$ can
be approximated with error control.

##  7 Computability of the spectrum for normal operators

In this section, we will prove Theorem 11, the computability of the spectrum
for normal operators. Our proof will be based on Corollary 28, the
computability of $\rho_{H}(\lambda)$. Note that the normal spectral problem is
not a special case of the pseudospectral problem because we can only compute
the $\varepsilon$-pseudospectrum for $\varepsilon>0$. In addition to normal
operators, the method described below could easily be extended, as in [36], to
classes of operators fulfilling a bound of the form

$\displaystyle\rho_{H}(\lambda)\geq g(d(\lambda,\operatorname{Spec}(H)))$ (45)

for some strictly increasing continuous function $g$.

###### Proof of Theorem 11.

Let the operator $H$ and $k\in\mathbb{N}$ be given. We define the desired
accuracy as $\tau:=2^{-k}$.

We know that $H$ is bounded, and the algorithm can access a bound on the norm
of $H$ via the evaluation function $f_{5}\in\Lambda$ (see Definition 35). Let
$M:=f_{5}(H)$ be this bound and define the restricted square grid

$\displaystyle
T_{\tau}:=B_{M}(0)\cap\left(\frac{\tau}{4}\sqrt{2}\cdot\mathbb{Z}^{2}\right)\subseteq\mathbb{C}\,,$
(46)

where we use the natural identification $\mathbb{R}^{2}\simeq\mathbb{C}$. The
side length of the rectangular grid is chosen such that $T_{\tau}$ has
covering radius $\tau/4$ inside $B_{M}(0)$. We will approximate the spectrum
by a subset of $T_{\tau}$.

For every $\lambda\in T_{\tau}$, we can use the algorithm of Corollary 28 to
compute an approximation $\tilde{\rho}_{H}(z,\tau/4)$ to $\rho_{H}(z)$. We
define our approximation $\tilde{\Gamma}(H,\tau)$ of the spectrum as

$\displaystyle\tilde{\Gamma}(H,\tau):=\Big{\\{}\,\lambda\in
T_{\tau}\;\Big{|}\;\tilde{\rho}_{H}(\lambda,\tau/4)<\tau/2\;\Big{\\}}\,.$ (47)

We will now show that
$d_{H}(\tilde{\Gamma}(H,\tau),\operatorname{Spec}(H))\leq\tau$ in Hausdorff
distance.

First, let $\lambda\in\operatorname{Spec}(H)$. Then $\rho_{H}(\lambda)=0$.
Because we have chosen $T_{\tau}$ to have covering radius $\tau/4$ inside
$B_{M}(0)$, there exists a point $\lambda^{\prime}\in T_{\tau}$ with
$|\lambda-\lambda^{\prime}|<\tau/4$. Because $\rho_{H}$ is Lipschitz
continuous with Lipschitz constant $1$ (see, for example, [76], Lemma 2.1), it
follows that $|\rho_{H}(\lambda)-\rho_{H}(\lambda^{\prime})|<\tau/4$. By
Corollary 28, we have
$|\rho_{H}(\lambda^{\prime})-\tilde{\rho}_{H}(\lambda^{\prime},\tau/4)|<\tau/4$.
The triangle inequality thus implies

$\tilde{\rho}_{H}(\lambda^{\prime},\tau/4)\leq\big{|}\tilde{\rho}_{H}(\lambda^{\prime},\tau/4)-\rho_{H}(\lambda^{\prime})\big{|}+\big{|}\rho_{H}(\lambda^{\prime})-\rho_{H}(\lambda)\big{|}+\rho_{H}(\lambda)<\tau/2\,,$

where we have used $\rho_{H}(\lambda)=0$. Hence,
$\lambda^{\prime}\in\Gamma_{k}(H)$. Because $\lambda$ was arbitrary, we have
$d(\lambda,\tilde{\Gamma}(H,\tau))\leq\tau/2$ for any
$\lambda\in\operatorname{Spec}(H)$.

On the other hand, for any $\lambda\in\tilde{\Gamma}(H,\tau)$, the condition
$\tilde{\rho}_{H}(\lambda,\tau/4)<\tau/2$ in (47) implies that
$\rho_{H}(\lambda)<\tau$ by Corollary 28. But for normal operators,
$\rho_{H}(\lambda)=d(\lambda,\operatorname{Spec}(H))$, so we have
$d(\lambda,\operatorname{Spec}(H))\leq\tau$.

Summing up, for any $\lambda\in\operatorname{Spec}(H)$ we have
$d(\lambda,\tilde{\Gamma}(H,\tau))\leq\tau/4$ and for any
$\lambda^{\prime}\in\tilde{\Gamma}(H,\tau)$ we have
$d(\lambda^{\prime},\operatorname{Spec}(H))\leq\tau$. Thus, we have shown that
$d_{\mathrm{H}}(\tilde{\Gamma}(H,\tau),\operatorname{Spec}(H))\leq\tau$. The
proof of Theorem 11 then follows simply by choosing
$\Gamma_{k}(H):=\tilde{\Gamma}(H,2^{-k})$. ∎

##  8 Computability of the pseudospectrum

In this section, we will prove Theorem 13, the computability of the
$\varepsilon$-pseudospectrum for potentially non-normal operators and for
$\varepsilon>0$. A related result about pseudospectra is [76], in which it is
shown that the pointwise convergence of the lower norm and the lower norm of
the adjoint implies the convergence of the $\varepsilon$-pseudospectrum in
Hausdorff distance. In the following, we show an analogous result about
computability, namely that the $\varepsilon$-pseudospectrum can be computed in
Hausdorff distance if arbitrarily extact estimates of the lower norm are
possible. We do not require computation of the lower norm of the adjoint. In
another related result [14], the constancy of the spectrum in minimal
dynamical systems has also been extended to pseudospectra, which might provide
an alternative avenue for computing pseudospectra rigorously.

As in the proof of Theorem 11, we will choose a sufficiently fine grid
$T_{\tau}$ on which to compute the approximations
$\tilde{\rho}_{H}(\lambda,\tau)$. However, in the non-normal case, the scale
$\tau$ cannot be determined a priori. Instead, we will simultaneously decrease
the maximum error $\tau$ of the approximation $\tilde{\rho}_{H}(\lambda,\tau)$
and the spacing of the grid $T_{\tau}$ on which it is computed until a certain
condition is met.

As a first step, Proposition 30 in Subsection 8.1 will show that a certain
easily computable criterion is sufficient to guarantee that the spectrum is
approximated well enough for a given $\tau$.

###  8.1 Approximating the pseudospectrum

To compute the $\varepsilon$-pseudospectrum, we will evaluate
$\tilde{\rho}_{H}(\lambda,\tau)$ for all $\lambda\in T_{\tau}$, where
$T_{\tau}$ is the following lattice:

$\displaystyle T_{\tau}$
$\displaystyle:=\tau\sqrt{2}\mathbb{Z}^{2}\,\cap\,B_{M+\varepsilon}(0)\subseteq\mathbb{C}\,.$
(48)

This definition is very close to (46), except that the factor $\frac{1}{4}$ is
not necessary in the present case. We then decompose $T_{\tau}$ into the
following three disjoint sets:

$\displaystyle S_{\tau}$ $\displaystyle:=\\{\,\lambda\in
T_{\tau}\;|\;\tilde{\rho}_{H}(\lambda,\tau)<\varepsilon-\tau\,\\}\,,$ (49)
$\displaystyle R_{\tau}$ $\displaystyle:=\\{\,\lambda\in
T_{\tau}\;|\;\tilde{\rho}_{H}(\lambda,\tau)>\varepsilon+2\tau\,\\}\,,$ (50)
$\displaystyle U_{\tau}$ $\displaystyle:=T_{\tau}\;\backslash\;(S_{\tau}\cup
R_{\tau})\,.$ (51)

It is easy to see, using Corollary 28, that all points $S_{\tau}$ are
certainly in $\operatorname{Spec}_{\varepsilon}(H)$, while all points in
$R_{\tau}$ are certainly not in $\operatorname{Spec}_{\varepsilon}(H)$. The
following proposition shows a simple condition on $S_{\tau}$, $R_{\tau}$ and
$U_{\tau}$ that, if fulfilled, guarantees that $S_{\tau}$ will be a good
approximation of the spectrum.

######  Proposition 30.

Let $H$ be an _flc_ operator and $\delta,\tau>0$. Let $S_{\tau}$ and
$U_{\tau}$ be the sets defined in (49) and (51). Then, if

$\displaystyle d(\lambda,S_{\tau})<\delta-\tau\qquad\text{for all }\lambda\in
U_{\tau}\,,$ (52)

we have

$\displaystyle d_{H}(S_{\tau},\operatorname{Spec}_{\varepsilon}(H))<\delta\,.$

###### Proof.

By definition of $S_{\tau}$, we have
$S_{\tau}\subseteq\operatorname{Spec}_{\varepsilon}(H)$. Thus, the inequality
for the Hausdorff distance reduces to showing that
$d(\lambda,S_{\tau})\leq\delta$ for all
$\lambda\in\operatorname{Spec}_{\varepsilon}(H)$.

Let $\lambda\in\operatorname{Spec}_{\varepsilon}(H)$ be given. It is easy to
show that $\lambda\in B_{M+\varepsilon}(0)$. The lattice $T_{\tau}$ was chosen
to have covering radius $\tau$ in $B_{M+\varepsilon}(0)$, so we can find a
$\lambda^{\prime}\in T_{\tau}$ with $d(\lambda,\lambda^{\prime})\leq\tau$.
Consider now the additional set $R_{\tau}$ defined in (50). It is clear from
the definitions of $S_{\tau}$, $R_{\tau}$ and $U_{\tau}$, (49), (50) and (51)
respectively, that they are a disjoint decomposition of $T_{\tau}$. Thus,
$\lambda^{\prime}$ must be in exactly one of these sets.

Of the three options, $\lambda^{\prime}\in R_{\tau}$ is actually impossible.
That is because we have $\lambda\in\operatorname{Spec}_{\varepsilon}(H)$, so
$\rho_{H}(\lambda)\leq\varepsilon$. The Lipschitz continuity of $\rho_{H}$
implies that $\rho_{H}(\lambda^{\prime})\leq\varepsilon+\tau$. From Corollary
28, we then get
$\tilde{\rho}_{H}(\lambda^{\prime},\tau)\leq\varepsilon+2\tau$. This means
$\lambda^{\prime}\notin R_{\tau}^{\prime}$.

If we have $\lambda^{\prime}\in S_{\tau}$, then $d(\lambda,S_{\tau})\leq\tau$.
But the algorithm always chooses $\tau\leq\delta$, so we have
$d(\lambda,S_{\tau})\leq\delta$ in this case.

Finally, suppose that $\lambda^{\prime}\in U_{\tau}$. By the hypothesis (52),
we have $d(\lambda^{\prime},S_{\tau})<\delta-\tau$. Moreover
$d(\lambda,\lambda^{\prime})\leq\tau$, thus we have
$d(\lambda,S_{\tau})\leq\delta$ also in this case. Therefore
$d(\lambda,S_{\tau})\leq\delta$ is fulfilled for every
$\lambda\in\operatorname{Spec}_{\epsilon}(H)$. ∎

###  8.2 The computational algorithm

Because the sets $S_{\tau}$ and $U_{\tau}$ are always finite, condition (52)
from Proposition 30 can be checked in finite time, given the sets. Because
this condition is sufficient to show that $S_{\tau}$ is within distance
$\delta$ of $\operatorname{Spec}_{\varepsilon}(H)$, we can compute the
$\varepsilon$-pseudospectrum by simply checking smaller and smaller $\tau>0$,
as in the following algorithm.

######  Algorithm 31 (Approximate the $\varepsilon$-pseudospectrum of $H$ with
maximum error $\delta$).

Compute an upper bound $M$ on the norm of $H$

Compute the lattice
$T_{\tau}:=\tau\sqrt{2}\mathbb{Z}^{2}\,\cap\,B_{M+\varepsilon}(0)$

for $j\leftarrow 1,2,3,\dots$ do

Set $\tau=2^{-j}\cdot\delta$

compute $S_{\tau}$ and $U_{\tau}$ according to Equations (49) and (51)

if condition (52) holds then

return $S_{\tau}$

end if

end for

Proposition 30 shows that if Algorithm 31 terminates, the result fulfills
$d_{H}(S_{\tau},\operatorname{Spec}_{\varepsilon}(H))<\delta$. To complete the
proof of Theorem 13 it remains to show that Algorithm 31 always terminates. In
other words, we need to show that for any _flc_ operator $H$, as well as
$\varepsilon$ and $\delta$, condition (52) is fulfilled for $\tau$ small
enough. This will be proven in the following subsection.

###  8.3 Proof that the algorithm terminates

######  Lemma 32.

Let an _flc_ operator $H$ and $\varepsilon,$ $\delta>0$ be given. Then there
exists a $\tau^{\prime}>0$ such that for all $0<\tau<\tau^{\prime}$, the sets
$S_{\tau}$ and $U_{\tau}$ defined in equations (49) and (51) fulfill the
condition (52) in Proposition 30.

###### Proof.

By Lemma 19, there exists a $\tau^{\prime}>0$ such that for all
$0<\tau<\tau^{\prime}$,

$\displaystyle
d_{H}(\operatorname{Spec}_{\varepsilon-3\tau^{\prime}}(H),\operatorname{Spec}_{\varepsilon+3\tau^{\prime}}(H))<\delta\,.$
(53)

(We can choose a smaller $\delta$ in Lemma 19 to obtain the strict
inequality.)

Now let $\lambda\in U_{\tau}$ be arbitrary. By definition of $U_{\tau}$, we
have

$\displaystyle\tilde{\rho}_{H}(\lambda,\tau)\leq\varepsilon+2\tau\,,$ (54)

because otherwise we would have $\lambda\in R_{\tau}$. From Corollary 28, we
can deduce

$\displaystyle\rho_{H}(\lambda)<\varepsilon+3\tau\,.$ (55)

Now by (53), we know that there exists a
$\lambda^{\prime\prime}\in\operatorname{Spec}_{\varepsilon-3\tau}(H)$ with
$d(\lambda,\lambda^{\prime\prime})<\delta$. This $\lambda^{\prime\prime}$
hence fulfills

$\displaystyle\rho_{H}(\lambda^{\prime\prime})\leq\varepsilon-3\tau\,.$ (56)

Now we will set

$\displaystyle\lambda^{\prime}=\lambda^{\prime\prime}+\tau\frac{\lambda-\lambda^{\prime\prime}}{|\lambda-\lambda^{\prime\prime}|}\,.$
(57)

The point $\lambda^{\prime}$ lies on the line connecting $\lambda$ and
$\lambda^{\prime\prime}$, at a distance $\tau$ from $\lambda^{\prime\prime}$
in the direction of $\lambda$. Clearly, we have

$\displaystyle d(\lambda^{\prime},\lambda)<\delta-\tau\,,$ (58)

because $d(\lambda,\lambda^{\prime\prime})<\delta$. On the other hand, because
$\rho_{H}$ is Lipschitz continuous with constant $\leq 1$ and
$d(\lambda^{\prime},\lambda^{\prime\prime})=\tau$, we have

$\displaystyle\rho_{H}(\lambda^{\prime})\leq\rho_{H}(\lambda^{\prime\prime})+\tau\leq\varepsilon-2\tau\,.$
(59)

where we used (56) in the second inequality. Corollary 28 again gives

$\displaystyle\tilde{\rho}_{H}(\lambda^{\prime},\tau)\leq\varepsilon-\tau\,.$
(60)

It follows that $\lambda^{\prime}\in S_{\tau}$. We have shown
$d(\lambda^{\prime},\lambda)<\delta-\tau$ in (58), so
$d(\lambda,S_{\tau})<\delta-\tau$. But $\lambda\in U_{\tau}$ was arbitrary,
proving the Lemma. ∎

###### Proof of Theorem 13.

The solution to the computational problem $(\Omega_{\rm ps},$ $\Lambda_{\rm
ps},$ $(\mathcal{M},d),$ $\Xi_{\rm ps})$ is given by the BSS algorithm
$\Gamma_{k}(H,\varepsilon)$ that is just the application of Algorithm 31 to
the given $H$, $\varepsilon$ and $\delta=2^{-k}$.

By Lemma 32, there exists a $\tau^{\prime}>0$ such that condition (52) is
fulfilled for all $0<\tau<\tau^{\prime}$. Thus, Algorithm 31 will terminate
after at most $\log_{2}(\max(1,\delta/\tau^{\prime}))$ iterations. After the
algorithm has terminated, the sets $S_{\tau}$ and $U_{\tau}$ fulfill condition
(52), and therefore, by Proposition 30, we have

$\displaystyle d_{H}(\Gamma_{k}(H,\varepsilon),\Xi_{\rm
ps}(H,\varepsilon))=d_{H}(S_{\tau},\operatorname{Spec}_{\varepsilon}(H))<\delta=2^{-k}\,.$

This completes the proof of Theorem 13. ∎

## Acknowledgements

We would like to thank Siegfried Beckus, Anuradha Jagannathan, Johannes
Kellendonk, and Lior Tenenbaum for valuable comments. The work of M.M. has
been supported by a fellowship of the Alexander von Humboldt Foundation during
his stay at the University of Tübingen, where this work initiated. M.M.
gratefully acknowledges the support of PNRR Italia Domani and Next Generation
EU through the ICSC National Research Centre for High Performance Computing,
Big Data and Quantum Computing and the support of the MUR grant Dipartimento
di Eccellenza 2023–2027. S.T. acknowledges financial support by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) – TRR 352 – Project-
ID 470903074.

##  Appendix A Elementary lemmas

This Appendix collects several Lemmas with simple proofs that have been moved
here to shorten the main text.

In proving the reduction to finite range in Section 3, we used the following
lemma, which provides a bound on the sum of polynomially decaying hoppings
starting at a given distance.

See 16

###### Proof.

Without loss of generality, we can assume that $m>l$. To compute the sum in
(14), we use the Cauchy-Maclaurin criterion adapted to our setting in same
spirit as in [80]. The main idea is to estimate the sum from above by using an
integral. First, notice that $d(x,y)\leq\|x-y\|_{2}\leq d(x,y)\sqrt{n}$ where
$\|\cdot\|_{2}$ denotes the usual Euclidean norm in $\mathbb{R}^{n}$. Then,
the function $\mathbb{R}^{n}\ni y\mapsto d(x,y)^{-(n+\varepsilon)}$ is such
that $d(x,y)^{-(n+\varepsilon)}\leq
n^{(n+\varepsilon)/2}\|x-y\|_{2}^{-(n+\varepsilon)}$. For every $y\in\Gamma$
such that $d(x,y)>m$, let $\tilde{B}^{(x)}_{l/4}(y)$ be a closed (possibly
rotated) hypercube of side length $l/2$ such that $y$ sits on one of its
corner and for every $z\in\tilde{B}^{(x)}_{l/4}(y)$ it holds that
$\|x-z\|_{2}\leq\|x-y\|_{2}$. Furthermore, by hypothesis on the uniform
discreteness of $\Gamma$ we have that
$\tilde{B}^{(x)}_{l/4}(y)\cap\Gamma=\\{y\\}$ for every $y\in\Gamma$ and
$\tilde{B}^{(x)}_{l/4}(y)\cap\tilde{B}^{(x)}_{l/4}(z)=\emptyset$ if $y\neq z$.
Thus we have

$\displaystyle\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}d(x,y)^{-(n+\varepsilon)}$ $\displaystyle\leq
n^{(n+\varepsilon)/2}(l/2)^{-n}\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}(l/2)^{n}\|x-y\|_{2}^{-(n+\varepsilon)}$
$\displaystyle\leq
n^{(n+\varepsilon)/2}(l/2)^{-n}\sum_{\begin{subarray}{c}y\in\Gamma\\\
d(x,y)>m\end{subarray}}\int_{\tilde{B}^{(x)}_{l/4}(y)}\mathrm{d}^{n}z\;\;\|x-z\|_{2}^{-(n+\varepsilon)}$
$\displaystyle\leq
n^{(n+\varepsilon)/2}(l/2)^{-n}\int_{\|y-x\|_{2}>\frac{m}{4}}\mathrm{d}^{n}z\;\;\|x-z\|_{2}^{-(n+\varepsilon)}$
$\displaystyle\leq
n^{(n+\varepsilon)/2}(l/2)^{-n}(2\pi)^{n-1}\int_{\frac{m}{4}}^{+\infty}\mathrm{d}r\;\;r^{n-1}r^{-(n+\varepsilon)}\,.$

where in the last integral we used the $n$-spherical coordinates. By explicit
integration, the proofs is concluded. ∎

We also needed the following Lemma, which shows that
$\varepsilon_{L,\lambda,x}$ is nonincreasing in $L$.

See 27

###### Proof.

It is clear that the statement about $\varepsilon_{L,\lambda}$ directly
follows from the statement about $\varepsilon_{L,\lambda,x}$, because the
infimum of a set of nonincreasing functions is again nonincreasing.

Let $0<L_{1}<L_{2}$ be two values of $L$. Now the bound
$\varepsilon_{L_{1},\lambda,x}$ is defined as the lower norm of
$Q_{L_{1},\lambda,x}$, which is the rectangular section of $H$ going from
$\mathcal{H}_{B_{L_{1}}(x)}$ to $\mathcal{H}_{B_{L_{1}+m}(x)}$. It follows
that we can find a sequence $(\psi_{n})_{n\in\mathbb{N}}$ with
$\psi_{n}\in\mathcal{H}_{B_{L_{1}}(x)}$ and $\lVert\psi_{n}\rVert=1$, such
that $\lVert
Q_{L_{1},\lambda,x}\psi_{n}\rVert\to\varepsilon_{L_{1},\lambda,x}$.

Because $B_{L_{1}}(x)\subseteq B_{L_{2}}(x)$, we have canonical inclusions

$\iota:\mathcal{H}_{B_{L_{1}}(x)}\to\mathcal{H}_{B_{L_{2}}(x)}\,\qquad\text{and}\qquad\iota_{m}:\mathcal{H}_{B_{L_{1}+m}(x)}\to\mathcal{H}_{B_{L_{2}+m}(x)}\,.$

Clearly, we have the commutation relation

$\iota_{m}Q_{L_{1},\lambda,x}\psi_{n}=Q_{L_{2},\lambda,x}\iota\psi_{n}\,,$

because $H$ has finite range $m$. Furthermore,
$\lVert\iota\phi\rVert_{B_{L_{2}}(x)}=\lVert\phi\rVert_{B_{L_{1}}(x)}$ for all
$\phi\in\mathcal{H}_{B_{L_{1}}(x)}$. Thus, we obtain

$\lVert Q_{L_{1},\lambda,x}\iota\psi_{n}\rVert=\lVert
Q_{L_{2},\lambda,x}\psi_{n}\rVert\,.$

Thus $\iota\psi_{n}$ is a sequence of states in $\mathcal{H}_{B_{L_{2}}(x)}$
with $\lVert
Q_{L_{1},\lambda,x}\iota\psi_{n}\rVert\to\varepsilon_{L_{1},\lambda,x}$.
Because $\varepsilon_{L_{2},\lambda,x}$ is defined as the lower norm of
$Q_{L_{2},\lambda,x}$, this implies that

$\varepsilon_{L_{2},\lambda,x}\leq\varepsilon_{L_{1},\lambda,x}\,.\qed$

The following is a sort of “Sandwich Lemma” for the Hausdorff distance. It
proves that if a set $B$ is sandwiched between two sets $A$ and $C$, then from
the perspective of any reference set $X$, the intermediate set $B$ cannot be
farther away than both of the extremal sets $A$ and $C$.

######  Lemma 33.

Let $A,B,C,X$ be four subsets of a metric space $(\mathcal{M},d)$ such that
$A\subseteq B\subseteq C$. Then the Hausdorff distance $d_{\mathrm{H}}$
fulfills

$\displaystyle d_{\mathrm{H}}(X,B)$
$\displaystyle\leq\max\left(d_{\mathrm{H}}(X,A),d_{\mathrm{H}}(X,C)\right)\,.$

###### Proof.

By definition, we have

$\displaystyle d_{\mathrm{H}}(X,B)=\max\left(\sup_{x\in X}d(x,B),\sup_{b\in
B}d(b,X)\right)\,.$

Now because $A\subseteq B$, we have

$\displaystyle d(x,B)\,\leq\,d(x,A)\,\leq\,d_{\mathrm{H}}(X,A),$

and from $B\subseteq C$, we get

$\displaystyle\sup_{b\in B}d(b,X)\,\leq\,\sup_{c\in
C}d(c,X)\,\leq\,d_{\mathrm{H}}(C,X).$

Thus we obtain
$d_{\mathrm{H}}(X,B)\leq\max(d_{\mathrm{H}}(X,A),d_{\mathrm{H}}(X,C))=M$. ∎

##  Appendix B Definition of BSS algorithms

Computational problems can be solved by algorithms. One can define classes of
algorithms corresponding to different models of computation [22]. In the
following, we will use Blum-Shub-Smale (BSS) machines to define the
computational steps of our algorithms [27, 26, 25, 81]. BSS machines are
similar to Turing machines [97] but can store arbitrary real numbers (or
elements of any other ring) on their tape. A BSS machine is characterized by a
certain set of states and rules. Any such machine defines a mapping

$\displaystyle f_{\text{BSS}}:\mathbb{R}^{\infty}\to\\{\framebox{\text{no-
halt}}\\}\cup\mathbb{R}^{\infty}\,,$

where
$\mathbb{R}^{\infty}=\mathbb{R}^{0}\,\dot{\cup}\,\mathbb{R}^{1}\,\dot{\cup}\,\mathbb{R}^{2}\,\dot{\cup}\,\dots$
is the set of finite real sequences and no-halt is a special symbol. To
determine the value of the function $f_{\text{BSS}}$ at a specific
$x\in\mathbb{R}^{\infty}$, the elements of $x$ are written on the tape, and
the value of the function $f_{\text{BSS}}$ will be the numbers on the tape
after the machine halts, or no-halt if the machine does not halt on the given
inputs. We say that a BSS machine always halts if $f(A)\neq\framebox{\text{no-
halt}}$ for all $A\in\mathbb{R}^{\infty}$.

######  Definition 34.

Let $(\Omega,\Lambda,(\mathcal{M},d),\Xi)$ be a computational problem and let
$F_{\text{embed}}:\mathbb{R}^{\infty}\to\mathcal{M}$ be a function with dense
image. (The function $F_{\text{embed}}$ is used to parameterize the solution
space.) Furthermore, suppose that $\Lambda$ is countable and
$(f_{i})_{i\in\mathbb{N}}$ is an enumeration of $\Lambda$.

A BSS algorithm $\Gamma$ for the problem
$(\Omega,\Lambda,(\mathcal{M},d),\Xi)$ can be described by a sequence of BSS
functions $(c_{k})_{k\in\mathbb{N}_{0}}:\mathbb{R}^{k}\to\mathbb{R}^{\infty}$,
all of which halt on any input. Furthermore, we require that for any
$x\in\mathbb{R}^{k}$, the vector $a:=c_{k}(x)$ has at least one element, and
furthermore

  * •

If $a_{0}\neq 0$, then $a\in\mathbb{R}^{2}$, and $a_{1}$ is an integer.

  * •

If $a_{0}=0$, then $a$ has an odd number of elements.

The purpose of these conditions on $a$ is that we wish to reserve the first
number of the result $a_{0}$ to indicate whether the algorithm has terminated
in step $k$ or whether a further evaluation is requested. If $a_{0}\neq 0$,
then $a_{1}\in\mathbb{Z}$ shall determine the evaluation function that is
requested. If $a_{0}=0$, then the execution terminates, and the following
pairs of numbers shall determine the endpoints of the intervals whose union is
the result of the computation, parameterized via $F_{\text{embed}}$.

To evaluate a BSS algorithm on a value $x\in\Omega$, we define a series of
functions

$\displaystyle d_{k}:\Omega\to\mathcal{M}\,\dot{\cup}\,\mathbb{R}^{k+1},\quad
k\in\mathbb{N}\,.$

which follow the instructions given by $c_{k}(x)$. As a first step, we let

$\displaystyle d_{0}(A)=c_{0}\,,$

where $c_{0}\in\mathbb{R}^{\infty}$ since $c_{0}$ has zero arguments.

Now for all $k>0$, the value of $d_{k}(A)$ depends on the value of
$d_{k-1}(A)$. If $d_{k-1}(A)\in\mathbb{R}^{k}$, then the algorithm has not
terminated yet, but has evaluated $(k+1)$ evaluation functions. To decide how
to proceed in the next step, we then use the function $c_{k}$. Let

$\displaystyle a=(a_{0},\dots,a_{m})=c_{k}(d_{k-1}(A))\,.$

If $a_{0}\neq 0$, then $c_{k}$ has determined that another evaluation is
necessary. In that case, $m=1$, and $a_{1}$ contains the index of the function
to be evaluated. Therefore, in this case, we let

$\displaystyle d_{k}(A)=(b_{1},\dots,b_{k},f_{a_{1}}(A))\,.$

where $(b_{0},\dots,b_{k-1})=d_{k-1}(A)$, thus appending the result of the
requested evaluation to the previous ones.

If on the other hand $a_{0}\neq 0$, then $c_{k}$ has determined that the
previous evaluations were sufficient to estimate the result, and the values
$a_{1},\dots,a_{N}$ contain a representation of the result. In this case,
therefore, we let

$\displaystyle d_{k}(A)=F_{\text{embed}}(a_{1},\dots,a_{N})\,.$

Finally, if $d_{k-1}(A)\in\mathcal{M}$, then a result has already been found
in a previous step, so that we have to perform no further computation and can
simply define

$\displaystyle d_{k}(A)=d_{k-1}(A)\,.$

Again, we say that the algorithm terminates for an argument $A\in\Omega$ if
$d_{k}(A)\in\mathcal{M}$ for some $k\in\mathbb{N}$. If an algorithm terminates
for all $A\in\Omega$, we can define a map $\Gamma:\Omega\to\mathcal{M}$ by
mapping $A$ to $d_{k}(A)$ for the first $k\in\mathbb{N}$ for which
$d_{k}(A)\in\mathcal{M}$. If we speak of an algorithm $\Omega\to\mathcal{M}$
in the following, we always mean an algorithm that terminates for all
$A\in\Omega$, and we will usually identify the algorithm with its associated
map $\Gamma:\Omega\to\mathcal{M}$.

##  Appendix C Evaluation functions for flc operators

In this section, we will describe how to augment the set of evaluation
functions $\Lambda$ in a way that allows algorithms to make use of the flc
structure for the flc spectral and pseudospectral problems defined in
Definitions 10 and 12.

The evaluation functions have to represent a given flc operator by a set of
real functions. Let $H$ be an flc discrete operator. As a first step, for
every $L\in\mathbb{N}$, let $(x_{L,i})_{i=1,\dots,n_{\textrm{patch}}(L)}$ be
an enumeration of the local patches at scale $L$, so that for every
$y\in\mathbb{R}^{n}$, there is exactly one
$n\in\\{1,\dots,n_{\textrm{patch}}(L)\\}$ such that $H$ has equivalent action
on $B_{L}(y)$ and $B_{L}(x_{L,i})$.

Now for every local patch $B_{L}(x_{m})$, since $\Gamma$ is uniformly
discrete, the set $B_{L}(x_{m})\cap\Gamma$ is finite. For any $L>0$,
$m\in\\{1,\dots,n_{\rm patch}(L)\\}$, let $(p_{L,m,k})$ be the $k$-th point in
$B_{L}(x_{m})$, according to some enumeration of the points. Using these
definitions, we can now define our conditions on a set of evaluation functions
that captures the finite local complexity structure.

######  Condition 35.

Let

$\displaystyle\mathcal{I}:=$
$\displaystyle\;(\\{1\\}\times\mathbb{N})\;\dot{\cup}\;(\\{2\\}\times\mathbb{N}\times\mathbb{N})\;\dot{\cup}\;(\\{3\\}\times\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\mathbb{N})$
$\displaystyle\;\dot{\cup}\;(\\{4\\}\times\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\mathbb{N})\,.$

Then a family of functions $(f_{i})_{i\in\mathcal{I}}$ fulfills our conditions
for a set of evaluation functions if:

  * •

$f_{1,L}(H)$ is the number of local patches, up to equivalent action, of $H$
at scale $L$, defined above as $n_{\textrm{patch}}(L)$.

  * •

$f_{2,L,m}(H)$ is the number of points in $\Gamma\cap B_{L}(x_{m})$, defined
above as $n_{\rm point}(L,m)$.

  * •

$f_{3,L,m,k,l}(H)$ is the matrix element $\langle
p_{k},H_{B_{L}(x_{m})}p_{l}\rangle$, where $p_{k}$ and $p_{l}$ are the points
in $\Gamma\cap B_{L}(x_{m})$ according to the above enumeration.

  * •

$f_{4,L,n,k,i}(H)$ is $i$-th coordinate of $p_{L,n,k}$, defined above as the
$k$-th point in the $m$-th patch at scale $L$, or zero if $n>n_{\rm patch}(L)$
or $i>n$ or $k>n_{\rm patch}(L)$.

  * •

$f_{5}(H)$ is a bound on the norm of $H$.

  * •

$f_{6}(H)=:C$ and $f_{7}(H)=:\varepsilon$ are real numbers such that

$\displaystyle|H_{xy}|\leq C\,d(x,y)^{-(n+\varepsilon)}\,,$

for all $x,y\in\Gamma$, as in Definition 5.

The evaluation functions $f_{2,L,m}(H)$, $f_{3,L,m,k,l}(H)$, and
$f_{4,L,m,k,i}(H)$ are defined to be zero if any index is out of bounds, that
is if $m>n_{\rm patch}(L)$ or $k>n_{\rm point}(L,m)$ or $l>n_{\rm point}(L,m)$
or $i>n$.

## References

  * [1] Abel, N. H. Mémoire sur les equations algébriques, où l’on démontre l’impossibilité de la résolution de l’équation générale du cinquième degré.  Groendahl, Christiania, 1824.
  * [2] Aizenman, M., and Warzel, S. Random operators, vol. 168 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2015.  Disorder effects on quantum spectra and dynamics.
  * [3] Anderson, P. W. Absence of diffusion in certain random lattices.  Physical Review 109, 5 (Mar. 1958), 1492–1505.
  * [4] Arveson, W. The role of C*-algebras in infinite-dimensional numerical linear algebra.  In C* -algebras: 1943–1993, vol. 167 of Contemporary Mathematics. American Mathematical Society, 1993, pp. 114–129.
  * [5] Band, R., Beckus, S., Pogorzelski, F., and Tenenbaum, L. Periodic approximation of substitution subshifts.  In preparation.
  * [6] Bauer, F. L., and Fike, C. T. Norms and exclusion theorems.  Numerische Mathematik 2, 1 (Dec. 1960), 137–141.
  * [7] Bazley, N. W. Lower bounds for eigenvalues.  Journal of Mathematics and Mechanics 10, 2 (1961), 289–307.
  * [8] Bazley, N. W., and Fox, D. W. Lower bounds for eigenvalues of Schrödinger’s equation.  Physical Review 124, 2 (Oct. 1961), 483–492.
  * [9] Bazley, N. W., and Fox, D. W. Methods for lower bounds to frequencies of continuous elastic systems.  Zeitschrift für angewandte Mathematik und Physik (1966).
  * [10] Beckus, S. personal communication.
  * [11] Beckus, S., Bellissard, J., and De Nittis, G. Spectral continuity for aperiodic quantum systems I. General theory.  Journal of Functional Analysis 275, 11 (Dec. 2018), 2917–2977.
  * [12] Beckus, S., Bellissard, J., and De Nittis, G. Spectral Continuity for Aperiodic Quantum Systems II. Periodic Approximations in 1D.  Tech. rep., Mar. 2018.  arXiv:1803.03099.
  * [13] Beckus, S., Hartnick, T., and Pogorzelski, F. Symbolic substitution systems beyond abelian groups.  arXiv preprint arXiv:2109.15210 (2021).
  * [14] Beckus, S., Lenz, D., Lindner, M., and Seifert, C. On the spectrum of operator families on discrete groups over minimal dynamical systems.  Mathematische Zeitschrift 287, 3 (Dec. 2017), 993–1007.
  * [15] Beckus, S., and Pogorzelski, F. Delone dynamical systems and spectral convergence.  Ergodic Theory and Dynamical Systems 40, 6 (June 2020), 1510–1544.
  * [16] Beckus, S., and Takase, A. Spectral estimates of dynamically-defined and amenable operator families, Oct. 2021.  arXiv:2110.05763.
  * [17] Behnke, H., and Goerisch, F. Inclusions for eigenvalues of selfadjoint problems.  In Topics in Validated Computations, J. Herzberger, Ed. 1994.
  * [18] Behnke, H., and Mertins, U. Eigenwertschranken fur das Problem der frei schwingenden rechteckigen Platte und Untersuchungen zum Ausweichphänomen.  Zeitschrift für Mathematik und Mechanik (1995).
  * [19] Bellissard, J. Spectral properties of schrödinger’s operator with a thue-morse potential.  In Number Theory and Physics: Proceedings of the Winter School, Les Houches, France, March 7–16, 1989. Springer, 1990, pp. 140–150.
  * [20] Bellissard, J., Bovier, A., and Ghez, J.-M. Gap labelling theorems for one dimensional discrete Schrödinger operators.  Reviews in Mathematical Physics 4, 01 (1992), 1–37.
  * [21] Bellissard, J., Iochum, B., Scoppola, E., and Testard, D. Spectral properties of one dimensional quasi-crystals.  Communications in Mathematical Physics 125, 3 (Sept. 1989), 527–543.
  * [22] Ben-Artzi, J., Colbrook, M. J., Hansen, A. C., Nevanlinna, O., and Seidel, M. Computing Spectra – On the Solvability Complexity Index Hierarchy and Towers of Algorithms, June 2020.  arXiv:1508.03280.
  * [23] Ben-Artzi, J., Marletta, M., and Rösler, F. Universal algorithms for computing spectra of periodic operators.  Numerische Mathematik 150, 3 (Mar. 2022), 719–767.
  * [24] Besbes, A., Boshernitzan, M., and Lenz, D. Delone Sets with Finite Local Complexity: Linear Repetitivity Versus Positivity of Weights.  Discrete & Computational Geometry 49, 2 (Mar. 2013), 335–347.
  * [25] Blum, L. Computing over the reals: Where Turing meets Newton.  Notices of the AMS 51, 9 (2004), 1024–1034.
  * [26] Blum, L., Cucker, F., Shub, M., and Smale, S. Complexity and Real Computation.  Springer Science & Business Media, 1998.
  * [27] Blum, L., Shub, M., and Smale, S. On a theory of computation and complexity over the real numbers: Mp-completeness, recursive functions and universal machines.  Bulletin of the American Mathematical Society 21, 1 (1989), 1–46.
  * [28] Böttcher, A. Pseudospectra and Singular Values of Large Convolution Operators.  The Journal of Integral Equations and Applications 6, 3 (1994), 267–301.
  * [29] Carstensen, C., and Gallistl, D. Guaranteed lower eigenvalue bounds for the biharmonic equation.  Numerische Mathematik 126, 1 (2014), 33–51.
  * [30] Carstensen, C., and Gedicke, J. Guaranteed lower bounds for eigenvalues.  Mathematics of Computation 83, 290 (Nov. 2014), 2605–2629.
  * [31] Chandler-Wilde, S. N., Chonchaiya, R., and Lindner, M. On the spectra and pseudospectra of a class of non-self-adjoint random matrices and operators.  Operators and Matrices, 4 (2013), 739–775.
  * [32] Chandler-Wilde, S. N., and Lindner, M. Coburn’s lemma and the finite section method for random Jacobi operators.  Journal of Functional Analysis 270, 2 (Jan. 2016), 802–841.
  * [33] Colbrook, M. Pseudoergodic operators and periodic boundary conditions.  Mathematics of Computation 89, 322 (2020), 737–766.
  * [34] Colbrook, M. J. On the Computation of Geometric Features of Spectra of Linear Operators on Hilbert Spaces.  Foundations of Computational Mathematics (2022).
  * [35] Colbrook, M. J., and Hansen, A. C. The foundations of spectral computations via the solvability complexity index hierarchy.  Journal of the European Mathematical Society (2022).
  * [36] Colbrook, M. J., Roman, B., and Hansen, A. C. How to compute spectra with error control.  Physical Review Letters 122, 25 (2019), 250201.
  * [37] Damanik, D., Embree, M., Gorodetski, A., and Tcheremchantsev, S. The fractal dimension of the spectrum of the fibonacci hamiltonian.  Communications in mathematical physics 280, 2 (2008), 499–516.
  * [38] Damanik, D., and Fillman, J. One-Dimensional Ergodic Schrödinger Operators: I. General Theory, vol. 221.  American Mathematical Society, 2022.
  * [39] Damanik, D., and Gorodetski, A.
  * [40] Damanik, D., Gorodetski, A., and Yessen, W. The Fibonacci Hamiltonian.  Inventiones mathematicae 206, 3 (Dec. 2016), 629–692.
  * [41] Davies, E. B. A Hierarchical Method for Obtaining Eigenvalue Enclosures.  Mathematics of Computation 69, 232 (2000), 1435–1455.
  * [42] Davies, E. B., and Plum, M. Spectral pollution.  IMA journal of numerical analysis 24, 3 (2004), 417–438.
  * [43] Davies, E. B., and Safarov, Y., Eds.  Spectral Theory and Geometry.  London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1999.
  * [44] Embree, M., and Fillman, J. Spectra of discrete two-dimensional periodic schrödinger operators with small potentials.  Journal of Spectral Theory 9, 3 (2019), 1063–1087.
  * [45] Fuchs, J.-N., Mosseri, R., and Vidal, J. Landau levels in quasicrystals.  Physical Review B 98, 16 (Oct. 2018), 165427.
  * [46] Fuchs, J.-N., and Vidal, J. Hofstadter butterfly of a quasicrystal.  Physical Review B 94, 20 (2016), 205437.
  * [47] Fulga, I. C., Pikulin, D., and Loring, T. Aperiodic Weak Topological Superconductors.  Physical Review Letters 116, 25 (June 2016), 257002.
  * [48] Gabel, F., Gallaun, D., Großmann, J., Lindner, M., and Ukena, R. Finite sections of periodic Schrödinger operators, Apr. 2022.  arXiv:2110.09339.
  * [49] Gershgorin, S. Über die Abgrenzung der Eigenwerte einer Matrix.  Bulletin de l’Académie des Sciences de l’URSS. VII. Série 1931, 6 (1931), 749–754.
  * [50] Golub, G. H., and van der Vorst, H. A. Eigenvalue computation in the 20th century.  In Numerical Analysis: Historical Developments in the 20th Century. Elsevier, 2001, pp. 209–239.
  * [51] Halperin, B. I. Properties of a particle in a one-dimensional random potential.  Advances in Chemical Physics 13 (1967), 123–177.
  * [52] Hansen, A. On the Solvability Complexity Index, the n-pseudospectrum and approximations of spectra of operators.  Journal of the American Mathematical Society 24, 1 (Jan. 2011), 81–124.
  * [53] Hansen, A. C. On the approximation of spectra of linear operators on Hilbert spaces.  Journal of Functional Analysis 254, 8 (Apr. 2008), 2092–2126.
  * [54] Hansen, A. C. Infinite-dimensional numerical linear algebra: theory and applications.  Proceedings of The Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 466, 2124 (2010), 3539–3559.
  * [55] Hansen, A. C., and Nevanlinna, O. Complexity Issues in Computing Spectra, Pseudospectra and Resolvents, Oct. 2016.  arXiv:1610.07072.
  * [56] Hege, P. Spectral gaps in systems of finite local complexity.  PhD thesis, University of Tübingen, 2024.
  * [57] Hege, P., Moscolari, M., and Teufel, S. Finding spectral gaps in quasicrystals.  Physical Review B 106, 15 (Oct. 2022), 155140.
  * [58] Hinrichsen, D., and Pritchard, A. J. On spectral variations under bounded real matrix perturbations.  Numerische Mathematik 60 (1991), 509–524.
  * [59] Hofstadter, D. R. Energy levels and wave functions of Bloch electrons in rational and irrational magnetic fields.  Physical Review B 14, 6 (Sept. 1976), 2239–2249.
  * [60] Hu, J., Huang, Y., and Ma, R. Guaranteed lower bounds for eigenvalues of elliptic operators.  Journal of Scientific Computing 67 (2016), 1181–1197.
  * [61] Jagannathan, A. The Fibonacci quasicrystal: Case study of hidden dimensions and multifractality.  Reviews of Modern Physics 93, 4 (Nov. 2021), 045001.
  * [62] Jagannathan, A., and Duneau, M. An eightfold optical quasicrystal with cold atoms.  Europhysics Letters 104, 6 (Jan. 2014), 66003.
  * [63] Kato, T. On the Upper and Lower Bounds of Eigenvalues.  Journal of the Physical Society of Japan 4, 4-6 (1949), 334–339.
  * [64] Katsura, S., Hatta, T., and Morita, A. On the Conception of the Energy Band in the Perturbed Periodic Potential.  Progress of Theoretical Physics 5, 2 (1950), 330–331.
  * [65] Kellendonk, J. Noncommutative geometry of tilings and gap labelling.  Reviews in Mathematical Physics 7, 07 (1995), 1133–1180.
  * [66] Kohmoto, M., Kadanoff, L. P., and Tang, C. Localization Problem in One Dimension: Mapping and Escape.  Physical Review Letters 50, 23 (June 1983), 1870–1872.
  * [67] Korotyaev, E., and Saburova, N. Schrödinger operators on periodic discrete graphs.  Journal of Mathematical Analysis and Applications 420, 1 (2014), 576–611.
  * [68] Lagarias, J. C. Meyer’s concept of quasicrystal and quasiregular sets.  Communications in mathematical physics 179, 2 (1996), 365–376.
  * [69] Lagarias, J. C. Geometric models for quasicrystals I. Delone sets of finite type.  Discrete & Computational Geometry 21, 2 (1999), 161–191.
  * [70] Lagarias, J. C. Geometric models for quasicrystals II. Local rules under isometries.  Discrete & Computational Geometry 21, 3 (1999), 345–372.
  * [71] Landau, H. J. On Szegö’s eingenvalue distribution theorem and non-Hermitian kernels.  Journal d’Analyse Mathématique 28, 1 (1975), 335–357.
  * [72] Levi, D., and Ragnisco, O. Non-linear differential-difference equations with N-dependent coefficients. II.  Journal of Physics A: Mathematical and General 12, 7 (1979), L163.
  * [73] Lewin, M., and Séré, E. Spectral pollution and how to avoid it.  Proceedings of the London Mathematical Society 100, 3 (2010), 864–900.
  * [74] Lindner, M. The finite section method in the space of essentially bounded functions: An approach using limit operators.  Numerical Functional Analysis and Optimization 24, 7-8 (Dec. 2003), 863–893.
  * [75] Lindner, M. Infinite Matrices and their Finite Sections: An Introduction to the Limit Operator Method.  Springer Science & Business Media, Nov. 2006.
  * [76] Lindner, M., and Schmeckpeper, D. A note on Hausdorff convergence of pseudospectra.  Opuscula Mathematica 43, 1 (2023), 101–108.
  * [77] Lindner, M., and Seidel, M. An affirmative answer to a core issue on limit operators.  Journal of Functional Analysis 267, 3 (Aug. 2014), 901–917.
  * [78] Liu, W. Fermi isospectrality for discrete periodic schrödinger operators.  Communications on Pure and Applied Mathematics 77, 2 (2024), 1126–1146.
  * [79] Liu, X. A framework of verified eigenvalue bounds for self-adjoint differential operators.  Applied Mathematics and Computation 267 (2015), 341–355.
  * [80] Marcelli, G., Moscolari, M., and Panati, G. Localization of generalized Wannier bases implies Chern triviality in non-periodic insulators.  Annales Henri Poincaré 24, 3 (Mar. 2023), 895–930.
  * [81] Neumann, E., and Pauly, A. A topological view on algebraic computation models.  Journal of Complexity 44 (2018), 1–22.
  * [82] Penrose, R. Pentaplexity: A class of non-periodic tilings of the plane.  The Mathematical Intelligencer 2, 1 (1979), 32–37.
  * [83] Plum, M. Guaranteed numerical bounds for eigenvalues.  In Spectral Theory & Computational Methods of Sturm-Liouville Problems. CRC Press, 2021, pp. 313–332.
  * [84] Rabinovich, V. S., and Roch, S. The essential spectrum of schrödinger operators on lattices.  Journal of Physics A: Mathematical and General 39, 26 (2006), 8377\.
  * [85] Ritz, W. Über eine neue Methode zur Lösung gewisser Variationsprobleme der mathematischen Physik.  Journal für die reine und angewandte Mathematik, 135 (1909).
  * [86] Ruffini, P. Sopra la determinazione delle radici nelle equazioni numeriche di qualunque grado. memoria del dottor Paolo Ruffini.  Modena, Società Tipografica (1804).
  * [87] Rösler, F. On the Solvability Complexity Index for Unbounded Selfadjoint and Schrödinger Operators.  Integral Equations and Operator Theory 91, 6 (Nov. 2019), 54.
  * [88] Saad, Y. Numerical methods for large eigenvalue problems.  SIAM, 2011.
  * [89] Satija, I. I. The Butterfly in the Quantum World: The story of the most fascinating quantum fractal.  IOP Concise Physics, Sept. 2016.
  * [90] Schur, J. Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen.
  * [91] Sy, P. W., and Sunada, T. Discrete schrödinger operators on a graph.  Nagoya mathematical journal 125 (1992), 141–150.
  * [92] Sütő, A. The spectrum of a quasiperiodic Schrödinger operator.  Communications in mathematical physics 111, 3 (1987), 409–415.
  * [93] Taussky, O. How I became a torchbearer for matrix theory.  The American Mathematical Monthly 95, 9 (Nov. 1988), 801–812.
  * [94] Tenenbaum, L. Approximations of symbolic substitution systems in one dimension.  arXiv preprint arXiv:2402.19151 (2024).
  * [95] Thouless, D. J. Electrons in disordered systems and the theory of localization.  Physics Reports 13, 3 (1974), 93–142.
  * [96] Trefethen, L. N., and Embree, M. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators.  University Press Group, Princeton, N.J, July 2005.
  * [97] Turing, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem.  Proceedings of the London Mathematical Society s2-42, 1 (1937), 230–265.
  * [98] Varah, J. M. On the separation of two matrices.  SIAM Journal on Numerical Analysis 16, 2 (1979), 216–222.
  * [99] von Mises, R., and Geiringer, H. Praktische Verfahren der Gleichungsauflösung.  Zeitschrift für angewandte Mathematik und Mechanik 9 (1929), 58–76.
  * [100] Weinstein, A. Étude des spectres des équations aux dérivées partielles de la theorie des plaques elastiques.  PhD thesis, Université de Paris, 1937.
  * [101] Weyl, H. Ramifications, old and new, of the eigenvalue problem.  Bulletin of the American Mathematical Society 56 (1950), 115–139.
  * [102] Wilkinson, J. H. Rigorous error bounds for computed eigensystems.  The Computer Journal. Section A / Section B 4 (1961), 230–241.
  * [103] Yamamoto, T. Error bounds for computed eigenvalues and eigenvectors.  Numerische Mathematik 34, 2 (June 1980), 189–199.
  * [104] Yamamoto, T. Error bounds for computed eigenvalues and eigenvectors. II.  Numerische Mathematik 40 (1982), 201–206.

(P. Hege) | Department of Neural Dynamics and MEG,
---|---
| Hertie Institute for Clinical Brain Research,
| Otfried-Müller-Str. 25, 72076 Tübingen, Germany
| and
| Werner Reichardt Centre for Integrative Neuroscience,
| Otfried-Müller-Str. 25, 72076 Tübingen, Germany
| and
| MEG Center, University of Tübingen,
| Otfried-Müller-Str. 47, 72076 Tübingen, Germany
|  E-mail address<EMAIL_ADDRESS>
(M. Moscolari) | Dipartimento di Matematica, Politecnico di Milano
| Piazza Leonardo da Vinci 32, 20133 Milano, Italy
|  E-mail address<EMAIL_ADDRESS>
(S. Teufel) | Mathematisches Institut, University of Tübingen
| Auf der Morgenstelle 10, 72076 Tübingen, Germany
|  E-mail address<EMAIL_ADDRESS>