simple_graph_normalized_hop_two_word
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
- simple_graph_normalized_cycle_factor_two_wordEvery individual disjoint cycle factor of a normalized allowed permutation can be isolated as a product of two actual hops. The…
- simple_graph_normalized_word_to_hop_wordEvery signed normalized word lifts to an actual hop word with exactly twice its length and the same product.
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.
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.
refine ⟨[h₀⁻¹,h₀*p], ?_, by simp, by simp⟩
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.
intro h hh have hcases : h = h₀⁻¹ ∨ h = h₀*p := by simpa using hh rcases hcases with rfl | rfl
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.
uses
simple_graph_is_hop_inv· exact simple_graph_is_hop_inv G h₀ hh₀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.
· 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
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.
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