Theorem 4.8 for the fixed linear system of Construction 4.5 — gap reduction and size bound
ProvedLatticePrepro.QuadraticVerifier.Tables.system_specLet be a prime and let be a quadratic verifier over with instance length , assignment coordinates, evaluation tables and language . For a gap exponent put (momentAxes) and with = gapExp p δ. Tables for and consist of an integer with and an explicit moment representation in the sense of Theorem A.8 with axes and representation bound . They do not depend on the instance.
The fixed linear system of the tables is the system of Construction 4.5 built from them: is a fixed -linear map on whose columns are partitioned into blocks of size , and the right-hand side , for , is zero except for the entries of the translation equations, where is the encoding of the instance.
Statement. Let and let be tables for and . Then the fixed linear system of satisfies:
- 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 more than .
- and .
- Size. .
This is Theorem 4.8 for the system the paper constructs. The existence form (exists_gapReduction) asserts that some linear system family has these properties; here the system is the one of Construction 4.5, and the statement holds for every choice of tables.
Formalization Note. Items 1 and 2 are IsGapReduction. The size bound is the bound (22) raised to the -th power. The running-time claims of Theorem 4.8 are not formalized.
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.system_spec (T : V.Tables δ) (hδ1 : δ < 1) :
T.system.IsGapReduction V.Language ((V.S + 1) ^ gapExp p δ) ∧
(V.S + 1) ^ gapExp p δ < T.system.blockSize ∧ 0 < T.system.numBlocks ∧
Fintype.card T.system.ι ^ momentAxes δ ≤
(8 * p ^ 4 * momentAxes δ * (V.S + 1)) ^ ((momentAxes δ + 7) * momentAxes δ) *
((V.S + 1) ^ gapExp p δ) ^ (momentAxes δ + 1) := by sorry