wild_normalized_array_common_six_seals_bound
For a symmetric idempotent row-injective array A on Fin n and two distinct colors a,b, let F consist of six-element sets S excluding a,b and closed under every a-edge and b-edge. Then 6*card(F)<=n-3. The matching partner involutions are obtained by inverting rows. Every common support excludes a,b and the b-partner of a, three distinct vertices. This bounds common six-vertex supports, not all bad cuts or their joint probabilities under a partition profile.
Statement
theorem wild_normalized_array_common_six_seals_bound (n : ℕ) (A : Fin n → Fin n → Fin n) (hdiag : ∀ x, A x x = x) (hsymm : ∀ x y, A x y = A y x) (hinj : ∀ x, Function.Injective (A x)) (a b : Fin n) (hab : a ≠ b) : 6 * (((Finset.univ : Finset (Fin n)).powersetCard 6).filter fun S => a ∉ S ∧ b ∉ S ∧ ∀ x ∈ S, ∀ y, A x y = a ∨ A x y = b → y ∈ S).card ≤ n - 3
- Source
- IN-374 / OP-306, dependence estimates for the weighted partition route to https://arxiv.org/html/2610.22142v1. Elementary matching support consequence of the standard even-cycle decomposition of two disjoint perfect matchings; matching background https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/9d33772f-c7dc-409f-a4ed-521da8d87890/content . Exact experiment9362 audits six saved15 arrays and cyclic9,13,21,27,39,61. No new wild-number bound, sharpness case or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- wild_two_matchings_six_closed_family_boundA finite family F of six-element subsets of U, closed under two involutions whose actions on each member are fixed-point-free and distinct…
- Used by 1
- wild_normalized_array_six_seal_second_factorial_boundFor every normalized symmetric idempotent row-injective array on Fin n, let mu(S) count colors outside a six-set S whose matching edges…
The proof, explained
The proof bounds the size of the family F of 6-vertex common supports by reducing to wild_two_matchings_six_closed_family_bound, a known bound for two matchings on a finite universe U. Each color i defines an involutive matching f_i obtained by inverting row A(x), whose only fixed point is i. For distinct colors a and b, every support S ∈ F is closed under f_a and f_b and avoids the three distinct vertices a, b, and f_b(a). Thus all supports are contained in a universe U of size n - 3, yielding 6 * |F| ≤ n - 3.
Each row A(x, ·) is a bijection, yielding row-inverse partner functions f(i, x) such that A(x, f(i, x)) = i.
Since each row map A(x) is an injective function on the finite set Fin n, Finite.surjective_of_injective shows that it is surjective and therefore bijective (hbij). Using Equiv.ofBijective, we convert each row into a permutation e(x). For each color i and vertex x, we set f(i, x) = (e(x))⁻¹(i), so that applying A(x) to f(i, x) returns i by definition of the inverse permutation (heq).
uses
Finite.surjective_of_injective,Equiv.ofBijectiveclassical have hbij : ∀ x, Function.Bijective (A x) := fun x => ⟨hinj x, Finite.surjective_of_injective (hinj x)⟩ let e : Fin n → Equiv.Perm (Fin n) := fun x => Equiv.ofBijective (A x) (hbij x) let f : Fin n → Fin n → Fin n := fun i x => (e x).symm i have heq : ∀ i x, A x (f i x) = i := by intro i x exact (e x).apply_symm_apply i
For every color i, the map f_i is an involution whose unique fixed point is i.
To verify that f_i is involutive (hf), we show f_i(f_i(x)) = x. By definition, A(f_i(x), f_i(f_i(x))) = i, while symmetry of A gives A(f_i(x), x) = A(x, f_i(x)) = i; row-injectivity of A at f_i(x) then yields f_i(f_i(x)) = x. Next, i is a fixed point (hfix) because A(i, f_i(i)) = i = A(i, i) by idempotence, so row-injectivity at i gives f_i(i) = i. Finally, f_i has no other fixed points (hne): if f_i(x) = x, then i = A(x, f_i(x)) = A(x, x) = x, contradicting i ≠ x.
have hf : ∀ i, Function.Involutive (f i) := by intro i x apply hinj (f i x) rw [heq, hsymm, heq] have hfix : ∀ i, f i i = i := by intro i apply hinj i rw [heq, hdiag] have hne : ∀ i x, i ≠ x → f i x ≠ x := by intro i x hix hx have hh := heq i x rw [hx, hdiag] at hh exact hix hh.symm
The b-partner of a, f_b(a), is distinct from both a and b.
Because a ≠ b, we have b ≠ a, so f_b(a) ≠ a by the fixed-point property hne. If f_b(a) = b, then since f_b(b) = b, we would have f_b(a) = f_b(b); since f_b is an involution, it is injective, which would imply a = b, contradicting a ≠ b.
have hpartner_a : f b a ≠ a := hne b a hab.symm have hpartner_b : f b a ≠ b := by intro h have hh : f b a = f b b := by rw [h, hfix] exact hab ((hf b).injective hh)
The family F consists of 6-element subsets avoiding a and b, and each S ∈ F is closed under f_a and f_b.
We define F as the collection of 6-element subsets S that omit a and b and contain every neighbor y with A(x, y) ∈ {a, b} for x ∈ S, and let U = Fin n \ {a, b, f_b(a)}. Unpacking the definition gives the properties of S ∈ F (hF). For any x ∈ S, since A(x, f_a(x)) = a and A(x, f_b(x)) = b, the edge-closure condition ensures f_a(x) ∈ S and f_b(x) ∈ S using Or.inl and Or.inr (hc).
uses
Or.inl,Or.inrlet F : Finset (Finset (Fin n)) := ((univ : Finset (Fin n)).powersetCard 6).filter fun S => a ∉ S ∧ b ∉ S ∧ ∀ x ∈ S, ∀ y, A x y = a ∨ A x y = b → y ∈ S let U : Finset (Fin n) := univ \ {a, b, f b a} have hF : ∀ S ∈ F, S.card = 6 ∧ a ∉ S ∧ b ∉ S ∧ ∀ x ∈ S, ∀ y, A x y = a ∨ A x y = b → y ∈ S := by intro S hS obtain ⟨hcard, hprop⟩ := mem_filter.mp hS exact ⟨(mem_powersetCard.mp hcard).2, hprop⟩ have hc : ∀ S ∈ F, ∀ x ∈ S, f a x ∈ S ∧ f b x ∈ S := by intro S hS x hx exact ⟨(hF S hS).2.2.2 x hx _ (Or.inl (heq a x)), (hF S hS).2.2.2 x hx _ (Or.inr (heq b x))⟩
Every set S ∈ F is contained in the universe U = Fin n \ {a, b, f_b(a)}.
For any x ∈ S, x cannot be a or b by definition of F. If x = f_b(a), then closure under f_b implies f_b(f_b(a)) ∈ S. Since f_b is an involution, f_b(f_b(a)) = a, which would mean a ∈ S, contradicting a ∉ S. Therefore x ∉ {a, b, f_b(a)}, so S ⊆ U.
have hsub : ∀ S ∈ F, S ⊆ U := by intro S hS x hx apply mem_sdiff.mpr refine ⟨mem_univ _, ?_⟩ intro hm simp only [mem_insert, mem_singleton] at hm rcases hm with rfl | rfl | rfl · exact (hF S hS).2.1 hx · exact (hF S hS).2.2.1 hx · have hh := (hc S hS (f b a) hx).2 rw [hf b a] at hh exact (hF S hS).2.1 hh
On every set S ∈ F, f_a and f_b have no fixed points and never agree on any vertex.
Since every x ∈ S avoids both a and b, the fixed-point property hne implies f_a(x) ≠ x and f_b(x) ≠ x. If f_a(x) = f_b(x), applying A(x, ·) via congrArg gives a = A(x, f_a(x)) = A(x, f_b(x)) = b, contradicting a ≠ b.
uses
congrArghave hn : ∀ S ∈ F, ∀ x ∈ S, f a x ≠ x ∧ f b x ≠ x ∧ f a x ≠ f b x := by intro S hS x hx refine ⟨hne a x (by intro h; subst x; exact (hF S hS).2.1 hx), hne b x (by intro h; subst x; exact (hF S hS).2.2.1 hx), ?_⟩ intro h have hh := congrArg (A x) h rw [heq, heq] at hh exact hab hh
The two-matching bound implies 6 * |F| ≤ |U| = n - 3.
The hypotheses of wild_two_matchings_six_closed_family_bound are satisfied by f_a and f_b on F and U, yielding 6 * |F| ≤ |U|. Since a, b, and f_b(a) are pairwise distinct (using hab, hpartner_a, hpartner_b, and Ne.symm), {a, b, f_b(a)} has 3 elements. By Finset.card_sdiff_of_subset and Finset.subset_univ, |U| = n - 3. Substituting this into the bound establishes 6 * |F| ≤ n - 3.
uses
wild_two_matchings_six_closed_family_bound,Ne.symm,Finset.card_sdiff_of_subset,Finset.subset_univhave hbound := wild_two_matchings_six_closed_family_bound (f a) (f b) (hf a) (hf b) F U (fun S hS => (hF S hS).1) hsub hc hn have hthree : ({a, b, f b a} : Finset (Fin n)).card = 3 := by simp [hab, hpartner_a, hpartner_b, Ne.symm hpartner_a, Ne.symm hpartner_b] have hU : U.card = n - 3 := by dsimp [U] rw [Finset.card_sdiff_of_subset (Finset.subset_univ _)] simp [hthree] rw [hU] at hbound exact hbound
Finite.surjective_of_injective- an injective map from a finite type to itself is surjective
Equiv.ofBijective- a bijective function forms an equivalence (permutation) of its domain
Or.inl- constructs a proof of a disjunction P ∨ Q from a proof of the left disjunct P
Or.inr- constructs a proof of a disjunction P ∨ Q from a proof of the right disjunct Q
congrArg- if two arguments are equal, applying a function yields equal results: x = y → f x = f y
wild_two_matchings_six_closed_family_bound- for two fixed-point-free involutions that never agree, any family F of 6-element subsets closed under both maps within a universe U satisfies 6 * |F| ≤ |U|
Ne.symm- inequality is symmetric: if x ≠ y then y ≠ x
Finset.card_sdiff_of_subset- for a subset s ⊆ t of a finite set, the cardinality of the difference t \ s equals |t| - |s|
Finset.subset_univ- every finset in a finite type is a subset of the universal finset univ
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 Finsettheorem wild_normalized_array_common_six_seals_bound (n : ℕ) (A : Fin n → Fin n → Fin n) (hdiag : ∀ x, A x x = x) (hsymm : ∀ x y, A x y = A y x) (hinj : ∀ x, Function.Injective (A x)) (a b : Fin n) (hab : a ≠ b) : 6 * (((Finset.univ : Finset (Fin n)).powersetCard 6).filter fun S => a ∉ S ∧ b ∉ S ∧ ∀ x ∈ S, ∀ y, A x y = a ∨ A x y = b → y ∈ S).card ≤ n - 3 := by classical have hbij : ∀ x, Function.Bijective (A x) := fun x => ⟨hinj x, Finite.surjective_of_injective (hinj x)⟩ let e : Fin n → Equiv.Perm (Fin n) := fun x => Equiv.ofBijective (A x) (hbij x) let f : Fin n → Fin n → Fin n := fun i x => (e x).symm i have heq : ∀ i x, A x (f i x) = i := by intro i x exact (e x).apply_symm_apply i have hf : ∀ i, Function.Involutive (f i) := by intro i x apply hinj (f i x) rw [heq, hsymm, heq] have hfix : ∀ i, f i i = i := by intro i apply hinj i rw [heq, hdiag] have hne : ∀ i x, i ≠ x → f i x ≠ x := by intro i x hix hx have hh := heq i x rw [hx, hdiag] at hh exact hix hh.symm have hpartner_a : f b a ≠ a := hne b a hab.symm have hpartner_b : f b a ≠ b := by intro h have hh : f b a = f b b := by rw [h, hfix] exact hab ((hf b).injective hh) let F : Finset (Finset (Fin n)) := ((univ : Finset (Fin n)).powersetCard 6).filter fun S => a ∉ S ∧ b ∉ S ∧ ∀ x ∈ S, ∀ y, A x y = a ∨ A x y = b → y ∈ S let U : Finset (Fin n) := univ \ {a, b, f b a} have hF : ∀ S ∈ F, S.card = 6 ∧ a ∉ S ∧ b ∉ S ∧ ∀ x ∈ S, ∀ y, A x y = a ∨ A x y = b → y ∈ S := by intro S hS obtain ⟨hcard, hprop⟩ := mem_filter.mp hS exact ⟨(mem_powersetCard.mp hcard).2, hprop⟩ have hc : ∀ S ∈ F, ∀ x ∈ S, f a x ∈ S ∧ f b x ∈ S := by intro S hS x hx exact ⟨(hF S hS).2.2.2 x hx _ (Or.inl (heq a x)), (hF S hS).2.2.2 x hx _ (Or.inr (heq b x))⟩ have hsub : ∀ S ∈ F, S ⊆ U := by intro S hS x hx apply mem_sdiff.mpr refine ⟨mem_univ _, ?_⟩ intro hm simp only [mem_insert, mem_singleton] at hm rcases hm with rfl | rfl | rfl · exact (hF S hS).2.1 hx · exact (hF S hS).2.2.1 hx · have hh := (hc S hS (f b a) hx).2 rw [hf b a] at hh exact (hF S hS).2.1 hh have hn : ∀ S ∈ F, ∀ x ∈ S, f a x ≠ x ∧ f b x ≠ x ∧ f a x ≠ f b x := by intro S hS x hx refine ⟨hne a x (by intro h; subst x; exact (hF S hS).2.1 hx), hne b x (by intro h; subst x; exact (hF S hS).2.2.1 hx), ?_⟩ intro h have hh := congrArg (A x) h rw [heq, heq] at hh exact hab hh have hbound := wild_two_matchings_six_closed_family_bound (f a) (f b) (hf a) (hf b) F U (fun S hS => (hF S hS).1) hsub hc hn have hthree : ({a, b, f b a} : Finset (Fin n)).card = 3 := by simp [hab, hpartner_a, hpartner_b, Ne.symm hpartner_a, Ne.symm hpartner_b] have hU : U.card = n - 3 := by dsimp [U] rw [Finset.card_sdiff_of_subset (Finset.subset_univ _)] simp [hthree] rw [hU] at hbound exact hbound