cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune
A compatible hierarchy of tight exact full-coverage dyadic models has monotone endpoint halves at every level, provided every selected middle bit at EVERY level forces a full prune. This is a conditional all-scale classification, not a derivation of those fullness hypotheses from optimal counts.
Statement
theorem cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune (M : ℕ) (B : ℕ → ℤ → ℕ → Bool) (htight : ∀ r ≤ M, ∀ p, cycle_power_dyadic_class_weight (r+1) (B r p) = (range (2^(r+1))).sum (fun a => (B r p a).toNat)) (hexact : ∀ r ≤ M, ∀ j < r+1, ∀ v : ℤ, (range (2^j)).sum (fun a => (B r (v-(a : ℤ)) a && B r (v-(a : ℤ)) (a+2^(r+1)-2^j)).toNat) = 1) (hcover : ∀ r ≤ M, ∀ d : ℕ, 1 ≤ d → d < 2^(r+1) → ∀ v : ℤ, ∃ c : ℕ, c < 2^(r+1)-d ∧ B r (v-(c : ℤ)) c = true ∧ B r (v-(c : ℤ)) (c+d) = true) (hprune : ∀ r < M, ∀ p a, B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a) (hmid : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r → B (r+1) p a = true → ∀ i < 2^(r+1), B r p i = true) : ∀ r ≤ M, ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^r → B r p b = true → B r p a = true) ∧ (∀ a b : ℕ, 2^r ≤ a → a ≤ b → b < 2^(r+1) → B r p a = true → B r 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 3
- 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_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,…
- 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_of_outer_projection_fullnessA tight exact full-coverage model has no-island class shape if every selected middle bit at EVERY direct outer projection level forces the…
The proof, explained
The theorem is proved by mathematical induction on the scale r ≤ M. At the base scale r = 0, the left and right intervals are singletons, so downward and upward monotonicity hold vacuously. In the inductive step from r to r+1, the induction hypothesis ensures that the outer quarters of B (r+1) p are monotone, while the hypothesis hmid guarantees that any selected middle bit forces a full prune on the lifted model. The inductive step is completed by invoking the single-scale propagation theorem cycle_power_dyadic_half_monotone_of_middle_full_prune, which promotes the quarter-monotonicity of B (r+1) p to half-monotonicity at scale r+1.
We induct on the scale r.
We introduce the dyadic scale r and set up mathematical induction on r to prove the half-monotonicity property for all r ≤ M and all phases p ∈ ℤ.
intro r induction r with
The monotonicity conditions hold at the base scale r = 0.
At scale r = 0, the left interval is [0, 2^0) = {0}, so a ≤ b < 1 forces a = b = 0, making downward monotonicity B 0 p b = true → B 0 p a = true trivial. Similarly, the right interval is [2^0, 2^1) = {1}, so 1 ≤ a ≤ b < 2 forces a = b = 1, making upward monotonicity B 0 p a = true → B 0 p b = true trivial. Both branches are closed by norm_num and omega.
| zero => intro hr p constructor · intro a b hab hb hx norm_num at hb have he : a=b := by omega simpa only [he] using hx · intro a b ha hab hb hx norm_num at ha hb have he : a=b := by omega simpa only [he] using hxAssume r+1 ≤ M, establish the dyadic power identities, and identify B r p as the dyadic lift of B (r+1) p.
In the inductive step, we assume the induction hypothesis for r and assume r + 1 ≤ M, which gives r < M. We express 2^(r+1) = 2 * 2^r and 2^(r+2) = 4 * 2^r using pow_succ. Applying hypothesis hprune and function extensionality, B r p equals the dyadic lift cycle_power_dyadic_b_lift r (B (r+1) p), which retains the left quarter [0, 2^r) and right quarter [3*2^r, 4*2^r) while removing the middle half [2^r, 3*2^r).
uses
pow_succ| succ r ih => intro hr have hrM : r < M := by omega have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega have hD : 2^(r+2)=4*2^r := by rw [show r+2=(r+1)+1 by omega,pow_succ,hH]; omega have hB (p : ℤ) : B r p = cycle_power_dyadic_b_lift r (B (r+1) p) := funext (hprune r hrM p)B (r+1) p is monotone downward on the initial quarter [0, 2^r).
For a ≤ b < 2^r, the definition of the dyadic lift gives B r p a = B (r+1) p a and B r p b = B (r+1) p b. The induction hypothesis at scale r ensures that B r p is downward monotone on [0, 2^r); transferring this to B (r+1) p yields B (r+1) p b = true → B (r+1) p a = true.
have hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^r → B (r+1) p b = true → B (r+1) p a = true := by intro p a b hab hb hx have ha : a < 2^r := by omega have hla : B r p a = B (r+1) p a := by rw [hB]; simp [cycle_power_dyadic_b_lift,ha] have hlb : B r p b = B (r+1) p b := by rw [hB]; simp [cycle_power_dyadic_b_lift,hb] rw [← hla] exact (ih (by omega) p).1 a b hab hb (by simpa only [hlb] using hx)
B (r+1) p is monotone upward on the final quarter [3*2^r, 2^(r+2)).
For 3*2^r ≤ a ≤ b < 2^(r+2) = 4*2^r, subtracting 2^(r+1) yields indices u = a - 2^(r+1) and v = b - 2^(r+1) with 2^r ≤ u ≤ v < 2^(r+1). Since u, v ≥ 2^r, the else branch of the lift definition applies (evaluated via if_neg), giving B r p u = B (r+1) p a and B r p v = B (r+1) p b. By the induction hypothesis at scale r, B r p is upward monotone on [2^r, 2^(r+1)), which implies B (r+1) p a = true → B (r+1) p b = true.
uses
if_neghave hright : ∀ (p : ℤ) (a b : ℕ), 3*2^r ≤ a → a ≤ b → b < 2^(r+2) → B (r+1) p a = true → B (r+1) p b = true := by intro p a b ha hab hb hx let u := a-2^(r+1) let v := b-2^(r+1) have hu0 : 2^r ≤ u := by dsimp [u]; omega have huv : u ≤ v := by dsimp [u,v]; omega have hv : v < 2^(r+1) := by dsimp [v]; omega have hua : u+2^(r+1)=a := by dsimp [u]; omega have hvb : v+2^(r+1)=b := by dsimp [v]; omega have hla : B r p u = B (r+1) p a := by rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬u<2^r),hua] have hlb : B r p v = B (r+1) p b := by rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬v<2^r),hvb] rw [← hlb] exact (ih (by omega) p).2 u v hu0 huv hv (by simpa only [hla] using hx)
Any active middle bit of B (r+1) p forces its dyadic lift to be identically true on [0, 2^(r+1)).
If B (r+1) p a = true for some middle index a ∈ [2^r, 3*2^r), hypothesis hmid implies B r p i = true for every i < 2^(r+1). Rewriting B r p via hprune shows that the lifted bitmask cycle_power_dyadic_b_lift r (B (r+1) p) is identically true for all i < 2^(r+1).
have hmf : ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r → B (r+1) p a = true → ∀ i < 2^(r+1), cycle_power_dyadic_b_lift r (B (r+1) p) i = true := by intro p a ha hb hx i hi rw [← hprune r hrM p i] exact hmid r hrM p a ha hb hx i hi
B (r+1) p is monotone downward on [0, 2^(r+1)) and upward on [2^(r+1), 2^(r+2)).
We apply the single-scale propagation theorem cycle_power_dyadic_half_monotone_of_middle_full_prune at scale k = r to B (r+1). Hypotheses htight, hexact, and hcover at level r+1 ≤ M supply the scale r+2 tightness, exactness, and coverage requirements. Together with middle pruning hmf, left-quarter monotonicity hleft, and right-quarter monotonicity hright, the lemma concludes that B (r+1) p is downward monotone on [0, 2^(r+1)) and upward monotone on [2^(r+1), 2^(r+2)), completing the inductive step.
uses
cycle_power_dyadic_half_monotone_of_middle_full_pruneexact cycle_power_dyadic_half_monotone_of_middle_full_prune r (B (r+1)) (htight (r+1) (by omega)) (hexact (r+1) (by omega)) hmf hleft hright (hcover (r+1) (by omega))
pow_succ- For any element a of a monoid and natural number n, a^(n+1) = a^n * a; in particular, 2^(n+1) = 2^n * 2.
if_neg- If a proposition c is false, the conditional expression (if c then t else e) evaluates to the else branch e.
cycle_power_dyadic_half_monotone_of_middle_full_prune- For a dyadic bitmask at scale k+2 satisfying tightness, exactness, and coverage, if any active middle bit in [2^k, 3*2^k) forces the lifted model at scale k+1 to be identically true, and the outer quarters [0, 2^k) and [3*2^k, 2^(k+2)) are monotone downward and upward respectively, then the bitmask is monotone downward on [0, 2^(k+1)) and monotone upward on [2^(k+1), 2^(k+2)).
- The base case r = 0 is degenerate: the left interval [0, 1) and right interval [1, 2) are singletons, so the monotonicity conditions are discharged by omega and norm_num without non-trivial arithmetic.
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_hierarchy_half_monotone_of_middle_full_prune (M : ℕ) (B : ℕ → ℤ → ℕ → Bool) (htight : ∀ r ≤ M, ∀ p, cycle_power_dyadic_class_weight (r+1) (B r p) = (range (2^(r+1))).sum (fun a => (B r p a).toNat)) (hexact : ∀ r ≤ M, ∀ j < r+1, ∀ v : ℤ, (range (2^j)).sum (fun a => (B r (v-(a : ℤ)) a && B r (v-(a : ℤ)) (a+2^(r+1)-2^j)).toNat) = 1) (hcover : ∀ r ≤ M, ∀ d : ℕ, 1 ≤ d → d < 2^(r+1) → ∀ v : ℤ, ∃ c : ℕ, c < 2^(r+1)-d ∧ B r (v-(c : ℤ)) c = true ∧ B r (v-(c : ℤ)) (c+d) = true) (hprune : ∀ r < M, ∀ p a, B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a) (hmid : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r → B (r+1) p a = true → ∀ i < 2^(r+1), B r p i = true) : ∀ r ≤ M, ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^r → B r p b = true → B r p a = true) ∧ (∀ a b : ℕ, 2^r ≤ a → a ≤ b → b < 2^(r+1) → B r p a = true → B r p b = true) := by intro r induction r with | zero => intro hr p constructor · intro a b hab hb hx norm_num at hb have he : a=b := by omega simpa only [he] using hx · intro a b ha hab hb hx norm_num at ha hb have he : a=b := by omega simpa only [he] using hx | succ r ih => intro hr have hrM : r < M := by omega have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega have hD : 2^(r+2)=4*2^r := by rw [show r+2=(r+1)+1 by omega,pow_succ,hH]; omega have hB (p : ℤ) : B r p = cycle_power_dyadic_b_lift r (B (r+1) p) := funext (hprune r hrM p) have hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^r → B (r+1) p b = true → B (r+1) p a = true := by intro p a b hab hb hx have ha : a < 2^r := by omega have hla : B r p a = B (r+1) p a := by rw [hB]; simp [cycle_power_dyadic_b_lift,ha] have hlb : B r p b = B (r+1) p b := by rw [hB]; simp [cycle_power_dyadic_b_lift,hb] rw [← hla] exact (ih (by omega) p).1 a b hab hb (by simpa only [hlb] using hx) have hright : ∀ (p : ℤ) (a b : ℕ), 3*2^r ≤ a → a ≤ b → b < 2^(r+2) → B (r+1) p a = true → B (r+1) p b = true := by intro p a b ha hab hb hx let u := a-2^(r+1) let v := b-2^(r+1) have hu0 : 2^r ≤ u := by dsimp [u]; omega have huv : u ≤ v := by dsimp [u,v]; omega have hv : v < 2^(r+1) := by dsimp [v]; omega have hua : u+2^(r+1)=a := by dsimp [u]; omega have hvb : v+2^(r+1)=b := by dsimp [v]; omega have hla : B r p u = B (r+1) p a := by rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬u<2^r),hua] have hlb : B r p v = B (r+1) p b := by rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬v<2^r),hvb] rw [← hlb] exact (ih (by omega) p).2 u v hu0 huv hv (by simpa only [hla] using hx) have hmf : ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r → B (r+1) p a = true → ∀ i < 2^(r+1), cycle_power_dyadic_b_lift r (B (r+1) p) i = true := by intro p a ha hb hx i hi rw [← hprune r hrM p i] exact hmid r hrM p a ha hb hx i hi exact cycle_power_dyadic_half_monotone_of_middle_full_prune r (B (r+1)) (htight (r+1) (by omega)) (hexact (r+1) (by omega)) hmf hleft hright (hcover (r+1) (by omega))