cycle_power_dyadic_neighbour_pair_count_prune_top
At the boundary rank of middle-quarter pruning, the neighbour pair count changes by exactly four boundary bits.
Statement
theorem cycle_power_dyadic_neighbour_pair_count_prune_top
(k : ℕ) (b : ℕ → Bool) (hroot : b 0 = true ∧ b (2 ^ (k + 2) - 1) = true) :
cycle_power_dyadic_neighbour_pair_count (k + 2) k b +
(b (2 ^ k - 1)).toNat + (b (3 * 2 ^ k)).toNat =
cycle_power_dyadic_neighbour_pair_count (k + 1) k (cycle_power_dyadic_b_lift k b) +
(b (3 * 2 ^ k - 1)).toNat + (b (2 ^ k)).toNat- 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 2
- cycle_power_dyadic_neighbour_pair_countThe finite neighbour pair sum. For ranks j strictly below m, it counts selected pairs at distance 2^m minus 2^j minus one in the dyadic arc.
- 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
Letting q = 2^k, both neighbour pair sums range over indices a ∈ [0, q] and are split into their initial term (a = 0), their final term (a = q), and the interior sum (a ∈ [1, q - 1]). For all interior terms, the definition of the pruning lift shifts indices in such a way that the lifted summand exactly equals the original summand, making the two interior sums coincide. Evaluating the lifted bits at the boundaries using the root hypotheses b(0) = true and b(4*q - 1) = true shows that both sides reduce to the interior sum plus the exact same four boundary bits, establishing the identity.
Setting q = 2^k, we have q > 0, 2^(k+1) = 2*q, 2^(k+2) = 4*q, b(0) = true, and b(4*q - 1) = true.
We introduce the block size q = 2^k, establish the powers of 2 in terms of q by exponent induction, and extract the boundary root conditions b(0) = true and b(4*q - 1) = true from the hypothesis hroot.
uses
Nat.two_pow_pos,pow_succlet q := 2 ^ k have hq : 0 < q := Nat.two_pow_pos k have hH : 2 ^ (k + 1) = 2 * q := by dsimp [q]; rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 4 * q := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega have hr0 : b 0 = true := hroot.1 have hr1 : b (4 * q - 1) = true := by simpa only [hD] using hroot.2
For any sequence f, the sum over range (q + 1) splits into the initial term f(0), the interior sum over a ∈ range (q - 1) of f(a + 1), and the final term f(q).
We decompose the sum over range (q + 1) by peeling off the last element q via sum_range_succ and then peeling off the initial element 0 via sum_range_succ', leaving the interior sum over a + 1 for a < q - 1.
uses
sum_range_succ,sum_range_succ'have hsplit (f : ℕ → ℕ) : (range (q + 1)).sum f = f 0 + (range (q - 1)).sum (fun a => f (a+1)) + f q := by have hqr : q + 1 = (q - 1 + 1) + 1 := by omega rw [hqr, sum_range_succ, sum_range_succ'] rw [show q-1+1=q by omega] omega
For every interior index a < q - 1, the lifted summand equals the original summand.
For a + 1 with a < q - 1, we have 1 ≤ a + 1 < q, so the lift condition a + 1 < q is satisfied and the first factor evaluates to b(a + 1). The paired index (a + 1) + 2*q - q - 1 = a + q satisfies ¬(a + q < q), so by definition of the lift it shifts by 2^(k+1) = 2*q, giving b(a + q + 2*q) = b(a + 3*q), which matches the original paired index (a + 1) + 4*q - q - 1 = a + 3*q.
uses
if_pos,if_neghave hb : ∀ a < q - 1, (cycle_power_dyadic_b_lift k b (a+1) && cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat = (b (a+1) && b (a+1+4*q-q-1)).toNat := by intro a ha dsimp [cycle_power_dyadic_b_lift] rw [if_pos (by dsimp [q] at *; omega), if_neg (by dsimp [q] at *; omega)] congr 2; congr 1; omega
Unfolding neighbour pair counts and decomposing both sums isolates the boundary terms from the interior sums.
We unfold the definition of cycle_power_dyadic_neighbour_pair_count, replace 2^k by q, 2^(k+1) by 2*q, and 2^(k+2) by 4*q, and apply the splitting lemma hsplit to both sides.
unfold cycle_power_dyadic_neighbour_pair_count rw [show 2^k=q from rfl, hD, hH, hsplit, hsplit]
The interior sums on both sides are identical and can be equated.
By sum_congr and lemma hb, since each interior term in the lifted sum equals the corresponding term in the unlifted sum, the two interior sums are equal and simplify against each other.
uses
sum_congr,mem_range.mphave hmid : (range (q-1)).sum (fun a => (cycle_power_dyadic_b_lift k b (a+1) && cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat) = (range (q-1)).sum (fun a => (b (a+1) && b (a+1+4*q-q-1)).toNat) := sum_congr rfl (fun a ha => hb a (mem_range.mp ha)) rw [hmid]
The boundary values of the lifted function evaluate to b(0), b(3*q), b(q - 1), and b(4*q - 1).
We evaluate cycle_power_dyadic_b_lift at each boundary index by checking whether the index is strictly less than q: at 0 (< q) it gives b(0); at q (≥ q) it shifts by 2*q to give b(3*q); at 0 + 2*q - q - 1 = q - 1 (< q) it gives b(q - 1); and at q + 2*q - q - 1 = 2*q - 1 (≥ q) it shifts by 2*q to give b(4*q - 1).
uses
if_pos,if_neghave hz : cycle_power_dyadic_b_lift k b 0 = b 0 := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hq] have hqlo : cycle_power_dyadic_b_lift k b q = b (3*q) := by dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)] congr 1; omega have hleft : cycle_power_dyadic_b_lift k b (0 + 2*q-q-1) = b (q-1) := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)] congr 1; omega have hright : cycle_power_dyadic_b_lift k b (q + 2*q-q-1) = b (4*q-1) := by dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)] congr 1; omega
Substituting the boundary values and simplifying boolean conjunctions balances the equation. automation
We substitute the boundary evaluations and the root conditions b(0) = true and b(4*q - 1) = true. Using Bool.true_and and Bool.and_true, the conjunctions with true simplify away. Both sides of the equation then consist of the same five terms (the interior sum and four boundary bit values: b(3*q - 1), b(q), b(q - 1), and b(3*q)), so linear integer arithmetic closes the goal.
uses
Bool.true_and,Bool.and_truerw [hz, hqlo, hleft, hright, hr0, hr1] have he0 : 0 + 4*q-q-1=3*q-1 := by omega have he1 : q+4*q-q-1=4*q-1 := by omega rw [he0, he1, hr1] simp only [Bool.true_and, Bool.and_true] omega
Nat.two_pow_pos- For any natural number w, 2^w is strictly positive.
pow_succ- In any monoid, a^(n+1) = a^n * a.
sum_range_succ- Peeling the last term off a sum: the sum of f over range (n+1) is the sum over range n plus f(n).
sum_range_succ'- Peeling the first term off a sum: the sum of f over range (n+1) is the sum of f(k+1) over range n plus f(0).
if_pos- If condition c holds, the conditional expression (if c then t else e) evaluates to t.
if_neg- If condition c is false, the conditional expression (if c then t else e) evaluates to e.
sum_congr- If two index sets are equal and their summands agree on all elements, the sums are equal.
mem_range.mp- If m is in range n, then m < n.
Bool.true_and- For any boolean b, true && b is equal to b.
Bool.and_true- For any boolean b, b && true is equal to b.
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_neighbour_pair_count_prune_top (k : ℕ) (b : ℕ → Bool) (hroot : b 0 = true ∧ b (2 ^ (k + 2) - 1) = true) : cycle_power_dyadic_neighbour_pair_count (k + 2) k b + (b (2 ^ k - 1)).toNat + (b (3 * 2 ^ k)).toNat = cycle_power_dyadic_neighbour_pair_count (k + 1) k (cycle_power_dyadic_b_lift k b) + (b (3 * 2 ^ k - 1)).toNat + (b (2 ^ k)).toNat := by let q := 2 ^ k have hq : 0 < q := Nat.two_pow_pos k have hH : 2 ^ (k + 1) = 2 * q := by dsimp [q]; rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 4 * q := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega have hr0 : b 0 = true := hroot.1 have hr1 : b (4 * q - 1) = true := by simpa only [hD] using hroot.2 have hsplit (f : ℕ → ℕ) : (range (q + 1)).sum f = f 0 + (range (q - 1)).sum (fun a => f (a+1)) + f q := by have hqr : q + 1 = (q - 1 + 1) + 1 := by omega rw [hqr, sum_range_succ, sum_range_succ'] rw [show q-1+1=q by omega] omega have hb : ∀ a < q - 1, (cycle_power_dyadic_b_lift k b (a+1) && cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat = (b (a+1) && b (a+1+4*q-q-1)).toNat := by intro a ha dsimp [cycle_power_dyadic_b_lift] rw [if_pos (by dsimp [q] at *; omega), if_neg (by dsimp [q] at *; omega)] congr 2; congr 1; omega unfold cycle_power_dyadic_neighbour_pair_count rw [show 2^k=q from rfl, hD, hH, hsplit, hsplit] have hmid : (range (q-1)).sum (fun a => (cycle_power_dyadic_b_lift k b (a+1) && cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat) = (range (q-1)).sum (fun a => (b (a+1) && b (a+1+4*q-q-1)).toNat) := sum_congr rfl (fun a ha => hb a (mem_range.mp ha)) rw [hmid] have hz : cycle_power_dyadic_b_lift k b 0 = b 0 := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hq] have hqlo : cycle_power_dyadic_b_lift k b q = b (3*q) := by dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)] congr 1; omega have hleft : cycle_power_dyadic_b_lift k b (0 + 2*q-q-1) = b (q-1) := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)] congr 1; omega have hright : cycle_power_dyadic_b_lift k b (q + 2*q-q-1) = b (4*q-1) := by dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)] congr 1; omega rw [hz, hqlo, hleft, hright, hr0, hr1] have he0 : 0 + 4*q-q-1=3*q-1 := by omega have he1 : q+4*q-q-1=4*q-1 := by omega rw [he0, he1, hr1] simp only [Bool.true_and, Bool.and_true] omega