Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Moment representations (Definition 4.4)

Definition
LatticePrepro_Moments_Representation

by WizardOfMenlo · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

Fix a prime ppp, a field KKK that is an Fp\mathbb{F}_pFp​-algebra (the moment field), and a field Ω\OmegaΩ extending KKK, with compatible Fp\mathbb{F}_pFp​-algebra structures; coefficient functions live on Ω\OmegaΩ. A moment representation over KKK (MomentRepresentation p K Ω) consists of:

  1. a moment parameter r≥2r \ge 2r≥2;
  2. a finite set ι\iotaι of table coordinates, a finite set β\betaβ of blocks, and a map blk ⁣:ι→β\mathrm{blk}\colon \iota \to \betablk:ι→β such that every block contains the same number bbb of coordinates (the block size); D=∣β∣D = |\beta|D=∣β∣ is the number of blocks (numBlocks), and vectors y∈Fpιy \in \mathbb{F}_p^{\iota}y∈Fpι​ are evaluation tables;
  3. an Fp\mathbb{F}_pFp​-linear map C ⁣:Fpι→W\mathcal C\colon \mathbb{F}_p^{\iota} \to WC:Fpι​→W into some Fp\mathbb{F}_pFp​-vector space WWW; the equations C(y)=0\mathcal C(y) = 0C(y)=0 are the evaluation table constraints;
  4. Fp\mathbb{F}_pFp​-linear moment maps M^k ⁣:Fpι→K\hat M_k\colon \mathbb{F}_p^{\iota} \to KM^k​:Fpι​→K for the orders 0≤k≤2r−20 \le k \le 2r - 20≤k≤2r−2;

subject to:

  • Completeness. For every α∈K\alpha \in Kα∈K there is a binary table y∈{0,1}ιy \in \{0,1\}^{\iota}y∈{0,1}ι with exactly one nonzero coordinate in each block, C(y)=0\mathcal C(y) = 0C(y)=0, and M^k(y)=αk\hat M_k(y) = \alpha^kM^k​(y)=αk for 0≤k≤2r−20 \le k \le 2r - 20≤k≤2r−2.
  • Soundness. For every y∈Fpιy \in \mathbb{F}_p^{\iota}y∈Fpι​ with C(y)=0\mathcal C(y) = 0C(y)=0 and 2wt⁡(y)<r⋅D2\operatorname{wt}(y) < r \cdot D2wt(y)<r⋅D, where wt⁡\operatorname{wt}wt is the Hamming weight, there is a finitely supported coefficient function f ⁣:Ω→Fpf\colon \Omega \to \mathbb{F}_pf:Ω→Fp​ with
M^k(y)=Mk(f)(0≤k≤2r−2),D⋅∣supp⁡f∣≤2wt⁡(y),\hat M_k(y) = \mathcal M_k(f) \quad (0 \le k \le 2r-2), \qquad D \cdot |\operatorname{supp} f| \le 2 \operatorname{wt}(y),M^k​(y)=Mk​(f)(0≤k≤2r−2),D⋅∣suppf∣≤2wt(y),

where M^k(y)∈K\hat M_k(y) \in KM^k​(y)∈K is viewed in Ω\OmegaΩ.

The bundle also defines the type of moment orders {0,…,2r−2}\{0, \dots, 2r-2\}{0,…,2r−2} (Order) and the order maps k↦kk \mapsto kk↦k and k↦k+1k \mapsto k+1k↦k+1 for k<rk < rk<r (low, lowSucc), and j↦jj \mapsto jj↦j for j<kj < kj<k (below), which index the equations of Construction 4.5.

Construction 4.5 and Theorem 4.6 work with an arbitrary moment representation; the polynomial evaluation tables of Appendix A (Construction A.4, Theorem A.8) provide a concrete one.

Formalization Note: Compared with Definition 4.4: the coefficient functions of the soundness property live on one fixed extension field Ω\OmegaΩ (in the explicit construction an algebraic closure) rather than on a finite extension depending on yyy; the constraints are an arbitrary linear map rather than a matrix; the partition is a map ι→β\iota \to \betaι→β whose fibers all have size blockSize; KKK is not required to be finite; the structure requires r≥2r \ge 2r≥2 (as Construction 4.5 does) instead of r≥1r \ge 1r≥1; and the weight threshold wt⁡(y)<rD/2\operatorname{wt}(y) < rD/2wt(y)<rD/2 and the bound ∣supp⁡f∣≤2wt⁡(y)/D|\operatorname{supp} f| \le 2\operatorname{wt}(y)/D∣suppf∣≤2wt(y)/D are stated without division. Orders are Fin (2 * r - 1). The simp lemmas low_val, lowSucc_val and below_val give the values of the order maps.

Definition code
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Moments_Basic

/-!
# Moment representations (Definition 4.4)

A *moment representation* over a field `K` of characteristic `p` consists of evaluation tables
`y : ι → 𝔽_p` (with coordinates partitioned into blocks of equal size), linear *evaluation table
constraints* `constraint y = 0`, and `𝔽_p`-linear *moment maps* `momentMap k : (ι → 𝔽_p) →ₗ K`
for the orders `k : Fin (2r - 1)`, i.e. `0 ≤ k ≤ 2r - 2`, such that

* **completeness**: every `α : K` has a binary table with exactly one `1` per block, satisfying
  the constraints, whose moments are `α ^ k`;
* **soundness**: every table satisfying the constraints with weight below the threshold
  `r · D / 2` (where `D` is the number of blocks) represents a coefficient function
  `f : Ω →₀ 𝔽_p` on an extension field `Ω` of `K`, with `|supp f| ≤ 2 · wt(y) / D`.

We fix a single extension field `Ω` of `K` once and for all (in the explicit construction,
an algebraic closure); this avoids embedding several finite extensions into a common one.
-/

namespace LatticePrepro

/-- A moment representation over `K` (Definition 4.4), with represented coefficient functions
living on the extension field `Ω`. -/
structure MomentRepresentation (p : ℕ) [Fact p.Prime] (K : Type) [Field K] [Algebra (ZMod p) K]
    (Ω : Type) [Field Ω] [Algebra (ZMod p) Ω] [Algebra K Ω] [IsScalarTower (ZMod p) K Ω] where
  /-- The moment parameter `r`. -/
  r : ℕ
  two_le_r : 2 ≤ r
  /-- Coordinates of an evaluation table. -/
  ι : Type
  [fintypeι : Fintype ι]
  [decEqι : DecidableEq ι]
  /-- Blocks. -/
  β : Type
  [fintypeβ : Fintype β]
  [decEqβ : DecidableEq β]
  /-- The partition of the coordinates into blocks. -/
  blk : ι → β
  /-- The block size. -/
  blockSize : ℕ
  card_fiber : ∀ s : β, (Finset.univ.filter fun i => blk i = s).card = blockSize
  /-- Codomain of the evaluation table constraints. -/
  W : Type
  [addCommGroupW : AddCommGroup W]
  [moduleW : Module (ZMod p) W]
  /-- The evaluation table constraints `constraint y = 0`. -/
  constraint : (ι → ZMod p) →ₗ[ZMod p] W
  /-- The moment maps `M̂_k` for the orders `0 ≤ k ≤ 2r - 2`. -/
  momentMap : Fin (2 * r - 1) → (ι → ZMod p) →ₗ[ZMod p] K
  /-- Completeness: every field element has a block-unit table. -/
  complete : ∀ α : K, ∃ y : ι → ZMod p, IsBinary y ∧ ExactlyOnePerBlock blk y ∧
    constraint y = 0 ∧ ∀ k, momentMap k y = α ^ (k : ℕ)
  /-- Soundness: light tables represent sparse coefficient functions over `Ω`. -/
  sound : ∀ y : ι → ZMod p, constraint y = 0 → 2 * hammingNorm y < r * Fintype.card β →
    ∃ f : Ω →₀ ZMod p, (∀ k, algebraMap K Ω (momentMap k y) = moment f k) ∧
      Fintype.card β * f.support.card ≤ 2 * hammingNorm y

namespace MomentRepresentation

variable {p : ℕ} [Fact p.Prime] {K : Type} [Field K] [Algebra (ZMod p) K]
    {Ω : Type} [Field Ω] [Algebra (ZMod p) Ω] [Algebra K Ω] [IsScalarTower (ZMod p) K Ω]

attribute [instance] fintypeι decEqι fintypeβ decEqβ addCommGroupW moduleW

variable (R : MomentRepresentation p K Ω)

/-- The number of blocks `D`. -/
abbrev numBlocks : ℕ := Fintype.card R.β

/-! ### Moment orders -/

/-- The moment orders `0 ≤ k ≤ 2r - 2` carried by the representation. -/
abbrev Order : Type := Fin (2 * R.r - 1)

/-- An order `k < r` as a moment order (`r ≤ 2r - 2`). -/
def low (k : Fin R.r) : R.Order := ⟨k, by have := R.two_le_r; have := k.isLt; omega⟩

@[simp] lemma low_val (k : Fin R.r) : (R.low k : ℕ) = k := rfl

/-- The order `k + 1` for `k < r`, as a moment order (`k + 1 ≤ r ≤ 2r - 2`). -/
def lowSucc (k : Fin R.r) : R.Order := ⟨k + 1, by have := R.two_le_r; have := k.isLt; omega⟩

@[simp] lemma lowSucc_val (k : Fin R.r) : (R.lowSucc k : ℕ) = k + 1 := rfl

/-- The orders below a moment order `k`, as moment orders. -/
def below (k : R.Order) (j : Fin k) : R.Order := Fin.castLE k.isLt.le j

@[simp] lemma below_val (k : R.Order) (j : Fin k) : (R.below k j : ℕ) = j := rfl

end MomentRepresentation

end LatticePrepro
Source
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), Definition 4.4 (\label{def:moment-representation}); Lean: LatticePrepro/Moments/Representation.lean, LatticePrepro.MomentRepresentation

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me