AFTD Auto-Formalizing Theoretical Domains

cycle_power_alternating_paired_compression_exact_sum

theoremverified

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

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.

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

    lines 14–16

    uses cycle_power_sum_range_double, sum_congr

      intro u
      rw [cycle_power_sum_range_double]
      apply sum_congr rfl
  2. 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).

    lines 17–22

    uses mem_range.mp

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

    lines 23–27

    uses Bool.eq_false_iff.mpr

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

    lines 28–30

    uses Bool.false_and, Bool.toNat_false, add_zero

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

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