AFTD Auto-Formalizing Theoretical Domains

wild_joint_alpha_eq_of_matching_isomorphism

theoremverified

A permutation preserving the canonical matching and carrying one conditioning set to another preserves its conditional whole-bad probability alpha. This follows by bijecting both the numerator and denominator permutation sets.

Statement

theorem wild_joint_alpha_eq_of_matching_isomorphism
    (q : ℕ) (S T : Finset (Fin (3*q))) (e : Equiv.Perm (Fin (3*q)))
    (heT : S.image e = T)
    (heR : ∀ x y, wild_joint_canonical_matching q (e x) (e y) ↔
      wild_joint_canonical_matching q x y) :
    wild_joint_alpha q S = wild_joint_alpha q 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 5
  • wild_joint_alphaalpha(T): the conditional probability, under the uniform distribution on all vertex permutations σ, that the fixed canonical matching is…
  • wild_joint_bad_relationA symmetric relation R is whole-bad for the block map p if some nonempty proper union of blocks (a nonempty proper set of block indices B,…
  • wild_joint_first_blockThe first block: the set of vertices placed in positions 0,1,2 by σ (= {σ 0, σ 1, σ 2}).
  • wild_joint_canonical_matchingThe fixed matching on Fin (3q) with isolated vertex 0 and pairs {2k-1, 2k} for k >= 1: (1,2),(3,4),(5,6),...
  • wild_joint_blockBlock (index of the consecutive triple) containing vertex v under the permutation σ, where σ p is the vertex at position p; blocks are…
Used by 1

The proof, explained

The theorem shows that the conditional whole-bad probability $\alpha(S)$ equals $\alpha(T)$ whenever a permutation $e$ maps the conditioning set $S$ to $T$ and preserves the canonical matching. The argument constructs a bijection between permutations by post-composing with $e$ ($\sigma \mapsto \sigma \circ e$). This map preserves both the first-block condition and the bad-relation property, simultaneously equating the numerators and denominators in the definition of $\alpha$.

  1. The block assignment of elements is equivariant under post-composition with $e$: for every permutation $\sigma$ and element $x$, the block of $e(x)$ under $\sigma \circ e$ is the block of $x$ under $\sigma$.

    By definition, the block of an element $v$ under a permutation $\tau$ is $\lfloor \tau^{-1}(v) / 3 \rfloor$. Since $(\sigma \circ e)^{-1}(e(x)) = e^{-1}(\sigma^{-1}(e(x))) = \sigma^{-1}(x)$, the indices divided by 3 are identical. Reducing equality in `Fin q` to equality of values via `Fin.ext`, the definition of `wild_joint_block` simplifies directly.

    lines 13–18

    uses Fin.ext

      classical
      have hblock : ∀ (σ : Equiv.Perm (Fin (3*q))) x,
          wild_joint_block q (σ.trans e) (e x) = wild_joint_block q σ x := by
        intro σ x
        apply Fin.ext
        simp [wild_joint_block]
  2. The first block of $\sigma \circ e$ is the image under $e$ of the first block of $\sigma$.

    The first block of a permutation consists of all elements whose inverse image has index strictly less than 3. An element $x$ is in the first block of $\sigma \circ e$ if and only if $(\sigma \circ e)^{-1}(x) < 3$, which means $\sigma^{-1}(e^{-1}(x)) < 3$, or equivalently $e^{-1}(x)$ is in the first block of $\sigma$. Thus $x = e(e^{-1}(x))$ is in the image under $e$ of the first block of $\sigma$. Extensionality and bidirectional inclusion complete the verification.

    lines 19–29

    uses mem_filter, mem_univ, true_and, mem_image

      have hfirst : ∀ σ : Equiv.Perm (Fin (3*q)),
          wild_joint_first_block q (σ.trans e) = (wild_joint_first_block q σ).image e := by
        intro σ
        ext x
        simp only [wild_joint_first_block,mem_filter,mem_univ,true_and,mem_image]
        constructor
        · intro hx
          refine ⟨e.symm x,?_,e.apply_symm_apply x⟩
          exact hx
        · rintro ⟨y,hy,rfl⟩
          simpa using hy
  3. A permutation $\sigma \circ e$ has first block $T$ if and only if $\sigma$ has first block $S$.

    Using the previous step, the first block of $\sigma \circ e$ is $e(\text{first\_block}(\sigma))$. Since $T = e(S)$ by hypothesis `heT`, the condition becomes $e(\text{first\_block}(\sigma)) = e(S)$. Because $e$ is a permutation, it is injective, and taking images under an injective function is injective on finsets (`Finset.image_injective`), so this is equivalent to $\text{first\_block}(\sigma) = S$.

    lines 30–34

    uses Finset.image_injective

      have hfirstiff : ∀ σ : Equiv.Perm (Fin (3*q)),
          wild_joint_first_block q (σ.trans e) = T ↔ wild_joint_first_block q σ = S := by
        intro σ
        rw [hfirst,← heT]
        exact Finset.image_injective e.injective |>.eq_iff
  4. A permutation $\sigma \circ e$ satisfies the bad relation with respect to the canonical matching if and only if $\sigma$ does.

    A permutation satisfies the bad relation if there exists a nonempty proper subset $B$ of block indices such that every canonically matched pair of elements have their blocks either both in $B$ or both outside $B$. In both directions, the same subset $B$ witnesses the property: by hypothesis `heR`, $x$ and $y$ are matched if and only if $e(x)$ and $e(y)$ are matched. Together with the block equivariance from Step 1, this translates the matching and block conditions between $\sigma$ and $\sigma \circ e$.

    lines 35–50

      have hbad : ∀ σ : Equiv.Perm (Fin (3*q)),
          wild_joint_bad_relation q (wild_joint_block q (σ.trans e)) (wild_joint_canonical_matching q) ↔
          wild_joint_bad_relation q (wild_joint_block q σ) (wild_joint_canonical_matching q) := by
        intro σ
        constructor
        · rintro ⟨B,hB,hBU,hBR⟩
          refine ⟨B,hB,hBU,?_⟩
          intro x y hxy
          have hh := hBR (e x) (e y) ((heR x y).mpr hxy)
          simpa only [hblock] using hh
        · rintro ⟨B,hB,hBU,hBR⟩
          refine ⟨B,hB,hBU,?_⟩
          intro x y hxy
          obtain ⟨x,rfl⟩ := e.surjective x
          obtain ⟨y,rfl⟩ := e.surjective y
          simpa only [hblock] using hBR x y ((heR x y).mp hxy)
  5. For any boolean flag, the number of permutations with first block $S$ equals the number of permutations with first block $T$ (subject to the bad-relation condition when the flag is true).

    The mapping $\sigma \mapsto \sigma \circ e$ is a bijection between the two sets: it maps valid permutations to valid permutations by the first-block equivalence and bad-relation equivalence proved in Steps 3 and 4; it is injective because post-composition by an invertible map is injective; and it is surjective because any target permutation $\tau$ is the image of $\tau \circ e^{-1}$. Hence `card_bij` equates the two set cardinalities.

    lines 51–80

    uses card_bij, mem_filter, mem_univ, true_and, Equiv.ext, congrArg

      have hcount (extra : Bool) :
          (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>
            wild_joint_first_block q σ = S ∧
              (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)
                (wild_joint_canonical_matching q))).card =
          (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>
            wild_joint_first_block q σ = T ∧
              (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)
                (wild_joint_canonical_matching q))).card := by
        apply card_bij (fun σ _ => σ.trans e)
        · intro σ hσ
          simp only [mem_filter,mem_univ,true_and] at hσ ⊢
          exact ⟨(hfirstiff σ).mpr hσ.1,fun h => (hbad σ).mpr (hσ.2 h)⟩
        · intro σ _ τ _ h
          apply Equiv.ext
          intro x
          have hh := congrArg (fun a : Equiv.Perm (Fin (3*q)) => a x) h
          exact e.injective hh
        · intro τ hτ
          have hc : (τ.trans e.symm).trans e = τ := by ext x; simp
          refine ⟨τ.trans e.symm,?_,hc⟩
          simp only [mem_filter,mem_univ,true_and] at hτ ⊢
          constructor
          · apply (hfirstiff _).mp
            rw [hc]
            exact hτ.1
          · intro h
            apply (hbad _).mp
            rw [hc]
            exact hτ.2 h
  6. The conditional whole-bad probability $\alpha(S)$ equals $\alpha(T)$.

    Specializing the counting lemma with `extra = true` shows the numerators in the definition of $\alpha$ are equal (`hnum`), while specializing with `extra = false` trivializes the bad-relation hypothesis and shows the denominators are equal (`hden`). Unfolding the definition of `wild_joint_alpha` as the ratio of these counts and rewriting with `hnum` and `hden` completes the proof.

    lines 81–85

    uses Bool.false_eq_true, false_implies, and_true, forall_const

      have hnum := hcount true
      have hden := hcount false
      simp only [Bool.false_eq_true, false_implies, and_true, forall_const] at hnum hden
      unfold wild_joint_alpha
      rw [hnum,hden]
Fin.ext
Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
mem_filter
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
mem_univ
Every element of a finite type belongs to its universal finset `univ`.
true_and
For any proposition `p`, the conjunction `True ∧ p` is logically equivalent to `p`.
mem_image
An element `b` belongs to `s.image f` if and only if `b = f a` for some `a ∈ s`.
Finset.image_injective
The image operation on finite sets preserves injectivity of the underlying function.
card_bij
Two finite sets have equal cardinality if there exists a bijection between them.
Equiv.ext
Two equivalences (or permutations) are equal if they produce the same output on every input.
congrArg
Functions preserve equality: if `a₁ = a₂`, then `f a₁ = f a₂`.
Bool.false_eq_true
The boolean equality `false = true` is equivalent to `False`.
false_implies
An implication with a false antecedent `False → p` is vacuously true (`True`).
and_true
For any proposition `p`, the conjunction `p ∧ True` is logically equivalent to `p`.
forall_const
A universal quantification of a constant proposition over a nonempty type is equivalent to that proposition.

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 6000000set_option maxRecDepth 100000set_option synthInstance.maxSize 10000theorem wild_joint_alpha_eq_of_matching_isomorphism    (q : ℕ) (S T : Finset (Fin (3*q))) (e : Equiv.Perm (Fin (3*q)))    (heT : S.image e = T)    (heR : ∀ x y, wild_joint_canonical_matching q (e x) (e y) ↔      wild_joint_canonical_matching q x y) :    wild_joint_alpha q S = wild_joint_alpha q T := by  classical  have hblock : ∀ (σ : Equiv.Perm (Fin (3*q))) x,      wild_joint_block q (σ.trans e) (e x) = wild_joint_block q σ x := by    intro σ x    apply Fin.ext    simp [wild_joint_block]  have hfirst : ∀ σ : Equiv.Perm (Fin (3*q)),      wild_joint_first_block q (σ.trans e) = (wild_joint_first_block q σ).image e := by    intro σ    ext x    simp only [wild_joint_first_block,mem_filter,mem_univ,true_and,mem_image]    constructor    · intro hx      refine ⟨e.symm x,?_,e.apply_symm_apply x⟩      exact hx    · rintro ⟨y,hy,rfl⟩      simpa using hy  have hfirstiff : ∀ σ : Equiv.Perm (Fin (3*q)),      wild_joint_first_block q (σ.trans e) = T ↔ wild_joint_first_block q σ = S := by    intro σ    rw [hfirst,← heT]    exact Finset.image_injective e.injective |>.eq_iff  have hbad : ∀ σ : Equiv.Perm (Fin (3*q)),      wild_joint_bad_relation q (wild_joint_block q (σ.trans e)) (wild_joint_canonical_matching q) ↔      wild_joint_bad_relation q (wild_joint_block q σ) (wild_joint_canonical_matching q) := by    intro σ    constructor    · rintro ⟨B,hB,hBU,hBR⟩      refine ⟨B,hB,hBU,?_⟩      intro x y hxy      have hh := hBR (e x) (e y) ((heR x y).mpr hxy)      simpa only [hblock] using hh    · rintro ⟨B,hB,hBU,hBR⟩      refine ⟨B,hB,hBU,?_⟩      intro x y hxy      obtain ⟨x,rfl⟩ := e.surjective x      obtain ⟨y,rfl⟩ := e.surjective y      simpa only [hblock] using hBR x y ((heR x y).mp hxy)  have hcount (extra : Bool) :      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>        wild_joint_first_block q σ = S ∧          (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)            (wild_joint_canonical_matching q))).card =      (univ.filter fun σ : Equiv.Perm (Fin (3*q)) =>        wild_joint_first_block q σ = T ∧          (extra = true → wild_joint_bad_relation q (wild_joint_block q σ)            (wild_joint_canonical_matching q))).card := by    apply card_bij (fun σ _ => σ.trans e)    · intro σ hσ      simp only [mem_filter,mem_univ,true_and] at hσ ⊢      exact ⟨(hfirstiff σ).mpr hσ.1,fun h => (hbad σ).mpr (hσ.2 h)⟩    · intro σ _ τ _ h      apply Equiv.ext      intro x      have hh := congrArg (fun a : Equiv.Perm (Fin (3*q)) => a x) h      exact e.injective hh    · intro τ hτ      have hc : (τ.trans e.symm).trans e = τ := by ext x; simp      refine ⟨τ.trans e.symm,?_,hc⟩      simp only [mem_filter,mem_univ,true_and] at hτ ⊢      constructor      · apply (hfirstiff _).mp        rw [hc]        exact hτ.1      · intro h        apply (hbad _).mp        rw [hc]        exact hτ.2 h  have hnum := hcount true  have hden := hcount false  simp only [Bool.false_eq_true, false_implies, and_true, forall_const] at hnum hden  unfold wild_joint_alpha  rw [hnum,hden]
See it in the graphDiscuss this resultChallenge it