wild_involution_partial_pattern_isomorphism_extends
An isomorphism of arbitrary injective finite patterns, preserving every partner equality including fixed points, extends to an isomorphism of ambient involutions each having a unique fixed point.
Statement
theorem wild_involution_partial_pattern_isomorphism_extends {V J : Type*} [Fintype V] [Fintype J] [DecidableEq V] (f g : Equiv.Perm V) (hf : Function.Involutive f) (hg : Function.Involutive g) (a b : V) (hfa : ∀ x, f x = x ↔ x = a) (hgb : ∀ x, g x = x ↔ x = b) (v w : J → V) (hv : Function.Injective v) (hw : Function.Injective w) (hpattern : ∀ j k, f (v j) = v k ↔ g (w j) = w k) : ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ (∀ j, e (v j) = w j)
- 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_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…
- Used by 2
- wild_involution_pattern_conditioned_bad_count_invariantFor finite matching patterns with the same internal partner equalities, the permutation counts of a whole-bad matching and any prescribed…
- wild_involution_three_set_isomorphismFor two finite involutions with unique fixed points, two three-element subsets can be carried to one another by a global intertwining…
The proof, explained
The proof extends the partial pattern isomorphism v ↦ w to an ambient automorphism conjugating f to g by first completing the patterns to their involution closures. We define S = v(J) ∪ f(v(J)) and T = w(J) ∪ g(w(J)) and show that the pattern-preservation hypothesis implies that the natural parameterizations from J × Bool to S and T share identical fibers. This gives a well-defined equivariant bijection eS : S ≃ T, which necessarily relates the unique fixed points of f and g. Finally, applying the closed extension theorem wild_involution_closed_partial_isomorphism_extends extends eS to a global automorphism e of V conjugating f to g that sends each v(j) to w(j).
The families uv and uw represent the pattern points and their involution partners, and flipping the boolean tag corresponds to applying the ambient involutions f and g.
We define uv(j, c) to be f(v(j)) if c is true and v(j) if c is false, and define uw(j, c) similarly using g and w. Defining flip(j, c) = (j, ¬c), we check that uv(flip(z)) = f(uv(z)) and uw(flip(z)) = g(uw(z)); when c is false this is the definition, and when c is true it follows from f and g being involutions (f(f(x)) = x and g(g(x)) = x).
classical let uv : J × Bool → V := fun z => if z.2 then f (v z.1) else v z.1 let uw : J × Bool → V := fun z => if z.2 then g (w z.1) else w z.1 let flip : J × Bool → J × Bool := fun z => (z.1,!z.2) have hvflip : ∀ z, uv (flip z) = f (uv z) := by rintro ⟨j,c⟩; cases c · rfl · exact (hf (v j)).symm have hwflip : ∀ z, uw (flip z) = g (uw z) := by rintro ⟨j,c⟩; cases c · rfl · exact (hg (w j)).symm
The maps uv and uw have identical kernels: uv(z) = uv(z') if and only if uw(z) = uw(z') for all z, z' ∈ J × Bool.
We split into cases on the boolean tags of z = (j, c) and z' = (k, d). If both are false, this is v(j) = v(k) ↔ w(j) = w(k), which holds by injectivity of v and w. If one is false and the other true, it reduces to f(v(j)) = v(k) ↔ g(w(j)) = w(k), which is the pattern preservation hypothesis hpattern. If both are true, it asserts f(v(j)) = f(v(k)) ↔ g(w(j)) = g(w(k)), which reduces to v(j) = v(k) ↔ w(j) = w(k) since f and g are permutations.
uses
Bool.false_eq_true,if_false,if_true,eq_commhave hkernel : ∀ z z', uv z = uv z' ↔ uw z = uw z' := by rintro ⟨j,c⟩ ⟨k,d⟩ cases c <;> cases d · simp only [uv,uw,Bool.false_eq_true,if_false] exact hv.eq_iff.trans hw.eq_iff.symm · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true,eq_comm] using hpattern k j · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true] using hpattern j k · simp only [uv,uw,if_true,f.injective.eq_iff,g.injective.eq_iff] exact hv.eq_iff.trans hw.eq_iff.symm
The images S = range(uv) and T = range(uw) are finite subsets of V closed under f and g, respectively.
We define S and T as the finset images of uv and uw. For any x, if f(x) ∈ S, then f(x) = uv(z) for some z, so x = f(f(x)) = f(uv(z)) = uv(flip(z)) ∈ S. Conversely, if x = uv(z) ∈ S, then f(x) = uv(flip(z)) ∈ S. An identical calculation with g and uw shows that g(x) ∈ T ↔ x ∈ T.
uses
mem_univlet S : Finset V := univ.image uv let T : Finset V := univ.image uw have hvS : ∀ z, uv z ∈ S := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩ have hwT : ∀ z, uw z ∈ T := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩ have hS : ∀ x, f x ∈ S ↔ x ∈ S := by intro x constructor · intro hx obtain ⟨z,_,hz⟩ := mem_image.mp hx have hh : uv (flip z) = x := by rw [hvflip,hz,hf] exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩ · intro hx obtain ⟨z,_,rfl⟩ := mem_image.mp hx rw [← hvflip]; exact hvS _ have hT : ∀ x, g x ∈ T ↔ x ∈ T := by intro x constructor · intro hx obtain ⟨z,_,hz⟩ := mem_image.mp hx have hh : uw (flip z) = x := by rw [hwflip,hz,hg] exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩ · intro hx obtain ⟨z,_,rfl⟩ := mem_image.mp hx rw [← hwflip]; exact hwT _
There is a bijection eS : S ≃ T satisfying eS(uv(z)) = uw(z) for all z ∈ J × Bool.
Viewing uv and uw as surjections sv : J × Bool ↠ S and tw : J × Bool ↠ T, their fibers coincide because they have the same kernel. Using choice, we pick for each x ∈ S a representative pick(x) in its preimage fiber under sv. Defining eS(x) = tw(pick(x)) gives a bijection via Equiv.ofBijective, and eS(sv(z)) = tw(z) holds for all z.
uses
Subtype.ext,Subtype.ext_iff,Classical.choose,Classical.choose_spec,Equiv.ofBijectivelet sv : J × Bool → {x // x ∈ S} := fun z => ⟨uv z,hvS z⟩ let tw : J × Bool → {x // x ∈ T} := fun z => ⟨uw z,hwT z⟩ have hsv : Function.Surjective sv := by intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property exact ⟨z,Subtype.ext hz⟩ have htw : Function.Surjective tw := by intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property exact ⟨z,Subtype.ext hz⟩ have hker : ∀ z z', sv z = sv z' ↔ tw z = tw z' := by intro z z' simpa only [Subtype.ext_iff] using hkernel z z' let pick : {x // x ∈ S} → J × Bool := fun x => Classical.choose (hsv x) have hpick : ∀ x, sv (pick x) = x := fun x => Classical.choose_spec (hsv x) let eS : {x // x ∈ S} ≃ {x // x ∈ T} := Equiv.ofBijective (fun x => tw (pick x)) (by constructor · intro x y h have hh := (hker (pick x) (pick y)).mpr h simpa only [hpick] using hh · intro y obtain ⟨z,rfl⟩ := htw y exact ⟨sv z,(hker _ _).mp (hpick (sv z))⟩) have heval : ∀ z, eS (sv z) = tw z := fun z => (hker _ _).mp (hpick (sv z))
The bijection eS is an equivariant isomorphism: eS(f(x)) = g(eS(x)) for all x ∈ S.
Every x ∈ S can be written as sv(z). The action of f on S corresponds to flip on J × Bool, since f(sv(z)) = sv(flip(z)). Since eS evaluates sv to tw, we compute eS(f(x)) = eS(sv(flip(z))) = tw(flip(z)) = g(tw(z)) = g(eS(x)).
uses
Subtype.exthave heS : ∀ x : {x // x ∈ S}, (eS ⟨f x.val,(hS x.val).mpr x.property⟩).val = g (eS x).val := by intro x obtain ⟨z,rfl⟩ := hsv x have hh : (⟨f (sv z).val,(hS (sv z).val).mpr (sv z).property⟩ : {x // x ∈ S}) = sv (flip z) := Subtype.ext (hvflip z).symm rw [hh,heval,heval] exact hwflip z
The unique fixed point a of f lies in S if and only if the unique fixed point b of g lies in T.
If a ∈ S, then f(a) = a implies g(eS(a)) = eS(f(a)) = eS(a). Because b is the unique fixed point of g, eS(a) = b, which shows b ∈ T. Conversely, if b ∈ T, by surjectivity of eS we have b = eS(x) for some x ∈ S. Then eS(f(x)) = g(eS(x)) = g(b) = b = eS(x). By injectivity of eS, f(x) = x, so x must be the unique fixed point a of f, proving a ∈ S.
uses
Subtype.ext,congrArghave hmem : a ∈ S ↔ b ∈ T := by constructor · intro ha let x : {x // x ∈ S} := ⟨a,ha⟩ have heq : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x := Subtype.ext ((hfa a).mpr rfl) have hh := heS x rw [heq] at hh have hb : (eS x).val = b := (hgb _).mp hh.symm exact hb ▸ (eS x).property · intro hb obtain ⟨x,hx⟩ := eS.surjective ⟨b,hb⟩ have hh := heS x have hxval : (eS x).val = b := congrArg Subtype.val hx rw [hxval,(hgb b).mpr rfl] at hh have hfix : f x.val = x.val := by have hsub : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x := by apply eS.injective apply Subtype.ext exact hh.trans hxval.symm exact congrArg Subtype.val hsub have ha : x.val = a := (hfa _).mp hfix exact ha ▸ x.property
The equivariant bijection eS extends to an ambient permutation e of V conjugating f to g and mapping each v(j) to w(j).
Applying wild_involution_closed_partial_isomorphism_extends with invariant sets S and T and equivariant bijection eS yields a permutation e of V such that e(f(x)) = g(e(x)) for all x ∈ V, and e agrees with eS on S. For each j ∈ J, v(j) = uv(j, false) ∈ S, so e(v(j)) = eS(sv(j, false)) = tw(j, false) = w(j).
uses
wild_involution_closed_partial_isomorphism_extendsobtain ⟨e,he,hext⟩ := wild_involution_closed_partial_isomorphism_extends f g hf hg a b hfa hgb S T hS hT hmem eS heS refine ⟨e,he,?_⟩ intro j have hh := hext (sv (j,false)) rw [heval] at hh exact hh
Bool.false_eq_true- The proposition (false = true) is False.
if_false- An if-then-else expression with condition False reduces to its else branch.
if_true- An if-then-else expression with condition True reduces to its then branch.
eq_comm- Equality is symmetric: a = b is equivalent to b = a.
mem_univ- Every element of a finite type belongs to the universal finset univ.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Subtype.ext_iff- Two subtype elements are equal if and only if their underlying values are equal.
Classical.choose- Produces an explicit witness from an existential proof.
Classical.choose_spec- The witness chosen by Classical.choose satisfies the property.
Equiv.ofBijective- A bijective map between types forms an equivalence (bijection).
congrArg- If two inputs are equal, then applying any function to them yields equal outputs.
wild_involution_closed_partial_isomorphism_extends- An equivariant isomorphism between involution-closed finite subsets, which preserves the condition of containing the unique fixed points, extends to an ambient automorphism conjugating the two involutions.
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_involution_partial_pattern_isomorphism_extends {V J : Type*} [Fintype V] [Fintype J] [DecidableEq V] (f g : Equiv.Perm V) (hf : Function.Involutive f) (hg : Function.Involutive g) (a b : V) (hfa : ∀ x, f x = x ↔ x = a) (hgb : ∀ x, g x = x ↔ x = b) (v w : J → V) (hv : Function.Injective v) (hw : Function.Injective w) (hpattern : ∀ j k, f (v j) = v k ↔ g (w j) = w k) : ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ (∀ j, e (v j) = w j) := by classical let uv : J × Bool → V := fun z => if z.2 then f (v z.1) else v z.1 let uw : J × Bool → V := fun z => if z.2 then g (w z.1) else w z.1 let flip : J × Bool → J × Bool := fun z => (z.1,!z.2) have hvflip : ∀ z, uv (flip z) = f (uv z) := by rintro ⟨j,c⟩; cases c · rfl · exact (hf (v j)).symm have hwflip : ∀ z, uw (flip z) = g (uw z) := by rintro ⟨j,c⟩; cases c · rfl · exact (hg (w j)).symm have hkernel : ∀ z z', uv z = uv z' ↔ uw z = uw z' := by rintro ⟨j,c⟩ ⟨k,d⟩ cases c <;> cases d · simp only [uv,uw,Bool.false_eq_true,if_false] exact hv.eq_iff.trans hw.eq_iff.symm · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true,eq_comm] using hpattern k j · simpa only [uv,uw,Bool.false_eq_true,if_false,if_true] using hpattern j k · simp only [uv,uw,if_true,f.injective.eq_iff,g.injective.eq_iff] exact hv.eq_iff.trans hw.eq_iff.symm let S : Finset V := univ.image uv let T : Finset V := univ.image uw have hvS : ∀ z, uv z ∈ S := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩ have hwT : ∀ z, uw z ∈ T := fun z => mem_image.mpr ⟨z,mem_univ _,rfl⟩ have hS : ∀ x, f x ∈ S ↔ x ∈ S := by intro x constructor · intro hx obtain ⟨z,_,hz⟩ := mem_image.mp hx have hh : uv (flip z) = x := by rw [hvflip,hz,hf] exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩ · intro hx obtain ⟨z,_,rfl⟩ := mem_image.mp hx rw [← hvflip]; exact hvS _ have hT : ∀ x, g x ∈ T ↔ x ∈ T := by intro x constructor · intro hx obtain ⟨z,_,hz⟩ := mem_image.mp hx have hh : uw (flip z) = x := by rw [hwflip,hz,hg] exact mem_image.mpr ⟨flip z,mem_univ _,hh⟩ · intro hx obtain ⟨z,_,rfl⟩ := mem_image.mp hx rw [← hwflip]; exact hwT _ let sv : J × Bool → {x // x ∈ S} := fun z => ⟨uv z,hvS z⟩ let tw : J × Bool → {x // x ∈ T} := fun z => ⟨uw z,hwT z⟩ have hsv : Function.Surjective sv := by intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property exact ⟨z,Subtype.ext hz⟩ have htw : Function.Surjective tw := by intro x; obtain ⟨z,_,hz⟩ := mem_image.mp x.property exact ⟨z,Subtype.ext hz⟩ have hker : ∀ z z', sv z = sv z' ↔ tw z = tw z' := by intro z z' simpa only [Subtype.ext_iff] using hkernel z z' let pick : {x // x ∈ S} → J × Bool := fun x => Classical.choose (hsv x) have hpick : ∀ x, sv (pick x) = x := fun x => Classical.choose_spec (hsv x) let eS : {x // x ∈ S} ≃ {x // x ∈ T} := Equiv.ofBijective (fun x => tw (pick x)) (by constructor · intro x y h have hh := (hker (pick x) (pick y)).mpr h simpa only [hpick] using hh · intro y obtain ⟨z,rfl⟩ := htw y exact ⟨sv z,(hker _ _).mp (hpick (sv z))⟩) have heval : ∀ z, eS (sv z) = tw z := fun z => (hker _ _).mp (hpick (sv z)) have heS : ∀ x : {x // x ∈ S}, (eS ⟨f x.val,(hS x.val).mpr x.property⟩).val = g (eS x).val := by intro x obtain ⟨z,rfl⟩ := hsv x have hh : (⟨f (sv z).val,(hS (sv z).val).mpr (sv z).property⟩ : {x // x ∈ S}) = sv (flip z) := Subtype.ext (hvflip z).symm rw [hh,heval,heval] exact hwflip z have hmem : a ∈ S ↔ b ∈ T := by constructor · intro ha let x : {x // x ∈ S} := ⟨a,ha⟩ have heq : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x := Subtype.ext ((hfa a).mpr rfl) have hh := heS x rw [heq] at hh have hb : (eS x).val = b := (hgb _).mp hh.symm exact hb ▸ (eS x).property · intro hb obtain ⟨x,hx⟩ := eS.surjective ⟨b,hb⟩ have hh := heS x have hxval : (eS x).val = b := congrArg Subtype.val hx rw [hxval,(hgb b).mpr rfl] at hh have hfix : f x.val = x.val := by have hsub : (⟨f x.val,(hS x.val).mpr x.property⟩ : {x // x ∈ S}) = x := by apply eS.injective apply Subtype.ext exact hh.trans hxval.symm exact congrArg Subtype.val hsub have ha : x.val = a := (hfa _).mp hfix exact ha ▸ x.property obtain ⟨e,he,hext⟩ := wild_involution_closed_partial_isomorphism_extends f g hf hg a b hfa hgb S T hS hT hmem eS heS refine ⟨e,he,?_⟩ intro j have hh := hext (sv (j,false)) rw [heval] at hh exact hh