AFTD Auto-Formalizing Theoretical Domains

five_vertex_t_star_wasserstein_ge

theoremverified

For the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α + 7(1−α)/3) − 1 = 4/3 − α/3.

Statement

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

The proof, explained

The proof establishes the lower bound by Kantorovich duality using the test function f(v) = d(v, 2), which is shown to be 1-Lipschitz via the graph triangle inequality. After checking that the lazy random walk measures μ_0^α and μ_1^α are valid probability distributions, Kantorovich duality bounds the Wasserstein distance below by the difference in their expectations under f. Evaluating f and both measures explicitly at each of the five vertices yields the expectation difference 4/3 - α/3, completing the proof.

  1. The graph five_vertex_t_star is connected, and the test function f(v) = d(v, 2) is 1-Lipschitz.

    Connectedness of the finite graph is verified by exhaustive computation (decide). For any two vertices a and b, the triangle inequality d(a, 2) ≤ d(a, b) + d(b, 2) holds in any connected graph. Rearranging this inequality yields f(a) - f(b) ≤ d(a, b), establishing that f is 1-Lipschitz.

    lines 5–13

      have hconn : five_vertex_t_star.Connected := by decide
      let f : Fin 5 → ℝ := fun v => (five_vertex_t_star.dist v 2 : ℝ)
      have hf : ∀ a b, f a - f b ≤ (five_vertex_t_star.dist a b : ℝ) := by
        intro a b
        dsimp [f]
        have := hconn.dist_triangle (u := a) (v := b) (w := 2)
        have h : (five_vertex_t_star.dist a 2 : ℝ) ≤ (five_vertex_t_star.dist a b : ℝ) + (five_vertex_t_star.dist b 2 : ℝ) := by
          exact_mod_cast this
        linarith
  2. The idle measures μ_0^α and μ_1^α are probability measures, and Kantorovich duality bounds the Wasserstein distance below by ∑ f μ_0^α - ∑ f μ_1^α.

    Since α ∈ [0, 1], the idle measures are pointwise nonnegative by graph_idle_measure_nonneg. The degrees of vertices 0 and 1 are strictly positive (verified by decide), so graph_idle_measure_sum_eq_one implies both measures sum to 1. Applying Kantorovich duality (graph_wasserstein_dist_ge_of_lipschitz) with the 1-Lipschitz function f provides the lower bound.

    lines 14–28

    uses graph_idle_measure_nonneg, graph_idle_measure_sum_eq_one, graph_wasserstein_dist_ge_of_lipschitz

      have hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure five_vertex_t_star α 0 a := by
        intro a
        exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 0 a
      have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure five_vertex_t_star α 1 b := by
        intro b
        exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 1 b
      have hd0 : 0 < five_vertex_t_star.degree 0 := by decide
      have hd1 : 0 < five_vertex_t_star.degree 1 := by decide
      have hμ1 : ∑ a, graph_idle_measure five_vertex_t_star α 0 a = 1 :=
        graph_idle_measure_sum_eq_one five_vertex_t_star α 0 hd0
      have hν1 : ∑ b, graph_idle_measure five_vertex_t_star α 1 b = 1 :=
        graph_idle_measure_sum_eq_one five_vertex_t_star α 1 hd1
      have hge := graph_wasserstein_dist_ge_of_lipschitz five_vertex_t_star
        (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1)
        hμ_nonneg hν_nonneg hμ1 hν1 f hf
  3. The values of the test function f at vertices 0, 1, 2, 3, 4 are 2, 1, 0, 3, 3 respectively.

    The values d(0, 2) = 2, d(3, 2) = 3, and d(4, 2) = 3 are extracted from the lemma five_vertex_t_star_dist_eq. Vertices 1 and 2 are adjacent (decide), so d(1, 2) = 1 by SimpleGraph.dist_eq_one_iff_adj.mpr. Finally, d(2, 2) = 0 by SimpleGraph.dist_self.

    lines 30–35

    uses five_vertex_t_star_dist_eq.2.1, SimpleGraph.dist_eq_one_iff_adj.mpr, SimpleGraph.dist_self, five_vertex_t_star_dist_eq.2.2.2.2.1, five_vertex_t_star_dist_eq.2.2.2.2.2

      have hd00 : 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 hd22 : five_vertex_t_star.dist 2 2 = 0 := SimpleGraph.dist_self
      have hd32 : five_vertex_t_star.dist 3 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.1
      have hd42 : five_vertex_t_star.dist 4 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.2
    
  4. The measure μ_0^α evaluates to α at 0, (1 - α)/3 at 1, 3, 4, and 0 at 2.

    By definition of graph_idle_measure, the measure puts mass α at the base vertex 0. The remaining mass 1 - α is distributed equally among the neighbours of 0. Since vertex 0 has degree 3 with neighbours 1, 3, and 4, each neighbour receives mass (1 - α)/3. Vertex 2 is not adjacent to 0, so it receives mass 0. Each case is resolved by simplifying the conditional branches using if_pos and if_neg with decidable adjacency.

    lines 36–56

    uses if_neg, if_pos

      have hμ0 : graph_idle_measure five_vertex_t_star α 0 0 = α := by
        unfold graph_idle_measure; simp
      have hμ1_val : 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
      have hμ2_val : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by
        unfold graph_idle_measure
        rw [if_neg (by decide), if_neg (by decide)]
      have hμ3_val : 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
      have hμ4_val : 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
    
  5. The measure μ_1^α evaluates to α at 1, (1 - α)/2 at 0 and 2, and 0 at 3 and 4.

    Similarly, the idle measure at vertex 1 places mass α on vertex 1. Because vertex 1 has degree 2 with neighbours 0 and 2, each neighbour gets (1 - α)/2. Vertices 3 and 4 are not adjacent to 1 and receive mass 0. These values are confirmed by simplifying the conditionals via if_pos and if_neg.

    lines 57–75

    uses if_neg, if_pos

      have hν0_val : 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
      have hν1_val : graph_idle_measure five_vertex_t_star α 1 1 = α := by
        unfold graph_idle_measure; simp
      have hν2_val : 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
      have hν3_val : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by
        unfold graph_idle_measure
        rw [if_neg (by decide), if_neg (by decide)]
      have hν4_val : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by
        unfold graph_idle_measure
        rw [if_neg (by decide), if_neg (by decide)]
    
  6. The difference between the expected values of f under μ_0^α and μ_1^α equals 4/3 - α/3.

    Expanding the summations over the 5 vertices using Fin.sum_univ_five and substituting the computed values of f, μ_0^α, and μ_1^α, the expression simplifies via ring normalization to (2α + 7(1 - α)/3) - 1 = 4/3 - α/3.

    lines 76–85

    uses Fin.sum_univ_five

      have hdiff : ∑ a, f a * graph_idle_measure five_vertex_t_star α 0 a -
          ∑ b, f b * graph_idle_measure five_vertex_t_star α 1 b = 4 / 3 - α / 3 := by
        rw [Fin.sum_univ_five, Fin.sum_univ_five]
        dsimp [f]
        rw [hd00, hd12, hd22, hd32, hd42]
        rw [hμ0, hμ1_val, hμ2_val, hμ3_val, hμ4_val]
        rw [hν0_val, hν1_val, hν2_val, hν3_val, hν4_val]
        push_cast
        ring
    
  7. The Wasserstein distance satisfies 4/3 - α/3 ≤ W(μ_0^α, μ_1^α).

    Combining the Kantorovich lower bound W(μ_0^α, μ_1^α) ≥ ∑ f μ_0^α - ∑ f μ_1^α with the calculated expectation difference 4/3 - α/3, linear arithmetic closes the goal.

    line 86

      linarith
graph_idle_measure_nonneg
The idle measure of any vertex in a graph assigns a nonnegative value to every vertex, provided the idle parameter α satisfies 0 ≤ α ≤ 1.
graph_idle_measure_sum_eq_one
The idle measure of a vertex with strictly positive degree sums to 1 over all vertices in the graph.
graph_wasserstein_dist_ge_of_lipschitz
By Kantorovich duality, the Wasserstein distance between two probability measures on a graph is bounded below by the difference of their expectations against any 1-Lipschitz function.
five_vertex_t_star_dist_eq.2.1
In five_vertex_t_star, the shortest path distance between vertex 0 and vertex 2 is 2.
SimpleGraph.dist_eq_one_iff_adj.mpr
In a simple graph, two adjacent vertices have distance 1.
SimpleGraph.dist_self
In a simple graph, the distance from any vertex to itself is 0.
five_vertex_t_star_dist_eq.2.2.2.2.1
In five_vertex_t_star, the shortest path distance between vertex 3 and vertex 2 is 3.
five_vertex_t_star_dist_eq.2.2.2.2.2
In five_vertex_t_star, the shortest path distance between vertex 4 and vertex 2 is 3.
if_neg
A conditional expression evaluates to its second branch when the condition is false.
if_pos
A conditional expression evaluates to its first branch when the condition is true.
Fin.sum_univ_five
The sum of a function over Fin 5 equals the sum of its values at 0, 1, 2, 3, and 4.

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

/-- Lower bound for the T-graph by Kantorovich duality with the 1-Lipschitz test function f = dist(·,2), whose values on the vertices are (2,1,0,3,3). -/theorem five_vertex_t_star_wasserstein_ge (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) :    4 / 3 - α / 3 ≤ graph_wasserstein_dist five_vertex_t_star      (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) := by  have hconn : five_vertex_t_star.Connected := by decide  let f : Fin 5 → ℝ := fun v => (five_vertex_t_star.dist v 2 : ℝ)  have hf : ∀ a b, f a - f b ≤ (five_vertex_t_star.dist a b : ℝ) := by    intro a b    dsimp [f]    have := hconn.dist_triangle (u := a) (v := b) (w := 2)    have h : (five_vertex_t_star.dist a 2 : ℝ) ≤ (five_vertex_t_star.dist a b : ℝ) + (five_vertex_t_star.dist b 2 : ℝ) := by      exact_mod_cast this    linarith  have hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure five_vertex_t_star α 0 a := by    intro a    exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 0 a  have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure five_vertex_t_star α 1 b := by    intro b    exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 1 b  have hd0 : 0 < five_vertex_t_star.degree 0 := by decide  have hd1 : 0 < five_vertex_t_star.degree 1 := by decide  have hμ1 : ∑ a, graph_idle_measure five_vertex_t_star α 0 a = 1 :=    graph_idle_measure_sum_eq_one five_vertex_t_star α 0 hd0  have hν1 : ∑ b, graph_idle_measure five_vertex_t_star α 1 b = 1 :=    graph_idle_measure_sum_eq_one five_vertex_t_star α 1 hd1  have hge := graph_wasserstein_dist_ge_of_lipschitz five_vertex_t_star    (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1)    hμ_nonneg hν_nonneg hμ1 hν1 f hf  have hd00 : 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 hd22 : five_vertex_t_star.dist 2 2 = 0 := SimpleGraph.dist_self  have hd32 : five_vertex_t_star.dist 3 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.1  have hd42 : five_vertex_t_star.dist 4 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.2  have hμ0 : graph_idle_measure five_vertex_t_star α 0 0 = α := by    unfold graph_idle_measure; simp  have hμ1_val : 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  have hμ2_val : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by    unfold graph_idle_measure    rw [if_neg (by decide), if_neg (by decide)]  have hμ3_val : 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  have hμ4_val : 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  have hν0_val : 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  have hν1_val : graph_idle_measure five_vertex_t_star α 1 1 = α := by    unfold graph_idle_measure; simp  have hν2_val : 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  have hν3_val : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by    unfold graph_idle_measure    rw [if_neg (by decide), if_neg (by decide)]  have hν4_val : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by    unfold graph_idle_measure    rw [if_neg (by decide), if_neg (by decide)]  have hdiff : ∑ a, f a * graph_idle_measure five_vertex_t_star α 0 a -      ∑ b, f b * graph_idle_measure five_vertex_t_star α 1 b = 4 / 3 - α / 3 := by    rw [Fin.sum_univ_five, Fin.sum_univ_five]    dsimp [f]    rw [hd00, hd12, hd22, hd32, hd42]    rw [hμ0, hμ1_val, hμ2_val, hμ3_val, hμ4_val]    rw [hν0_val, hν1_val, hν2_val, hν3_val, hν4_val]    push_cast    ring  linarith
See it in the graphDiscuss this resultChallenge it