AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_inverse_two_word

theoremverified

The inverse of a normalized allowed permutation also has a two-hop realization, although it need not itself be normalized allowed.

Statement

theorem simple_graph_normalized_hop_inverse_two_word {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) :
    ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧
      w.length = 2 ∧ w.prod = p⁻¹
Source
Routine word-metric/cycle-factor assembly for IN-262 / OP-543, using the verified baseline normalization. The remaining quadratic diameter theorem is conjectural; no diameter assumption is silently discharged and no research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_is_hop_invThe inverse of a hop is a hop (the graph is undirected).
  • 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

The proof, explained

To show that $p⁻¹$ has a two-hop realization, we exhibit the candidate word $w = [(h₀ * p)⁻¹, h₀]$. The first element is a hop because $h₀ * p$ is a hop by normalized allowance and the inverse of any hop is a hop; the second element $h₀$ is a hop by hypothesis. Finally, computing the product in the permutation group gives $(h₀ * p)⁻¹ * h₀ = p⁻¹ * h₀⁻¹ * h₀ = p⁻¹$.

  1. We choose the candidate word $w = [(h₀ * p)⁻¹, h₀]$, whose length is 2.

    We provide the explicit list $[(h₀ * p)⁻¹, h₀]$ as a witness for the existential quantifier. Its length is 2 by definition (discharged by reflexivity), leaving two subgoals: verifying that every permutation in the list is a hop, and that the product of the list is $p⁻¹$.

    line 6

      refine ⟨[(h₀ * p)⁻¹, h₀], ?_, rfl, ?_⟩
  2. Every permutation in the list $[(h₀ * p)⁻¹, h₀]$ is a hop on $G$.

    Let $h$ be an element in the candidate word. Simplifying list membership shows that either $h = (h₀ * p)⁻¹$ or $h = h₀$. If $h = (h₀ * p)⁻¹$, the hypothesis `hp` states that $h₀ * p$ is a hop, so its inverse is a hop by `simple_graph_is_hop_inv`. If $h = h₀$, it is a hop directly by hypothesis `hh₀`.

    lines 7–11

    uses List.mem_cons, List.not_mem_nil, or_false, simple_graph_is_hop_inv

      · intro h hh
        simp only [List.mem_cons, List.not_mem_nil, or_false] at hh
        rcases hh with rfl | rfl
        · exact simple_graph_is_hop_inv G (h₀ * p) hp
        · exact hh₀
  3. The product of the word $[(h₀ * p)⁻¹, h₀]$ equals $p⁻¹$. automation

    Unfolding the definition of list product reduces $[(h₀ * p)⁻¹, h₀].\mathrm{prod}$ to $((h₀ * p)⁻¹ * h₀) * 1 = (h₀ * p)⁻¹ * h₀$. The `group` tactic then closes the goal by simplifying this word in the permutation group to $p⁻¹ * h₀⁻¹ * h₀ = p⁻¹$.

    lines 12–13

    uses List.prod_cons, List.prod_nil, mul_one

      · simp only [List.prod_cons, List.prod_nil, mul_one]
        group
List.mem_cons
An element belongs to the list `b :: l` if and only if it equals `b` or belongs to `l`.
List.not_mem_nil
The empty list contains no elements.
or_false
A proposition disjoined with `False` is equivalent to itself: $(P \lor \mathrm{False}) \leftrightarrow P$.
simple_graph_is_hop_inv
If a permutation is a hop on a graph, its inverse permutation is also a hop.
List.prod_cons
The product of elements in a non-empty list `a :: l` is `a * l.prod`.
List.prod_nil
The product of an empty list is 1.
mul_one
Multiplying an element by 1 on the right leaves it unchanged: $a \cdot 1 = a$.

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_inverse_two_word {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) :    ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧      w.length = 2 ∧ w.prod = p⁻¹ := by  refine ⟨[(h₀ * p)⁻¹, h₀], ?_, rfl, ?_⟩  · intro h hh    simp only [List.mem_cons, List.not_mem_nil, or_false] at hh    rcases hh with rfl | rfl    · exact simple_graph_is_hop_inv G (h₀ * p) hp    · exact hh₀  · simp only [List.prod_cons, List.prod_nil, mul_one]    group
See it in the graphDiscuss this resultChallenge it