One variance guess controls all residual integer Gaussian laws
ProvedInfoLossLAR.WorstCase.RegevSearch.residual_variance_grid_gaussian_tvdiscrete-gaussianlar-regev-bridgelattices
Let and be integers. Let be an unknown initial noise energy. Write for the normalized discrete Gaussian on . There is a single index such that at every stage the publicly specified rational variance belongs to . For one has
Under correct modular residual updates in bounded-distance decoding, the energy falls by per digit. Consequently, all digits admit the same one of the publicly enumerable variance schedules.
Preamble
import Definitions.Def_InfoLossLAR_NativeSparsePrefix_01 import Mathlib.Analysis.SpecialFunctions.Gaussian.PoissonSummation set_option autoImplicit false open scoped BigOperators
Formal statement
namespace InfoLossLAR.WorstCase.RegevSearch
theorem residual_variance_grid_gaussian_tv
(s q M : ℕ) (hs : 2 ≤ s) (hq : 2 ≤ q) (hM : 0 < M)
(E : ℝ) (hE : 0 ≤ E) (hcap : E ≤ (s : ℝ)^2 / 2) :
∃ i : Fin (M + 1), ∀ j : ℕ,
let den : ℚ := (q : ℚ)^(2*j)
let v : ℚ := (s : ℚ)^2 - ((s : ℚ)^2/2) * (i.val : ℚ) / M / den
let total := E / (den : ℝ) + (v : ℝ)
let mass := fun (width : ℝ) (z : ℤ) => AFT.GaussianSource.weight width z /
AFT.GaussianSource.realNormalizer width
(s : ℚ)^2/2 ≤ v ∧ v ≤ (s : ℚ)^2 ∧
0 ≤ (s : ℝ)^2 - total ∧
(s : ℝ)^2 - total ≤ (s : ℝ)^2 / (2 * M * (den : ℝ)) ∧
(∑' z : ℤ, |mass (Real.sqrt total) z - mass (s : ℝ) z|)/2 ≤
1 / ((M : ℝ) * (den : ℝ)) := by
sorry
end InfoLossLAR.WorstCase.RegevSearchSource
Specialization to the exact integer Gaussian in InfoLossLAR.WorstCase.RegevSearch.search_to_shared_pool_bdd (https://prove2.me/theorems/0bf36425-687f-493d-a04f-ac2e81e7e02e). Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, §3.2.1, Lemma 3.5 (recursion) and Lemma 3.11 (noise), https://cims.nyu.edu/~regev/papers/qcrypto.pdf. The simultaneous rational grid and its sharp discrete bound are derived here. The scalar identity used is Mathlib Real.tsum_exp_neg_mul_int_sq (Gaussian Poisson summation).