wild_normalized_array_whole_bad_first_moment
For a symmetric idempotent row-injective array on Fin n and any finite block profile, the sum over all vertex permutations of the number of whole bad colors equals n times the permutation count for any one chosen color. Bad means failure across some nonempty proper block cut; this counts colors, not closed cuts.
Statement
theorem wild_normalized_array_whole_bad_first_moment {K : Type*} [Fintype K] (n : ℕ) (p : Fin n → K) (A : Fin n → Fin n → Fin n) (hAd : ∀ x, A x x = x) (hAs : ∀ x y, A x y = A y x) (hAi : ∀ x, Function.Injective (A x)) (a : Fin n) : (∑ σ : Equiv.Perm (Fin n), (univ.filter fun i : Fin n => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = i)).card) = n * (univ.filter fun σ : Equiv.Perm (Fin n) => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = a)).card
- Source
- IN-382 / OP-306 campaign9, 2026-10-30. Standard finite involution conjugacy and permutation transport, supporting the moment route for https://arxiv.org/html/2610.22142v1. Background https://arxiv.org/abs/0911.3604 . No new wild-number bound or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- wild_normalized_array_single_bad_count_invariantFor any finite block profile p and two symmetric idempotent row-injective arrays on Fin n, the number of vertex permutations for which a…
- wild_profile_conditioned_joint_count_transportFor a finite vertex type, finite block type, arbitrary block profile p, chosen block b and vertex subset S, and any finite set of color…
The proof, explained
The proof is a double-counting argument. We first interchange the order of summation, expressing the total count of whole bad colors across all permutations as the sum over each color of the number of permutations making that color bad. By color-count invariance for normalized arrays (wild_normalized_array_single_bad_count_invariant), this count is identical for every color, so each term equals the count for the fixed color a. Summing this constant over all n colors gives n times the permutation count for a.
The sum over all permutations of the number of bad colors equals the sum over all colors of the number of permutations making each color bad.
Using card_eq_sum_ones and sum_filter, the cardinality of the filtered set of bad colors is rewritten as a sum of indicator functions. Exchanging the order of summation with sum_comm turns the double sum over permutations and colors into a sum over colors of the permutation count for each color.
uses
card_eq_sum_ones,sum_filter,sum_commclassical calc _ = ∑ i : Fin n, (univ.filter fun σ : Equiv.Perm (Fin n) => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = i)).card := by simp_rw [card_eq_sum_ones, sum_filter] exact sum_comm
For every color i, the number of permutations making color i bad equals the number of permutations making the fixed color a bad.
By sum_congr, it suffices to equate the summands for each color i. Since the array A is idempotent (hAd), symmetric (hAs), and row-injective (hAi), the invariance lemma wild_normalized_array_single_bad_count_invariant applies with both arrays set to A, showing that the count of bad permutations for color i is equal to that for color a.
uses
sum_congr,wild_normalized_array_single_bad_count_invariant_ = ∑ _i : Fin n, (univ.filter fun σ : Equiv.Perm (Fin n) => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = a)).card := by apply sum_congr rfl intro i _ exact wild_normalized_array_single_bad_count_invariant n p A A hAd hAs hAi hAd hAs hAi i a
The sum over all n colors of the constant count equals n times that count. automation
The summand no longer depends on the color index, so summing this constant over the n elements of Fin n simplifies to n times the constant.
_ = _ := by simp
card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all its elements.
sum_filter- The sum of a function over the subset of elements satisfying a predicate equals the sum over the whole set with terms not satisfying the predicate replaced by 0.
sum_comm- The order of summation in a finite double sum can be exchanged.
sum_congr- Two finite sums are equal if their index sets are identical and their summands agree on every element of the index set.
wild_normalized_array_single_bad_count_invariant- For symmetric, idempotent, row-injective arrays on Fin n, the number of permutations for which a given color is bad is invariant under the choice of array and color.
- Line 15 invokes classical logic so that decidability instances for set filtering and indicator functions are available automatically.
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 3000000theorem wild_normalized_array_whole_bad_first_moment {K : Type*} [Fintype K] (n : ℕ) (p : Fin n → K) (A : Fin n → Fin n → Fin n) (hAd : ∀ x, A x x = x) (hAs : ∀ x y, A x y = A y x) (hAi : ∀ x, Function.Injective (A x)) (a : Fin n) : (∑ σ : Equiv.Perm (Fin n), (univ.filter fun i : Fin n => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = i)).card) = n * (univ.filter fun σ : Equiv.Perm (Fin n) => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = a)).card := by classical calc _ = ∑ i : Fin n, (univ.filter fun σ : Equiv.Perm (Fin n) => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = i)).card := by simp_rw [card_eq_sum_ones, sum_filter] exact sum_comm _ = ∑ _i : Fin n, (univ.filter fun σ : Equiv.Perm (Fin n) => wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = a)).card := by apply sum_congr rfl intro i _ exact wild_normalized_array_single_bad_count_invariant n p A A hAd hAs hAi hAd hAs hAi i a _ = _ := by simp