AFTD Auto-Formalizing Theoretical Domains

wild_involutions_conjugate_of_fixed_count

theoremverified

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

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.

  1. 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.

    lines 12–15

    uses Equiv.Perm.cycleType_of_pow_prime_eq_one

      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
  2. 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.

    lines 16–22

    uses card_sdiff_of_subset, subset_univ

      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]
  3. 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.

    lines 23–30

    uses Multiset.sum_replicate, nsmul_eq_mul, Nat.cast_id

      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]
  4. 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.

    lines 31–34

    uses congrArg

      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)
  5. 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.

    line 35

    uses isConj_iff.mp, Equiv.Perm.isConj_of_cycleType_eq

      obtain ⟨e, he⟩ := isConj_iff.mp (Equiv.Perm.isConj_of_cycleType_eq htype)
  6. 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).

    lines 36–39

    uses congrArg

      refine ⟨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.

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

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
See it in the graphDiscuss this resultChallenge it