AFTD Auto-Formalizing Theoretical Domains

wild_involutions_equiv_of_card_and_fixed_count

theoremverified

Cross-type version of finite involution conjugacy: equal finite cardinalities and equal fixed-point counts give an intertwining equivalence.

Statement

theorem wild_involutions_equiv_of_card_and_fixed_count
    {V W : Type*} [Fintype V] [Fintype W]
    (f : Equiv.Perm V) (g : Equiv.Perm W)
    (hf : Function.Involutive f) (hg : Function.Involutive g)
    (hcard : Fintype.card V = Fintype.card W)
    (hfix : (univ.filter fun x => f x = x).card =
      (univ.filter fun y => g y = y).card) :
    ∃ e : V ≃ W, ∀ 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
Built on 1
Used by 1

The proof, explained

The proof reduces the cross-type conjugacy problem between involutions f on V and g on W to the same-type case on V. Using the assumption that V and W have equal cardinality, an arbitrary bijection e₀ : V ≃ W pulls g back to an involution g' = e₀⁻¹ ∘ g ∘ e₀ on V. Because e₀ restricts to a bijection between the fixed points of g' and g, the number of fixed points of g' matches that of f. Applying the same-type classification theorem (wild_involutions_conjugate_of_fixed_count) yields a conjugating equivalence c on V, and composing c with e₀ gives the required equivalence e : V ≃ W intertwining f and g.

  1. An arbitrary bijection e₀ : V ≃ W is chosen to pull back the involution g on W to a permutation g' on V.

    Since V and W have equal finite cardinalities (hypothesis hcard), Fintype.equivOfCardEq yields an equivalence e₀ : V ≃ W. Using e₀, g is pulled back to a permutation g' = e₀.symm ∘ g ∘ e₀ on V (defined via (e₀.trans g).trans e₀.symm).

    lines 14–16

    uses Fintype.equivOfCardEq

      classical
      let e₀ : V ≃ W := Fintype.equivOfCardEq hcard
      let g' : Equiv.Perm V := (e₀.trans g).trans e₀.symm
  2. The transferred permutation g' is an involution on V.

    For any x ∈ V, expanding g' (g' x) using Equiv.trans_apply and Equiv.apply_symm_apply simplifies the expression to e₀.symm (g (g (e₀ x))). Since g is an involution (hypothesis hg), g (g (e₀ x)) = e₀ x, and applying e₀.symm yields x by Equiv.symm_apply_apply.

    lines 17–20

    uses Equiv.trans_apply, Equiv.apply_symm_apply, Equiv.symm_apply_apply

      have hg' : Function.Involutive g' := by
        intro x
        simp only [g',Equiv.trans_apply,Equiv.apply_symm_apply]
        rw [hg,Equiv.symm_apply_apply]
  3. g' and g have the same number of fixed points.

    We apply card_bij with the map x ↦ e₀ x to show that e₀ restricts to a bijection between the fixed points of g' in V and the fixed points of g in W: (1) if g' x = x, applying e₀ to both sides gives e₀ (g' x) = e₀ x, which unfolds to g (e₀ x) = e₀ x, so e₀ x is fixed by g; (2) the map is injective because e₀ is an equivalence; (3) for any fixed point y of g, its preimage e₀.symm y is fixed by g' because g' (e₀.symm y) = e₀.symm (g (e₀ (e₀.symm y))) = e₀.symm (g y) = e₀.symm y. In each branch, membership in the filtered Finset is simplified using mem_filter, mem_univ, and true_and, and equality of function values uses congrArg.

    lines 21–33

    uses card_bij, mem_filter, mem_univ, true_and, congrArg

      have hgc : (univ.filter fun x => g' x = x).card =
          (univ.filter fun y => g y = y).card := by
        apply card_bij (fun x _ => e₀ x)
        · intro x hx
          simp only [mem_filter,mem_univ,true_and] at hx ⊢
          have hh := congrArg e₀ hx
          simpa [g'] using hh
        · intro x _ y _ h
          exact e₀.injective h
        · intro y hy
          refine ⟨e₀.symm y,?_,e₀.apply_symm_apply y⟩
          simp only [mem_filter,mem_univ,true_and] at hy ⊢
          simp [g',hy]
  4. There exists an equivalence c on V conjugating f to g'.

    Both f and g' are involutions on the same finite type V. Hypothesis hfix states that f and g have the same fixed-point count, and hgc shows g' and g have the same fixed-point count, so f and g' have equal fixed-point counts by transitivity. Applying the same-type theorem wild_involutions_conjugate_of_fixed_count yields an equivalence c : Equiv.Perm V such that c (f x) = g' (c x) for all x.

    lines 34–35

    uses wild_involutions_conjugate_of_fixed_count

      obtain ⟨c,hc⟩ := wild_involutions_conjugate_of_fixed_count f g' hf hg'
        (hfix.trans hgc.symm)
  5. The composite equivalence e = c.trans e₀ intertwines f and g.

    We propose e = c.trans e₀ (the composite sending x to e₀ (c x)). For any x ∈ V, applying e₀ to the conjugacy relation c (f x) = g' (c x) via congrArg gives e₀ (c (f x)) = e₀ (g' (c x)). By definition of g', e₀ (g' (c x)) simplifies to g (e₀ (c x)), which means e (f x) = g (e x).

    lines 36–39

    uses congrArg

      refine ⟨c.trans e₀,?_⟩
      intro x
      have hh := congrArg e₀ (hc x)
      simpa [g'] using hh
Fintype.equivOfCardEq
Two finite types with the same cardinality admit an equivalence between them.
Equiv.trans_apply
Evaluating the composition of two equivalences f and g at an element a equals g (f a).
Equiv.apply_symm_apply
Applying an equivalence to the image of its inverse is the identity: e (e.symm x) = x.
Equiv.symm_apply_apply
Applying the inverse of an equivalence to the image of the equivalence is the identity: e.symm (e x) = x.
card_bij
Two finite sets have equal cardinality if there exists a map between them that is well-defined into the codomain, injective, and surjective on the sets.
mem_filter
An element belongs to filter p s if and only if it belongs to s and satisfies the predicate p.
mem_univ
Every element of a finite type belongs to the universal finite set univ.
true_and
The proposition True ∧ p simplifies to p.
congrArg
Equality of inputs implies equality of their values under any function: if a₁ = a₂ then f a₁ = f a₂.
wild_involutions_conjugate_of_fixed_count
Two involutions on the same finite type are conjugate by an equivalence if and only if they have the same number of fixed points.

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 4000000set_option maxRecDepth 10000theorem wild_involutions_equiv_of_card_and_fixed_count    {V W : Type*} [Fintype V] [Fintype W]    (f : Equiv.Perm V) (g : Equiv.Perm W)    (hf : Function.Involutive f) (hg : Function.Involutive g)    (hcard : Fintype.card V = Fintype.card W)    (hfix : (univ.filter fun x => f x = x).card =      (univ.filter fun y => g y = y).card) :    ∃ e : V ≃ W, ∀ x, e (f x) = g (e x) := by  classical  let e₀ : V ≃ W := Fintype.equivOfCardEq hcard  let g' : Equiv.Perm V := (e₀.trans g).trans e₀.symm  have hg' : Function.Involutive g' := by    intro x    simp only [g',Equiv.trans_apply,Equiv.apply_symm_apply]    rw [hg,Equiv.symm_apply_apply]  have hgc : (univ.filter fun x => g' x = x).card =      (univ.filter fun y => g y = y).card := by    apply card_bij (fun x _ => e₀ x)    · intro x hx      simp only [mem_filter,mem_univ,true_and] at hx ⊢      have hh := congrArg e₀ hx      simpa [g'] using hh    · intro x _ y _ h      exact e₀.injective h    · intro y hy      refine ⟨e₀.symm y,?_,e₀.apply_symm_apply y⟩      simp only [mem_filter,mem_univ,true_and] at hy ⊢      simp [g',hy]  obtain ⟨c,hc⟩ := wild_involutions_conjugate_of_fixed_count f g' hf hg'    (hfix.trans hgc.symm)  refine ⟨c.trans e₀,?_⟩  intro x  have hh := congrArg e₀ (hc x)  simpa [g'] using hh
See it in the graphDiscuss this resultChallenge it