Theorem 5.1.4 — Concentration of Lipschitz functions on the sphere
ProvedHighDimProb.Isoperimetry.lipschitz_concentration_sphereThis 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 .
There is an absolute constant such that the following holds. Let
be a probability space, , and let
be a random vector uniformly distributed on the Euclidean
sphere of radius (the companion definition IsUniformOnSphere). Let
be a function that is -Lipschitz on that sphere. Then
where is the sub-gaussian (Orlicz) norm of the companion definition
subgaussianNorm. Equivalently, for every ,
for an absolute constant .
The proof (not part of this formalization) compares sub-level sets of 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 is a function on all of , but the Lipschitz
hypothesis (LipschitzOnWith L f) and the conclusion only constrain its values on the
sphere, matching the book's own domain . The constant
is existentially quantified ahead of every other object, so no numeral is fixed for it;
is a fixed NNReal Lipschitz constant supplied as a hypothesis (equivalent to using the
Lipschitz seminorm itself, since the bound is monotone in ).
import Mathlib import Definitions.Def_HighDimProb_Isoperimetry_SubgaussianNorm import Definitions.Def_HighDimProb_Isoperimetry_UniformOnSphere open MeasureTheory
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1
The declaration asserts the existence of a real constant such that the following holds for every instance of the data below.
The data quantified over. A type equipped with a σ-algebra, a measure on that is a probability measure (total mass ), a natural number (including ), a map (Euclidean space , i.e. with the Euclidean norm) that is measurable, a function , and a non-negative real number . Two hypotheses are imposed:
- satisfies the bundle's predicate — a definition imported from
Def_HighDimProb_Isoperimetry_UniformOnSphere, whose body is not shown here, so its exact content (whether it fixes the law of under to be the normalized surface measure on the sphere of radius , and what it means when , where and the "sphere" of radius in the zero-dimensional space is the single point ) must be checked in that file. Note that here is the real square root of the natural number cast to . - is Lipschitz with constant on the set only, i.e. for all ,
No regularity of (not even measurability) is assumed off this sphere, and is any non-negative real number for which this holds — it need not be the smallest such constant.
The conclusion. Let denote the Bochner integral of with respect to . This is a total expression: if is not integrable (or not a.e.-strongly measurable) with respect to , the integral takes the junk value , 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
where is the bundle's own definition of a sub-gaussian norm of a real-valued function on , imported from Def_HighDimProb_Isoperimetry_SubgaussianNorm; its body is not shown here, so the precise quantity being bounded (an infimum over parameters 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 times the coercion of to .
Order of quantifiers. is chosen before everything else: a single must work simultaneously for all dimensions , all probability spaces, all such , all such , and all admissible . In particular, if the conclusion demands that the sub-gaussian norm of be ; if the subgaussian norm is always non-negative this forces it to equal for any constant on the sphere. Degenerate instances are included: (where ), and any instance in which the uniformity predicate is unsatisfiable, in which case the statement is vacuous for that instance.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.