AFTD Auto-Formalizing Theoretical Domains

graph_wasserstein_dist_ge_of_lipschitz

theoremverified

Weak Kantorovich duality: for probability measures μ, ν and any function f with f(a) − f(b) ≤ d(a, b), Σ f μ − Σ f ν ≤ W(μ, ν).

Statement

theorem graph_wasserstein_dist_ge_of_lipschitz {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) (f : V → ℝ) (hf : ∀ a b, f a - f b ≤ (G.dist a b : ℝ)) :
    ∑ a, f a * μ a - ∑ b, f b * ν b ≤ graph_wasserstein_dist G μ ν
Source
Helper for the curvature computations of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature); the easy half of the Kantorovich duality quoted in Sec. 2.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 7

The proof, explained

The Wasserstein distance W(μ, ν) is defined as the infimum of the transport costs ∑_{a,b} d(a, b) π(a, b) over all couplings π of μ and ν. The proof first applies `le_csInf`, showing nonemptiness of the set of couplings by exhibiting the independent product coupling π(a, b) = μ(a) ν(b). It then shows that ∑ f μ - ∑ f ν is a lower bound for every transport cost: for any coupling π, expressing both marginal expectations as double sums over π gives ∑ f μ - ∑ f ν = ∑_{a,b} (f(a) - f(b)) π(a, b), which is bounded termwise by ∑_{a,b} d(a, b) π(a, b) using the 1-Lipschitz hypothesis f(a) - f(b) ≤ d(a, b) and non-negativity of π.

  1. It suffices to show that the set of coupling transport costs between μ and ν is nonempty and that ∑ a, f a * μ a - ∑ b, f b * ν b is a lower bound for every transport cost in that set.

    The Wasserstein distance is defined as the infimum of the transport costs ∑ a, ∑ b, d(a, b) * π a b over all couplings π of μ and ν. By `le_csInf`, bounding an expression from above by an infimum reduces to checking that the underlying set is nonempty and that the expression is a lower bound for every element of that set.

    line 5

    uses le_csInf

      apply le_csInf
  2. The set of transport costs of couplings between μ and ν is nonempty.

    The independent product coupling π(a, b) = μ(a) * ν(b) provides an explicit witness. Non-negativity π(a, b) ≥ 0 follows from non-negativity of μ and ν via `mul_nonneg`. Summing over b gives ∑ b, μ(a) * ν(b) = μ(a) * (∑ b, ν(b)) = μ(a) * 1 = μ(a) using `Finset.mul_sum`, the total mass hypothesis hν1, and `mul_one`. Similarly, summing over a yields ∑ a, μ(a) * ν(b) = (∑ a, μ(a)) * ν(b) = 1 * ν(b) = ν(b) using `Finset.sum_mul`, hμ1, and `one_mul`.

    lines 6–8

    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. For any coupling π of μ and ν, the expectations under μ and ν can be rewritten as double sums over π: ∑ a, f a * μ a = ∑ a, ∑ b, f a * π a b and ∑ b, f b * ν b = ∑ a, ∑ b, f b * π a b.

    Let π be an arbitrary coupling with non-negative entries and marginals μ and ν. For the first equality, since μ(a) = ∑ b, π a b, distributing f(a) over the sum via `Finset.mul_sum` gives f(a) * μ(a) = ∑ b, f(a) * π(a, b), which extends to the outer sum by `Finset.sum_congr`. For the second equality, swapping the double sum with `Finset.sum_comm` and applying the second marginal condition ν(b) = ∑ a, π a b via `Finset.mul_sum` and `Finset.sum_congr` gives the analogous double-sum representation for the ν-expectation.

    lines 9–16

    uses Finset.sum_congr, Finset.mul_sum, Finset.sum_comm

      · rintro c ⟨π, h0, h1, h2, rfl⟩
        have e1 : ∑ a, f a * μ a = ∑ a, ∑ b, f a * π a b := by
          refine Finset.sum_congr rfl fun a _ => ?_
          rw [← h1 a, Finset.mul_sum]
        have e2 : ∑ b, f b * ν b = ∑ a, ∑ b, f b * π a b := by
          rw [Finset.sum_comm]
          refine Finset.sum_congr rfl fun b _ => ?_
          rw [← h2 b, Finset.mul_sum]
  4. The difference ∑ a, f a * μ a - ∑ b, f b * ν b is bounded above by the transport cost ∑ a, ∑ b, d(a, b) * π a b.

    Rewriting both expectations using the double sums from the previous step and combining them via `Finset.sum_sub_distrib`, the difference becomes ∑ a, ∑ b, (f(a) * π(a, b) - f(b) * π(a, b)). Applying `Finset.sum_le_sum` across both outer and inner summations reduces the goal to proving the inequality termwise. Rewriting f(a) * π(a, b) - f(b) * π(a, b) as (f(a) - f(b)) * π(a, b) via `sub_mul`, the termwise inequality follows by `mul_le_mul_of_nonneg_right` from the 1-Lipschitz condition f(a) - f(b) ≤ d(a, b) and the coupling non-negativity π(a, b) ≥ 0.

    lines 17–22

    uses Finset.sum_sub_distrib, Finset.sum_le_sum, sub_mul, mul_le_mul_of_nonneg_right

        rw [e1, e2, ← Finset.sum_sub_distrib]
        refine Finset.sum_le_sum fun a _ => ?_
        rw [← Finset.sum_sub_distrib]
        refine Finset.sum_le_sum fun b _ => ?_
        rw [← sub_mul]
        exact mul_le_mul_of_nonneg_right (hf a b) (h0 a b)
le_csInf
In a conditionally complete lattice, an element a is at most sInf s if s is nonempty and a is a lower bound for every element of s.
mul_nonneg
The product of two non-negative numbers is non-negative.
Finset.mul_sum
Left-multiplication distributes over a finite sum: a * ∑ i, f i = ∑ i, a * f i.
mul_one
Multiplying on the right by 1 leaves an element unchanged: a * 1 = a.
Finset.sum_mul
Right-multiplication distributes over a finite sum: (∑ i, f i) * a = ∑ i, f i * a.
one_mul
Multiplying on the left by 1 leaves an element unchanged: 1 * a = a.
Finset.sum_congr
Two finite sums over the same index set are equal if their terms are equal for every index.
Finset.sum_comm
The order of two nested finite summations can be swapped: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.sum_sub_distrib
The sum of termwise differences is the difference of the sums: ∑ x, (f x - g x) = ∑ x, f x - ∑ x, g x.
Finset.sum_le_sum
If f i ≤ g i for every index i in a finite set, then ∑ i, f i ≤ ∑ i, g i.
sub_mul
Right-distributivity of subtraction over multiplication: (a - b) * c = a * c - b * c.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality by a non-negative element on the right preserves the inequality: if b ≤ c and 0 ≤ a, then b * a ≤ c * 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_lipschitz {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) (f : V → ℝ) (hf : ∀ a b, f a - f b ≤ (G.dist a b : ℝ)) :    ∑ a, f a * μ a - ∑ b, f b * ν b ≤ graph_wasserstein_dist G μ ν := by  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⟩    have e1 : ∑ a, f a * μ a = ∑ a, ∑ b, f a * π a b := by      refine Finset.sum_congr rfl fun a _ => ?_      rw [← h1 a, Finset.mul_sum]    have e2 : ∑ b, f b * ν b = ∑ a, ∑ b, f b * π a b := by      rw [Finset.sum_comm]      refine Finset.sum_congr rfl fun b _ => ?_      rw [← h2 b, Finset.mul_sum]    rw [e1, e2, ← Finset.sum_sub_distrib]    refine Finset.sum_le_sum fun a _ => ?_    rw [← Finset.sum_sub_distrib]    refine Finset.sum_le_sum fun b _ => ?_    rw [← sub_mul]    exact mul_le_mul_of_nonneg_right (hf a b) (h0 a b)
See it in the graphDiscuss this resultChallenge it