Theorem 5.1 (lattices) for the paper's lattice, with the gap exponent as a variable
ProvedLatticePrepro.QuadraticVerifier.Tables.latticeFamily_hasGap_of_eqLet be a real norm exponent or , with , and let . Let be a quadratic verifier over with instance length , assignment coordinates and language , and let be tables for and a real number with (a base and an explicit moment representation, independent of the instance). Let be the fixed linear system of Construction 4.5 for , with blocks, let be the lattice of Lemma 3.12 for this system (the Construction A lattice of the padded code if , its blockwise Walsh–Hadamard transform otherwise), with its integer targets , and let be the radius of Lemma 3.12 (, or ).
Statement. With = sizeExp 2 δ,
This is the statement Tables.latticeFamily_hasGap with the exponent kept as a variable that is assumed equal to . It carries the proof; the stated form of Theorem 5.1 for lattices follows by substituting .
Formalization Note. The conclusion is LatticeFamily.HasGap. Polynomial-time computability of the lattice and the targets is not formalized. The target uses a solution of picked by classical choice, where the paper uses Gaussian elimination; the distance from the target to the lattice does not depend on the solution.
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_Codes_Ext
import Definitions.Def_LatticePrepro_Conversions_ConstructionA
import Definitions.Def_LatticePrepro_Conversions_ConstructionA_Ext
import Definitions.Def_LatticePrepro_Conversions_Hadamard
import Definitions.Def_LatticePrepro_Conversions_Hadamard_Ext
import Definitions.Def_LatticePrepro_Conversions_Padding
import Definitions.Def_LatticePrepro_Conversions_Lattices
import Definitions.Def_LatticePrepro_Conversions_Lattices_Ext
import Definitions.Def_LatticePrepro_Lattices_Distance
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_Lattices_Mathlib
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
import Definitions.Def_LatticePrepro_ThreeSAT_Ext
import Definitions.Def_LatticePrepro_Explicit
open LatticePrepro
open LatticePrepro.QuadraticVerifier
variable {p : ℕ} [hp : Fact p.Prime]
open LatticePrepro.QuadraticVerifier.Tables
variable {V : QuadraticVerifier p} {δ : ℝ}theorem LatticePrepro.QuadraticVerifier.Tables.latticeFamily_hasGap_of_eq (pn : PNorm) {ε δ : ℝ} (hδ : δ = 1 - pn.s * ε) (hε : 0 < ε)
(hε1 : ε < 1 / pn.s) {V : QuadraticVerifier 2} (T : V.Tables δ) :
(T.latticeFamily pn).HasGap pn (T.latticeRadius pn) ε V.Language (V.S + 1) (sizeExp 2 δ) := by sorry