cycle_power_dyadic_neighbour_pair_count_prune_low
Deleting the middle two quarters preserves each strictly smaller neighbour pair count.
Statement
theorem cycle_power_dyadic_neighbour_pair_count_prune_low
(k j : ℕ) (hj : j < k) (b : ℕ → Bool) :
cycle_power_dyadic_neighbour_pair_count (k + 2) j b =
cycle_power_dyadic_neighbour_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 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
The theorem states that pruning the middle two quarters of a sequence of length 2 ^ (k + 2) down to length 2 ^ (k + 1) (via cycle_power_dyadic_b_lift) preserves each dyadic neighbour pair count at strictly smaller scales j < k. Both counts are defined as sums over indices a ≤ 2 ^ j of the product of two sequence values. The proof establishes equality term-by-term using sum_congr: since 2 ^ j < 2 ^ k, the first index a lies in the first quarter [0, 2 ^ k) where the lifted sequence coincides with the original, while the second index falls into the fourth quarter, where the lift shifts the argument by 2 ^ (k + 1) to match the original index at scale k + 2.
2 ^ j < 2 ^ k
Because 1 < 2 and j < k, the base-2 exponential function is strictly increasing, so 2 ^ j < 2 ^ k by Nat.pow_lt_pow_right.
uses
Nat.pow_lt_pow_righthave hpow : 2 ^ j < 2 ^ k := Nat.pow_lt_pow_right (by decide) hj
2 ^ (k + 1) = 2 * 2 ^ k and 2 ^ (k + 2) = 2 * 2 ^ (k + 1)
Each power identity is obtained by rewriting the successor power into 2 ^ m * 2 using pow_succ and commuting the factors with linear arithmetic.
uses
pow_succhave hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega
It suffices to show that the summands coincide for each index a ≤ 2 ^ j.
By sum_congr, equality of the two sums follows if their summands agree across the index set. The summation domain is range (2 ^ j + 1), which means a < 2 ^ j + 1 by mem_range, or equivalently a ≤ 2 ^ j by Nat.lt_succ_iff.
uses
sum_congr,mem_range,Nat.lt_succ_iffapply sum_congr rfl intro a ha have ha : a ≤ 2 ^ j := by simpa only [mem_range, Nat.lt_succ_iff] using ha
cycle_power_dyadic_b_lift k b a = b a
Unfolding cycle_power_dyadic_b_lift, the value at a is given by testing whether a < 2 ^ k. Since a ≤ 2 ^ j and 2 ^ j < 2 ^ k, this inequality holds, so if_pos selects the first branch b a.
uses
if_poshave hlo : cycle_power_dyadic_b_lift k b a = b a := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)]
cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j - 1) = b (a + 2 ^ (k + 2) - 2 ^ j - 1)
Unfolding cycle_power_dyadic_b_lift at the shifted index, the branch condition is a + 2 ^ (k + 1) - 2 ^ j - 1 < 2 ^ k. Because 2 ^ (k + 1) = 2 * 2 ^ k and 2 ^ j < 2 ^ k, this index is at least 2 ^ k, making the condition false. Applying if_neg selects the second branch, evaluating b at (a + 2 ^ (k + 1) - 2 ^ j - 1) + 2 ^ (k + 1). Linear arithmetic then verifies that this argument equals a + 2 ^ (k + 2) - 2 ^ j - 1.
uses
if_neghave hhi : cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j - 1) = b (a + 2 ^ (k + 2) - 2 ^ j - 1) := by dsimp [cycle_power_dyadic_b_lift] rw [if_neg (by omega)] congr 1; omega
The summands are equal, completing the proof.
Rewriting the lifted terms using the identities established in the previous two steps transforms the summand of the lifted count into that of the original count.
rw [hlo, hhi]
Nat.pow_lt_pow_right- For a base greater than 1, strictly smaller exponents give strictly smaller powers: if 1 < a and m < n, then a ^ m < a ^ n.
pow_succ- Powers in a monoid satisfy a ^ (n + 1) = a ^ n * a.
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element of the index set.
mem_range- A natural number m belongs to range n if and only if m < n.
Nat.lt_succ_iff- A natural number m is strictly less than n + 1 if and only if m ≤ n.
if_pos- If condition c is true, then if c then t else e evaluates to t.
if_neg- If condition c is false, then if c then t else e evaluates to e.
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_low (k j : ℕ) (hj : j < k) (b : ℕ → Bool) : cycle_power_dyadic_neighbour_pair_count (k + 2) j b = cycle_power_dyadic_neighbour_pair_count (k + 1) j (cycle_power_dyadic_b_lift k b) := by have hpow : 2 ^ j < 2 ^ k := Nat.pow_lt_pow_right (by decide) hj have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega apply sum_congr rfl intro a ha have ha : a ≤ 2 ^ j := by simpa only [mem_range, Nat.lt_succ_iff] using ha have hlo : cycle_power_dyadic_b_lift k b a = b a := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)] have hhi : cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j - 1) = b (a + 2 ^ (k + 2) - 2 ^ j - 1) := by dsimp [cycle_power_dyadic_b_lift] rw [if_neg (by omega)] congr 1; omega rw [hlo, hhi]