wild_involutions_equiv_of_card_and_fixed_count
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
- wild_involutions_conjugate_of_fixed_countFor two involutive permutations of any finite type, equality of the numbers of fixed points implies that a permutation simultaneously…
- Used by 1
- wild_involution_closed_partial_isomorphism_extendsA matching isomorphism on closed finite subsets extends globally when both involutions have a unique fixed point and the subsets either…
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.
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).
uses
Fintype.equivOfCardEqclassical let e₀ : V ≃ W := Fintype.equivOfCardEq hcard let g' : Equiv.Perm V := (e₀.trans g).trans e₀.symm
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.
uses
Equiv.trans_apply,Equiv.apply_symm_apply,Equiv.symm_apply_applyhave hg' : Function.Involutive g' := by intro x simp only [g',Equiv.trans_apply,Equiv.apply_symm_apply] rw [hg,Equiv.symm_apply_apply]
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.
uses
card_bij,mem_filter,mem_univ,true_and,congrArghave 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]
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.
uses
wild_involutions_conjugate_of_fixed_countobtain ⟨c,hc⟩ := wild_involutions_conjugate_of_fixed_count f g' hf hg' (hfix.trans hgc.symm)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).
uses
congrArgrefine ⟨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
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 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