simple_graph_normalized_hop_group_conjugate_inv
Conjugation by the inverse baseline also preserves the normalized subgroup.
Statement
theorem simple_graph_normalized_hop_group_conjugate_inv {V : Type*} (G : SimpleGraph V) (h₀ p : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (hp : p ∈ simple_graph_normalized_hop_group G h₀) : 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_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_normalized_hop_group_conjugateConjugation by the baseline preserves the normalized subgroup.
- simple_graph_normalized_hop_group_squareThe 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.
- Used by 1
- simple_graph_leap_group_normalized_cosetsEvery leap lies in the normalized subgroup or in its left coset by the baseline hop. Together with containment, this gives index at most…
The proof, explained
To show that conjugation by the inverse baseline preserves the normalized hop group $K$, the element $h₀⁻¹ p h₀$ is expressed as the product $h₀⁻² (h₀ p h₀⁻¹) h₀^2$. Each factor—the conjugate $h₀ p h₀⁻¹$, the square $h₀^2$, and the inverse square $h₀⁻²$—is already known to belong to $K$. Since $K$ is a subgroup, their product lies in $K$, and group cancellation simplifies this product to $h₀⁻¹ p h₀$.
Define $K$ as the normalized hop group, and obtain that $h₀ p h₀⁻¹$, $h₀^2$, and $h₀⁻²$ are in $K$.
Let $K$ denote the normalized hop group of $G$ with baseline $h₀$. By `simple_graph_normalized_hop_group_conjugate`, the conjugate $h₀ p h₀⁻¹$ is in $K$. Furthermore, by `simple_graph_normalized_hop_group_square` and `simple_graph_normalized_hop_group_square_inv`, the square $h₀^2$ and inverse square $h₀⁻²$ also belong to $K$.
uses
simple_graph_normalized_hop_group_conjugate,simple_graph_normalized_hop_group_square,simple_graph_normalized_hop_group_square_invlet K := simple_graph_normalized_hop_group G h₀ have hm := simple_graph_normalized_hop_group_conjugate G h₀ p hh₀ hp have hs := simple_graph_normalized_hop_group_square G h₀ hh₀ have hsi := simple_graph_normalized_hop_group_square_inv G h₀ hh₀
The product $h₀⁻² (h₀ p h₀⁻¹) h₀^2$ belongs to $K$.
Because $K$ is a subgroup, it is closed under multiplication (`K.mul_mem`). Multiplying the three elements $h₀⁻²$, $h₀ p h₀⁻¹$, and $h₀^2$ establishes that $(h₀⁻¹ h₀⁻¹) (h₀ p h₀⁻¹) (h₀ h₀) \in K$.
uses
K.mul_memhave hh := K.mul_mem (K.mul_mem hsi hm) hs$h₀⁻¹ p h₀ \in K$. automation
The goal element $h₀⁻¹ p h₀$ matches the product from the previous step by simplifying the group expression: the inner adjacent inverses $h₀⁻¹ h₀$ and $h₀⁻¹ h₀$ cancel out. The `group` tactic verifies this formal equality in the group of permutations.
convert hh using 1 <;> group
simple_graph_normalized_hop_group_conjugate- If $h₀$ is a hop of $G$ and $p$ is in the normalized hop group with baseline $h₀$, then $h₀ p h₀⁻¹$ is also in the normalized hop group.
simple_graph_normalized_hop_group_square- If $h₀$ is a hop of $G$, then $h₀^2$ is in the normalized hop group with baseline $h₀$.
simple_graph_normalized_hop_group_square_inv- If $h₀$ is a hop of $G$, then $h₀⁻²$ is in the normalized hop group with baseline $h₀$.
K.mul_mem- A subgroup is closed under multiplication: if $x, y \in K$, then $x y \in K$.
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_group_conjugate_inv {V : Type*} (G : SimpleGraph V) (h₀ p : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (hp : p ∈ simple_graph_normalized_hop_group G h₀) : h₀⁻¹*p*h₀ ∈ simple_graph_normalized_hop_group G h₀ := by let K := simple_graph_normalized_hop_group G h₀ have hm := simple_graph_normalized_hop_group_conjugate G h₀ p hh₀ hp have hs := simple_graph_normalized_hop_group_square G h₀ hh₀ have hsi := simple_graph_normalized_hop_group_square_inv G h₀ hh₀ have hh := K.mul_mem (K.mul_mem hsi hm) hs convert hh using 1 <;> group