Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Small-ball bound for the distance of a Gaussian column to the span of the others: P{dist⁡(aj,Hj)2≤u}≤(eu/(N−n+1))(N−n+1)/2\mathbb P\{\operatorname{dist}(a_j,H_j)^2\le u\}\le (eu/(N-n+1))^{(N-n+1)/2}P{dist(aj​,Hj​)2≤u}≤(eu/(N−n+1))(N−n+1)/2

Proved
GaussianMatrix.dist_col_span_small_ball

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

chi-squaredistance-to-subspacegaussianrandom-matricessmall-ball

Let 1≤n≤N1\le n\le N1≤n≤N and let AAA be an N×nN\times nN×n random matrix with independent standard normal entries, with columns a1,…,ana_1,\dots,a_na1​,…,an​. Fix a column index jjj and let Hj=span⁡{ai:i≠j}H_j=\operatorname{span}\{a_i:i\ne j\}Hj​=span{ai​:i=j}, with

dist⁡(aj,Hj)=inf⁡x∈Rn, xj=1∥Ax∥2.\operatorname{dist}(a_j,H_j)=\inf_{x\in\mathbb R^n,\ x_j=1}\|Ax\|_2 .dist(aj​,Hj​)=x∈Rn, xj​=1inf​∥Ax∥2​.

Then for every real uuu with 0≤u≤N−n+10\le u\le N-n+10≤u≤N−n+1,

P{dist⁡(aj,Hj)2≤u}  ≤  (e uN−n+1)(N−n+1)/2.\mathbb P\big\{\operatorname{dist}(a_j,H_j)^2\le u\big\}\;\le\;\Big(\frac{e\,u}{N-n+1}\Big)^{(N-n+1)/2}.P{dist(aj​,Hj​)2≤u}≤(N−n+1eu​)(N−n+1)/2.

Conditionally on the other columns, aja_jaj​ is a standard Gaussian vector independent of HjH_jHj​, a subspace of dimension at most n−1n-1n−1; the squared distance of aja_jaj​ to it dominates a χ2\chi^2χ2 variable with N−n+1N-n+1N−n+1 degrees of freedom, whose lower tail obeys the stated bound. Integrating over the other columns gives the claim.

Combined with the deterministic reduction σmin⁡(A)≤s⇒∃j, dist⁡(aj,Hj)≤ns\sigma_{\min}(A)\le s\Rightarrow\exists j,\ \operatorname{dist}(a_j,H_j)\le\sqrt n sσmin​(A)≤s⇒∃j, dist(aj​,Hj​)≤n​s and a union bound over jjj, this yields the small-ball estimate P{σmin⁡(A)≤s}≤n (ens2/(N−n+1))(N−n+1)/2\mathbb P\{\sigma_{\min}(A)\le s\}\le n\,(e n s^2/(N-n+1))^{(N-n+1)/2}P{σmin​(A)≤s}≤n(ens2/(N−n+1))(N−n+1)/2.

Formalization Note. The law of AAA is gaussianMatrix N n (a product over rows of product measures); the event is written with the explicit infimum, and the probability of a possibly non-measurable set is the outer measure (the set is in fact measurable). The dimension of HjH_jHj​ may drop below n−1n-1n−1; the bound holds regardless since the degrees of freedom only increase.

Preamble
import Definitions.Def_GaussianMatrix_basic

open MeasureTheory ProbabilityTheory
open scoped Matrix
Formal statement
namespace GaussianMatrix

theorem dist_col_span_small_ball {N n : ℕ} (hnN : n ≤ N) (j : Fin n) (u : ℝ) (hu : 0 ≤ u)
    (hud : u ≤ (N : ℝ) - n + 1) :
    (gaussianMatrix N n) {A | (⨅ x : {x : Fin n → ℝ // x j = 1},
        Real.sqrt ((Matrix.of A *ᵥ x.1) ⬝ᵥ (Matrix.of A *ᵥ x.1))) ^ 2 ≤ u}
      ≤ ENNReal.ofReal ((Real.exp 1 * u / ((N : ℝ) - n + 1)) ^ (((N : ℝ) - n + 1) / 2)) := by sorry

end GaussianMatrix
Source
standard fact: for a standard Gaussian vector g in R^N independent of a subspace H with dim H ≤ n−1, dist(g,H)^2 stochastically dominates χ²_{N−n+1}; combined with the χ² lower tail P{χ²_d ≤ u} ≤ (eu/d)^{d/2} (cf. Rudelson–Vershynin, Adv. Math. 218 (2008), §3; Laurent–Massart, Ann. Statist. 28 (2000), Lemma 1).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me