AFTD Auto-Formalizing Theoretical Domains

wild_normalized_array_disjoint_witness_pair_count

theoremverified

Let n>=3 and let A be a symmetric idempotent row-injective array on Fin n. Index its ordered witnesses by W={(x,y):x!=y}, with support T(x,y)={x,y,A(x,y)}. The number D of ORDERED pairs of witnesses whose supports are disjoint, plus the number Q of ORDERED pairs whose supports are identical, equals n*(n-1)*(n^2-10*n+27), with all arithmetic in the displayed equality interpreted in the integers. This holds for every such full normalized array; it does not assert the required uniform cubic-cost inequality.

Statement

theorem wild_normalized_array_disjoint_witness_pair_count
    (n : ℕ) (hn : 3 ≤ n) (A : Fin n → Fin n → Fin n)
    (hid : ∀ a, A a a = a)
    (hsym : ∀ a b, A a b = A b a)
    (hinj : ∀ a, Function.Injective (A a)) :
    let W := {p : Fin n × Fin n // p.1 ≠ p.2}
    let T : W → Finset (Fin n) := fun p => {p.val.1,p.val.2,A p.val.1 p.val.2}
    ((univ.filter fun p : W × W => Disjoint (T p.1) (T p.2)).card : ℤ) +
      ((univ.filter fun p : W × W => T p.1 = T p.2).card : ℤ) =
        (n : ℤ) * ((n : ℤ)-1) * ((n : ℤ)^2-10*(n : ℤ)+27)
Source
IN-359 / OP-306 helper for the uniform weighted-moment route. The associated threefold triple system is standard: Compatible factorizations and three-fold triple systems (2006), construction in the proof of Theorem4.1, https://citeseerx.ist.psu.edu/document?doi=58cc9f2b7c3862f0964a05e0ac1529b9c9de8e5e&repid=rep1&type=pdf (bibliographic record https://repo.uum.edu.my/id/eprint/3494/). The graph motivation is https://arxiv.org/html/2610.22142v1, Section3.3 and the open conjecture in Section6. Incidence square sums and three-element inclusion-exclusion are ordinary finite counting. No novelty, wild-number bound, sharpness case, or research advance is claimed. Exact finite audit8955 is diagnostic, not a hypothesis.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

First, an auxiliary lemma (wild_array_witness_filter_card) establishes that counting over the witness subtype W coincides with counting over off-diagonal pairs. The main proof then models the supports of these ordered witnesses as a 3-uniform hypergraph on n vertices. By symmetry, idempotence, and row-injectivity of the array, each support has size 3, each vertex has degree 3*(n-1), and each pair has codegree 6. Applying the general 3-uniform disjoint pair formula (wild_three_uniform_disjoint_pair_count) and simplifying the resulting integer polynomial yields n*(n-1)*(n^2-10*n+27).

  1. For any predicate P on pairs, the number of witnesses p in the subtype W satisfying P(p) equals the number of pairs (x, y) with x ≠ y satisfying P(x, y).

    We establish a bijection between the subtype filter and the product filter using card_bij via the subtype coercion p ↦ p.val. The map preserves the filter condition using mem_univ, is injective by subtype extensionality (Subtype.ext), and is surjective because any off-diagonal pair satisfying P lifts to the subtype.

    lines 9–17

    uses card_bij, mem_univ, Subtype.ext

      classical
      apply card_bij (fun p _ => p.val)
      · intro p hp
        exact mem_filter.mpr ⟨mem_univ _, p.property, (mem_filter.mp hp).2⟩
      · intro p hp q hq heq
        exact Subtype.ext heq
      · intro p hp
        have hp := (mem_filter.mp hp).2
        exact ⟨⟨p,hp.1⟩, mem_filter.mpr ⟨mem_univ _,hp.2⟩, rfl⟩
  2. Let W be the set of pairs (x, y) with x ≠ y, and let T(w) = {x, y, A(x, y)} be the support of each witness w. The goal is to evaluate the sum of the count of disjoint pairs of supports and identical pairs of supports.

    We introduce the subtype W of off-diagonal pairs and the support map T : W → Finset (Fin n). We rephrase the goal in terms of these definitions.

    lines 29–34

      classical
      dsimp only
      let W := {p : Fin n × Fin n // p.1 ≠ p.2}
      let T : W → Finset (Fin n) := fun p => {p.val.1,p.val.2,A p.val.1 p.val.2}
      change ((univ.filter fun p : W × W => Disjoint (T p.1) (T p.2)).card : ℤ) +
          ((univ.filter fun p : W × W => T p.1 = T p.2).card : ℤ) = _
  3. For any distinct elements x and y, the array entry A(x, y) is distinct from both x and y.

    If A(x, y) = x, then since A(x, x) = x by idempotence, injectivity of the row map A(x, ·) implies y = x, a contradiction. Similarly, if A(x, y) = y, symmetry gives A(y, x) = y = A(y, y), so injectivity of A(y, ·) implies x = y, a contradiction.

    lines 35–40

      have hout (x y : Fin n) (hxy : x ≠ y) : A x y ≠ x ∧ A x y ≠ y := by
        constructor
        · intro h
          exact hxy ((hinj x) (h.trans (hid x).symm)).symm
        · intro h
          exact hxy ((hinj y) ((hsym y x).trans (h.trans (hid y).symm)))
  4. For every witness w ∈ W, its support T(w) contains exactly 3 distinct elements. automation

    Since w = (x, y) satisfies x ≠ y, and by the previous step A(x, y) is neither x nor y, the set {x, y, A(x, y)} consists of three pairwise distinct elements.

    lines 41–45

    uses card_insert_of_notMem, Ne.symm

      have hsize : ∀ w : W, (T w).card = 3 := by
        intro w
        have h := hout w.val.1 w.val.2 w.property
        simp [T,card_insert_of_notMem,w.property,h.1,h.2,
          Ne.symm w.property,Ne.symm h.1,Ne.symm h.2]
  5. Every element a ∈ Fin n belongs to the support of exactly 3*(n-1) witnesses.

    Using wild_array_witness_filter_card, we translate the counting problem from the subtype W to the filtered Cartesian product of distinct pairs. Then wild_normalized_array_vertex_witness_card establishes that each vertex has degree 3*(n-1).

    lines 46–55

    uses wild_array_witness_filter_card, wild_normalized_array_vertex_witness_card

      have hvertex (a : Fin n) :
          (univ.filter fun w : W => a ∈ T w).card = 3*(n-1) := by
        change (univ.filter fun w : {p : Fin n × Fin n // p.1 ≠ p.2} =>
          a ∈ ({w.val.1,w.val.2,A w.val.1 w.val.2} : Finset (Fin n))).card = _
        calc
          _ = (univ.filter fun p : Fin n × Fin n =>
              p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card :=
            wild_array_witness_filter_card n
              (fun p => a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)))
          _ = _ := wild_normalized_array_vertex_witness_card n A hid hsym hinj a
  6. Every pair of distinct elements a, b ∈ Fin n belongs to the support of exactly 6 witnesses.

    Again using wild_array_witness_filter_card to transfer between the subtype and the product, we invoke wild_normalized_array_pair_witness_card to show that any two distinct vertices have codegree 6.

    lines 56–68

    uses wild_array_witness_filter_card, wild_normalized_array_pair_witness_card

      have hpair (a b : Fin n) (hab : a ≠ b) :
          (univ.filter fun w : W => a ∈ T w ∧ b ∈ T w).card = 6 := by
        change (univ.filter fun w : {p : Fin n × Fin n // p.1 ≠ p.2} =>
          a ∈ ({w.val.1,w.val.2,A w.val.1 w.val.2} : Finset (Fin n)) ∧
          b ∈ ({w.val.1,w.val.2,A w.val.1 w.val.2} : Finset (Fin n))).card = _
        calc
          _ = (univ.filter fun p : Fin n × Fin n =>
              p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)) ∧
              b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card :=
            wild_array_witness_filter_card n
              (fun p => a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)) ∧
                b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)))
          _ = _ := wild_normalized_array_pair_witness_card n A hid hsym hinj a b hab
  7. The total number of witnesses is |W| = n*(n-1) in the integers.

    Transferring the count of W via wild_array_witness_filter_card identifies |W| with the size of the off-diagonal of Fin n. By wild_finset_offDiag_card_int, the off-diagonal of a set of size n has cardinality n^2 - n = n*(n-1).

    lines 69–81

    uses wild_array_witness_filter_card, wild_finset_offDiag_card_int, card_univ, Fintype.card_fin

      have hcount : Fintype.card W = ((univ : Finset (Fin n)).offDiag).card := by
        calc
          _ = (univ.filter fun _ : W => True).card := by simp
          _ = (univ.filter fun p : Fin n × Fin n => p.1 ≠ p.2 ∧ True).card :=
            wild_array_witness_filter_card n (fun _ => True)
          _ = _ := by
            congr 1
            ext p
            simp
      have hcountZ : (Fintype.card W : ℤ) = (n : ℤ)*((n : ℤ)-1) := by
        rw [hcount,wild_finset_offDiag_card_int]
        simp only [card_univ,Fintype.card_fin]
        ring
  8. The number of disjoint witness pairs plus the number of identical witness pairs equals n*(n-1)*(n^2-10*n+27). automation

    We apply the general counting lemma wild_three_uniform_disjoint_pair_count for 3-uniform hypergraphs with |W| = n*(n-1) hyperedges on n vertices, vertex degree d = 3*(n-1), and pair codegree l = 6. Substituting these parameters into 2*D = 2*|W|^2 - 2*n*d^2 + (n^2 - n)*l^2 - 2*Q and rearranging algebraically over the integers yields the desired equality D + Q = n*(n-1)*(n^2-10*n+27).

    lines 82–88

    uses wild_three_uniform_disjoint_pair_count, Fintype.card_fin, Nat.cast_mul, Nat.cast_sub

      have h := wild_three_uniform_disjoint_pair_count T (3*(n-1)) 6 hsize hvertex hpair
      rw [hcountZ] at h
      simp only [Fintype.card_fin] at h
      have hn1 : 1 ≤ n := by omega
      rw [Nat.cast_mul, Nat.cast_sub hn1] at h
      norm_num at h
      nlinarith [h]
card_bij
Two finite sets have the same cardinality if there is a bijection between them (a map that sends elements into the codomain, is injective, and is surjective).
mem_univ
Every element of a finite type belongs to its universal finset univ.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
wild_array_witness_filter_card
The number of elements in the subtype {p : Fin n × Fin n // p.1 ≠ p.2} satisfying P equals the number of pairs (x, y) with x ≠ y satisfying P(x, y).
wild_normalized_array_vertex_witness_card
In a symmetric idempotent row-injective array on Fin n, each element belongs to the support of exactly 3*(n-1) ordered witness pairs.
wild_normalized_array_pair_witness_card
In a symmetric idempotent row-injective array on Fin n, any two distinct elements belong to the support of exactly 6 ordered witness pairs.
wild_finset_offDiag_card_int
For any finite set S, the integer cardinality of its off-diagonal (distinct pairs) is |S|^2 - |S|.
card_univ
The cardinality of the universal finset univ on a finite type is the cardinality of that type.
Fintype.card_fin
The cardinality of Fin n is n.
wild_three_uniform_disjoint_pair_count
For any 3-uniform hypergraph with edge set ι on vertex set κ, constant vertex degree d, and constant pair codegree l, twice the number of disjoint ordered pairs of edges equals 2*|ι|^2 - 2*|κ|*d^2 + (|κ|^2 - |κ|)*l^2 minus twice the number of identical pairs.
Nat.cast_mul
The canonical cast from the natural numbers to a semiring preserves multiplication: ↑(m * n) = ↑m * ↑n.
Nat.cast_sub
If m ≤ n, the canonical cast from the natural numbers to an additive group with one preserves subtraction: ↑(n - m) = ↑n - ↑m.

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 BigOperatorsset_option maxHeartbeats 4000000theorem wild_array_witness_filter_card (n : ℕ)    (P : Fin n × Fin n → Prop) [DecidablePred P] :    (univ.filter fun p : {p : Fin n × Fin n // p.1 ≠ p.2} => P p.val).card =      (univ.filter fun p : Fin n × Fin n => p.1 ≠ p.2 ∧ P p).card := by  classical  apply card_bij (fun p _ => p.val)  · intro p hp    exact mem_filter.mpr ⟨mem_univ _, p.property, (mem_filter.mp hp).2⟩  · intro p hp q hq heq    exact Subtype.ext heq  · intro p hp    have hp := (mem_filter.mp hp).2    exact ⟨⟨p,hp.1⟩, mem_filter.mpr ⟨mem_univ _,hp.2⟩, rfl⟩theorem wild_normalized_array_disjoint_witness_pair_count    (n : ℕ) (hn : 3 ≤ n) (A : Fin n → Fin n → Fin n)    (hid : ∀ a, A a a = a)    (hsym : ∀ a b, A a b = A b a)    (hinj : ∀ a, Function.Injective (A a)) :    let W := {p : Fin n × Fin n // p.1 ≠ p.2}    let T : W → Finset (Fin n) := fun p => {p.val.1,p.val.2,A p.val.1 p.val.2}    ((univ.filter fun p : W × W => Disjoint (T p.1) (T p.2)).card : ℤ) +      ((univ.filter fun p : W × W => T p.1 = T p.2).card : ℤ) =        (n : ℤ) * ((n : ℤ)-1) * ((n : ℤ)^2-10*(n : ℤ)+27) := by  classical  dsimp only  let W := {p : Fin n × Fin n // p.1 ≠ p.2}  let T : W → Finset (Fin n) := fun p => {p.val.1,p.val.2,A p.val.1 p.val.2}  change ((univ.filter fun p : W × W => Disjoint (T p.1) (T p.2)).card : ℤ) +      ((univ.filter fun p : W × W => T p.1 = T p.2).card : ℤ) = _  have hout (x y : Fin n) (hxy : x ≠ y) : A x y ≠ x ∧ A x y ≠ y := by    constructor    · intro h      exact hxy ((hinj x) (h.trans (hid x).symm)).symm    · intro h      exact hxy ((hinj y) ((hsym y x).trans (h.trans (hid y).symm)))  have hsize : ∀ w : W, (T w).card = 3 := by    intro w    have h := hout w.val.1 w.val.2 w.property    simp [T,card_insert_of_notMem,w.property,h.1,h.2,      Ne.symm w.property,Ne.symm h.1,Ne.symm h.2]  have hvertex (a : Fin n) :      (univ.filter fun w : W => a ∈ T w).card = 3*(n-1) := by    change (univ.filter fun w : {p : Fin n × Fin n // p.1 ≠ p.2} =>      a ∈ ({w.val.1,w.val.2,A w.val.1 w.val.2} : Finset (Fin n))).card = _    calc      _ = (univ.filter fun p : Fin n × Fin n =>          p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card :=        wild_array_witness_filter_card n          (fun p => a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)))      _ = _ := wild_normalized_array_vertex_witness_card n A hid hsym hinj a  have hpair (a b : Fin n) (hab : a ≠ b) :      (univ.filter fun w : W => a ∈ T w ∧ b ∈ T w).card = 6 := by    change (univ.filter fun w : {p : Fin n × Fin n // p.1 ≠ p.2} =>      a ∈ ({w.val.1,w.val.2,A w.val.1 w.val.2} : Finset (Fin n)) ∧      b ∈ ({w.val.1,w.val.2,A w.val.1 w.val.2} : Finset (Fin n))).card = _    calc      _ = (univ.filter fun p : Fin n × Fin n =>          p.1 ≠ p.2 ∧ a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)) ∧          b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n))).card :=        wild_array_witness_filter_card n          (fun p => a ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)) ∧            b ∈ ({p.1,p.2,A p.1 p.2} : Finset (Fin n)))      _ = _ := wild_normalized_array_pair_witness_card n A hid hsym hinj a b hab  have hcount : Fintype.card W = ((univ : Finset (Fin n)).offDiag).card := by    calc      _ = (univ.filter fun _ : W => True).card := by simp      _ = (univ.filter fun p : Fin n × Fin n => p.1 ≠ p.2 ∧ True).card :=        wild_array_witness_filter_card n (fun _ => True)      _ = _ := by        congr 1        ext p        simp  have hcountZ : (Fintype.card W : ℤ) = (n : ℤ)*((n : ℤ)-1) := by    rw [hcount,wild_finset_offDiag_card_int]    simp only [card_univ,Fintype.card_fin]    ring  have h := wild_three_uniform_disjoint_pair_count T (3*(n-1)) 6 hsize hvertex hpair  rw [hcountZ] at h  simp only [Fintype.card_fin] at h  have hn1 : 1 ≤ n := by omega  rw [Nat.cast_mul, Nat.cast_sub hn1] at h  norm_num at h  nlinarith [h]
See it in the graphDiscuss this resultChallenge it