Lemma 4.7 (pointwise form) — recovering a valid Boolean assignment at a support point
ProvedLatticePrepro.FixedSystem.recoverLet 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 coordinates and gate coefficients , and let be an encoding tuple, with linearly independent over . Let () and satisfy:
- and for all ;
- the encoding identities in , for every ;
- the gate identities in , for every gate ;
- .
Then there is an assignment with and for all , which is valid, i.e. for every gate , and which encodes :
In the paper, Lemma 4.7 is stated for functions on a finite set of points. This is its pointwise version at a single point , with . In the soundness part of Theorem 4.6 it is applied at a point where the main coefficient function is nonzero, which yields an accepting computation.
Formalization Note The Lean statement assumes , whereas the paper derives from any nonzero . It concludes existence of but not its uniqueness, and it does not record the paper's identity . Because , sums over may start at . "Boolean with " is IsBooleanAssignment and validity is IsValid.
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.recover {Fv : Fin (V.S + 1) → Fin (V.S + 1) → ZMod p}
(hsymm : ∀ i j, Fv i j = Fv j i) (hdiag : ∀ i, Fv i i = Fv i 0) {α : Ω}
(henc : ∀ j, α * algebraMap (ZMod p) Ω (Fv 0 j) =
∑ i, algebraMap K Ω (ε.E i) * algebraMap (ZMod p) Ω (Fv i j))
(hgate : ∀ b, ∑ i, ∑ j, V.coeff b i j * Fv i j = 0) (hne : Fv 0 0 ≠ 0) :
∃ z : Fin (V.S + 1) → ZMod p, V.IsBooleanAssignment z ∧ V.IsValid z ∧
algebraMap K Ω (ε.enc z) = α := by sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.