cycle_power_dyadic_b_lift_high
Middle-quarter pruning maps every smaller-scale right endpoint to its original larger-scale position.
Statement
theorem cycle_power_dyadic_b_lift_high (k j a : ℕ) (hjk : j ≤ k) (ha : a < 2 ^ j) (b : ℕ → Bool) :
cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j) =
b (a + 2 ^ (k + 2) - 2 ^ j)- Source
- Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- 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 3
- cycle_power_dyadic_pair_count_pruneDeleting the middle two quarters preserves each smaller dyadic pair count.
- cycle_power_dyadic_no_island_rank_owner_orderUnder no-island class shape, tightness, exact dyadic edges and full ordinary coverage, the unique owner roots of consecutive edges are…
- cycle_power_dyadic_tight_class_parentEquality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc…
The proof, explained
The theorem states that evaluating the lifted sequence cycle_power_dyadic_b_lift k b at the offset a + 2^(k + 1) - 2^j produces b (a + 2^(k + 2) - 2^j). Since j ≤ k, the power bound 2^j ≤ 2^k ensures that the index is at least 2^k, placing it in the second (else) branch of the definition of the lift. In this branch, an additional 2^(k + 1) is added to the index, which combines with the existing 2^(k + 1) to equal 2^(k + 2), matching the target argument.
2^j ≤ 2^k, 2^(k + 1) = 2 * 2^k, and 2^(k + 2) = 2 * 2^(k + 1)
Three powers-of-two facts are established. First, since 2 > 0 and j ≤ k, monotonicity of powers (Nat.pow_le_pow_right) gives 2^j ≤ 2^k. Second, rewriting 2^(k + 1) using pow_succ gives 2^k * 2, which equals 2 * 2^k by commutativity (omega). Third, the same recurrence and commutativity show 2^(k + 2) = 2 * 2^(k + 1).
uses
Nat.pow_le_pow_right,pow_succhave hpow : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hjk 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
The definition of cycle_power_dyadic_b_lift simplifies to its second branch: b (a + 2^(k + 1) - 2^j + 2^(k + 1)) = b (a + 2^(k + 2) - 2^j)
Unfolding cycle_power_dyadic_b_lift yields an if-then-else testing whether the index a + 2^(k + 1) - 2^j is strictly less than 2^k. Since 2^(k + 1) = 2 * 2^k and 2^j ≤ 2^k, the index is at least 2 * 2^k - 2^k = 2^k, so this condition is false (disproved by omega). Rewriting with if_neg selects the else branch, which adds 2^(k + 1) to the argument.
uses
if_negdsimp [cycle_power_dyadic_b_lift] rw [if_neg (by omega : ¬a + 2 ^ (k + 1) - 2 ^ j < 2 ^ k)]
The arguments to b coincide, completing the proof.
By congruence (congr 1), it suffices to check that the inputs to b are identical: a + 2^(k + 1) - 2^j + 2^(k + 1) = a + 2^(k + 2) - 2^j. Substituting 2^(k + 2) = 2 * 2^(k + 1), this is a straightforward identity in natural number arithmetic (omega).
congr 1 omega
Nat.pow_le_pow_right- For any base n > 0, if i ≤ j, then n^i ≤ n^j.
pow_succ- In any monoid, raising an element to the power n + 1 equals its nth power multiplied by the element.
if_neg- If a condition c is false (¬c), then the expression (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_b_lift_high (k j a : ℕ) (hjk : j ≤ k) (ha : a < 2 ^ j) (b : ℕ → Bool) : cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j) = b (a + 2 ^ (k + 2) - 2 ^ j) := by have hpow : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hjk 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 dsimp [cycle_power_dyadic_b_lift] rw [if_neg (by omega : ¬a + 2 ^ (k + 1) - 2 ^ j < 2 ^ k)] congr 1 omega