AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_word_to_hop_word

theoremverified

Every signed normalized word lifts to an actual hop word with exactly twice its length and the same product.

Statement

theorem simple_graph_normalized_word_to_hop_word {V : Type*} (G : SimpleGraph V)
    (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀)
    (w : List (Equiv.Perm V))
    (hw : ∀ p ∈ w, simple_graph_normalized_hop G h₀ p ∨
      simple_graph_normalized_hop G h₀ p⁻¹) :
    ∃ u : List (Equiv.Perm V), (∀ h ∈ u, simple_graph_is_hop G h) ∧
      u.length = 2*w.length ∧ u.prod = w.prod
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
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_normalized_hop_inverse_two_wordThe inverse of a normalized allowed permutation also has a two-hop realization, although it need not itself be normalized allowed.
  • 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

The proof, explained

The proof proceeds by induction on the word w. In the base case of an empty word, the empty list trivially satisfies the conditions. For the inductive step p :: t, the head p is represented as a 2-hop word using helper lemmas for normalized hops and their inverses, while the induction hypothesis provides a hop word for the tail t; concatenating these two words gives a hop word of twice the length whose product is preserved.

  1. The theorem is proved by induction on the list w.

    We perform induction on the word w, producing a base case for the empty list and an inductive step for a list with head p and tail t.

    line 8

      induction' w with p t ih
  2. The claim holds for the empty list w = [].

    For the empty word, the empty list u = [] serves as the witness: all its elements are vacuously hops, its length is 0 = 2 * 0, and its product is the identity element, all verified by simplification.

    line 9

      · refine ⟨[], by simp, by simp, by simp⟩
  3. By the induction hypothesis, there exists a hop word u_t for the tail t of length 2 * length(t) and product prod(t).

    Using List.mem_cons_self and List.mem_cons_of_mem, we verify that the head p and all elements of the tail t satisfy the signed normalized hop condition. Applying the induction hypothesis to the tail gives the witness word u_t.

    lines 10–14

    uses List.mem_cons_self, List.mem_cons_of_mem

      · have hp : simple_graph_normalized_hop G h₀ p ∨ simple_graph_normalized_hop G h₀ p⁻¹ :=
          hw p List.mem_cons_self
        have ht : ∀ q ∈ t, simple_graph_normalized_hop G h₀ q ∨ simple_graph_normalized_hop G h₀ q⁻¹ :=
          fun q hq => hw q (List.mem_cons_of_mem p hq)
        obtain ⟨u_t, hu_t_hop, hu_t_len, hu_t_prod⟩ := ih ht
  4. The head permutation p can be represented as a length-2 list of hops w_p with product p.

    We case split on whether p or p⁻¹ is a normalized hop. If p is a normalized hop, simple_graph_normalized_hop_two_word yields a 2-hop word with product p. If p⁻¹ is a normalized hop, simple_graph_normalized_hop_inverse_two_word applied to p⁻¹ yields a 2-hop word with product (p⁻¹)⁻¹ = p by inv_inv.

    lines 15–22

    uses simple_graph_normalized_hop_two_word, simple_graph_normalized_hop_inverse_two_word, inv_inv

        have h_p : ∃ w_p : List (Equiv.Perm V), (∀ h ∈ w_p, simple_graph_is_hop G h) ∧
            w_p.length = 2 ∧ w_p.prod = p := by
          rcases hp with hpos | hneg
          · exact simple_graph_normalized_hop_two_word G h₀ p hh₀ hpos
          · obtain ⟨w_p, hw1, hw2, hw3⟩ := simple_graph_normalized_hop_inverse_two_word G h₀ p⁻¹ hh₀ hneg
            refine ⟨w_p, hw1, hw2, ?_⟩
            rw [hw3, inv_inv]
        obtain ⟨w_p, hw_p_hop, hw_p_len, hw_p_prod⟩ := h_p
  5. Every permutation in the concatenated list w_p ++ u_t is a hop.

    We propose w_p ++ u_t as the witness for the composite word p :: t. By List.mem_append, any element in the concatenation is either in w_p or in u_t, both of which consist entirely of hops.

    lines 23–28

    uses List.mem_append

        refine ⟨w_p ++ u_t, ?_, ?_, ?_⟩
        · intro h hh
          rw [List.mem_append] at hh
          rcases hh with hh | hh
          · exact hw_p_hop h hh
          · exact hu_t_hop h hh
  6. The length of w_p ++ u_t is 2 * length(p :: t).

    Rewriting by List.length_append and List.length_cons reduces the goal to 2 + 2 * length(t) = 2 * (length(t) + 1), which is discharged by linear arithmetic (omega).

    lines 29–30

    uses List.length_append, List.length_cons

        · rw [List.length_append, hw_p_len, hu_t_len, List.length_cons]
          omega
  7. The product of w_p ++ u_t is equal to prod(p :: t).

    By List.prod_append and List.prod_cons, the product evaluates to prod(w_p) * prod(u_t) = p * prod(t) = prod(p :: t).

    line 31

    uses List.prod_append, List.prod_cons

        · rw [List.prod_append, hw_p_prod, hu_t_prod, List.prod_cons]
List.mem_cons_self
The head element a belongs to the list a :: l.
List.mem_cons_of_mem
If an element belongs to l, it also belongs to y :: l.
simple_graph_normalized_hop_two_word
If h₀ is a hop and p is a normalized hop with respect to h₀, then p can be written as the product of a length-2 list of hops.
simple_graph_normalized_hop_inverse_two_word
If h₀ is a hop and p is a normalized hop with respect to h₀, then p⁻¹ can be written as the product of a length-2 list of hops.
inv_inv
Inverting an element twice yields the original element: (a⁻¹)⁻¹ = a.
List.mem_append
An element belongs to s ++ t if and only if it belongs to s or to t.
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
List.length_cons
Prepending an element to a list increases its length by 1.
List.prod_append
The product of the concatenation of two lists is the product of their respective products.
List.prod_cons
The product of a :: l is a multiplied by the product of l.

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_word_to_hop_word {V : Type*} (G : SimpleGraph V)    (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀)    (w : List (Equiv.Perm V))    (hw : ∀ p ∈ w, simple_graph_normalized_hop G h₀ p ∨      simple_graph_normalized_hop G h₀ p⁻¹) :    ∃ u : List (Equiv.Perm V), (∀ h ∈ u, simple_graph_is_hop G h) ∧      u.length = 2*w.length ∧ u.prod = w.prod := by  induction' w with p t ih  · refine ⟨[], by simp, by simp, by simp⟩  · have hp : simple_graph_normalized_hop G h₀ p ∨ simple_graph_normalized_hop G h₀ p⁻¹ :=      hw p List.mem_cons_self    have ht : ∀ q ∈ t, simple_graph_normalized_hop G h₀ q ∨ simple_graph_normalized_hop G h₀ q⁻¹ :=      fun q hq => hw q (List.mem_cons_of_mem p hq)    obtain ⟨u_t, hu_t_hop, hu_t_len, hu_t_prod⟩ := ih ht    have h_p : ∃ w_p : List (Equiv.Perm V), (∀ h ∈ w_p, simple_graph_is_hop G h) ∧        w_p.length = 2 ∧ w_p.prod = p := by      rcases hp with hpos | hneg      · exact simple_graph_normalized_hop_two_word G h₀ p hh₀ hpos      · obtain ⟨w_p, hw1, hw2, hw3⟩ := simple_graph_normalized_hop_inverse_two_word G h₀ p⁻¹ hh₀ hneg        refine ⟨w_p, hw1, hw2, ?_⟩        rw [hw3, inv_inv]    obtain ⟨w_p, hw_p_hop, hw_p_len, hw_p_prod⟩ := h_p    refine ⟨w_p ++ u_t, ?_, ?_, ?_⟩    · intro h hh      rw [List.mem_append] at hh      rcases hh with hh | hh      · exact hw_p_hop h hh      · exact hu_t_hop h hh    · rw [List.length_append, hw_p_len, hu_t_len, List.length_cons]      omega    · rw [List.prod_append, hw_p_prod, hu_t_prod, List.prod_cons]
See it in the graphDiscuss this resultChallenge it