AFTD Auto-Formalizing Theoretical Domains

wild_normalized_array_whole_bad_first_moment

theoremverified

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

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.

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

    lines 15–20

    uses card_eq_sum_ones, sum_filter, sum_comm

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

    lines 21–26

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

    line 27

        _ = _ := 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.

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