savitch_depth_topological_potential_bound
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.
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.
cases h rfl
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.
cases h with | tail h1 h2 => cases h1 exact h2
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.
induction h with | refl => exact ⟨0, .refl s⟩ | tail hab hbc ih => obtain ⟨n, hn⟩ := ih exact ⟨n + 1, .tail hn hbc⟩
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.
uses
Nat.le_reflinduction h with | refl u => exact Nat.le_refl _ | tail h_uv h_vw ih => have hlt := hℓ _ _ h_vw omega
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.
induction h generalizing m with | refl u => have : m = 0 := by omega subst this exact ⟨u, .refl u, .refl u⟩
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.
| @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_vwWhen 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.
· 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⟩
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).
uses
savitch_depth_topological_potential_bound_zero,savitch_depth_topological_potential_bound_oneinduction 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
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.
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 omegaReachability 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.
uses
savitch_depth_topological_potential_bound_of_reflTransGen,savitch_depth_topological_potential_bound_pot,savitch_depth_topological_potential_bound_midpointobtain ⟨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.
- To carry out the induction on path length, the formalization defines an auxiliary length-indexed reachability relation rather than working directly with the length-free reflexive-transitive closure.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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