wild_involution_pattern_conditioned_bad_count_invariant
For finite matching patterns with the same internal partner equalities, the permutation counts of a whole-bad matching and any prescribed block assignments to marked pattern vertices agree. Both ambient involutions have a unique fixed point.
Statement
theorem wild_involution_pattern_conditioned_bad_count_invariant {V J K : Type*} [Fintype V] [Fintype J] [Fintype K] [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) (p : V → K) (M : Finset J) (t : J → K) : (univ.filter fun σ : Equiv.Perm V => (∀ j ∈ M, wild_profile_permute p σ (v j) = t j) ∧ wild_profile_bad (wild_profile_permute p σ) (fun x y => f x = y)).card = (univ.filter fun σ : Equiv.Perm V => (∀ j ∈ M, wild_profile_permute p σ (w j) = t j) ∧ wild_profile_bad (wild_profile_permute p σ) (fun x y => g x = y)).card
- 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 2
- wild_involution_partial_pattern_isomorphism_extendsAn isomorphism of arbitrary injective finite patterns, preserving every partner equality including fixed points, extends to an isomorphism…
- wild_profile_conditioned_joint_count_transportFor a finite vertex type, finite block type, arbitrary block profile p, chosen block b and vertex subset S, and any finite set of color…
The proof, explained
The proof establishes an equality of counts by constructing a bijection between the two sets of permutations via post-composition with a symmetry $e$ of the ambient space. An extension lemma extends the matching pattern isomorphism between $v$ and $w$ to a full permutation $e$ that conjugates the involution $f$ to $g$ and maps each marked vertex $v(j)$ to $w(j)$. Under the assignment $\sigma \mapsto \sigma \circ e$, the pattern conditions on $v$ translate directly to those on $w$, while relabeling invariance ensures that bad profiles for $f$ correspond bijectively to bad profiles for $g$.
There exists an ambient permutation $e$ conjugating $f$ to $g$ and sending each $v(j)$ to $w(j)$.
By `wild_involution_partial_pattern_isomorphism_extends`, the pattern-preserving injective map from the image of $v$ to the image of $w$ extends to a full permutation $e$ of $V$ satisfying $e(f(x)) = g(e(x))$ for all $x \in V$ and $e(v(j)) = w(j)$ for all $j \in J$.
uses
wild_involution_partial_pattern_isomorphism_extendsclassical obtain ⟨e,he,hevw⟩ := wild_involution_partial_pattern_isomorphism_extends f g hf hg a b hfa hgb v w hv hw hpatternThe equivalence $e$ respects the graph relations: $g(e(x)) = e(y) \iff f(x) = y$.
Rewriting $g(e(x))$ as $e(f(x))$ using the conjugation identity yields $e(f(x)) = e(y)$, which is equivalent to $f(x) = y$ because $e$ is injective.
have hrel : ∀ x y, g (e x) = e y ↔ f x = y := by intro x y rw [← he,e.injective.eq_iff]
For any permutation $\sigma$, the conditioned values under $\sigma \circ e$ on $w$ match those under $\sigma$ on $v$.
Unfolding the definition of profile permutation and substituting $w(j) = e(v(j))$, the expression evaluates to $p(\sigma^{-1}(e^{-1}(e(v(j)))))$, which simplifies to $p(\sigma^{-1}(v(j)))$ because $e^{-1}(e(v(j))) = v(j)$.
uses
Equiv.symm_apply_applyhave hcondition : ∀ σ : Equiv.Perm V, (∀ j ∈ M, wild_profile_permute p (σ.trans e) (w j) = t j) ↔ ∀ j ∈ M, wild_profile_permute p σ (v j) = t j := by intro σ simp only [← hevw,wild_profile_permute] change (∀ j ∈ M, p (σ.symm (e.symm (e (v j)))) = t j) ↔ _ simp only [Equiv.symm_apply_apply]
It suffices to construct a bijection between the two sets of permutations using $\sigma \mapsto \sigma \circ e$.
By `card_bij`, showing that post-composition with $e$ maps the first set into the second injectively and surjectively proves that both sets have identical cardinality.
uses
card_bijapply card_bij (fun σ _ => σ.trans e)
Post-composition with $e$ maps elements of the first set into the second set.
Given $\sigma$ satisfying the pattern and badness conditions for $(v, f)$, the pattern constraint for $(w, g)$ follows from the equivalence proved earlier. Badness under $g$ follows from badness under $f$ by decomposing $\sigma \circ e$ into sequential permutations and invoking `wild_profile_bad_relabel` with the relation isomorphism $hrel$.
uses
mem_filter,mem_univ,true_and,wild_profile_permute_trans,wild_profile_bad_relabel· intro σ hσ simp only [mem_filter,mem_univ,true_and] at hσ ⊢ refine ⟨(hcondition σ).mpr hσ.1,?_⟩ rw [wild_profile_permute_trans] exact (wild_profile_bad_relabel (wild_profile_permute p σ) (fun x y => f x = y) (fun x y => g x = y) e hrel).mpr hσ.2
Post-composition with $e$ is injective.
If $\sigma \circ e = \tau \circ e$, evaluating both permutations on any element $x \in V$ gives $e(\sigma(x)) = e(\tau(x))$. Because $e$ is injective, $\sigma(x) = \tau(x)$ for all $x$, so $\sigma = \tau$.
uses
congrArg· intro σ _ τ _ h ext x exact e.injective (congrArg (fun a : Equiv.Perm V => a x) h)
Post-composition with $e$ is surjective.
Given $\tau$ in the target set, we choose the candidate preimage $\tau \circ e^{-1}$. Since $(\tau \circ e^{-1}) \circ e = \tau$, it maps to $\tau$. The pattern conditions and badness conditions for $(v, f)$ hold for this preimage by applying the earlier equivalences in the reverse direction.
uses
mem_filter,mem_univ,true_and,wild_profile_bad_relabel,wild_profile_permute_trans· intro τ hτ have hcancel : (τ.trans e.symm).trans e = τ := by ext x; simp refine ⟨τ.trans e.symm,?_,hcancel⟩ simp only [mem_filter,mem_univ,true_and] at hτ ⊢ constructor · apply (hcondition (τ.trans e.symm)).mp rw [hcancel] exact hτ.1 · apply (wild_profile_bad_relabel (wild_profile_permute p (τ.trans e.symm)) (fun x y => f x = y) (fun x y => g x = y) e hrel).mp rw [← wild_profile_permute_trans,hcancel] exact hτ.2
wild_involution_partial_pattern_isomorphism_extends- An isomorphism between partial matching patterns on a set with unique-fixed-point involutions extends to an ambient permutation conjugating the two involutions.
Equiv.symm_apply_apply- Applying the inverse of an equivalence to its value at an element recovers that element: $e^{-1}(e(x)) = x$.
card_bij- Two finite sets have the same size if there is a well-defined map between them that is both injective and surjective.
mem_filter- An element is in `filter p s` if and only if it is in $s$ and satisfies property $p$.
mem_univ- Every element of a finite type belongs to the universal finset `univ`.
true_and- The propositional conjunction $\text{True} \wedge P$ is equivalent to $P$.
wild_profile_permute_trans- Permuting a profile by the composition $\sigma \circ e$ is equivalent to permuting it by $\sigma$ and then permuting the result by $e$.
wild_profile_bad_relabel- A profile permuted by an equivalence $e$ is bad under a relation $T$ if and only if the original profile is bad under $R$, provided $e$ respects the relations ($T(e(u), e(v)) \iff R(u, v)$).
congrArg- If two arguments are equal, the values of any function applied to them are equal.
- In Lean, `σ.trans e` denotes the composition of equivalences where `σ` is applied first and then `e` (that is, `(e ∘ σ)(x) = e(σ(x))`). Consequently, `wild_profile_permute p σ` evaluates to `p ∘ σ⁻¹`.
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_pattern_conditioned_bad_count_invariant {V J K : Type*} [Fintype V] [Fintype J] [Fintype K] [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) (p : V → K) (M : Finset J) (t : J → K) : (univ.filter fun σ : Equiv.Perm V => (∀ j ∈ M, wild_profile_permute p σ (v j) = t j) ∧ wild_profile_bad (wild_profile_permute p σ) (fun x y => f x = y)).card = (univ.filter fun σ : Equiv.Perm V => (∀ j ∈ M, wild_profile_permute p σ (w j) = t j) ∧ wild_profile_bad (wild_profile_permute p σ) (fun x y => g x = y)).card := by classical obtain ⟨e,he,hevw⟩ := wild_involution_partial_pattern_isomorphism_extends f g hf hg a b hfa hgb v w hv hw hpattern have hrel : ∀ x y, g (e x) = e y ↔ f x = y := by intro x y rw [← he,e.injective.eq_iff] have hcondition : ∀ σ : Equiv.Perm V, (∀ j ∈ M, wild_profile_permute p (σ.trans e) (w j) = t j) ↔ ∀ j ∈ M, wild_profile_permute p σ (v j) = t j := by intro σ simp only [← hevw,wild_profile_permute] change (∀ j ∈ M, p (σ.symm (e.symm (e (v j)))) = t j) ↔ _ simp only [Equiv.symm_apply_apply] apply card_bij (fun σ _ => σ.trans e) · intro σ hσ simp only [mem_filter,mem_univ,true_and] at hσ ⊢ refine ⟨(hcondition σ).mpr hσ.1,?_⟩ rw [wild_profile_permute_trans] exact (wild_profile_bad_relabel (wild_profile_permute p σ) (fun x y => f x = y) (fun x y => g x = y) e hrel).mpr hσ.2 · intro σ _ τ _ h ext x exact e.injective (congrArg (fun a : Equiv.Perm V => a x) h) · intro τ hτ have hcancel : (τ.trans e.symm).trans e = τ := by ext x; simp refine ⟨τ.trans e.symm,?_,hcancel⟩ simp only [mem_filter,mem_univ,true_and] at hτ ⊢ constructor · apply (hcondition (τ.trans e.symm)).mp rw [hcancel] exact hτ.1 · apply (wild_profile_bad_relabel (wild_profile_permute p (τ.trans e.symm)) (fun x y => f x = y) (fun x y => g x = y) e hrel).mp rw [← wild_profile_permute_trans,hcancel] exact hτ.2