AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_b_lift_low

theoremverified

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
Used by 3

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.

  1. 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.

    line 5

    uses Nat.pow_le_pow_right

      have hpow : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hjk
  2. 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.

    lines 6–7

    uses if_pos

      dsimp [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

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)]
See it in the graphDiscuss this resultChallenge it