AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_b_lift_high

theoremverified

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

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.

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

    lines 6–8

    uses Nat.pow_le_pow_right, pow_succ

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

    lines 9–10

    uses if_neg

      dsimp [cycle_power_dyadic_b_lift]
      rw [if_neg (by omega : ¬a + 2 ^ (k + 1) - 2 ^ j < 2 ^ k)]
  3. 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).

    lines 11–12

      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

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