Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.7 — moment reconstruction from a Hankel matrix with Frobenius identities

Proved
LatticePrepro.hankel_reconstruction

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

coding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing

Let ppp be a prime and let Ω\OmegaΩ be an algebraically closed field that is an Fp\mathbb{F}_pFp​-algebra (so of characteristic ppp). Let r≥2r\ge2r≥2 be an integer and ℓ=p(r−1)+1\ell=p(r-1)+1ℓ=p(r−1)+1. Let (yk)k≥0(y_k)_{k\ge0}(yk​)k≥0​ be a sequence in Ω\OmegaΩ satisfying the Frobenius identities

ypk=yk pwhenever pk≤2ℓ−2.y_{pk}=y_k^{\,p}\qquad\text{whenever } pk\le2\ell-2 .ypk​=ykp​whenever pk≤2ℓ−2.

Let t<rt<rt<r, and suppose that the first t+1t+1t+1 columns of the Hankel matrix (yi+j)0≤i,j<ℓ(y_{i+j})_{0\le i,j<\ell}(yi+j​)0≤i,j<ℓ​ are linearly dependent over Ω\OmegaΩ: there are c0,…,ct∈Ωc_0,\dots,c_t\in\Omegac0​,…,ct​∈Ω, not all zero, with

∑j=0tcj yi+j=0(0≤i<ℓ).\sum_{j=0}^{t}c_j\,y_{i+j}=0\qquad(0\le i<\ell).j=0∑t​cj​yi+j​=0(0≤i<ℓ).

Then there is a finitely supported coefficient function f ⁣:Ω→Fpf\colon\Omega\to\mathbb{F}_pf:Ω→Fp​ with ∣supp f∣≤t|\mathrm{supp}\,f|\le t∣suppf∣≤t and

yk=μk(f)=∑α∈Ωf(α) αk(0≤k<ℓ).y_k=\mu_k(f)=\sum_{\alpha\in\Omega}f(\alpha)\,\alpha^k\qquad(0\le k<\ell).yk​=μk​(f)=α∈Ω∑​f(α)αk(0≤k<ℓ).

This is the reconstruction step behind the soundness of the explicit tables. In Theorem A.8 it is applied to the moments yk=μ^k(y)y_k=\hat\mu_k(y)yk​=μ^​k​(y) of a light evaluation table satisfying the constraints, whose Hankel matrix has small rank by Lemma A.6, and shows that the table represents a sparse coefficient function.

Formalization Note: The paper takes the yky_kyk​ in a finite field KKK, assumes rank⁡K(yi+j)i,j<ℓ=t<r\operatorname{rank}_K(y_{i+j})_{i,j<\ell}=t<rrankK​(yi+j​)i,j<ℓ​=t<r, and obtains fff on some finite extension of KKK. The Lean version works directly in a fixed algebraically closed field Ω\OmegaΩ (later Mathlib's AlgebraicClosure K) and only assumes that the first t+1t+1t+1 Hankel columns are dependent, which follows from rank ≤t\le t≤t since t+1≤ℓt+1\le\ellt+1≤ℓ; it is therefore a slight generalization. The sequence is a function ℕ → Ω, of which only y0,…,y2ℓ−2y_0,\dots,y_{2\ell-2}y0​,…,y2ℓ−2​ matter. Coefficient functions are Ω →₀ ZMod p, and μk\mu_kμk​ uses the convention 00=10^0=100=1.

Preamble
import Mathlib
import Definitions.Def_LatticePrepro_Moments_Basic
import Definitions.Def_LatticePrepro_Tables_Hankel

open LatticePrepro
open Polynomial
Formal statement
theorem LatticePrepro.hankel_reconstruction {p : ℕ} [hp : Fact p.Prime] {Ω : Type} [Field Ω]
    [Algebra (ZMod p) Ω] [IsAlgClosed Ω] {r : ℕ} (hr : 2 ≤ r) (y : ℕ → Ω)
    (hfrob : ∀ k, p * k ≤ 2 * hankelLen p r - 2 → y (p * k) = y k ^ p)
    {t : ℕ} (ht : t < r)
    (hdep : ∃ c : Fin (t + 1) → Ω, c ≠ 0 ∧
      ∀ i : Fin (hankelLen p r), ∑ j, c j * y (i.val + j.val) = 0) :
    ∃ f : Ω →₀ ZMod p, f.support.card ≤ t ∧ ∀ k < hankelLen p r, y k = moment f k := by sorry
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), Theorem A.7 (\label{thm:moment-hankel-reconstruction}); Lean: LatticePrepro/Tables/Hankel.lean, LatticePrepro.hankel_reconstruction
Human review
  • Endorsed by Shuze Chen · Nov 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by WizardOfMenlo · Nov 15, 2026

    Confirmed by the mission captain (proposal self-audit).

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