AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_cycle_factor_two_word

theoremverified

Every individual disjoint cycle factor of a normalized allowed permutation can be isolated as a product of two actual hops. The intermediate baseline moves all vertices, so this does not assume idle moves in the original graph.

Statement

theorem simple_graph_normalized_cycle_factor_two_word {V : Type*}
    [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (h₀ p q : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀)
    (hp : simple_graph_normalized_hop G h₀ p) (hq : q ∈ p.cycleFactorsFinset) :
    ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧
      w.length = 2 ∧ w.prod = q
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 4
  • simple_graph_normalized_hop_recombineIf p is allowed relative to a baseline hop h0, and a PERMUTATION q chooses p(v) or v at each vertex, then q is also allowed relative to…
  • simple_graph_normalized_hop_two_wordEvery normalized allowed permutation is the product of exactly two actual hops on an undirected graph. No vertex is allowed to wait during…
  • 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…

The proof, explained

To isolate any disjoint cycle factor q of a normalized hop p as a product of two hops, we first show that q agrees with p on its support and acts as the identity elsewhere. A recombination lemma then implies that q inherits the property of being a normalized hop with respect to the base hop h₀. The result follows by applying the two-word decomposition theorem for normalized hops to q.

  1. For every vertex v, either q v = p v or q v = v.

    We distinguish whether v lies in the support of q. If v ∈ supp(q), then because q is a cycle factor of p, q(v) = p(v) by Equiv.Perm.mem_cycleFactorsFinset_iff.mp. Otherwise, v ∉ supp(q), so q fixes v by Equiv.Perm.notMem_support.mp.

    lines 7–13

    uses Equiv.Perm.mem_cycleFactorsFinset_iff.mp, Equiv.Perm.notMem_support.mp

      have hq_agree : ∀ v : V, q v = p v ∨ q v = v := by
        intro v
        by_cases hv : v ∈ q.support
        · left
          exact (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hq).2 v hv
        · right
          exact Equiv.Perm.notMem_support.mp hv
  2. The cycle factor q is a normalized hop with respect to h₀.

    Since h₀ is a hop, p is a normalized hop with respect to h₀, and q agrees with p or fixes every vertex, simple_graph_normalized_hop_recombine implies that q is also a normalized hop.

    lines 14–15

    uses simple_graph_normalized_hop_recombine

      have hq_norm : simple_graph_normalized_hop G h₀ q :=
        simple_graph_normalized_hop_recombine G h₀ p q hh₀ hp hq_agree
  3. There exists a list of two hops in G whose product equals q.

    Applying simple_graph_normalized_hop_two_word to the normalized hop q produces a list of two actual hops whose product is q.

    line 16

    uses simple_graph_normalized_hop_two_word

      exact simple_graph_normalized_hop_two_word G h₀ q hh₀ hq_norm
Equiv.Perm.mem_cycleFactorsFinset_iff.mp
If a permutation q belongs to the cycle factors of p, then q is a cycle and q a = p a for every element a in the support of q.
Equiv.Perm.notMem_support.mp
If an element is not in the support of a permutation, the permutation fixes that element.
simple_graph_normalized_hop_recombine
If h₀ is a hop, p is a normalized hop with respect to h₀, and q agrees with p or fixes every vertex, then q is also a normalized hop with respect to h₀.
simple_graph_normalized_hop_two_word
Any normalized hop with respect to a base hop h₀ can be factored into a word of length 2 whose elements are hops.

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_cycle_factor_two_word {V : Type*}    [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (h₀ p q : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀)    (hp : simple_graph_normalized_hop G h₀ p) (hq : q ∈ p.cycleFactorsFinset) :    ∃ w : List (Equiv.Perm V), (∀ h ∈ w, simple_graph_is_hop G h) ∧      w.length = 2 ∧ w.prod = q := by  have hq_agree : ∀ v : V, q v = p v ∨ q v = v := by    intro v    by_cases hv : v ∈ q.support    · left      exact (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hq).2 v hv    · right      exact Equiv.Perm.notMem_support.mp hv  have hq_norm : simple_graph_normalized_hop G h₀ q :=    simple_graph_normalized_hop_recombine G h₀ p q hh₀ hp hq_agree  exact simple_graph_normalized_hop_two_word G h₀ q hh₀ hq_norm
See it in the graphDiscuss this resultChallenge it