AFTD Auto-Formalizing Theoretical Domains

wild_joint_expected_ID_eq_alpha_sum

theoremverified

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

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

    lines 11–12

    uses sum_ite

      classical
      simp [wild_joint_bad_color_count,sum_ite]
  2. 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).

    lines 21–26

    uses wild_joint_bad_count_eq_indicator_sum, sum_comm, sum_congr, filter_filter, sum_ite

      classical
      simp_rw [wild_joint_bad_count_eq_indicator_sum]
      rw [sum_comm]
      apply sum_congr rfl
      intro i _
      simp [sum_ite,filter_filter]
  3. 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.

    lines 30–38

    uses Nat.factorial_ne_zero, Nat.choose_pos, Nat.ne_of_gt

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

    lines 39–48

    uses wild_joint_first_block_fiber_mass, Fintype.card_perm, Fintype.card_fin, zero_mul

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

    lines 49–61

    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_comm

      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 _ _)
  6. 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.

    lines 62–69

    uses wild_joint_first_block_fiber_mass_card, mem_filter, mem_univ, sum_fiberwise_of_maps_to

      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 σ : ℝ))
  7. 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.

    lines 70–88

    uses mul_sum, sum_congr, mem_filter

      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
  8. 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).

    lines 89–94

    uses wild_joint_first_block_mixed_reduction

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

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