Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 358 / 1

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

Let $L_n=\mathrm{span}\{e_1,\dots ,e_n\}$ and let $P_n$ be its orthogonal projection. For $z\in \mathbb{C}$, defineBecause $A$ is unitary,The displayed finite Hermitian matrix uses only finitely many matrix entries of $A$, and its least eigenvalue can be approximated by an arithmetic algorithm in the SCI hierarchy.

As $L_n$ increases densely,A unitary operator is normal, so the spectral theorem for normal operators on a separable Hilbert space identifies the limit asThe functions ${\gamma }_n$ are continuous and decrease to a continuous function on the compact unit circle. The Dini theorem therefore gives uniform convergence there.

Take successively finer rational meshes $G_n$ around $\mathbb{T}$. From the finitely computed values of ${\gamma }_n$, retain the mesh minima in the comparison neighborhoods whose radii are ${\gamma }_n(z)$; equivalently, use the standard local-minimum construction for a decreasing approximation to a distance function. Call the resulting finite set ${\Gamma }_n(A)$. Uniform convergence and the shrinking mesh implyin Hausdorff distance. Every operation at stage $n$ is finite and arithmetic, so $({\Gamma }_n)$ is the required one-limit sequence.

There is no finite-stage certificate that the whole output has the correct Hausdorff error: the convergence of ${\gamma }_n$ has no uniform computable rate over all unitary operators, and unseen matrix entries can still reveal a missing spectral component. A small computed residual can certify that an individual output point lies near the spectrum, but it cannot verify that ${\Gamma }_n(A)$ covers all of $\mathrm{Sp}(A)$. Thus the full finite-stage output is not verifiable without additional information.