simple_graph_leap_group_normalized_cosets
Every leap lies in the normalized subgroup or in its left coset by the baseline hop. Together with containment, this gives index at most two WITHIN the leap group, not within the full permutation group. No finite, connected or diameter hypothesis is asserted.
Statement
theorem simple_graph_leap_group_normalized_cosets {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : ∀ g ∈ simple_graph_leap_group G, g ∈ simple_graph_normalized_hop_group G h₀ ∨ h₀⁻¹*g ∈ 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 8
- 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_normalized_hop_group_conjugate_invConjugation by the inverse baseline also preserves the normalized subgroup.
- simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
- 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 leap group is the subgroup generated by all hops of $G$. The theorem establishes that every leap $g$ lies either in the normalized hop group $K$ or in the coset $h_0 K$ (that is, $h_0^{-1} g \in K$), showing that the normalized hop group has index at most two in the leap group. The proof proceeds by subgroup closure induction on the generators: any hop generator $h$ satisfies $h_0 (h_0^{-1} h) = h$, placing $h_0^{-1} h$ in the generating set of $K$, the identity lies in $K$, and closure under multiplication and inversion follows by case analysis using the fact that $K$ contains $h_0^{\pm 2}$ and is stable under conjugation by $h_0^{\pm 1}$.
It suffices to show that the property $g \in K \lor h_0^{-1} g \in K$ holds for every generator hop, holds for the identity, and is preserved under multiplication and inversion.
Let $K$ be the normalized hop group with baseline $h_0$. By definition, the leap group is the subgroup generated by the set of all hops of $G$. Using subgroup closure induction (`Subgroup.closure_induction`), proving that every leap $g$ satisfies $g \in K \lor h_0^{-1} g \in K$ reduces to four obligations: generators, identity, products, and inverses.
uses
Subgroup.closure_inductionlet K := simple_graph_normalized_hop_group G h₀ intro g hg refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hg
Every hop generator $h$ lies in the coset $h_0 K$, so $h_0^{-1} h \in K$.
For any hop $h$, we verify the right alternative $h_0^{-1} h \in K$. By definition, $K$ is the subgroup generated by all permutations $p$ such that $h_0 p$ is a hop. Since $h_0 (h_0^{-1} h) = h$ is a hop by hypothesis, $h_0^{-1} h$ is in the generating set of $K$, and hence in $K$ by `Subgroup.subset_closure`. The equality $h_0 (h_0^{-1} h) = h$ simplifies using associativity (`mul_assoc`) and inverse cancellation.
uses
Subgroup.subset_closure,mul_assoc· intro h hh right apply Subgroup.subset_closure change simple_graph_is_hop G (h₀*(h₀⁻¹*h)) simpa [mul_assoc] using hh
The identity element satisfies $1 \in K$.
Because $K$ is a subgroup, $1 \in K$, which establishes the left disjunct via `Or.inl`.
uses
Or.inl· exact Or.inl K.one_memThe property is closed under products: if $x, y \in K \cup h_0 K$, then $x y \in K \cup h_0 K$.
We perform a case analysis on which coset $x$ and $y$ belong to: 1. If $x \in K$ and $y \in K$, then $x y \in K$ by subgroup closure under multiplication. 2. If $x \in K$ and $h_0^{-1} y \in K$, conjugation invariance (`simple_graph_normalized_hop_group_conjugate_inv`) implies $h_0^{-1} x h_0 \in K$. Multiplying by $h_0^{-1} y \in K$ gives $(h_0^{-1} x h_0)(h_0^{-1} y) = h_0^{-1} (x y) \in K$. 3. If $h_0^{-1} x \in K$ and $y \in K$, multiplying them in $K$ yields $(h_0^{-1} x) y = h_0^{-1} (x y) \in K$ by associativity (`mul_assoc`). 4. If $h_0^{-1} x \in K$ and $h_0^{-1} y \in K$, conjugation invariance (`simple_graph_normalized_hop_group_conjugate`) shows $h_0 (h_0^{-1} x) h_0^{-1} \in K$. Together with $h_0^2 \in K$ (`simple_graph_normalized_hop_group_square`) and $h_0^{-1} y \in K$, their product $[h_0 (h_0^{-1} x) h_0^{-1}] (h_0^2) (h_0^{-1} y)$ equals $x y$, so $x y \in K$.
uses
Or.inl,simple_graph_normalized_hop_group_conjugate_inv,mul_assoc,simple_graph_normalized_hop_group_conjugate,simple_graph_normalized_hop_group_square· intro x y hx hy hcx hcy rcases hcx with hcx | hcx <;> rcases hcy with hcy | hcy · exact Or.inl (K.mul_mem hcx hcy) · right have hc := simple_graph_normalized_hop_group_conjugate_inv G h₀ x hh₀ hcx have hh := K.mul_mem hc hcy convert hh using 1 <;> group · right simpa [mul_assoc] using K.mul_mem hcx hcy · left have hc := simple_graph_normalized_hop_group_conjugate G h₀ (h₀⁻¹*x) hh₀ hcx have hs := simple_graph_normalized_hop_group_square G h₀ hh₀ have hh := K.mul_mem (K.mul_mem hc hs) hcy convert hh using 1 <;> group
The property is closed under taking inverses: if $x \in K \cup h_0 K$, then $x^{-1} \in K \cup h_0 K$.
We split into two cases: 1. If $x \in K$, then $x^{-1} \in K$ because $K$ is closed under taking inverses. 2. If $h_0^{-1} x \in K$, then its inverse $(h_0^{-1} x)^{-1}$ is in $K$. By `simple_graph_normalized_hop_group_conjugate_inv`, conjugating by $h_0^{-1}$ gives $h_0^{-1} (h_0^{-1} x)^{-1} h_0 \in K$. Multiplying this with $h_0^{-2} \in K$ (from `simple_graph_normalized_hop_group_square_inv`) yields $[h_0^{-1} (h_0^{-1} x)^{-1} h_0] (h_0^{-2}) = h_0^{-1} x^{-1} \in K$.
uses
Or.inl,simple_graph_normalized_hop_group_conjugate_inv,simple_graph_normalized_hop_group_square_inv· intro x hx hcx rcases hcx with hcx | hcx · exact Or.inl (K.inv_mem hcx) · right have hc := simple_graph_normalized_hop_group_conjugate_inv G h₀ (h₀⁻¹*x)⁻¹ hh₀ (K.inv_mem hcx) have hs := simple_graph_normalized_hop_group_square_inv G h₀ hh₀ have hh := K.mul_mem hc hs convert hh using 1 <;> group
Subgroup.closure_induction- Principle of induction for subgroup closures: to show that a property holds for all elements of $\langle k \rangle$, it suffices to check that it holds for all generators in $k$ and the identity, and is closed under products and inverses.
Subgroup.subset_closure- Every element of a generating set $k$ belongs to the subgroup closure $\langle k \rangle$.
mul_assoc- Group multiplication is associative: $(a * b) * c = a * (b * c)$.
Or.inl- From a proof of $a$, infer the disjunction $a \lor b$.
simple_graph_normalized_hop_group_conjugate_inv- If $h_0$ is a hop and $p$ belongs to the normalized hop group with baseline $h_0$, then the conjugate $h_0^{-1} p h_0$ also belongs to that group.
simple_graph_normalized_hop_group_conjugate- If $h_0$ is a hop and $p$ belongs to the normalized hop group with baseline $h_0$, then the conjugate $h_0 p h_0^{-1}$ also belongs to that group.
simple_graph_normalized_hop_group_square- If $h_0$ is a hop, then $h_0^2 = h_0 * h_0$ belongs to the normalized hop group with baseline $h_0$.
simple_graph_normalized_hop_group_square_inv- If $h_0$ is a hop, then $h_0^{-2} = h_0^{-1} * h_0^{-1}$ belongs to the normalized hop group with baseline $h_0$.
- The tactic `group` automates the simplification of expressions in the group of permutations, verifying algebraic identities like $(h_0^{-1} x h_0)(h_0^{-1} y) = h_0^{-1} (x y)$ and $[h_0 (h_0^{-1} x) h_0^{-1}] (h_0^2) (h_0^{-1} y) = x y$.
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_leap_group_normalized_cosets {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : ∀ g ∈ simple_graph_leap_group G, g ∈ simple_graph_normalized_hop_group G h₀ ∨ h₀⁻¹*g ∈ simple_graph_normalized_hop_group G h₀ := by let K := simple_graph_normalized_hop_group G h₀ intro g hg refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hg · intro h hh right apply Subgroup.subset_closure change simple_graph_is_hop G (h₀*(h₀⁻¹*h)) simpa [mul_assoc] using hh · exact Or.inl K.one_mem · intro x y hx hy hcx hcy rcases hcx with hcx | hcx <;> rcases hcy with hcy | hcy · exact Or.inl (K.mul_mem hcx hcy) · right have hc := simple_graph_normalized_hop_group_conjugate_inv G h₀ x hh₀ hcx have hh := K.mul_mem hc hcy convert hh using 1 <;> group · right simpa [mul_assoc] using K.mul_mem hcx hcy · left have hc := simple_graph_normalized_hop_group_conjugate G h₀ (h₀⁻¹*x) hh₀ hcx have hs := simple_graph_normalized_hop_group_square G h₀ hh₀ have hh := K.mul_mem (K.mul_mem hc hs) hcy convert hh using 1 <;> group · intro x hx hcx rcases hcx with hcx | hcx · exact Or.inl (K.inv_mem hcx) · right have hc := simple_graph_normalized_hop_group_conjugate_inv G h₀ (h₀⁻¹*x)⁻¹ hh₀ (K.inv_mem hcx) have hs := simple_graph_normalized_hop_group_square_inv G h₀ hh₀ have hh := K.mul_mem hc hs convert hh using 1 <;> group