Choice of the gap and size exponents for Theorem 5.1
ProvedLatticePrepro.params_speccoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be a natural number and a real number with . Set
These are momentAxes δ, prefactorExp p m, gapExp p δ and sizeExp p δ. Let and be integers with
Then
This is the parameter bookkeeping in the proof of Theorem 5.1. There, is the number of columns of the system given by Theorem 4.8 with moment axes and gap , so the hypothesis is exactly the size bound of Theorem 4.8. The code or lattice dimension satisfies , so the conclusions give the gap requirement (compare (25)) and the dimension bound . Here plays the role of the paper's exponent , and the constants are explicit.
Formalization Note The ceilings are Nat.ceil. is a real power (Real.rpow), and is cast from to in the first conclusion. The lemma does not require to be prime.
Preamble
import Mathlib import Definitions.Def_LatticePrepro_Basic_Blocks import Definitions.Def_LatticePrepro_Reduction_LinearSystem import Definitions.Def_LatticePrepro_Conversions_Codes import Definitions.Def_LatticePrepro_Conversions_ConstructionA import Definitions.Def_LatticePrepro_Conversions_Hadamard import Definitions.Def_LatticePrepro_Conversions_Lattices import Definitions.Def_LatticePrepro_Lattices_Distance import Definitions.Def_LatticePrepro_Lattices_Mathlib import Definitions.Def_LatticePrepro_Moments_Basic import Definitions.Def_LatticePrepro_Moments_Representation import Definitions.Def_LatticePrepro_Verifier_Quadratic import Definitions.Def_LatticePrepro_Reduction_FixedSystem import Definitions.Def_LatticePrepro_Tables_Digits import Definitions.Def_LatticePrepro_Tables_FieldSetup import Definitions.Def_LatticePrepro_Tables_Hankel import Definitions.Def_LatticePrepro_Tables_Construction import Definitions.Def_LatticePrepro_Tables_ElementTable import Definitions.Def_LatticePrepro_Tables_TableSoundness import Definitions.Def_LatticePrepro_Tables_Explicit import Definitions.Def_LatticePrepro_Main open LatticePrepro
Formal statement
theorem LatticePrepro.params_spec (p : ℕ) {δ : ℝ} (hδ0 : 0 ≤ δ) (hδ1 : δ < 1) (S n : ℕ) (hS : 1 ≤ S)
(hn : 1 ≤ n)
(hbound : n ^ momentAxes δ ≤ (8 * p ^ 4 * momentAxes δ * (S + 1)) ^
((momentAxes δ + 7) * momentAxes δ) * ((S + 1) ^ gapExp p δ) ^ (momentAxes δ + 1)) :
64 * (n : ℝ) ^ δ ≤ ((S + 1) ^ gapExp p δ : ℕ) ∧ 4 * n ≤ (S + 1) ^ sizeExp p δ := 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 5.1 (\label{thm:approximation-hardness}), choice of parameters and inequality (25) (\label{eq:final-gap-requirement}); Lean: LatticePrepro/Main.lean, LatticePrepro.params_spec