wild_joint_first_block_mixed_reduction
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
- wild_joint_expected_ID_eq_alpha_sumCore 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…
- wild_partition_two_block_deficit_obstructionFor the same explicit15 array, every way of choosing two distinct original triple blocks and a three-element subset of their six local…
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.
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.
uses
eq_univ_of_forall,mem_univ,exists_eq_rightclassical 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
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.
uses
Equiv.symm_apply_applyconstructor · intro h have := forward (fun v => e (p v)) e.symm h simpa only [Equiv.symm_apply_apply] using this · exact forward p e
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).
uses
Fin.extapply Fin.ext simp [wild_joint_block,wild_joint_position_relabel,finProdFinEquiv,Fin.divNat] omega
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 σ.
uses
wild_joint_position_relabel_block,wild_joint_bad_relation_block_relabelclassical 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
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.
uses
Fin.val_mkext v simp only [wild_joint_block_set,wild_joint_first_block,mem_filter,mem_univ,true_and,Fin.val_mk] omega
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.
uses
wild_joint_block_set_zero,wild_joint_block_set_mem,wild_joint_position_relabel_block,Equiv.symm_apply_eqrw [← 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
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.
uses
Fintype.sum_equiv,wild_joint_position_swap_first,wild_joint_position_relabel_bad_countclassical 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]
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.
uses
wild_joint_invalid_count_eq_sum_multiplicity,Nat.cast_sum,sum_mul,sum_commsimp_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 σ.
- The transposition of block 0 and block b requires 0 < q, which is proved on the fly via omega from 3 ≤ q.
- Integer division arithmetic in the block index transformation is verified by omega automation.
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_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