Bit-length precision budget for a coherent hybrid bound
ProvedInfoLossLAR.WorstCase.RegevSketch.coherent_precision_budgetlar-regev-bridgelatticeslearning-with-errorsquantum-computing
Let be nonnegative integers, and let be real step-error bounds for . Put
If each , then
This allocates at most half of an inverse numerical budget to the square-root losses of the coherent hybrid bound. It is a mathematical precision bound; it does not construct a decoder, prove its per-step error, or establish a machine implementation of precision selection.
Formalization Note. Nat.size is binary length and the theorem uses Lean's real square root.
Preamble
import Mathlib set_option autoImplicit false open scoped BigOperators
Formal statement
theorem InfoLossLAR.WorstCase.RegevSketch.coherent_precision_budget (steps budget : ℕ) (failure : ℕ → ℝ)
(hfailure : ∀ i < steps,
failure i ≤ (1 / (2 : ℝ) ^ (3 + Nat.size (steps+1) + Nat.size (budget+1))) ^ 2) :
(∑ i ∈ Finset.range steps, 4 * Real.sqrt (failure i)) ≤
1 / (2 * ((budget : ℝ)+1)) := by sorry
Source
Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, https://cims.nyu.edu/~regev/papers/qcrypto.pdf, Theorem 3.1 and Lemma 3.3, pp. 18–19. This explicit numerical precision allocation is a separately derived auxiliary bound for the formal hybrid error estimate, not a verbatim theorem in the source.