wild_normalized_array_disjoint_witness_pair_count
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
- wild_normalized_array_pair_witness_cardLet A be a symmetric idempotent row-injective array on Fin n. For any two distinct vertices a,b, exactly six ORDERED pairs (x,y), x!=y,…
- wild_normalized_array_vertex_witness_cardLet A be a symmetric idempotent row-injective array on Fin n. For any fixed vertex a, exactly3*(n-1) ORDERED pairs (x,y), x!=y, have a in…
- wild_three_uniform_disjoint_pair_countLet T_i be three-element subsets of a finite vertex type, indexed by a finite type of size N, with repeated subsets allowed. Suppose each…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
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).
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.
uses
card_bij,mem_univ,Subtype.extclassical 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⟩
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.
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 : ℤ) = _
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.
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)))
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.
uses
card_insert_of_notMem,Ne.symmhave 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]
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).
uses
wild_array_witness_filter_card,wild_normalized_array_vertex_witness_cardhave 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
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.
uses
wild_array_witness_filter_card,wild_normalized_array_pair_witness_cardhave 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
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).
uses
wild_array_witness_filter_card,wild_finset_offDiag_card_int,card_univ,Fintype.card_finhave 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
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).
uses
wild_three_uniform_disjoint_pair_count,Fintype.card_fin,Nat.cast_mul,Nat.cast_subhave 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.
- The algebraic reduction from the general 3-uniform hypergraph identity to the final polynomial expression n*(n-1)*(n^2-10*n+27) is handled automatically by integer polynomial arithmetic tactics.
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 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]