Soundness setup — a light constrained table has a short dependence among its Hankel columns
ProvedLatticePrepro.ExplicitTables.soundness_setupFix a field setup: a sample field with elements and an extension of degree , of characteristic . Let and be integers, let , assume , and let . Let be an evaluation table that satisfies all the constraints of Construction A.4 (low-degree, index-consistency and Frobenius) and has weight
Then there is a natural number with
and there are , not all zero, with
That is, the first columns of the Hankel matrix of the moments of are linearly dependent over .
This packages Lemma A.6 with the counting in the soundness part of the proof of Theorem A.8, where is the rank of the moment Hankel matrix and the paper shows for . Its conclusion is the hypothesis of the Hankel reconstruction Theorem A.7, which then yields a coefficient function with at most support points.
Formalization Note: "Satisfies all the constraints" is constraintFun FS m B y = 0, and is Mathlib's hammingNorm (the number of nonzero entries). The hypothesis is implied by the paper's choice . The weight condition is the soundness threshold of Definition 4.4 with and blocks.
import Mathlib
import Definitions.Def_LatticePrepro_Basic_Blocks
import Definitions.Def_LatticePrepro_Moments_Basic
import Definitions.Def_LatticePrepro_Moments_Representation
import Definitions.Def_LatticePrepro_Tables_Digits
import Definitions.Def_LatticePrepro_Tables_FieldSetup
import Definitions.Def_LatticePrepro_Tables_Construction
import Definitions.Def_LatticePrepro_Tables_TableSoundness
open LatticePrepro
open Polynomial Matrix
open LatticePrepro.ExplicitTables
variable {p : ℕ} [Fact p.Prime] {d δ : ℕ} (FS : FieldSetup p d δ) (m B : ℕ)
variable {FS m B}theorem LatticePrepro.ExplicitTables.soundness_setup (hB : 2 ≤ B) (hm : 1 ≤ m)
(hΔ : 4 * degBound p m B δ < Fintype.card FS.𝕊) {y : Coord FS m → ZMod p}
(hy : constraintFun FS m B y = 0) (hw : 2 * hammingNorm y < B ^ m * Fintype.card FS.𝕊) :
∃ t : ℕ, t < B ^ m ∧ Fintype.card FS.𝕊 * t ≤ 2 * hammingNorm y ∧
∃ c : Fin (t + 1) → FS.K, c ≠ 0 ∧
∀ i : Fin (hLen p m B), ∑ j, c j * mom FS m B y (i.val + j.val) = 0 := by sorry