Claim A.2 (second part) — bound on the generalized digits
ProvedLatticePrepro.gdigits_lecoding-theorycvp-ncp-preprocessinghardness-of-approximationlatticespreprocessing
Let , and be integers, and let be a natural number with
Then every entry of the generalized digit vector of (Definition A.1) is at most : for every ,
that is, .
In Appendix A this is used with and . It shows that the vectors with (Definition A.5) and the vectors with (Theorem A.8) lie in the index set on which the constraints of Construction A.4 are imposed.
Formalization Note: The paper's lower bound is automatic, since the entries are natural numbers.
Preamble
import Mathlib import Definitions.Def_LatticePrepro_Tables_Digits open LatticePrepro
Formal statement
theorem LatticePrepro.gdigits_le {B m J k : ℕ} (hB : 2 ≤ B) (hm : 1 ≤ m) (hJ : 1 ≤ J)
(hk : k ≤ J * (B ^ m - 1)) (h : Fin m) : gdigits B m k h ≤ J * (B - 1) := 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), Claim A.2 (\label{clm:generalized-digits}), second part; Lean: LatticePrepro/Tables/Digits.lean, LatticePrepro.gdigits_le