Theorem 4.6 — the fixed-verifier system is a gap reduction to block-sparse linear systems
ProvedLatticePrepro.FixedSystem.isGapReductionLet be a prime, a field that is an -algebra, and an extension field of . Elements of and are viewed in through the algebra maps. Let:
- be a quadratic verifier over with instance length , assignment coordinates and language ;
- be a moment representation over , with moment parameter , blocks per evaluation table and block size , whose soundness produces coefficient functions on ;
- be an encoding tuple ( linearly independent over ).
Let be the fixed-verifier system of Construction 4.5. It has evaluation tables, blocks of size , and the matrix does not depend on . Let satisfy
Then:
- Completeness. For every there is a binary vector with and at most one nonzero coordinate in each block.
- Soundness. For every , every over with has Hamming weight .
So reduces to the block-sparse linear-system problem with gap (Definition 3.10).
This is Theorem 4.6 of the paper; in its notation, are . Theorem 4.8 applies it with the explicit moment representation of Appendix A.
Formalization Note The conclusion is (fixedSystem V R ε).IsGapReduction V.Language g, where ε is the encoding tuple and is Fintype.card V.TblIdx. The paper also assumes and , which make the target a -BSLSP instance in the sense of Definition 3.10; the Lean statement does not need them. is not required to be finite. The time bound of the paper is not formalized. The verifier is given by quadratic gate equations rather than a Boolean circuit (compare Claim 3.15).
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.isGapReduction {g : ℕ} (hg : 2 * g * Fintype.card V.TblIdx < R.r) :
(fixedSystem V R ε).IsGapReduction V.Language g := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.