Theorem 5.1 (codes, 3SAT) — fixed codes with gap for 3SAT
ProvedLatticePrepro.ThreeSAT.exists_code_gapLet be a prime, let be a finite field of characteristic (a finite field that is an -algebra), 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 linear code , and a target for every 3SAT instance on variables (the code depends only on , the target on );
- an integer radius ,
such that, writing for Hamming distance and :
- YES instances. If is satisfiable, then .
- NO instances. If is unsatisfiable, then
This is the code half of Theorem 5.1, instantiated with a verifier for 3SAT: one fixed code per number of variables separates satisfiable from unsatisfiable formulas with gap . It is the combinatorial core of the NCP part of Theorem 1.1; the remaining ingredients there (polynomial-time computability of code, radius and targets, and the complexity-theoretic argument) are not formalized.
Formalization Note: The conclusion is Nonempty (CodeGap F ε (SAT v) (len v) C), a structure whose fields are the code family (CodeFamily: a finite coordinate type, a subspace Submodule F (M → F) and the targets), the radius, and the properties above. Instances are 3SAT formulas encoded by one bit per possible clause, so is len v , and the families are indexed by rather than by ; may depend on , and but not on . The distance is the natural number codeDist (an sInf of Hamming distances), is Fintype.card 𝒞.M, and is a real power. Polynomial-time computability, the generator-matrix presentation and the description-length bounds of Theorem 5.1 are not part of the statement, and neither is the search test of Lemma 5.2, which is stated separately for the concrete test.
Note (existence form). This statement asserts only that some code 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_code_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_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 → Nonempty (CodeGap F ε (SAT v) (len v) C) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.