A base with
ProvedLatticePrepro.exists_basecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
For all natural numbers and there is an integer such that
In the size–gap tradeoff of Theorem 4.8, the explicit moment representation has moment parameter , where is chosen with for the number of evaluation tables and the gap (the paper takes the least such ). The lower bound gives the hypothesis of Theorem 4.6, and the upper bound controls the number of columns of the resulting linear system.
Formalization Note: All quantities are natural numbers; the lemma only asserts the existence of such a .
Preamble
import Mathlib
Formal statement
theorem LatticePrepro.exists_base {Y m : ℕ} (hm : 1 ≤ m) (hY : 1 ≤ Y) :
∃ B : ℕ, 2 ≤ B ∧ Y ≤ B ^ m ∧ B ^ m ≤ 2 ^ m * Y := 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 4.8 (\label{thm:quantitative-affine-gap}); Lean: LatticePrepro/Basic/Nat.lean, LatticePrepro.exists_base