cycle_power_dyadic_half_monotone_of_middle_full_prune
One uniform induction step: if all middle marks have full prunes and both retained outer quarters are monotone toward their endpoints, then the entire left and right halves are monotone toward the endpoints. Tightness, exact dyadic ownership and ordinary coverage are assumed; no counts, period or pre-existing original no-island shape are used.
Statement
theorem cycle_power_dyadic_half_monotone_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 : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ, ∃ c : ℕ, c < 2^(k+2)-d ∧ x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+d) = true) : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^(k+1) → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2^(k+1) ≤ a → a ≤ b → b < 2^(k+2) → x p a = true → x p b = 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
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_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_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_full_prune_outerFullness after middle-quarter pruning means that both outer quarters of the original class are entirely selected.
- 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_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_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 2
- cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_pruneA compatible hierarchy of tight exact full-coverage dyadic models has monotone endpoint halves at every level, provided every selected…
- cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_monoCurrent middle-bit fullness and monotonicity of both halves of the pruned model imply monotonicity of both original halves, in a tight…
The proof, explained
The theorem extends endpoint-directed monotonicity from the outer quarters [0, 2^k) and [3·2^k, 2^(k+2)) across the entire left and right halves [0, 2^(k+1)) and [2^(k+1), 2^(k+2)). The proof first establishes two single-step propagation lemmas: any mark at i+1 in the left half propagates leftward to i, and any mark at i in the right half propagates rightward to i+1. When the mark falls in an inner quarter, tightness pairs it into a half-owner, and coverage supplies an adjacent half-owner that the ordering and full-prune root separation uniquely pin down to the adjacent mark. Finally, natural induction on the step lemmas propagates the marks across each half.
The dyadic scale parameters q = 2^k, 2^(k+1) = 2*q, and 2^(k+2) = 4*q are established.
Define q = 2^k, note that q > 0 by Nat.two_pow_pos, and establish 2^(k+1) = 2*q and 2^(k+2) = 4*q by rewriting with 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
Half-owners inherit full prunes and satisfy the adjacent-diagonal ordering b ≤ a + 1.
Apply cycle_power_dyadic_half_owner_full_prune_of_middle to show that any half-owner has a full prune, and apply cycle_power_dyadic_half_owner_order_of_middle_full_prune with coverage distance 2^(k+1)+1 to deduce that consecutive half-owners on diagonals v and v+1 satisfy b ≤ a + 1.
uses
cycle_power_dyadic_half_owner_full_prune_of_middle,cycle_power_dyadic_half_owner_order_of_middle_full_prunehave hfull := cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid have horder := cycle_power_dyadic_half_owner_order_of_middle_full_prune k x htight hexact hmid hleft hright (hcover (2^(k+1)+1) (by omega) (by omega))
Leftward single-step propagation holds: if x p (i+1) = true with i+1 < 2^(k+1), then x p i = true.
If i+1 < q, the result holds by the assumed left-quarter monotonicity. Otherwise, i+1 is in the second quarter [q, 2*q), so by hmid the path p has a full prune. If i < q, the full prune directly implies x p i = true via cycle_power_dyadic_full_prune_outer. If i ≥ q, tightness (cycle_power_dyadic_tight_class_middle_parent) ensures x p (i+1 + 2^(k+1)) = true, making p a half-owner at i+1 on diagonal p+i+1. Coverage at distance 2^(k+1) on diagonal p+i yields a half-owner b < 2^(k+1). The adjacent ordering gives i ≤ b. If b ≠ i, the root separation s = b - i > 0 between the two full-prune paths must satisfy 2^k ≤ s by cycle_power_dyadic_full_prune_root_separation, which contradicts s = b - i < 2*q - q = 2^k. Thus b = i, which proves x p i = true.
uses
cycle_power_dyadic_full_prune_outer,cycle_power_dyadic_tight_class_middle_parent,cycle_power_dyadic_full_prune_root_separationhave hstepL (p : ℤ) (i : ℕ) (hi : i+1 < 2^(k+1)) (hx : x p (i+1) = true) : x p i = true := by by_cases hil : i+1 < q · exact hleft p i (i+1) (by omega) hil hx have hpf := hmid p (i+1) (by omega) (by omega) hx have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf by_cases hiq : i < q · exact hout.1 i hiq have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).1 (i+1) (by omega) hi hx obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(i : ℤ)) have hbH : b < 2^(k+1) := by omega have hrt : p+(i : ℤ)+1-((i+1 : ℕ) : ℤ)=p := by omega have hle := horder (p+(i : ℤ)) b (i+1) hbH hi hb0 hb1 (by simpa only [hrt] using hx) (by simpa only [hrt] using hp) have hib : i ≤ b := by omega have hbf := hfull (p+(i : ℤ)-(b : ℤ)) b hbH hb0 hb1 have hbi : b=i := by by_contra hne let s := b-i have hs : 0 < s := by dsimp [s]; omega have hroot : p+(i : ℤ)-(b : ℤ)+(s : ℤ)=p := by dsimp [s]; omega have hsep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) (p+(i : ℤ)-(b : ℤ)) s hs hbf (by simpa only [hroot] using hpf) dsimp [s] at hsep omega subst b simpa using hb0
Rightward single-step propagation holds: if x p i = true with 2^(k+1) ≤ i and i+1 < 2^(k+2), then x p (i+1) = true.
If i ≥ 3*q, the result holds by the assumed right-quarter monotonicity. Otherwise, i is in the third quarter [2*q, 3*q), so by hmid the path p has a full prune. If i+1 ≥ 3*q, the full prune implies x p (i+1) = true via cycle_power_dyadic_full_prune_outer. If i+1 < 3*q, setting a = i - 2^(k+1) < q, tightness (cycle_power_dyadic_tight_class_middle_parent) gives x p a = true, so p is a half-owner at a on diagonal p+a. Coverage at distance 2^(k+1) on diagonal p+a+1 gives a half-owner b < 2^(k+1). The ordering implies b ≤ a+1. If b ≠ a+1, the difference s = a+1-b > 0 between the two full-prune paths requires 2^k ≤ s by cycle_power_dyadic_full_prune_root_separation, contradicting s ≤ a+1 < q = 2^k (since i+1 < 3*q means a+1 < q). Thus b = a+1, which yields x p (i+1) = true.
uses
cycle_power_dyadic_full_prune_outer,cycle_power_dyadic_tight_class_middle_parent,cycle_power_dyadic_full_prune_root_separationhave hstepR (p : ℤ) (i : ℕ) (hi0 : 2^(k+1) ≤ i) (hi1 : i+1 < 2^(k+2)) (hx : x p i = true) : x p (i+1) = true := by by_cases hir : 3*q ≤ i · exact hright p i (i+1) hir (by omega) hi1 hx have hpf := hmid p i (by omega) (by omega) hx have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf by_cases hit : 3*q ≤ i+1 · exact hout.2 (i+1) hit hi1 let a := i-2^(k+1) have ha : a < q := by dsimp [a]; omega have hai : a+2^(k+1)=i := by dsimp [a]; omega have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).2 i hi0 (by omega) hx have hpa : x p a = true := hp have hpH : x p (a+2^(k+1)) = true := by simpa only [hai] using hx obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(a : ℤ)+1) have hbH : b < 2^(k+1) := by omega have hrt : p+(a : ℤ)-(a : ℤ)=p := by omega have hle := horder (p+(a : ℤ)) a b (by omega) hbH (by simpa only [hrt] using hpa) (by simpa only [hrt] using hpH) hb0 hb1 have hbf := hfull (p+(a : ℤ)+1-(b : ℤ)) b hbH hb0 hb1 have hba : b=a+1 := by by_contra hne let s := a+1-b have hs : 0 < s := by dsimp [s]; omega have hroot : p+(s : ℤ)=p+(a : ℤ)+1-(b : ℤ) := by dsimp [s]; omega have hsep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) p s hs hpf (by simpa only [hroot] using hbf) dsimp [s] at hsep omega have hroot : p+(a : ℤ)+1-(b : ℤ)=p := by omega have hindex : b+2^(k+1)=i+1 := by omega simpa only [hroot,hindex] using hb1
The left half [0, 2^(k+1)) is monotone toward 0: if a ≤ b < 2^(k+1) and x p b = true, then x p a = true.
Fix p. By induction on b starting from a using Nat.le_induction, the base case b = a is immediate, and the induction step applies the leftward step lemma hstepL to move from b+1 to b, then finishes by the induction hypothesis.
uses
Nat.le_inductionintro p constructor · intro a b hab hb hx have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+1) → x p b = true → x p a = true := by induction b,hab using Nat.le_induction with | base => intro _ hx; exact hx | succ b hab ih => intro hb hx exact ih (by omega) (hstepL p b hb hx) exact hmove b hab hb hx
The right half [2^(k+1), 2^(k+2)) is monotone toward the endpoint 2^(k+2): if 2^(k+1) ≤ a ≤ b < 2^(k+2) and x p a = true, then x p b = true.
By induction on b starting from a using Nat.le_induction, the base case b = a is given by the assumption, and the induction step applies the rightward step lemma hstepR to advance from b to b+1 using the induction hypothesis.
uses
Nat.le_induction· intro a b ha hab hb hx have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+2) → x p b = true := by induction b,hab using Nat.le_induction with | base => intro _; exact hx | succ b hab ih => intro hb exact hstepR p b (by omega) hb (ih (by omega)) exact hmove b hab hb
Nat.two_pow_pos- Powers of two are strictly positive: 0 < 2^w for any natural number w.
pow_succ- Successor power identity in a monoid: a^(n+1) = a^n * a.
cycle_power_dyadic_half_owner_full_prune_of_middle- If every middle mark on a path induces a full prune, then any half-owner (a pair of marks separated by 2^(k+1)) also has a full prune.
cycle_power_dyadic_half_owner_order_of_middle_full_prune- Under tightness, exact dyadic ownership, middle full pruning, outer monotonicity, and coverage, half-owners on adjacent diagonals satisfy the ordering b ≤ a + 1.
cycle_power_dyadic_full_prune_outer- A configuration with a full prune has all marks true in the outer quarters: for all i < 2^k and all 3*2^k ≤ i < 2^(k+2).
cycle_power_dyadic_tight_class_middle_parent- In a tight configuration, any mark in the second quarter [2^k, 2^(k+1)) is paired with a mark at a + 2^(k+1), and any mark in the third quarter [2^(k+1), 3*2^k) is paired with a mark at a - 2^(k+1).
cycle_power_dyadic_full_prune_root_separation- Under exact dyadic ownership, two distinct paths separated by r > 0 that both have full prunes must be separated by at least 2^k ≤ r.
Nat.le_induction- Induction principle for natural numbers: to prove P(n) for all n ≥ m, it suffices to prove P(m) and that P(n) implies P(n+1).
- In the contradiction steps pinning down the half-owner positions (lines 56 and 89), linear integer arithmetic (omega) derives False by combining the root separation lower bound 2^k ≤ s with the quarter-interval upper bound s < 2^k.
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_monotone_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 : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ, ∃ c : ℕ, c < 2^(k+2)-d ∧ x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+d) = true) : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^(k+1) → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2^(k+1) ≤ a → a ≤ b → b < 2^(k+2) → x p a = true → x p b = true) := 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 have horder := cycle_power_dyadic_half_owner_order_of_middle_full_prune k x htight hexact hmid hleft hright (hcover (2^(k+1)+1) (by omega) (by omega)) have hstepL (p : ℤ) (i : ℕ) (hi : i+1 < 2^(k+1)) (hx : x p (i+1) = true) : x p i = true := by by_cases hil : i+1 < q · exact hleft p i (i+1) (by omega) hil hx have hpf := hmid p (i+1) (by omega) (by omega) hx have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf by_cases hiq : i < q · exact hout.1 i hiq have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).1 (i+1) (by omega) hi hx obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(i : ℤ)) have hbH : b < 2^(k+1) := by omega have hrt : p+(i : ℤ)+1-((i+1 : ℕ) : ℤ)=p := by omega have hle := horder (p+(i : ℤ)) b (i+1) hbH hi hb0 hb1 (by simpa only [hrt] using hx) (by simpa only [hrt] using hp) have hib : i ≤ b := by omega have hbf := hfull (p+(i : ℤ)-(b : ℤ)) b hbH hb0 hb1 have hbi : b=i := by by_contra hne let s := b-i have hs : 0 < s := by dsimp [s]; omega have hroot : p+(i : ℤ)-(b : ℤ)+(s : ℤ)=p := by dsimp [s]; omega have hsep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) (p+(i : ℤ)-(b : ℤ)) s hs hbf (by simpa only [hroot] using hpf) dsimp [s] at hsep omega subst b simpa using hb0 have hstepR (p : ℤ) (i : ℕ) (hi0 : 2^(k+1) ≤ i) (hi1 : i+1 < 2^(k+2)) (hx : x p i = true) : x p (i+1) = true := by by_cases hir : 3*q ≤ i · exact hright p i (i+1) hir (by omega) hi1 hx have hpf := hmid p i (by omega) (by omega) hx have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf by_cases hit : 3*q ≤ i+1 · exact hout.2 (i+1) hit hi1 let a := i-2^(k+1) have ha : a < q := by dsimp [a]; omega have hai : a+2^(k+1)=i := by dsimp [a]; omega have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).2 i hi0 (by omega) hx have hpa : x p a = true := hp have hpH : x p (a+2^(k+1)) = true := by simpa only [hai] using hx obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(a : ℤ)+1) have hbH : b < 2^(k+1) := by omega have hrt : p+(a : ℤ)-(a : ℤ)=p := by omega have hle := horder (p+(a : ℤ)) a b (by omega) hbH (by simpa only [hrt] using hpa) (by simpa only [hrt] using hpH) hb0 hb1 have hbf := hfull (p+(a : ℤ)+1-(b : ℤ)) b hbH hb0 hb1 have hba : b=a+1 := by by_contra hne let s := a+1-b have hs : 0 < s := by dsimp [s]; omega have hroot : p+(s : ℤ)=p+(a : ℤ)+1-(b : ℤ) := by dsimp [s]; omega have hsep := cycle_power_dyadic_full_prune_root_separation k x (hexact k (by omega)) p s hs hpf (by simpa only [hroot] using hbf) dsimp [s] at hsep omega have hroot : p+(a : ℤ)+1-(b : ℤ)=p := by omega have hindex : b+2^(k+1)=i+1 := by omega simpa only [hroot,hindex] using hb1 intro p constructor · intro a b hab hb hx have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+1) → x p b = true → x p a = true := by induction b,hab using Nat.le_induction with | base => intro _ hx; exact hx | succ b hab ih => intro hb hx exact ih (by omega) (hstepL p b hb hx) exact hmove b hab hb hx · intro a b ha hab hb hx have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+2) → x p b = true := by induction b,hab using Nat.le_induction with | base => intro _; exact hx | succ b hab ih => intro hb exact hstepR p b (by omega) hb (ih (by omega)) exact hmove b hab hb