wild_involutions_conjugate_of_fixed_count
For two involutive permutations of any finite type, equality of the numbers of fixed points implies that a permutation simultaneously carries every f-edge to a g-edge.
Statement
theorem wild_involutions_conjugate_of_fixed_count {V : Type*} [Fintype V] [DecidableEq V] (f g : Equiv.Perm V) (hf : Function.Involutive f) (hg : Function.Involutive g) (hcard : (univ.filter fun x => f x = x).card = (univ.filter fun x => g x = x).card) : ∃ e : Equiv.Perm V, ∀ x, e (f x) = g (e x)
- Source
- IN-382 / OP-306 campaign9, 2026-10-30. Standard finite involution conjugacy and permutation transport, supporting the moment route for https://arxiv.org/html/2610.22142v1. Background https://arxiv.org/abs/0911.3604 . No new wild-number bound or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- wild_normalized_color_canonical_isomorphismFor odd q>=3, every chosen color of a symmetric idempotent row-injective array on Fin(3q) is carried to the canonical matching by a vertex…
- wild_normalized_array_single_color_isomorphismFor two symmetric idempotent row-injective arrays A and B on Fin n and any chosen colors a and b, there is a vertex permutation e sending…
- wild_involutions_equiv_of_card_and_fixed_countCross-type version of finite involution conjugacy: equal finite cardinalities and equal fixed-point counts give an intertwining equivalence.
The proof, explained
Two involutive permutations of a finite set are conjugate if and only if they have the same cycle type. Because every non-trivial cycle of an involution has length 2, the cycle type is uniquely determined by the number of 2-cycles, which is half the cardinality of the support. The support is the complement of the fixed-point set, so equality of the fixed-point counts implies that both involutions have supports of the same size and therefore identical cycle types. Conjugacy in the symmetric group then yields a permutation e such that e * f * e⁻¹ = g, which on evaluation at e x gives e (f x) = g (e x) for all x.
The involutions f and g satisfy f ^ 2 = 1 and g ^ 2 = 1, and their cycle types consist exclusively of 2-cycles.
Because f and g are involutions, applying either map twice is the identity, so f ^ 2 = 1 and g ^ 2 = 1. Applying Equiv.Perm.cycleType_of_pow_prime_eq_one for the prime p = 2 shows that every non-trivial cycle in their disjoint cycle decompositions has length 2, so the cycle types are multisets repeating 2 for their respective lengths.
uses
Equiv.Perm.cycleType_of_pow_prime_eq_onehave hf2 : f ^ 2 = 1 := by ext x; exact hf x have hg2 : g ^ 2 = 1 := by ext x; exact hg x have hfs := Equiv.Perm.cycleType_of_pow_prime_eq_one hf2 have hgs := Equiv.Perm.cycleType_of_pow_prime_eq_one hg2
The supports of f and g have equal cardinality: |f.support| = |g.support|.
The support of any permutation a is the complement of its fixed points in the universe V. Since V is finite, the cardinality of this complement is |V| minus the number of fixed points (by card_sdiff_of_subset and subset_univ). By hypothesis hcard, f and g have the same number of fixed points, so their supports have the same cardinality.
uses
card_sdiff_of_subset,subset_univhave hc : f.support.card = g.support.card := by have he (a : Equiv.Perm V) : a.support = univ \ (univ.filter fun x => a x = x) := by ext x simp rw [he f, he g, card_sdiff_of_subset (subset_univ _), card_sdiff_of_subset (subset_univ _), hcard]
The support sizes satisfy |f.support| = 2 * |f.cycleType| and |g.support| = 2 * |g.cycleType|.
The size of the support of a permutation equals the sum of the cycle lengths in its cycle decomposition. Since all cycles in the cycle types of f and g have length 2, this sum simplifies via Multiset.sum_replicate, nsmul_eq_mul, and Nat.cast_id to twice the number of 2-cycles in each permutation.
uses
Multiset.sum_replicate,nsmul_eq_mul,Nat.cast_idhave hsf : f.support.card = f.cycleType.card * 2 := by rw [← f.sum_cycleType] conv_lhs => rw [hfs] simp only [Multiset.sum_replicate, nsmul_eq_mul, Nat.cast_id] have hsg : g.support.card = g.cycleType.card * 2 := by rw [← g.sum_cycleType] conv_lhs => rw [hgs] simp only [Multiset.sum_replicate, nsmul_eq_mul, Nat.cast_id]
f and g have the same number of 2-cycles, and hence identical cycle types: f.cycleType = g.cycleType.
Equating the support sizes gives 2 * |f.cycleType| = 2 * |g.cycleType|, which implies |f.cycleType| = |g.cycleType| by integer arithmetic (omega). Since both cycle types consist of 2s repeated for their respective lengths, applying congrArg to this length equality proves f.cycleType = g.cycleType.
uses
congrArghave hs : f.cycleType.card * 2 = g.cycleType.card * 2 := by omega have hlen : f.cycleType.card = g.cycleType.card := by omega have htype : f.cycleType = g.cycleType := hfs.trans ((congrArg (fun k => Multiset.replicate k 2) hlen).trans hgs.symm)
f and g are conjugate: there exists a permutation e such that e * f * e⁻¹ = g.
In the symmetric group of a finite set, two permutations with identical cycle types are conjugate (Equiv.Perm.isConj_of_cycleType_eq). By the definition of conjugacy (isConj_iff.mp), there is an element e such that e * f * e⁻¹ = g.
uses
isConj_iff.mp,Equiv.Perm.isConj_of_cycleType_eqobtain ⟨e, he⟩ := isConj_iff.mp (Equiv.Perm.isConj_of_cycleType_eq htype)The conjugating permutation e satisfies e (f x) = g (e x) for all x ∈ V.
Using e as witness, we evaluate both sides of the conjugacy identity e * f * e⁻¹ = g at e x via congrArg. Permutation composition simplifies (e * f * e⁻¹) (e x) to e (f (e⁻¹ (e x))) = e (f x), yielding e (f x) = g (e x).
uses
congrArgrefine ⟨e, ?_⟩ intro x have hh := congrArg (fun a : Equiv.Perm V => a (e x)) he simpa using hh
Equiv.Perm.cycleType_of_pow_prime_eq_one- If σ^p = 1 for a prime p, then every cycle in the cycle type of σ has length p.
Equiv.Perm.isConj_of_cycleType_eq- Two permutations on a finite set with the same cycle type are conjugate.
Nat.cast_id- The canonical embedding of natural numbers into itself is the identity map.
card_sdiff_of_subset- For finite sets s ⊆ t, the cardinality of the difference t \ s is |t| - |s|.
congrArg- If two arguments are equal, applying any function to them yields equal values.
isConj_iff.mp- If two group elements σ and τ are conjugate, then there exists c such that c * σ * c⁻¹ = τ.
nsmul_eq_mul- Multiplication of a ring element by a natural number scalar n equals the product n * a.
subset_univ- Every subset of a finite type is a subset of the universal set.
Multiset.sum_replicate- The sum of a multiset consisting of n copies of an element a is n • a.
- The group-theoretic conjugacy relation e * f * e⁻¹ = g translates to the pointwise equality e (f x) = g (e x) by evaluating both permutations at e x and using the fact that e⁻¹ (e x) = x.
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.
open Finsetopen scoped BigOperators Classicalset_option maxHeartbeats 3000000theorem wild_involutions_conjugate_of_fixed_count {V : Type*} [Fintype V] [DecidableEq V] (f g : Equiv.Perm V) (hf : Function.Involutive f) (hg : Function.Involutive g) (hcard : (univ.filter fun x => f x = x).card = (univ.filter fun x => g x = x).card) : ∃ e : Equiv.Perm V, ∀ x, e (f x) = g (e x) := by have hf2 : f ^ 2 = 1 := by ext x; exact hf x have hg2 : g ^ 2 = 1 := by ext x; exact hg x have hfs := Equiv.Perm.cycleType_of_pow_prime_eq_one hf2 have hgs := Equiv.Perm.cycleType_of_pow_prime_eq_one hg2 have hc : f.support.card = g.support.card := by have he (a : Equiv.Perm V) : a.support = univ \ (univ.filter fun x => a x = x) := by ext x simp rw [he f, he g, card_sdiff_of_subset (subset_univ _), card_sdiff_of_subset (subset_univ _), hcard] have hsf : f.support.card = f.cycleType.card * 2 := by rw [← f.sum_cycleType] conv_lhs => rw [hfs] simp only [Multiset.sum_replicate, nsmul_eq_mul, Nat.cast_id] have hsg : g.support.card = g.cycleType.card * 2 := by rw [← g.sum_cycleType] conv_lhs => rw [hgs] simp only [Multiset.sum_replicate, nsmul_eq_mul, Nat.cast_id] have hs : f.cycleType.card * 2 = g.cycleType.card * 2 := by omega have hlen : f.cycleType.card = g.cycleType.card := by omega have htype : f.cycleType = g.cycleType := hfs.trans ((congrArg (fun k => Multiset.replicate k 2) hlen).trans hgs.symm) obtain ⟨e, he⟩ := isConj_iff.mp (Equiv.Perm.isConj_of_cycleType_eq htype) refine ⟨e, ?_⟩ intro x have hh := congrArg (fun a : Equiv.Perm V => a (e x)) he simpa using hh