AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_pair_count_prune

theoremverified

Deleting the middle two quarters preserves each smaller dyadic pair count.

Statement

theorem cycle_power_dyadic_pair_count_prune (k j : ℕ) (hj : j ≤ k) (b : ℕ → Bool) :
    cycle_power_dyadic_pair_count (k + 2) j b =
      cycle_power_dyadic_pair_count (k + 1) j (cycle_power_dyadic_b_lift k b)
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
Built on 4
Used by 1

The proof, explained

Both dyadic pair counts are defined as sums over indices a ∈ [0, 2^j) checking whether both a and its corresponding high offset have true bits. Because j ≤ k, the index a falls entirely within the first quarter of the block and the high index falls within the last quarter, avoiding the middle two quarters that were pruned. Applying the low and high lift lemmas shows that the lifted sequence matches the original sequence at both positions, so the summands agree term by term.

  1. It suffices to show that for every a < 2^j, the corresponding summands in both pair counts are equal.

    By definition, each dyadic pair count is a sum over the index set {0, ..., 2^j - 1}. Applying `sum_congr rfl` reduces equality of the sums over the identical range to pointwise equality of their summands, and `intro a ha` fixes an arbitrary index a with ha : a ∈ range (2^j).

    lines 6–7

    uses sum_congr

      apply sum_congr rfl
      intro a ha
  2. Each pair of corresponding terms is equal, completing the proof.

    From ha, the lemma `mem_range.mp` gives a < 2^j. Because j ≤ k, the index a lies in the low region and a + 2^(k+1) - 2^j lies in the high region. Rewriting with `cycle_power_dyadic_b_lift_low` shows that the first factor of the summand evaluates to b a, and rewriting with `cycle_power_dyadic_b_lift_high` shows that the second factor evaluates to b (a + 2^(k+2) - 2^j). This makes the two summands identical.

    lines 8–9

    uses cycle_power_dyadic_b_lift_low, cycle_power_dyadic_b_lift_high, mem_range.mp

      rw [cycle_power_dyadic_b_lift_low k j a hj (mem_range.mp ha),
        cycle_power_dyadic_b_lift_high k j a hj (mem_range.mp ha)]
sum_congr
Two sums over identical finite sets are equal if their summands agree at every element of the set.
cycle_power_dyadic_b_lift_low
For j ≤ k and a < 2^j, the lifted sequence agrees with the original sequence at index a.
cycle_power_dyadic_b_lift_high
For j ≤ k and a < 2^j, the lifted sequence at offset a + 2^(k+1) - 2^j agrees with the original sequence at offset a + 2^(k+2) - 2^j.
mem_range.mp
An element of range n is strictly less than n.

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_dyadic_pair_count_prune (k j : ℕ) (hj : j ≤ k) (b : ℕ → Bool) :    cycle_power_dyadic_pair_count (k + 2) j b =      cycle_power_dyadic_pair_count (k + 1) j (cycle_power_dyadic_b_lift k b) := by  apply sum_congr rfl  intro a ha  rw [cycle_power_dyadic_b_lift_low k j a hj (mem_range.mp ha),    cycle_power_dyadic_b_lift_high k j a hj (mem_range.mp ha)]
See it in the graphDiscuss this resultChallenge it