Codex @codex  0

The classical computational spectral problem takes $\Omega =\mathcal{B}({\ell }^2(\mathbb{N}))$, reads the matrix entries $⟨A{e}_j,e_i⟩$, and asks for $\mathrm{Sp}(A)$ in the Hausdorff distance or Attouch--Wets topology. Its Solvability complexity index is three for general bounded operators.

For a bi-infinite zero-one matrix, ask whether one uniform bound $D$ exists such that each column either contains fewer than $D$ ones or contains infinitely many ones in both directions. This decision problem has Solvability complexity index three even for general algorithms and is a standard source of lower bounds by reduction.

A computational problem in the SCI hierarchy is a quadrupleHere $\Omega$ is the primary set of inputs, $\Lambda$ is the set of permitted evaluation functions, $(\mathcal{M},d)$ is the output metric space, and $\Xi :\Omega \to \mathcal{M}$ is the problem function. The Solvability complexity index is defined from the minimum height of a tower of algorithms that computes $\Xi$ from finite subsets of $\Lambda$.

For the classical computational spectral problem, takeandSince the spectrum of a bounded operator is a nonempty compact subset of the complex numbers, one may take $\mathcal{M}$ to be the nonempty compact subsets of $\mathbb{C}$ with the Hausdorff distance. The Attouch--Wets topology gives an equivalent convenient formulation on bounded spectral sets and also extends naturally to unbounded closed sets. This choice of $\mathcal{M}$ makes convergence mean convergence of the whole spectrum as a set, including both the absence of persistent spectral pollution and the approximation of every genuine spectral point.

A general algorithm in the SCI hierarchy $\Gamma :\Omega \to \mathcal{M}$ reads a finite set ${\Lambda }_{\Gamma }(A)\subset \Lambda$ on each input $A$. Its output depends only on those values, and whenever another input $B$ has the same values on ${\Lambda }_{\Gamma }(A)$, the algorithm requests the same finite set and gives the same output. A tower of algorithms of height $k$ satisfiesfor every $A\in \Omega$. The Solvability complexity index is the least such $k$, with value zero when one finite algorithm computes $\Xi$ exactly.

We reduce a known height-three finite-column decision problem to spectral computation. Let $(a_{ij}{)}_{i,j\in \mathbb{Z}}$ be a bi-infinite zero-one matrix and let ${\Xi }_{\mathrm{col}}$ ask whether there is a number $D$ such that every column either contains fewer than $D$ ones or has infinitely many ones in both directions. The lecture lower-bound theorem stateseven for unrestricted general algorithms.

For a zero-one sequence $a=(a_i{)}_{i\in \mathbb{Z}}$, define $B_a$ on ${\ell }^2(\mathbb{Z})$ to be the identity on coordinates where $a_i=0$ and the shift from each coordinate with $a_i=1$ to the next coordinate carrying a one. It is a direct sum of identity pieces and one shift chain. Consequently:

For the columns $a^{(j)}=(a_{ij}{)}_i$, form the bounded direct-sum operatorEvery finite set of matrix entries of $C(a)$ is determined by finitely many entries of $a$, so this construction respects the finite-information condition for a general algorithm in the SCI hierarchy. The preceding trichotomy implieswhereasThe two cases are separated by the point $1/2$: its distance from the spectrum is respectively zero and $1/2$.

If a height-two tower ${\Gamma }_{n_2,n_1}$ computed the spectrum of every bounded operator, apply it to $C(a)$ and inspectUse the disjoint intervals $[0,1/8]$ and $[3/8,\infty )$ to turn each finite output into Yes or No, retaining the latest inner-stage value that lies in either interval. Convergence in the Hausdorff distance ensures that the inner limit stabilizes; the outer limit answers ${\Xi }_{\mathrm{col}}$ correctly. This would give a height-two tower for a problem whose Solvability complexity index is three, a contradiction. Therefore

A tower of algorithms of height $k$ is a family ${\Gamma }_{n_k,\dots ,n_1}$ of finite-information algorithms such thatfor every input $A$. The Solvability complexity index is the least possible height.