cycle_power_dyadic_pair_count_prune
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
- cycle_power_dyadic_pair_countThe finite dyadic pair sum. For ranks j at most m, it counts selected pairs at distance 2^m minus 2^j in the dyadic arc.
- cycle_power_dyadic_b_lift_lowMiddle-quarter pruning preserves every smaller-scale left position.
- cycle_power_dyadic_b_lift_highMiddle-quarter pruning maps every smaller-scale right endpoint to its original larger-scale position.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- Used by 1
- cycle_power_dyadic_neighbour_weight_boundA tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a…
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.
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).
uses
sum_congrapply sum_congr rfl intro a ha
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.
uses
cycle_power_dyadic_b_lift_low,cycle_power_dyadic_b_lift_high,mem_range.mprw [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
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_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)]