Theorem 5.1 (codes, 3SAT) for the paper's code — gap with
ProvedLatticePrepro.ThreeSAT.explicit_code_gapInstances of 3SAT on variables are encoded as bit strings of length , one bit per possible clause, and is the quadratic verifier of the 3SAT verifier circuit over the relevant prime field. Tables for consist of a base and an explicit moment representation (Theorem A.8) in the ranges of the proof of Theorem 4.8; they do not depend on the instance.
Codes. For every prime , every finite field of characteristic and every , there is such that for every there are tables for over for which the following holds. Let be the fixed linear system of Construction 4.5 for , with blocks, and let be the code spanned over by , with the targets of Lemma 3.11. Then , , and
This is the code half of Theorem 5.1 for the code that the paper constructs. The existence form of this statement only asserts that some code or lattice with targets has the gap. Since the Lean statement does not require the targets to be computable, that form is satisfied by a construction unrelated to the paper, in which the target records whether is in the language. Here the code, the lattice and the targets are the ones the paper constructs.
Formalization Note. Only the tables are asserted to exist; the code, the lattice, the targets and the radius are defined from them, and the instance enters through the right-hand side of the fixed linear system alone. Polynomial-time computability of the code, 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 code does not depend on the solution. The description lengths of Theorem 5.1 are not formalized either.
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.ThreeSAT open QuadraticVerifier
theorem LatticePrepro.ThreeSAT.explicit_code_gap (p : ℕ) [Fact p.Prime] (F : Type) [Field F] [Fintype F]
[DecidableEq F] [Algebra (ZMod p) F] (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1) :
∃ C : ℕ, ∀ v : ℕ, 1 ≤ v → ∃ T : (verifier p v).Tables (1 - ε),
((T.codeFamily F).comap encode).HasGap T.system.numBlocks ε (SAT v) (len v) C := by sorry