Radius bound for (proof of Lemma 3.12, eq. (43))
ProvedLatticePrepro.radius_bound_gt_twocoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let be real numbers with
Then
where is the ceiling, a natural number read in .
This is the real-number estimate behind the weight bound (43) in the proof of Lemma 3.12 for . There , is the padded block size, the number of blocks, the lattice dimension, for the residual (so ), , and is the residual weight. The hypotheses are the Parseval bound of (42) and the power-mean inequality . The conclusion is for the radius , which is the weight bound of Lemma 3.12 with .
Formalization Note. All powers with exponents , , and the outer exponent are real powers (Real.rpow); the ceiling is Nat.ceil.
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 open LatticePrepro
Formal statement
theorem LatticePrepro.radius_bound_gt_two {q t D A B w : ℝ} (hq : 2 < q) (ht : 1 ≤ t) (hD : 1 ≤ D)
(hB : 0 ≤ B) (hw : w ≤ A / t) (hAB : A ≤ (2 * (t * D)) ^ (1 - 2 / q) * B ^ (2 / q)) :
w ≤ 16 * D * (B ^ (1 / q) / (⌈(t * D) ^ (1 / q)⌉₊ : ℝ)) ^ (2 : ℝ) := 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 Lemma 3.12 (\label{lem:block-system-lattices}), equation (43) (\label{eq:residue-weight}) for 2 < p < ∞; Lean: LatticePrepro/Conversions/Lattices.lean, LatticePrepro.radius_bound_gt_two