AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_half_owner_full_prune_of_middle

theoremverified

If every selected middle-quarter bit forces a full prune, then every class owning a half-radius edge has a full prune.

Statement

theorem cycle_power_dyadic_half_owner_full_prune_of_middle
    (k : ℕ) (x : ℤ → ℕ → Bool)
    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →
      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)
    (p : ℤ) (a : ℕ) (ha : a < 2^(k+1))
    (h0 : x p a = true) (h1 : x p (a+2^(k+1)) = true) :
    ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true
Source
Uniform conditional structural helper for OP-205 / RT-1 following arXiv:2610.15635 Section 3. The middle-bit fullness assumptions and smaller-quarter monotonicity are explicit when used; no optimal-count classification, graph covering value or research advance is claimed.
Verified
27 Oct 2026
Axioms
Quot.soundpropext
Built on 1
Used by 3

The proof, explained

To show that owning a half-radius edge forces a full prune, we consider the two bit coordinates a and a + 2^(k+1), both of which evaluate to true under x p. We split into cases depending on whether a < 2^k. Because 2^(k+1) = 2 * 2^k, either the shifted index a + 2^(k+1) or the index a itself falls into the middle range [2^k, 3 * 2^k), so the middle-quarter pruning hypothesis applies in either case.

  1. 2^(k+1) = 2 * 2^k

    We expand 2^(k+1) into 2^k * 2 using pow_succ, after which linear arithmetic simplifies the product to 2 * 2^k.

    line 10

    uses pow_succ

      have hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega
  2. In the case a < 2^k, the shifted index a + 2^(k+1) lies in the middle range [2^k, 3 * 2^k), forcing a full prune.

    We split into cases on whether a < 2^k. When a < 2^k, the shifted index a + 2^(k+1) satisfies 2^k ≤ a + 2^(k+1) and a + 2^(k+1) < 2^k + 2 * 2^k = 3 * 2^k. Since x p (a + 2^(k+1)) = true by assumption (h1), the middle-range pruning hypothesis (hmid) applies to a + 2^(k+1), establishing the full prune.

    lines 11–12

      by_cases hl : a < 2^k
      · exact hmid p (a+2^(k+1)) (by omega) (by omega) h1
  3. In the case a ≥ 2^k, the index a itself lies in the middle range [2^k, 3 * 2^k), forcing a full prune.

    When ¬(a < 2^k), we have 2^k ≤ a. Together with the assumption a < 2^(k+1) = 2 * 2^k < 3 * 2^k, this places a directly in [2^k, 3 * 2^k). Since x p a = true by assumption (h0), applying the middle-range pruning hypothesis (hmid) to a completes the second case.

    line 13

      · exact hmid p a (by omega) (by omega) h0
pow_succ
Raising a base to power n + 1 equals raising it to power n multiplied by the base: a^(n+1) = a^n * a.

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_half_owner_full_prune_of_middle    (k : ℕ) (x : ℤ → ℕ → Bool)    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)    (p : ℤ) (a : ℕ) (ha : a < 2^(k+1))    (h0 : x p a = true) (h1 : x p (a+2^(k+1)) = true) :    ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true := by  have hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega  by_cases hl : a < 2^k  · exact hmid p (a+2^(k+1)) (by omega) (by omega) h1  · exact hmid p a (by omega) (by omega) h0
See it in the graphDiscuss this resultChallenge it