Theorem 5.1 (lattices) — fixed lattice with gap in for any quadratic verifier over , explicit exponent
ProvedLatticePrepro.lattice_gapLet be a norm exponent (any real , or ), and let , with for . Let . Let be a quadratic verifier over with instance length , assignment coordinates and language , and let
an explicit exponent depending only on . Then there are a dimension , a lattice (a -submodule), an integer target for every , an integer radius and an integer such that:
- ;
- , so has full rank;
- for every , ;
- for every , .
Here is the norm on (the maximum norm for ) and . In short,
The lattice and the radius do not depend on ; only the target does.
This is the lattice case of Theorem 5.1. As in the paper's proof, the verifier is over . The result is stated for an arbitrary quadratic verifier, with dimension bounded by . The paper fixes a 3SAT verifier and obtains ; that instantiation is a separate Lean result. The paper allows rational ; here every real is allowed.
Formalization Note The conclusion is Nonempty (LatticeGap pn ε V.Language (V.S + 1) C), where pn : PNorm encodes . The lattice distance is a real infimum (⨅ over lattice vectors), and is a real power (Real.rpow). Polynomial-time computability and description lengths are not formalized; the search test of Lemma 5.2 is stated separately (LatticeReduction.accepts_of_isApprox, LatticeReduction.not_accepts_of_isNo).
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.QuadraticVerifier.Tables.latticeFamily_hasGap.
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 open LatticePrepro
theorem LatticePrepro.lattice_gap (pn : PNorm) (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1 / pn.s)
(V : QuadraticVerifier 2) :
Nonempty (LatticeGap pn ε V.Language (V.S + 1) (sizeExp 2 (1 - pn.s * ε))) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.