AFTD Auto-Formalizing Theoretical Domains

five_vertex_t_star_wasserstein_le

theoremverified

For the T-graph and α in [2/5, 1], the explicit plan π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3, π(4,1)=(1−α)/3 shows W(μ_0^α, μ_1^α) ≤ 4/3 − α/3.

Statement

theorem five_vertex_t_star_wasserstein_le (α : ℝ) (hα0 : 2 / 5 ≤ α) (hα1 : α ≤ 1) :
    graph_wasserstein_dist five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0)
      (graph_idle_measure five_vertex_t_star α 1) ≤ 4 / 3 - α / 3
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 2

The proof, explained

The theorem proves that on the 5-vertex T-graph, the 1-Wasserstein distance between the lazy random walk measures μ_0^α and μ_1^α is at most 4/3 - α/3 for any α ∈ [2/5, 1]. This is shown by constructing an explicit transport plan π with six nonzero entries. The proof checks entrywise nonnegativity using the bound α ≥ 2/5, verifies that the row and column marginals of π equal μ_0^α and μ_1^α by exhausting vertices in Fin 5, and evaluates the transport cost to be exactly 4/3 - α/3.

  1. An explicit candidate transport plan π : Fin 5 → Fin 5 → ℝ is defined.

    The coupling is assigned six nonzero values: π(0,0) = (1 - α)/2, π(0,1) = (5α - 2)/3, π(0,2) = (1 - α)/6, π(1,2) = (1 - α)/3, π(3,1) = (1 - α)/3, and π(4,1) = (1 - α)/3, with π(a,b) = 0 for all other pairs (a,b).

    lines 5–12

      let π : Fin 5 → Fin 5 → ℝ := fun a b =>
        if a = 0 ∧ b = 0 then (1 - α) / 2
        else if a = 0 ∧ b = 1 then (5 * α - 2) / 3
        else if a = 0 ∧ b = 2 then (1 - α) / 6
        else if a = 1 ∧ b = 2 then (1 - α) / 3
        else if a = 3 ∧ b = 1 then (1 - α) / 3
        else if a = 4 ∧ b = 1 then (1 - α) / 3
        else 0
  2. Every entry of the transport plan π is nonnegative.

    The proof exhaustively inspects all 25 pairs (a,b) ∈ Fin 5 × Fin 5 using `fin_cases`. Nonnegativity of the nonzero entries follows from 2/5 ≤ α ≤ 1 via linear arithmetic (`linarith`), since (1 - α) ≥ 0 and (5α - 2) ≥ 0.

    lines 13–15

      have hπ : ∀ a b, 0 ≤ π a b := by
        intro a b
        fin_cases a <;> fin_cases b <;> { dsimp [π]; linarith }
  3. The row sums of π match the first idle measure: ∑_b π(a, b) = μ_0^α(a) for all a ∈ Fin 5.

    Exhausting a ∈ {0, 1, 2, 3, 4}, the sum over b is expanded using `Fin.sum_univ_five`. In the T-graph, vertex 0 has degree 3 with neighbors 1, 3, 4. Thus μ_0^α puts mass α on 0, mass (1 - α)/3 on each neighbor 1, 3, 4, and mass 0 on vertex 2. Evaluating `graph_idle_measure` and simplifying ring expressions confirms that the row sums match these probabilities in every case.

    lines 16–48

    uses Fin.sum_univ_five, if_neg, if_pos

      have h1 : ∀ a, ∑ b, π a b = graph_idle_measure five_vertex_t_star α 0 a := by
        intro a
        fin_cases a
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 0 0 = α := by
            unfold graph_idle_measure; simp
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 0 1 = (1 - α) / 3 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_pos (by decide)]
            have hd : five_vertex_t_star.degree 0 = 3 := by decide
            rw [hd]; norm_cast
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_neg (by decide)]
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 0 3 = (1 - α) / 3 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_pos (by decide)]
            have hd : five_vertex_t_star.degree 0 = 3 := by decide
            rw [hd]; norm_cast
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 0 4 = (1 - α) / 3 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_pos (by decide)]
            have hd : five_vertex_t_star.degree 0 = 3 := by decide
            rw [hd]; norm_cast
          rw [this]; ring
  4. The column sums of π match the second idle measure: ∑_a π(a, b) = μ_1^α(b) for all b ∈ Fin 5.

    Exhausting b ∈ {0, 1, 2, 3, 4}, the sum over a is expanded using `Fin.sum_univ_five`. In the T-graph, vertex 1 has degree 2 with neighbors 0 and 2. Thus μ_1^α puts mass α on 1, mass (1 - α)/2 on each of 0 and 2, and mass 0 on vertices 3 and 4. In each case, evaluating `graph_idle_measure` and simplifying confirms that the column sum equals the required marginal weight.

    lines 49–79

    uses Fin.sum_univ_five, if_neg, if_pos

      have h2 : ∀ b, ∑ a, π a b = graph_idle_measure five_vertex_t_star α 1 b := by
        intro b
        fin_cases b
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 1 0 = (1 - α) / 2 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_pos (by decide)]
            have hd : five_vertex_t_star.degree 1 = 2 := by decide
            rw [hd]; norm_cast
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 1 1 = α := by
            unfold graph_idle_measure; simp
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 1 2 = (1 - α) / 2 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_pos (by decide)]
            have hd : five_vertex_t_star.degree 1 = 2 := by decide
            rw [hd]; norm_cast
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_neg (by decide)]
          rw [this]; ring
        · rw [Fin.sum_univ_five]; dsimp [π]
          have : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by
            unfold graph_idle_measure
            rw [if_neg (by decide), if_neg (by decide)]
          rw [this]; ring
  5. The total transport cost ∑_{a, b} d(a, b) π(a, b) equals 4/3 - α/3.

    The graph distances between the relevant pairs are recorded: d(0,0)=0, d(0,1)=1, d(0,2)=2, d(1,2)=1, d(3,1)=2, and d(4,1)=2. Expanding the double sum over Fin 5 × Fin 5 with `Fin.sum_univ_five` and substituting these distances into ∑_{a, b} d(a,b) π(a,b) gives 1 · (5α - 2)/3 + 2 · (1 - α)/6 + 1 · (1 - α)/3 + 2 · (1 - α)/3 + 2 · (1 - α)/3, which simplifies via `ring` to 4/3 - α/3.

    lines 80–91

    uses SimpleGraph.dist_self, five_vertex_t_star_dist_eq.1, five_vertex_t_star_dist_eq.2.1, SimpleGraph.dist_eq_one_iff_adj.mpr, five_vertex_t_star_dist_eq.2.2.1, five_vertex_t_star_dist_eq.2.2.2.1, Fin.sum_univ_five

      have hcost : (∑ a, ∑ b, (five_vertex_t_star.dist a b : ℝ) * π a b) = 4 / 3 - α / 3 := by
        have hd00 : five_vertex_t_star.dist 0 0 = 0 := SimpleGraph.dist_self
        have hd01 : five_vertex_t_star.dist 0 1 = 1 := five_vertex_t_star_dist_eq.1
        have hd02 : five_vertex_t_star.dist 0 2 = 2 := five_vertex_t_star_dist_eq.2.1
        have hd12 : five_vertex_t_star.dist 1 2 = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr (by decide)
        have hd31 : five_vertex_t_star.dist 3 1 = 2 := five_vertex_t_star_dist_eq.2.2.1
        have hd41 : five_vertex_t_star.dist 4 1 = 2 := five_vertex_t_star_dist_eq.2.2.2.1
        repeat rw [Fin.sum_univ_five]
        dsimp [π]
        rw [hd00, hd01, hd02, hd12, hd31, hd41]
        push_cast
        ring
  6. The Wasserstein distance W(μ_0^α, μ_1^α) on the T-graph is at most 4/3 - α/3.

    By `graph_wasserstein_dist_le_of_plan`, the Wasserstein distance is bounded by the cost of any valid coupling whose marginals match μ_0^α and μ_1^α. Applying this theorem to π using the verified nonnegativity, row sums, and column sums, and rewriting with the calculated cost, yields the upper bound.

    lines 92–95

    uses graph_wasserstein_dist_le_of_plan

      have h_bound := graph_wasserstein_dist_le_of_plan five_vertex_t_star
        (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) π hπ h1 h2
      rw [hcost] at h_bound
      exact h_bound
Fin.sum_univ_five
For any function f on Fin 5 with values in an additive commutative monoid, its sum over Fin 5 is f 0 + f 1 + f 2 + f 3 + f 4.
if_neg
If a proposition c is false, then (if c then t else e) reduces to e.
if_pos
If a proposition c is true, then (if c then t else e) reduces to t.
SimpleGraph.dist_self
In any simple graph, the shortest-path distance from any vertex to itself is 0.
SimpleGraph.dist_eq_one_iff_adj.mpr
If two vertices in a simple graph are adjacent, the distance between them is 1.
five_vertex_t_star_dist_eq.1
In the 5-vertex T-graph, the distance between vertices 0 and 1 is 1.
five_vertex_t_star_dist_eq.2.1
In the 5-vertex T-graph, the distance between vertices 0 and 2 is 2.
five_vertex_t_star_dist_eq.2.2.1
In the 5-vertex T-graph, the distance between vertices 3 and 1 is 2.
five_vertex_t_star_dist_eq.2.2.2.1
In the 5-vertex T-graph, the distance between vertices 4 and 1 is 2.
graph_wasserstein_dist_le_of_plan
Any nonnegative transport plan π whose marginals match μ and ν provides an upper bound on the graph Wasserstein distance: W(μ, ν) ≤ ∑_{a, b} d(a, b) π(a, b).

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

/-- Upper bound for the T-graph by an explicit transport plan. NOTE: the plan proposed in the earlier escalation was infeasible (its column-1 sum is (4α−1)/3, not α). The corrected table is: π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3, π(4,1)=(1−α)/3, everything else 0; it needs α ≥ 2/5 and has cost exactly 4/3 − α/3. -/theorem five_vertex_t_star_wasserstein_le (α : ℝ) (hα0 : 2 / 5 ≤ α) (hα1 : α ≤ 1) :    graph_wasserstein_dist five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0)      (graph_idle_measure five_vertex_t_star α 1) ≤ 4 / 3 - α / 3 := by  let π : Fin 5 → Fin 5 → ℝ := fun a b =>    if a = 0 ∧ b = 0 then (1 - α) / 2    else if a = 0 ∧ b = 1 then (5 * α - 2) / 3    else if a = 0 ∧ b = 2 then (1 - α) / 6    else if a = 1 ∧ b = 2 then (1 - α) / 3    else if a = 3 ∧ b = 1 then (1 - α) / 3    else if a = 4 ∧ b = 1 then (1 - α) / 3    else 0  have hπ : ∀ a b, 0 ≤ π a b := by    intro a b    fin_cases a <;> fin_cases b <;> { dsimp [π]; linarith }  have h1 : ∀ a, ∑ b, π a b = graph_idle_measure five_vertex_t_star α 0 a := by    intro a    fin_cases a    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 0 0 = α := by        unfold graph_idle_measure; simp      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 0 1 = (1 - α) / 3 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_pos (by decide)]        have hd : five_vertex_t_star.degree 0 = 3 := by decide        rw [hd]; norm_cast      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_neg (by decide)]      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 0 3 = (1 - α) / 3 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_pos (by decide)]        have hd : five_vertex_t_star.degree 0 = 3 := by decide        rw [hd]; norm_cast      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 0 4 = (1 - α) / 3 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_pos (by decide)]        have hd : five_vertex_t_star.degree 0 = 3 := by decide        rw [hd]; norm_cast      rw [this]; ring  have h2 : ∀ b, ∑ a, π a b = graph_idle_measure five_vertex_t_star α 1 b := by    intro b    fin_cases b    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 1 0 = (1 - α) / 2 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_pos (by decide)]        have hd : five_vertex_t_star.degree 1 = 2 := by decide        rw [hd]; norm_cast      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 1 1 = α := by        unfold graph_idle_measure; simp      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 1 2 = (1 - α) / 2 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_pos (by decide)]        have hd : five_vertex_t_star.degree 1 = 2 := by decide        rw [hd]; norm_cast      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_neg (by decide)]      rw [this]; ring    · rw [Fin.sum_univ_five]; dsimp [π]      have : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by        unfold graph_idle_measure        rw [if_neg (by decide), if_neg (by decide)]      rw [this]; ring  have hcost : (∑ a, ∑ b, (five_vertex_t_star.dist a b : ℝ) * π a b) = 4 / 3 - α / 3 := by    have hd00 : five_vertex_t_star.dist 0 0 = 0 := SimpleGraph.dist_self    have hd01 : five_vertex_t_star.dist 0 1 = 1 := five_vertex_t_star_dist_eq.1    have hd02 : five_vertex_t_star.dist 0 2 = 2 := five_vertex_t_star_dist_eq.2.1    have hd12 : five_vertex_t_star.dist 1 2 = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr (by decide)    have hd31 : five_vertex_t_star.dist 3 1 = 2 := five_vertex_t_star_dist_eq.2.2.1    have hd41 : five_vertex_t_star.dist 4 1 = 2 := five_vertex_t_star_dist_eq.2.2.2.1    repeat rw [Fin.sum_univ_five]    dsimp [π]    rw [hd00, hd01, hd02, hd12, hd31, hd41]    push_cast    ring  have h_bound := graph_wasserstein_dist_le_of_plan five_vertex_t_star    (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) π hπ h1 h2  rw [hcost] at h_bound  exact h_bound
See it in the graphDiscuss this resultChallenge it