Degree bound for products of element polynomials
ProvedLatticePrepro.ExplicitTables.natDegree_elemProd_lecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a prime and fix a field setup with sample field and extension of degree (every element of is with , ). Let be natural numbers, , and let be the element polynomials of , so that and . If satisfies for every , i.e. lies in the index set , then
This is the estimate in the completeness part of the proof of Theorem A.8. Since the interpolants of the element table are exactly these products, it shows that element tables satisfy the low-degree constraints of Construction A.4.
Formalization Note: The degree is Mathlib's natDegree (the zero polynomial has degree ). No hypotheses on , or are needed.
Preamble
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_ElementTable
open LatticePrepro
open Polynomial
open LatticePrepro.ExplicitTables
variable {p : ℕ} [Fact p.Prime] {d δ : ℕ} (FS : FieldSetup p d δ) (m B : ℕ)
variable {FS m B}Formal statement
theorem LatticePrepro.ExplicitTables.natDegree_elemProd_le (α : FS.K) {η : Fin m → ℕ} (hη : ∀ h, η h ≤ 2 * p * (B - 1)) :
(elemProd FS m B α η).natDegree ≤ degBound p m B δ := by sorrySource
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); auxiliary lemma used in the proof of Theorem A.8 (\label{thm:moment-representation-construction}); Lean: LatticePrepro/Tables/ElementTable.lean, LatticePrepro.ExplicitTables.natDegree_elemProd_le