cycle_cover_difference_cycle_factor_two_word
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.
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.
uses
Equiv.Perm.mem_cycleFactorsFinset_iff.mphave hr_prop := (Equiv.Perm.mem_cycleFactorsFinset_iff.mp hr).2The 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.
uses
if_true,if_false,Equiv.Perm.mul_apply,Equiv.Perm.apply_mem_support.mprhave 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
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.
uses
Finite.injective_iff_bijective.mp,Equiv.ofBijective_applylet 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 _ _ _
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.
refine ⟨[p⁻¹, A], ?_, by simp, ?_⟩
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.
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
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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