Theorem 4.6 (soundness, weight form) — a solution below the weight threshold certifies membership
ProvedLatticePrepro.FixedSystem.mem_language_of_solvesLet be a prime, a field that is an -algebra, and an extension field of . Elements of and are viewed in through the algebra maps. Consider the fixed-verifier system of Construction 4.5 for a quadratic verifier with language , a moment representation over (moment parameter , blocks per evaluation table, coefficient functions on ), and an encoding tuple. Let and let satisfy all equations of the system for . If
then . Here is the Hamming weight.
This is the core of the soundness part of Theorem 4.6. The paper's proof assumes a solution of weight below (in its notation ) and exhibits an accepting computation on . Theorem 4.6 follows: if for the number of tables, then every solution of weight at most is below the threshold.
Formalization Note " satisfies the equations" is the predicate Solves V R ε x v, which is equivalent to for the linear map of fixedSystem. is R.numBlocks, the number of blocks of a single table, not of the whole system.
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Reduction_LinearSystem
import Definitions.Def_LatticePrepro_Moments_Basic
import Definitions.Def_LatticePrepro_Moments_Representation
import Definitions.Def_LatticePrepro_Verifier_Quadratic
import Definitions.Def_LatticePrepro_Reduction_FixedSystem
open LatticePrepro
open Finsupp
open LatticePrepro.FixedSystem
variable {p : ℕ} [Fact p.Prime] {K : Type} [Field K] [Algebra (ZMod p) K]
{Ω : Type} [Field Ω] [Algebra (ZMod p) Ω] [Algebra K Ω] [IsScalarTower (ZMod p) K Ω]
(V : QuadraticVerifier p) (R : MomentRepresentation p K Ω) (ε : EncodingTuple p K V.S)theorem LatticePrepro.FixedSystem.mem_language_of_solves {x : Fin V.n → Bool} {v : Col V R → ZMod p}
(hv : Solves V R ε x v) (hw : 2 * hammingNorm v < R.r * R.numBlocks) : x ∈ V.Language := by sorry