AFTD Auto-Formalizing Theoretical Domains

wild_involution_pattern_conditioned_bad_count_invariant

theoremverified

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

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$.

  1. 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$.

    lines 20–22

    uses wild_involution_partial_pattern_isomorphism_extends

      classical
      obtain ⟨e,he,hevw⟩ := wild_involution_partial_pattern_isomorphism_extends
        f g hf hg a b hfa hgb v w hv hw hpattern
  2. The 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.

    lines 23–25

      have hrel : ∀ x y, g (e x) = e y ↔ f x = y := by
        intro x y
        rw [← he,e.injective.eq_iff]
  3. 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)$.

    lines 26–32

    uses Equiv.symm_apply_apply

      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]
  4. 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.

    line 33

    uses card_bij

      apply card_bij (fun σ _ => σ.trans e)
  5. 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$.

    lines 34–39

    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
  6. 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$.

    lines 40–42

    uses congrArg

      · intro σ _ τ _ h
        ext x
        exact e.injective (congrArg (fun a : Equiv.Perm V => a x) h)
  7. 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.

    lines 43–54

    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.

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_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
See it in the graphDiscuss this resultChallenge it