Proof of Claim 2.2, p. 34:16 — |e^{−π(1−1/(1+ϵ)²)x²} − 1| ≤ π(1 − 1/(1+ϵ)²)x² ≤ 2πϵx²
ProvedRegevLWE.PeriodicGauss.pointwise_boundgaussianinequalitylearning-with-errorsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every and every real ,
The paper derives this from for .
It turns the integral left over by the first display into a second moment of a Gaussian.
Formalization Note The paper uses the bound for ; it holds, and is stated, for every .
Preamble
import Mathlib import Definitions.Def_RegevLWE_PeriodicGauss_Gaussian open MeasureTheory
Formal statement
namespace RegevLWE.PeriodicGauss
/-- Proof of Claim 2.2, p. 34:16: since `1 - z ≤ e^{-z} ≤ 1` for all `z ≥ 0`,
`|e^{-π(1-1/(1+ϵ)²)x²} - 1| ≤ π(1 - 1/(1+ϵ)²)x² ≤ 2πϵx²` (here for every `ϵ ≥ 0` and real `x`). -/
theorem pointwise_bound (ϵ : ℝ) (hϵ : 0 ≤ ϵ) (x : ℝ) :
|Real.exp (-Real.pi * (1 - 1 / (1 + ϵ) ^ 2) * x ^ 2) - 1| ≤
Real.pi * (1 - 1 / (1 + ϵ) ^ 2) * x ^ 2 ∧
Real.pi * (1 - 1 / (1 + ϵ) ^ 2) * x ^ 2 ≤ 2 * Real.pi * ϵ * x ^ 2 := by sorry
end RegevLWE.PeriodicGauss
Source
Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, J. ACM 56(6) (2009), Article 34, p. 34:16, proof of Claim 2.2, display after "since 1 − z ≤ e^{−z} ≤ 1 for all z ≥ 0"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.