AFTD Auto-Formalizing Theoretical Domains

graph_wasserstein_dist_self_eq_zero

theoremverified

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

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.

  1. 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.

    lines 4–9

      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
  2. 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 π.

    lines 10–12

      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 [π]
  3. 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.

    lines 13–15

    uses graph_wasserstein_dist_le_of_plan

      have hle : graph_wasserstein_dist G μ μ ≤ 0 := by
        have := graph_wasserstein_dist_le_of_plan G μ μ π hπ h1 h2
        rwa [hcost] at this
  4. 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.

    lines 16–21

    uses le_csInf, Finset.sum_nonneg, mul_nonneg

      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)
  5. 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.

    line 22

    uses le_antisymm

      exact 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.

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

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
See it in the graphDiscuss this resultChallenge it