cycle_power_alternating_paired_compression_exact_sum
For a positive distance d and s+d at most h, the original sum over 2s possible witnesses for distance 2d at an odd vertex equals the compressed sum over s witnesses for distance d, provided all even-start classes are endpoint-only.
Statement
theorem cycle_power_alternating_paired_compression_exact_sum (h d s : ℕ) (hd : 0 < d) (hds : s + d ≤ h) (x : ℤ → ℕ → Bool) (heven : ∀ p : ℤ, ∀ j < 2 * h, x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1) : ∀ u : ℤ, (range (2 * s)).sum (fun a => (x (2 * u + 1 - (a : ℤ)) a && x (2 * u + 1 - (a : ℤ)) (a + 2 * d)).toNat) = (range s).sum (fun a => (x (2 * (u - (a : ℤ)) + 1) (2 * a) && x (2 * (u - (a : ℤ)) + 1) (2 * (a + d))).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
The proof groups the sum over 2s candidates into s adjacent pairs (2a and 2a + 1) using cycle_power_sum_range_double. For each pair, the odd term 2a + 1 falls on an even row 2(u - a), where the endpoint-only hypothesis forces the indicator to evaluate to false (zero) because the column index lies strictly between the boundary endpoints 0 and 2h - 1. The surviving even term 2a lies on an odd row and matches the summand of the compressed sum over s candidates.
The sum over 2s witnesses reduces to showing that each paired sum of the 2a-th and (2a+1)-th terms equals the corresponding compressed summand for every a < s.
We fix an arbitrary vertex shift u. The lemma cycle_power_sum_range_double groups the sum over 2s into a sum over s pairs of adjacent terms, f(2a) + f(2a+1). Applying sum_congr reduces the equality of the two sums to checking that each paired summand matches the compressed summand for each index a in the range.
uses
cycle_power_sum_range_double,sum_congrintro u rw [cycle_power_sum_range_double] apply sum_congr rfl
For each index a < s, the row indices simplify to 2(u - a) + 1 for the even index 2a, and to the even integer 2(u - a) for the odd index 2a + 1.
Fix a in range s, so a < s by mem_range.mp. Elementary ring arithmetic shows that 2u + 1 - 2a = 2(u - a) + 1 (an odd row) and 2u + 1 - (2a + 1) = 2(u - a) (an even row).
uses
mem_range.mpintro a ha have hal : a < s := mem_range.mp ha have hevenstart : 2 * u + 1 - ((2 * a : ℕ) : ℤ) = 2 * (u - (a : ℤ)) + 1 := by push_cast; ring have hoddstart : 2 * u + 1 - ((2 * a + 1 : ℕ) : ℤ) = 2 * (u - (a : ℤ)) := by push_cast; ring
The odd summand vanishes because its first factor evaluates to false: x(2(u - a), 2a + 1) = false.
By Bool.eq_false_iff.mpr, it suffices to derive a contradiction from assuming x(2(u - a), 2a + 1) = true. Because the row index 2(u - a) is even, hypothesis heven requires the column index 2a + 1 to be either 0 or 2h - 1 (since 2a + 1 < 2h). But from a < s, s + d ≤ h, and d > 0, linear arithmetic establishes that 0 < 2a + 1 < 2h - 1, ruling out both endpoints.
uses
Bool.eq_false_iff.mprhave hfalse : x (2 * (u - (a : ℤ))) (2 * a + 1) = false := by apply Bool.eq_false_iff.mpr intro ht have := (heven _ _ (by omega)).mp ht omega
Each paired summand equals the compressed summand, concluding the proof.
Substituting the simplified row indices and the fact that the odd factor is false reduces the odd term to false && ..., which evaluates to 0. Factoring 2a + 2d as 2(a + d), the remaining even term matches the summand of the compressed sum.
uses
Bool.false_and,Bool.toNat_false,add_zerorw [hevenstart, hoddstart, hfalse] have hi : 2 * a + 2 * d = 2 * (a + d) := by omega simp only [Bool.false_and, Bool.toNat_false, add_zero, hi]
cycle_power_sum_range_double- a sum over the first 2n natural numbers can be rewritten as a sum over n of adjacent pairs f(2i) + f(2i+1)
sum_congr- two sums over finite sets are equal if the index sets are equal and their summands agree on every element
mem_range.mp- an element belongs to Finset.range n if and only if it is strictly less than n (forward direction: m ∈ range n implies m < n)
Bool.eq_false_iff.mpr- a boolean value is false if it is not equal to true
Bool.false_and- the boolean conjunction of false and any boolean value is false
Bool.toNat_false- the natural number associated with the boolean false is 0
add_zero- adding zero to any element leaves it unchanged
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_exact_sum (h d s : ℕ) (hd : 0 < d) (hds : s + d ≤ h) (x : ℤ → ℕ → Bool) (heven : ∀ p : ℤ, ∀ j < 2 * h, x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1) : ∀ u : ℤ, (range (2 * s)).sum (fun a => (x (2 * u + 1 - (a : ℤ)) a && x (2 * u + 1 - (a : ℤ)) (a + 2 * d)).toNat) = (range s).sum (fun a => (x (2 * (u - (a : ℤ)) + 1) (2 * a) && x (2 * (u - (a : ℤ)) + 1) (2 * (a + d))).toNat) := by intro u rw [cycle_power_sum_range_double] apply sum_congr rfl intro a ha have hal : a < s := mem_range.mp ha have hevenstart : 2 * u + 1 - ((2 * a : ℕ) : ℤ) = 2 * (u - (a : ℤ)) + 1 := by push_cast; ring have hoddstart : 2 * u + 1 - ((2 * a + 1 : ℕ) : ℤ) = 2 * (u - (a : ℤ)) := by push_cast; ring have hfalse : x (2 * (u - (a : ℤ))) (2 * a + 1) = false := by apply Bool.eq_false_iff.mpr intro ht have := (heven _ _ (by omega)).mp ht omega rw [hevenstart, hoddstart, hfalse] have hi : 2 * a + 2 * d = 2 * (a + d) := by omega simp only [Bool.false_and, Bool.toNat_false, add_zero, hi]