AFTD Auto-Formalizing Theoretical Domains

wild_normalized_array_common_six_seals_bound

theoremverified

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
Used by 1

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.

  1. 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).

    lines 11–18

    uses Finite.surjective_of_injective, Equiv.ofBijective

      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
  2. 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.

    lines 19–31

      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
  3. 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.

    lines 32–36

      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)
  4. 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).

    lines 37–50

    uses Or.inl, Or.inr

      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))⟩
  5. 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.

    lines 51–62

      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
  6. 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.

    lines 63–71

    uses congrArg

      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
  7. 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.

    lines 72–81

    uses wild_two_matchings_six_closed_family_bound, Ne.symm, Finset.card_sdiff_of_subset, Finset.subset_univ

      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
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

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
See it in the graphDiscuss this resultChallenge it