AFTD Auto-Formalizing Theoretical Domains

graph_wasserstein_dist_le_of_plan

theoremverified

The Wasserstein distance is at most the cost of any transport plan.

Statement

theorem graph_wasserstein_dist_le_of_plan {V : Type*} [Fintype V] (G : SimpleGraph V)
    (μ ν : V → ℝ) (π : V → V → ℝ) (hπ : ∀ a b, 0 ≤ π a b) (h1 : ∀ a, ∑ b, π a b = μ a)
    (h2 : ∀ b, ∑ a, π a b = ν b) :
    graph_wasserstein_dist G μ ν ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b
Source
Helper for the curvature computations of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature) (upper bounds on W by explicit plans, as in the proof of Lemma 3.2).
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
Used by 9

The proof, explained

The graph Wasserstein distance is defined as the infimum of the total transport cost over all valid transport plans between μ and ν. The proof applies `csInf_le`, which states that the infimum of a set bounded below is at most any of its elements. It establishes that 0 is a lower bound because graph distances and plan weights are non-negative, and concludes by observing that the assumed plan π is a valid coupling whose cost belongs to the set.

  1. To show that the Wasserstein distance is at most the transport cost of π, it suffices to show that the set of transport costs is bounded below and that the cost of π is an element of that set.

    By definition, the graph Wasserstein distance is the infimum of all transport costs across valid plans coupling μ and ν. By `csInf_le`, the infimum of a non-empty set bounded below is at most any of its elements.

    line 5

    uses csInf_le

      apply csInf_le
  2. The set of transport costs is bounded below by 0.

    We provide 0 as a candidate lower bound. For any valid coupling p and its associated transport cost c = ∑ a, ∑ b, dist(a, b) * p(a, b), the distances dist(a, b) are non-negative and the weights p(a, b) are non-negative. By `mul_nonneg`, each term in the sum is non-negative, and by `Finset.sum_nonneg`, the double sum of non-negative reals is non-negative. Hence 0 ≤ c.

    lines 6–8

    uses Finset.sum_nonneg, mul_nonneg

      · refine ⟨0, ?_⟩
        rintro c ⟨p, hp, -, -, rfl⟩
        exact Finset.sum_nonneg fun a _ => Finset.sum_nonneg fun b _ => mul_nonneg (by positivity) (hp a b)
  3. The cost of π belongs to the set of transport costs.

    The given plan π is non-negative by hπ and has marginals μ and ν by h1 and h2, so its cost is indeed a member of the set of transport costs between μ and ν.

    line 9

      · exact ⟨π, hπ, h1, h2, rfl⟩
csInf_le
In a conditionally complete lattice, the infimum of a set that is bounded below is less than or equal to any element of that set.
Finset.sum_nonneg
A finite sum of non-negative elements is non-negative.
mul_nonneg
The product of two non-negative elements is non-negative.

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_le_of_plan {V : Type*} [Fintype V] (G : SimpleGraph V)    (μ ν : V → ℝ) (π : V → V → ℝ) (hπ : ∀ a b, 0 ≤ π a b) (h1 : ∀ a, ∑ b, π a b = μ a)    (h2 : ∀ b, ∑ a, π a b = ν b) :    graph_wasserstein_dist G μ ν ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b := by  apply csInf_le  · refine ⟨0, ?_⟩    rintro c ⟨p, hp, -, -, rfl⟩    exact Finset.sum_nonneg fun a _ => Finset.sum_nonneg fun b _ => mul_nonneg (by positivity) (hp a b)  · exact ⟨π, hπ, h1, h2, rfl⟩
See it in the graphDiscuss this resultChallenge it