AFTD Auto-Formalizing Theoretical Domains

cycle_cover_difference_cycle_factor_two_word

theoremverified

If p and q are cycle covers of a relation R, then every cycle factor of p⁻¹ q is a product of at most two letters, each a cycle cover or the inverse of one.

Statement

theorem cycle_cover_difference_cycle_factor_two_word {V : Type*} [Fintype V] [DecidableEq V]
    (R : V → V → Prop) (p q r : Equiv.Perm V) (hp : ∀ v, R v (p v)) (hq : ∀ v, R v (q v))
    (hr : r ∈ (p⁻¹ * q).cycleFactorsFinset) :
    ∃ w : List (Equiv.Perm V),
      (∀ x ∈ w, (∀ v, R v (x v)) ∨ (∀ v, R (x v) v)) ∧ w.length ≤ 2 ∧ w.prod = r
Source
step towards simple_graph_normalized_hop_group_quadratic_word_diameter
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The cycle factor r is represented as the two-letter word [p⁻¹, A], where A is constructed by cycle surgery: setting A(v) = q(v) on the support of r and A(v) = p(v) elsewhere. Because r agrees with p⁻¹ q on its support and the support of r is invariant under r, the map A is proven injective, and thus a permutation since V is finite. Both p⁻¹ (the inverse of a cycle cover) and A (a cycle cover by piecewise definition) satisfy the required relation conditions, and their product evaluates to p⁻¹ q = r on the support of r and to p⁻¹ p = id = r outside it.

  1. On the support of r, the permutation r coincides with p⁻¹ q.

    From the hypothesis that r is a cycle factor of p⁻¹ q, the lemma `Equiv.Perm.mem_cycleFactorsFinset_iff.mp` extracts the property that r(a) = (p⁻¹ q)(a) for every element a in the support of r.

    line 7

    uses Equiv.Perm.mem_cycleFactorsFinset_iff.mp

      have hr_prop := (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hr).2
  2. The spliced function f(v) = (if v ∈ r.support then q v else p v) is injective.

    Suppose f(x) = f(y). We split into cases depending on whether x and y lie in the support of r. If both belong to the support, q(x) = q(y), so x = y by injectivity of q. If neither belongs to the support, p(x) = p(y), so x = y by injectivity of p. If x ∈ r.support and y ∉ r.support, then q(x) = p(y). Since r(x) = (p⁻¹ q)(x) = p⁻¹(q(x)), applying p gives p(r(x)) = q(x) = p(y), whence r(x) = y by injectivity of p. But the support of r is invariant under r, so x ∈ r.support implies r(x) ∈ r.support, forcing y ∈ r.support, a contradiction. The remaining case x ∉ r.support and y ∈ r.support reaches a contradiction symmetrically.

    lines 8–37

    uses if_true, if_false, Equiv.Perm.mul_apply, Equiv.Perm.apply_mem_support.mpr

      have h_inj : Function.Injective (fun v => if v ∈ r.support then q v else p v) := by
        intro x y h
        dsimp only at h
        by_cases hx : x ∈ r.support <;> by_cases hy : y ∈ r.support
        · simp only [hx, hy, if_true] at h
          exact q.injective h
        · simp only [hx, hy, if_true, if_false] at h
          exfalso
          have hrx : r x = (p⁻¹ * q) x := hr_prop x hx
          have h1 : p (r x) = q x := by
            rw [hrx, Equiv.Perm.mul_apply]
            simp
          have h2 : p (r x) = p y := by rw [h1, h]
          have h3 : r x = y := p.injective h2
          have hsupp : r x ∈ r.support := Equiv.Perm.apply_mem_support.mpr hx
          rw [h3] at hsupp
          exact hy hsupp
        · simp only [hx, hy, if_true, if_false] at h
          exfalso
          have hry : r y = (p⁻¹ * q) y := hr_prop y hy
          have h1 : p (r y) = q y := by
            rw [hry, Equiv.Perm.mul_apply]
            simp
          have h2 : p (r y) = p x := by rw [h1, ← h]
          have h3 : r y = x := p.injective h2
          have hsupp : r y ∈ r.support := Equiv.Perm.apply_mem_support.mpr hy
          rw [h3] at hsupp
          exact hx hsupp
        · simp only [hx, hy, if_false] at h
          exact p.injective h
  3. The spliced function defines a permutation A of V.

    Since V is finite, injectivity of the spliced function implies its bijectivity via `Finite.injective_iff_bijective.mp`. It is packaged into a permutation A whose evaluation A(v) equals q(v) when v ∈ r.support and p(v) otherwise.

    lines 38–40

    uses Finite.injective_iff_bijective.mp, Equiv.ofBijective_apply

      let A : Equiv.Perm V := Equiv.ofBijective (fun v => if v ∈ r.support then q v else p v)
        (Finite.injective_iff_bijective.mp h_inj)
      have hA_apply (v : V) : A v = if v ∈ r.support then q v else p v := Equiv.ofBijective_apply _ _ _
  4. The list w = [p⁻¹, A] has length at most 2, serving as the candidate word.

    We supply [p⁻¹, A] as the witness for the existential quantifier. Its length is 2 ≤ 2, which holds immediately by simplification, leaving the cover properties and the product identity to be verified.

    line 41

      refine ⟨[p⁻¹, A], ?_, by simp, ?_⟩
  5. Every element of [p⁻¹, A] is either a cycle cover or the inverse of a cycle cover for R.

    The elements of [p⁻¹, A] are p⁻¹ and A. For p⁻¹, the assumption that p is a cycle cover gives R(p⁻¹(v), p(p⁻¹(v))) = R(p⁻¹(v), v) for all v, so p⁻¹ is the inverse of a cycle cover. For A, by definition A(v) is q(v) if v ∈ r.support and p(v) otherwise; since both p and q are cycle covers, R(v, A(v)) holds in both cases, showing A is a cycle cover.

    lines 42–54

    uses List.mem_cons, List.not_mem_nil, or_false

      · intro x hx
        simp only [List.mem_cons, List.not_mem_nil, or_false] at hx
        rcases hx with rfl | rfl
        · right
          intro v
          have h := hp (p⁻¹ v)
          simpa using h
        · left
          intro v
          rw [hA_apply]
          split_ifs with hv
          · exact hq v
          · exact hp v
  6. The product of the word [p⁻¹, A] equals r.

    The product of [p⁻¹, A] is p⁻¹ A. By extensionality, we compare (p⁻¹ A)(v) = p⁻¹(A(v)) with r(v) for any v. If v ∈ r.support, A(v) = q(v), so p⁻¹(A(v)) = p⁻¹(q(v)) = (p⁻¹ q)(v) = r(v). If v ∉ r.support, A(v) = p(v), so p⁻¹(A(v)) = p⁻¹(p(v)) = v, which equals r(v) since permutations fix points outside their support. Hence p⁻¹ A = r.

    lines 55–64

    uses List.prod_cons, List.prod_nil, mul_one, Equiv.Perm.mul_apply, if_true, if_false, Equiv.Perm.notMem_support.mp

      · simp only [List.prod_cons, List.prod_nil, mul_one]
        ext v
        rw [Equiv.Perm.mul_apply, hA_apply]
        by_cases hv : v ∈ r.support
        · simp only [hv, if_true]
          have hrx := hr_prop v hv
          rw [hrx, Equiv.Perm.mul_apply]
        · simp only [hv, if_false]
          rw [Equiv.Perm.notMem_support.mp hv]
          simp
Equiv.Perm.mem_cycleFactorsFinset_iff.mp
If a permutation r is in the finset of cycle factors of f, then r is a cycle and r(a) = f(a) for every a in the support of r.
if_true
Evaluating an if-then-else expression whose condition is True yields the then-branch.
if_false
Evaluating an if-then-else expression whose condition is False yields the else-branch.
Equiv.Perm.mul_apply
The composition (product) of permutations f and g evaluated at x is f(g(x)).
Equiv.Perm.apply_mem_support.mpr
If an element is in the support of a permutation, its image under that permutation is also in the support.
Finite.injective_iff_bijective.mp
For a map from a finite type to itself, injectivity implies bijectivity.
Equiv.ofBijective_apply
Evaluating the equivalence constructed from a bijection at an element yields the value of the original function at that element.
List.mem_cons
An element belongs to a non-empty list if and only if it is equal to the head or belongs to the tail.
List.not_mem_nil
No element belongs to the empty list.
or_false
Disjunction with False is equivalent to the proposition itself: P ∨ False ↔ P.
List.prod_cons
The product of elements of a list starting with head a and tail l is a multiplied by the product of l.
List.prod_nil
The product of the empty list in a monoid is the identity element 1.
mul_one
Multiplying an element by 1 on the right yields the element itself.
Equiv.Perm.notMem_support.mp
If an element is not in the support of a permutation, the permutation fixes that element.

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

/-- Cycle factors of p⁻¹q for cycle covers p, q are two-letter words (cycle surgery for covers). -/theorem cycle_cover_difference_cycle_factor_two_word {V : Type*} [Fintype V] [DecidableEq V]    (R : V → V → Prop) (p q r : Equiv.Perm V) (hp : ∀ v, R v (p v)) (hq : ∀ v, R v (q v))    (hr : r ∈ (p⁻¹ * q).cycleFactorsFinset) :    ∃ w : List (Equiv.Perm V),      (∀ x ∈ w, (∀ v, R v (x v)) ∨ (∀ v, R (x v) v)) ∧ w.length ≤ 2 ∧ w.prod = r := by  have hr_prop := (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hr).2  have h_inj : Function.Injective (fun v => if v ∈ r.support then q v else p v) := by    intro x y h    dsimp only at h    by_cases hx : x ∈ r.support <;> by_cases hy : y ∈ r.support    · simp only [hx, hy, if_true] at h      exact q.injective h    · simp only [hx, hy, if_true, if_false] at h      exfalso      have hrx : r x = (p⁻¹ * q) x := hr_prop x hx      have h1 : p (r x) = q x := by        rw [hrx, Equiv.Perm.mul_apply]        simp      have h2 : p (r x) = p y := by rw [h1, h]      have h3 : r x = y := p.injective h2      have hsupp : r x ∈ r.support := Equiv.Perm.apply_mem_support.mpr hx      rw [h3] at hsupp      exact hy hsupp    · simp only [hx, hy, if_true, if_false] at h      exfalso      have hry : r y = (p⁻¹ * q) y := hr_prop y hy      have h1 : p (r y) = q y := by        rw [hry, Equiv.Perm.mul_apply]        simp      have h2 : p (r y) = p x := by rw [h1, ← h]      have h3 : r y = x := p.injective h2      have hsupp : r y ∈ r.support := Equiv.Perm.apply_mem_support.mpr hy      rw [h3] at hsupp      exact hx hsupp    · simp only [hx, hy, if_false] at h      exact p.injective h  let A : Equiv.Perm V := Equiv.ofBijective (fun v => if v ∈ r.support then q v else p v)    (Finite.injective_iff_bijective.mp h_inj)  have hA_apply (v : V) : A v = if v ∈ r.support then q v else p v := Equiv.ofBijective_apply _ _ _  refine ⟨[p⁻¹, A], ?_, by simp, ?_⟩  · intro x hx    simp only [List.mem_cons, List.not_mem_nil, or_false] at hx    rcases hx with rfl | rfl    · right      intro v      have h := hp (p⁻¹ v)      simpa using h    · left      intro v      rw [hA_apply]      split_ifs with hv      · exact hq v      · exact hp v  · simp only [List.prod_cons, List.prod_nil, mul_one]    ext v    rw [Equiv.Perm.mul_apply, hA_apply]    by_cases hv : v ∈ r.support    · simp only [hv, if_true]      have hrx := hr_prop v hv      rw [hrx, Equiv.Perm.mul_apply]    · simp only [hv, if_false]      rw [Equiv.Perm.notMem_support.mp hv]      simp
See it in the graphDiscuss this resultChallenge it