Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Euclidean metric sparsifiers, Q(D,A)Q(\mathcal D,A)Q(D,A), e(D,A)e(\mathcal D,A)e(D,A), QkQ_kQk​, eke_kek​

Definition
BourgainUnion_Euclidean_Supplement_SparsifierModel

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

discrete-geometryfunctional-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let XXX be a finite set, U1,…,UkU_1,\dots,U_kU1​,…,Uk​ a partition of XXX into nonempty sets, and D\mathcal DD the class of pseudometrics on XXX whose restriction to every UjU_jUj​ is Euclidean. Fix A=UiA=U_iA=Ui​.

  1. A weighted graph HHH on AAA (nonnegative symmetric weights, zero diagonal, no weight outside A×AA\times AA×A) is a Euclidean metric sparsifier of a weighted graph GGG on XXX with quality Q≥1Q\ge1Q≥1 if, for every Euclidean pseudometric ρ\rhoρ on AAA,
1QEH(ρ2)≤min-ext⁡D(ρ,G)≤EH(ρ2),\frac1Q E_H(\rho^2)\le \operatorname{min\text{-}ext}_{\mathcal D}(\rho,G)\le E_H(\rho^2),Q1​EH​(ρ2)≤min-extD​(ρ,G)≤EH​(ρ2),

with the same HHH for every ρ\rhoρ (Definition 4.1, inequality (4)); min-ext⁡D\operatorname{min\text{-}ext}_{\mathcal D}min-extD​ is the published optimal extension cost (3). 2. Q(D,A)Q(\mathcal D,A)Q(D,A) is the least QQQ such that every loopless weighted graph GGG on XXX has a sparsifier of quality QQQ. 3. e(D,A)e(\mathcal D,A)e(D,A) is the least Λ≥1\Lambda\ge1Λ≥1 such that for every d∈Dd\in\mathcal Dd∈D, every L≥0L\ge0L≥0 and every map f:A→ℓ2f:A\to\ell_2f:A→ℓ2​ that is LLL-Lipschitz for ddd, some F:X→ℓ2F:X\to\ell_2F:X→ℓ2​ extends fff and is ΛL\Lambda LΛL-Lipschitz for ddd on all of XXX. 4. QkQ_kQk​ and eke_kek​ are the suprema of Q(D,A)Q(\mathcal D,A)Q(D,A) and e(D,A)e(\mathcal D,A)e(D,A) over all finite sets XXX, all partitions of XXX into at most kkk nonempty sets, and all choices A=UiA=U_iA=Ui​.

All four quantities take values in [0,∞][0,\infty][0,∞]: an infimum over an empty set of admissible constants is ∞\infty∞.

Formalization Note Lipschitz conditions in e(D,A)e(\mathcal D,A)e(D,A) are with respect to the varying pseudometric ddd, not a fixed metric instance; the suprema range over finite types in Type.

Definition code
import Mathlib
import Definitions.Def_BourgainUnion_Euclidean_GraphModel

set_option autoImplicit false
open scoped BigOperators ENNReal
noncomputable section

namespace BourgainUnion.Euclidean.Supplement

open BourgainUnion.Euclidean

/-- Definition 4.1, p. 13: `h` is a weighted graph on `A` (nonnegative, symmetric, zero diagonal,
no weight outside `A × A`) and a Euclidean metric sparsifier of the graph with weights `w` for the
class `D` of `U`, with quality `Q ≥ 1`: inequality (4) holds for every Euclidean `ρ` on `A`, with
the same `h` for all such `ρ`. -/
def IsSparsifier {X : Type*} [Fintype X] {k : ℕ} (U : Fin k → Set X) (A : Finset X)
    (w h : X → X → ℝ) (Q : ℝ) : Prop :=
  1 ≤ Q ∧ (∀ x y, 0 ≤ h x y) ∧ (∀ x y, h x y = h y x) ∧ (∀ x, h x x = 0) ∧
  (∀ x y, x ∉ A ∨ y ∉ A → h x y = 0) ∧
  ∀ ρ : X → X → ℝ, RawEuclidean ρ (A : Set X) →
    ENNReal.ofReal (energy h ρ A / Q) ≤ minExt U A ρ w ∧
      minExt U A ρ w ≤ ENNReal.ofReal (energy h ρ A)

/-- `Q(D, A)`, p. 13: the least quality guaranteed for every (loopless) weighted graph on `X`;
`⊤` when no finite quality works. -/
def sparsifierQuality {X : Type*} [Fintype X] {k : ℕ} (U : Fin k → Set X) (A : Finset X) :
    ℝ≥0∞ :=
  sInf {q | ∃ Q : ℝ, (∀ G : ClusterDecomp.WGraph X, Loopless G →
      ∃ h : X → X → ℝ, IsSparsifier U A G.w h Q) ∧ q = ENNReal.ofReal Q}

/-- `e(D, A)`, pp. 13–14: the least `Λ ≥ 1` such that, for every pseudometric `d` in the class
`D` of `U`, every `L`-Lipschitz map `(A, d) → ℓ₂` extends to a `ΛL`-Lipschitz map `(X, d) → ℓ₂`.
Lipschitz conditions are with respect to `d`, which varies over the class. -/
def extensionConstantD {X : Type*} {k : ℕ} (U : Fin k → Set X) (A : Set X) : ℝ≥0∞ :=
  sInf {q | ∃ Λ : ℝ, 1 ≤ Λ ∧
    (∀ d : X → X → ℝ, MetricClass U d → ∀ L : ℝ, 0 ≤ L → ∀ f : X → H2,
      (∀ x ∈ A, ∀ y ∈ A, dist (f x) (f y) ≤ L * d x y) →
      ∃ F : X → H2, Set.EqOn F f A ∧ ∀ x y, dist (F x) (F y) ≤ Λ * L * d x y) ∧
    q = ENNReal.ofReal Λ}

/-- `Q_k`, p. 14: the supremum of `Q(D, A)` over finite sets `X`, partitions of `X` into at most
`k` nonempty sets, and choices `A = U_i`. -/
def Qk (k : ℕ) : ℝ≥0∞ :=
  ⨆ (X : Type) (_ : Fintype X) (j : ℕ) (_ : j ≤ k) (U : Fin j → Set X) (_ : Partition U)
    (i : Fin j), sparsifierQuality U (U i).toFinite.toFinset

/-- `e_k`, p. 14: the supremum of `e(D, A)` over the same data as `Q_k`. -/
def ek (k : ℕ) : ℝ≥0∞ :=
  ⨆ (X : Type) (_ : Fintype X) (j : ℕ) (_ : j ≤ k) (U : Fin j → Set X) (_ : Partition U)
    (i : Fin j), extensionConstantD U (U i)

end BourgainUnion.Euclidean.Supplement
Source
Dimitar Chakarov, Sepideh Mahabadi, Yury Makarychev, Ali Vakilian, Bourgain's Theorem for a Union of Euclidean Metric Spaces, STOC 2027 submission #699 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/699.pdf, PDF = printed p. 13–14, §4.1, equation (3), Definition 4.1, inequality (4), definitions of Q(D,A), e(D,A), Q_k, e_k

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