simple_graph_normalized_hop_conjugate_mem
Conjugating one normalized allowed permutation by the baseline yields an element of the normalized SUBGROUP, without claiming it stays in the normalized generating set.
Statement
theorem simple_graph_normalized_hop_conjugate_mem {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) : h₀*p*h₀⁻¹ ∈ simple_graph_normalized_hop_group G h₀
- 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 5
- 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_normalized_hop_groupThe subgroup generated by permutations allowed relative to a fixed baseline hop.
- simple_graph_normalized_hop_group_square_invThe inverse square of a baseline hop belongs to the normalized subgroup.
- 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 1
- simple_graph_normalized_hop_group_conjugateConjugation by the baseline preserves the normalized subgroup.
The proof, explained
To show that the conjugate h₀ * p * h₀⁻¹ belongs to the normalized hop subgroup K, the proof factors it as q⁻¹ * s, where q = h₀⁻¹ * (h₀ * p)⁻¹ and s = h₀⁻¹ * h₀⁻¹. The factor q belongs to K because h₀ * q = (h₀ * p)⁻¹ is the inverse of a hop and therefore an element of the generating set. Since s also belongs to K by a prior lemma, subgroup closure implies q⁻¹ * s ∈ K, and simplifying q⁻¹ * s yields the desired conjugate h₀ * p * h₀⁻¹.
The element h₀⁻¹ * (h₀ * p)⁻¹ belongs to the normalized hop subgroup K.
Let K denote simple_graph_normalized_hop_group G h₀, the subgroup generated by permutations x such that h₀ * x is a hop. By Subgroup.subset_closure, to show h₀⁻¹ * (h₀ * p)⁻¹ ∈ K it suffices to show that h₀ * (h₀⁻¹ * (h₀ * p)⁻¹) is a hop. By associativity (mul_assoc), this product simplifies to (h₀ * p)⁻¹. Since h₀ * p is a hop by hypothesis hp, its inverse (h₀ * p)⁻¹ is also a hop by simple_graph_is_hop_inv.
uses
Subgroup.subset_closure,mul_assoc,simple_graph_is_hop_invlet K := simple_graph_normalized_hop_group G h₀ have hq : h₀⁻¹*(h₀*p)⁻¹ ∈ K := by apply Subgroup.subset_closure change simple_graph_is_hop G (h₀*(h₀⁻¹*(h₀*p)⁻¹)) simpa [mul_assoc] using simple_graph_is_hop_inv G (h₀*p) hp
The square h₀⁻¹ * h₀⁻¹ belongs to K.
By simple_graph_normalized_hop_group_square_inv, the element h₀⁻¹ * h₀⁻¹ belongs to K because h₀ is a hop (hypothesis hh₀).
uses
simple_graph_normalized_hop_group_square_invhave hs : h₀⁻¹*h₀⁻¹ ∈ K := simple_graph_normalized_hop_group_square_inv G h₀ hh₀The conjugate h₀ * p * h₀⁻¹ belongs to K.
Since K is a subgroup containing q = h₀⁻¹ * (h₀ * p)⁻¹ and s = h₀⁻¹ * h₀⁻¹, it contains q⁻¹ * s. Expanding q⁻¹ * s in group theory gives (h₀⁻¹ * (h₀ * p)⁻¹)⁻¹ * (h₀⁻¹ * h₀⁻¹) = (h₀ * p) * h₀ * h₀⁻¹ * h₀⁻¹ = h₀ * p * h₀⁻¹, which establishes the goal.
convert K.mul_mem (K.inv_mem hq) hs using 1 <;> group
Subgroup.subset_closure- Every element of a generating set is contained in the subgroup it generates.
mul_assoc- Multiplication in a group is associative: (a * b) * c = a * (b * c).
simple_graph_is_hop_inv- If a permutation is a hop on a simple graph (maps every vertex to an adjacent vertex), then its inverse is also a hop.
simple_graph_normalized_hop_group_square_inv- If h₀ is a hop, then the square h₀⁻¹ * h₀⁻¹ belongs to the normalized hop subgroup associated with h₀.
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_conjugate_mem {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) : h₀*p*h₀⁻¹ ∈ simple_graph_normalized_hop_group G h₀ := by let K := simple_graph_normalized_hop_group G h₀ have hq : h₀⁻¹*(h₀*p)⁻¹ ∈ K := by apply Subgroup.subset_closure change simple_graph_is_hop G (h₀*(h₀⁻¹*(h₀*p)⁻¹)) simpa [mul_assoc] using simple_graph_is_hop_inv G (h₀*p) hp have hs : h₀⁻¹*h₀⁻¹ ∈ K := simple_graph_normalized_hop_group_square_inv G h₀ hh₀ convert K.mul_mem (K.inv_mem hq) hs using 1 <;> group