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
ProvedGeometryOfGraphs.EuclidDist.corollary_3_5Let be a finite semi-metric space ( points, distances ) and let . Then embeds in a Euclidean space with distortion at most if and only if for every real positive semidefinite matrix with (every row sums to zero)
The sums run over ordered pairs with , respectively , as printed; diagonal terms vanish because .
The corollary characterises the least Euclidean distortion 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 certifies a lower bound on , and the corollary says that these certificates are complete. For 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 " means that an embedding with distortion at most exists (attained), using the contractive form of Definition 2.1; the target 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 is Q.mulVec (fun _ => 1) = 0. The corollary's second sentence ("In particular … with ") rests on Bourgain's embedding theorem, which the paper only cites, and is not part of this statement.
import Mathlib import Definitions.Def_GeometryOfGraphs_EuclidDist_EuclideanDistortion
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.