wild_joint_expected_ID_eq_alpha_sum
Core reduction: E[I*D] = q/C(n,3) * sum over 3-sets T of mu(T) * sum_i alpha_of_color_type(T,i), where alpha_of_color_type is the alpha of the colour-i orbit type of T.
Statement
theorem wild_joint_expected_ID_eq_alpha_sum (q : ℕ) (hq : 3 ≤ q) (hodd : q % 2 = 1) (A : Fin (3*q) → Fin (3*q) → Fin (3*q)) (hid : ∀ a, A a a = a) (hsym : ∀ a b, A a b = A b a) (hinj : ∀ a, Function.Injective (A a)) : wild_joint_expected_ID q A = ((q : ℝ) / ((3*q).choose 3 : ℝ)) * ∑ T ∈ (Finset.univ.filter (fun T : Finset (Fin (3*q)) => T.card = 3)), (wild_joint_multiplicity q A T : ℝ) * (∑ i : Fin (3*q), wild_joint_alpha_of_color_type q hq A T i)
- Source
- step towards wild_one_bad_color_mixed_moment_formula_with_context
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 23
- wild_joint_expected_IDE[I*D]: the expectation of I(σ)*D(σ) over the uniform distribution on all vertex permutations σ of Fin (3q), i.e. (1/n!) * sum over σ of…
- wild_joint_multiplicitymu(T): the number of unordered vertex pairs {x,y} (x != y) whose witness support {x,y,A x y} equals T. Equals half the ordered count…
- wild_joint_alpha_of_color_typeThe alpha of the type of the pair (T,i): an if-chain on colour_type(T,i) selecting alpha at the concrete triple of that type. Because…
- wild_joint_color_typeThe orbit type in {0,1,2,3} of triple T relative to colour i, where a colour-i edge inside T is an unordered pair of distinct elements of…
- wild_joint_alphaalpha(T): the conditional probability, under the uniform distribution on all vertex permutations σ, that the fixed canonical matching is…
- wild_joint_invalid_countI(σ): the number of colours i that invalidate a triple block, i.e. there exist distinct x,y in a single σ-block with A x y = i and i in…
- wild_joint_bad_color_countD(σ): the number of colours i that are whole-bad, i.e. some proper union of σ-blocks has no colour-i edge crossing it (block graph of the…
- 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_block_setThe b-th block as a vertex set = {σ (3b), σ (3b+1), σ (3b+2)}. Note wild_joint_block_set q σ 0 = wild_joint_first_block q σ.
- wild_joint_first_blockThe first block: the set of vertices placed in positions 0,1,2 by σ (= {σ 0, σ 1, σ 2}).
- 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_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_canonical_typeThe orbit type in {0,1,2,3} of a triple T relative to the fixed canonical matching: 0 (=A) if T contains a canonical edge and 0; 1 (=B) if…
- wild_joint_type_AType-A triple {0,1,2}: contains the isolated vertex 0 and the canonical edge {1,2}; immediately whole-bad, so alpha at it is 1.
- wild_joint_type_BType-B triple {0,1,3}: contains the isolated vertex 0 but no canonical edge.
- wild_joint_type_CType-C triple {1,2,3}: contains the canonical edge {1,2} but not the isolated vertex 0.
- wild_joint_type_DType-D triple {1,3,5}: contains neither the isolated vertex 0 nor a canonical edge (three vertices from distinct pairs).
- wild_joint_invalid_count_eq_sum_multiplicityFor every vertex permutation σ, the invalid-colour count I(σ) equals the sum, over the q blocks, of the witness-support multiplicity mu of…
- wild_joint_canonical_type_valuesThe four concrete triples have canonical orbit types 0,1,2,3 respectively.
- 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…
- 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…
- wild_joint_first_block_fiber_massFor any three-element T on Fin(3q), q>=3, the number of vertex permutations with first block T times choose(3q,3) equals the number of all…
- wild_joint_first_block_mixed_reductionFor q>=3 and a normalized array, summing I times the whole-bad count D over all permutations equals q times the sum of first-block witness…
The proof, explained
The theorem reduces the expectation E[I * D] to a weighted sum of orbit-type probabilities α over 3-element subsets T. First, a mixed reduction expresses the total permutation sum of I(σ) * D(σ) as q times the sum of μ(first_block(σ)) * D(σ). Second, the sum over permutations is partitioned into fibers according to their first block T, each having cardinality 3. On each fiber, the multiplicity μ(T) factors out and the bad color counts sum to (N / C) * ∑_i α(T, i) by conditional probability. Finally, the normalising factor 1 / N cancels the total permutation count N = (3q)!, leaving the prefactor q / C(3q, 3).
The bad color count of a permutation σ equals the sum over all colors i of the indicator that the color-i relation is bad for the block partition induced by σ.
By definition, the bad color count is the cardinality of the set of bad colors. Summing an indicator function over all colors equals the cardinality of the subset where the predicate holds (via sum_ite).
uses
sum_iteclassical simp [wild_joint_bad_color_count,sum_ite]For any 3-element subset T, the sum of bad color counts over all permutations in the fiber with first block T equals the sum over all colors i of the number of permutations in that fiber for which color i is bad.
We replace the bad color count by its indicator sum using wild_joint_bad_count_eq_indicator_sum and interchange the order of summation over the fiber and over colors i using sum_comm. For each fixed color i, the inner sum of indicators collapses to the cardinality of the filtered subfiber where color i is bad (via filter_filter and sum_ite).
uses
wild_joint_bad_count_eq_indicator_sum,sum_comm,sum_congr,filter_filter,sum_iteclassical simp_rw [wild_joint_bad_count_eq_indicator_sum] rw [sum_comm] apply sum_congr rfl intro i _ simp [sum_ite,filter_filter]
The constants N = (3q)! and C = C(3q, 3) are non-zero.
We define the fiber size function F(T), the total number of permutations N = (3q)!, and the number of 3-element subsets C = C(3q, 3). Factorials are always positive by Nat.factorial_ne_zero. Since 3 ≤ q implies 3 ≤ 3q, the binomial coefficient C is strictly positive by Nat.choose_pos and Nat.ne_of_gt.
uses
Nat.factorial_ne_zero,Nat.choose_pos,Nat.ne_of_gtclassical let F := fun T : Finset (Fin (3*q)) => (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T).card let N : ℝ := (3*q).factorial let C : ℝ := (3*q).choose 3 have hN : N≠0 := by dsimp [N]; exact_mod_cast Nat.factorial_ne_zero (3*q) have hC : C≠0 := by dsimp [C] exact_mod_cast Nat.ne_of_gt (Nat.choose_pos (by omega : 3≤3*q))
For every 3-element subset T, the fiber size F(T) satisfies F(T) * C = N, and in particular F(T) ≠ 0.
By wild_joint_first_block_fiber_mass, the fiber cardinality F(T) times C(3q, 3) equals the total permutation count (3q)! (using Fintype.card_perm and Fintype.card_fin). If F(T) were zero, multiplying by C would give zero (zero_mul), contradicting N ≠ 0.
uses
wild_joint_first_block_fiber_mass,Fintype.card_perm,Fintype.card_fin,zero_mulhave hmass (T : Finset (Fin (3*q))) (hT : T.card=3) : (F T : ℝ)*C=N := by have h := wild_joint_first_block_fiber_mass q hq T hT rw [Fintype.card_perm,Fintype.card_fin] at h dsimp [F,C,N] exact_mod_cast h have hF (T : Finset (Fin (3*q))) (hT : T.card=3) : (F T : ℝ)≠0 := by intro hh have h := hmass T hT rw [hh,zero_mul] at h exact hN h.symm
For any 3-element subset T, the sum over the fiber of permutations with first block T of the bad color count equals (N / C) * ∑ i, wild_joint_alpha_of_color_type q hq A T i.
Applying wild_joint_first_block_bad_fiber_sum expresses the fiber sum as the sum over colors i of the number of permutations in the fiber for which color i is bad. Dividing this subfiber size by F(T) gives the color-type probability wild_joint_alpha_of_color_type (by wild_joint_conditional_bad_eq_alpha_of_color_type). Since F(T) = N / C, multiplying through by F(T) using div_eq_iff, eq_div_iff, and mul_comm yields (N / C) * α(T, i) for each color, which sums over i as claimed.
uses
wild_joint_first_block_bad_fiber_sum,mul_sum,sum_congr,wild_joint_conditional_bad_eq_alpha_of_color_type,div_eq_iff,eq_div_iff,mul_commhave hfiber (T : Finset (Fin (3*q))) (hT : T.card=3) : (∑ σ ∈ (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T), (wild_joint_bad_color_count q A σ : ℝ)) = (N/C)*(∑ i : Fin (3*q),wild_joint_alpha_of_color_type q hq A T i) := by rw [wild_joint_first_block_bad_fiber_sum,mul_sum] apply sum_congr rfl intro i _ have h := wild_joint_conditional_bad_eq_alpha_of_color_type q hq hodd A hid hsym hinj T hT i change _/(F T : ℝ)=_ at h have hn := (div_eq_iff (hF T hT)).mp h have hm : (F T : ℝ)=N/C := (eq_div_iff hC).mpr (hmass T hT) rw [hm] at hn exact hn.trans (mul_comm _ _)
The total sum over all permutations of μ(first_block(σ)) * bad_color_count(σ) partitions fiberwise over all 3-element subsets T.
For every permutation σ, the first block has cardinality exactly 3 (wild_joint_first_block_fiber_mass_card, mem_filter, mem_univ). We apply sum_fiberwise_of_maps_to to decompose the sum over all permutations into an outer sum over 3-element subsets T and an inner sum over the fiber of permutations whose first block is T.
uses
wild_joint_first_block_fiber_mass_card,mem_filter,mem_univ,sum_fiberwise_of_maps_tohave hmaps : ∀ σ ∈ (univ : Finset (Equiv.Perm (Fin (3*q)))), wild_joint_first_block q σ ∈ (univ.filter fun T : Finset (Fin (3*q)) => T.card=3) := by intro σ _ exact mem_filter.mpr ⟨mem_univ _,wild_joint_first_block_fiber_mass_card q hq σ⟩ have hdecomp := sum_fiberwise_of_maps_to hmaps (fun σ : Equiv.Perm (Fin (3*q)) => (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ)* (wild_joint_bad_color_count q A σ : ℝ))
The total sum ∑_σ μ(first_block(σ)) * bad_color_count(σ) equals (N / C) * ∑_{|T|=3} μ(T) * ∑_i α(T, i).
In the fiberwise decomposition, for each fixed 3-set T, the multiplicity μ(first_block(σ)) is constant on the fiber and equals μ(T) (mem_filter), so it factors out of the fiber sum (mul_sum, sum_congr). Substituting the fiber sum formula from step 5 replaces the inner sum with (N / C) * ∑_i α(T, i). Finally, the constant factor N / C factors out of the entire sum over 3-sets T.
uses
mul_sum,sum_congr,mem_filterhave hsum : (∑ σ : Equiv.Perm (Fin (3*q)), (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ)* (wild_joint_bad_color_count q A σ : ℝ)) = (N/C)*(∑ T ∈ (univ.filter fun T : Finset (Fin (3*q)) => T.card=3), (wild_joint_multiplicity q A T : ℝ)* (∑ i : Fin (3*q),wild_joint_alpha_of_color_type q hq A T i)) := by rw [← hdecomp,mul_sum] apply sum_congr rfl intro T hT have hc := (mem_filter.mp hT).2 calc _ = (wild_joint_multiplicity q A T : ℝ)* (∑ σ ∈ (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T), (wild_joint_bad_color_count q A σ : ℝ)) := by rw [mul_sum] apply sum_congr rfl intro σ hσ rw [(mem_filter.mp hσ).2] _ = _ := by rw [hfiber T hc]; ring
E[I * D] = (q / C(3q, 3)) * ∑_{|T|=3} μ(T) * ∑_i α(T, i). automation
Unfolding wild_joint_expected_ID writes the expectation as (1 / N) * ∑_σ I(σ) D(σ). By the mixed reduction lemma (wild_joint_first_block_mixed_reduction), this equals (1 / N) * q * ∑_σ μ(first_block(σ)) D(σ). Substituting the evaluated sum (N / C) * ∑_T μ(T) ∑_i α(T, i) gives (1 / N) * q * (N / C) * ∑_T μ(T) ∑_i α(T, i). Since N ≠ 0 and C ≠ 0, clearing denominators and cancelling N via field_simp and ring arithmetic leaves (q / C) * ∑_T μ(T) ∑_i α(T, i).
uses
wild_joint_first_block_mixed_reductionunfold wild_joint_expected_ID rw [wild_joint_first_block_mixed_reduction q hq A hid hsym hinj] rw [hsum] change (1/N)*((q : ℝ)*((N/C)*_))=((q : ℝ)/C)*_ field_simp [hN,hC] <;> ring
sum_ite- The sum of an indicator function over a finite set equals the cardinality of the subset where the condition holds.
wild_joint_bad_count_eq_indicator_sum- The number of bad colors for a permutation σ equals the sum over all colors i of the indicator that the color-i relation is bad for σ.
sum_comm- Finitely many sums over two index sets can be interchanged: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every index.
filter_filter- Filtering a finite set successively by two predicates is equivalent to filtering once by their conjunction.
Nat.factorial_ne_zero- The factorial of any natural number is non-zero.
Nat.ne_of_gt- If a natural number is strictly greater than another, they are not equal.
Nat.choose_pos- The binomial coefficient C(n, k) is strictly positive whenever k ≤ n.
wild_joint_first_block_fiber_mass- For any 3-element subset T, the number of permutations whose first block is T multiplied by C(3q, 3) equals the total number of permutations (3q)!.
Fintype.card_perm- The number of permutations of a finite type of cardinality n is n!.
Fintype.card_fin- The cardinality of Fin n is n.
zero_mul- Multiplying zero by any element in a ring yields zero.
wild_joint_first_block_bad_fiber_sum- The sum of the bad color counts over all permutations with first block T equals the sum over all colors i of the number of permutations with first block T for which color i is bad.
mul_sum- Multiplication distributes over finite sums: a * ∑ i, f i = ∑ i, a * f i.
wild_joint_conditional_bad_eq_alpha_of_color_type- The conditional probability that color i is bad given that the first block is T equals α evaluated at the orbit color type of (T, i).
div_eq_iff- For b ≠ 0, a / b = c is equivalent to a = c * b.
eq_div_iff- For b ≠ 0, c = a / b is equivalent to c * b = a.
mul_comm- Multiplication is commutative: a * b = b * a.
wild_joint_first_block_fiber_mass_card- When 3 ≤ q, the first block of any permutation has cardinality exactly 3.
mem_filter- An element belongs to a filtered set if and only if it belongs to the ambient set and satisfies the predicate.
mem_univ- Every element of a finite type belongs to its universal set univ.
sum_fiberwise_of_maps_to- A sum over a finite set can be partitioned into a double sum over the fibers of a mapping into a target set.
wild_joint_first_block_mixed_reduction- The sum over all permutations of the invalid count times the bad color count equals q times the sum of the first block multiplicity times the bad color count.
- The reduction of the fiber sum to the color-type probabilities (wild_joint_conditional_bad_eq_alpha_of_color_type) and the mixed reduction (wild_joint_first_block_mixed_reduction) are proved as separate lemmas in the project.
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 linter.unusedSimpArgs falselemma wild_joint_bad_count_eq_indicator_sum (q : ℕ) (A : Fin (3*q) → Fin (3*q) → Fin (3*q)) (σ : Equiv.Perm (Fin (3*q))) : (wild_joint_bad_color_count q A σ : ℝ) = ∑ i : Fin (3*q),if wild_joint_bad_relation q (wild_joint_block q σ) (fun x y => x≠y ∧ A x y=i) then (1 : ℝ) else 0 := by classical simp [wild_joint_bad_color_count,sum_ite]lemma wild_joint_first_block_bad_fiber_sum (q : ℕ) (A : Fin (3*q) → Fin (3*q) → Fin (3*q)) (T : Finset (Fin (3*q))) : (∑ σ ∈ (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T), (wild_joint_bad_color_count q A σ : ℝ)) = ∑ i : Fin (3*q),((univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T ∧ wild_joint_bad_relation q (wild_joint_block q σ) (fun x y => x≠y ∧ A x y=i)).card : ℝ) := by classical simp_rw [wild_joint_bad_count_eq_indicator_sum] rw [sum_comm] apply sum_congr rfl intro i _ simp [sum_ite,filter_filter]/-- Reduction of E[I*D] to a single sum of mu(T) against colour-type alphas. -/theorem wild_joint_expected_ID_eq_alpha_sum (q : ℕ) (hq : 3 ≤ q) (hodd : q % 2 = 1) (A : Fin (3*q) → Fin (3*q) → Fin (3*q)) (hid : ∀ a, A a a = a) (hsym : ∀ a b, A a b = A b a) (hinj : ∀ a, Function.Injective (A a)) : wild_joint_expected_ID q A = ((q : ℝ) / ((3*q).choose 3 : ℝ)) * ∑ T ∈ (Finset.univ.filter (fun T : Finset (Fin (3*q)) => T.card = 3)), (wild_joint_multiplicity q A T : ℝ) * (∑ i : Fin (3*q), wild_joint_alpha_of_color_type q hq A T i) := by classical let F := fun T : Finset (Fin (3*q)) => (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T).card let N : ℝ := (3*q).factorial let C : ℝ := (3*q).choose 3 have hN : N≠0 := by dsimp [N]; exact_mod_cast Nat.factorial_ne_zero (3*q) have hC : C≠0 := by dsimp [C] exact_mod_cast Nat.ne_of_gt (Nat.choose_pos (by omega : 3≤3*q)) have hmass (T : Finset (Fin (3*q))) (hT : T.card=3) : (F T : ℝ)*C=N := by have h := wild_joint_first_block_fiber_mass q hq T hT rw [Fintype.card_perm,Fintype.card_fin] at h dsimp [F,C,N] exact_mod_cast h have hF (T : Finset (Fin (3*q))) (hT : T.card=3) : (F T : ℝ)≠0 := by intro hh have h := hmass T hT rw [hh,zero_mul] at h exact hN h.symm have hfiber (T : Finset (Fin (3*q))) (hT : T.card=3) : (∑ σ ∈ (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T), (wild_joint_bad_color_count q A σ : ℝ)) = (N/C)*(∑ i : Fin (3*q),wild_joint_alpha_of_color_type q hq A T i) := by rw [wild_joint_first_block_bad_fiber_sum,mul_sum] apply sum_congr rfl intro i _ have h := wild_joint_conditional_bad_eq_alpha_of_color_type q hq hodd A hid hsym hinj T hT i change _/(F T : ℝ)=_ at h have hn := (div_eq_iff (hF T hT)).mp h have hm : (F T : ℝ)=N/C := (eq_div_iff hC).mpr (hmass T hT) rw [hm] at hn exact hn.trans (mul_comm _ _) have hmaps : ∀ σ ∈ (univ : Finset (Equiv.Perm (Fin (3*q)))), wild_joint_first_block q σ ∈ (univ.filter fun T : Finset (Fin (3*q)) => T.card=3) := by intro σ _ exact mem_filter.mpr ⟨mem_univ _,wild_joint_first_block_fiber_mass_card q hq σ⟩ have hdecomp := sum_fiberwise_of_maps_to hmaps (fun σ : Equiv.Perm (Fin (3*q)) => (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ)* (wild_joint_bad_color_count q A σ : ℝ)) have hsum : (∑ σ : Equiv.Perm (Fin (3*q)), (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ)* (wild_joint_bad_color_count q A σ : ℝ)) = (N/C)*(∑ T ∈ (univ.filter fun T : Finset (Fin (3*q)) => T.card=3), (wild_joint_multiplicity q A T : ℝ)* (∑ i : Fin (3*q),wild_joint_alpha_of_color_type q hq A T i)) := by rw [← hdecomp,mul_sum] apply sum_congr rfl intro T hT have hc := (mem_filter.mp hT).2 calc _ = (wild_joint_multiplicity q A T : ℝ)* (∑ σ ∈ (univ.filter fun σ : Equiv.Perm (Fin (3*q)) => wild_joint_first_block q σ=T), (wild_joint_bad_color_count q A σ : ℝ)) := by rw [mul_sum] apply sum_congr rfl intro σ hσ rw [(mem_filter.mp hσ).2] _ = _ := by rw [hfiber T hc]; ring unfold wild_joint_expected_ID rw [wild_joint_first_block_mixed_reduction q hq A hid hsym hinj] rw [hsum] change (1/N)*((q : ℝ)*((N/C)*_))=((q : ℝ)/C)*_ field_simp [hN,hC] <;> ring