Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.2, p. 377 — for a distance matrix D and p ≥ 1, W_p = L_{D^p}^{1/p} is a distance on Σ_n

Proved
CompOT.Metric.proposition_2_2

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

metricoptimal-transportp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1wasserstein

Let p≥1p\ge1p≥1 and let D∈R+n×nD\in\mathbb R^{n\times n}_+D∈R+n×n​ be a distance on [ ⁣[n] ⁣][\![n]\!][[n]], i.e.

  1. DDD is symmetric;
  2. Di,j=0D_{i,j}=0Di,j​=0 if and only if i=ji=ji=j;
  3. Di,k≤Di,j+Dj,kD_{i,k}\le D_{i,j}+D_{j,k}Di,k​≤Di,j​+Dj,k​ for all (i,j,k)∈[ ⁣[n] ⁣]3(i,j,k)\in[\![n]\!]^3(i,j,k)∈[[n]]3.

For histograms a,b∈Σna,b\in\Sigma_na,b∈Σn​ let Wp(a,b)=LDp(a,b)1/p\mathrm W_p(a,b)=L_{D^p}(a,b)^{1/p}Wp​(a,b)=LDp​(a,b)1/p, where LDp(a,b)=min⁡P∈U(a,b)∑i,jDi,jpPi,jL_{D^p}(a,b)=\min_{P\in U(a,b)}\sum_{i,j}D_{i,j}^pP_{i,j}LDp​(a,b)=minP∈U(a,b)​∑i,j​Di,jp​Pi,j​ is the optimal transport cost for the entrywise power DpD^pDp. Then Wp\mathrm W_pWp​ is a distance on Σn\Sigma_nΣn​: for all a,b,c∈Σna,b,c\in\Sigma_na,b,c∈Σn​,

Wp(a,b)=Wp(b,a),Wp(a,b)≥0,Wp(a,b)=0  ⟺  a=b,Wp(a,c)≤Wp(a,b)+Wp(b,c).\mathrm W_p(a,b)=\mathrm W_p(b,a),\qquad \mathrm W_p(a,b)\ge0,\qquad \mathrm W_p(a,b)=0\iff a=b,\qquad \mathrm W_p(a,c)\le\mathrm W_p(a,b)+\mathrm W_p(b,c).Wp​(a,b)=Wp​(b,a),Wp​(a,b)≥0,Wp​(a,b)=0⟺a=b,Wp​(a,c)≤Wp​(a,b)+Wp​(b,c).

Optimal transport thus lifts a ground distance on bins to a distance between histograms on those bins, the ppp-Wasserstein distance.

Formalization Note Indices are Fin n (0-based); Σn\Sigma_nΣn​ is Mathlib's stdSimplex ℝ (Fin n). The book's "positive" is read as nonnegativity; strict positivity for a≠ba\ne ba=b is the clause Wp(a,b)=0  ⟺  a=b\mathrm W_p(a,b)=0\iff a=bWp​(a,b)=0⟺a=b. The minimum is written as a real infimum over U(a,b)U(a,b)U(a,b), which is nonempty and compact for a,b∈Σna,b\in\Sigma_na,b∈Σn​. Powers are real powers with p∈Rp\in\mathbb Rp∈R, p≥1p\ge1p≥1. The book's D∈R+n×nD\in\mathbb R^{n\times n}_+D∈R+n×n​ is the hypothesis Di,j≥0D_{i,j}\ge0Di,j​≥0. For n=0n=0n=0 the simplex is empty and the statement holds vacuously, as in the book.

Preamble
import Mathlib
import Definitions.Def_CompOT_Metric_Defs
Formal statement
namespace CompOT.Metric

open Matrix

/-- **Proposition 2.2** (p. 377). Let `D ∈ ℝ₊^{n×n}` be a distance on `⟦n⟧` (symmetric,
`D_{i,j} = 0 ↔ i = j`, triangle inequality) and `p ≥ 1`. Then `W_p(a, b) = L_{D^p}(a, b)^{1/p}`
(2.17) is a distance on `Σ_n`: symmetric, nonnegative, `W_p(a, b) = 0 ↔ a = b`, and it satisfies
the triangle inequality. -/
theorem proposition_2_2 {n : ℕ} (D : Matrix (Fin n) (Fin n) ℝ) (p : ℝ) (hp : 1 ≤ p)
    (hD_nonneg : ∀ i j, 0 ≤ D i j)
    (hD_symm : ∀ i j, D i j = D j i)
    (hD_zero : ∀ i j, D i j = 0 ↔ i = j)
    (hD_tri : ∀ i j k, D i k ≤ D i j + D j k) :
    ∀ a ∈ stdSimplex ℝ (Fin n), ∀ b ∈ stdSimplex ℝ (Fin n), ∀ c ∈ stdSimplex ℝ (Fin n),
      W D p a b = W D p b a ∧
      0 ≤ W D p a b ∧
      (W D p a b = 0 ↔ a = b) ∧
      W D p a c ≤ W D p a b + W D p b c := by sorry

end CompOT.Metric
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), Proposition 2.2 and (2.17), p. 377
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

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