Weight of a fixed-system vector is the sum of the weights of its tables
ProvedLatticePrepro.FixedSystem.hammingNorm_eq_sum_tblcoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Consider the fixed-verifier system of Construction 4.5 for a quadratic verifier over ( prime) and a moment representation over a field , with table coordinates . Its columns are the pairs of a table index and a coordinate . For every ,
where is the table with index , and is the Hamming weight (the number of nonzero coordinates).
This bookkeeping identity is used in the soundness part of Theorem 4.6. It bounds the weight of each table by the total weight and lets the per-table support bounds of the moment representation be summed.
Formalization Note The Hamming weight is Mathlib's hammingNorm, and is tbl V R v T.
Preamble
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
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)
open LatticePrepro.FixedSystemFormal statement
theorem LatticePrepro.FixedSystem.hammingNorm_eq_sum_tbl (v : Col V R → ZMod p) :
hammingNorm v = ∑ T, hammingNorm (tbl V R v T) := by sorrySource
G. Fenzi, G. Weissenberg, Nearly Optimal Hardness for CVP and NCP with Preprocessing (STOC 2027 submission #847; IACR ePrint 2026/2634, https://eprint.iacr.org/2026/2634); auxiliary lemma used in the proof of Theorem 4.6 (\label{thm:fixed-verifier-reduction}); Lean: LatticePrepro/Reduction/FixedSystem.lean, LatticePrepro.FixedSystem.hammingNorm_eq_sum_tbl