cycle_power_dyadic_half_owner_full_prune_of_middle
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
- 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_prune_full_class_cover_of_middle_fullnessCurrent-scale middle-bit fullness ensures that every vertex of the pruned model lies in a full pruned class. Fullness and half-distance…
- cycle_power_dyadic_half_owner_order_of_middle_full_pruneIf selected middle bits force full prunes and the retained outer quarters are monotone toward the endpoints, then coverage only at the…
- cycle_power_dyadic_half_monotone_of_middle_full_pruneOne uniform induction step: if all middle marks have full prunes and both retained outer quarters are monotone toward their endpoints,…
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.
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.
uses
pow_succhave hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega
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.
by_cases hl : a < 2^k · exact hmid p (a+2^(k+1)) (by omega) (by omega) h1
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.
· 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
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_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