AFTD Auto-Formalizing Theoretical Domains

simple_graph_leap_group_normalized_cosets

theoremverified

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
Used by 1

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}$.

  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.

    lines 6–8

    uses Subgroup.closure_induction

      let K := simple_graph_normalized_hop_group G h₀
      intro g hg
      refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hg
  2. 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.

    lines 9–13

    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
  3. The identity element satisfies $1 \in K$.

    Because $K$ is a subgroup, $1 \in K$, which establishes the left disjunct via `Or.inl`.

    line 14

    uses Or.inl

      · exact Or.inl K.one_mem
  4. The 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$.

    lines 15–28

    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
  5. 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$.

    lines 29–37

    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$.

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

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
See it in the graphDiscuss this resultChallenge it