Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Chernoff lower tail of a chi-square variable: P{χd2≤u}≤(eu/d)d/2\mathbb P\{\chi_d^2\le u\}\le(eu/d)^{d/2}P{χd2​≤u}≤(eu/d)d/2 for 0≤u≤d0\le u\le d0≤u≤d

Proved
GaussianMatrix.chi_square_lower_tail

by tc · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussian-matrixprobabilityrandom-matrix-theoryrandomized-numerical-linear-algebra

Let g=(g1,…,gd)g=(g_1,\dots,g_d)g=(g1​,…,gd​) be a standard Gaussian vector in Rd\mathbb R^{d}Rd, d≥1d\ge1d≥1, so that χd2=∑i=1dgi2\chi_d^2=\sum_{i=1}^d g_i^2χd2​=∑i=1d​gi2​ has the chi-square distribution with ddd degrees of freedom. For every uuu with 0≤u≤d0\le u\le d0≤u≤d,

P{χd2≤u} ≤ (e ud)d/2.\mathbb P\bigl\{\chi_d^2\le u\bigr\}\ \le\ \Bigl(\frac{e\,u}{d}\Bigr)^{d/2}.P{χd2​≤u} ≤ (deu​)d/2.

This is the elementary Chernoff (moment-generating-function) estimate for the lower tail of a chi-square variable (Dasgupta–Gupta, Lemma 2.2); it is the probabilistic input for small-ball estimates of distances of a Gaussian vector to a fixed subspace, and hence for the small-ball bound on the smallest singular value of a Gaussian matrix.

Formalization Note. The chi-square variable is realized as ∑igi2\sum_i g_i^2∑i​gi2​ under the product of ddd standard normal measures on Rd\mathbb R^dRd; the exponent d/2d/2d/2 is a real power. For u=0u=0u=0 the right side is 000 and the left side is the probability of the null event {g=0}\{g=0\}{g=0}.

Preamble
import Definitions.Def_GaussianMatrix_basic

open MeasureTheory ProbabilityTheory
open scoped Matrix
Formal statement
namespace GaussianMatrix
theorem chi_square_lower_tail {d : ℕ} (hd : 1 ≤ d) (u : ℝ) (hu : 0 ≤ u) (hud : u ≤ d) :
    (Measure.pi fun _ : Fin d => gaussianReal 0 1) {g | ∑ i, g i ^ 2 ≤ u}
      ≤ ENNReal.ofReal ((Real.exp 1 * u / d) ^ ((d : ℝ) / 2)) := by sorry
end GaussianMatrix
Source
S. Dasgupta, A. Gupta, *An elementary proof of a theorem of Johnson and Lindenstrauss*, Random Structures & Algorithms 22(1), 60–65, 2003, https://doi.org/10.1002/rsa.10073, Lemma 2.2(a): for L∼χd2L\sim\chi^2_dL∼χd2​ and β<1\beta<1β<1, P[L≤βd]≤βd/2exp⁡(d(1−β)/2)\mathbb P[L\le\beta d]\le\beta^{d/2}\exp(d(1-\beta)/2)P[L≤βd]≤βd/2exp(d(1−β)/2); with β=u/d\beta=u/dβ=u/d this is (u/d)d/2e(d−u)/2≤(eu/d)d/2(u/d)^{d/2}e^{(d-u)/2}\le(eu/d)^{d/2}(u/d)d/2e(d−u)/2≤(eu/d)d/2 (the case u=du=du=d is trivial). Also N. Halko, P.-G. Martinsson, J. A. Tropp, *Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions*, SIAM Review 53(2), 2011, https://arxiv.org/abs/0909.4061 (v2), Appendix A.3.1 p. 65, Proposition A.8 (chi-square moments) for the moment-generating-function route.
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1

Let ddd be a natural number with 1≤d1 \le d1≤d, and let uuu be a real number with 0≤u≤d0 \le u \le d0≤u≤d. Let γd\gamma_dγd​ be the product measure on Rd\mathbb R^dRd (functions g:{0,…,d−1}→Rg : \{0,\dots,d-1\} \to \mathbb Rg:{0,…,d−1}→R) under which the ddd coordinates are independent standard normals N(0,1)\mathcal N(0,1)N(0,1); this is a probability measure and is written directly as a product of one-dimensional Gaussians, not via the matrix-law construction. The statement asserts

γd({g:∑i<dgi2≤u})  ≤  ofReal⁡ ⁣((e⋅ud)d/2),\gamma_d\Big(\Big\{ g : \sum_{i<d} g_i^2 \le u \Big\}\Big) \;\le\; \operatorname{ofReal}\!\Big(\Big(\frac{e \cdot u}{d}\Big)^{d/2}\Big),γd​({g:i<d∑​gi2​≤u})≤ofReal((de⋅u​)d/2),

where e=exp⁡(1)e = \exp(1)e=exp(1), the division eu/de u / deu/d is real division (no division by zero since d≥1d \ge 1d≥1), the exponent d/2d/2d/2 is the real number d/2>0d/2 > 0d/2>0, and the power is the real power xyx^{y}xy (for base x=eu/d≥0x = eu/d \ge 0x=eu/d≥0 and exponent y>0y > 0y>0 this is the usual nonnegative power; in particular 0d/2=00^{d/2} = 00d/2=0). The left side is the outer measure of the set (no measurability assumed); the right side is in [0,∞][0,\infty][0,∞] and the base is nonnegative so ofReal⁡\operatorname{ofReal}ofReal does not truncate. Edge cases: when u=0u = 0u=0 the right-hand side is 000, so the claim is that γd({g:∑igi2≤0})=γd({g=0})=0\gamma_d(\{g : \sum_i g_i^2 \le 0\}) = \gamma_d(\{g = 0\}) = 0γd​({g:∑i​gi2​≤0})=γd​({g=0})=0; when u=du = du=d the right-hand side is ed/2≥1e^{d/2} \ge 1ed/2≥1 and the inequality is automatic for a probability measure.

Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by tc · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me