AFTD Auto-Formalizing Theoretical Domains

savitch_depth_topological_potential_bound

theoremverifiedoriginal

Let V be a type, r a relation on V, and ℓ : V → ℕ a topological potential such that r u v implies ℓ u < ℓ v. For any vertices s, t with ℓ t - ℓ s ≤ D, and any k with D ≤ 2^k, if t is reachable from s under the reflexive-transitive closure of r, then the Savitch midpoint relation SavitchMidpoint r k s t holds.

Statement

theorem savitch_depth_topological_potential_bound {V : Type*} (r : V → V → Prop)
    (ℓ : V → ℕ) (hℓ : ∀ u v, r u v → ℓ u < ℓ v) {s t : V} (D k : ℕ)
    (hD : ℓ t - ℓ s ≤ D) (hk : D ≤ 2 ^ k) (h : Relation.ReflTransGen r s t) :
    SavitchMidpoint r k s t
Related work
Savitch 1970; Sipser, Theorem 8.5
Verified
20 Oct 2026
Axioms
Quot.soundpropext
Built on 2
  • SavitchMidpointThe Savitch midpoint reachability relation family R_k(r) for a binary relation r on a type V, defined recursively: at step 0, u can reach…
  • savitch_midpoint_monoThe Savitch midpoint reachability relation is monotone in the recursion depth: for any relation r on V, any depth k, and any vertices u…

Read back from the Lean

For any type V, binary relation r : V → V → Prop, function ℓ : V → ℕ such that for all u, v : V, r u v implies ℓ u < ℓ v, any elements s, t : V, and any natural numbers D and k: if ℓ t - ℓ s ≤ D, D ≤ 2 ^ k, and t is reachable from s under r (i.e., Relation.ReflTransGen r s t), then SavitchMidpoint r k s t holds.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

Reachability under relation r is first converted into an explicit n-step path. Because the topological potential strictly increases across each edge, the path length satisfies n ≤ ℓ t - ℓ s ≤ D ≤ 2^k. By induction on k, any path of length at most 2^k can be recursively halved at a midpoint m = min(n, 2^k), certifying that the endpoints satisfy the Savitch midpoint relation SavitchMidpoint r k s t.

  1. A path of length 0 only exists between identical vertices.

    Case analysis on the 0-step path h rules out the inductive constructor (tail), which requires positive length n + 1, leaving only reflexivity where the endpoints s and t are identical.

    lines 10–11

      cases h
      rfl
  2. A path of length 1 implies a single relation edge between the endpoints.

    Case analysis on the 1-step path decomposes it into an edge into t preceded by a 0-step path from s. Case analysis on that 0-step path identifies the intermediate vertex with s, concluding r s t.

    lines 15–18

      cases h with
      | tail h1 h2 =>
        cases h1
        exact h2
  3. Reflexive-transitive reachability implies reachability via an n-step path for some natural number n.

    We induct on Relation.ReflTransGen r s t. The base case gives a 0-step path via reflexivity, while the inductive step extends an n-step path to an (n + 1)-step path by appending the final relation step.

    lines 23–27

      induction h with
      | refl => exact ⟨0, .refl s⟩
      | tail hab hbc ih =>
        obtain ⟨n, hn⟩ := ih
        exact ⟨n + 1, .tail hn hbc⟩
  4. Along any n-step path from s to t, the potential increases by at least n: ℓ s + n ≤ ℓ t.

    We induct on the path h. In the base case n = 0, ℓ u + 0 ≤ ℓ u holds by reflexivity (Nat.le_refl). In the inductive step, the induction hypothesis provides ℓ u + n ≤ ℓ v, and hypothesis hℓ gives ℓ v < ℓ w; linear arithmetic (omega) combines these into ℓ u + (n + 1) ≤ ℓ w.

    lines 32–36

    uses Nat.le_refl

      induction h with
      | refl u => exact Nat.le_refl _
      | tail h_uv h_vw ih =>
        have hlt := hℓ _ _ h_vw
        omega
  5. A path of length 0 can be split at prefix length m = 0 into two 0-step paths.

    We induct on path h, generalizing the split point m. In the base case n = 0, the assumption m ≤ 0 forces m = 0 by linear arithmetic (omega). Taking the endpoint u as the midpoint yields two 0-step paths from u to u.

    lines 43–47

      induction h generalizing m with
      | refl u =>
        have : m = 0 := by omega
        subst this
        exact ⟨u, .refl u, .refl u⟩
  6. When splitting an (n' + 1)-step path at prefix length m with m ≤ n', the midpoint from the prefix induction hypothesis splits the path.

    We split into cases based on whether m ≤ n'. If m ≤ n', applying the induction hypothesis to the n'-step prefix yields a midpoint w' with an m-step path from u to w' and an (n' - m)-step path from w' to v. Appending the final edge v → w produces an (n' + 1 - m)-step path from w' to w.

    lines 48–54

      | @tail n' u v w h_uv h_vw ih =>
        by_cases hle : m ≤ n'
        · obtain ⟨w', hw1, hw2⟩ := ih m hle
          refine ⟨w', hw1, ?_⟩
          have : n' + 1 - m = (n' - m) + 1 := by omega
          rw [this]
          exact .tail hw2 h_vw
  7. When splitting an (n' + 1)-step path at prefix length m with m > n', the target vertex itself serves as the midpoint.

    From m ≤ n' + 1 and ¬(m ≤ n'), linear arithmetic forces m = n' + 1. The full (n' + 1)-step path reaches w, and the remaining subpath from w to w has length n' + 1 - (n' + 1) = 0.

    lines 55–59

        · have heq : m = n' + 1 := by omega
          subst heq
          have : n' + 1 - (n' + 1) = 0 := by omega
          rw [this]
          exact ⟨w, .tail h_uv h_vw, .refl w⟩
  8. At recursion depth k = 0, any path of length n ≤ 1 satisfies SavitchMidpoint r 0 s t.

    Induction on k. When k = 0, n ≤ 2^0 = 1 forces n = 0 or n = 1 by linear arithmetic. For n = 0, savitch_depth_topological_potential_bound_zero shows s = t. For n = 1, savitch_depth_topological_potential_bound_one shows r s t. Both cases satisfy SavitchMidpoint r 0 s t = (s = t ∨ r s t).

    lines 65–72

    uses savitch_depth_topological_potential_bound_zero, savitch_depth_topological_potential_bound_one

      induction k generalizing s t n with
      | zero =>
        have : n ≤ 1 := hn
        rcases (by omega : n = 0 ∨ n = 1) with rfl | rfl
        · left
          exact savitch_depth_topological_potential_bound_zero h
        · right
          exact savitch_depth_topological_potential_bound_one h
  9. At depth k + 1, splitting a path of length n ≤ 2^(k + 1) at min(n, 2^k) establishes SavitchMidpoint r (k + 1) s t.

    In the inductive step for k + 1, we set m = min(n, 2^k). Since m ≤ n by Nat.min_le_left, savitch_depth_topological_potential_bound_split yields a midpoint w with an m-step path from s to w and an (n - m)-step path from w to t. The first path has length m ≤ 2^k by Nat.min_le_right. For the second, rewriting 2^(k + 1) as 2^k * 2 with Nat.pow_succ allows linear arithmetic (omega) to conclude n - m ≤ 2^k. The induction hypothesis then applies to both halves.

    lines 73–80

    uses Nat.min_le_left, savitch_depth_topological_potential_bound_split, Nat.min_le_right, Nat.pow_succ

      | succ k ih =>
        let m := min n (2 ^ k)
        have hm : m ≤ n := Nat.min_le_left _ _
        obtain ⟨w, hw1, hw2⟩ := savitch_depth_topological_potential_bound_split h m hm
        refine ⟨w, ih ?_ hw1, ih ?_ hw2⟩
        · exact Nat.min_le_right _ _
        · rw [Nat.pow_succ] at hn
          omega
  10. Reachability between vertices with potential span at most D ≤ 2^k implies SavitchMidpoint r k s t.

    By savitch_depth_topological_potential_bound_of_reflTransGen, reachability gives an n-step path from s to t. Lemma savitch_depth_topological_potential_bound_pot gives ℓ s + n ≤ ℓ t, which with ℓ t - ℓ s ≤ D ≤ 2^k implies n ≤ 2^k by linear arithmetic (omega). Lemma savitch_depth_topological_potential_bound_midpoint then proves SavitchMidpoint r k s t.

    lines 87–90

    uses savitch_depth_topological_potential_bound_of_reflTransGen, savitch_depth_topological_potential_bound_pot, savitch_depth_topological_potential_bound_midpoint

      obtain ⟨n, hn⟩ := savitch_depth_topological_potential_bound_of_reflTransGen h
      have hpot := savitch_depth_topological_potential_bound_pot hℓ hn
      have hn_le : n ≤ 2 ^ k := by omega
      exact savitch_depth_topological_potential_bound_midpoint k hn_le hn
Nat.le_refl
The less-than-or-equal relation on natural numbers is reflexive: for any natural number n, n ≤ n.
Nat.min_le_left
The minimum of two natural numbers is less than or equal to the first: min a b ≤ a.
Nat.min_le_right
The minimum of two natural numbers is less than or equal to the second: min a b ≤ b.
Nat.pow_succ
Successor exponentiation identity for natural numbers: n^(m + 1) = n^m * n.
savitch_depth_topological_potential_bound_zero
A path of length 0 from s to t implies s = t.
savitch_depth_topological_potential_bound_one
A path of length 1 from s to t implies r s t.
savitch_depth_topological_potential_bound_of_reflTransGen
Reflexive-transitive reachability from s to t implies the existence of an n-step path from s to t for some natural number n.
savitch_depth_topological_potential_bound_pot
If potential ℓ strictly increases along every step of r, then any n-step path from s to t satisfies ℓ s + n ≤ ℓ t.
savitch_depth_topological_potential_bound_split
An n-step path from s to t can be split at any prefix length m ≤ n into an m-step path from s to w and an (n - m)-step path from w to t for some intermediate vertex w.
savitch_depth_topological_potential_bound_midpoint
If there is an n-step path from s to t with n ≤ 2^k, then the Savitch midpoint relation SavitchMidpoint r k s t holds.

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

inductive savitch_depth_topological_potential_bound_reach {V : Type*} (r : V → V → Prop) :    ℕ → V → V → Prop where  | refl (u : V) : savitch_depth_topological_potential_bound_reach r 0 u u  | tail {n : ℕ} {u v w : V} :      savitch_depth_topological_potential_bound_reach r n u v → r v w →      savitch_depth_topological_potential_bound_reach r (n + 1) u wlemma savitch_depth_topological_potential_bound_zero {V : Type*} {r : V → V → Prop} {s t : V}    (h : savitch_depth_topological_potential_bound_reach r 0 s t) : s = t := by  cases h  rfllemma savitch_depth_topological_potential_bound_one {V : Type*} {r : V → V → Prop} {s t : V}    (h : savitch_depth_topological_potential_bound_reach r 1 s t) : r s t := by  cases h with  | tail h1 h2 =>    cases h1    exact h2lemma savitch_depth_topological_potential_bound_of_reflTransGen {V : Type*} {r : V → V → Prop}    {s t : V} (h : Relation.ReflTransGen r s t) :    ∃ n, savitch_depth_topological_potential_bound_reach r n s t := by  induction h with  | refl => exact ⟨0, .refl s⟩  | tail hab hbc ih =>    obtain ⟨n, hn⟩ := ih    exact ⟨n + 1, .tail hn hbc⟩lemma savitch_depth_topological_potential_bound_pot {V : Type*} {r : V → V → Prop}    {ℓ : V → ℕ} (hℓ : ∀ u v, r u v → ℓ u < ℓ v) {s t : V} {n : ℕ}    (h : savitch_depth_topological_potential_bound_reach r n s t) : ℓ s + n ≤ ℓ t := by  induction h with  | refl u => exact Nat.le_refl _  | tail h_uv h_vw ih =>    have hlt := hℓ _ _ h_vw    omegalemma savitch_depth_topological_potential_bound_split {V : Type*} {r : V → V → Prop}    {s t : V} {n : ℕ} (h : savitch_depth_topological_potential_bound_reach r n s t)    (m : ℕ) (hm : m ≤ n) :    ∃ w, savitch_depth_topological_potential_bound_reach r m s w ∧      savitch_depth_topological_potential_bound_reach r (n - m) w t := by  induction h generalizing m with  | refl u =>    have : m = 0 := by omega    subst this    exact ⟨u, .refl u, .refl u⟩  | @tail n' u v w h_uv h_vw ih =>    by_cases hle : m ≤ n'    · obtain ⟨w', hw1, hw2⟩ := ih m hle      refine ⟨w', hw1, ?_⟩      have : n' + 1 - m = (n' - m) + 1 := by omega      rw [this]      exact .tail hw2 h_vw    · have heq : m = n' + 1 := by omega      subst heq      have : n' + 1 - (n' + 1) = 0 := by omega      rw [this]      exact ⟨w, .tail h_uv h_vw, .refl w⟩lemma savitch_depth_topological_potential_bound_midpoint {V : Type*} {r : V → V → Prop}    (k : ℕ) {s t : V} {n : ℕ} (hn : n ≤ 2 ^ k)    (h : savitch_depth_topological_potential_bound_reach r n s t) :    SavitchMidpoint r k s t := by  induction k generalizing s t n with  | zero =>    have : n ≤ 1 := hn    rcases (by omega : n = 0 ∨ n = 1) with rfl | rfl    · left      exact savitch_depth_topological_potential_bound_zero h    · right      exact savitch_depth_topological_potential_bound_one h  | succ k ih =>    let m := min n (2 ^ k)    have hm : m ≤ n := Nat.min_le_left _ _    obtain ⟨w, hw1, hw2⟩ := savitch_depth_topological_potential_bound_split h m hm    refine ⟨w, ih ?_ hw1, ih ?_ hw2⟩    · exact Nat.min_le_right _ _    · rw [Nat.pow_succ] at hn      omega/-- Savitch midpoint depth bound on ranked DAGs: reachability is certified at depth k whenever the topological potential span D satisfies D ≤ 2^k. -/theorem savitch_depth_topological_potential_bound {V : Type*} (r : V → V → Prop)    (ℓ : V → ℕ) (hℓ : ∀ u v, r u v → ℓ u < ℓ v) {s t : V} (D k : ℕ)    (hD : ℓ t - ℓ s ≤ D) (hk : D ≤ 2 ^ k) (h : Relation.ReflTransGen r s t) :    SavitchMidpoint r k s t := by  obtain ⟨n, hn⟩ := savitch_depth_topological_potential_bound_of_reflTransGen h  have hpot := savitch_depth_topological_potential_bound_pot hℓ hn  have hn_le : n ≤ 2 ^ k := by omega  exact savitch_depth_topological_potential_bound_midpoint k hn_le hn
See it in the graphDiscuss this resultChallenge it