AFTD Auto-Formalizing Theoretical Domains

exact_steiner_hopset_layered_dag_steiner_shortcut

theoremverifiedformalization

Let V and W be finite types, Gv a directed graph on V and ℓ : V → ℕ a layering such that every arc u → v of Gv has ℓ v = ℓ u + 1 (a layered DAG), and let G be its undirected version (u, v adjacent iff u ≠ v and u → v or v → u). Let H be a simple graph on V ⊕ W (W the Steiner vertices) containing the copy of G on V, with edge weights w that are positive on the edges of H and equal to 1 on the edges of G, forming an exact Steiner hopset of G with hopbound β: every walk in H between original vertices s, t has weight at least the distance dist_G(s, t) (in particular s and t are connected in G), and every pair s, t connected in G is joined by a walk in H of weight exactly dist_G(s, t) with at most β edges. Then there is a directed graph Hv on V ⊕ W containing every arc of Gv (on V) such that the number of arcs of Hv that are not arcs of Gv is at most the number of edges of H not in the copy of G, for original vertices x, y, x reaches y in Hv iff x reaches y in Gv, and whenever x reaches y in Gv, x reaches y in Hv in at most β steps.

Statement

theorem exact_steiner_hopset_layered_dag_steiner_shortcut
    {V W : Type*} [Finite V] [Finite W]
    (Gv : Digraph V) (ℓ : V → ℕ) (hℓ : ∀ u v, Gv.Adj u v → ℓ v = ℓ u + 1)
    (H : SimpleGraph (V ⊕ W)) (w : Sym2 (V ⊕ W) → ℝ) (β : ℕ)
    (hGH : (SimpleGraph.fromRel Gv.Adj).map Function.Embedding.inl ≤ H)
    (hw1 : ∀ u v, (SimpleGraph.fromRel Gv.Adj).Adj u v → w s(Sum.inl u, Sum.inl v) = 1)
    (hwpos : ∀ e ∈ H.edgeSet, 0 < w e)
    (hdist : ∀ s t (p : H.Walk (Sum.inl s) (Sum.inl t)),
      (SimpleGraph.fromRel Gv.Adj).Reachable s t ∧
        ((SimpleGraph.fromRel Gv.Adj).dist s t : ℝ) ≤ (p.edges.map w).sum)
    (hhop : ∀ s t, (SimpleGraph.fromRel Gv.Adj).Reachable s t →
      ∃ p : H.Walk (Sum.inl s) (Sum.inl t),
        (p.edges.map w).sum = (SimpleGraph.fromRel Gv.Adj).dist s t ∧ p.length ≤ β) :
    ∃ Hv : Digraph (V ⊕ W),
      (∀ u v, Gv.Adj u v → Hv.Adj (Sum.inl u) (Sum.inl v)) ∧
      {x : (V ⊕ W) × (V ⊕ W) | Hv.Adj x.1 x.2 ∧ ¬ ∃ u v, x = (Sum.inl u, Sum.inl v) ∧ Gv.Adj u v}.ncard ≤
        (H.edgeSet \ ((SimpleGraph.fromRel Gv.Adj).map Function.Embedding.inl).edgeSet).ncard ∧
      (∀ x y : V, Relation.ReflTransGen Hv.Adj (Sum.inl x) (Sum.inl y) ↔
        Relation.ReflTransGen Gv.Adj x y) ∧
      (∀ x y : V, Relation.ReflTransGen Gv.Adj x y →
        Relation.RelatesWithinSteps Hv.Adj (Sum.inl x) (Sum.inl y) β)
Formalizes
arXiv:2611.07043 (Polynomial Lower Bounds for Steiner Shortcuts via Test Functions), Lemma 4.2. The hopset's distance conditions are stated through walks (every H-walk between original vertices weighs at least dist_G, and connected pairs have a walk of weight dist_G with at most β edges), which is equivalent to dist_H = dist_G on V plus the hopbound, without infinite distances. Proof differs slightly from the paper's: the extended layering is the infimum of ℓ(u) + weight over all walks from original vertices (0 for vertices not connected to V), so no shortest path or vertex deletion is needed.
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

Read back from the Lean

Let $V$ and $W$ be finite types. Let $G_v$ be a directed graph on $V$, and let $\ell : V \to \mathbb{N}$ be a layering function such that for all $u, v \in V$, if $G_v.\text{Adj } u\ v$ then $\ell(v) = \ell(u) + 1$ (so $G_v$ is a unit-increment layered DAG). Let $H$ be a simple graph on $V \oplus W$, let $w : \text{Sym2}(V \oplus W) \to \mathbb{R}$ be an edge-weight function, and let $\beta \in \mathbb{N}$ be a hop bound. Assume: 1. hGH: The symmetrization of $G_v$ (given by SimpleGraph.fromRel Gv.Adj), mapped into $V \oplus W$ via the canonical inclusion Sum.inl, is a subgraph of $H$ (i.e., every embedded symmetrized edge of $G_v$ is an edge of $H$). 2. hw1: For every adjacent pair $u, v$ in the symmetrization of $G_v$, the weight of the corresponding edge $s(\text{inl } u, \text{inl } v)$ in $H$ is $1$. 3. hwpos: Every edge $e \in H.\text{edgeSet}$ has strictly positive weight: $w(e) > 0$. 4. hdist: For all $s, t \in V$ and for every walk $p$ in $H$ from $\text{Sum.inl } s$ to $\text{Sum.inl } t$: - $s$ and $t$ are reachable from each other in the symmetrization of $G_v$, and - the graph distance between $s$ and $t$ in the symmetrization of $G_v$ (cast to $\mathbb{R}$) is at most the total weight of the walk $\sum_{e \in p.\text{edges}} w(e)$. 5. hhop: For all $s, t \in V$, if $s$ and $t$ are reachable from each other in the symmetrization of $G_v$, then there exists a walk $p$ in $H$ from $\text{Sum.inl } s$ to $\text{Sum.inl } t$ such that: - the total weight of $p$, $\sum_{e \in p.\text{edges}} w(e)$, equals the graph distance between $s$ and $t$ in the symmetrization of $G_v$, and - the length of $p$ (number of edges) is at most $\beta$. Then there exists a directed graph $H_v$ on $V \oplus W$ such that: 1. (Edge containment) For all $u, v \in V$, if $G_v.\text{Adj } u\ v$, then $H_v.\text{Adj } (\text{Sum.inl } u)\ (\text{Sum.inl } v)$. 2. (Extra edge count bound) The number of directed edges in $H_v$ that are not of the form $(\text{Sum.inl } u, \text{Sum.inl } v)$ with $G_v.\text{Adj } u\ v$ is at most the number of undirected edges of $H$ that are not in the embedded edge set of the symmetrization of $G_v$. 3. (Reachability preservation) For all $x, y \in V$, $\text{Sum.inl } y$ is reachable from $\text{Sum.inl } x$ in $H_v$ (via the reflexive transitive closure of $H_v.\text{Adj}$) if and only if $y$ is reachable from $x$ in $G_v$ (via the reflexive transitive closure of $G_v.\text{Adj}$). 4. (Hopset bound) For all $x, y \in V$, if $y$ is reachable from $x$ in $G_v$, then $\text{Sum.inl } y$ is reachable from $\text{Sum.inl } x$ in $H_v$ within $\beta$ steps (Relation.RelatesWithinSteps Hv.Adj (Sum.inl x) (Sum.inl y) β).

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

Lean source view module on GitHub

theorem steiner_hopset_layer_diff_le_length {V : Type*} (Gv : Digraph V) (ℓ : V → ℕ)    (hℓ : ∀ u v, Gv.Adj u v → ℓ v = ℓ u + 1) {u x : V}    (q : (SimpleGraph.fromRel Gv.Adj).Walk u x) :    |(ℓ x : ℤ) - ℓ u| ≤ q.length := by  induction q with  | nil => simp  | @cons a b c h q ih =>    rw [SimpleGraph.fromRel_adj] at h    rw [SimpleGraph.Walk.length_cons]    rw [abs_le] at ih ⊢    rcases h.2 with h' | h'    · have := hℓ _ _ h'; push_cast; constructor <;> omega    · have := hℓ _ _ h'; push_cast; constructor <;> omegatheorem steiner_hopset_walk_directed_of_length_le {V : Type*} (Gv : Digraph V) (ℓ : V → ℕ)    (hℓ : ∀ u v, Gv.Adj u v → ℓ v = ℓ u + 1) {u x : V}    (q : (SimpleGraph.fromRel Gv.Adj).Walk u x) (hq : (q.length : ℤ) ≤ (ℓ x : ℤ) - ℓ u) :    Relation.ReflTransGen Gv.Adj u x := by  induction q with  | nil => exact Relation.ReflTransGen.refl  | @cons a b c h q ih =>    rw [SimpleGraph.fromRel_adj] at h    rw [SimpleGraph.Walk.length_cons] at hq    have hb := steiner_hopset_layer_diff_le_length Gv ℓ hℓ q    rw [abs_le] at hb    rcases h.2 with h' | h'    · have := hℓ _ _ h'      exact Relation.ReflTransGen.head h' (ih (by push_cast at hq; omega))    · have := hℓ _ _ h'      push_cast at hq      omegatheorem steiner_hopset_walk_of_directed {V : Type*} (Gv : Digraph V) (ℓ : V → ℕ)    (hℓ : ∀ u v, Gv.Adj u v → ℓ v = ℓ u + 1) {x y : V}    (h : Relation.ReflTransGen Gv.Adj x y) :    ∃ q : (SimpleGraph.fromRel Gv.Adj).Walk x y, (q.length : ℤ) = (ℓ y : ℤ) - ℓ x := by  induction h with  | refl => exact ⟨SimpleGraph.Walk.nil, by simp⟩  | @tail b c _ hbc ih =>    obtain ⟨q, hq⟩ := ih    have hl := hℓ _ _ hbc    have hadj : (SimpleGraph.fromRel Gv.Adj).Adj b c := by      rw [SimpleGraph.fromRel_adj]      refine ⟨?_, Or.inl hbc⟩      rintro rfl; omega    refine ⟨q.concat hadj, ?_⟩    rw [SimpleGraph.Walk.length_concat]    push_cast; omegatheorem exact_steiner_hopset_layered_dag_steiner_shortcut    {V W : Type*} [Finite V] [Finite W]    (Gv : Digraph V) (ℓ : V → ℕ) (hℓ : ∀ u v, Gv.Adj u v → ℓ v = ℓ u + 1)    (H : SimpleGraph (V ⊕ W)) (w : Sym2 (V ⊕ W) → ℝ) (β : ℕ)    (hGH : (SimpleGraph.fromRel Gv.Adj).map Function.Embedding.inl ≤ H)    (hw1 : ∀ u v, (SimpleGraph.fromRel Gv.Adj).Adj u v → w s(Sum.inl u, Sum.inl v) = 1)    (hwpos : ∀ e ∈ H.edgeSet, 0 < w e)    (hdist : ∀ s t (p : H.Walk (Sum.inl s) (Sum.inl t)),      (SimpleGraph.fromRel Gv.Adj).Reachable s t ∧        ((SimpleGraph.fromRel Gv.Adj).dist s t : ℝ) ≤ (p.edges.map w).sum)    (hhop : ∀ s t, (SimpleGraph.fromRel Gv.Adj).Reachable s t →      ∃ p : H.Walk (Sum.inl s) (Sum.inl t),        (p.edges.map w).sum = (SimpleGraph.fromRel Gv.Adj).dist s t ∧ p.length ≤ β) :    ∃ Hv : Digraph (V ⊕ W),      (∀ u v, Gv.Adj u v → Hv.Adj (Sum.inl u) (Sum.inl v)) ∧      {x : (V ⊕ W) × (V ⊕ W) | Hv.Adj x.1 x.2 ∧ ¬ ∃ u v, x = (Sum.inl u, Sum.inl v) ∧ Gv.Adj u v}.ncard ≤        (H.edgeSet \ ((SimpleGraph.fromRel Gv.Adj).map Function.Embedding.inl).edgeSet).ncard ∧      (∀ x y : V, Relation.ReflTransGen Hv.Adj (Sum.inl x) (Sum.inl y) ↔        Relation.ReflTransGen Gv.Adj x y) ∧      (∀ x y : V, Relation.ReflTransGen Gv.Adj x y →        Relation.RelatesWithinSteps Hv.Adj (Sum.inl x) (Sum.inl y) β) := by  set G := SimpleGraph.fromRel Gv.Adj with hG  -- weights of walks are nonnegative  have wt_nonneg : ∀ {a b} (p : H.Walk a b), 0 ≤ (p.edges.map w).sum := by    intro a b p    apply List.sum_nonneg    intro r hr    obtain ⟨e, he, rfl⟩ := List.mem_map.mp hr    exact (hwpos e (p.edges_subset_edgeSet he)).le  let S : V ⊕ W → Set ℝ := fun a => {r | ∃ u, ∃ p : H.Walk (Sum.inl u) a, r = ℓ u + (p.edges.map w).sum}  have hS_bdd : ∀ a, BddBelow (S a) := by    intro a    refine ⟨0, ?_⟩    rintro r ⟨u, p, rfl⟩    have := wt_nonneg p    positivity  let φ : V ⊕ W → ℝ := fun a => sInf (S a)  -- P1: potential inequality along edges  have P1 : ∀ a b, H.Adj a b → φ b ≤ φ a + w s(a, b) := by    intro a b hab    by_cases hne : (S a).Nonempty    · have : φ b - w s(a, b) ≤ φ a := by        apply le_csInf hne        rintro r ⟨u, p, rfl⟩        have hmem : (ℓ u : ℝ) + ((p.concat hab).edges.map w).sum ∈ S b := ⟨u, p.concat hab, rfl⟩        have := csInf_le (hS_bdd b) hmem        simp only [SimpleGraph.Walk.edges_concat, List.concat_eq_append, List.map_append,          List.sum_append, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil] at this        show φ b - w s(a, b) ≤ _        linarith      linarith    · have hb : ¬ (S b).Nonempty := by        rintro ⟨r, u, p, rfl⟩        exact hne ⟨_, u, p.concat hab.symm, rfl⟩      rw [Set.not_nonempty_iff_eq_empty] at hne hb      have := hwpos s(a, b) ((SimpleGraph.mem_edgeSet H).mpr hab)      show sInf (S b) ≤ sInf (S a) + _      rw [hne, hb, Real.sInf_empty]      linarith  -- P2: potential agrees with the layering on V  have P2 : ∀ x : V, φ (Sum.inl x) = ℓ x := by    intro x    have hmem : (ℓ x : ℝ) + ((SimpleGraph.Walk.nil : H.Walk (Sum.inl x) (Sum.inl x)).edges.map w).sum ∈ S (Sum.inl x) :=      ⟨x, SimpleGraph.Walk.nil, rfl⟩    apply le_antisymm    · have := csInf_le (hS_bdd _) hmem      simpa using this    · apply le_csInf ⟨_, hmem⟩      rintro r ⟨u, p, rfl⟩      obtain ⟨hr, hd⟩ := hdist u x p      obtain ⟨q, hq⟩ := hr.exists_walk_length_eq_dist      have hl := steiner_hopset_layer_diff_le_length Gv ℓ hℓ q      rw [abs_le, hq] at hl      have h1 : (ℓ x : ℝ) - ℓ u ≤ (G.dist u x : ℝ) := by exact_mod_cast hl.2      linarith  -- lower bound along walks  have lower : ∀ {a b} (p : H.Walk a b), φ b - φ a ≤ (p.edges.map w).sum := by    intro a b p    induction p with    | nil => simp    | @cons a c b h p ih =>      have := P1 a c h      simp only [SimpleGraph.Walk.edges_cons, List.map_cons, List.sum_cons]      linarith  let Hv : Digraph (V ⊕ W) := { Adj := fun a b => H.Adj a b ∧ φ b - φ a = w s(a, b) }  have C1 : ∀ u v, Gv.Adj u v → Hv.Adj (Sum.inl u) (Sum.inl v) := by    intro u v huv    have hl := hℓ u v huv    have hGuv : G.Adj u v := by      rw [hG, SimpleGraph.fromRel_adj]      refine ⟨?_, Or.inl huv⟩      rintro rfl; omega    refine ⟨hGH ?_, ?_⟩    · rw [SimpleGraph.map_adj]      exact ⟨u, v, hGuv, rfl, rfl⟩    · show φ (Sum.inl v) - φ (Sum.inl u) = _      rw [P2, P2, hw1 u v hGuv, hl]      push_cast; ring  have walk_of_Hv : ∀ {a b}, Relation.ReflTransGen Hv.Adj a b →      ∃ p : H.Walk a b, (p.edges.map w).sum = φ b - φ a := by    intro a b h    induction h with    | refl => exact ⟨SimpleGraph.Walk.nil, by simp⟩    | @tail b c _ hbc ih =>      obtain ⟨p, hp⟩ := ih      refine ⟨p.concat hbc.1, ?_⟩      simp only [SimpleGraph.Walk.edges_concat, List.concat_eq_append, List.map_append,        List.sum_append, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil]      have := hbc.2      linarith  have tight : ∀ {a b} (p : H.Walk a b), (p.edges.map w).sum ≤ φ b - φ a →      Relation.RelatesInSteps Hv.Adj a b p.length := by    intro a b p    induction p with    | nil => intro _; exact Relation.RelatesInSteps.refl _    | @cons a c b h p ih =>      intro hp      simp only [SimpleGraph.Walk.edges_cons, List.map_cons, List.sum_cons] at hp      have h1 := P1 a c h      have h2 := lower p      rw [SimpleGraph.Walk.length_cons]      refine Relation.RelatesInSteps.head _ _ _ _ ⟨h, ?_⟩ (ih (by linarith))      linarith  refine ⟨Hv, C1, ?_, ?_, ?_⟩  · -- counting the added edges    apply Set.ncard_le_ncard_of_injOn (fun x => s(x.1, x.2))    · rintro ⟨a, b⟩ ⟨⟨hab, hφ⟩, hnot⟩      refine ⟨(SimpleGraph.mem_edgeSet H).mpr hab, ?_⟩      intro hmem      rw [SimpleGraph.mem_edgeSet, SimpleGraph.map_adj] at hmem      obtain ⟨u, v, huv, rfl, rfl⟩ := hmem      have huv' := huv      rw [hG, SimpleGraph.fromRel_adj] at huv'      rcases huv'.2 with h' | h'      · exact hnot ⟨u, v, rfl, h'⟩      · have hl := hℓ _ _ h'        have hw := hw1 u v huv        change φ (Sum.inl v) - φ (Sum.inl u) = w s(Sum.inl u, Sum.inl v) at hφ        rw [P2, P2, hw, hl] at hφ        push_cast at hφ        linarith    · rintro ⟨a, b⟩ ⟨⟨hab, hφ⟩, _⟩ ⟨c, d⟩ ⟨⟨hcd, hφ'⟩, _⟩ heq      simp only [Sym2.eq_iff] at heq      rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩      · rfl      · have := hwpos s(a, b) ((SimpleGraph.mem_edgeSet H).mpr hab)        simp only at hφ hφ'        rw [Sym2.eq_swap] at hφ'        linarith  · intro x y    constructor    · intro h      obtain ⟨p, hp⟩ := walk_of_Hv h      obtain ⟨hr, hd⟩ := hdist x y p      rw [hp, P2, P2] at hd      obtain ⟨q, hq⟩ := hr.exists_walk_length_eq_dist      apply steiner_hopset_walk_directed_of_length_le Gv ℓ hℓ q      rw [hq]      exact_mod_cast hd    · intro h      exact h.lift Sum.inl C1  · intro x y h    obtain ⟨q, hq⟩ := steiner_hopset_walk_of_directed Gv ℓ hℓ h    have hr : G.Reachable x y := ⟨q⟩    obtain ⟨p, hpw, hpl⟩ := hhop x y hr    obtain ⟨q', hq'⟩ := hr.exists_walk_length_eq_dist    have hl := steiner_hopset_layer_diff_le_length Gv ℓ hℓ q'    rw [abs_le, hq'] at hl    have h1 : (ℓ y : ℝ) - ℓ x ≤ (G.dist x y : ℝ) := by exact_mod_cast hl.2    refine ⟨p.length, hpl, tight p ?_⟩    rw [hpw, P2, P2]    have h2 : (G.dist x y : ℤ) ≤ (ℓ y : ℤ) - ℓ x := by      rw [← hq]; exact_mod_cast SimpleGraph.dist_le q    have h3 : (G.dist x y : ℝ) ≤ (ℓ y : ℝ) - ℓ x := by exact_mod_cast h2    exact h3
See it in the graphDiscuss this resultChallenge it