AFTD Auto-Formalizing Theoretical Domains

graph_wasserstein_dist_mix_dirac_le

theoremverified

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

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(μ, ν).

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

    lines 7–25

    uses graph_wasserstein_dist_le_of_plan, Finset.sum_add_distrib, Finset.mul_sum

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

    lines 26–36

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

    lines 37–41

    uses eq_or_lt_of_le, mul_nonneg, Finset.mul_sum, mul_one, Finset.sum_mul, one_mul

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

    lines 42–49

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

    lines 50–51

    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.

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

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