Theorem 5.1 (codes) — fixed code with gap for any quadratic verifier, explicit exponent
ProvedLatticePrepro.code_gapLet be a prime, a finite field of characteristic , and . Let be a quadratic verifier over with instance length , assignment coordinates and language . Let
the explicit exponent of the parameter choice, which depends only on and . Then there are a finite block length , an -linear code , a target for every , and an integer radius such that:
- ;
- for every , ;
- for every , .
Here is the Hamming distance and . In short,
The code and the radius do not depend on ; only the target does.
This is the code case () of Theorem 5.1. It is stated for an arbitrary quadratic verifier, with block length bounded by . The paper instead fixes a 3SAT verifier and obtains ; that instantiation is a separate Lean result.
Formalization Note The conclusion is Nonempty (CodeGap F ε V.Language (V.S + 1) C). The characteristic of is expressed by an Algebra (ZMod p) F instance. The code distance is a natural number defined via sInf, and is a real power (Real.rpow). Polynomial-time computability of the code and targets is not formalized; the search test of Lemma 5.2 is stated separately (CodeFamily.accepts_of_isApprox, CodeFamily.not_accepts_of_lt).
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.QuadraticVerifier.Tables.codeFamily_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.code_gap (p : ℕ) [hp : Fact p.Prime] (F : Type) [Field F] [Fintype F]
[DecidableEq F] [Algebra (ZMod p) F] (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1)
(V : QuadraticVerifier p) :
Nonempty (CodeGap F ε V.Language (V.S + 1) (sizeExp p (1 - ε))) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.