Theorem 5.1 (lattices, 3SAT) — fixed lattices with gap in every norm
ProvedLatticePrepro.ThreeSAT.exists_lattice_gapLet (a real number , or ), let (so for ), and let . Then there is a constant such that for every number of variables , with the instance length of 3SAT on variables, there exist
- a finite coordinate set of size with , a lattice (a subgroup) containing for some integer , so that has full rank, and an integer target for every 3SAT instance on variables;
- an integer radius ,
such that, writing for the norm and :
- YES instances. If is satisfiable, then .
- NO instances. If is unsatisfiable, then
This is the lattice half of Theorem 5.1, instantiated with a verifier for 3SAT: one fixed lattice per number of variables separates satisfiable from unsatisfiable formulas with gap . It is the combinatorial core of the CVP part of Theorem 1.1; the remaining ingredients there (polynomial-time computability and the complexity-theoretic argument) are not formalized.
Formalization Note: The conclusion is Nonempty (LatticeGap pn ε (SAT v) (len v) C), a structure bundling the lattice family (LatticeFamily: a finite coordinate type, a Submodule ℤ (M → ℤ) and the targets), , and the properties above. The norm exponent is a PNorm: any real (the paper states rational , which only matters for computability) or ; uses real powers and . is the real infimum latticeDist, and full rank is expressed by . Instances are encoded by one bit per possible clause ( is len v ) and indexed by ; may depend on and but not on . Polynomial-time computability, the description-length bounds and the search test of Lemma 5.2 (stated separately for the concrete test) are not part of the statement.
Note (existence form). This statement asserts only that some lattice with targets has the gap. The Lean statement does not require the targets to be computable, so this form is also satisfied by a construction unrelated to the paper, in which the target records whether the instance is in the language. The statement for the object that the paper constructs is LatticePrepro.ThreeSAT.explicit_lattice_gap.
import Mathlib import Definitions.Def_LatticePrepro_Basic_Blocks import Definitions.Def_LatticePrepro_Reduction_LinearSystem import Definitions.Def_LatticePrepro_Conversions_Codes import Definitions.Def_LatticePrepro_Conversions_ConstructionA import Definitions.Def_LatticePrepro_Conversions_Hadamard import Definitions.Def_LatticePrepro_Conversions_Lattices import Definitions.Def_LatticePrepro_Lattices_Distance import Definitions.Def_LatticePrepro_Lattices_Mathlib import Definitions.Def_LatticePrepro_Moments_Basic import Definitions.Def_LatticePrepro_Moments_Representation import Definitions.Def_LatticePrepro_Verifier_Quadratic import Definitions.Def_LatticePrepro_Reduction_FixedSystem import Definitions.Def_LatticePrepro_Tables_Digits import Definitions.Def_LatticePrepro_Tables_FieldSetup import Definitions.Def_LatticePrepro_Tables_Hankel import Definitions.Def_LatticePrepro_Tables_Construction import Definitions.Def_LatticePrepro_Tables_ElementTable import Definitions.Def_LatticePrepro_Tables_TableSoundness import Definitions.Def_LatticePrepro_Tables_Explicit import Definitions.Def_LatticePrepro_Main import Definitions.Def_LatticePrepro_Verifier_Gates import Definitions.Def_LatticePrepro_Verifier_Circuit import Definitions.Def_LatticePrepro_Verifier_Expr import Definitions.Def_LatticePrepro_Verifier_ThreeSAT import Definitions.Def_LatticePrepro_ThreeSAT open LatticePrepro open LatticePrepro.ThreeSAT
theorem LatticePrepro.ThreeSAT.exists_lattice_gap (pn : PNorm) (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1 / pn.s) :
∃ C : ℕ, ∀ v : ℕ, 1 ≤ v → Nonempty (LatticeGap pn ε (SAT v) (len v) C) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.