Pointwise translation identity for light solutions (soundness of Theorem 4.6)
ProvedLatticePrepro.FixedSystem.translation_pointwiseLet 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 (instance length , coordinates), a moment representation over (moment parameter , moment maps ) and an encoding tuple . Let . Let and let satisfy all equations of the system for . Suppose that every table has a finitely supported coefficient function such that
- in , for every table and every ;
- .
Write for the function of the main table and for that of the auxiliary table , . Then for every ,
This is the translation identity (19) of the paper. The soundness proof of Theorem 4.6 shows that it holds pointwise for solutions below the weight threshold. Summing it over the coset then gives on that coset.
Formalization Note Lean writes the identity as "left-hand side minus Finsupp.single θ_x 1 evaluated at equals ". The functions are Ω →₀ ZMod p indexed by TblIdx, and is the function at index rep 0 0. The support hypothesis sums over all tables, product and auxiliary. The moment hypothesis is stated after mapping into .
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)
variable {x : Fin V.n → Bool} {v : Col V R → ZMod p} (hv : Solves V R ε x v)
(f : V.TblIdx → Ω →₀ ZMod p)
(hf : ∀ T (k : R.Order), algebraMap K Ω (R.momentMap k (tbl V R v T)) = moment (f T) k)
(hN : ∑ T, (f T).support.card < R.r)
include hv hf hNtheorem LatticePrepro.FixedSystem.translation_pointwise (α : Ω) :
algebraMap (ZMod p) Ω (f (Sum.inl (V.rep 0 0)) α) -
∑ i : V.AuxIdx, (algebraMap (ZMod p) Ω (f (Sum.inr i) (α - algebraMap K Ω (ε.E i.1))) -
algebraMap (ZMod p) Ω (f (Sum.inr i) α)) -
Finsupp.single (algebraMap K Ω (V.instanceEnc ε x)) (1 : Ω) α = 0 := by sorry