wild_joint_conditioned_bad_probability_transport
For arbitrary relations R,U and a vertex permutation e carrying S to T and preserving the relations, the conditional whole-bad probabilities given first block S or T agree. Both probabilities are explicit finite-cardinality ratios.
Statement
theorem wild_joint_conditioned_bad_probability_transport (q : ℕ) (R U : Fin (3*q) → Fin (3*q) → Prop) (S T : Finset (Fin (3*q))) (e : Equiv.Perm (Fin (3*q))) (heT : S.image e = T) (heR : ∀ x y, U (e x) (e y) ↔ R x y) : (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = S ∧ wild_joint_bad_relation q (wild_joint_block q σ) R).card : ℝ) / (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = S).card) = (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = T ∧ wild_joint_bad_relation q (wild_joint_block q σ) U).card : ℝ) / (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = T).card)
- Source
- IN-382 / OP-306 campaign9, 2026-10-30. Standard finite matching symmetry and exact permutation conditioning supporting wild_joint_expected_ID_eq_alpha_sum. This uses the corrected odd-q orbit theorem; it does not establish the main weighted sign or a new wild-number bound.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- wild_joint_alphaalpha(T): the conditional probability, under the uniform distribution on all vertex permutations σ, that the fixed canonical matching is…
- wild_joint_first_blockThe first block: the set of vertices placed in positions 0,1,2 by σ (= {σ 0, σ 1, σ 2}).
- wild_joint_blockBlock (index of the consecutive triple) containing vertex v under the permutation σ, where σ p is the vertex at position p; blocks are…
- 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,…
- Used by 1
- wild_joint_conditional_bad_eq_alpha_of_color_typeFor odd q>=3 and a normalized symmetric row-injective array, the conditional probability that a chosen WHOLE color is bad, given a…
The proof, explained
The proof establishes that post-composition by the vertex permutation $e$, mapping $\sigma \mapsto \sigma \circ e$, provides a cardinality-preserving bijection between permutations associated with $(S, R)$ and those associated with $(T, U)$. First, block assignments and first blocks are shown to transform equivariantly under $e$, which makes the condition of having first block $S$ equivalent to having first block $T$, and preserves badness between relations $R$ and $U$. A single bijective equicardinality lemma parameterised by a boolean flag then simultaneously equates the numerators (with the badness condition) and denominators (conditioning only on the first block), completing the equality of conditional probabilities.
Block assignment is equivariant under composition with $e$: the block of $e(x)$ under $\sigma \circ e$ equals the block of $x$ under $\sigma$.
Enabling classical logic, we consider the block assignment `wild_joint_block`, which assigns element $v$ to block $\lfloor \sigma^{-1}(v) / 3 \rfloor$. For the composed permutation $\sigma \circ e$ evaluated at $e(x)$, the inverse permutation gives $(\sigma \circ e)^{-1}(e(x)) = \sigma^{-1}(e^{-1}(e(x))) = \sigma^{-1}(x)$. Dividing by 3 gives identical quotient values, which `Fin.ext` and `simp` verify by definition.
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$.
By definition, an element $x$ belongs to `wild_joint_first_block q (σ.trans e)` if and only if $((\sigma \circ e)^{-1}(x)) < 3$, which is equivalent to $\sigma^{-1}(e^{-1}(x)) < 3$. This means $e^{-1}(x)$ belongs to the first block of $\sigma$, or equivalently, $x$ lies in the image under $e$ of the first block of $\sigma$. The equivalence is established by exhibiting $e^{-1}(x)$ in the forward direction and simplifying in the reverse direction.
uses
true_andhave 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
The first block of $\sigma \circ e$ equals $T$ if and only if the first block of $\sigma$ equals $S$.
From the previous step, the first block of $\sigma \circ e$ is $e(\text{first\_block}(\sigma))$. Since $T = e(S)$ by hypothesis `heT`, this equality is $e(\text{first\_block}(\sigma)) = e(S)$. Because $e$ is an equivalence and therefore injective, the finset image operation is injective (`Finset.image_injective`), so the image sets are equal if and only if the original sets are equal.
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
The relation $U$ is bad under $\sigma \circ e$ if and only if $R$ is bad under $\sigma$.
A relation is bad if there is a non-trivial block subset $B$ such that related pairs belong to $B$ either both or neither. By `hblock`, the block of $e(x)$ under $\sigma \circ e$ is the block of $x$ under $\sigma$. Because $U(e(x), e(y)) \leftrightarrow R(x, y)$ by hypothesis `heR` and $e$ is surjective, pairs related by $R$ correspond bijectively to pairs related by $U$. Thus, a subset of blocks $B$ witnesses badness for $U$ under $\sigma \circ e$ if and only if it witnesses badness for $R$ under $\sigma$.
have hbad : ∀ σ : Equiv.Perm (Fin (3*q)), wild_joint_bad_relation q (wild_joint_block q (σ.trans e)) U ↔ wild_joint_bad_relation q (wild_joint_block q σ) R := 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 `extra`, the set of permutations with first block $S$ (and bad for $R$ if `extra = true`) has the same cardinality as the corresponding set for $T$ and $U$.
We apply `card_bij` with the map $\sigma \mapsto \sigma \circ e$. This map preserves the membership conditions by `hfirstiff` and `hbad`. It is injective because $\sigma \circ e = \tau \circ e$ implies $\sigma(x) = \tau(x)$ for all $x$ via $e$'s injectivity, yielding $\sigma = \tau$ by `Equiv.ext`. It is surjective because any target permutation $\tau$ is the image of $\tau \circ e^{-1}$, which satisfies the required conditions since $(\tau \circ e^{-1}) \circ e = \tau$.
uses
card_bij,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 σ) R)).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 σ) U)).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 probabilities given first block $S$ under $R$ and given first block $T$ under $U$ are equal.
Setting `extra = true` in `hcount` equates the numerators of the two conditional probability ratios (permutations whose first block matches and for which the relation is bad). Setting `extra = false` makes the badness implication vacuously true (`false_implies`), which equates the denominators (all permutations with the given first block). Rewriting both the numerator and denominator counts by these equalities finishes 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 rw [hnum,hden]
Fin.ext- Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
true_and- The conjunction `True ∧ p` simplifies to `p`.
Finset.image_injective- If `f` is an injective function, then the finset image operation `Finset.image f` is also injective.
card_bij- Two finite sets have equal cardinality if there exists a bijection (an injective and surjective map) between them.
Equiv.ext- Two equivalences (or permutations) are equal if they agree pointwise on all inputs.
congrArg- Applying a function to equal arguments produces equal results: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
Bool.false_eq_true- The equality `false = true` in `Bool` evaluates to `False`.
false_implies- An implication with a false antecedent, `False → p`, is logically equivalent to `True`.
and_true- The conjunction `p ∧ True` simplifies to `p`.
forall_const- A universal quantification over a nonempty domain of a constant proposition is equivalent to the proposition itself.
- In Lean, `Equiv.trans σ e` denotes the composite permutation $e \circ \sigma$ (post-composition by $e$), so that $(\sigma \circ e)^{-1}(e(x)) = \sigma^{-1}(x)$.
- The lemma `hcount` introduces a boolean flag `extra : Bool` as a formal device to unify the equicardinality proofs for the numerator (`extra = true`) and denominator (`extra = false`) via a single application of `card_bij`.
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 20000set_option synthInstance.maxSize 10000theorem wild_joint_conditioned_bad_probability_transport (q : ℕ) (R U : Fin (3*q) → Fin (3*q) → Prop) (S T : Finset (Fin (3*q))) (e : Equiv.Perm (Fin (3*q))) (heT : S.image e = T) (heR : ∀ x y, U (e x) (e y) ↔ R x y) : (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = S ∧ wild_joint_bad_relation q (wild_joint_block q σ) R).card : ℝ) / (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = S).card) = (((univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = T ∧ wild_joint_bad_relation q (wild_joint_block q σ) U).card : ℝ) / (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ = T).card) := 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)) U ↔ wild_joint_bad_relation q (wild_joint_block q σ) R := 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 σ) R)).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 σ) U)).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 rw [hnum,hden]