AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_two_word

theoremverified

Every normalized allowed permutation is the product of exactly two actual hops on an undirected graph. No vertex is allowed to wait during either actual hop.

Statement

theorem simple_graph_normalized_hop_two_word {V : Type*} (G : SimpleGraph V)
    (h₀ p : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀)
    (hp : simple_graph_normalized_hop G h₀ p) :
    ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧
      w.length = 2 ∧ w.prod = p
Source
Uniform structural helper for IN-262 / OP-543, using the hop and leap-group definitions of arXiv:2610.18463. The universal quadratic word bound is a question proposed here, not a theorem of that paper. No diameter estimate or research advance is claimed by this algebraic normalization.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_normalized_hopA permutation p is allowed relative to baseline h0 when h0*p is an actual hop. Relative p may fix vertices; the resulting actual hop still…
  • simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.
  • simple_graph_is_hop_invThe inverse of a hop is a hop (the graph is undirected).
Used by 2

The proof, explained

To represent the permutation p as the product of two hops, we choose the two-element list [h₀⁻¹, h₀ * p]. Its length is 2, and its product simplifies to h₀⁻¹ * (h₀ * p) = p by group cancellation. The two elements are both hops because the inverse of a hop is always a hop on an undirected graph, and h₀ * p is a hop by the definition of a normalized hop.

  1. The candidate list [h₀⁻¹, h₀ * p] has length 2 and product p.

    We supply the two-element list [h₀⁻¹, h₀ * p] as the witness w. Its length is 2 and its product simplifies to h₀⁻¹ * (h₀ * p) = p via group cancellation, leaving only the requirement that every element of the list is a hop.

    line 6

      refine ⟨[h₀⁻¹,h₀*p], ?_, by simp, by simp⟩
  2. It suffices to verify that both h₀⁻¹ and h₀ * p are hops.

    Let h be any element of [h₀⁻¹, h₀ * p]. Expanding the definition of list membership gives h = h₀⁻¹ or h = h₀ * p, splitting the goal into these two cases.

    lines 7–9

      intro h hh
      have hcases : h = h₀⁻¹ ∨ h = h₀*p := by simpa using hh
      rcases hcases with rfl | rfl
  3. h₀⁻¹ is a hop.

    Since h₀ is assumed to be a hop (hypothesis hh₀), its inverse h₀⁻¹ is also a hop by simple_graph_is_hop_inv.

    line 10

    uses simple_graph_is_hop_inv

      · exact simple_graph_is_hop_inv G h₀ hh₀
  4. h₀ * p is a hop.

    By definition, the assumption hp that p is a normalized hop with respect to h₀ states directly that h₀ * p is a hop.

    line 11

      · exact hp
simple_graph_is_hop_inv
If a permutation on the vertices of a simple graph is a hop, then its inverse permutation is also a hop.

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

theorem simple_graph_normalized_hop_two_word {V : Type*} (G : SimpleGraph V)    (h₀ p : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀)    (hp : simple_graph_normalized_hop G h₀ p) :    ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧      w.length = 2 ∧ w.prod = p := by  refine ⟨[h₀⁻¹,h₀*p], ?_, by simp, by simp⟩  intro h hh  have hcases : h = h₀⁻¹ ∨ h = h₀*p := by simpa using hh  rcases hcases with rfl | rfl  · exact simple_graph_is_hop_inv G h₀ hh₀  · exact hp
See it in the graphDiscuss this resultChallenge it