Hankel length of the explicit tables, (Construction A.4, Definition A.5)
DefinitionLatticePrepro_Tables_TableSoundnesscoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
For natural numbers , hLen p m B is
the Hankel length for the moment parameter . In Construction A.4, is the characteristic, the number of axes and the base. Then is the size of the polynomial matrix of an evaluation table (Definition A.5), and of the Hankel matrix of its moments.
Since , Claim A.2 with places in the index set , and is the largest moment order constrained by the tables.
Formalization Note: hLen p m B coincides with hankelLen p (B ^ m) from the Hankel reconstruction module. The polynomial matrix itself, and the matrix used to analyse it, are defined in the source module but are not part of this bundle. The paper writes for .
Definition code
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
/-!
# Soundness of the explicit tables: the polynomial matrix (Definition A.5, Lemma A.6)
For a table `y` satisfying the constraints, the *polynomial matrix* `Hmat y` has entries
`P^y_{digits(h) + digits(h')} ∈ 𝕊[X]` (`0 ≤ h, h' < ℓ`, `ℓ = p (B^m - 1) + 1`). We show:
* its entries have degree `≤ Δ` (low-degree constraints);
* `Hmat y (s) = E · diag(y(·, s)) · Eᵀ`, so `∑_s rank Hmat y (s) ≤ wt(y)`;
* `Hmat y (γ)` is the Hankel matrix `(M̂_{h+h'}(y))` (index-consistency constraints);
* hence, by `card_mul_rank_eval_le`, the Hankel matrix has rank `ρ` with `(q - Δ) ρ ≤ wt(y)`,
and its first `ρ + 1` columns are linearly dependent.
-/
namespace LatticePrepro
open Polynomial Matrix
namespace ExplicitTables
variable {p : ℕ} [Fact p.Prime] {d δ : ℕ} (FS : FieldSetup p d δ) (m B : ℕ)
/-- The Hankel length `ℓ = p (B^m - 1) + 1` (this is `hankelLen p (B^m)`). -/
def hLen (p m B : ℕ) : ℕ := p * (B ^ m - 1) + 1
variable {FS m B}
end ExplicitTables
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), Construction A.4, step 2 (\label{step:moment-parameters}) and Definition A.5 (\label{def:table-matrix}); Lean: LatticePrepro/Tables/TableSoundness.lean, LatticePrepro.ExplicitTables.hLen