Short independent vectors in an ideal DGS pool
ProvedInfoLossLAR.WorstCase.RegevSketch.dgs_ideal_short_spanning_pooldiscrete-gaussianlar-regev-bridgelattices
In all sufficiently large positive dimensions, a pool of independent exact discrete Gaussian samples at any admissible width contains independent vectors of norm at most twice that width times with probability at least . Interpret samples as original-basis coefficients. Use Regev’s constant escape probability from any proper span, followed by Gaussian norm concentration and a union bound over the pool.
Preamble
import Definitions.Def_InfoLossLAR_RegevSketch_DGS set_option autoImplicit false set_option maxHeartbeats 200000 open QAlgorithms.Complexity open scoped BigOperators Classical
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem dgs_ideal_short_spanning_pool : ∃ n₀ : ℕ, ∀ n ≥ n₀, 1 ≤ n →
∀ (B : Matrix (Fin n) (Fin n) ℤ), B.det ≠ 0 →
∀ r : ℝ, 0 < r → dgsThreshold B ≤ r →
(7 : ℝ)/8 ≤ ∑' pool : Fin (16 * (n + 1)^2) → Fin n → ℤ,
(∏ i, coefficientMass B r (pool i)) *
(if ∃ pick : Fin n → Fin (16 * (n + 1)^2),
LinearIndependent ℝ (fun i => latVec B (pool (pick i))) ∧
∀ i, ‖latVec B (pool (pick i))‖ ≤ 2 * Real.sqrt n * r
then 1 else 0) := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, full version dated May 2, 2009, https://cims.nyu.edu/~regev/papers/qcrypto.pdf. Lemmas 3.15–3.17, full-version PDF pp. 28–29; fixed-family substitution and explicit uniform multi-output realization.