wild_joint_alpha_eq_of_matching_isomorphism
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
- 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
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$.
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.
uses
Fin.extclassical 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]
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.
uses
mem_filter,mem_univ,true_and,mem_imagehave 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
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$.
uses
Finset.image_injectivehave 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
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$.
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)
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.
uses
card_bij,mem_filter,mem_univ,true_and,Equiv.ext,congrArghave 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
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.
uses
Bool.false_eq_true,false_implies,and_true,forall_consthave 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.
- In the auxiliary lemma `hcount`, the boolean parameter `extra` is a formal device that unifies the counts for the numerator (`extra = true`, requiring the bad relation) and the denominator (`extra = false`, where the bad condition is vacuously satisfied), avoiding duplication of the bijection proof.
- In Lean, permutation composition `σ.trans e` evaluates on elements as `e (σ x)`, meaning that composition with `e` on the right acts as post-composition by `e`.
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_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]