wasserstein_dist_le_of_diameter_two
On any graph of diameter at most 2, the Wasserstein distance between probability measures μ and ν with d(x, y) = 1 is bounded by 2 - 2 * S0 - m_xy, where S0 = ∑ min(μ v, ν v) and m_xy is the minimum excess mass at x and y.
Statement
theorem wasserstein_dist_le_of_diameter_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hdist2 : ∀ a b : V, (G.dist a b : ℝ) ≤ 2) (μ ν : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) (hν : ∀ b, 0 ≤ ν b) (hμ1 : ∑ a, μ a = 1) (hν1 : ∑ b, ν b = 1) (x y : V) (hxy_dist : (G.dist x y : ℝ) = 1) : let S0 := ∑ v, min (μ v) (ν v) let μ1 (a : V) := μ a - min (μ a) (ν a) let ν1 (b : V) := ν b - min (μ b) (ν b) let m_xy := min (μ1 x) (ν1 y) graph_wasserstein_dist G μ ν ≤ 2 - 2 * S0 - m_xy
- Source
- step towards five_vertex_min_degree_two_wasserstein_lt_one
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- graph_wasserstein_dist_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
- 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
- five_vertex_min_degree_two_wasserstein_lt_oneEvery connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
The proof, explained
To bound the Wasserstein distance between probability measures μ and ν on a graph of diameter at most 2, we construct an explicit three-stage transport plan π. First, mass min(μ v, ν v) is kept in place at each vertex v at distance 0, accounting for total mass S0. Second, the maximum possible excess mass m = min(m1 x, n1 y) is sent from x to y along the edge between them at distance d(x, y) = 1, costing 1 * m. Finally, the remaining mass rem = 1 - S0 - m is transported via an independent product coupling, where the graph diameter bound d(a, b) ≤ 2 ensures this remainder costs at most 2 * rem. Summing these costs gives 0 + m + 2(1 - S0 - m) = 2 - 2 * S0 - m, yielding the desired upper bound.
Define the intermediate excess distributions and the three-stage transport plan π
Simplify the let-bindings and define the retained diagonal mass S0 = ∑ min(μ v, ν v), the excess masses m1(a) = μ(a) - min(μ a, ν a) and n1(b) = ν(b) - min(μ b, ν b), the mass m = min(m1 x, n1 y) to be transported along the edge (x, y), the remaining excess mass rem = 1 - S0 - m, the adjusted excesses μ2 and ν2, and the candidate coupling π consisting of diagonal retention, direct edge transport from x to y, and an independent product coupling of the remainder.
dsimp only set S0 : ℝ := ∑ v, min (μ v) (ν v) with hS0 set m1 : V → ℝ := (fun a => μ a - min (μ a) (ν a)) with hm1 set n1 : V → ℝ := (fun b => ν b - min (μ b) (ν b)) with hn1 set m : ℝ := min (μ x - min (μ x) (ν x)) (ν y - min (μ y) (ν y)) with hm have hm_eq : m = min (m1 x) (n1 y) := by rw [hm, hm1, hn1] set rem : ℝ := 1 - S0 - m with hrem set μ2 : V → ℝ := (fun a => m1 a - (if a = x then m else 0)) with hμ2 set ν2 : V → ℝ := (fun b => n1 b - (if b = y then m else 0)) with hν2 set π : V → V → ℝ := (fun a b => (if a = b then min (μ a) (ν a) else 0) + (if b = y then (if a = x then m else 0) else 0) + μ2 a * ν2 b / rem) with hπ
The excess measures m1, n1 are non-negative, have total mass 1 - S0, and satisfy 0 ≤ m ≤ 1 - S0, so rem ≥ 0
Because min(μ a, ν a) ≤ μ a and min(μ b, ν b) ≤ ν b, m1 and n1 are pointwise non-negative. Subtracting the sum of minimums from the unit total mass of μ and ν gives ∑ m1(a) = ∑ n1(b) = 1 - S0. The mass m is non-negative and bounded by m1(x) ≤ ∑ m1(a) = 1 - S0, which ensures rem = 1 - S0 - m ≥ 0.
uses
sub_nonneg.mpr,min_le_left,min_le_right,Finset.sum_sub_distrib,le_min,Finset.single_le_sum,Finset.mem_univhave hμ1_nonneg : ∀ a, 0 ≤ m1 a := by intro a; rw [hm1]; exact sub_nonneg.mpr (min_le_left _ _) have hν1_nonneg : ∀ b, 0 ≤ n1 b := by intro b; rw [hn1]; exact sub_nonneg.mpr (min_le_right _ _) have hsum_m1 : ∑ a, m1 a = 1 - S0 := by have h : ∑ a, m1 a = ∑ a, (μ a - min (μ a) (ν a)) := by rw [hm1] rw [h, Finset.sum_sub_distrib, hμ1, hS0] have hsum_n1 : ∑ b, n1 b = 1 - S0 := by have h : ∑ b, n1 b = ∑ b, (ν b - min (μ b) (ν b)) := by rw [hn1] rw [h, Finset.sum_sub_distrib, hν1, hS0] have hm_le_m1 : m ≤ m1 x := by rw [hm_eq]; exact min_le_left _ _ have hm_le_n1 : m ≤ n1 y := by rw [hm_eq]; exact min_le_right _ _ have hm_nonneg : 0 ≤ m := by rw [hm_eq]; exact le_min (hμ1_nonneg x) (hν1_nonneg y) have hm_le : m ≤ 1 - S0 := by calc m ≤ m1 x := hm_le_m1 _ ≤ ∑ a, m1 a := Finset.single_le_sum (fun a _ => hμ1_nonneg a) (Finset.mem_univ x) _ = 1 - S0 := hsum_m1 have hrem_nonneg : 0 ≤ rem := by rw [hrem]; linarith
The second-stage excess measures μ2 and ν2 are non-negative and each sum to rem
At x, μ2(x) = m1(x) - m ≥ 0 because m ≤ m1(x); for all other vertices, μ2(a) = m1(a) ≥ 0. Symmetrically, ν2 is pointwise non-negative. Summing μ2 over V subtracts m from ∑ m1(a) = 1 - S0, yielding exactly rem, and similarly for ν2.
uses
if_pos,sub_nonneg,if_neg,Finset.sum_sub_distrib,Finset.sum_ite_eq',Finset.mem_univ,if_truehave hμ2_nonneg : ∀ a, 0 ≤ μ2 a := by intro a simp only [hμ2] by_cases h : a = x · rw [if_pos h, sub_nonneg] rw [h]; exact hm_le_m1 · rw [if_neg h]; simpa using hμ1_nonneg a have hν2_nonneg : ∀ b, 0 ≤ ν2 b := by intro b simp only [hν2] by_cases h : b = y · rw [if_pos h, sub_nonneg] rw [h]; exact hm_le_n1 · rw [if_neg h]; simpa using hν1_nonneg b have hsum_μ2 : ∑ a, μ2 a = rem := by rw [hμ2, hrem, Finset.sum_sub_distrib, Finset.sum_ite_eq'] simp only [Finset.mem_univ, if_true] rw [hsum_m1] have hsum_ν2 : ∑ b, ν2 b = rem := by rw [hν2, hrem, Finset.sum_sub_distrib, Finset.sum_ite_eq'] simp only [Finset.mem_univ, if_true] rw [hsum_n1]
The row and column sums of the independent remainder coupling equal μ2(a) and ν2(b) respectively
If rem = 0, then since μ2 ≥ 0 and ∑ μ2 = 0, μ2 is identically zero and the sum vanishes. If rem ≠ 0, factoring out μ2(a) / rem gives (μ2(a) / rem) * ∑ ν2(b) = (μ2(a) / rem) * rem = μ2(a). An identical calculation gives column sums equal to ν2(b).
uses
Finset.sum_eq_zero_iff_of_nonneg,Finset.mem_univ,Finset.sum_eq_zero,Finset.sum_div,Finset.mul_sum,mul_div_cancel_right₀,Finset.sum_mul,mul_div_cancel_left₀have hcoupl_row : ∀ a, ∑ b, μ2 a * ν2 b / rem = μ2 a := by intro a by_cases h0 : rem = 0 · have hz : μ2 a = 0 := by have hsum0 : ∑ b, μ2 b = 0 := by rw [hsum_μ2, h0] exact (Finset.sum_eq_zero_iff_of_nonneg (fun b _ => hμ2_nonneg b)).mp hsum0 a (Finset.mem_univ a) rw [hz] apply Finset.sum_eq_zero; intro b _ rw [h0]; simp · rw [← Finset.sum_div, ← Finset.mul_sum, hsum_ν2] exact mul_div_cancel_right₀ (μ2 a) h0 have hcoupl_col : ∀ b, ∑ a, μ2 a * ν2 b / rem = ν2 b := by intro b by_cases h0 : rem = 0 · have hz : ν2 b = 0 := by have hsum0 : ∑ b, ν2 b = 0 := by rw [hsum_ν2, h0] exact (Finset.sum_eq_zero_iff_of_nonneg (fun b _ => hν2_nonneg b)).mp hsum0 b (Finset.mem_univ b) rw [hz] apply Finset.sum_eq_zero; intro a _ rw [h0]; simp · rw [← Finset.sum_div, ← Finset.sum_mul, hsum_μ2] exact mul_div_cancel_left₀ (ν2 b) h0
The transport plan π is non-negative everywhere
Each of the three terms in π(a, b) is non-negative: min(μ a, ν a) ≥ 0 on the diagonal, m ≥ 0 on (x, y), and the quotient μ2(a) * ν2(b) / rem is non-negative since both numerators and the denominator are non-negative.
uses
if_pos,le_min,if_neg,div_nonneg,mul_nonneghave hπ_nonneg : ∀ a b, 0 ≤ π a b := by intro a b have h1 : (0:ℝ) ≤ (if a = b then min (μ a) (ν a) else 0) := by by_cases h : a = b · rw [if_pos h]; exact le_min (hμ a) (hν a) · rw [if_neg h] have h2 : (0:ℝ) ≤ (if b = y then (if a = x then m else 0) else 0) := by by_cases hby : b = y · rw [if_pos hby] by_cases hax : a = x · rw [if_pos hax]; exact hm_nonneg · rw [if_neg hax] · rw [if_neg hby] have h3 : (0:ℝ) ≤ μ2 a * ν2 b / rem := div_nonneg (mul_nonneg (hμ2_nonneg a) (hν2_nonneg b)) hrem_nonneg simp only [hπ] linarith
The transport plan π has marginals μ and ν
Summing π(a, b) over b yields min(μ a, ν a) from the diagonal, m * 1_{a=x} from the edge term, and μ2(a) = m1(a) - m * 1_{a=x} from the product coupling. These add up to min(μ a, ν a) + m1(a) = μ(a). Symmetrically, summing over a yields ν(b).
uses
Finset.sum_add_distrib,Finset.sum_ite_eq,Finset.sum_ite_eq'have hrow : ∀ a, ∑ b, π a b = μ a := by intro a simp only [hπ] rw [Finset.sum_add_distrib, Finset.sum_add_distrib] have hdiag : ∑ b, (if a = b then min (μ a) (ν a) else 0) = min (μ a) (ν a) := by rw [Finset.sum_ite_eq]; simp have hmxy : ∑ b, (if b = y then (if a = x then m else 0) else 0) = (if a = x then m else 0) := by rw [Finset.sum_ite_eq']; simp rw [hdiag, hmxy, hcoupl_row a] simp only [hμ2, hm1] ring have hcol : ∀ b, ∑ a, π a b = ν b := by intro b simp only [hπ] rw [Finset.sum_add_distrib, Finset.sum_add_distrib] have hdiag : ∑ a, (if a = b then min (μ a) (ν a) else 0) = min (μ b) (ν b) := by rw [Finset.sum_ite_eq']; simp have hmxy : ∑ a, (if b = y then (if a = x then m else 0) else 0) = (if b = y then m else 0) := by by_cases hby : b = y · simp [hby, Finset.sum_ite_eq'] · simp [hby] rw [hdiag, hmxy, hcoupl_col b] simp only [hν2, hn1] ring
The expected transport cost of π is at most 2 - 2 * S0 - m
Split the transport cost into the three stages: the diagonal terms incur distance d(a, a) = 0, contributing 0; the edge term transfers mass m across d(x, y) = 1, contributing 1 * m = m; and every remaining pair has distance d(a, b) ≤ 2 by the diameter bound, so the product coupling contributes at most 2 * rem. The total cost is at most 0 + m + 2 * rem = m + 2 * (1 - S0 - m) = 2 - 2 * S0 - m.
uses
Finset.sum_eq_zero,if_pos,zero_mul,if_neg,mul_zero,mul_ite,Finset.sum_ite_eq',div_nonneg,mul_nonneg,mul_le_mul_of_nonneg_right,Finset.sum_le_sum,Finset.mul_sum,Finset.sum_add_distribhave hcost : ∑ a, ∑ b, (G.dist a b : ℝ) * π a b ≤ 2 - 2 * S0 - m := by have hsplit : ∀ a b, (G.dist a b : ℝ) * π a b = (G.dist a b : ℝ) * (if a = b then min (μ a) (ν a) else 0) + (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0) + (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) := by intro a b; simp only [hπ]; ring have hD : ∑ a, ∑ b, (G.dist a b : ℝ) * (if a = b then min (μ a) (ν a) else 0) = 0 := by apply Finset.sum_eq_zero intro a _ apply Finset.sum_eq_zero intro b _ by_cases h : a = b · rw [if_pos h] have hd : (G.dist a b : ℝ) = 0 := by rw [h]; simp rw [hd, zero_mul] · rw [if_neg h, mul_zero] have hM : ∑ a, ∑ b, (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0) = m := by have inner : ∀ a, ∑ b, (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0) = (G.dist a y : ℝ) * (if a = x then m else 0) := by intro a simp only [mul_ite, mul_zero] rw [Finset.sum_ite_eq']; simp simp only [inner] have inner2 : ∑ a, (G.dist a y : ℝ) * (if a = x then m else 0) = (G.dist x y : ℝ) * m := by simp only [mul_ite, mul_zero] rw [Finset.sum_ite_eq']; simp rw [inner2, hxy_dist]; ring have hC : ∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) ≤ 2 * rem := by by_cases h0 : rem = 0 · have hz : ∀ a b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) = 0 := by intro a b; rw [h0]; simp simp only [hz] simp [h0] · have hle : ∀ a b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) ≤ 2 * (μ2 a * ν2 b / rem) := by intro a b have ht : 0 ≤ μ2 a * ν2 b / rem := div_nonneg (mul_nonneg (hμ2_nonneg a) (hν2_nonneg b)) hrem_nonneg exact mul_le_mul_of_nonneg_right (hdist2 a b) ht calc ∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) ≤ ∑ a, ∑ b, 2 * (μ2 a * ν2 b / rem) := by apply Finset.sum_le_sum; intro a _ apply Finset.sum_le_sum; intro b _ exact hle a b _ = 2 * rem := by have inner : ∀ a, ∑ b, 2 * (μ2 a * ν2 b / rem) = 2 * μ2 a := by intro a; rw [← Finset.mul_sum, hcoupl_row a] simp only [inner] rw [← Finset.mul_sum, hsum_μ2] calc ∑ a, ∑ b, (G.dist a b : ℝ) * π a b = (∑ a, ∑ b, (G.dist a b : ℝ) * (if a = b then min (μ a) (ν a) else 0)) + (∑ a, ∑ b, (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0)) + (∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem)) := by simp only [hsplit, Finset.sum_add_distrib] _ = 0 + m + (∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem)) := by rw [hD, hM] _ ≤ 0 + m + 2 * rem := by linarith _ = 2 - 2 * S0 - m := by rw [hrem]; ring
The Wasserstein distance is bounded by 2 - 2 * S0 - m
Because π is a valid coupling between μ and ν with non-negative entries and correct marginals, the Wasserstein distance, which is the infimum over all transport plans, is bounded by the transport cost of π, which is at most 2 - 2 * S0 - m.
uses
graph_wasserstein_dist_le_of_plancalc graph_wasserstein_dist G μ ν ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b := graph_wasserstein_dist_le_of_plan G μ ν π hπ_nonneg hrow hcol _ ≤ 2 - 2 * S0 - m := hcost
sub_nonneg.mpr- if b ≤ a, then 0 ≤ a - b
min_le_left- the minimum min(a, b) is at most a
min_le_right- the minimum min(a, b) is at most b
Finset.sum_sub_distrib- a sum of differences distributes into the difference of the sums: ∑ (f x - g x) = ∑ f x - ∑ g x
le_min- if c ≤ a and c ≤ b, then c ≤ min(a, b)
Finset.single_le_sum- a single term f(a) is at most the sum ∑ x ∈ s, f(x) over a finite set containing a, provided all terms are non-negative
Finset.mem_univ- every element of a finite type belongs to the universal finset Finset.univ
if_pos- if a condition c holds, then (if c then t else e) = t
sub_nonneg- 0 ≤ a - b if and only if b ≤ a
if_neg- if a condition c does not hold, then (if c then t else e) = e
Finset.sum_ite_eq'- the sum over s of (if x = a then b(x) else 0) is b(a) if a ∈ s, and 0 otherwise
if_true- (if True then t else e) = t
Finset.sum_eq_zero_iff_of_nonneg- a finite sum of non-negative terms is zero if and only if each term is zero
Finset.sum_eq_zero- if every term in a finite sum is zero, the sum is zero
Finset.sum_div- division by a scalar distributes over finite sums: (∑ f i) / a = ∑ (f i / a)
Finset.mul_sum- multiplication by a scalar distributes over finite sums: a * ∑ f i = ∑ (a * f i)
mul_div_cancel_right₀- if b ≠ 0, then a * b / b = a
Finset.sum_mul- multiplication on the right distributes over finite sums: (∑ f i) * a = ∑ (f i * a)
mul_div_cancel_left₀- if a ≠ 0, then a * b / a = b
div_nonneg- if a ≥ 0 and b ≥ 0, then a / b ≥ 0
mul_nonneg- if a ≥ 0 and b ≥ 0, then a * b ≥ 0
Finset.sum_add_distrib- a sum of sums distributes: ∑ (f x + g x) = ∑ f x + ∑ g x
Finset.sum_ite_eq- the sum over s of (if a = x then b(x) else 0) is b(a) if a ∈ s, and 0 otherwise
zero_mul- 0 * a = 0
mul_zero- a * 0 = 0
mul_ite- multiplication distributes over an if-then-else: a * (if P then b else c) = if P then a * b else a * c
mul_le_mul_of_nonneg_right- if b ≤ c and 0 ≤ a, then b * a ≤ c * a
Finset.sum_le_sum- if f(i) ≤ g(i) for all elements i of a finite set, then ∑ f(i) ≤ ∑ g(i)
graph_wasserstein_dist_le_of_plan- the graph Wasserstein distance between μ and ν is at most the transport cost ∑ a, ∑ b, d(a, b) * π(a, b) of any valid coupling π
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.
/-- Wasserstein distance upper bound on diameter ≤ 2 graphs via an explicit 3-stage transport plan. -/theorem wasserstein_dist_le_of_diameter_two {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hdist2 : ∀ a b : V, (G.dist a b : ℝ) ≤ 2) (μ ν : V → ℝ) (hμ : ∀ a, 0 ≤ μ a) (hν : ∀ b, 0 ≤ ν b) (hμ1 : ∑ a, μ a = 1) (hν1 : ∑ b, ν b = 1) (x y : V) (hxy_dist : (G.dist x y : ℝ) = 1) : let S0 := ∑ v, min (μ v) (ν v) let μ1 (a : V) := μ a - min (μ a) (ν a) let ν1 (b : V) := ν b - min (μ b) (ν b) let m_xy := min (μ1 x) (ν1 y) graph_wasserstein_dist G μ ν ≤ 2 - 2 * S0 - m_xy := by dsimp only set S0 : ℝ := ∑ v, min (μ v) (ν v) with hS0 set m1 : V → ℝ := (fun a => μ a - min (μ a) (ν a)) with hm1 set n1 : V → ℝ := (fun b => ν b - min (μ b) (ν b)) with hn1 set m : ℝ := min (μ x - min (μ x) (ν x)) (ν y - min (μ y) (ν y)) with hm have hm_eq : m = min (m1 x) (n1 y) := by rw [hm, hm1, hn1] set rem : ℝ := 1 - S0 - m with hrem set μ2 : V → ℝ := (fun a => m1 a - (if a = x then m else 0)) with hμ2 set ν2 : V → ℝ := (fun b => n1 b - (if b = y then m else 0)) with hν2 set π : V → V → ℝ := (fun a b => (if a = b then min (μ a) (ν a) else 0) + (if b = y then (if a = x then m else 0) else 0) + μ2 a * ν2 b / rem) with hπ have hμ1_nonneg : ∀ a, 0 ≤ m1 a := by intro a; rw [hm1]; exact sub_nonneg.mpr (min_le_left _ _) have hν1_nonneg : ∀ b, 0 ≤ n1 b := by intro b; rw [hn1]; exact sub_nonneg.mpr (min_le_right _ _) have hsum_m1 : ∑ a, m1 a = 1 - S0 := by have h : ∑ a, m1 a = ∑ a, (μ a - min (μ a) (ν a)) := by rw [hm1] rw [h, Finset.sum_sub_distrib, hμ1, hS0] have hsum_n1 : ∑ b, n1 b = 1 - S0 := by have h : ∑ b, n1 b = ∑ b, (ν b - min (μ b) (ν b)) := by rw [hn1] rw [h, Finset.sum_sub_distrib, hν1, hS0] have hm_le_m1 : m ≤ m1 x := by rw [hm_eq]; exact min_le_left _ _ have hm_le_n1 : m ≤ n1 y := by rw [hm_eq]; exact min_le_right _ _ have hm_nonneg : 0 ≤ m := by rw [hm_eq]; exact le_min (hμ1_nonneg x) (hν1_nonneg y) have hm_le : m ≤ 1 - S0 := by calc m ≤ m1 x := hm_le_m1 _ ≤ ∑ a, m1 a := Finset.single_le_sum (fun a _ => hμ1_nonneg a) (Finset.mem_univ x) _ = 1 - S0 := hsum_m1 have hrem_nonneg : 0 ≤ rem := by rw [hrem]; linarith have hμ2_nonneg : ∀ a, 0 ≤ μ2 a := by intro a simp only [hμ2] by_cases h : a = x · rw [if_pos h, sub_nonneg] rw [h]; exact hm_le_m1 · rw [if_neg h]; simpa using hμ1_nonneg a have hν2_nonneg : ∀ b, 0 ≤ ν2 b := by intro b simp only [hν2] by_cases h : b = y · rw [if_pos h, sub_nonneg] rw [h]; exact hm_le_n1 · rw [if_neg h]; simpa using hν1_nonneg b have hsum_μ2 : ∑ a, μ2 a = rem := by rw [hμ2, hrem, Finset.sum_sub_distrib, Finset.sum_ite_eq'] simp only [Finset.mem_univ, if_true] rw [hsum_m1] have hsum_ν2 : ∑ b, ν2 b = rem := by rw [hν2, hrem, Finset.sum_sub_distrib, Finset.sum_ite_eq'] simp only [Finset.mem_univ, if_true] rw [hsum_n1] have hcoupl_row : ∀ a, ∑ b, μ2 a * ν2 b / rem = μ2 a := by intro a by_cases h0 : rem = 0 · have hz : μ2 a = 0 := by have hsum0 : ∑ b, μ2 b = 0 := by rw [hsum_μ2, h0] exact (Finset.sum_eq_zero_iff_of_nonneg (fun b _ => hμ2_nonneg b)).mp hsum0 a (Finset.mem_univ a) rw [hz] apply Finset.sum_eq_zero; intro b _ rw [h0]; simp · rw [← Finset.sum_div, ← Finset.mul_sum, hsum_ν2] exact mul_div_cancel_right₀ (μ2 a) h0 have hcoupl_col : ∀ b, ∑ a, μ2 a * ν2 b / rem = ν2 b := by intro b by_cases h0 : rem = 0 · have hz : ν2 b = 0 := by have hsum0 : ∑ b, ν2 b = 0 := by rw [hsum_ν2, h0] exact (Finset.sum_eq_zero_iff_of_nonneg (fun b _ => hν2_nonneg b)).mp hsum0 b (Finset.mem_univ b) rw [hz] apply Finset.sum_eq_zero; intro a _ rw [h0]; simp · rw [← Finset.sum_div, ← Finset.sum_mul, hsum_μ2] exact mul_div_cancel_left₀ (ν2 b) h0 have hπ_nonneg : ∀ a b, 0 ≤ π a b := by intro a b have h1 : (0:ℝ) ≤ (if a = b then min (μ a) (ν a) else 0) := by by_cases h : a = b · rw [if_pos h]; exact le_min (hμ a) (hν a) · rw [if_neg h] have h2 : (0:ℝ) ≤ (if b = y then (if a = x then m else 0) else 0) := by by_cases hby : b = y · rw [if_pos hby] by_cases hax : a = x · rw [if_pos hax]; exact hm_nonneg · rw [if_neg hax] · rw [if_neg hby] have h3 : (0:ℝ) ≤ μ2 a * ν2 b / rem := div_nonneg (mul_nonneg (hμ2_nonneg a) (hν2_nonneg b)) hrem_nonneg simp only [hπ] linarith have hrow : ∀ a, ∑ b, π a b = μ a := by intro a simp only [hπ] rw [Finset.sum_add_distrib, Finset.sum_add_distrib] have hdiag : ∑ b, (if a = b then min (μ a) (ν a) else 0) = min (μ a) (ν a) := by rw [Finset.sum_ite_eq]; simp have hmxy : ∑ b, (if b = y then (if a = x then m else 0) else 0) = (if a = x then m else 0) := by rw [Finset.sum_ite_eq']; simp rw [hdiag, hmxy, hcoupl_row a] simp only [hμ2, hm1] ring have hcol : ∀ b, ∑ a, π a b = ν b := by intro b simp only [hπ] rw [Finset.sum_add_distrib, Finset.sum_add_distrib] have hdiag : ∑ a, (if a = b then min (μ a) (ν a) else 0) = min (μ b) (ν b) := by rw [Finset.sum_ite_eq']; simp have hmxy : ∑ a, (if b = y then (if a = x then m else 0) else 0) = (if b = y then m else 0) := by by_cases hby : b = y · simp [hby, Finset.sum_ite_eq'] · simp [hby] rw [hdiag, hmxy, hcoupl_col b] simp only [hν2, hn1] ring have hcost : ∑ a, ∑ b, (G.dist a b : ℝ) * π a b ≤ 2 - 2 * S0 - m := by have hsplit : ∀ a b, (G.dist a b : ℝ) * π a b = (G.dist a b : ℝ) * (if a = b then min (μ a) (ν a) else 0) + (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0) + (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) := by intro a b; simp only [hπ]; ring have hD : ∑ a, ∑ b, (G.dist a b : ℝ) * (if a = b then min (μ a) (ν a) else 0) = 0 := by apply Finset.sum_eq_zero intro a _ apply Finset.sum_eq_zero intro b _ by_cases h : a = b · rw [if_pos h] have hd : (G.dist a b : ℝ) = 0 := by rw [h]; simp rw [hd, zero_mul] · rw [if_neg h, mul_zero] have hM : ∑ a, ∑ b, (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0) = m := by have inner : ∀ a, ∑ b, (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0) = (G.dist a y : ℝ) * (if a = x then m else 0) := by intro a simp only [mul_ite, mul_zero] rw [Finset.sum_ite_eq']; simp simp only [inner] have inner2 : ∑ a, (G.dist a y : ℝ) * (if a = x then m else 0) = (G.dist x y : ℝ) * m := by simp only [mul_ite, mul_zero] rw [Finset.sum_ite_eq']; simp rw [inner2, hxy_dist]; ring have hC : ∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) ≤ 2 * rem := by by_cases h0 : rem = 0 · have hz : ∀ a b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) = 0 := by intro a b; rw [h0]; simp simp only [hz] simp [h0] · have hle : ∀ a b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) ≤ 2 * (μ2 a * ν2 b / rem) := by intro a b have ht : 0 ≤ μ2 a * ν2 b / rem := div_nonneg (mul_nonneg (hμ2_nonneg a) (hν2_nonneg b)) hrem_nonneg exact mul_le_mul_of_nonneg_right (hdist2 a b) ht calc ∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem) ≤ ∑ a, ∑ b, 2 * (μ2 a * ν2 b / rem) := by apply Finset.sum_le_sum; intro a _ apply Finset.sum_le_sum; intro b _ exact hle a b _ = 2 * rem := by have inner : ∀ a, ∑ b, 2 * (μ2 a * ν2 b / rem) = 2 * μ2 a := by intro a; rw [← Finset.mul_sum, hcoupl_row a] simp only [inner] rw [← Finset.mul_sum, hsum_μ2] calc ∑ a, ∑ b, (G.dist a b : ℝ) * π a b = (∑ a, ∑ b, (G.dist a b : ℝ) * (if a = b then min (μ a) (ν a) else 0)) + (∑ a, ∑ b, (G.dist a b : ℝ) * (if b = y then (if a = x then m else 0) else 0)) + (∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem)) := by simp only [hsplit, Finset.sum_add_distrib] _ = 0 + m + (∑ a, ∑ b, (G.dist a b : ℝ) * (μ2 a * ν2 b / rem)) := by rw [hD, hM] _ ≤ 0 + m + 2 * rem := by linarith _ = 2 - 2 * S0 - m := by rw [hrem]; ring calc graph_wasserstein_dist G μ ν ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b := graph_wasserstein_dist_le_of_plan G μ ν π hπ_nonneg hrow hcol _ ≤ 2 - 2 * S0 - m := hcost