AFTD Auto-Formalizing Theoretical Domains

wasserstein_dist_le_of_diameter_two

theoremverified

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
Used by 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.

  1. 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.

    lines 12–22

      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π
  2. 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.

    lines 23–40

    uses sub_nonneg.mpr, min_le_left, min_le_right, Finset.sum_sub_distrib, le_min, Finset.single_le_sum, Finset.mem_univ

      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
  3. 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.

    lines 41–62

    uses if_pos, sub_nonneg, if_neg, Finset.sum_sub_distrib, Finset.sum_ite_eq', Finset.mem_univ, if_true

      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]
  4. 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).

    lines 63–84

    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
  5. 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.

    lines 85–101

    uses if_pos, le_min, if_neg, div_nonneg, mul_nonneg

      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
  6. 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).

    lines 102–125

    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
  7. 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.

    lines 126–180

    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_distrib

      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
  8. 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.

    lines 181–183

    uses graph_wasserstein_dist_le_of_plan

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it