AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_le_of_lipschitz_cut_potential

theoremverified

Kantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y), κ_LLY(x,y) ≤ (d − A_x + A_y)/d, where A_z is the average of f over the neighbourhood of z.

Statement

theorem graph_lly_curvature_le_of_lipschitz_cut_potential
    {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (hG : G.Connected) (x y : V) (hxy : x ≠ y) (f : V → ℝ)
    (hf : ∀ a b : V, f a - f b ≤ (G.dist a b : ℝ))
    (hval : f x - f y = (G.dist x y : ℝ)) :
    graph_lly_curvature G x y ≤
      ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ)
        + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ)
Source
step towards exists_dist_three_lly_curvature_le_cut
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 1

The proof, explained

To bound the Lin–Lu–Yau curvature κ_LLY(x, y) from above, we first express the expectation of any function under the idle random walk measure m_z^α as a convex combination α * f(z) + (1 - α) * A_z of its value at z and its neighborhood average A_z. By Kantorovich duality, the Wasserstein distance between the idle measures at x and y is bounded below by the difference in these expectations for the 1-Lipschitz potential f. This translates into an upper bound on the Ollivier curvature ratio κ_O(α, x, y) / (1 - α) for all α ∈ [0, 1), and taking the limit as α → 1⁻ yields the Kantorovich bound on κ_LLY(x, y).

  1. The distance between x and y is strictly positive, and both x and y have positive degree.

    Because G is connected and x ≠ y, the distance between x and y is strictly positive (from hG.pos_dist_of_ne). Furthermore, in any connected graph with at least two vertices, both vertices have strictly positive degree (graph_degree_pos_of_connected_of_ne).

    lines 11–13

    uses graph_degree_pos_of_connected_of_ne

      have hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy
      have hdx : 0 < G.degree x := graph_degree_pos_of_connected_of_ne G hG x y hxy
      have hdy : 0 < G.degree y := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm
  2. For any vertex z of positive degree and any α ∈ ℝ, the expectation of f under the idle measure at z is α * f(z) + (1 - α) * A_z, where A_z is the average of f over the neighbors of z.

    We isolate the vertex z from the sum over all vertices using Finset.add_sum_erase. At z, the idle measure evaluates to α, giving α * f(z). For each a ≠ z, the idle measure evaluates to (1 - α) / deg(z) if a is adjacent to z, and 0 otherwise. Factoring (1 - α) / deg(z) out of the sum over a ≠ z (Finset.mul_sum), the remaining sum consists of f(a) for all a ≠ z adjacent to z. Since simple graphs have no self-loops (SimpleGraph.irrefl), z is never adjacent to itself, so this sum equals the sum of f over all neighbors of z. Denominators are then cleared with field_simp.

    lines 14–44

    uses Finset.add_sum_erase, Finset.mem_univ, Finset.sum_congr, Finset.mem_erase.mp, Finset.mul_sum, mul_comm, Finset.sum_filter, SimpleGraph.neighborFinset_eq_filter, SimpleGraph.irrefl, if_false, zero_add

      have sumid : ∀ (z : V), 0 < G.degree z → ∀ α : ℝ,
          ∑ a, f a * graph_idle_measure G α z a
            = α * f z + (1 - α) * ((∑ a ∈ G.neighborFinset z, f a) / (G.degree z : ℝ)) := by
        intro z hz α
        have hd_ne : (G.degree z : ℝ) ≠ 0 := by positivity
        have step1 : ∑ a, f a * graph_idle_measure G α z a
            = f z * α + ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0) := by
          rw [← Finset.add_sum_erase Finset.univ (fun a => f a * graph_idle_measure G α z a) (Finset.mem_univ z)]
          congr 1
          · simp [graph_idle_measure]
          · apply Finset.sum_congr rfl
            intro a ha
            have haz : a ≠ z := (Finset.mem_erase.mp ha).1
            simp [graph_idle_measure, haz]
        have step2 : ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0)
            = (1 - α) / (G.degree z : ℝ) * ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) := by
          rw [Finset.mul_sum]
          apply Finset.sum_congr rfl
          intro a ha
          by_cases h : G.Adj z a <;> simp [h, mul_comm]
        have step3 : ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by
          have h1 : ∑ a, (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by
            rw [← Finset.sum_filter, SimpleGraph.neighborFinset_eq_filter]
          have h2 : (if G.Adj z z then f z else 0) + ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0)
              = ∑ a, (if G.Adj z a then f a else 0) :=
            Finset.add_sum_erase Finset.univ (fun a => if G.Adj z a then f a else 0) (Finset.mem_univ z)
          rw [← h2] at h1
          simp only [SimpleGraph.irrefl, if_false, zero_add] at h1
          exact h1
        rw [step1, step2, step3]
        field_simp
  3. For every α ∈ [0, 1), the Ollivier curvature ratio satisfies κ_O(α, x, y) / (1 - α) ≤ (d(x, y) - A_x + A_y) / d(x, y).

    For α ∈ [0, 1), the idle measures at x and y are non-negative (graph_idle_measure_nonneg) and sum to 1 (graph_idle_measure_sum_eq_one). By Kantorovich duality (graph_wasserstein_dist_ge_of_lipschitz), the Wasserstein distance W₁ is bounded below by the difference between the expectations of the 1-Lipschitz function f. Using the expectation formula sumid and the condition f(x) - f(y) = d(x, y), this gives W₁ ≥ d(x, y) - (1 - α) * (d(x, y) - A_x + A_y). Unfolding the definition of Ollivier curvature κ_O(α) = 1 - W₁ / d(x, y) and cross-multiplying denominators with div_le_div_iff₀, this lower bound on W₁ is equivalent to the desired upper bound on the curvature ratio.

    lines 45–69

    uses graph_idle_measure_nonneg, graph_idle_measure_sum_eq_one, graph_wasserstein_dist_ge_of_lipschitz, div_le_div_iff₀

      have key : ∀ α : ℝ, 0 ≤ α → α < 1 →
          graph_ollivier_curvature G α x y / (1 - α) ≤
            ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ)
              + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ) := by
        intro α hα0 hα1
        have h1α : 0 < 1 - α := by linarith
        have hnx := graph_idle_measure_nonneg G α hα0 hα1.le x
        have hny := graph_idle_measure_nonneg G α hα0 hα1.le y
        have hsx := graph_idle_measure_sum_eq_one G α x hdx
        have hsy := graph_idle_measure_sum_eq_one G α y hdy
        have hW := graph_wasserstein_dist_ge_of_lipschitz G (graph_idle_measure G α x) (graph_idle_measure G α y)
          hnx hny hsx hsy f hf
        rw [sumid x hdx α, sumid y hdy α] at hW
        have hWlow : (G.dist x y : ℝ) - (1 - α) * ((G.dist x y : ℝ)
            - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ)
            + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) ≤
            graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by
          nlinarith [hW, hval]
        unfold graph_ollivier_curvature
        rw [div_le_div_iff₀ h1α hd]
        have hsimp : (1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x y : ℝ)) * (G.dist x y : ℝ)
            = (G.dist x y : ℝ) - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by
          field_simp
        rw [hsimp]
        nlinarith [hWlow]
  4. The Lin–Lu–Yau curvature κ_LLY(x, y) is at most (d(x, y) - A_x + A_y) / d(x, y).

    The Lin–Lu–Yau curvature is defined as the limit of κ_O(α, x, y) / (1 - α) as α → 1⁻ (graph_lly_curvature_tendsto). Since the upper bound holds for all α in the open interval (0, 1) (Ioo_mem_nhdsLT), passing to the limit preserves the non-strict inequality (le_of_tendsto).

    lines 70–72

    uses le_of_tendsto, graph_lly_curvature_tendsto, Ioo_mem_nhdsLT

      apply le_of_tendsto (graph_lly_curvature_tendsto G hG x y hxy)
      filter_upwards [Ioo_mem_nhdsLT (show (0 : ℝ) < 1 by norm_num)] with α hα
      exact key α hα.1.le hα.2
graph_degree_pos_of_connected_of_ne
in a connected graph with at least two vertices, every vertex has strictly positive degree
Finset.add_sum_erase
a sum over a finite set can be decomposed as the term at a chosen element plus the sum over the remaining elements
Finset.mem_univ
every element of a finite type belongs to the universal finset
Finset.sum_congr
two sums are equal if their index sets are equal and their summands agree on each element
Finset.mem_erase.mp
membership in an erased set implies distinctness from the erased element
Finset.mul_sum
multiplication by a constant distributes over a finite sum
mul_comm
multiplication is commutative
Finset.sum_filter
a sum over a filtered subset equals the sum over the ambient set with an indicator function
SimpleGraph.neighborFinset_eq_filter
the neighbor set of a vertex is the finset of all vertices adjacent to it
SimpleGraph.irrefl
in a simple graph, no vertex is adjacent to itself (no self-loops)
if_false
an if-expression with a false condition evaluates to its else branch
zero_add
zero plus any element equals that element
graph_idle_measure_nonneg
the idle random walk measure assigns non-negative values to all vertices when α is in [0, 1]
graph_idle_measure_sum_eq_one
the idle random walk measure sums to 1 when the vertex has positive degree
graph_wasserstein_dist_ge_of_lipschitz
Kantorovich duality: the Wasserstein distance between probability measures is bounded below by the difference between expectations of any 1-Lipschitz function
div_le_div_iff₀
for positive denominators, a / b ≤ c / d is equivalent to a * d ≤ c * b
le_of_tendsto
if a function converges to a limit and is eventually bounded above by b, its limit is at most b
graph_lly_curvature_tendsto
the Ollivier curvature ratio κ_O(α) / (1 - α) tends to the Lin–Lu–Yau curvature as α approaches 1 from the left
Ioo_mem_nhdsLT
the open interval (a, b) is a neighborhood of b in the left-half-line topology when 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

/-- Kantorovich-duality (1-Lipschitz potential) upper bound for the Lin–Lu–Yau curvature at a pair of distinct vertices. -/theorem graph_lly_curvature_le_of_lipschitz_cut_potential    {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (hG : G.Connected) (x y : V) (hxy : x ≠ y) (f : V → ℝ)    (hf : ∀ a b : V, f a - f b ≤ (G.dist a b : ℝ))    (hval : f x - f y = (G.dist x y : ℝ)) :    graph_lly_curvature G x y ≤      ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ)        + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ) := by  have hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy  have hdx : 0 < G.degree x := graph_degree_pos_of_connected_of_ne G hG x y hxy  have hdy : 0 < G.degree y := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm  have sumid : ∀ (z : V), 0 < G.degree z → ∀ α : ℝ,      ∑ a, f a * graph_idle_measure G α z a        = α * f z + (1 - α) * ((∑ a ∈ G.neighborFinset z, f a) / (G.degree z : ℝ)) := by    intro z hz α    have hd_ne : (G.degree z : ℝ) ≠ 0 := by positivity    have step1 : ∑ a, f a * graph_idle_measure G α z a        = f z * α + ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0) := by      rw [← Finset.add_sum_erase Finset.univ (fun a => f a * graph_idle_measure G α z a) (Finset.mem_univ z)]      congr 1      · simp [graph_idle_measure]      · apply Finset.sum_congr rfl        intro a ha        have haz : a ≠ z := (Finset.mem_erase.mp ha).1        simp [graph_idle_measure, haz]    have step2 : ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0)        = (1 - α) / (G.degree z : ℝ) * ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) := by      rw [Finset.mul_sum]      apply Finset.sum_congr rfl      intro a ha      by_cases h : G.Adj z a <;> simp [h, mul_comm]    have step3 : ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by      have h1 : ∑ a, (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by        rw [← Finset.sum_filter, SimpleGraph.neighborFinset_eq_filter]      have h2 : (if G.Adj z z then f z else 0) + ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0)          = ∑ a, (if G.Adj z a then f a else 0) :=        Finset.add_sum_erase Finset.univ (fun a => if G.Adj z a then f a else 0) (Finset.mem_univ z)      rw [← h2] at h1      simp only [SimpleGraph.irrefl, if_false, zero_add] at h1      exact h1    rw [step1, step2, step3]    field_simp  have key : ∀ α : ℝ, 0 ≤ α → α < 1 →      graph_ollivier_curvature G α x y / (1 - α) ≤        ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ)          + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ) := by    intro α hα0 hα1    have h1α : 0 < 1 - α := by linarith    have hnx := graph_idle_measure_nonneg G α hα0 hα1.le x    have hny := graph_idle_measure_nonneg G α hα0 hα1.le y    have hsx := graph_idle_measure_sum_eq_one G α x hdx    have hsy := graph_idle_measure_sum_eq_one G α y hdy    have hW := graph_wasserstein_dist_ge_of_lipschitz G (graph_idle_measure G α x) (graph_idle_measure G α y)      hnx hny hsx hsy f hf    rw [sumid x hdx α, sumid y hdy α] at hW    have hWlow : (G.dist x y : ℝ) - (1 - α) * ((G.dist x y : ℝ)        - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ)        + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) ≤        graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by      nlinarith [hW, hval]    unfold graph_ollivier_curvature    rw [div_le_div_iff₀ h1α hd]    have hsimp : (1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x y : ℝ)) * (G.dist x y : ℝ)        = (G.dist x y : ℝ) - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by      field_simp    rw [hsimp]    nlinarith [hWlow]  apply le_of_tendsto (graph_lly_curvature_tendsto G hG x y hxy)  filter_upwards [Ioo_mem_nhdsLT (show (0 : ℝ) < 1 by norm_num)] with α hα  exact key α hα.1.le hα.2
See it in the graphDiscuss this resultChallenge it