A power of in the interval
ProvedLatticePrepro.exists_pow_betweencoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
For all natural numbers and there is an exponent such that
Since consecutive powers of differ by a factor , such a is the least power of that is at least .
Construction A.4 takes the extension degree to be the least power of the prime with ( the number of assignment coordinates), and the sample field size to be the least power of with . The lemma provides these powers together with the upper bounds and , which give the size bound of Theorem A.8.
Formalization Note: The lemma is stated for any natural number , not only primes.
Preamble
import Mathlib
Formal statement
theorem LatticePrepro.exists_pow_between {p N : ℕ} (hp : 2 ≤ p) (hN : 2 ≤ N) :
∃ d, 1 ≤ d ∧ N ≤ p ^ d ∧ p ^ d < p * N := 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 Construction A.4 (\label{con:moment-representation}) and the proof of Theorem A.8 (\label{thm:moment-representation-construction}); Lean: LatticePrepro/Basic/Nat.lean, LatticePrepro.exists_pow_between