AFTD Auto-Formalizing Theoretical Domains

johnson_lindenstrauss

theoremverifiedformalizationimported Lean

Johnson–Lindenstrauss flattening lemma. Let $0 < \varepsilon < 1$ and let $n \ge 2$ be an integer. Suppose the target dimension $k$ satisfies $k \ge 32\,\log n / \varepsilon^2$. Then for every finite set $V \subseteq \bbr^d$ of at most $n$ points there exists a linear map $f : \bbr^d \to \bbr^k$ that is an $\varepsilon$-JL embedding of $V$; that is, \[ (1 - \varepsilon)\,\norm{u - v}^2 \;\le\; \norm{f(u) - f(v)}^2 \;\le\; (1 + \varepsilon)\,\norm{u - v}^2 \] for all $u, v \in V$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in
variable {d k : ℕ} in
theorem johnson_lindenstrauss
    (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1)
    (n : ℕ) (hn : 2 ≤ n)
    (hk : (32 : ℝ) * Real.log n / ε ^ 2 ≤ k)
    (V : Finset (EuclideanSpace ℝ (Fin d))) (hV : V.card ≤ n) :
    ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k),
      IsJLEmbedding ε V f
Formalizes
Johnson–Lindenstrauss flattening lemma, as formalized in TCSlib (`johnson_lindenstrauss`)
Lean proof
By Ganesh Sankar, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Ganesh Sankar. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • johnson_lindenstrauss_of_gaussianJohnson–Lindenstrauss embedding from a Gaussian matrix. Fix dimensions $d$ and $k$ with $k \ge 1$, a distortion parameter…
  • instMeasurableSpaceMatrixFinReal_tCSlibMatrices as m → n → α inherit a Pi measurable space structure.
  • measurableSet_badSingleMeasurability of the single-vector distortion event. Fix a vector $x\in\bbr^d$ and a real number $\varepsilon$, and let…
  • exists_iid_gaussian_matrixExistence of a Gaussian matrix with independent entries. Let $k \ge 1$ and $d \ge 0$ be integers. Then there is a probability space…
  • jl_failure_bound_of_dimNumerical failure-probability bound for Johnson–Lindenstrauss. Let $\varepsilon > 0$ and let $n \ge 2$ be an integer, and suppose the…
  • BadSingleFor a parameter $\varepsilon\in\mathbb{R}$, a matrix $A$, and a vector $x\in\mathbb{R}^d$, the predicate…
  • IsJLEmbeddingA linear map $f : \mathbb{R}^d \to_L[\mathbb{R}] \mathbb{R}^k$ is an $\varepsilon$-JL embedding of a finite set $V$ if, for every…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in
variable {d k : ℕ} in
/-- **Johnson–Lindenstrauss flattening lemma (standard form)** [DG03, Thm 2.1]; [Ver18, Thm 5.3.1]; origin [JL84, Lemma 1]. For any `0 < ε < 1`, any `n ≥ 2`, and target dimension `k` with `k ≥ 32 · log n / ε²`, every finite set `V` of at most `n` points in `ℝ^d` admits a linear embedding `f : ℝ^d → ℝ^k` preserving pairwise squared distances up to factor `(1 ± ε)`. The embedding is a realization of a matrix with iid `N(0, 1/k)` entries; the proof is axiom-free. Deviation: the dimension bound is `k ≥ 32 · log n / ε²`, whereas [DG03] obtains `k ≥ 4 (ε²/2 − ε³/3)⁻¹ log n` and [Ver18] states `k ≥ C ε⁻² log n` for an unspecified constant; the conclusion is stated for squared distances (see `johnson_lindenstrauss_dist` for the distance form). The `32` is not tight: it is chosen for cleanness of the numerical bookkeeping, giving `|V|² · 2 · exp(-kε²/8) ≤ 1/2`. **Proof sketch.** Step 1: numerical bookkeeping (`jl_failure_bound_of_dim`): the dimension hypothesis gives `k > 0` and the union-bound failure probability `|V|² · 2 · exp(−kε²/8)` is strictly less than `1`. Step 2: realize an iid `N(0, 1/k)` matrix `A` on a probability space (`exists_iid_gaussian_matrix`) and check that its per-pair bad events are measurable (`measurableSet_badSingle`). Step 3: the structural theorem `johnson_lindenstrauss_of_gaussian` (single-vector concentration, union bound, probabilistic method) extracts a good realization. -/
theorem johnson_lindenstrauss
    (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1)
    (n : ℕ) (hn : 2 ≤ n)
    (hk : (32 : ℝ) * Real.log n / ε ^ 2 ≤ k)
    (V : Finset (EuclideanSpace ℝ (Fin d))) (hV : V.card ≤ n) :
    ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k),
      IsJLEmbedding ε V f := by
  -- Step 1: numerical bookkeeping: k > 0 and union-bound failure prob < 1.
  obtain ⟨hk_pos, hFail⟩ :=
    jl_failure_bound_of_dim ε hε_pos n hn hk V hV
  -- Step 2: obtain a Gaussian probability space; the per-pair bad events are measurable.
  obtain ⟨Ω, _, μ, _, A, hA_meas, hA_law, hRowEntryIndep, hRowsIndep⟩ :=
    exists_iid_gaussian_matrix hk_pos d
  have hBadMeas : ∀ u ∈ V, ∀ v ∈ V,
      MeasurableSet {ω | BadSingle ε (A ω) (u - v)} :=
    fun u _ v _ => measurableSet_badSingle A hA_meas (u - v) ε
  -- Step 3: invoke the structural theorem `_of_gaussian`.
  exact johnson_lindenstrauss_of_gaussian hk_pos μ A hA_meas hA_law
    hRowEntryIndep hRowsIndep ε hε_pos hε_lt V hBadMeas hFail
See it in the graphDiscuss this resultChallenge it