cycle_power_alternating_paired_compression_count
At every odd vertex, when all even-start classes consist exactly of their two endpoints, the original active count is one plus the count after retaining odd-start classes and halving the even ages. This identity does not need the consecutive-bit-pairing assumption.
Statement
theorem cycle_power_alternating_paired_compression_count (h : ℕ) (hh : 0 < h) (x : ℤ → ℕ → Bool) (heven : ∀ p : ℤ, ∀ j < 2 * h, x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1) : ∀ u : ℤ, (range (2 * h)).sum (fun j => (x (2 * u + 1 - (j : ℤ)) j).toNat) = 1 + (range h).sum (fun j => (x (2 * (u - (j : ℤ)) + 1) (2 * j)).toNat)
- Source
- Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635, Section 3. These conditional class-system and pruning lemmas do not establish the unresolved graph covering bound. The earlier fixed-radius helpers handle radii eight and sixteen; this session works with arbitrary dyadic radii. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cycle_power_sum_range_doubleA sum over the first 2n indices equals the sum over n consecutive even-odd pairs.
- Used by 1
- cycle_power_dyadic_no_island_of_alternating_pairedUniform induction step for the no-island class shape. Let m ≥ 1 and suppose every tight, exactly dyadically covered, fully ordinarily…
The proof, explained
To compute the active count at an odd vertex 2u + 1, the sum over all 2h ages is split into even ages 2j and odd ages 2j + 1 for j ∈ {0, ..., h - 1}. For even ages 2j, the start vertex simplifies to 2(u - j) + 1, matching the compressed sum term by term. For odd ages 2j + 1, the start vertex is even, so the hypothesis on even-start classes implies that the entry is false everywhere except at the single upper boundary age j = h - 1 (age 2h - 1), where it is true and contributes 1. Combining the two parts yields the compressed count plus 1.
For any vertex u, the active count sum over all 2h ages decomposes into the sum of even-age terms plus the sum of odd-age terms over range h.
We introduce the integer vertex u. Using `cycle_power_sum_range_double`, the sum over {0, ..., 2h - 1} is grouped into pairs of consecutive even and odd indices 2j and 2j + 1. Then `sum_add_distrib` splits this into two separate sums over j ∈ {0, ..., h - 1}.
uses
cycle_power_sum_range_double,sum_add_distribintro u rw [cycle_power_sum_range_double, sum_add_distrib]
The sum of the even-age terms equals the compressed sum ∑ j < h, x(2(u - j) + 1, 2j).
For each j, the first coordinate 2u + 1 - 2j simplifies algebraically to 2(u - j) + 1 by basic ring arithmetic. Applying `sum_congr` replaces the summand across the entire range, establishing hypothesis `hleft`, which is then rewritten into the goal.
uses
sum_congrhave hleft : (range h).sum (fun j => (x (2 * u + 1 - ((2 * j : ℕ) : ℤ)) (2 * j)).toNat) = (range h).sum (fun j => (x (2 * (u - (j : ℤ)) + 1) (2 * j)).toNat) := by apply sum_congr rfl intro j hj congr 2 push_cast ring rw [hleft]
In the sum of the odd-age terms, the term at index j = h - 1 evaluates to 1.
Applying `sum_eq_single` isolates the single index j = h - 1. At this index, the start position 2u + 1 - (2(h - 1) + 1) simplifies to the even integer 2(u - (h - 1)), and the age is 2(h - 1) + 1 = 2h - 1. Because 2h - 1 < 2h and matches the upper endpoint in `heven`, x evaluates to true, contributing 1 to the sum.
uses
sum_eq_single,Or.inrhave hodd : (range h).sum (fun j => (x (2 * u + 1 - ((2 * j + 1 : ℕ) : ℤ)) (2 * j + 1)).toNat) = 1 := by rw [sum_eq_single (h - 1)] · have he : 2 * u + 1 - ((2 * (h - 1) + 1 : ℕ) : ℤ) = 2 * (u - ((h - 1 : ℕ) : ℤ)) := by push_cast; ring have hi : 2 * (h - 1) + 1 < 2 * h := by omega rw [he, (heven _ _ hi).mpr (Or.inr (by omega))] rfl
Every other odd-age term with j ≠ h - 1 evaluates to 0.
For any j < h with j ≠ h - 1, the start position 2u + 1 - (2j + 1) is the even integer 2(u - j). By hypothesis `heven`, x at an even start position and age 2j + 1 < 2h can only be true if 2j + 1 = 0 or 2j + 1 = 2h - 1. But 2j + 1 is odd (hence never 0) and j ≠ h - 1 ensures 2j + 1 ≠ 2h - 1. Thus x must be false by `Bool.eq_false_iff.mpr`, contributing 0 to the sum.
uses
Bool.eq_false_iff.mpr· intro j hj hne have hi : j < h := mem_range.mp hj have he : 2 * u + 1 - ((2 * j + 1 : ℕ) : ℤ) = 2 * (u - (j : ℤ)) := by push_cast; ring rw [he] have hfalse : x (2 * (u - (j : ℤ))) (2 * j + 1) = false := by apply Bool.eq_false_iff.mpr intro ht have := (heven _ _ (by omega)).mp ht omega rw [hfalse] rfl
The isolated index h - 1 belongs to the range {0, ..., h - 1}.
Since h > 0, we have h - 1 < h, so h - 1 is indeed in `range h`. If it were not, a contradiction would follow via `False.elim`.
uses
False.elim· intro hnot exact False.elim (hnot (mem_range.mpr (by omega)))
The total active count is 1 plus the compressed count.
With the even sum replaced by the compressed sum and the odd sum shown to equal 1, the remaining goal is S + 1 = 1 + S, which is closed by linear arithmetic (`omega`).
omega
cycle_power_sum_range_double- A sum of a sequence over the first 2n natural numbers equals the sum over n of the paired even and odd terms f(2i) + f(2i + 1).
sum_add_distrib- The sum of a sum of functions f(x) + g(x) over a finite set distributes into the sum of f plus the sum of g.
sum_congr- If two finite sets are equal and two summands agree pointwise on that set, their sums are equal.
sum_eq_single- If all terms in a finite sum vanish except possibly at a single index a, then the sum equals the value of the summand at a.
Or.inr- A proof of the right disjunct b proves the disjunction a ∨ b.
Bool.eq_false_iff.mpr- A boolean value that is not true must equal false.
False.elim- From a contradiction (a proof of False), any goal follows (the principle of explosion).
- Several linear arithmetic subgoals (such as boundary inequalities and the final equality S + 1 = 1 + S) are closed automatically by `omega`.
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_alternating_paired_compression_count (h : ℕ) (hh : 0 < h) (x : ℤ → ℕ → Bool) (heven : ∀ p : ℤ, ∀ j < 2 * h, x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1) : ∀ u : ℤ, (range (2 * h)).sum (fun j => (x (2 * u + 1 - (j : ℤ)) j).toNat) = 1 + (range h).sum (fun j => (x (2 * (u - (j : ℤ)) + 1) (2 * j)).toNat) := by intro u rw [cycle_power_sum_range_double, sum_add_distrib] have hleft : (range h).sum (fun j => (x (2 * u + 1 - ((2 * j : ℕ) : ℤ)) (2 * j)).toNat) = (range h).sum (fun j => (x (2 * (u - (j : ℤ)) + 1) (2 * j)).toNat) := by apply sum_congr rfl intro j hj congr 2 push_cast ring rw [hleft] have hodd : (range h).sum (fun j => (x (2 * u + 1 - ((2 * j + 1 : ℕ) : ℤ)) (2 * j + 1)).toNat) = 1 := by rw [sum_eq_single (h - 1)] · have he : 2 * u + 1 - ((2 * (h - 1) + 1 : ℕ) : ℤ) = 2 * (u - ((h - 1 : ℕ) : ℤ)) := by push_cast; ring have hi : 2 * (h - 1) + 1 < 2 * h := by omega rw [he, (heven _ _ hi).mpr (Or.inr (by omega))] rfl · intro j hj hne have hi : j < h := mem_range.mp hj have he : 2 * u + 1 - ((2 * j + 1 : ℕ) : ℤ) = 2 * (u - (j : ℤ)) := by push_cast; ring rw [he] have hfalse : x (2 * (u - (j : ℤ))) (2 * j + 1) = false := by apply Bool.eq_false_iff.mpr intro ht have := (heven _ _ (by omega)).mp ht omega rw [hfalse] rfl · intro hnot exact False.elim (hnot (mem_range.mpr (by omega))) omega