graph_wasserstein_dist_ge_of_lipschitz
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
- graph_lly_curvature_of_twinsIf x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- graph_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- graph_ollivier_curvature_div_le_two_div_distIn a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, y).
- graph_lly_curvature_le_two_div_distFor distinct vertices x, y of a finite connected graph, κ_LLY(x, y) ≤ 2/d(x, y).
- graph_lly_curvature_le_of_lipschitz_cut_potentialKantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y),…
- five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
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 π.
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.
uses
le_csInfapply le_csInfThe 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`.
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]
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.
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]
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.
uses
Finset.sum_sub_distrib,Finset.sum_le_sum,sub_mul,mul_le_mul_of_nonneg_rightrw [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
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_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)