wild_involution_three_set_isomorphism
For two finite involutions with unique fixed points, two three-element subsets can be carried to one another by a global intertwining permutation if they agree on containing the fixed point and on containing a non-loop matching edge.
Statement
theorem wild_involution_three_set_isomorphism {V : Type*} [Fintype V] [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) (S T : Finset V) (hS : S.card = 3) (hT : T.card = 3) (hfixed : a ∈ S ↔ b ∈ T) (hedge : (∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y) ↔ ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y) : ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ S.image e = T
- Source
- IN-382 / OP-306 campaign9, 2026-10-30. Standard finite matching symmetry supporting the mixed-moment route for https://arxiv.org/html/2610.22142v1. Exact experiment9566 exposed the missing parity assumption. The original false helper remains retired and its proof record is preserved. No wild-number bound or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- wild_three_partial_involution_classificationOn three vertices, two symmetric partial partner maps, each with at most one fixed point, are isomorphic whenever the existence of a fixed…
- wild_involution_partial_pattern_isomorphism_extendsAn isomorphism of arbitrary injective finite patterns, preserving every partner equality including fixed points, extends to an isomorphism…
- Used by 1
- wild_joint_alpha_type_well_defined_oddFor odd q>=3, any two three-element subsets of the same canonical type have equal conditional whole-bad probabilities alpha. This…
The proof, explained
To find a global intertwining permutation carrying S to T, the proof first encodes the induced actions of f on S and g on T as partial maps on Fin 3. By the hypotheses that S and T agree on containing the unique fixed points and on containing a 2-cycle, these two partial involutions share the same invariant data. A classification lemma (wild_three_partial_involution_classification) produces an isomorphism between the two partial patterns, which is then extended to a global conjugating permutation of V mapping S to T using wild_involution_partial_pattern_isomorphism_extends.
The subsets S and T are parameterized as injective sequences v, w : Fin 3 → V whose ranges are exactly S and T.
Since |S| = 3 and |T| = 3, Fintype.equivFinOfCardEq provides bijections between Fin 3 and S, T. Composing their inverses with the inclusion into V yields injections v and w whose images are precisely S and T.
uses
Fintype.equivFinOfCardEq,Subtype.ext,congrArgclassical let eS : S ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hS) let eT : T ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hT) let v : Fin 3 → V := fun j => (eS.symm j).val let w : Fin 3 → V := fun j => (eT.symm j).val have hv : Function.Injective v := by intro j k h; exact eS.symm.injective (Subtype.ext h) have hw : Function.Injective w := by intro j k h; exact eT.symm.injective (Subtype.ext h) have hvS : ∀ j, v j ∈ S := fun j => (eS.symm j).property have hwT : ∀ j, w j ∈ T := fun j => (eT.symm j).property have hSv : ∀ x ∈ S, ∃ j, v j = x := by intro x hx; exact ⟨eS ⟨x,hx⟩,congrArg Subtype.val (eS.symm_apply_apply _)⟩ have hTw : ∀ x ∈ T, ∃ j, w j = x := by intro x hx; exact ⟨eT ⟨x,hx⟩,congrArg Subtype.val (eT.symm_apply_apply _)⟩
The partial action enc h u of a map h on the sequence u is well-defined and satisfies enc h u j = some k ↔ h (u j) = u k.
The encoding enc h u j checks whether h (u j) equals u k for some index k in Fin 3, returning some k if so and none otherwise. Since u is injective, the index k is unique when it exists.
uses
Option.some.injEqlet enc (h : V → V) (u : Fin 3 → V) (j : Fin 3) : Option (Fin 3) := if hh : ∃ k, h (u j) = u k then some hh.choose else none have henc (h : V → V) (u : Fin 3 → V) (hu : Function.Injective u) (j k : Fin 3) : enc h u j = some k ↔ h (u j) = u k := by dsimp only [enc] split_ifs with hh · simp only [Option.some.injEq] constructor · intro he; exact he ▸ hh.choose_spec · intro he; apply hu; exact hh.choose_spec.symm.trans he · constructor · intro he; cases he · intro he; exact (hh ⟨k,he⟩).elim
The partial action enc h u inherits involution symmetry and has at most one fixed point.
Because h is an involution, h (u j) = u k implies h (u k) = u j, giving symmetry of enc. Moreover, since h has a unique fixed point c and u is injective, enc h u can have at most one fixed point index.
have hsym (h : Equiv.Perm V) (hh : Function.Involutive h) (u : Fin 3 → V) (hu : Function.Injective u) : ∀ j k, enc h u j = some k ↔ enc h u k = some j := by intro j k rw [henc h u hu,henc h u hu] constructor · intro he; rw [← he,hh] · intro he; rw [← he,hh] have huniq (h : Equiv.Perm V) (c : V) (hc : ∀ x, h x = x ↔ x = c) (u : Fin 3 → V) (hu : Function.Injective u) : ∀ j k, enc h u j = some j → enc h u k = some k → j = k := by intro j k hj hk apply hu exact ((hc _).mp ((henc h u hu j j).mp hj)).trans ((hc _).mp ((henc h u hu k k).mp hk)).symm
The partial action enc f v has a fixed point if and only if a ∈ S, and similarly enc g w has a fixed point if and only if b ∈ T.
A fixed point of the encoded action corresponds to f (v j) = v j, which by the characterization of fixed points of f is equivalent to v j = a, meaning a ∈ S. The same reasoning applies to g, w, and b ∈ T.
have hfixv : (∃ j, enc f v j = some j) ↔ a ∈ S := by constructor · rintro ⟨j,hj⟩ have he := (hfa _).mp ((henc f v hv j j).mp hj) exact he ▸ hvS j · intro ha obtain ⟨j,hj⟩ := hSv a ha exact ⟨j,(henc f v hv j j).mpr ((hfa _).mpr hj)⟩ have hfixw : (∃ j, enc g w j = some j) ↔ b ∈ T := by constructor · rintro ⟨j,hj⟩ have he := (hgb _).mp ((henc g w hw j j).mp hj) exact he ▸ hwT j · intro hb obtain ⟨j,hj⟩ := hTw b hb exact ⟨j,(henc g w hw j j).mpr ((hgb _).mpr hj)⟩
The partial action enc f v contains an off-diagonal 2-cycle if and only if S contains a 2-cycle of f, and similarly for g and T.
An off-diagonal match enc f v j = some k with j ≠ k corresponds directly to a pair of distinct elements x = v j and y = v k in S such that f x = y. The equivalent equivalence holds for g and T.
uses
congrArghave hedgev : (∃ j k, j ≠ k ∧ enc f v j = some k) ↔ ∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y := by constructor · rintro ⟨j,k,hjk,hjk'⟩ exact ⟨v j,hvS j,v k,hvS k,fun h => hjk (hv h),(henc f v hv j k).mp hjk'⟩ · rintro ⟨x,hx,y,hy,hxy,hfxy⟩ obtain ⟨j,rfl⟩ := hSv x hx obtain ⟨k,rfl⟩ := hSv y hy exact ⟨j,k,fun h => hxy (congrArg v h),(henc f v hv j k).mpr hfxy⟩ have hedgew : (∃ j k, j ≠ k ∧ enc g w j = some k) ↔ ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y := by constructor · rintro ⟨j,k,hjk,hjk'⟩ exact ⟨w j,hwT j,w k,hwT k,fun h => hjk (hw h),(henc g w hw j k).mp hjk'⟩ · rintro ⟨x,hx,y,hy,hxy,hgxy⟩ obtain ⟨j,rfl⟩ := hTw x hx obtain ⟨k,rfl⟩ := hTw y hy exact ⟨j,k,fun h => hxy (congrArg w h),(henc g w hw j k).mpr hgxy⟩
There exists a permutation r of Fin 3 conjugating the partial pattern of f on v to the partial pattern of g on w.
By the assumptions hfixed and hedge, the encoded actions enc f v and enc g w have the same number of fixed points (both either 0 or 1) and agree on whether they contain an edge. Applying the classification lemma wild_three_partial_involution_classification yields a bijection r : Fin 3 → Fin 3 matching the two partial patterns: f (v j) = v k ↔ g (w (r j)) = w (r k).
uses
wild_three_partial_involution_classificationobtain ⟨r,hr,hrp⟩ := wild_three_partial_involution_classification (enc f v) (enc g w) (hsym f hf v hv) (hsym g hg w hw) (huniq f a hfa v hv) (huniq g b hgb w hw) (hfixv.trans (hfixed.trans hfixw.symm)) (hedgev.trans (hedge.trans hedgew.symm)) have hp : ∀ j k, f (v j) = v k ↔ g (w (r j)) = w (r k) := by intro j k exact (henc f v hv j k).symm.trans ((hrp j k).trans (henc g w hw (r j) (r k)))
The local isomorphism r extends to a global permutation e of V conjugating f to g and mapping v j to w (r j).
Applying wild_involution_partial_pattern_isomorphism_extends to v and w ∘ r lifts the 3-element pattern isomorphism to a global permutation e such that e (f x) = g (e x) for all x ∈ V and e (v j) = w (r j) for all j ∈ Fin 3.
uses
wild_involution_partial_pattern_isomorphism_extendsobtain ⟨e,he,hev⟩ := wild_involution_partial_pattern_isomorphism_extends f g hf hg a b hfa hgb v (w ∘ r) hv (hw.comp hr.1) hp refine ⟨e,he,?_⟩
The global intertwining permutation e maps S onto T, completing the proof.
Every element of S is v j for some j, so its image under e is w (r j) ∈ T. Conversely, every element of T is w k, and by surjectivity of r, k = r j, so w k = e (v j) with v j ∈ S. Thus e(S) = T.
ext x constructor · intro hx obtain ⟨y,hy,rfl⟩ := mem_image.mp hx obtain ⟨j,rfl⟩ := hSv y hy rw [hev] exact hwT (r j) · intro hx obtain ⟨k,rfl⟩ := hTw x hx obtain ⟨j,rfl⟩ := hr.2 k exact mem_image.mpr ⟨v j,hvS j,hev j⟩
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
congrArg- Applying a function to equal inputs yields equal outputs: if a = b then f a = f b.
Fintype.equivFinOfCardEq- A finite type with cardinality n is in bijection with Fin n.
Option.some.injEq- The Option constructor some is injective: some x = some y if and only if x = y.
wild_three_partial_involution_classification- Two partial involutive maps on Fin 3 with at most one fixed point are isomorphic via a permutation of Fin 3 if and only if they agree on the existence of a fixed point and on the existence of a 2-cycle.
wild_involution_partial_pattern_isomorphism_extends- Any pattern-preserving injection between indexed subsets under two finite involutions with unique fixed points extends to a global permutation conjugating the two involutions.
- The classification of symmetric partial maps on three elements and the extension theorem lifting a local pattern isomorphism to a global conjugacy permutation are outsourced to the external helper theorems wild_three_partial_involution_classification and wild_involution_partial_pattern_isomorphism_extends.
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 6000000set_option maxRecDepth 100000set_option synthInstance.maxSize 10000theorem wild_involution_three_set_isomorphism {V : Type*} [Fintype V] [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) (S T : Finset V) (hS : S.card = 3) (hT : T.card = 3) (hfixed : a ∈ S ↔ b ∈ T) (hedge : (∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y) ↔ ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y) : ∃ e : Equiv.Perm V, (∀ x, e (f x) = g (e x)) ∧ S.image e = T := by classical let eS : S ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hS) let eT : T ≃ Fin 3 := Fintype.equivFinOfCardEq (by simpa using hT) let v : Fin 3 → V := fun j => (eS.symm j).val let w : Fin 3 → V := fun j => (eT.symm j).val have hv : Function.Injective v := by intro j k h; exact eS.symm.injective (Subtype.ext h) have hw : Function.Injective w := by intro j k h; exact eT.symm.injective (Subtype.ext h) have hvS : ∀ j, v j ∈ S := fun j => (eS.symm j).property have hwT : ∀ j, w j ∈ T := fun j => (eT.symm j).property have hSv : ∀ x ∈ S, ∃ j, v j = x := by intro x hx; exact ⟨eS ⟨x,hx⟩,congrArg Subtype.val (eS.symm_apply_apply _)⟩ have hTw : ∀ x ∈ T, ∃ j, w j = x := by intro x hx; exact ⟨eT ⟨x,hx⟩,congrArg Subtype.val (eT.symm_apply_apply _)⟩ let enc (h : V → V) (u : Fin 3 → V) (j : Fin 3) : Option (Fin 3) := if hh : ∃ k, h (u j) = u k then some hh.choose else none have henc (h : V → V) (u : Fin 3 → V) (hu : Function.Injective u) (j k : Fin 3) : enc h u j = some k ↔ h (u j) = u k := by dsimp only [enc] split_ifs with hh · simp only [Option.some.injEq] constructor · intro he; exact he ▸ hh.choose_spec · intro he; apply hu; exact hh.choose_spec.symm.trans he · constructor · intro he; cases he · intro he; exact (hh ⟨k,he⟩).elim have hsym (h : Equiv.Perm V) (hh : Function.Involutive h) (u : Fin 3 → V) (hu : Function.Injective u) : ∀ j k, enc h u j = some k ↔ enc h u k = some j := by intro j k rw [henc h u hu,henc h u hu] constructor · intro he; rw [← he,hh] · intro he; rw [← he,hh] have huniq (h : Equiv.Perm V) (c : V) (hc : ∀ x, h x = x ↔ x = c) (u : Fin 3 → V) (hu : Function.Injective u) : ∀ j k, enc h u j = some j → enc h u k = some k → j = k := by intro j k hj hk apply hu exact ((hc _).mp ((henc h u hu j j).mp hj)).trans ((hc _).mp ((henc h u hu k k).mp hk)).symm have hfixv : (∃ j, enc f v j = some j) ↔ a ∈ S := by constructor · rintro ⟨j,hj⟩ have he := (hfa _).mp ((henc f v hv j j).mp hj) exact he ▸ hvS j · intro ha obtain ⟨j,hj⟩ := hSv a ha exact ⟨j,(henc f v hv j j).mpr ((hfa _).mpr hj)⟩ have hfixw : (∃ j, enc g w j = some j) ↔ b ∈ T := by constructor · rintro ⟨j,hj⟩ have he := (hgb _).mp ((henc g w hw j j).mp hj) exact he ▸ hwT j · intro hb obtain ⟨j,hj⟩ := hTw b hb exact ⟨j,(henc g w hw j j).mpr ((hgb _).mpr hj)⟩ have hedgev : (∃ j k, j ≠ k ∧ enc f v j = some k) ↔ ∃ x ∈ S, ∃ y ∈ S, x ≠ y ∧ f x = y := by constructor · rintro ⟨j,k,hjk,hjk'⟩ exact ⟨v j,hvS j,v k,hvS k,fun h => hjk (hv h),(henc f v hv j k).mp hjk'⟩ · rintro ⟨x,hx,y,hy,hxy,hfxy⟩ obtain ⟨j,rfl⟩ := hSv x hx obtain ⟨k,rfl⟩ := hSv y hy exact ⟨j,k,fun h => hxy (congrArg v h),(henc f v hv j k).mpr hfxy⟩ have hedgew : (∃ j k, j ≠ k ∧ enc g w j = some k) ↔ ∃ x ∈ T, ∃ y ∈ T, x ≠ y ∧ g x = y := by constructor · rintro ⟨j,k,hjk,hjk'⟩ exact ⟨w j,hwT j,w k,hwT k,fun h => hjk (hw h),(henc g w hw j k).mp hjk'⟩ · rintro ⟨x,hx,y,hy,hxy,hgxy⟩ obtain ⟨j,rfl⟩ := hTw x hx obtain ⟨k,rfl⟩ := hTw y hy exact ⟨j,k,fun h => hxy (congrArg w h),(henc g w hw j k).mpr hgxy⟩ obtain ⟨r,hr,hrp⟩ := wild_three_partial_involution_classification (enc f v) (enc g w) (hsym f hf v hv) (hsym g hg w hw) (huniq f a hfa v hv) (huniq g b hgb w hw) (hfixv.trans (hfixed.trans hfixw.symm)) (hedgev.trans (hedge.trans hedgew.symm)) have hp : ∀ j k, f (v j) = v k ↔ g (w (r j)) = w (r k) := by intro j k exact (henc f v hv j k).symm.trans ((hrp j k).trans (henc g w hw (r j) (r k))) obtain ⟨e,he,hev⟩ := wild_involution_partial_pattern_isomorphism_extends f g hf hg a b hfa hgb v (w ∘ r) hv (hw.comp hr.1) hp refine ⟨e,he,?_⟩ ext x constructor · intro hx obtain ⟨y,hy,rfl⟩ := mem_image.mp hx obtain ⟨j,rfl⟩ := hSv y hy rw [hev] exact hwT (r j) · intro hx obtain ⟨k,rfl⟩ := hTw x hx obtain ⟨j,rfl⟩ := hr.2 k exact mem_image.mpr ⟨v j,hvS j,hev j⟩