cycle_power_class_palette_of_count
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
- cycle_power_class_label_period_of_bounded_endpoint_overlapFor bounded Boolean classes with complete distinct palettes, endpoint overlap forces the root labels to repeat after the class radius.
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.
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.
classical intro v s let A := (range D).filter (fun (a : ℕ) => x (v-(a : ℤ)) a = true)
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.
uses
card_eq_sum_ones,sum_filter,sum_congrhave 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]
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.
uses
mem_filter,mem_rangehave 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
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.
uses
card_image_of_injOn,eq_univ_of_cardhave 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
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.
uses
mem_filter,mem_rangeobtain ⟨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.
- The cardinality equality |A| = t in lines 15–21 is formally verified by rewriting the cardinality into a sum of ones (using card_eq_sum_ones) and matching terms with the indicator sum from hcount.
- The surjectivity argument in lines 34–35 uses eq_univ_of_card, which deduces that a subset of Fin t of size t must be the universal set Finset.univ, implicitly evaluating Fintype.card (Fin t) = t via automation.
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 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⟩