wild_normalized_array_pair_witness_card
Let 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, have both a and b in the witness support {x,y,A(x,y)}. Opposite orientations are counted separately; this is pair multiplicity three for the unordered witness multiset. Outputs lie in the full Fin n universe.
Statement
theorem wild_normalized_array_pair_witness_card (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)) (a b : Fin n) (hab : a ≠ b) : (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 = 6
- 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- Used by 1
- wild_normalized_array_disjoint_witness_pair_countLet 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…
The proof, explained
The proof proceeds by explicitly characterizing the set of all ordered pairs (x, y) with x ≠ y whose support {x, y, A(x, y)} contains both a and b, and then computing its cardinality. Because each row map A(x, -) is an injective endofunction on the finite set Fin n, it is surjective, yielding unique elements u and v such that A(a, u) = b and A(b, v) = a. Idempotence, symmetry, and row-injectivity guarantee that u and v are distinct from each other and from a and b, and a case analysis demonstrates that (x, y) must be one of exactly six pairs: (a, b), (b, a), (a, u), (u, a), (b, v), or (v, b). Finally, because all six pairs are distinct, the cardinality of this set is 6.
There exist vertices u and v such that A(a, u) = b and A(b, v) = a.
Because `Fin n` is a finite set and each row function `A(x, -)` is assumed injective (`hinj`), every row function is also surjective by `Finite.surjective_of_injective`. Applying surjectivity of `A(a, -)` to `b` yields a witness `u` with `A(a, u) = b`, and applying surjectivity of `A(b, -)` to `a` yields a witness `v` with `A(b, v) = a`.
uses
Finite.surjective_of_injectiveclassical obtain ⟨u, hu⟩ := (Finite.surjective_of_injective (hinj a)) b obtain ⟨v, hv⟩ := (Finite.surjective_of_injective (hinj b)) a
The witnesses u and v are distinct from both a and b, and satisfy A(u, a) = b and A(v, b) = a.
If `u = a`, then by idempotence (`hid`), `b = A(a, u) = A(a, a) = a`, contradicting `a ≠ b`; thus `u ≠ a`. If `u = b`, then symmetry and idempotence give `A(b, a) = A(a, b) = A(a, u) = b = A(b, b)`, so injectivity of `A(b, -)` forces `a = b`, again a contradiction; thus `u ≠ b`. Interchanging the roles of `a` and `b` gives `v ≠ b` and `v ≠ a`. Finally, symmetry of `A` (`hsym`) implies `A(u, a) = A(a, u) = b` and `A(v, b) = A(b, v) = a`.
have hua : u ≠ a := by intro h subst u rw [hid] at hu exact hab hu have hub : u ≠ b := by intro h subst u have h : A b a = A b b := by rw [← hsym, hu, hid] exact hab ((hinj b) h) have hvb : v ≠ b := by intro h subst v rw [hid] at hv exact hab hv.symm have hva : v ≠ a := by intro h subst v have h : A a b = A a a := by rw [hsym, hv, hid] exact hab ((hinj a) h).symm have hua' : A u a = b := by rw [hsym, hu] have hvb' : A v b = a := by rw [hsym, hv]
The set of pairs (x, y) with x ≠ y whose witness support {x, y, A(x, y)} contains both a and b is precisely {(a, b), (b, a), (a, u), (u, a), (b, v), (v, b)}.
By set extensionality, we establish both set inclusions. In the forward direction, assume `x ≠ y` and `{a, b} ⊆ {x, y, A(x, y)}`. We case split on which element of the support equals `a` and which equals `b`: if `a = x`, then `b ≠ x` (since `a ≠ b`), so either `b = y` yielding `(a, b)`, or `b = A(a, y)` which by injectivity of `A(a, -)` forces `y = u`, giving `(a, u)`. If `a = y`, symmetrically we obtain `(b, a)` or `(u, a)`. If `a = A(x, y)`, then either `b = x`, which by injectivity of `A(b, -)` forces `y = v` giving `(b, v)`; or `b = y`, giving `(v, b)`; while `b = A(x, y)` implies `a = b`, ruled out by `False.elim`. In the reverse direction, each of the six candidate pairs is checked directly: each pair has distinct components and contains both `a` and `b` in its witness support via the established identities for `u` and `v`.
uses
mem_filter,mem_univ,true_and,mem_insert,mem_singleton,False.elim,Prod.mk.injEq,Ne.symmhave heq : (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))) = {(a,b),(b,a),(a,u),(u,a),(b,v),(v,b)} := by ext p rcases p with ⟨x,y⟩ simp only [mem_filter, mem_univ, true_and] constructor · rintro ⟨hxy, ha, hb⟩ simp only [mem_insert, mem_singleton] at ha hb rcases ha with hax | hay | haA · subst x rcases hb with hba | hby | hbA · exact False.elim (hab hba.symm) · subst y simp · have hy : y = u := (hinj a) (hbA.symm.trans hu.symm) subst y simp · subst y rcases hb with hbx | hba | hbA · subst x simp · exact False.elim (hab hba.symm) · have hx : x = u := (hinj a) ((hsym a x).trans (hbA.symm.trans hu.symm)) subst x simp · rcases hb with hbx | hby | hbA · subst x have hy : y = v := (hinj b) (haA.symm.trans hv.symm) subst y simp · subst y have hx : x = v := (hinj b) ((hsym b x).trans (haA.symm.trans hv.symm)) subst x simp · exact False.elim (hab (haA.trans hbA.symm)) · intro hp simp only [mem_insert, mem_singleton, Prod.mk.injEq] at hp rcases hp with h | h | h | h | h | h all_goals rcases h with ⟨rfl,rfl⟩ all_goals simp [hab, Ne.symm hab, hua, hub, hva, hvb, Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb, hu, hv, hua', hvb']
The cardinality of the set of witness pairs is 6.
Rewriting the set of witness pairs with the explicit six-element set equality `heq`, we compute its cardinality. The pairwise distinctness of `a, b, u, v` ensures that all six pairs are distinct from one another. Repeated application of `card_insert_of_notMem` strips each element while adding 1 to the count, giving 6.
uses
card_insert_of_notMem,Prod.mk.injEq,Ne.symmrw [heq] simp [card_insert_of_notMem, Prod.mk.injEq, hab, Ne.symm hab, hua, hub, hva, hvb, Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb]
Finite.surjective_of_injective- An injective function from a finite type to itself is surjective.
mem_filter- An element belongs to the filtered sub-finset if and only if it belongs to the base set and satisfies the predicate.
mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The conjunction of True with any proposition p simplifies to p.
mem_insert- An element belongs to the insertion `insert b s` if and only if it equals `b` or belongs to `s`.
mem_singleton- An element belongs to a singleton `{a}` if and only if it equals `a`.
False.elim- From a contradiction (False), any conclusion can be deduced (principle of explosion).
Prod.mk.injEq- Two ordered pairs are equal if and only if their respective first and second components are equal.
Ne.symm- Inequality is symmetric: if `a ≠ b`, then `b ≠ a`.
card_insert_of_notMem- Inserting an element not already present into a finite set increases its cardinality by 1.
- Classical logic is activated at the start (line 13) to provide decidable equality and membership for Finset operations over `Fin n`.
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 Finsetset_option maxHeartbeats 4000000theorem wild_normalized_array_pair_witness_card (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)) (a b : Fin n) (hab : a ≠ b) : (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 = 6 := by classical obtain ⟨u, hu⟩ := (Finite.surjective_of_injective (hinj a)) b obtain ⟨v, hv⟩ := (Finite.surjective_of_injective (hinj b)) a have hua : u ≠ a := by intro h subst u rw [hid] at hu exact hab hu have hub : u ≠ b := by intro h subst u have h : A b a = A b b := by rw [← hsym, hu, hid] exact hab ((hinj b) h) have hvb : v ≠ b := by intro h subst v rw [hid] at hv exact hab hv.symm have hva : v ≠ a := by intro h subst v have h : A a b = A a a := by rw [hsym, hv, hid] exact hab ((hinj a) h).symm have hua' : A u a = b := by rw [hsym, hu] have hvb' : A v b = a := by rw [hsym, hv] have heq : (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))) = {(a,b),(b,a),(a,u),(u,a),(b,v),(v,b)} := by ext p rcases p with ⟨x,y⟩ simp only [mem_filter, mem_univ, true_and] constructor · rintro ⟨hxy, ha, hb⟩ simp only [mem_insert, mem_singleton] at ha hb rcases ha with hax | hay | haA · subst x rcases hb with hba | hby | hbA · exact False.elim (hab hba.symm) · subst y simp · have hy : y = u := (hinj a) (hbA.symm.trans hu.symm) subst y simp · subst y rcases hb with hbx | hba | hbA · subst x simp · exact False.elim (hab hba.symm) · have hx : x = u := (hinj a) ((hsym a x).trans (hbA.symm.trans hu.symm)) subst x simp · rcases hb with hbx | hby | hbA · subst x have hy : y = v := (hinj b) (haA.symm.trans hv.symm) subst y simp · subst y have hx : x = v := (hinj b) ((hsym b x).trans (haA.symm.trans hv.symm)) subst x simp · exact False.elim (hab (haA.trans hbA.symm)) · intro hp simp only [mem_insert, mem_singleton, Prod.mk.injEq] at hp rcases hp with h | h | h | h | h | h all_goals rcases h with ⟨rfl,rfl⟩ all_goals simp [hab, Ne.symm hab, hua, hub, hva, hvb, Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb, hu, hv, hua', hvb'] rw [heq] simp [card_insert_of_notMem, Prod.mk.injEq, hab, Ne.symm hab, hua, hub, hva, hvb, Ne.symm hua, Ne.symm hub, Ne.symm hva, Ne.symm hvb]