AFTD Auto-Formalizing Theoretical Domains

cycle_power_class_palette_of_count

theoremverified

Exactly t active classes with distinct labels in Fin t use every label at each vertex.

Statement

theorem cycle_power_class_palette_of_count
    (D t : ℕ) (x : ℤ → ℕ → Bool) (ell : ℤ → Fin t)
    (hcount : ∀ v : ℤ, (range D).sum
      (fun a => (x (v-(a : ℤ)) a).toNat) = t)
    (hsep : ∀ (v : ℤ) (a b : ℕ), a < D → b < D → a ≠ b →
      x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true →
        ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ))) :
    ∀ (v : ℤ) (s : Fin t), ∃ a : ℕ, a < D ∧
      x (v-(a : ℤ)) a = true ∧ ell (v-(a : ℤ)) = s
Source
Uniform helpers for OP-205 / RT-1 following arXiv:2610.15635, Section 3. The neighbour-weight induction and central occurrence are class-model helpers; they do not prove the unresolved covering number. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To show that every label s ∈ Fin t is attained at a given vertex v, we consider the set A of offsets a < D where the indicator x(v - a, a) is true. The counting hypothesis ensures that A has size t, and the separation hypothesis ensures that the labeling map a ↦ ell(v - a) is injective on A. Because the target Fin t also has cardinality t, any injective map from A into Fin t is necessarily surjective by the pigeonhole principle. Hence, the target label s is achieved by some active offset a < D.

  1. Fix an arbitrary vertex v ∈ ℤ and label s ∈ Fin t, and define A to be the set of offsets a < D where x(v - a, a) is true.

    We assume classical logic, fix the vertex v and target label s, and define the finite set A ⊆ {0, …, D-1} by filtering Finset.range D with the condition x(v - a, a) = true.

    lines 12–14

      classical
      intro v s
      let A := (range D).filter (fun (a : ℕ) => x (v-(a : ℤ)) a = true)
  2. The set A has cardinality t.

    By the hypothesis hcount, the sum over a ∈ {0, …, D-1} of (x(v - a, a)).toNat is equal to t. By card_eq_sum_ones and sum_filter, the cardinality of A equals the sum over a < D of (if x(v - a, a) = true then 1 else 0). A case split on the boolean value of x(v - a, a) shows that this conditional equals (x(v - a, a)).toNat in both cases (1 when true and 0 when false), so by sum_congr the two sums coincide, yielding |A| = t.

    lines 15–21

    uses card_eq_sum_ones, sum_filter, sum_congr

      have hc : A.card = t := by
        rw [← hcount v]
        dsimp [A]
        rw [card_eq_sum_ones, sum_filter]
        apply sum_congr rfl
        intro a ha
        cases hx : x (v-(a : ℤ)) a <;> simp [hx]
  3. The assignment a ↦ ell(v - a) is injective on A.

    Take two elements a, b ∈ A such that ell(v - a) = ell(v - b). Since both belong to A, they satisfy a < D and b < D with x(v - a, a) = true and x(v - b, b) = true. If a ≠ b, the separation hypothesis hsep would imply ell(v - a) ≠ ell(v - b), which contradicts the assumed equality. Therefore, a = b.

    lines 22–31

    uses mem_filter, mem_range

      have hinj : Set.InjOn (fun a : ℕ => ell (v-(a : ℤ))) (A : Set ℕ) := by
        intro a ha b hb hab
        change a ∈ A at ha
        change b ∈ A at hb
        have ha' : a < D ∧ x (v-(a : ℤ)) a = true := by
          simpa only [A, mem_filter, mem_range] using ha
        have hb' : b < D ∧ x (v-(b : ℤ)) b = true := by
          simpa only [A, mem_filter, mem_range] using hb
        by_contra hne
        exact hsep v a b ha'.1 hb'.1 hne ha'.2 hb'.2 hab
  4. The image of A under a ↦ ell(v - a) is the entire set Fin t, and in particular contains s.

    Because the map is injective on A, card_image_of_injOn implies that its image has cardinality |A| = t. Since the target type Fin t has total cardinality t, eq_univ_of_card shows that this image is the universal set Finset.univ. Thus, any label s ∈ Fin t belongs to the image.

    lines 32–36

    uses card_image_of_injOn, eq_univ_of_card

      have hi : (A.image (fun a : ℕ => ell (v-(a : ℤ)))).card = t := by
        rw [card_image_of_injOn hinj, hc]
      have hu : A.image (fun a : ℕ => ell (v-(a : ℤ))) = univ :=
        eq_univ_of_card _ (by simpa using hi)
      have hs : s ∈ A.image (fun a : ℕ => ell (v-(a : ℤ))) := by rw [hu]; simp
  5. There exists an offset a < D such that x(v - a, a) = true and ell(v - a) = s.

    Because s is in the image of A, there is some a ∈ A such that ell(v - a) = s. Unfolding the definition of A reveals that a < D and x(v - a, a) = true, providing the required witness a.

    lines 37–40

    uses mem_filter, mem_range

      obtain ⟨a, ha, he⟩ := mem_image.mp hs
      have ha' : a < D ∧ x (v-(a : ℤ)) a = true := by
        simpa only [A, mem_filter, mem_range] using ha
      exact ⟨a, ha'.1, ha'.2, he⟩
card_eq_sum_ones
The cardinality of a finite set s equals the sum of 1 over all elements of s.
sum_filter
The sum of a function over elements of a finite set satisfying a predicate equals the sum over the whole set of that function if the predicate holds and 0 otherwise.
sum_congr
Two sums over finite sets are equal if the sets of summation are equal and their summands agree at every element.
mem_filter
An element belongs to the filtered subset of a finite set if and only if it belongs to the set and satisfies the filtering predicate.
mem_range
A natural number m belongs to range n if and only if m < n.
card_image_of_injOn
If a function is injective on a finite set, the cardinality of its image equals the cardinality of the set.
eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the type is the entire universal set.

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 cycle_power_class_palette_of_count    (D t : ℕ) (x : ℤ → ℕ → Bool) (ell : ℤ → Fin t)    (hcount : ∀ v : ℤ, (range D).sum      (fun a => (x (v-(a : ℤ)) a).toNat) = t)    (hsep : ∀ (v : ℤ) (a b : ℕ), a < D → b < D → a ≠ b →      x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true →        ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ))) :    ∀ (v : ℤ) (s : Fin t), ∃ a : ℕ, a < D ∧      x (v-(a : ℤ)) a = true ∧ ell (v-(a : ℤ)) = s := by  classical  intro v s  let A := (range D).filter (fun (a : ℕ) => x (v-(a : ℤ)) a = true)  have hc : A.card = t := by    rw [← hcount v]    dsimp [A]    rw [card_eq_sum_ones, sum_filter]    apply sum_congr rfl    intro a ha    cases hx : x (v-(a : ℤ)) a <;> simp [hx]  have hinj : Set.InjOn (fun a : ℕ => ell (v-(a : ℤ))) (A : Set ℕ) := by    intro a ha b hb hab    change a ∈ A at ha    change b ∈ A at hb    have ha' : a < D ∧ x (v-(a : ℤ)) a = true := by      simpa only [A, mem_filter, mem_range] using ha    have hb' : b < D ∧ x (v-(b : ℤ)) b = true := by      simpa only [A, mem_filter, mem_range] using hb    by_contra hne    exact hsep v a b ha'.1 hb'.1 hne ha'.2 hb'.2 hab  have hi : (A.image (fun a : ℕ => ell (v-(a : ℤ)))).card = t := by    rw [card_image_of_injOn hinj, hc]  have hu : A.image (fun a : ℕ => ell (v-(a : ℤ))) = univ :=    eq_univ_of_card _ (by simpa using hi)  have hs : s ∈ A.image (fun a : ℕ => ell (v-(a : ℤ))) := by rw [hu]; simp  obtain ⟨a, ha, he⟩ := mem_image.mp hs  have ha' : a < D ∧ x (v-(a : ℤ)) a = true := by    simpa only [A, mem_filter, mem_range] using ha  exact ⟨a, ha'.1, ha'.2, he⟩
See it in the graphDiscuss this resultChallenge it