graph_wasserstein_dist_mix_dirac_le
Mixing 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].
Statement
theorem graph_wasserstein_dist_mix_dirac_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (μ ν : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) (hν : ∀ b, 0 ≤ ν b) (hμ1 : ∑ a, μ a = 1) (hν1 : ∑ b, ν b = 1) (x y : V) (t : ℝ) (ht0 : 0 ≤ t) (ht1 : t ≤ 1) : graph_wasserstein_dist G (fun v => t * μ v + (1 - t) * (if v = x then 1 else 0)) (fun v => t * ν v + (1 - t) * (if v = y then 1 else 0)) ≤ t * graph_wasserstein_dist G μ ν + (1 - t) * (G.dist x y : ℝ)
- 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 3
- graph_wasserstein_dist_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
- graph_wasserstein_dist_ge_of_forall_planA lower bound on the cost of every transport plan between two probability measures is a lower bound on their Wasserstein distance.
- 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 2
- 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_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
The proof, explained
To bound the Wasserstein distance between the mixture measures t μ + (1 - t) δ_x and t ν + (1 - t) δ_y, the proof constructs the interpolated coupling t π + (1 - t) δ_{(x, y)} for an arbitrary transport plan π between μ and ν. The cost of this interpolated coupling is t · cost(π) + (1 - t) d(x, y), which gives an upper bound on the mixed Wasserstein distance for every coupling π. Finally, a case split on t = 0 versus t > 0 uses the infimum property of the Wasserstein distance (via `graph_wasserstein_dist_ge_of_forall_plan`) to pass from the bound on all couplings to the Wasserstein distance W(μ, ν).
For any transport plan π between μ and ν, the convex combination t π + (1 - t) δ_{(x, y)} is a valid transport plan between t μ + (1 - t) δ_x and t ν + (1 - t) δ_y, and its cost bounds the Wasserstein distance between the mixtures.
We introduce an arbitrary coupling π between μ and ν and test the mixture candidate π' defined by π'(a, b) = t π(a, b) + (1 - t) (if a = x and b = y then 1 else 0). By `graph_wasserstein_dist_le_of_plan`, the Wasserstein distance between the two mixture measures is bounded above by the expected distance under any valid coupling. Non-negativity of π' follows because 0 ≤ t ≤ 1 and π is non-negative (checked by `positivity`). Summing π'(a, b) over b yields t μ(a) + (1 - t) δ_x(a) using the marginal property of π and the definition of the indicator; similarly, summing over a gives the second marginal t ν(b) + (1 - t) δ_y(b).
uses
graph_wasserstein_dist_le_of_plan,Finset.sum_add_distrib,Finset.mul_sumhave key : ∀ π : V → V → ℝ, (∀ a b, 0 ≤ π a b) → (∀ a, ∑ b, π a b = μ a) → (∀ b, ∑ a, π a b = ν b) → graph_wasserstein_dist G (fun v => t * μ v + (1 - t) * (if v = x then 1 else 0)) (fun v => t * ν v + (1 - t) * (if v = y then 1 else 0)) ≤ t * (∑ a, ∑ b, (G.dist a b : ℝ) * π a b) + (1 - t) * (G.dist x y : ℝ) := by intro π h0 h1 h2 calc _ ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * (t * π a b + (1 - t) * (if a = x then (if b = y then 1 else 0) else 0)) := by apply graph_wasserstein_dist_le_of_plan · intro a b have := h0 a b have h1t : 0 ≤ 1 - t := by linarith split_ifs <;> positivity · intro a rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, h1 a] by_cases ha : a = x <;> simp [ha] · intro b rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, h2 b] by_cases hb : b = y <;> simp [hb]
The transport cost of the mixture coupling equals t (∑ a b, dist(a, b) π(a, b)) + (1 - t) dist(x, y), completing the key lemma.
The double sum of the cost d(a, b) π'(a, b) splits into two parts via `Finset.sum_add_distrib` and `mul_add`. The first part factors out t to give t ∑ a b, d(a, b) π(a, b). In the second part, summing d(a, b) (1 - t) 1_{a = x, b = y} collapses to the single term (1 - t) d(x, y) at a = x and b = y, evaluated by `Finset.sum_ite_eq` and ring arithmetic.
uses
mul_add,Finset.sum_add_distrib,Finset.mul_sum,Finset.sum_congr,mul_ite,mul_one,mul_zero,Finset.sum_ite_eq',Finset.sum_ite_eq,Finset.mem_univ,if_true,Finset.sum_ite_irrel,Finset.sum_const_zero_ = _ := by simp only [mul_add, Finset.sum_add_distrib] congr 1 · rw [Finset.mul_sum] refine Finset.sum_congr rfl fun a _ => ?_ rw [Finset.mul_sum] refine Finset.sum_congr rfl fun b _ => ?_ ring · simp only [mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_ite_irrel, Finset.sum_const_zero] ring
When t = 0, the inequality holds.
We split into cases using `eq_or_lt_of_le`. When t = 0, the mixture measures reduce to the Dirac masses δ_x and δ_y. We instantiate the key lemma with the product coupling π(a, b) = μ(a) ν(b), which is non-negative and has the correct marginals since ∑ μ = 1 and ∑ ν = 1. Specializing the key inequality to t = 0 eliminates the transport cost of π and leaves W(δ_x, δ_y) ≤ d(x, y).
uses
eq_or_lt_of_le,mul_nonneg,Finset.mul_sum,mul_one,Finset.sum_mul,one_mulrcases eq_or_lt_of_le ht0 with rfl | htpos · have := key (fun a b => μ a * ν b) (fun a b => mul_nonneg (hμ a) (hν b)) (fun a => by rw [← Finset.mul_sum, hν1, mul_one]) (fun b => by rw [← Finset.sum_mul, hμ1, one_mul]) simpa using this
When t > 0, the quantity (W(t μ + (1 - t) δ_x, t ν + (1 - t) δ_y) - (1 - t) d(x, y)) / t is a lower bound for W(μ, ν).
By `graph_wasserstein_dist_ge_of_forall_plan`, to bound a constant below W(μ, ν), it suffices to show that the constant is at most the cost of every transport plan π between μ and ν. For any valid coupling π, dividing the inequality from the key lemma by t > 0 (via `div_le_iff₀`) directly shows that the constant is bounded above by ∑ a b, d(a, b) π(a, b).
uses
graph_wasserstein_dist_ge_of_forall_plan,div_le_iff₀· have hlow : (graph_wasserstein_dist G (fun v => t * μ v + (1 - t) * (if v = x then 1 else 0)) (fun v => t * ν v + (1 - t) * (if v = y then 1 else 0)) - (1 - t) * (G.dist x y : ℝ)) / t ≤ graph_wasserstein_dist G μ ν := by apply graph_wasserstein_dist_ge_of_forall_plan G μ ν hμ hν hμ1 hν1 intro π h0 h1 h2 rw [div_le_iff₀ htpos] have := key π h0 h1 h2 linarith
Multiplying by t yields the desired mixing inequality.
Clearing the division by t > 0 in the previous lower bound via `div_le_iff₀` and rearranging linearly with `linarith` completes the proof.
uses
div_le_iff₀rw [div_le_iff₀ htpos] at hlow linarith
graph_wasserstein_dist_le_of_plan- The Wasserstein distance between two probability measures on a graph is bounded from above by the cost of any valid transport plan coupling them.
graph_wasserstein_dist_ge_of_forall_plan- A constant c is a lower bound for the Wasserstein distance between probability measures μ and ν if c is bounded above by the transport cost of every valid transport plan between them.
Finset.sum_add_distrib- Addition inside a finite sum distributes: ∑ (f x + g x) = ∑ f x + ∑ g x.
Finset.mul_sum- Multiplication distributes from the left over a finite sum: a * ∑ f i = ∑ (a * f i).
Finset.sum_mul- Multiplication distributes from the right over a finite sum: (∑ f i) * a = ∑ (f i * a).
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every index.
Finset.sum_ite_eq'- Summing an expression that is non-zero only when the index equals a evaluates to the value at a (provided a is in the set).
Finset.sum_ite_eq- Summing an expression that is non-zero only when a equals the index evaluates to the value at a (provided a is in the set).
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
if_true- A conditional expression whose condition is True simplifies to the `then` branch.
Finset.sum_ite_irrel- A condition independent of the summation variable can be factored outside the finite sum.
Finset.sum_const_zero- The sum of the constant zero over any finite set is 0.
mul_ite- Multiplication distributes over an `if-then-else` expression: a * (if P then b else c) = if P then a * b else a * c.
mul_one- Multiplying by 1 on the right leaves an element unchanged: a * 1 = a.
one_mul- Multiplying by 1 on the left leaves an element unchanged: 1 * a = a.
mul_zero- Multiplying by 0 on the right gives 0: a * 0 = 0.
mul_add- Multiplication distributes over addition: a * (b + c) = a * b + a * c.
eq_or_lt_of_le- In a partial order, a ≤ b implies a = b or a < b.
mul_nonneg- The product of two non-negative elements is non-negative: 0 ≤ a and 0 ≤ b imply 0 ≤ a * b.
div_le_iff₀- For a positive divisor c > 0, the inequality b / c ≤ a is equivalent to b ≤ a * c.
- Rather than relying on the existence of an optimal transport plan achieving the infimum (which would require a compactness or linear programming argument), the formal proof establishes an upper bound for every valid coupling π (the key lemma) and then uses the dual property of the infimum via `graph_wasserstein_dist_ge_of_forall_plan` to conclude.
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_mix_dirac_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (μ ν : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) (hν : ∀ b, 0 ≤ ν b) (hμ1 : ∑ a, μ a = 1) (hν1 : ∑ b, ν b = 1) (x y : V) (t : ℝ) (ht0 : 0 ≤ t) (ht1 : t ≤ 1) : graph_wasserstein_dist G (fun v => t * μ v + (1 - t) * (if v = x then 1 else 0)) (fun v => t * ν v + (1 - t) * (if v = y then 1 else 0)) ≤ t * graph_wasserstein_dist G μ ν + (1 - t) * (G.dist x y : ℝ) := by have key : ∀ π : V → V → ℝ, (∀ a b, 0 ≤ π a b) → (∀ a, ∑ b, π a b = μ a) → (∀ b, ∑ a, π a b = ν b) → graph_wasserstein_dist G (fun v => t * μ v + (1 - t) * (if v = x then 1 else 0)) (fun v => t * ν v + (1 - t) * (if v = y then 1 else 0)) ≤ t * (∑ a, ∑ b, (G.dist a b : ℝ) * π a b) + (1 - t) * (G.dist x y : ℝ) := by intro π h0 h1 h2 calc _ ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * (t * π a b + (1 - t) * (if a = x then (if b = y then 1 else 0) else 0)) := by apply graph_wasserstein_dist_le_of_plan · intro a b have := h0 a b have h1t : 0 ≤ 1 - t := by linarith split_ifs <;> positivity · intro a rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, h1 a] by_cases ha : a = x <;> simp [ha] · intro b rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, h2 b] by_cases hb : b = y <;> simp [hb] _ = _ := by simp only [mul_add, Finset.sum_add_distrib] congr 1 · rw [Finset.mul_sum] refine Finset.sum_congr rfl fun a _ => ?_ rw [Finset.mul_sum] refine Finset.sum_congr rfl fun b _ => ?_ ring · simp only [mul_ite, mul_one, mul_zero, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_ite_irrel, Finset.sum_const_zero] ring rcases eq_or_lt_of_le ht0 with rfl | htpos · have := key (fun a b => μ a * ν b) (fun a b => mul_nonneg (hμ a) (hν b)) (fun a => by rw [← Finset.mul_sum, hν1, mul_one]) (fun b => by rw [← Finset.sum_mul, hμ1, one_mul]) simpa using this · have hlow : (graph_wasserstein_dist G (fun v => t * μ v + (1 - t) * (if v = x then 1 else 0)) (fun v => t * ν v + (1 - t) * (if v = y then 1 else 0)) - (1 - t) * (G.dist x y : ℝ)) / t ≤ graph_wasserstein_dist G μ ν := by apply graph_wasserstein_dist_ge_of_forall_plan G μ ν hμ hν hμ1 hν1 intro π h0 h1 h2 rw [div_le_iff₀ htpos] have := key π h0 h1 h2 linarith rw [div_le_iff₀ htpos] at hlow linarith