Computing Spectral Size: Rigorous Algorithms and the Limits of Computation
For researchers in spectral theory and computational mathematics, this provides a rigorous foundation and optimal algorithms for computing spectral properties that were previously intractable, with implications for physics and materials science.
This work develops a unified framework for rigorous computation of spectral size (e.g., Lebesgue measure, fractal dimension) for bounded self-adjoint operators, achieving algorithmically optimal methods with complexity classified in the SCI hierarchy. It establishes sharp lower bounds via impossibility results for limit-periodic Schrödinger operators and enables state-of-the-art computations for aperiodic systems.
Many structures in mathematical physics and dynamics exhibit intricate fractal geometry. Such behavior appears prominently in quantum mechanics and materials science through spectra of aperiodic and quasicrystalline operators, where questions of ``size'' (Lebesgue measure, fractal dimension, spectral gaps, etc.) are central. Yet the lack of rigorous computational tools for analyzing these quantities limits both theory and application. Naïve truncation often fails, and there is no overarching framework to explain what can, and cannot, be computed. We develop a unified program for the rigorous computation of spectral size for bounded self-adjoint operators, based on local spectral exclusions and adaptive covers. This constructive framework yields algorithmically optimal methods (under natural computational assumptions) that bridge spectral theory with computation to address problems previously deemed intractable. Their complexity is classified within the Solvability Complexity Index (SCI) hierarchy, extending Smale's program on the limits of computation. Sharp computational lower bounds are established through impossibility results for limit-periodic Schrödinger operators constructed from adversarial potentials. The methods enable state-of-the-art rigorous computations for one- and two-dimensional aperiodic systems, and pinpoint problems where numerics can feed directly into computer-assisted proofs. Beyond spectral analysis, they apply broadly to computing measures of size for general closed sets, opening new directions in the computational study of complex geometric structures.