AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_lower_bound_le_of_dist_eq

theoremverified

The scale-i lower curvature bound is a lower bound for κ_LLY at any pair at distance i: κ_LLY^(i)(G) ≤ κ_LLY(x,y) whenever d(x,y) = i.

Statement

theorem graph_lly_curvature_lower_bound_le_of_dist_eq
    {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (x y : V) (i : ℕ) (h : G.dist x y = i) :
    graph_lly_curvature_lower_bound G i ≤ graph_lly_curvature G x y
Source
step towards exists_dist_three_lly_curvature_le_cut
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

By definition, the scale-i lower curvature bound κ_LLY^(i)(G) is the infimum of the set of curvatures κ_LLY(a, b) over all vertex pairs at graph distance i. Because the graph has finitely many vertices, the set of all pairwise curvatures is finite, making this distance-i subset finite and therefore bounded below. Since the vertices x and y are at distance i, their curvature belongs to this set, and the infimum is at most any element of the set.

  1. Unfolding the definition, the set of curvatures achieved by pairs at distance i is contained in the range of the curvature function on all vertex pairs V × V.

    By definition, `graph_lly_curvature_lower_bound G i` is the infimum of the set S = {κ : ℝ | ∃ a b, d(a, b) = i ∧ κ_LLY(a, b) = κ}. Any κ in this set is the curvature of some pair (a, b) ∈ V × V, so S is a subset of the range of (u, v) ↦ κ_LLY(u, v).

    lines 7–11

      unfold graph_lly_curvature_lower_bound
      have hS : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ graph_lly_curvature G x y = κ}
          ⊆ Set.range (fun p : V × V => graph_lly_curvature G p.1 p.2)) := by
        rintro κ ⟨a, b, -, rfl⟩
        exact ⟨(a, b), rfl⟩
  2. The set of curvatures achieved by pairs at distance i is finite.

    Since the vertex type V is finite, the product V × V is finite. By `Set.finite_range`, the range of the curvature function on V × V is finite. Because the set of distance-i curvatures is a subset of this range, `Set.Finite.subset` implies it is also finite.

    lines 12–13

    uses Set.Finite.subset, Set.finite_range

      have hfin : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ graph_lly_curvature G x y = κ}).Finite :=
        Set.Finite.subset (Set.finite_range _) hS
  3. The scale-i lower curvature bound is at most κ_LLY(x, y).

    A finite set of real numbers is bounded below. Since d(x, y) = i, κ_LLY(x, y) is an element of the set defining the lower bound. By `csInf_le`, the infimum of a set bounded below is less than or equal to any of its elements.

    line 14

    uses csInf_le

      exact csInf_le hfin.bddBelow ⟨x, y, h, rfl⟩
Set.Finite.subset
A subset of a finite set is finite.
Set.finite_range
The range of a function defined on a finite domain is finite.
csInf_le
In a conditionally complete lattice (such as ℝ), the infimum of a set bounded below is less than or equal to any element of the set.

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

/-- The infimum defining κ_LLY^(i)(G) is attained-below by every distance-i pair. -/theorem graph_lly_curvature_lower_bound_le_of_dist_eq    {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (x y : V) (i : ℕ) (h : G.dist x y = i) :    graph_lly_curvature_lower_bound G i ≤ graph_lly_curvature G x y := by  unfold graph_lly_curvature_lower_bound  have hS : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ graph_lly_curvature G x y = κ}      ⊆ Set.range (fun p : V × V => graph_lly_curvature G p.1 p.2)) := by    rintro κ ⟨a, b, -, rfl⟩    exact ⟨(a, b), rfl⟩  have hfin : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ graph_lly_curvature G x y = κ}).Finite :=    Set.Finite.subset (Set.finite_range _) hS  exact csInf_le hfin.bddBelow ⟨x, y, h, rfl⟩
See it in the graphDiscuss this resultChallenge it