Theorem 4.8 — size and gap of the fixed linear system
ProvedLatticePrepro.exists_gapReductionLet be a prime, let be a quadratic verifier over with instance length , assignment coordinates and language , and let and be integers. Then there is a linear system family over , consisting of a fixed -linear map on , a right-hand side for every , and a partition of the columns into blocks of size , with the following properties.
- Completeness. For every , the system has a solution with at most one nonzero coordinate in each block.
- Soundness. For every , every solution of has Hamming weight .
- Block structure. , the block size is a power of ( for some ), and .
- Size. The number of columns satisfies
This is Theorem 4.8 of the paper without its running-time claims. Items 1 and 2 say that reduces to -BSLSP (Definition 3.10). Item 4 is the bound (22), , raised to the -th power. In the paper's notation, are . The theorem feeds the code and lattice conversions in the proof of Theorem 5.1 (code_gap, lattice_gap).
Formalization Note The conclusion is Nonempty (GapReduction p V g m), a structure bundling the system with the properties above. The verifier is an abstract QuadraticVerifier: a system of quadratic gate equations over with a designated input prefix and output coordinate. Claim 3.15 produces one from a Boolean circuit. The size bound is kept in integer form. The paper's statement also includes the time bounds and the uniform size bound (24) for a choice of depending on and ; these are not part of the Lean statement. The facts that is a power of and are extra conclusions that the paper's statement does not list explicitly.
Note (existence form). This statement asserts only that some linear system family has these properties. The statement for the object that the paper constructs is LatticePrepro.QuadraticVerifier.Tables.system_spec.
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.exists_gapReduction (p : ℕ) [hp : Fact p.Prime] (V : QuadraticVerifier p) (g m : ℕ)
(hg : 1 ≤ g) (hm : 1 ≤ m) : Nonempty (GapReduction p V g m) := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.