AFTD Auto-Formalizing Theoretical Domains

wild_normalized_array_single_bad_count_invariant

theoremverified

For any finite block profile p and two symmetric idempotent row-injective arrays on Fin n, the number of vertex permutations for which a chosen whole color fails some nontrivial block cut is identical for any chosen color of either array. No independence or numerical probability bound is asserted.

Statement

theorem wild_normalized_array_single_bad_count_invariant
    {K : Type*} [Fintype K]
    (n : ℕ) (p : Fin n → K) (A B : 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))
    (hBd : ∀ x, B x x = x) (hBs : ∀ x y, B x y = B y x)
    (hBi : ∀ x, Function.Injective (B x))
    (a b : Fin n) :
    (univ.filter fun σ : Equiv.Perm (Fin n) =>
      wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = a)).card =
    (univ.filter fun σ : Equiv.Perm (Fin n) =>
      wild_profile_bad (wild_profile_permute p σ) (fun x y => B x y = b)).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
Used by 1

The proof, explained

The proof reduces the invariance of single-color bad permutation counts to the general transport theorem `wild_profile_joint_bad_count_transport`. By `wild_normalized_array_single_color_isomorphism`, the normalization hypotheses on the arrays A and B yield an isomorphism between the two single-color relations. Packaging each single-color relation as a family indexed by the singleton set {()} in Unit, the transport lemma shows the counts are equal, and unfolding the joint definition over the singleton set completes the proof.

  1. There exists a vertex permutation e that is an isomorphism between the single-color relation for A at color a and the single-color relation for B at color b.

    Applying `wild_normalized_array_single_color_isomorphism` with the idempotence, symmetry, and row-injectivity hypotheses for arrays A and B produces a permutation e of Fin n such that B(e x, e y) = b if and only if A x y = a for all vertices x and y.

    lines 17–19

    uses wild_normalized_array_single_color_isomorphism

      classical
      obtain ⟨e,_,he⟩ := wild_normalized_array_single_color_isomorphism n A B
        hAd hAs hAi hBd hBs hBi a b
  2. The joint bad permutation count for A at color a over the singleton set {()} equals the joint bad permutation count for B at color b over {()}.

    We regard the single-color relation A(x, y) = a as a family of relations indexed by Unit, evaluated on the singleton set {()} ⊆ Unit, and similarly for B(x, y) = b. By the isomorphism e obtained previously, the transport lemma `wild_profile_joint_bad_count_transport` guarantees that the joint bad counts for these two singleton families are equal.

    lines 20–23

    uses wild_profile_joint_bad_count_transport

      have hh := wild_profile_joint_bad_count_transport p
        (fun _ : Unit => fun x y => A x y = a)
        (fun _ : Unit => fun x y => B x y = b) ({()} : Finset Unit)
        e (fun _ _ x y => he x y)
  3. The single-color bad permutation count for A at color a equals the joint bad permutation count for A at color a over the singleton set {()}.

    We unfold the definition of `wild_profile_joint_bad_count`, which counts permutations that are bad for every color in the set. Congruence and extensionality reduce the equality of counts to verifying that a permutation is bad for the single relation if and only if it is bad for all elements in {()}, which simplification verifies since {()} contains only the unique element ().

    lines 24–30

      calc
        _ = wild_profile_joint_bad_count p
            (fun _ : Unit => fun x y => A x y = a) ({()} : Finset Unit) := by
          unfold wild_profile_joint_bad_count
          congr 1
          ext σ
          simp
  4. The joint bad count for A at color a over {()} equals the joint bad count for B at color b over {()}.

    This step substitutes the transport equality established in the second step.

    lines 31–32

        _ = wild_profile_joint_bad_count p
            (fun _ : Unit => fun x y => B x y = b) ({()} : Finset Unit) := hh
  5. The joint bad count for B at color b over {()} equals the single-color bad permutation count for B at color b.

    Symmetrically to the first step of the calculation, unfolding `wild_profile_joint_bad_count` and simplifying the universal quantification over the singleton set {()} converts the joint bad count back to the original single-color bad count for array B and color b.

    lines 33–37

        _ = _ := by
          unfold wild_profile_joint_bad_count
          congr 1
          ext σ
          simp
wild_normalized_array_single_color_isomorphism
For any two normalized (idempotent, symmetric, row-injective) arrays A and B on Fin n and any colors a and b, there exists a permutation e of Fin n that maps a to b and induces an isomorphism between the relations A(x, y) = a and B(x, y) = b.
wild_profile_joint_bad_count_transport
If a vertex permutation e induces an isomorphism between two families of relations R and T for every color in a given finite set of colors, then the joint bad permutation count for R on that color set equals the joint bad permutation count for T.

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_single_bad_count_invariant    {K : Type*} [Fintype K]    (n : ℕ) (p : Fin n → K) (A B : 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))    (hBd : ∀ x, B x x = x) (hBs : ∀ x y, B x y = B y x)    (hBi : ∀ x, Function.Injective (B x))    (a b : Fin n) :    (univ.filter fun σ : Equiv.Perm (Fin n) =>      wild_profile_bad (wild_profile_permute p σ) (fun x y => A x y = a)).card =    (univ.filter fun σ : Equiv.Perm (Fin n) =>      wild_profile_bad (wild_profile_permute p σ) (fun x y => B x y = b)).card := by  classical  obtain ⟨e,_,he⟩ := wild_normalized_array_single_color_isomorphism n A B    hAd hAs hAi hBd hBs hBi a b  have hh := wild_profile_joint_bad_count_transport p    (fun _ : Unit => fun x y => A x y = a)    (fun _ : Unit => fun x y => B x y = b) ({()} : Finset Unit)    e (fun _ _ x y => he x y)  calc    _ = wild_profile_joint_bad_count p        (fun _ : Unit => fun x y => A x y = a) ({()} : Finset Unit) := by      unfold wild_profile_joint_bad_count      congr 1      ext σ      simp    _ = wild_profile_joint_bad_count p        (fun _ : Unit => fun x y => B x y = b) ({()} : Finset Unit) := hh    _ = _ := by      unfold wild_profile_joint_bad_count      congr 1      ext σ      simp
See it in the graphDiscuss this resultChallenge it