cycle_power_dyadic_half_owner_order_of_middle_full_prune
If selected middle bits force full prunes and the retained outer quarters are monotone toward the endpoints, then coverage only at the half-radius-plus-one distance forces the exact half-edge owners to be ordered by root. The structural premises remain explicit.
Statement
theorem cycle_power_dyadic_half_owner_order_of_middle_full_prune (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) (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) (hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^k → x p b = true → x p a = true) (hright : ∀ (p : ℤ) (a b : ℕ), 3*2^k ≤ a → a ≤ b → b < 2^(k+2) → x p a = true → x p b = true) (hcover : ∀ v : ℤ, ∃ c : ℕ, c < 2^(k+2)-(2^(k+1)+1) ∧ x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+(2^(k+1)+1)) = 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 6
- 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_full_prune_root_separationTwo roots whose pruned classes are full must be separated by at least one quarter of the original radius.
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- cycle_power_dyadic_tight_class_middle_parentEquality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent…
- cycle_power_dyadic_half_owner_full_prune_of_middleIf every selected middle-quarter bit forces a full prune, then every class owning a half-radius edge has a full prune.
- 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_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
The theorem is proved by contradiction: assuming b > a + 1, the roots v - a and v + 1 - b of the two half-edge owners are separated by r = b - a - 1 > 0. Because both rows possess half-edges, middle-prune propagation forces both rows to have fully pruned lifts, which by root separation implies r ≥ 2^k, restricting a < 2^k - 1 and b > 2^k. A covering pair at distance 2^(k+1)+1 with index c is then analyzed: if c < 2^k - 1 or c ≥ 2^k, tight class weight and exactness force c + 1 = b or c = a (contradicting the bounds on a and b), while if c = 2^k - 1, monotonicity forces row v - c to be fully pruned as well, contradicting the root separation bound between v - c and v - a.
Define q = 2^k and establish the dyadic scaling relations 2^(k+1) = 2q and 2^(k+2) = 4q, with q > 0.
We abbreviate q = 2^k. Powers of two are strictly positive by Nat.two_pow_pos. The scaling identities 2^(k+1) = 2q and 2^(k+2) = 4q follow from pow_succ and linear arithmetic.
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 containing a half-edge pair is fully pruned.
Applying cycle_power_dyadic_half_owner_full_prune_of_middle with the middle-prune assumption hmid shows that any row p with true bits at a and a + 2^(k+1) (where a < 2^(k+1)) has its b-lift identically true on all inputs.
uses
cycle_power_dyadic_half_owner_full_prune_of_middlehave hfull := cycle_power_dyadic_half_owner_full_prune_of_middle k x hmidAssume for contradiction that the half-owner order fails, so b > a + 1.
We introduce the vertex v and the owners a, b < 2^(k+1) of the half-edges at v and v+1. Assuming the negation of the conclusion b ≤ a + 1 yields a + 1 < b by linear arithmetic.
intro v a b ha hb ha0 ha1 hb0 hb1 by_contra hne have hab : a+1 < b := by omega
The root separation r = b - a - 1 between rows v+1-b and v-a is at least 2^k.
Setting r = b - a - 1 > 0, the root indices satisfy (v+1-b) + r = v - a. Since both row v-a and row v+1-b contain half-edges, both have fully pruned b-lifts. Applying cycle_power_dyadic_full_prune_root_separation at scale k, the separation r between two fully pruned rows must satisfy 2^k ≤ r.
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 owners satisfy the strict bounds a < q - 1 and b > q.
Since 2^k = q ≤ r = b - a - 1 and both a, b < 2q, linear arithmetic forces a + 1 < q (so a < q - 1) and b > q + a + 1 > q.
have haq : a+1 < q := by omega have hbq : q < b := by omega
Obtain a covering pair at distance 2^(k+1)+1 for vertex v with offset c < 2^(k+1).
Hypothesis hcover provides an index c < 2^(k+2) - (2^(k+1)+1) = 2q - 1 such that row v-c has true bits at both c and c + (2^(k+1)+1). In particular, c < 2^(k+1).
obtain ⟨c,hc,hc0,hc1⟩ := hcover v have hcH : c < 2^(k+1) := by omega
The case c < q - 1 is impossible.
If c < q - 1, the index c + 2^(k+1) + 1 falls in the right-middle range [2^(k+1), 3*2^k). By cycle_power_dyadic_tight_class_middle_parent, row v-c also has a true bit at (c + 2^(k+1) + 1) - 2^(k+1) = c + 1. Since v - c = (v+1) - (c+1), index c+1 is a half-edge owner at vertex v+1. By uniqueness of exact pairs at scale k+1 (cycle_power_exact_pair_unique), c + 1 = b. But c < q - 1 implies b = c + 1 < q, contradicting b > q.
uses
cycle_power_dyadic_tight_class_middle_parent,cycle_power_exact_pair_uniqueby_cases hcl : c < q-1 · have hp := (cycle_power_dyadic_tight_class_middle_parent k (x (v-(c : ℤ))) (htight _)).2 (c+(2^(k+1)+1)) (by omega) (by omega) hc1 have hi : c+(2^(k+1)+1)-2^(k+1)=c+1 := by omega rw [hi] at hp have hrt : v+1-((c+1 : ℕ) : ℤ)=v-(c : ℤ) := by omega have hiC : c+1+2^(k+2)-2^(k+1)=c+(2^(k+1)+1) := by omega have hiB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) (v+1) (c+1) b (by omega) hb (by simpa only [hrt] using hp) (by simpa only [hrt,hiC] using hc1) hb0 (by simpa only [hiB] using hb1) omega
The case q ≤ c is impossible.
If q ≤ c < 2q, index c lies in the left-middle range [2^k, 2^(k+1)). By cycle_power_dyadic_tight_class_middle_parent, row v-c also has a true bit at c + 2^(k+1), making c a half-edge owner at vertex v. Uniqueness of exact pairs (cycle_power_exact_pair_unique) gives c = a. But q ≤ c implies q ≤ a, contradicting a < q - 1.
uses
cycle_power_dyadic_tight_class_middle_parent,cycle_power_exact_pair_unique· by_cases hch : q ≤ c · have hp := (cycle_power_dyadic_tight_class_middle_parent k (x (v-(c : ℤ))) (htight _)).1 c (by omega) (by omega) hc0 have hiC : c+2^(k+2)-2^(k+1)=c+2^(k+1) := by omega have hiA : a+2^(k+2)-2^(k+1)=a+2^(k+1) := by omega have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) v c a hcH ha hc0 (by simpa only [hiC] using hp) ha0 (by simpa only [hiA] using ha1) omega
The remaining case c = q - 1 is impossible, completing the proof.
If c = q - 1, then c < 2^k, so left-monotonicity (hleft) forces all bits i ≤ c in row v-c to be true. Similarly, c + 2^(k+1) + 1 = 3*2^k, so right-monotonicity (hright) forces all bits from 3*2^k onward to be true. Thus row v-c has a fully pruned b-lift. Let s = c - a > 0. The root shift is (v-c) + s = v - a. By cycle_power_dyadic_full_prune_root_separation, 2^k ≤ s. But s = c - a ≤ c = q - 1 < q = 2^k, a contradiction.
uses
cycle_power_dyadic_full_prune_root_separation· have hcq : c=q-1 := by omega have hcf : ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x (v-(c : ℤ))) i = true := by intro i hi dsimp [cycle_power_dyadic_b_lift] split_ifs with hil · exact hleft (v-(c : ℤ)) i c (by omega) (by omega) hc0 · have he : c+(2^(k+1)+1)=3*2^k := by omega apply hright (v-(c : ℤ)) (3*2^k) (i+2^(k+1)) (by omega) (by omega) (by omega) simpa only [he] using hc1 let s := c-a have hs : 0 < s := by dsimp [s]; omega have hrt : v-(c : ℤ)+(s : ℤ)=v-(a : ℤ) := by dsimp [s]; omega have hssep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) (v-(c : ℤ)) s hs hcf (by simpa only [hrt] using hfa) dsimp [s] at hssep omega
Nat.two_pow_pos- For any natural number w, the power 2^w is strictly positive.
pow_succ- In any monoid (including natural numbers), a^(n+1) = a^n * a.
cycle_power_dyadic_half_owner_full_prune_of_middle- If any middle bit forces a full prune on row p, then a row with both half-edge bits true at distance 2^(k+1) has its entire b-lift identically true.
cycle_power_dyadic_full_prune_root_separation- Under exact coverage at scale k, two rows separated by r > 0 that both have fully pruned b-lifts must satisfy 2^k ≤ r.
cycle_power_dyadic_tight_class_middle_parent- For a configuration with tight class weight at scale k+2, a true bit in [2^k, 2^(k+1)) forces the bit at offset +2^(k+1) to be true, and a true bit in [2^(k+1), 3*2^k) forces the bit at offset -2^(k+1) to be true.
cycle_power_exact_pair_unique- When exact coverage holds with pair distance D - R and range R at vertex v, at most one index a < R can satisfy both pair conditions; any two such indices must be equal.
- The proof makes extensive use of the `omega` tactic to verify linear inequalities and arithmetic over natural numbers and integers across the case analysis.
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_order_of_middle_full_prune (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) (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) (hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^k → x p b = true → x p a = true) (hright : ∀ (p : ℤ) (a b : ℕ), 3*2^k ≤ a → a ≤ b → b < 2^(k+2) → x p a = true → x p b = true) (hcover : ∀ v : ℤ, ∃ c : ℕ, c < 2^(k+2)-(2^(k+1)+1) ∧ x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+(2^(k+1)+1)) = 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 := cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid 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 hbq : q < b := by omega obtain ⟨c,hc,hc0,hc1⟩ := hcover v have hcH : c < 2^(k+1) := by omega by_cases hcl : c < q-1 · have hp := (cycle_power_dyadic_tight_class_middle_parent k (x (v-(c : ℤ))) (htight _)).2 (c+(2^(k+1)+1)) (by omega) (by omega) hc1 have hi : c+(2^(k+1)+1)-2^(k+1)=c+1 := by omega rw [hi] at hp have hrt : v+1-((c+1 : ℕ) : ℤ)=v-(c : ℤ) := by omega have hiC : c+1+2^(k+2)-2^(k+1)=c+(2^(k+1)+1) := by omega have hiB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) (v+1) (c+1) b (by omega) hb (by simpa only [hrt] using hp) (by simpa only [hrt,hiC] using hc1) hb0 (by simpa only [hiB] using hb1) omega · by_cases hch : q ≤ c · have hp := (cycle_power_dyadic_tight_class_middle_parent k (x (v-(c : ℤ))) (htight _)).1 c (by omega) (by omega) hc0 have hiC : c+2^(k+2)-2^(k+1)=c+2^(k+1) := by omega have hiA : a+2^(k+2)-2^(k+1)=a+2^(k+1) := by omega have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x (hexact (k+1) (by omega)) v c a hcH ha hc0 (by simpa only [hiC] using hp) ha0 (by simpa only [hiA] using ha1) omega · have hcq : c=q-1 := by omega have hcf : ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x (v-(c : ℤ))) i = true := by intro i hi dsimp [cycle_power_dyadic_b_lift] split_ifs with hil · exact hleft (v-(c : ℤ)) i c (by omega) (by omega) hc0 · have he : c+(2^(k+1)+1)=3*2^k := by omega apply hright (v-(c : ℤ)) (3*2^k) (i+2^(k+1)) (by omega) (by omega) (by omega) simpa only [he] using hc1 let s := c-a have hs : 0 < s := by dsimp [s]; omega have hrt : v-(c : ℤ)+(s : ℤ)=v-(a : ℤ) := by dsimp [s]; omega have hssep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) (v-(c : ℤ)) s hs hcf (by simpa only [hrt] using hfa) dsimp [s] at hssep omega