cycle_power_dyadic_no_island_half_owner_order
In a tight dyadic full-coverage class model with explicit no-island shapes, the root owning the next half-radius edge is at least the root owning the preceding one. No scalar count or periodicity is assumed.
Statement
theorem cycle_power_dyadic_no_island_half_owner_order (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) = (range (2^(k+2))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1) (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) → x p a = false → x p b = true → x p c = true) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+2)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) : ∀ (v : ℤ) (a b : ℕ), a < 2^(k+1) → b < 2^(k+1) → x (v-(a : ℤ)) a = true → x (v-(a : ℤ)) (a+2^(k+1)) = true → x (v+1-(b : ℤ)) b = true → x (v+1-(b : ℤ)) (b+2^(k+1)) = true → b ≤ a+1
- 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
Classical.choiceQuot.soundpropext- Built on 7
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_no_island_no_long_prefixConditional shape-model half-width theorem: a class with an initial selected interval extending strictly beyond half the radius cannot…
- cycle_power_dyadic_full_prune_root_separationTwo roots whose pruned classes are full must be separated by at least one quarter of the original radius.
- cycle_power_dyadic_no_island_middle_imp_full_pruneIf a tight dyadic two-interval class contains any middle-quarter vertex, deleting the middle two quarters leaves a full smaller class.…
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- cycle_power_dyadic_full_prune_outerFullness after middle-quarter pruning means that both outer quarters of the original class are entirely selected.
- 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 1
- 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…
The proof, explained
The theorem shows that when moving from vertex v to v + 1, the owner index b of the half-radius chord (span 2^(k+1)) satisfies b ≤ a + 1, meaning the root (v+1) - b owning the edge at v + 1 is at least the preceding root v - a. Assuming for contradiction that a + 1 < b, both roots own chords of span 2^(k+1) and are therefore fully pruned. By the root separation theorem, the offset r = b - a - 1 between the roots must be at least 2^k, which implies a + 1 < 2^k. This upper bound allows us, via the outer pattern of fully pruned rows and the no-long-prefix property, to show that a + 1 also owns the half-radius chord at vertex v + 1. By uniqueness of the owner at v + 1, we obtain a + 1 = b, contradicting a + 1 < b.
Define q = 2^k and establish the powers 2^(k+1) = 2q and 2^(k+2) = 4q with q > 0.
We set q = 2^k. By Nat.two_pow_pos, q > 0. Using pow_succ and linear arithmetic (omega), we rewrite the half-period 2^(k+1) as 2q and the full period 2^(k+2) as 4q.
uses
Nat.two_pow_pos,pow_succlet q := 2^k have hq : 0 < q := Nat.two_pow_pos _ have hH : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega have hD : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hH]; omega
Any row owning a chord of span 2^(k+1) is fully pruned.
Suppose a row p satisfies x(p, a) = true and x(p, a + 2^(k+1)) = true for some a < 2^(k+1) = 2q. We case-split on whether a < q. If a < q, then the second endpoint a + 2^(k+1) = a + 2q falls in [2q, 3q) = [2^k, 3 · 2^k). If a ≥ q, then the first endpoint a lies in [q, 2q) ⊆ [2^k, 3 · 2^k). In either case, row p contains a true bit in [2^k, 3 · 2^k). Applying cycle_power_dyadic_no_island_middle_imp_full_prune shows that row p is fully pruned on [0, 2^(k+1)).
uses
cycle_power_dyadic_no_island_middle_imp_full_prunehave hfull (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 by_cases hl : a < q · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p) (hshape p) (a+2^(k+1)) (by omega) (by omega) h1 · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p) (hshape p) a (by omega) (by omega) h0
Assume for contradiction that the next owner index satisfies b > a + 1.
We introduce vertices and owner indices a, b < 2^(k+1) for the chords of span 2^(k+1) at vertex v and vertex v + 1, respectively. We assume for contradiction that ¬(b ≤ a + 1), which means a + 1 < b.
intro v a b ha hb ha0 ha1 hb0 hb1 by_contra hne have hab : a+1 < b := by omega
The root offset r = b - a - 1 is positive and satisfies r ≥ 2^k.
Let r = b - a - 1. Since a + 1 < b, we have r > 0 and b = a + r + 1. The root owning the chord at v + 1 is v + 1 - b, and shifting it by r yields (v + 1 - b) + r = v - a, the root owning the chord at v. Because both rows own chords of span 2^(k+1), both are fully pruned by the helper lemma hfull. Applying cycle_power_dyadic_full_prune_root_separation to these two distinct fully pruned rows separated by r > 0 yields r ≥ 2^k.
uses
cycle_power_dyadic_full_prune_root_separationlet r := b-a-1 have hr : 0 < r := by dsimp [r]; omega have hsum : b = a+r+1 := by dsimp [r]; omega have hroot : v+1-(b : ℤ)+(r : ℤ)=v-(a : ℤ) := by omega have hfa := hfull (v-(a : ℤ)) a ha ha0 ha1 have hfb := hfull (v+1-(b : ℤ)) b hb hb0 hb1 have hsep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) (v+1-(b : ℤ)) r hr hfb (by simpa only [hroot] using hfa)
The index a + 1 is strictly less than q, which implies x(v - a, a + 1) = true.
From b < 2^(k+1) = 2q, b = a + r + 1, and r ≥ q, we have a + 1 = b - r < 2q - q = q. By cycle_power_dyadic_full_prune_outer, any fully pruned row is identically true on [0, 2^k) = [0, q). Thus x(v - a, a + 1) = true.
uses
cycle_power_dyadic_full_prune_outerhave haq : a+1 < q := by omega have hout := cycle_power_dyadic_full_prune_outer k (x (v-(a : ℤ))) hfa have hanext : x (v-(a : ℤ)) (a+1) = true := hout.1 _ haq
The right endpoint also holds: x(v - a, a + 1 + 2^(k+1)) = true.
We know x(v - a, a + 2^(k+1)) = true from hypothesis ha1. Applying cycle_power_dyadic_no_island_no_long_prefix at index h = a + 1 + 2^(k+1) (which satisfies 2^(k+1) < h < 2^(k+2) because a + 1 < q), the truth of bit h - 1 = a + 2^(k+1) forces bit h to be true as well.
uses
cycle_power_dyadic_no_island_no_long_prefixhave hanextH : x (v-(a : ℤ)) (a+1+2^(k+1)) = true := by have hh := cycle_power_dyadic_no_island_no_long_prefix k x htight hexact hshape hcover (v-(a : ℤ)) (a+1+2^(k+1)) (by omega) (by omega) (by convert ha1 using 1 <;> congr 1 <;> omega) exact hh
Index a + 1 is also an owner at vertex v + 1, forcing a + 1 = b by uniqueness and contradicting a + 1 < b.
Rewriting the root as v - a = (v + 1) - (a + 1), the verified values show that a + 1 < 2^(k+1) satisfies both x((v + 1) - (a + 1), a + 1) = true and x((v + 1) - (a + 1), a + 1 + 2^(k+2) - 2^(k+1)) = true. Thus a + 1 is an owner of the half-radius pair at vertex v + 1. By cycle_power_exact_pair_unique, the exactness condition hexact (k+1) ensures that the owner in [0, 2^(k+1)) is unique at vertex v + 1. Since b is also an owner, a + 1 = b, contradicting a + 1 < b and completing the proof.
uses
cycle_power_exact_pair_uniquehave hroot' : v+1-((a+1 : ℕ) : ℤ)=v-(a : ℤ) := by omega have heA : a+1+2^(k+2)-2^(k+1)=a+1+2^(k+1) := by omega have heB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega have hd := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) (v+1) (a+1) b (by omega) hb (by simpa only [hroot'] using hanext) (by simpa only [hroot',heA] using hanextH) hb0 (by simpa only [heB] using hb1) omega
Nat.two_pow_pos- Powers of two with natural exponents are strictly positive.
pow_succ- The (n+1)-th power of an element in a monoid equals its n-th power multiplied by the element.
cycle_power_dyadic_no_island_middle_imp_full_prune- In a tight dyadic class with no-island shape, any true bit at an index in [2^k, 3 · 2^k) implies that the row is fully pruned (its dyadic lift is identically true on [0, 2^(k+1))).
cycle_power_dyadic_full_prune_root_separation- Under exact dyadic coverage, two distinct fully pruned rows separated by distance r > 0 must satisfy r ≥ 2^k.
cycle_power_dyadic_full_prune_outer- A fully pruned row has all bits set to true in both the initial interval [0, 2^k) and the upper interval [3 · 2^k, 2^(k+2)).
cycle_power_dyadic_no_island_no_long_prefix- In a tight full-coverage model with no-island shapes, for any index h with 2^(k+1) < h < 2^(k+2), if bit h - 1 is true, then bit h is also true.
cycle_power_exact_pair_unique- When an exact coverage condition specifies that exactly one pair of span D - R occurs over range R, the owner index in [0, R) for that pair at any vertex is unique.
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_no_island_half_owner_order (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) = (range (2^(k+2))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1) (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) → x p a = false → x p b = true → x p c = true) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+2)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) : ∀ (v : ℤ) (a b : ℕ), a < 2^(k+1) → b < 2^(k+1) → x (v-(a : ℤ)) a = true → x (v-(a : ℤ)) (a+2^(k+1)) = true → x (v+1-(b : ℤ)) b = true → x (v+1-(b : ℤ)) (b+2^(k+1)) = true → b ≤ a+1 := by let q := 2^k have hq : 0 < q := Nat.two_pow_pos _ have hH : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega have hD : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hH]; omega have hfull (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 by_cases hl : a < q · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p) (hshape p) (a+2^(k+1)) (by omega) (by omega) h1 · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p) (hshape p) a (by omega) (by omega) h0 intro v a b ha hb ha0 ha1 hb0 hb1 by_contra hne have hab : a+1 < b := by omega let r := b-a-1 have hr : 0 < r := by dsimp [r]; omega have hsum : b = a+r+1 := by dsimp [r]; omega have hroot : v+1-(b : ℤ)+(r : ℤ)=v-(a : ℤ) := by omega have hfa := hfull (v-(a : ℤ)) a ha ha0 ha1 have hfb := hfull (v+1-(b : ℤ)) b hb hb0 hb1 have hsep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) (v+1-(b : ℤ)) r hr hfb (by simpa only [hroot] using hfa) have haq : a+1 < q := by omega have hout := cycle_power_dyadic_full_prune_outer k (x (v-(a : ℤ))) hfa have hanext : x (v-(a : ℤ)) (a+1) = true := hout.1 _ haq have hanextH : x (v-(a : ℤ)) (a+1+2^(k+1)) = true := by have hh := cycle_power_dyadic_no_island_no_long_prefix k x htight hexact hshape hcover (v-(a : ℤ)) (a+1+2^(k+1)) (by omega) (by omega) (by convert ha1 using 1 <;> congr 1 <;> omega) exact hh have hroot' : v+1-((a+1 : ℕ) : ℤ)=v-(a : ℤ) := by omega have heA : a+1+2^(k+2)-2^(k+1)=a+1+2^(k+1) := by omega have heB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega have hd := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) (v+1) (a+1) b (by omega) hb (by simpa only [hroot'] using hanext) (by simpa only [hroot',heA] using hanextH) hb0 (by simpa only [heB] using hb1) omega