Abstract

The problem of finding algorithms for computing spectra of operators and solutions to PDEs has both fascinated and frustrated mathematicians since the seminal work by H. Goldstine, F. Murray, and J. von Neumann in the 1950s.  W. Arveson pointed out in the 1990s that despite the plethora of papers on the subject of computing spectra, the general computational spectral problem remained unsolved. We will discuss the solution to the computational spectral problem and show how it can only be solved through the Solvability Complexity Index (SCI) hierarchy. Moreover, the theory of the SCI hierarchy also implies uncertainty principles in spectral theory and PDEs. In particular, for the wave equation, given appropriate Sobolev norms, one can prove that the forward operator taking the initial data to the solution of the PDE at time T=1 is bounded. Yet, there is an epsilon > 0 such that — under the same conditions — the question: `does the solution at T = 1 intersect the open ball centred at zero with radius epsilon?’ becomes undecidable (non-provable). That is, determining the location of the solution is independent of the mathematical axioms. This implies that there is an uncertainty principle for the wave equation. This phenomenon is linked to T. Tao’s program on blow-up of PDEs and undecidability of long term behaviour of PDEs. Potentially surprisingly, our results imply that a similar undecidability phenomenon can happen even for finite fixed time for well-posed problems. Finally, uncertainty principles exist for spectra of operators, even for the self-adjoint cases: one can prove that there are self-adjoint operators  where the spectrum depends continuously on the operator, yet, there is an epsilon, so that statements about the location of the spectrum to epsilon accuracy becomes undecidable.