AFTD Auto-Formalizing Theoretical Domains

cycle_power_alternating_paired_compression_count

theoremverified

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
Used by 1

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.

  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}.

    lines 10–11

    uses cycle_power_sum_range_double, sum_add_distrib

      intro u
      rw [cycle_power_sum_range_double, sum_add_distrib]
  2. 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.

    lines 12–20

    uses sum_congr

      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]
  3. 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.

    lines 21–28

    uses sum_eq_single, Or.inr

      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
  4. 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.

    lines 29–40

    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
  5. 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`.

    lines 41–42

    uses False.elim

        · intro hnot
          exact False.elim (hnot (mem_range.mpr (by omega)))
  6. 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`).

    line 43

      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).

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_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
See it in the graphDiscuss this resultChallenge it