Theorem A.7 — moment reconstruction from a Hankel matrix with Frobenius identities
ProvedLatticePrepro.hankel_reconstructionLet be a prime and let be an algebraically closed field that is an -algebra (so of characteristic ). Let be an integer and . Let be a sequence in satisfying the Frobenius identities
Let , and suppose that the first columns of the Hankel matrix are linearly dependent over : there are , not all zero, with
Then there is a finitely supported coefficient function with and
This is the reconstruction step behind the soundness of the explicit tables. In Theorem A.8 it is applied to the moments 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 in a finite field , assumes , and obtains on some finite extension of . The Lean version works directly in a fixed algebraically closed field (later Mathlib's AlgebraicClosure K) and only assumes that the first Hankel columns are dependent, which follows from rank since ; it is therefore a slight generalization. The sequence is a function ℕ → Ω, of which only matter. Coefficient functions are Ω →₀ ZMod p, and uses the convention .
import Mathlib import Definitions.Def_LatticePrepro_Moments_Basic import Definitions.Def_LatticePrepro_Tables_Hankel open LatticePrepro open Polynomial
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 sorryConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.