Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 3.5 — distortion ≤ c into Euclidean space iff Σ_{q>0} q d² + c² Σ_{q<0} q d² ≤ 0 for every PSD Q with Q·1 = 0

Proved
GeometryOfGraphs.EuclidDist.corollary_3_5

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

distortionmetric-embeddingsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programming

Let (X,d)(X,d)(X,d) be a finite semi-metric space (n=∣X∣n = |X|n=∣X∣ points, distances di,j=d(i,j)d_{i,j} = d(i,j)di,j​=d(i,j)) and let c≥1c \ge 1c≥1. Then (X,d)(X,d)(X,d) embeds in a Euclidean space with distortion at most ccc if and only if for every real positive semidefinite matrix Q=(qi,j)i,j∈XQ = (q_{i,j})_{i,j\in X}Q=(qi,j​)i,j∈X​ with Q⋅1⃗=0⃗Q\cdot\vec 1 = \vec 0Q⋅1=0 (every row sums to zero)

∑qi,j>0qi,j di,j2  +  c2∑qi,j<0qi,j di,j2  ≤  0.\sum_{q_{i,j}>0} q_{i,j}\, d_{i,j}^2 \;+\; c^2 \sum_{q_{i,j}<0} q_{i,j}\, d_{i,j}^2 \;\le\; 0 .qi,j​>0∑​qi,j​di,j2​+c2qi,j​<0∑​qi,j​di,j2​≤0.

The sums run over ordered pairs (i,j)(i,j)(i,j) with qi,j>0q_{i,j} > 0qi,j​>0, respectively qi,j<0q_{i,j} < 0qi,j​<0, as printed; diagonal terms vanish because di,i=0d_{i,i}=0di,i​=0.

The corollary characterises the least Euclidean distortion c2(X)c_2(X)c2​(X) of a finite metric space by a family of linear inequalities in the squared distances, indexed by the positive semidefinite matrices with zero row sums: each such QQQ certifies a lower bound on c2(X)c_2(X)c2​(X), and the corollary says that these certificates are complete. For c=1c=1c=1 it reduces to the classical characterisation of finite metric spaces that embed isometrically in Euclidean space (Remark 3.7).

Formalization Note "May be embedded with distortion ≤c\le c≤c" means that an embedding with distortion at most ccc exists (attained), using the contractive form ∥φ(x)−φ(y)∥≤d(x,y)≤c∥φ(x)−φ(y)∥\|\varphi(x)-\varphi(y)\| \le d(x,y) \le c\|\varphi(x)-\varphi(y)\|∥φ(x)−φ(y)∥≤d(x,y)≤c∥φ(x)−φ(y)∥ of Definition 2.1; the target Rm\mathbb{R}^mRm has an existentially quantified dimension. "Metric space" is a semi-metric as allowed by the paper (p. 218, footnote 1). The positive semidefinite cone is Matrix.PosSemidef (symmetric by definition) and Q⋅1⃗=0⃗Q\cdot\vec1=\vec0Q⋅1=0 is Q.mulVec (fun _ => 1) = 0. The corollary's second sentence ("In particular … with c=O(log⁡n)c = O(\log n)c=O(logn)") rests on Bourgain's embedding theorem, which the paper only cites, and is not part of this statement.

Preamble
import Mathlib
import Definitions.Def_GeometryOfGraphs_EuclidDist_EuclideanDistortion
Formal statement
namespace GeometryOfGraphs.EuclidDist

/-- Corollary 3.5 (p. 224), first sentence: a finite metric space `(X, d)` embeds in a Euclidean
space with distortion at most `c` iff for every positive semidefinite `Q` with `Q · 1 = 0`,
`∑_{q_ij > 0} q_ij d_ij^2 + c^2 ∑_{q_ij < 0} q_ij d_ij^2 ≤ 0` (sums over ordered pairs). -/
theorem corollary_3_5 {X : Type*} [Fintype X] [DecidableEq X]
    (d : X → X → ℝ) (hd : GeometryOfGraphs.FlowCut.IsPseudometric d) (c : ℝ) (hc : 1 ≤ c) :
    EmbedsEuclidean d c ↔
      ∀ Q : Matrix X X ℝ, Q.PosSemidef → Q.mulVec (fun _ => (1 : ℝ)) = 0 →
        (∑ i, ∑ j, if 0 < Q i j then Q i j * d i j ^ 2 else 0) +
          c ^ 2 * (∑ i, ∑ j, if Q i j < 0 then Q i j * d i j ^ 2 else 0) ≤ 0 := by sorry

end GeometryOfGraphs.EuclidDist
Source
N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), p. 224, Corollary 3.5 (first sentence)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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