AFTD Auto-Formalizing Theoretical Domains

wild_joint_first_block_mixed_reduction

theoremverified

For 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 multiplicity times D. This is block symmetry with full color deduplication.

Statement

theorem wild_joint_first_block_mixed_reduction
    (q : ℕ) (hq : 3 ≤ q)
    (A : Fin (3*q) → Fin (3*q) → Fin (3*q))
    (hid : ∀ x, A x x = x) (hsym : ∀ x y, A x y = A y x)
    (hinj : ∀ x, Function.Injective (A x)) :
    (∑ σ : Equiv.Perm (Fin (3*q)),
      (wild_joint_invalid_count q A σ : ℝ) * (wild_joint_bad_color_count q A σ : ℝ)) =
    (q : ℝ) * ∑ σ : Equiv.Perm (Fin (3*q)),
      (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ) *
        (wild_joint_bad_color_count q A σ : ℝ)
Source
IN-382 / OP-306 campaign9. Explicit residual finite-counting tasks for wild_joint_expected_ID_eq_alpha_sum; no wild-number advance is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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_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_first_blockThe first block: the set of vertices placed in positions 0,1,2 by σ (= {σ 0, σ 1, σ 2}).
  • 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_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_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_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_blockBlock (index of the consecutive triple) containing vertex v under the permutation σ, where σ p is the vertex at position p; blocks are…
Used by 2

The proof, explained

By block decomposition, the invalid color count I(A, σ) is the sum over all q blocks of the multiplicity of each block set. Exchanging the order of summation expresses the total sum of I · D as the sum over all blocks b of the permutation sums for block b. For each block b, transposing block 0 and block b defines a bijection on the permutation group that maps the first block to the b-th block set while preserving the bad color count D(A, σ). Re-indexing shows that every block contributes identically to the first block, so the total sum is exactly q times the first-block sum.

  1. Permuting block labels preserves the property of being a bad relation in the forward direction.

    Given a non-empty proper subset of blocks B respecting the relation R under a block assignment p, its image e(B) under a permutation e is also non-empty and cannot be the full universe (by eq_univ_of_forall, as e is bijective). For any pair (x, y) related by R, e(p(x)) ∈ e(B) ↔ p(x) ∈ B ↔ p(y) ∈ B ↔ e(p(y)) ∈ e(B), so e(B) respects R under e ∘ p.

    lines 10–22

    uses eq_univ_of_forall, mem_univ, exists_eq_right

      classical
      have forward (p : Fin (3*q) → Fin q) (e : Equiv.Perm (Fin q)) :
          wild_joint_bad_relation q p R → wild_joint_bad_relation q (fun v => e (p v)) R := by
        rintro ⟨B,hB,hBU,hR⟩
        refine ⟨B.image e,hB.image _,?_,?_⟩
        · intro hh
          apply hBU
          apply eq_univ_of_forall
          intro b
          have : e b ∈ B.image e := by rw [hh]; exact mem_univ _
          simpa only [mem_image,e.injective.eq_iff,exists_eq_right] using this
        · intro x y hxy
          simpa only [mem_image,e.injective.eq_iff,exists_eq_right] using hR x y hxy
  2. A relation is bad with respect to e ∘ p if and only if it is bad with respect to p.

    The forward direction applies the previous step. The reverse direction applies the forward direction with the inverse permutation e⁻¹ to e ∘ p, using Equiv.symm_apply_apply to simplify e⁻¹ ∘ e ∘ p back to p.

    lines 23–27

    uses Equiv.symm_apply_apply

      constructor
      · intro h
        have := forward (fun v => e (p v)) e.symm h
        simpa only [Equiv.symm_apply_apply] using this
      · exact forward p e
  3. Relabeling position blocks by e transforms the assigned block of any element under σ by e⁻¹. automation

    Identifying Fin(3q) with Fin q × Fin 3, the permutation induced by e acts on the block factor. The block index of v under t ∘ σ is the quotient (σ⁻¹(v)%3 + 3 * e⁻¹(⌊σ⁻¹(v)/3⌋)) / 3, which equals e⁻¹(⌊σ⁻¹(v)/3⌋) by linear integer arithmetic (omega).

    lines 39–41

    uses Fin.ext

      apply Fin.ext
      simp [wild_joint_block,wild_joint_position_relabel,finProdFinEquiv,Fin.divNat]
      omega
  4. The bad color count D(A, σ) is invariant under relabeling position blocks.

    The bad color count is the number of colors whose fiber relation is bad with respect to the block assignment. By wild_joint_position_relabel_block, the block assignment for t ∘ σ is e⁻¹ ∘ block(σ, ·). By wild_joint_bad_relation_block_relabel, applying e⁻¹ preserves badness of the relation, so each color is bad for t ∘ σ if and only if it is bad for σ.

    lines 47–55

    uses wild_joint_position_relabel_block, wild_joint_bad_relation_block_relabel

      classical
      unfold wild_joint_bad_color_count
      congr 1
      ext i
      simp only [mem_filter,mem_univ,true_and]
      have hp : wild_joint_block q ((wild_joint_position_relabel q e).trans σ) =
          fun v => e.symm (wild_joint_block q σ v) := funext (wild_joint_position_relabel_block q e σ)
      rw [hp]
      exact wild_joint_bad_relation_block_relabel q _ _ e.symm
  5. The 0-th block set of σ is identical to the first block of σ. automation

    An element v belongs to block 0 when ⌊σ⁻¹(v) / 3⌋ = 0, which is equivalent to σ⁻¹(v) < 3, the definition of wild_joint_first_block.

    lines 59–61

    uses Fin.val_mk

      ext v
      simp only [wild_joint_block_set,wild_joint_first_block,mem_filter,mem_univ,true_and,Fin.val_mk]
      omega
  6. Transposing block 0 and block b in positions transforms the first block of the relabeled permutation into the b-th block set of σ.

    By wild_joint_block_set_zero, the first block of t ∘ σ is its 0-th block set. An element v belongs to this set if and only if its assigned block under t ∘ σ is 0, which by wild_joint_position_relabel_block means (0 b)⁻¹(block(σ, v)) = 0. By Equiv.symm_apply_eq, this is equivalent to block(σ, v) = (0 b)(0) = b, which defines the b-th block set.

    lines 68–72

    uses wild_joint_block_set_zero, wild_joint_block_set_mem, wild_joint_position_relabel_block, Equiv.symm_apply_eq

      rw [← wild_joint_block_set_zero q hq]
      ext v
      rw [wild_joint_block_set_mem,wild_joint_block_set_mem,wild_joint_position_relabel_block]
      rw [Equiv.symm_apply_eq]
      simp
  7. For every block b, the sum over permutations of the multiplicity of block b times D(A, σ) equals the sum for the first block.

    Let t be the permutation of Fin(3q) that swaps block 0 and block b. Composing with t defines a permutation E of S_{3q}. Re-indexing the sum by E via Fintype.sum_equiv, wild_joint_position_swap_first turns the first block of t ∘ σ into the b-th block set of σ, while wild_joint_position_relabel_bad_count shows that the bad color count is invariant under t.

    lines 84–101

    uses Fintype.sum_equiv, wild_joint_position_swap_first, wild_joint_position_relabel_bad_count

      classical
      have hb (b : Fin q) :
          (∑ σ : Equiv.Perm (Fin (3*q)),
            (wild_joint_multiplicity q A (wild_joint_block_set q σ b) : ℝ)*
              (wild_joint_bad_color_count q A σ : ℝ)) =
          ∑ σ : Equiv.Perm (Fin (3*q)),
            (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ)*
              (wild_joint_bad_color_count q A σ : ℝ) := by
        let t := wild_joint_position_relabel q (Equiv.swap (⟨0,by omega⟩ : Fin q) b)
        let E : Equiv.Perm (Equiv.Perm (Fin (3*q))) :=
          { toFun := fun σ => t.trans σ
            invFun := fun σ => t.symm.trans σ
            left_inv := by intro σ; ext v; simp
            right_inv := by intro σ; ext v; simp }
        apply Fintype.sum_equiv E
        intro σ
        dsimp [E,t]
        rw [wild_joint_position_swap_first q (by omega),wild_joint_position_relabel_bad_count]
  8. The total sum of invalid count times bad color count equals q times the first-block multiplicity sum.

    By wild_joint_invalid_count_eq_sum_multiplicity, the invalid color count decomposes into the sum over all q blocks b of the multiplicity of the b-th block set. Multiplying by D(A, σ) and swapping the double summation using sum_comm expresses the total sum as a sum over b of the block-b sums. By the previous step, each of these q sums is equal to the first-block sum, yielding a factor of q.

    lines 102–105

    uses wild_joint_invalid_count_eq_sum_multiplicity, Nat.cast_sum, sum_mul, sum_comm

      simp_rw [wild_joint_invalid_count_eq_sum_multiplicity q A hid hsym hinj,Nat.cast_sum,sum_mul]
      rw [sum_comm]
      simp_rw [hb]
      simp
Equiv.symm_apply_apply
Applying the inverse of an equivalence to the image of an element yields the original element.
Equiv.symm_apply_eq
For an equivalence e, e⁻¹(x) = y if and only if x = e(y).
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
Fin.val_mk
The numerical value of ⟨m, h⟩ in Fin n is m.
Fintype.sum_equiv
Summing over a finite type is invariant under re-indexing by an equivalence between index types.
Nat.cast_sum
The canonical cast from natural numbers to a semiring commutes with finite sums.
eq_univ_of_forall
A finset containing every element of a finite type is the universal set.
exists_eq_right
An existential statement ∃ a, p(a) ∧ a = a' simplifies to p(a').
mem_univ
Every element of a finite type belongs to the universal finset.
sum_mul
Multiplication distributes from the right over finite sums.
sum_comm
Double sums over finite sets can be interchanged.
wild_joint_bad_relation_block_relabel
Permuting block labels does not change whether a binary relation is a bad relation.
wild_joint_block_set_mem
An element belongs to the b-th block set under σ if and only if its assigned block under σ is b.
wild_joint_block_set_zero
The 0-th block set under σ equals the first block of σ.
wild_joint_invalid_count_eq_sum_multiplicity
For a normalized array, the invalid color count under σ is the sum of multiplicities over all block sets.
wild_joint_position_relabel_bad_count
The number of bad colors is invariant under relabeling the blocks of positions.
wild_joint_position_relabel_block
Relabeling position blocks by e transforms the block assignment under σ by e⁻¹.
wild_joint_position_swap_first
Transposing block 0 and block b in positions transforms the first block of the relabeled permutation into the b-th block set of σ.

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_relation_block_relabel (q : ℕ)    (p : Fin (3*q) → Fin q) (R : Fin (3*q) → Fin (3*q) → Prop)    (e : Equiv.Perm (Fin q)) :    wild_joint_bad_relation q (fun v => e (p v)) R ↔ wild_joint_bad_relation q p R := by  classical  have forward (p : Fin (3*q) → Fin q) (e : Equiv.Perm (Fin q)) :      wild_joint_bad_relation q p R → wild_joint_bad_relation q (fun v => e (p v)) R := by    rintro ⟨B,hB,hBU,hR⟩    refine ⟨B.image e,hB.image _,?_,?_⟩    · intro hh      apply hBU      apply eq_univ_of_forall      intro b      have : e b ∈ B.image e := by rw [hh]; exact mem_univ _      simpa only [mem_image,e.injective.eq_iff,exists_eq_right] using this    · intro x y hxy      simpa only [mem_image,e.injective.eq_iff,exists_eq_right] using hR x y hxy  constructor  · intro h    have := forward (fun v => e (p v)) e.symm h    simpa only [Equiv.symm_apply_apply] using this  · exact forward p enoncomputable def wild_joint_position_relabel (q : ℕ) (e : Equiv.Perm (Fin q)) :    Equiv.Perm (Fin (3*q)) :=  let E : Fin q × Fin 3 ≃ Fin (3*q) :=    finProdFinEquiv.trans (finCongr (Nat.mul_comm q 3))  E.symm.trans ((e.prodCongr (Equiv.refl (Fin 3))).trans E)lemma wild_joint_position_relabel_block (q : ℕ) (e : Equiv.Perm (Fin q))    (σ : Equiv.Perm (Fin (3*q))) (v : Fin (3*q)) :    wild_joint_block q ((wild_joint_position_relabel q e).trans σ) v =      e.symm (wild_joint_block q σ v) := by  apply Fin.ext  simp [wild_joint_block,wild_joint_position_relabel,finProdFinEquiv,Fin.divNat]  omegalemma wild_joint_position_relabel_bad_count (q : ℕ) (A : Fin (3*q) → Fin (3*q) → Fin (3*q))    (e : Equiv.Perm (Fin q)) (σ : Equiv.Perm (Fin (3*q))) :    wild_joint_bad_color_count q A ((wild_joint_position_relabel q e).trans σ) =      wild_joint_bad_color_count q A σ := by  classical  unfold wild_joint_bad_color_count  congr 1  ext i  simp only [mem_filter,mem_univ,true_and]  have hp : wild_joint_block q ((wild_joint_position_relabel q e).trans σ) =      fun v => e.symm (wild_joint_block q σ v) := funext (wild_joint_position_relabel_block q e σ)  rw [hp]  exact wild_joint_bad_relation_block_relabel q _ _ e.symmlemma wild_joint_block_set_zero (q : ℕ) (hq : 0<q) (σ : Equiv.Perm (Fin (3*q))) :    wild_joint_block_set q σ ⟨0,hq⟩ = wild_joint_first_block q σ := by  ext v  simp only [wild_joint_block_set,wild_joint_first_block,mem_filter,mem_univ,true_and,Fin.val_mk]  omegalemma wild_joint_position_swap_first (q : ℕ) (hq : 0<q)    (b : Fin q) (σ : Equiv.Perm (Fin (3*q))) :    wild_joint_first_block q      ((wild_joint_position_relabel q (Equiv.swap ⟨0,hq⟩ b)).trans σ) =      wild_joint_block_set q σ b := by  rw [← wild_joint_block_set_zero q hq]  ext v  rw [wild_joint_block_set_mem,wild_joint_block_set_mem,wild_joint_position_relabel_block]  rw [Equiv.symm_apply_eq]  simptheorem wild_joint_first_block_mixed_reduction    (q : ℕ) (hq : 3 ≤ q)    (A : Fin (3*q) → Fin (3*q) → Fin (3*q))    (hid : ∀ x, A x x = x) (hsym : ∀ x y, A x y = A y x)    (hinj : ∀ x, Function.Injective (A x)) :    (∑ σ : Equiv.Perm (Fin (3*q)),      (wild_joint_invalid_count q A σ : ℝ) * (wild_joint_bad_color_count q A σ : ℝ)) =    (q : ℝ) * ∑ σ : Equiv.Perm (Fin (3*q)),      (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ) *        (wild_joint_bad_color_count q A σ : ℝ) := by  classical  have hb (b : Fin q) :      (∑ σ : Equiv.Perm (Fin (3*q)),        (wild_joint_multiplicity q A (wild_joint_block_set q σ b) : ℝ)*          (wild_joint_bad_color_count q A σ : ℝ)) =      ∑ σ : Equiv.Perm (Fin (3*q)),        (wild_joint_multiplicity q A (wild_joint_first_block q σ) : ℝ)*          (wild_joint_bad_color_count q A σ : ℝ) := by    let t := wild_joint_position_relabel q (Equiv.swap (⟨0,by omega⟩ : Fin q) b)    let E : Equiv.Perm (Equiv.Perm (Fin (3*q))) :=      { toFun := fun σ => t.trans σ        invFun := fun σ => t.symm.trans σ        left_inv := by intro σ; ext v; simp        right_inv := by intro σ; ext v; simp }    apply Fintype.sum_equiv E    intro σ    dsimp [E,t]    rw [wild_joint_position_swap_first q (by omega),wild_joint_position_relabel_bad_count]  simp_rw [wild_joint_invalid_count_eq_sum_multiplicity q A hid hsym hinj,Nat.cast_sum,sum_mul]  rw [sum_comm]  simp_rw [hb]  simp
See it in the graphDiscuss this resultChallenge it