graph_wasserstein_dist_self_eq_zero
The Wasserstein distance from a nonnegative measure to itself is 0.
Statement
theorem graph_wasserstein_dist_self_eq_zero {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (μ : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) : graph_wasserstein_dist G μ μ = 0
- Source
- Sanity check of the definitions of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Definition 2.1.
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- graph_wasserstein_dist_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
The proof, explained
The proof shows that the Wasserstein distance graph_wasserstein_dist(G, μ, μ) is equal to 0 by proving the two inequalities ≤ 0 and ≥ 0. For the upper bound, the diagonal coupling π(a, b) = (if a = b then μ(a) else 0) provides a valid transport plan between μ and itself with total cost 0. For the lower bound, graph distances and transport plans are everywhere non-negative, meaning every transport cost is at least 0, so their infimum is at least 0.
Define the diagonal transport plan π and establish that it is non-negative everywhere.
We define π(a, b) to be μ(a) when a = b and 0 otherwise. To show 0 ≤ π(a, b) for all a and b, we split into cases: if a = b, π(a, b) = μ(a), which is non-negative by the hypothesis hμ; if a ≠ b, π(a, b) = 0 ≥ 0 holds by reflexivity.
let π : V → V → ℝ := fun a b => if a = b then μ a else 0 have hπ : ∀ a b, 0 ≤ π a b := fun a b => by dsimp [π] split_ifs · exact hμ a · rfl
Both marginals of π equal μ, and its total transport cost is 0.
Summing π(a, b) over b leaves only the diagonal term b = a, giving μ(a); similarly, summing π(a, b) over a gives μ(b). For the total cost ∑ a, ∑ b, dist(a, b) * π(a, b), every term with a ≠ b vanishes because π(a, b) = 0, and every diagonal term vanishes because the graph distance dist(a, a) = 0, so the total sum is 0. All three identities are verified by simplifying with the definition of π.
have h1 : ∀ a, ∑ b, π a b = μ a := fun a => by simp [π] have h2 : ∀ b, ∑ a, π a b = μ b := fun b => by simp [π] have hcost : ∑ a, ∑ b, (G.dist a b : ℝ) * π a b = 0 := by simp [π]
The Wasserstein distance satisfies graph_wasserstein_dist(G, μ, μ) ≤ 0.
Because π is a valid transport plan between μ and itself, the lemma graph_wasserstein_dist_le_of_plan shows that the Wasserstein distance is at most the cost of π. Rewriting with the previous step's evaluation that this cost is 0 yields the upper bound.
uses
graph_wasserstein_dist_le_of_planhave hle : graph_wasserstein_dist G μ μ ≤ 0 := by have := graph_wasserstein_dist_le_of_plan G μ μ π hπ h1 h2 rwa [hcost] at this
The Wasserstein distance satisfies 0 ≤ graph_wasserstein_dist(G, μ, μ).
By definition, the Wasserstein distance is the infimum (sInf) of the set of all transport costs from valid plans. By le_csInf, 0 is at most this infimum provided that the set is nonempty (witnessed by cost 0 achieved by plan π) and that 0 is a lower bound for every element in the set. Any element in the set is the cost of some valid plan p, which is a sum of terms dist(a, b) * p(a, b); since graph distances are non-negative and each p(a, b) ≥ 0, each term is non-negative by mul_nonneg, and the finite sum of non-negative terms is non-negative by Finset.sum_nonneg.
uses
le_csInf,Finset.sum_nonneg,mul_nonneghave hge : 0 ≤ graph_wasserstein_dist G μ μ := by dsimp [graph_wasserstein_dist] apply le_csInf · exact ⟨0, π, hπ, h1, h2, hcost.symm⟩ · rintro c ⟨p, hp, -, -, rfl⟩ exact Finset.sum_nonneg fun a _ => Finset.sum_nonneg fun b _ => mul_nonneg (by positivity) (hp a b)
graph_wasserstein_dist(G, μ, μ) = 0.
Combining the upper bound graph_wasserstein_dist(G, μ, μ) ≤ 0 and the lower bound 0 ≤ graph_wasserstein_dist(G, μ, μ) via antisymmetry (le_antisymm) yields the equality.
uses
le_antisymmexact le_antisymm hle hge
graph_wasserstein_dist_le_of_plan- A valid transport plan π with non-negative values and marginals μ and ν provides an upper bound on the graph Wasserstein distance between μ and ν given by its total transport cost ∑ a, ∑ b, dist(a, b) * π(a, b).
le_csInf- In a conditionally complete lattice, an element a is less than or equal to the infimum of a set s if s is nonempty and a is a lower bound for s (i.e. a ≤ b for all b ∈ s).
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
mul_nonneg- The product of two non-negative numbers is non-negative.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
- The marginal identities and the zero-cost evaluation for the diagonal plan π are discharged by the simplifier (`simp`), which simplifies the finite sums over the if-then-else definition of π.
- The non-negativity of the graph distance in the lower bound step is discharged automatically by the `positivity` tactic.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem graph_wasserstein_dist_self_eq_zero {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (μ : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) : graph_wasserstein_dist G μ μ = 0 := by let π : V → V → ℝ := fun a b => if a = b then μ a else 0 have hπ : ∀ a b, 0 ≤ π a b := fun a b => by dsimp [π] split_ifs · exact hμ a · rfl have h1 : ∀ a, ∑ b, π a b = μ a := fun a => by simp [π] have h2 : ∀ b, ∑ a, π a b = μ b := fun b => by simp [π] have hcost : ∑ a, ∑ b, (G.dist a b : ℝ) * π a b = 0 := by simp [π] have hle : graph_wasserstein_dist G μ μ ≤ 0 := by have := graph_wasserstein_dist_le_of_plan G μ μ π hπ h1 h2 rwa [hcost] at this have hge : 0 ≤ graph_wasserstein_dist G μ μ := by dsimp [graph_wasserstein_dist] apply le_csInf · exact ⟨0, π, hπ, h1, h2, hcost.symm⟩ · rintro c ⟨p, hp, -, -, rfl⟩ exact Finset.sum_nonneg fun a _ => Finset.sum_nonneg fun b _ => mul_nonneg (by positivity) (hp a b) exact le_antisymm hle hge