Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 358 (Infinite Dimensional Spectral Computation)

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.

A projection-valued measure on the Borel sets of $\mathbb{C}$ is a map $E$ into the orthogonal projections on a separable Hilbert space $\mathcal{H}$ such thatand for pairwise disjoint $B_j$,for every $v\in \mathcal{H}$, with convergence in norm.

The spectral theorem for normal operators on a separable Hilbert space states that a bounded normal operator $A$ has a unique projection-valued measure supported on $\mathrm{Sp}(A)$ for whichMore generally, the Borel functional calculus for a normal operator is

For $v,w\in \mathcal{H}$, the scalar spectral measures areIf $A$ is self-adjoint, its spectrum and hence the support of $E$ lie in $\mathbb{R}$. Moreover,so ${\mu }_v$ is a positive measure, andThe paper prints total mass $\Vert v\Vert$; with the standard definition it is $\Vert v{\Vert }^2$, so the unsquared norm is a typographical error.

Let $E_n$ and $E$ be the projection-valued measures of $A_n$ and $A$. Using the projection $P_n:\mathcal{H}\to {\mathcal{H}}_n$, defineThe scalar spectral measures converge weakly whenfor every bounded continuous function $f$ and every $v,w\in \mathcal{H}$. By the spectral theorem for normal operators on a separable Hilbert space, this is equivalent to

The assumed moment identities say precisely that this convergence holds for every monomial $f(x)=x^m$. It follows by linearity for every polynomial. For $v=w$, the $m=2$ identity givesso Markov inequality makes the positive measures $({\mu }_v^{(n)})$ tight. Higher even moments similarly control the tails of any fixed polynomial.

Given a bounded continuous $f$ and $ϵ>0$, choose $R$ so that the measure tails are uniformly small. The Weierstrass approximation theorem supplies a polynomial $p$ withMoment convergence handles $p$; tightness and a sufficiently high even moment handle the two tails. Hence $\int fd{\mu }_v^{(n)}\to \int fd{\mu }_v$. The polarization identity then gives the same conclusion for ${\mu }_{v,w}^{(n)}$. This proves weak convergence of scalar spectral measures.

The assertion fails if only $m=1$ is assumed. Let $\mathcal{H}={\ell }^2(\mathbb{N})$, let ${\mathcal{H}}_n=\mathrm{span}\{e_1,\dots ,e_n\}$, take $A=0$, and letThe reversal matrices are self-adjoint unitaries. For fixed $v,w\in {\ell }^2$,because the finite head of one vector is paired with the vanishing tail of the other. Thus the $m=1$ condition holds. However, $A_n^2=I_{{\mathcal{H}}_n}$, soin general. Taking $f(x)=x^2$ shows that the spectral measures do not converge weakly.

Here functional calculus convergence means that for every $f\in C(\mathbb{T})$,

Embed ${\mathcal{H}}_n$ in $\mathcal{H}$ and write ${\tilde{A}}_n=P_n^{\ast }{A}_n{P}_n$. The hypothesis gives ${\tilde{A}}_n\rightharpoonup A$ in the weak operator topology. Since $A_n$ and $A$ are unitary operators,Thus ${\tilde{A}}_n\to A$ in the strong operator topology. Applying the same argument to the adjoints gives ${\tilde{A}}_n^{\ast }\to A^{\ast }$ strongly.

Products of uniformly bounded strongly convergent operators converge strongly, so for every integer $k$,strongly, with negative $k$ interpreted through adjoints. Therefore convergence holds for every Laurent polynomial. The Stone-Weierstrass theorem says that Laurent polynomials are uniformly dense in $C(\mathbb{T})$. Since the continuous functional calculus is contractive, uniform approximation finishes the proof for every $f\in C(\mathbb{T})$.

Let $P_n:{\ell }^2(\mathbb{N})\to {\mathbb{C}}^n$ be coordinate projection and setThis finite matrix is computable from the matrix entries of $A$. Compute its singular value decompositionand define the unitary polar factor of a finite compressionThis is a unitary operator on ${\mathbb{C}}^n$, including when $T_n$ is singular.

Put $Q_n=P_n^{\ast }{P}_n$. Since $Q_n\to I$ strongly and $A$ is unitary,The continuous functional calculus for positive matrices therefore givesThe polar identity $T_n=A_n|T_n|$ now yieldsAlso $P_n^{\ast }{T}_n{P}_n=Q_{n}A{Q}_n\to A$ strongly, and henceIn particular the weak convergence required in part (c) holds. The construction uses only a finite block of the given matrix and a finite singular value decomposition, so it is an algorithm realizing all the assumptions of part (c).

The map $F$ is a nonsingular transformation with respect to $\omega$ whenEquivalently, the pushforward measure $F_{\ast }\omega (B)=\omega (F^{-1}(B))$ satisfies $F_{\ast }\omega \ll \omega$.

For an essentially bounded observable $g$, define the Koopman operatorNonsingularity makes this well defined on almost-everywhere equivalence classes. By the Radon-Nikodym theorem,Consequently the bounded Koopman operator criterion is

The map $F$ is a measure-preserving transformation whenfor every Borel set $B$, equivalently $F_{\ast }\omega =\omega$. In this case its Koopman operator is an isometry on $L^2(\omega )$.

The map is invertible with respect to $\omega$ when there is a measurable $G:X\to X$ such thatalmost everywhere. For an invertible measure-preserving system, $K_G=K_F^{-1}=K_F^{\ast }$, so its Koopman operator is unitary.

Suppose first that the system is ergodic and $K_{F}g=g$. For each real $t$, the level setis invariant modulo a null set, so $\omega (E_t)\in \{0,1\}$. The distribution function of $\mathrm{Re}g$ can therefore jump only once, which makes $\mathrm{Re}g$ constant almost everywhere. The same argument applies to $\mathrm{Im}g$.

Conversely, if $E$ is invariant, then $K_F{1}_E=1_E$. If every invariant $L^2$ function is constant, the indicator function $1_E$ is almost everywhere zero or one, and hence $\omega (E)=0$ or $1$. This proves the invariant-function characterization of ergodicity.

Use the Fourier basisof $L^2([-\pi ,\pi {]}_{\mathrm{per}})$. For the rotation $F(x)=x+a$,If $a/\pi$ is irrational, $e^{ika}=1$ implies $k=0$. Hence every fixed $L^2$ function has only its constant Fourier coefficient, and part (i) proves ergodicity.

If $a/\pi =p/q$ is rational, thenis a nonconstant fixed function because $e^{i2qa}=e^{i2\pi p}=1$. Part (i) now shows that the system is not ergodic. Therefore the ergodicity criterion for a circle rotation is

For inexact information in the SCI hierarchy, replace every exact evaluation $\lambda \in \Lambda$ by a family of admissible approximations ${\lambda }_m$ satisfyingAn algorithm must converge for every admissible choice of approximations, not merely for one favored encoding.

For continuous nonsingular maps $F:X\to X$, take the evaluations to be arbitrary point queries. At precision $m$, a query at $x\in X$ returns any $y$ satisfyingThus the information set contains all triples $(x,m,y)$ satisfying this inequality. This is a perfect measurement device for a dynamical system: it can sample any state, at any requested accuracy, with no fixed noise floor. The finite-information rule still requires each terminating computation to make only finitely many such measurements.

Assume for contradiction that a sequence of general algorithms ${\Gamma }_n$ decides ergodicity from the perfect measurement data, so that ${\Gamma }_n(F)$ eventually equals ${\Xi }_{\mathrm{erg}}(F)$ for every $F\in \Omega$.

Restrict the input class to the circle rotationsFrom inexact information in the SCI hierarchy for the real number $a$, one can answer every requested measurement of $F_a(x)$ to the same precision. The supposed algorithms would therefore give a one-limit decision procedure forbecause part (b)(ii) identifies ergodicity with irrationality.

Every finite-information general algorithm is locally constant on a sufficiently small cylinder of the inexact data. A pointwise limit of a sequence of such functions is a Baire class one function. But the rationality indicator is discontinuous at every real number: every interval contains both rational and irrational numbers. The theorem that the discontinuity set of a Baire class one function is meagre, or directly rationality indicator is not Baire class one, gives a contradiction.

Hence no one-limit tower of general algorithms can decide ergodicity, even with the perfect measurement device: