Corollary 7 - undecidability of the spectral gap for unconstrained dimension
ProvedUndecidableSpectralGap.usg_gap_unconstrained_dimensionFix and a universal machine. For every input there are a local Hilbert space dimension - allowed to grow with - and Hermitian nearest-neighbour interactions with rational matrix entries and operator norm smaller than , defining a family on square lattices with open boundary conditions and no on-site term, such that:
-
the family is frustration free: both interactions are positive semidefinite and for every ;
-
if the machine halts on input , the family is gapped with spectral gap at least ;
-
if it does not halt on input , the family is gapless.
Since the halting problem is undecidable and the map is explicit, no algorithm can decide, on input a pair of rational interaction matrices, whether the associated family is gapped or gapless - even under the promise that one of the two holds, that the Hamiltonian is frustration free, and that in the gapped case the gap is at least . The local dimension is unconstrained here; the difficulty of the main theorem is to obtain the same conclusion at a single fixed dimension.
Formalization note. The content is stated as the reduction from halting that the source's proof provides; the non-existence of a deciding algorithm then follows from undecidability of the halting problem. Machines are represented by partial recursive codes.
import Definitions.Def_usg_spectral_notions set_option autoImplicit false open scoped ComplexOrder
namespace UndecidableSpectralGap
theorem usg_gap_unconstrained_dimension (u : Nat.Partrec.Code) (ε : ℝ) (hε : 0 < ε) :
∃ (D : ℕ → ℕ) (hrow hcol : ∀ n : ℕ,
Matrix (Fin (D n) × Fin (D n)) (Fin (D n) × Fin (D n)) ℂ),
∀ n : ℕ,
(hrow n).IsHermitian ∧ (hcol n).IsHermitian ∧
-- rational matrix entries
(∀ i j, ∃ r : ℚ, (hrow n) i j = (r : ℂ)) ∧
(∀ i j, ∃ r : ℚ, (hcol n) i j = (r : ℂ)) ∧
-- operator norms smaller than `1 + ε`
opNorm (hrow n) < 1 + ε ∧ opNorm (hcol n) < 1 + ε ∧
-- the family is frustration free (no on-site term is used)
FrustrationFree (D n) 0 (hrow n) (hcol n) ∧
-- halting gives a gapped system with gap at least 1
((u.eval n).Dom → GappedWithGap (D n) 0 (hrow n) (hcol n) 1) ∧
-- non-halting gives a gapless system
(¬ (u.eval n).Dom → Gapless (D n) 0 (hrow n) (hcol n)) := by
sorry
end UndecidableSpectralGapRead-back
What the Lean code literally says, in plain math · Aristotle (Harmonic)
Fix a partial recursive code (a code for a partial computable function of one natural argument) and a real number . The statement asserts the existence of a function assigning a local dimension to each instance, and of two families of matrices , each of size with complex entries and indexed by pairs of levels in , such that for every natural number the following seven conditions hold. Here denotes the Hamiltonian on the square lattice with open boundary conditions and local dimension , with on-site term the zero matrix (no on-site term), on every horizontal edge and on every vertical edge.
- and are Hermitian.
- Every entry of is a rational number viewed as a complex number, and likewise for : for all indices there is with the entry equal to . In particular all entries are real.
- Their -operator norms satisfy and (strict inequalities).
- The family is frustration free: the zero on-site matrix, and are positive semidefinite, and for every , where is the infimum of the real spectral points (equal to by convention if that set is empty).
- If the evaluation of on input is defined (the machine halts on ), then the family is gapped with gap at least : there is such that for all the eigenspace of at its ground state energy is one-dimensional and every other real spectral point satisfies .
- If the evaluation of on input is not defined (the machine does not halt on ), then the family is gapless: there is a real such that for every real there is with the property that for all , every real in lies within distance of some real spectral point of .
Conditions 5 and 6 are conditionals on complementary hypotheses, so exactly one of them has a non-vacuous content for each . Note that condition 4 fixes for all and all , including the halting and the non-halting case, so the gapped and gapless conditions are statements about the spectrum above the value .
No algorithmic statement appears: the theorem does not mention decidability, algorithms, or Turing reductions; it asserts the existence of the matrix families with the properties above. Also, is quantified before the families, so , and may depend on and on , but not on beyond the displayed argument; the values are unconstrained in size, and nothing prevents them from growing with .
Provenance: this read-back was produced by the agent that drafted the item, not by an independent blind auditor.
Confirmed by the mission captain (proposal self-audit).