AFTD Auto-Formalizing Theoretical Domains

op861_selector_palette_lower_bound

theoremverified

In any pair of proper standard-list selectors at positive k and threshold r, each selector uses at least k+r distinct colors.

Statement

theorem op861_selector_palette_lower_bound (k r : ℕ) (hk : 1 ≤ k) (f g : {S : Finset (Fin (2*k-1)) // S.card = k} → Fin (2*k-1)) (hf : ∀ S, f S ∈ S.val) (hg : ∀ S, g S ∈ S.val) (hfg : ∀ S T, (S.val ∩ T.val).card ≤ r → f S ≠ g T) : k+r ≤ (Finset.univ.image f).card ∧ k+r ≤ (Finset.univ.image g).card
Source
A used-palette restriction for the standard-list coloring in arXiv:2610.42094; the case of two size-six palettes at k=6, r=3 is illustrated by experiment 26970.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is established by first proving a one-sided lower bound showing that any valid selector f uses at least k + r colors, and then applying symmetry to obtain the same bound for g. To show |im(f)| ≥ k + r, we assume for contradiction that the palette P = im(f) satisfies |P| = k + s with s + 1 ≤ r. For every (s+1)-subset X ⊆ P, completing X with the complement Pᶜ yields a k-subset S(X) whose selector value f(S(X)) must lie in X ⊆ P. The set A of all such values satisfies |P \ A| ≤ s (hence |A| ≥ k), yet any k-subset T ⊆ A forces an intersection |S(X) ∩ T| = |X ∩ T| ≤ s + 1 ≤ r with f(S(X)) = g(T), contradicting the separation hypothesis.

  1. The palette P = f(univ) of selector f contains at least k colors.

    Let P be the image of f. We first show |P| ≥ k. If instead |P| < k, then the complement Pᶜ in the universe of size 2k - 1 would have cardinality at least k (via card_compl and Fintype.card_fin). Choosing a subset t ⊆ Pᶜ of size k via exists_subset_card_eq gives a valid k-set S = t. Since f is a selector, f(S) ∈ S ⊆ Pᶜ, so f(S) ∉ P. But f(S) must belong to P by definition of the image, yielding a contradiction.

    lines 8–19

    uses card_compl, Fintype.card_fin, exists_subset_card_eq, mem_image_of_mem, mem_univ, mem_compl

      set P := Finset.univ.image f
      have hk_le : k ≤ P.card := by
        by_contra! hlt
        have hcompl : k ≤ Pᶜ.card := by
          rw [card_compl, Fintype.card_fin]
          omega
        obtain ⟨t, ht_sub, ht_card⟩ := exists_subset_card_eq hcompl
        let S : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨t, ht_card⟩
        have hfS_in_compl : f S ∈ Pᶜ := ht_sub (hf S)
        have hfS_in_P : f S ∈ P := mem_image_of_mem _ (mem_univ S)
        rw [mem_compl] at hfS_in_compl
        exact hfS_in_compl hfS_in_P
  2. Assuming for contradiction that |P| < k + r, setting s = |P| - k gives s + 1 ≤ r and |Pᶜ| = k - 1 - s.

    Suppose for contradiction that |P| < k + r. Defining s = |P| - k ≥ 0, we have |P| = k + s, and the contradiction hypothesis immediately implies s + 1 ≤ r. Because P is a subset of the (2k - 1)-element universe, |P| ≤ 2k - 1 (using card_le_card, subset_univ, card_univ, and Fintype.card_fin). Consequently, the complement Pᶜ has cardinality |Pᶜ| = (2k - 1) - (k + s) = k - 1 - s.

    lines 20–30

    uses card_le_card, subset_univ, card_univ, Fintype.card_fin, card_compl

      by_contra! hlt
      set s := P.card - k
      have hPcard : P.card = k + s := by omega
      have hsr : s + 1 ≤ r := by omega
      have hPle : P.card ≤ 2 * k - 1 := by
        have h1 := card_le_card (subset_univ P)
        rw [card_univ, Fintype.card_fin] at h1
        exact h1
      have hc : Pᶜ.card = k - 1 - s := by
        rw [card_compl, Fintype.card_fin, hPcard]
        omega
  3. For every (s+1)-element subset X ⊆ P, X ∪ Pᶜ is a valid k-set S(X), and the set A of all chosen values f(S(X)) is a subset of P.

    For any X ⊆ P with |X| = s + 1, X is disjoint from Pᶜ. By card_union_eq_card_add_card, |X ∪ Pᶜ| = (s + 1) + (k - 1 - s) = k, so S(X) = X ∪ Pᶜ is a valid k-set. We define A to be the set of selector values f(S(X)) across all (s+1)-subsets X of P. Every element of A is f evaluated at some k-set, hence A ⊆ P by mem_image_of_mem and mem_univ.

    lines 31–41

    uses mem_powersetCard, card_union_eq_card_add_card, mem_image_of_mem, mem_univ

      let S_of : (X : Finset (Fin (2*k-1))) → X ∈ P.powersetCard (s + 1) →
          {S : Finset (Fin (2*k-1)) // S.card = k} := fun X hX =>
        have hX' := mem_powersetCard.mp hX
        have hdisj : Disjoint X Pᶜ := disjoint_compl_right.mono_left hX'.1
        ⟨X ∪ Pᶜ, by rw [card_union_eq_card_add_card.2 hdisj, hX'.2, hc]; omega⟩
      let A := (P.powersetCard (s + 1)).attach.image (fun ⟨X, hX⟩ => f (S_of X hX))
      have hAP : A ⊆ P := by
        intro a ha
        simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at ha
        obtain ⟨X, hX, rfl⟩ := ha
        exact mem_image_of_mem _ (mem_univ _)
  4. The set difference P \ A has cardinality at most s.

    Suppose for contradiction that |P \ A| > s, so |P \ A| ≥ s + 1. By exists_subset_card_eq, choose an (s+1)-element subset X ⊆ P \ A. Since X ⊆ P \ A ⊆ P (using sdiff_subset), X is an (s+1)-subset of P. The selector f picks f(S(X)) ∈ S(X) = X ∪ Pᶜ. Since f(S(X)) ∈ P, it cannot lie in Pᶜ (by mem_compl), so f(S(X)) ∈ X. But X ⊆ P \ A implies f(S(X)) ∉ A, which directly contradicts the fact that f(S(X)) ∈ A by definition of A.

    lines 42–63

    uses exists_subset_card_eq, sdiff_subset, mem_powersetCard, mem_union, mem_image_of_mem, mem_compl, mem_sdiff

      have hdiff : (P \ A).card ≤ s := by
        by_contra! hgt
        obtain ⟨X, hX_sub, hX_card⟩ := exists_subset_card_eq hgt
        have hXP : X ⊆ P := hX_sub.trans sdiff_subset
        have hX_mem : X ∈ P.powersetCard (s + 1) := by
          rw [mem_powersetCard]
          exact ⟨hXP, hX_card⟩
        have hf_in_X : f (S_of X hX_mem) ∈ X := by
          have h1 : f (S_of X hX_mem) ∈ (S_of X hX_mem).val := hf _
          rw [mem_union] at h1
          cases h1 with
          | inl hX_in => exact hX_in
          | inr hcompl =>
            have hP_in : f (S_of X hX_mem) ∈ P := mem_image_of_mem _ (mem_univ _)
            rw [mem_compl] at hcompl
            exact (hcompl hP_in).elim
        have hf_in_A : f (S_of X hX_mem) ∈ A := by
          simp only [A, mem_image, mem_attach, true_and, Subtype.exists]
          exact ⟨X, hX_mem, rfl⟩
        have hf_in_sdiff : f (S_of X hX_mem) ∈ P \ A := hX_sub hf_in_X
        rw [mem_sdiff] at hf_in_sdiff
        exact hf_in_sdiff.2 hf_in_A
  5. The set A has cardinality at least k.

    Since A ⊆ P, card_sdiff_add_card_eq_card gives |P \ A| + |A| = |P|. Since |P| = k + s and |P \ A| ≤ s, linear arithmetic gives |A| = |P| - |P \ A| ≥ (k + s) - s = k.

    lines 64–66

    uses card_sdiff_add_card_eq_card

      have hk_le_A : k ≤ A.card := by
        have := card_sdiff_add_card_eq_card hAP
        omega
  6. The set A must have cardinality strictly less than k, which contradicts |A| ≥ k and establishes the one-sided lower bound k + r ≤ |P|.

    Suppose |A| ≥ k. By exists_subset_card_eq, pick a k-element subset T ⊆ A ⊆ P. The selector g chooses g(T) ∈ T ⊆ A. By definition of A, there is an (s+1)-subset X ⊆ P such that f(S(X)) = g(T), where S = S(X) = X ∪ Pᶜ. Because T ⊆ P, T is disjoint from Pᶜ, so S ∩ T = (X ∪ Pᶜ) ∩ T = X ∩ T. Thus |S ∩ T| = |X ∩ T| ≤ |X| = s + 1 ≤ r (using card_le_card and inter_subset_left). But by the separation hypothesis, |S ∩ T| ≤ r implies f(S) ≠ g(T), contradicting f(S) = g(T). Hence |A| < k, and combining this with k ≤ |A| yields False via omega, completing the proof of k + r ≤ |P|.

    lines 67–94

    uses exists_subset_card_eq, mem_powersetCard, card_le_card, inter_subset_left

      have hA_lt_k : A.card < k := by
        by_contra! hge
        obtain ⟨T, hTsub, hTcard⟩ := exists_subset_card_eq hge
        have hTP : T ⊆ P := hTsub.trans hAP
        have hg_in_A : g ⟨T, hTcard⟩ ∈ A := hTsub (hg ⟨T, hTcard⟩)
        simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at hg_in_A
        obtain ⟨X, hX_mem, hf_eq⟩ := hg_in_A
        have hX' := mem_powersetCard.mp hX_mem
        let S := S_of X hX_mem
        let T_sub : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨T, hTcard⟩
        have hinter : (S.val ∩ T_sub.val) = X ∩ T := by
          dsimp [S, S_of, T_sub]
          ext x
          simp only [mem_inter, mem_union, mem_compl]
          constructor
          · rintro ⟨h1 | h2, hxT⟩
            · exact ⟨h1, hxT⟩
            · exact (h2 (hTP hxT)).elim
          · rintro ⟨hxX, hxT⟩
            exact ⟨Or.inl hxX, hxT⟩
        have hcard_inter : (S.val ∩ T_sub.val).card ≤ r := by
          rw [hinter]
          have : (X ∩ T).card ≤ X.card := card_le_card inter_subset_left
          rw [hX'.2] at this
          omega
        have hne := hfg S T_sub hcard_inter
        exact hne hf_eq
      omega
  7. Both selectors f and g each use at least k + r colors.

    The lower bound k + r ≤ |im(f)| follows directly from op861_selector_palette_lower_bound_one_side. For g, we apply the one-sided lemma with g and f swapped. The swapped separation hypothesis requires that |S ∩ T| ≤ r implies g(S) ≠ f(T); by commutativity of intersection (Finset.inter_comm), |T ∩ S| = |S ∩ T| ≤ r, so the original hypothesis gives f(T) ≠ g(S), whose symmetry yields g(S) ≠ f(T).

    lines 97–101

    uses op861_selector_palette_lower_bound_one_side, Finset.inter_comm

      refine ⟨op861_selector_palette_lower_bound_one_side k r hk f g hf hg hfg, ?_⟩
      apply op861_selector_palette_lower_bound_one_side k r hk g f hg hf
      intro S T hST
      rw [Finset.inter_comm] at hST
      exact (hfg T S hST).symm
card_compl
For a finite set s, the cardinality of its complement sᶜ is Fintype.card α - s.card.
Fintype.card_fin
The cardinality of the standard finite type Fin n is n.
exists_subset_card_eq
If n ≤ s.card, there exists a subset t ⊆ s with t.card = n.
mem_image_of_mem
If a ∈ s, then f(a) belongs to the image Finset.image f s.
mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
mem_compl
An element belongs to the complement sᶜ if and only if it does not belong to s.
card_le_card
If s ⊆ t, then s.card ≤ t.card.
subset_univ
Every finite set in a finite type is a subset of Finset.univ.
card_univ
The cardinality of Finset.univ is Fintype.card α.
mem_powersetCard
A set s belongs to the n-element powerset of t if and only if s ⊆ t and s.card = n.
card_union_eq_card_add_card
For disjoint finite sets s and t, (s ∪ t).card = s.card + t.card.
sdiff_subset
The set difference s \ t is a subset of s.
mem_union
An element belongs to s ∪ t if and only if it belongs to s or to t.
mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
card_sdiff_add_card_eq_card
If s ⊆ t, then (t \ s).card + s.card = t.card.
inter_subset_left
The intersection s₁ ∩ s₂ is a subset of s₁.
op861_selector_palette_lower_bound_one_side
Under the given hypotheses, the first selector f uses at least k + r colors.
Finset.inter_comm
Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.

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 Finset intheorem op861_selector_palette_lower_bound_one_side (k r : ℕ) (hk : 1 ≤ k)    (f g : {S : Finset (Fin (2*k-1)) // S.card = k} → Fin (2*k-1))    (hf : ∀ S, f S ∈ S.val)    (hg : ∀ S, g S ∈ S.val)    (hfg : ∀ S T, (S.val ∩ T.val).card ≤ r → f S ≠ g T) :    k + r ≤ (Finset.univ.image f).card := by  set P := Finset.univ.image f  have hk_le : k ≤ P.card := by    by_contra! hlt    have hcompl : k ≤ Pᶜ.card := by      rw [card_compl, Fintype.card_fin]      omega    obtain ⟨t, ht_sub, ht_card⟩ := exists_subset_card_eq hcompl    let S : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨t, ht_card⟩    have hfS_in_compl : f S ∈ Pᶜ := ht_sub (hf S)    have hfS_in_P : f S ∈ P := mem_image_of_mem _ (mem_univ S)    rw [mem_compl] at hfS_in_compl    exact hfS_in_compl hfS_in_P  by_contra! hlt  set s := P.card - k  have hPcard : P.card = k + s := by omega  have hsr : s + 1 ≤ r := by omega  have hPle : P.card ≤ 2 * k - 1 := by    have h1 := card_le_card (subset_univ P)    rw [card_univ, Fintype.card_fin] at h1    exact h1  have hc : Pᶜ.card = k - 1 - s := by    rw [card_compl, Fintype.card_fin, hPcard]    omega  let S_of : (X : Finset (Fin (2*k-1))) → X ∈ P.powersetCard (s + 1) →      {S : Finset (Fin (2*k-1)) // S.card = k} := fun X hX =>    have hX' := mem_powersetCard.mp hX    have hdisj : Disjoint X Pᶜ := disjoint_compl_right.mono_left hX'.1    ⟨X ∪ Pᶜ, by rw [card_union_eq_card_add_card.2 hdisj, hX'.2, hc]; omega⟩  let A := (P.powersetCard (s + 1)).attach.image (fun ⟨X, hX⟩ => f (S_of X hX))  have hAP : A ⊆ P := by    intro a ha    simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at ha    obtain ⟨X, hX, rfl⟩ := ha    exact mem_image_of_mem _ (mem_univ _)  have hdiff : (P \ A).card ≤ s := by    by_contra! hgt    obtain ⟨X, hX_sub, hX_card⟩ := exists_subset_card_eq hgt    have hXP : X ⊆ P := hX_sub.trans sdiff_subset    have hX_mem : X ∈ P.powersetCard (s + 1) := by      rw [mem_powersetCard]      exact ⟨hXP, hX_card⟩    have hf_in_X : f (S_of X hX_mem) ∈ X := by      have h1 : f (S_of X hX_mem) ∈ (S_of X hX_mem).val := hf _      rw [mem_union] at h1      cases h1 with      | inl hX_in => exact hX_in      | inr hcompl =>        have hP_in : f (S_of X hX_mem) ∈ P := mem_image_of_mem _ (mem_univ _)        rw [mem_compl] at hcompl        exact (hcompl hP_in).elim    have hf_in_A : f (S_of X hX_mem) ∈ A := by      simp only [A, mem_image, mem_attach, true_and, Subtype.exists]      exact ⟨X, hX_mem, rfl⟩    have hf_in_sdiff : f (S_of X hX_mem) ∈ P \ A := hX_sub hf_in_X    rw [mem_sdiff] at hf_in_sdiff    exact hf_in_sdiff.2 hf_in_A  have hk_le_A : k ≤ A.card := by    have := card_sdiff_add_card_eq_card hAP    omega  have hA_lt_k : A.card < k := by    by_contra! hge    obtain ⟨T, hTsub, hTcard⟩ := exists_subset_card_eq hge    have hTP : T ⊆ P := hTsub.trans hAP    have hg_in_A : g ⟨T, hTcard⟩ ∈ A := hTsub (hg ⟨T, hTcard⟩)    simp only [A, mem_image, mem_attach, true_and, Subtype.exists] at hg_in_A    obtain ⟨X, hX_mem, hf_eq⟩ := hg_in_A    have hX' := mem_powersetCard.mp hX_mem    let S := S_of X hX_mem    let T_sub : {S : Finset (Fin (2*k-1)) // S.card = k} := ⟨T, hTcard⟩    have hinter : (S.val ∩ T_sub.val) = X ∩ T := by      dsimp [S, S_of, T_sub]      ext x      simp only [mem_inter, mem_union, mem_compl]      constructor      · rintro ⟨h1 | h2, hxT⟩        · exact ⟨h1, hxT⟩        · exact (h2 (hTP hxT)).elim      · rintro ⟨hxX, hxT⟩        exact ⟨Or.inl hxX, hxT⟩    have hcard_inter : (S.val ∩ T_sub.val).card ≤ r := by      rw [hinter]      have : (X ∩ T).card ≤ X.card := card_le_card inter_subset_left      rw [hX'.2] at this      omega    have hne := hfg S T_sub hcard_inter    exact hne hf_eq  omegatheorem op861_selector_palette_lower_bound (k r : ℕ) (hk : 1 ≤ k) (f g : {S : Finset (Fin (2*k-1)) // S.card = k} → Fin (2*k-1)) (hf : ∀ S, f S ∈ S.val) (hg : ∀ S, g S ∈ S.val) (hfg : ∀ S T, (S.val ∩ T.val).card ≤ r → f S ≠ g T) : k+r ≤ (Finset.univ.image f).card ∧ k+r ≤ (Finset.univ.image g).card := by  refine ⟨op861_selector_palette_lower_bound_one_side k r hk f g hf hg hfg, ?_⟩  apply op861_selector_palette_lower_bound_one_side k r hk g f hg hf  intro S T hST  rw [Finset.inter_comm] at hST  exact (hfg T S hST).symm
See it in the graphDiscuss this resultChallenge it