graph_wasserstein_dist_ge_of_forall_plan
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.
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.
uses
le_csInfunfold graph_wasserstein_dist apply le_csInf
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.
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]
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.
· 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
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_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