Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1.4 — Concentration of Lipschitz functions on the sphere

Proved
HighDimProb.Isoperimetry.lipschitz_concentration_sphere

by mikedeng1 · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

concentrationisoperimetrylipschitzprobability

This is Theorem 5.1.4, the concentration-of-measure engine behind the Johnson-Lindenstrauss Lemma: every Lipschitz function of a point drawn uniformly from a high-dimensional Euclidean sphere concentrates tightly around its mean, with a sub-gaussian tail whose rate depends only on the function's Lipschitz constant — not on the ambient dimension nnn.

There is an absolute constant C>0C > 0C>0 such that the following holds. Let (Ω,F,Prob)(\Omega, \mathcal F, \mathrm{Prob})(Ω,F,Prob) be a probability space, n∈Nn \in \mathbb Nn∈N, and let X:Ω→RnX : \Omega \to \mathbb R^nX:Ω→Rn be a random vector uniformly distributed on the Euclidean sphere of radius n\sqrt nn​ (the companion definition IsUniformOnSphere). Let f:Rn→Rf : \mathbb R^n \to \mathbb Rf:Rn→R be a function that is LLL-Lipschitz on that sphere. Then

∥f(X)−Ef(X)∥ψ2  ≤  CL,\bigl\|f(X) - \mathbb E f(X)\bigr\|_{\psi_2} \;\le\; C L,​f(X)−Ef(X)​ψ2​​≤CL,

where ∥⋅∥ψ2\|\cdot\|_{\psi_2}∥⋅∥ψ2​​ is the sub-gaussian (Orlicz) norm of the companion definition subgaussianNorm. Equivalently, for every t≥0t \ge 0t≥0, P{∣f(X)−Ef(X)∣≥t}≤2exp⁡(−ct2/L2)P\{|f(X) - \mathbb E f(X)| \ge t\} \le 2\exp(-ct^2/L^2)P{∣f(X)−Ef(X)∣≥t}≤2exp(−ct2/L2) for an absolute constant c>0c > 0c>0.

The proof (not part of this formalization) compares sub-level sets of fff to spherical caps via the isoperimetric inequality on the sphere, reducing the general Lipschitz case to the already-known concentration of linear functions of a uniform point.

Formalization Note fff is a function on all of Rn\mathbb R^nRn, but the Lipschitz hypothesis (LipschitzOnWith L f) and the conclusion only constrain its values on the sphere, matching the book's own domain f:n Sn−1→Rf : \sqrt n\,S^{n-1} \to \mathbb Rf:n​Sn−1→R. The constant CCC is existentially quantified ahead of every other object, so no numeral is fixed for it; LLL is a fixed NNReal Lipschitz constant supplied as a hypothesis (equivalent to using the Lipschitz seminorm ∥f∥Lip\|f\|_{\mathrm{Lip}}∥f∥Lip​ itself, since the bound is monotone in LLL).

Preamble
import Mathlib
import Definitions.Def_HighDimProb_Isoperimetry_SubgaussianNorm
import Definitions.Def_HighDimProb_Isoperimetry_UniformOnSphere

open MeasureTheory
Formal statement
namespace HighDimProb.Isoperimetry

/-- **Theorem 5.1.4** (Concentration of Lipschitz functions on the sphere), Vershynin,
*High-Dimensional Probability* (2018), p. 107.

Consider a random vector `X ∼ Unif(√n Sⁿ⁻¹)`, i.e. `X` is uniformly distributed on the
Euclidean sphere of radius `√n`. Consider a Lipschitz function `f : √n Sⁿ⁻¹ → ℝ`. Then

`‖f(X) − E f(X)‖_{ψ₂} ≤ C ‖f‖_{Lip}`. -/
theorem lipschitz_concentration_sphere :
    ∃ C : ℝ, 0 < C ∧
      ∀ {Ω : Type} [MeasurableSpace Ω] (Prob : Measure Ω) [IsProbabilityMeasure Prob]
        {n : ℕ} (X : Ω → EuclideanSpace ℝ (Fin n)) (hX_meas : Measurable X)
        (hX_unif : IsUniformOnSphere Prob (Real.sqrt n) X)
        (f : EuclideanSpace ℝ (Fin n) → ℝ) (L : NNReal)
        (hf_lip : LipschitzOnWith L f (Metric.sphere (0 : EuclideanSpace ℝ (Fin n)) (Real.sqrt n))),
        subgaussianNorm Prob (fun ω => f (X ω) - ∫ ω, f (X ω) ∂Prob) ≤ C * (L : ℝ) := by sorry

end HighDimProb.Isoperimetry
Source
Vershynin, High-Dimensional Probability (2018), Theorem 5.1.4, p. 107 (PDF p. 115)
Read-back

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

The declaration asserts the existence of a real constant C>0C > 0C>0 such that the following holds for every instance of the data below.

The data quantified over. A type Ω\OmegaΩ equipped with a σ-algebra, a measure P\mathbb{P}P on Ω\OmegaΩ that is a probability measure (total mass 111), a natural number nnn (including n=0n = 0n=0), a map X:Ω→RnX : \Omega \to \mathbb{R}^nX:Ω→Rn (Euclidean space Rn\mathbb{R}^nRn, i.e. Fin n→R\mathrm{Fin}\,n \to \mathbb{R}Finn→R with the Euclidean norm) that is measurable, a function f:Rn→Rf : \mathbb{R}^n \to \mathbb{R}f:Rn→R, and a non-negative real number LLL. Two hypotheses are imposed:

  • XXX satisfies the bundle's predicate IsUniformOnSphere(P,n,X)\mathrm{IsUniformOnSphere}(\mathbb{P}, \sqrt{n}, X)IsUniformOnSphere(P,n​,X) — a definition imported from Def_HighDimProb_Isoperimetry_UniformOnSphere, whose body is not shown here, so its exact content (whether it fixes the law of XXX under P\mathbb{P}P to be the normalized surface measure on the sphere of radius n\sqrt nn​, and what it means when n=0n = 0n=0, where 0=0\sqrt{0} = 00​=0 and the "sphere" of radius 000 in the zero-dimensional space is the single point 000) must be checked in that file. Note that n\sqrt{n}n​ here is the real square root of the natural number nnn cast to R\mathbb{R}R.
  • fff is Lipschitz with constant LLL on the set S={x∈Rn:∥x∥=n}S = \{x \in \mathbb{R}^n : \|x\| = \sqrt n\}S={x∈Rn:∥x∥=n​} only, i.e. for all x,y∈Sx, y \in Sx,y∈S,
∣f(x)−f(y)∣≤L ∥x−y∥.|f(x) - f(y)| \le L\,\|x - y\|.∣f(x)−f(y)∣≤L∥x−y∥.

No regularity of fff (not even measurability) is assumed off this sphere, and LLL is any non-negative real number for which this holds — it need not be the smallest such constant.

The conclusion. Let m=∫Ωf(X(ω)) dP(ω)m = \int_\Omega f(X(\omega))\,d\mathbb{P}(\omega)m=∫Ω​f(X(ω))dP(ω) denote the Bochner integral of f∘Xf \circ Xf∘X with respect to P\mathbb{P}P. This is a total expression: if f∘Xf \circ Xf∘X is not integrable (or not a.e.-strongly measurable) with respect to P\mathbb{P}P, the integral takes the junk value 000, and no hypothesis in the statement rules this out (integrability would have to follow from the uniformity predicate together with the Lipschitz bound, if it follows at all). The claim is then

subgaussianNormP(ω↦f(X(ω))−m)  ≤  C⋅L,\mathrm{subgaussianNorm}_{\mathbb{P}}\bigl(\omega \mapsto f(X(\omega)) - m\bigr) \;\le\; C \cdot L ,subgaussianNormP​(ω↦f(X(ω))−m)≤C⋅L,

where subgaussianNormP(⋅)\mathrm{subgaussianNorm}_{\mathbb{P}}(\cdot)subgaussianNormP​(⋅) is the bundle's own definition of a sub-gaussian norm of a real-valued function on Ω\OmegaΩ, imported from Def_HighDimProb_Isoperimetry_SubgaussianNorm; its body is not shown here, so the precise quantity being bounded (an infimum over parameters t>0t>0t>0 of some exponential-moment condition, its value when that set of parameters is empty, whether it returns a real number or an extended real, etc.) must be read from that file. The inequality is non-strict, and the right-hand side is the real number CCC times the coercion of LLL to R\mathbb{R}R.

Order of quantifiers. CCC is chosen before everything else: a single CCC must work simultaneously for all dimensions nnn, all probability spaces, all such XXX, all such fff, and all admissible LLL. In particular, if L=0L = 0L=0 the conclusion demands that the sub-gaussian norm of f(X)−mf(X) - mf(X)−m be ≤0\le 0≤0; if the subgaussian norm is always non-negative this forces it to equal 000 for any fff constant on the sphere. Degenerate instances are included: n=0n = 0n=0 (where n=0\sqrt n = 0n​=0), and any instance in which the uniformity predicate is unsatisfiable, in which case the statement is vacuous for that instance.

Human review
  • Endorsed by Shuze Chen · Sep 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 24, 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