AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_group_le

theoremverified

For a fixed baseline hop, its normalized subgroup is contained in the original leap group.

Statement

theorem simple_graph_normalized_hop_group_le {V : Type*}
    (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) :
    simple_graph_normalized_hop_group G h₀ ≤ simple_graph_leap_group G
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_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_is_hop_invThe inverse of a hop is a hop (the graph is undirected).
  • 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…

The proof, explained

To show that the normalized hop group generated by {p | h₀ * p is a hop} is contained in the leap group generated by all hops, it suffices to show that every generating permutation p belongs to the leap group. Since h₀ is a hop, its inverse h₀⁻¹ is also a hop, and thus both h₀⁻¹ and h₀ * p belong to the leap group. The claim follows because the leap group is closed under multiplication, so it contains the product h₀⁻¹ * (h₀ * p) = p.

  1. It suffices to show that every generator of the normalized hop group belongs to the leap group.

    We unfold the definition of simple_graph_normalized_hop_group, which is the subgroup closure of the normalized hops {p | h₀ * p is a hop}, and rewrite with Subgroup.closure_le to reduce the subgroup inclusion to proving that every generator p belongs to the leap group. We then fix an arbitrary permutation p and assume h₀ * p is a hop (hypothesis hp).

    lines 4–5

    uses simple_graph_normalized_hop_group, Subgroup.closure_le

      rw [simple_graph_normalized_hop_group, Subgroup.closure_le]
      intro p hp
  2. Both h₀⁻¹ and h₀ * p belong to the leap group of G.

    Since h₀ is a hop by assumption, its inverse h₀⁻¹ is also a hop by simple_graph_is_hop_inv, and therefore belongs to the leap group because any generator belongs to its subgroup closure (Subgroup.subset_closure). Similarly, by the assumption hp that p is a normalized hop, h₀ * p is a hop, so it also belongs to the leap group by Subgroup.subset_closure.

    lines 6–8

    uses Subgroup.subset_closure, simple_graph_is_hop_inv

      have ha : h₀⁻¹ ∈ simple_graph_leap_group G :=
        Subgroup.subset_closure (simple_graph_is_hop_inv G h₀ hh₀)
      have hb : h₀*p ∈ simple_graph_leap_group G := Subgroup.subset_closure hp
  3. The permutation p belongs to the leap group of G, completing the proof.

    Because the leap group is a subgroup, it contains the product h₀⁻¹ * (h₀ * p) by closure under multiplication (mul_mem). Using associativity (mul_assoc) and group inverse cancellation, h₀⁻¹ * (h₀ * p) simplifies to p, proving that p belongs to the leap group.

    line 9

    uses mul_assoc, mul_mem

      simpa [mul_assoc] using (simple_graph_leap_group G).mul_mem ha hb
simple_graph_normalized_hop_group
The definition of the normalized hop group with respect to a base hop h₀, defined as the subgroup generated by all permutations p such that h₀ * p is a hop.
Subgroup.closure_le
A subgroup closure ⟨k⟩ is contained in a subgroup K if and only if the generating set k is a subset of K.
Subgroup.subset_closure
Every element of a generating set k is contained in the subgroup closure ⟨k⟩.
simple_graph_is_hop_inv
If a permutation h is a hop on a simple graph G, then its inverse h⁻¹ is also a hop on G.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
mul_mem
If two elements belong to a subgroup (or any set closed under multiplication), their product also belongs to it.

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_normalized_hop_group_le {V : Type*}    (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) :    simple_graph_normalized_hop_group G h₀ ≤ simple_graph_leap_group G := by  rw [simple_graph_normalized_hop_group, Subgroup.closure_le]  intro p hp  have ha : h₀⁻¹ ∈ simple_graph_leap_group G :=    Subgroup.subset_closure (simple_graph_is_hop_inv G h₀ hh₀)  have hb : h₀*p ∈ simple_graph_leap_group G := Subgroup.subset_closure hp  simpa [mul_assoc] using (simple_graph_leap_group G).mul_mem ha hb
See it in the graphDiscuss this resultChallenge it