Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 7 - undecidability of the spectral gap for unconstrained dimension

Proved
UndecidableSpectralGap.usg_gap_unconstrained_dimension

by LG · Sep 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

mathematical-physicsquantum-informationspectral-gaptheoretical-computer-scienceundecidability

Fix ε>0\varepsilon>0ε>0 and a universal machine. For every input nnn there are a local Hilbert space dimension D(n)D(n)D(n) - allowed to grow with nnn - and Hermitian nearest-neighbour interactions hrow(n),hcol(n)h_{\mathrm{row}}(n),h_{\mathrm{col}}(n)hrow​(n),hcol​(n) with rational matrix entries and operator norm smaller than 1+ε1+\varepsilon1+ε, defining a family {HΛ(L)(n)}L\{H^{\Lambda(L)}(n)\}_L{HΛ(L)(n)}L​ on square lattices with open boundary conditions and no on-site term, such that:

  1. the family is frustration free: both interactions are positive semidefinite and λ0(HΛ(L)(n))=0\lambda_0(H^{\Lambda(L)}(n))=0λ0​(HΛ(L)(n))=0 for every L≥1L\ge1L≥1;

  2. if the machine halts on input nnn, the family is gapped with spectral gap at least 111;

  3. if it does not halt on input nnn, the family is gapless.

Since the halting problem is undecidable and the map n↦(hrow(n),hcol(n))n\mapsto(h_{\mathrm{row}}(n),h_{\mathrm{col}}(n))n↦(hrow​(n),hcol​(n)) 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 111. 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.

Preamble
import Definitions.Def_usg_spectral_notions

set_option autoImplicit false
open scoped ComplexOrder
Formal statement
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 UndecidableSpectralGap
Source
Cubitt, Perez-Garcia & Wolf, Undecidability of the Spectral Gap, Forum of Mathematics Pi 10:e14 (2022), pp. 1-102, doi:10.1017/fmp.2021.15, https://doi.org/10.1017/fmp.2021.15 (full version; same numbering as arXiv:1502.04573v5), Section 2.1, p. 10, Corollary 7 (Undecidability of the spectral gap for unconstrained dimension), together with Theorem 6 (i) (frustration-freeness), p. 9.
Read-back

What the Lean code literally says, in plain math · Aristotle (Harmonic)

Fix a partial recursive code uuu (a code for a partial computable function of one natural argument) and a real number ε>0\varepsilon > 0ε>0. The statement asserts the existence of a function D:N→ND:\mathbb{N}\to\mathbb{N}D:N→N assigning a local dimension to each instance, and of two families of matrices hrow(n),hcol(n)h_{\mathrm{row}}(n), h_{\mathrm{col}}(n)hrow​(n),hcol​(n), each of size D(n)2×D(n)2D(n)^2 \times D(n)^2D(n)2×D(n)2 with complex entries and indexed by pairs of levels in {0,…,D(n)−1}\{0,\dots,D(n)-1\}{0,…,D(n)−1}, such that for every natural number nnn the following seven conditions hold. Here HnΛ(L)H_n^{\Lambda(L)}HnΛ(L)​ denotes the Hamiltonian on the L×LL\times LL×L square lattice with open boundary conditions and local dimension D(n)D(n)D(n), with on-site term the zero matrix (no on-site term), hrow(n)h_{\mathrm{row}}(n)hrow​(n) on every horizontal edge and hcol(n)h_{\mathrm{col}}(n)hcol​(n) on every vertical edge.

  1. hrow(n)h_{\mathrm{row}}(n)hrow​(n) and hcol(n)h_{\mathrm{col}}(n)hcol​(n) are Hermitian.
  2. Every entry of hrow(n)h_{\mathrm{row}}(n)hrow​(n) is a rational number viewed as a complex number, and likewise for hcol(n)h_{\mathrm{col}}(n)hcol​(n): for all indices i,ji,ji,j there is r∈Qr\in\mathbb{Q}r∈Q with the entry equal to rrr. In particular all entries are real.
  3. Their ℓ2\ell^2ℓ2-operator norms satisfy ∥hrow(n)∥<1+ε\lVert h_{\mathrm{row}}(n)\rVert < 1+\varepsilon∥hrow​(n)∥<1+ε and ∥hcol(n)∥<1+ε\lVert h_{\mathrm{col}}(n)\rVert < 1+\varepsilon∥hcol​(n)∥<1+ε (strict inequalities).
  4. The family is frustration free: the zero on-site matrix, hrow(n)h_{\mathrm{row}}(n)hrow​(n) and hcol(n)h_{\mathrm{col}}(n)hcol​(n) are positive semidefinite, and λ0(HnΛ(L))=0\lambda_0\bigl(H_n^{\Lambda(L)}\bigr) = 0λ0​(HnΛ(L)​)=0 for every L>0L > 0L>0, where λ0\lambda_0λ0​ is the infimum of the real spectral points (equal to 000 by convention if that set is empty).
  5. If the evaluation of uuu on input nnn is defined (the machine halts on nnn), then the family {HnΛ(L)}L\{H_n^{\Lambda(L)}\}_L{HnΛ(L)​}L​ is gapped with gap at least 111: there is L0L_0L0​ such that for all L>L0L > L_0L>L0​ the eigenspace of HnΛ(L)H_n^{\Lambda(L)}HnΛ(L)​ at its ground state energy is one-dimensional and every other real spectral point μ\muμ satisfies μ≥λ0+1\mu \ge \lambda_0 + 1μ≥λ0​+1.
  6. If the evaluation of uuu on input nnn is not defined (the machine does not halt on nnn), then the family is gapless: there is a real c>0c>0c>0 such that for every real δ>0\delta>0δ>0 there is L0L_0L0​ with the property that for all L>L0L>L_0L>L0​, every real xxx in [λ0(HnΛ(L)), λ0(HnΛ(L))+c][\lambda_0(H_n^{\Lambda(L)}),\,\lambda_0(H_n^{\Lambda(L)})+c][λ0​(HnΛ(L)​),λ0​(HnΛ(L)​)+c] lies within distance δ\deltaδ of some real spectral point of HnΛ(L)H_n^{\Lambda(L)}HnΛ(L)​.

Conditions 5 and 6 are conditionals on complementary hypotheses, so exactly one of them has a non-vacuous content for each nnn. Note that condition 4 fixes λ0(HnΛ(L))=0\lambda_0(H_n^{\Lambda(L)}) = 0λ0​(HnΛ(L)​)=0 for all L>0L>0L>0 and all nnn, including the halting and the non-halting case, so the gapped and gapless conditions are statements about the spectrum above the value 000.

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, ε\varepsilonε is quantified before the families, so DDD, hrowh_{\mathrm{row}}hrow​ and hcolh_{\mathrm{col}}hcol​ may depend on ε\varepsilonε and on uuu, but not on nnn beyond the displayed argument; the values D(n)D(n)D(n) are unconstrained in size, and nothing prevents them from growing with nnn.

Provenance: this read-back was produced by the agent that drafted the item, not by an independent blind auditor.

Human review
  • Endorsed by Shuze Chen · Sep 15, 2026

  • Endorsed by LG · Sep 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me