cycle_power_dyadic_b_lift_low
Middle-quarter pruning preserves every smaller-scale left position.
Statement
theorem cycle_power_dyadic_b_lift_low (k j a : ℕ) (hjk : j ≤ k) (ha : a < 2 ^ j) (b : ℕ → Bool) :
cycle_power_dyadic_b_lift k b a = b a- 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
To show that the dyadic lift operation at scale k preserves values at indices a < 2^j when j ≤ k, we observe that a < 2^j ≤ 2^k. By definition, the lift evaluates to the original function b whenever the index is strictly less than 2^k. Since a < 2^k holds by transitivity, the conditional simplifies directly to b a.
2^j ≤ 2^k
Because j ≤ k and the base 2 is strictly positive (verified by `decide`), monotonicity of powers (Nat.pow_le_pow_right) establishes that 2^j ≤ 2^k.
uses
Nat.pow_le_pow_righthave hpow : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hjk
cycle_power_dyadic_b_lift k b a = b a
Unfolding the definition of cycle_power_dyadic_b_lift gives the conditional `if a < 2^k then b a else b (a + 2^(k + 1))`. Since a < 2^j and 2^j ≤ 2^k, linear arithmetic (`omega`) proves that a < 2^k. Rewriting with if_pos selects the first branch, yielding b a.
uses
if_posdsimp [cycle_power_dyadic_b_lift] rw [if_pos (by omega : a < 2 ^ k)]
Nat.pow_le_pow_right- For any base n > 0 and natural numbers i ≤ j, n^i ≤ n^j.
if_pos- If a condition c is true, then the conditional expression `if c then t else e` evaluates to t.
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_low (k j a : ℕ) (hjk : j ≤ k) (ha : a < 2 ^ j) (b : ℕ → Bool) : cycle_power_dyadic_b_lift k b a = b a := by have hpow : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hjk dsimp [cycle_power_dyadic_b_lift] rw [if_pos (by omega : a < 2 ^ k)]