Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Coefficient functions and their moments (Definitions 4.1–4.2)

Definition
LatticePrepro_Moments_Basic

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

Let FFF be a commutative ring and Ω\OmegaΩ a commutative FFF-algebra. In the paper, F=FpF = \mathbb{F}_pF=Fp​ is the prime field and Ω\OmegaΩ is an extension field of the moment field.

  • Coefficient functions (Definition 4.1) are finitely supported functions f ⁣:Ω→Ff\colon \Omega \to Ff:Ω→F; the support supp⁡f={α∈Ω:f(α)≠0}\operatorname{supp} f = \{\alpha \in \Omega : f(\alpha) \ne 0\}suppf={α∈Ω:f(α)=0} is finite.
  • Moments (moment, Definition 4.2). For an integer k≥0k \ge 0k≥0, the kkk-th moment of fff is
Mk(f)=∑α∈supp⁡ff(α)⋅αk ∈Ω,\mathcal M_k(f) = \sum_{\alpha \in \operatorname{supp} f} f(\alpha)\cdot \alpha^k \ \in \Omega,Mk​(f)=α∈suppf∑​f(α)⋅αk ∈Ω,

where f(α)⋅αkf(\alpha)\cdot\alpha^kf(α)⋅αk is the scalar multiplication of FFF on Ω\OmegaΩ, with the convention 00=10^0 = 100=1.

The bundle also records two evaluation rules: the zero function has all moments 000, and the function equal to ccc at a single point α\alphaα and 000 elsewhere has Mk=c⋅αk\mathcal M_k = c \cdot \alpha^kMk​=c⋅αk. In particular the indicator 1α\mathbf{1}_\alpha1α​ has moments αk\alpha^kαk, as noted after Definition 4.2.

Moments connect evaluation tables to field elements. A moment representation (Definition 4.4) requires the moment maps of light evaluation tables to agree with the moments of sparse coefficient functions, and the soundness proof of Theorem 4.6 recovers an accepting assignment from coefficient functions through their moments.

Formalization Note: Coefficient functions are Mathlib's finitely supported functions Ω →₀ F, and moment f k is f.sum (fun α c => c • α ^ k). In the paper coefficient functions live on varying finite extensions; the formalization uses one fixed extension field Ω\OmegaΩ throughout. The simp lemmas moment_zero and moment_single are included in the bundle.

Definition code
import Mathlib

/-!
# Coefficient functions and moments

A *coefficient function* (Definition 4.1 of the paper) is a finitely supported function from a
field `Ω` to a coefficient ring `F` (in the paper, the prime field `𝔽_p`). We model it as a
`Finsupp` `Ω →₀ F`. Its `k`-th moment (Definition 4.2) is `∑ α, f α • α ^ k ∈ Ω`.

The main facts proved here are:
* `moment` is `F`-linear (`momentₗ`);
* the Vandermonde identification lemma (Lemma 4.3): a function supported on at most `t` points
  whose first `t` moments vanish is zero;
* the binomial identity for the moments of a translation difference (equation (20)).
-/

namespace LatticePrepro

open Finsupp

section Moment

variable {F Ω : Type*} [CommRing F] [CommRing Ω] [Algebra F Ω]

/-- The `k`-th moment `∑ α, f α • α ^ k` of a finitely supported `f : Ω →₀ F`
(Definition 4.2; with the convention `0 ^ 0 = 1`). -/
noncomputable def moment (f : Ω →₀ F) (k : ℕ) : Ω :=
  f.sum fun α c => c • α ^ k

@[simp] lemma moment_zero (k : ℕ) : moment (0 : Ω →₀ F) k = 0 := by
  simp [moment]

@[simp] lemma moment_single (α : Ω) (c : F) (k : ℕ) :
    moment (single α c) k = c • α ^ k := by
  simp [moment, sum_single_index]

end Moment

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), Definitions 4.1–4.2 (\label{def:coefficient-functions}, \label{def:coefficient-moments}); Lean: LatticePrepro/Moments/Basic.lean, LatticePrepro.moment

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