AFTD Auto-Formalizing Theoretical Domains

graph_wasserstein_dist_ge_of_forall_plan

theoremverified

A lower bound on the cost of every transport plan between two probability measures is a lower bound on their Wasserstein distance.

Statement

theorem graph_wasserstein_dist_ge_of_forall_plan {V : Type*} [Fintype V] (G : SimpleGraph V)
    (μ ν : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) (hν : ∀ b, 0 ≤ ν b) (hμ1 : ∑ a, μ a = 1)
    (hν1 : ∑ b, ν b = 1) (c : ℝ)
    (h : ∀ π : V → V → ℝ, (∀ a b, 0 ≤ π a b) → (∀ a, ∑ b, π a b = μ a) →
      (∀ b, ∑ a, π a b = ν b) → c ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b) :
    c ≤ graph_wasserstein_dist G μ ν
Source
Helper for graph_lly_curvature_le_two_div_dist (OP-164, arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature)).
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 1
  • graph_wasserstein_dist_mix_dirac_leMixing with point masses: W(tμ + (1−t)δ_x, tν + (1−t)δ_y) ≤ t W(μ, ν) + (1−t) d(x, y) for probability measures μ, ν and t ∈ [0, 1].

The proof, explained

The Wasserstein distance on the graph is defined as the infimum of the transport costs over all valid couplings between μ and ν. The proof applies `le_csInf`, reducing the lower bound to two checks: that the set of couplings is nonempty, and that c lower-bounds the cost of every coupling. Nonemptiness is established by taking the independent product coupling π(a, b) = μ(a) * ν(b), and the assumed universal lower bound on transport plans directly bounds the cost of every coupling.

  1. It suffices to show that the set of transport costs is nonempty and that c is a lower bound for every element of that set.

    By definition, the Wasserstein distance is the infimum (`sInf`) of the set of transport costs across all admissible transport plans (couplings) between μ and ν. Lemma `le_csInf` states that c is bounded below by the infimum of a set provided the set is nonempty and c is at most every element of the set.

    lines 7–8

    uses le_csInf

      unfold graph_wasserstein_dist
      apply le_csInf
  2. The set of transport costs is nonempty.

    We exhibit the independent product coupling π(a, b) = μ(a) * ν(b). Since μ and ν are pointwise non-negative, π is non-negative everywhere (`mul_nonneg`). Factoring μ(a) out of the sum over b (`Finset.mul_sum`) and using the total mass assumption ∑ b, ν(b) = 1 (`mul_one`) establishes the first marginal constraint. Symmetrically, factoring ν(b) out of the sum over a (`Finset.sum_mul`) and using ∑ a, μ(a) = 1 (`one_mul`) establishes the second marginal constraint.

    lines 9–11

    uses mul_nonneg, Finset.mul_sum, mul_one, Finset.sum_mul, one_mul

      · refine ⟨_, fun a b => μ a * ν b, fun a b => mul_nonneg (hμ a) (hν b), ?_, ?_, rfl⟩
        · intro a; rw [← Finset.mul_sum, hν1, mul_one]
        · intro b; rw [← Finset.sum_mul, hμ1, one_mul]
  3. c is a lower bound for every transport cost in the set.

    Any cost in the set is the transport cost of an admissible coupling π satisfying non-negativity and both marginal conditions. The hypothesis h immediately implies that c is at most this transport cost.

    lines 12–13

      · rintro c' ⟨π, h0, h1, h2, rfl⟩
        exact h π h0 h1 h2
le_csInf
A lower bound for every element of a nonempty set is a lower bound for its infimum.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
Finset.mul_sum
Left-distributivity of multiplication over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
mul_one
Multiplying a number by 1 on the right leaves it unchanged: a * 1 = a.
Finset.sum_mul
Right-distributivity of multiplication over a finite sum: (∑ i, f i) * a = ∑ i, f i * a.
one_mul
Multiplying a number by 1 on the left leaves it unchanged: 1 * a = a.

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_ge_of_forall_plan {V : Type*} [Fintype V] (G : SimpleGraph V)    (μ ν : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) (hν : ∀ b, 0 ≤ ν b) (hμ1 : ∑ a, μ a = 1)    (hν1 : ∑ b, ν b = 1) (c : ℝ)    (h : ∀ π : V → V → ℝ, (∀ a b, 0 ≤ π a b) → (∀ a, ∑ b, π a b = μ a) →      (∀ b, ∑ a, π a b = ν b) → c ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b) :    c ≤ graph_wasserstein_dist G μ ν := by  unfold graph_wasserstein_dist  apply le_csInf  · refine ⟨_, fun a b => μ a * ν b, fun a b => mul_nonneg (hμ a) (hν b), ?_, ?_, rfl⟩    · intro a; rw [← Finset.mul_sum, hν1, mul_one]    · intro b; rw [← Finset.sum_mul, hμ1, one_mul]  · rintro c' ⟨π, h0, h1, h2, rfl⟩    exact h π h0 h1 h2
See it in the graphDiscuss this resultChallenge it