simple_graph_normalized_word_to_hop_word
Every signed normalized word lifts to an actual hop word with exactly twice its length and the same product.
Statement
theorem simple_graph_normalized_word_to_hop_word {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (w : List (Equiv.Perm V)) (hw : ∀ p ∈ w, simple_graph_normalized_hop G h₀ p ∨ simple_graph_normalized_hop G h₀ p⁻¹) : ∃ u : List (Equiv.Perm V), (∀ h ∈ u, simple_graph_is_hop G h) ∧ u.length = 2*w.length ∧ u.prod = w.prod
- Source
- Routine word-metric/cycle-factor assembly for IN-262 / OP-543, using the verified baseline normalization. The remaining quadratic diameter theorem is conjectural; no diameter assumption is silently discharged and no research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_normalized_hop_two_wordEvery normalized allowed permutation is the product of exactly two actual hops on an undirected graph. No vertex is allowed to wait during…
- simple_graph_normalized_hop_inverse_two_wordThe inverse of a normalized allowed permutation also has a two-hop realization, although it need not itself be normalized allowed.
- 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_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…
- Used by 1
- simple_graph_leap_word_bound_of_normalizedA signed normalized-word diameter bound D implies an actual hop-word diameter bound 2D+1. The normalized diameter bound remains an…
The proof, explained
The proof proceeds by induction on the word w. In the base case of an empty word, the empty list trivially satisfies the conditions. For the inductive step p :: t, the head p is represented as a 2-hop word using helper lemmas for normalized hops and their inverses, while the induction hypothesis provides a hop word for the tail t; concatenating these two words gives a hop word of twice the length whose product is preserved.
The theorem is proved by induction on the list w.
We perform induction on the word w, producing a base case for the empty list and an inductive step for a list with head p and tail t.
induction' w with p t ihThe claim holds for the empty list w = [].
For the empty word, the empty list u = [] serves as the witness: all its elements are vacuously hops, its length is 0 = 2 * 0, and its product is the identity element, all verified by simplification.
· refine ⟨[], by simp, by simp, by simp⟩
By the induction hypothesis, there exists a hop word u_t for the tail t of length 2 * length(t) and product prod(t).
Using List.mem_cons_self and List.mem_cons_of_mem, we verify that the head p and all elements of the tail t satisfy the signed normalized hop condition. Applying the induction hypothesis to the tail gives the witness word u_t.
uses
List.mem_cons_self,List.mem_cons_of_mem· have hp : simple_graph_normalized_hop G h₀ p ∨ simple_graph_normalized_hop G h₀ p⁻¹ := hw p List.mem_cons_self have ht : ∀ q ∈ t, simple_graph_normalized_hop G h₀ q ∨ simple_graph_normalized_hop G h₀ q⁻¹ := fun q hq => hw q (List.mem_cons_of_mem p hq) obtain ⟨u_t, hu_t_hop, hu_t_len, hu_t_prod⟩ := ih ht
The head permutation p can be represented as a length-2 list of hops w_p with product p.
We case split on whether p or p⁻¹ is a normalized hop. If p is a normalized hop, simple_graph_normalized_hop_two_word yields a 2-hop word with product p. If p⁻¹ is a normalized hop, simple_graph_normalized_hop_inverse_two_word applied to p⁻¹ yields a 2-hop word with product (p⁻¹)⁻¹ = p by inv_inv.
uses
simple_graph_normalized_hop_two_word,simple_graph_normalized_hop_inverse_two_word,inv_invhave h_p : ∃ w_p : List (Equiv.Perm V), (∀ h ∈ w_p, simple_graph_is_hop G h) ∧ w_p.length = 2 ∧ w_p.prod = p := by rcases hp with hpos | hneg · exact simple_graph_normalized_hop_two_word G h₀ p hh₀ hpos · obtain ⟨w_p, hw1, hw2, hw3⟩ := simple_graph_normalized_hop_inverse_two_word G h₀ p⁻¹ hh₀ hneg refine ⟨w_p, hw1, hw2, ?_⟩ rw [hw3, inv_inv] obtain ⟨w_p, hw_p_hop, hw_p_len, hw_p_prod⟩ := h_p
Every permutation in the concatenated list w_p ++ u_t is a hop.
We propose w_p ++ u_t as the witness for the composite word p :: t. By List.mem_append, any element in the concatenation is either in w_p or in u_t, both of which consist entirely of hops.
uses
List.mem_appendrefine ⟨w_p ++ u_t, ?_, ?_, ?_⟩ · intro h hh rw [List.mem_append] at hh rcases hh with hh | hh · exact hw_p_hop h hh · exact hu_t_hop h hh
The length of w_p ++ u_t is 2 * length(p :: t).
Rewriting by List.length_append and List.length_cons reduces the goal to 2 + 2 * length(t) = 2 * (length(t) + 1), which is discharged by linear arithmetic (omega).
uses
List.length_append,List.length_cons· rw [List.length_append, hw_p_len, hu_t_len, List.length_cons] omega
The product of w_p ++ u_t is equal to prod(p :: t).
By List.prod_append and List.prod_cons, the product evaluates to prod(w_p) * prod(u_t) = p * prod(t) = prod(p :: t).
uses
List.prod_append,List.prod_cons· rw [List.prod_append, hw_p_prod, hu_t_prod, List.prod_cons]
List.mem_cons_self- The head element a belongs to the list a :: l.
List.mem_cons_of_mem- If an element belongs to l, it also belongs to y :: l.
simple_graph_normalized_hop_two_word- If h₀ is a hop and p is a normalized hop with respect to h₀, then p can be written as the product of a length-2 list of hops.
simple_graph_normalized_hop_inverse_two_word- If h₀ is a hop and p is a normalized hop with respect to h₀, then p⁻¹ can be written as the product of a length-2 list of hops.
inv_inv- Inverting an element twice yields the original element: (a⁻¹)⁻¹ = a.
List.mem_append- An element belongs to s ++ t if and only if it belongs to s or to t.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_cons- Prepending an element to a list increases its length by 1.
List.prod_append- The product of the concatenation of two lists is the product of their respective products.
List.prod_cons- The product of a :: l is a multiplied by the product of l.
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_word_to_hop_word {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (w : List (Equiv.Perm V)) (hw : ∀ p ∈ w, simple_graph_normalized_hop G h₀ p ∨ simple_graph_normalized_hop G h₀ p⁻¹) : ∃ u : List (Equiv.Perm V), (∀ h ∈ u, simple_graph_is_hop G h) ∧ u.length = 2*w.length ∧ u.prod = w.prod := by induction' w with p t ih · refine ⟨[], by simp, by simp, by simp⟩ · have hp : simple_graph_normalized_hop G h₀ p ∨ simple_graph_normalized_hop G h₀ p⁻¹ := hw p List.mem_cons_self have ht : ∀ q ∈ t, simple_graph_normalized_hop G h₀ q ∨ simple_graph_normalized_hop G h₀ q⁻¹ := fun q hq => hw q (List.mem_cons_of_mem p hq) obtain ⟨u_t, hu_t_hop, hu_t_len, hu_t_prod⟩ := ih ht have h_p : ∃ w_p : List (Equiv.Perm V), (∀ h ∈ w_p, simple_graph_is_hop G h) ∧ w_p.length = 2 ∧ w_p.prod = p := by rcases hp with hpos | hneg · exact simple_graph_normalized_hop_two_word G h₀ p hh₀ hpos · obtain ⟨w_p, hw1, hw2, hw3⟩ := simple_graph_normalized_hop_inverse_two_word G h₀ p⁻¹ hh₀ hneg refine ⟨w_p, hw1, hw2, ?_⟩ rw [hw3, inv_inv] obtain ⟨w_p, hw_p_hop, hw_p_len, hw_p_prod⟩ := h_p refine ⟨w_p ++ u_t, ?_, ?_, ?_⟩ · intro h hh rw [List.mem_append] at hh rcases hh with hh | hh · exact hw_p_hop h hh · exact hu_t_hop h hh · rw [List.length_append, hw_p_len, hu_t_len, List.length_cons] omega · rw [List.prod_append, hw_p_prod, hu_t_prod, List.prod_cons]