cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono
Current middle-bit fullness and monotonicity of both halves of the pruned model imply monotonicity of both original halves, in a tight exact full ordinary-cover model.
Statement
theorem cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono (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) (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) (hpruned : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true → cycle_power_dyadic_b_lift k (x p) a = true) ∧ (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) → cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = 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 full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 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 2
- cycle_power_dyadic_no_island_of_middle_full_pruneIn a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no…
- cycle_power_dyadic_half_monotone_of_full_class_coverA tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately…
The proof, explained
The theorem reduces monotonicity of both dyadic halves of the original model to monotonicity on the outer fringe intervals [0, 2^k) and [3 * 2^k, 2^(k+2)) using `cycle_power_dyadic_half_monotone_of_middle_full_prune`. By the definition of `cycle_power_dyadic_b_lift`, the lower fringe [0, 2^k) corresponds directly to the first half of the pruned model, while the upper fringe [3 * 2^k, 2^(k+2)) shifts by 2^(k+1) to the second half [2^k, 2^(k+1)) of the pruned model. The assumed monotonicity of both halves of the pruned model (`hpruned`) therefore implies monotonicity on both fringes, which combined with the cover condition proves the theorem.
2^(k+1) = 2 * 2^k and 2^(k+2) = 4 * 2^k.
We rewrite the power operations using `pow_succ` to expand 2^(k+1) = 2^k * 2 and 2^(k+2) = 2^(k+1) * 2, and close the arithmetic goals with `omega`.
uses
pow_succhave hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega have hD : 2^(k+2)=4*2^k := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega
It suffices to prove monotonicity on the lower fringe [0, 2^k) and the upper fringe [3 * 2^k, 2^(k+2)), alongside the cover condition.
We apply `cycle_power_dyadic_half_monotone_of_middle_full_prune`, which reduces monotonicity of both full halves of the original configuration to monotonicity on the fringe intervals [0, 2^k) and [3 * 2^k, 2^(k+2)), supplying the tightness, exactness, and middle-bit fullness hypotheses directly.
uses
cycle_power_dyadic_half_monotone_of_middle_full_pruneapply cycle_power_dyadic_half_monotone_of_middle_full_prune k x htight hexact hmidMonotonicity holds on the lower fringe: for any a ≤ b < 2^k, if x(p)(b) = true then x(p)(a) = true.
Since b < 2^k and a ≤ b, linear arithmetic gives a < 2^k. On indices below 2^k, the lifted configuration `cycle_power_dyadic_b_lift` agrees with the original x(p) by `if_pos`. Thus x(p)(b) = true implies the pruned lift is true at b. The first half of the pruned monotonicity hypothesis `hpruned` gives that the pruned lift is true at a, which simplifies via `if_pos` to x(p)(a) = true.
uses
cycle_power_dyadic_b_lift,if_pos· intro p a b hab hb hx have ha : a < 2^k := by omega have hh := (hpruned p).1 a b hab hb (by simpa only [cycle_power_dyadic_b_lift, if_pos hb] using hx) simpa only [cycle_power_dyadic_b_lift, if_pos ha] using hh
Monotonicity holds on the upper fringe: for any 3 * 2^k ≤ a ≤ b < 2^(k+2), if x(p)(a) = true then x(p)(b) = true.
We shift indices by subtracting 2^(k+1), setting a' = a - 2^(k+1) and b' = b - 2^(k+1). Linear arithmetic (`omega`) shows that 2^k ≤ a' ≤ b' < 2^(k+1), that neither a' nor b' is strictly less than 2^k, and that adding 2^(k+1) recovers a and b. By `if_neg`, `cycle_power_dyadic_b_lift` at a' equals x(p)(a). The second half of `hpruned` ensures the pruned lift is true at b', which simplifies via `if_neg` to x(p)(b) = true.
uses
cycle_power_dyadic_b_lift,if_neg· intro p a b ha₀ hab hbD hx have ha' : 2^k ≤ a-2^(k+1) := by omega have hab' : a-2^(k+1) ≤ b-2^(k+1) := by omega have hb' : b-2^(k+1) < 2^(k+1) := by omega have hna : ¬a-2^(k+1) < 2^k := by omega have hnb : ¬b-2^(k+1) < 2^k := by omega have hea : a-2^(k+1)+2^(k+1) = a := by omega have heb : b-2^(k+1)+2^(k+1) = b := by omega have hh := (hpruned p).2 (a-2^(k+1)) (b-2^(k+1)) ha' hab' hb' (by simpa only [cycle_power_dyadic_b_lift, if_neg hna, hea] using hx) simpa only [cycle_power_dyadic_b_lift, if_neg hnb, heb] using hh
The cover condition is satisfied, completing the proof.
The remaining premise required by `cycle_power_dyadic_half_monotone_of_middle_full_prune` is the ordinary-cover property, which matches the assumption `hcover` directly.
· exact hcover
cycle_power_dyadic_half_monotone_of_middle_full_prune- In a tight, exact dyadic model with middle-bit fullness and the ordinary-cover property, monotonicity of the fringe intervals [0, 2^k) and [3 * 2^k, 2^(k+2)) implies monotonicity of both dyadic halves [0, 2^(k+1)) and [2^(k+1), 2^(k+2)).
cycle_power_dyadic_b_lift- The lifted Boolean configuration at scale k, which maps index i to b(i) if i < 2^k, and to b(i + 2^(k+1)) otherwise.
pow_succ- For any base a and natural number n, a^(n + 1) = a^n * a.
if_pos- If condition c is true, then (if c then t else e) simplifies to t.
if_neg- If condition c is false, then (if c then t else e) simplifies to e.
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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono (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) (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) (hpruned : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true → cycle_power_dyadic_b_lift k (x p) a = true) ∧ (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) → cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = 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 have hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega have hD : 2^(k+2)=4*2^k := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega apply cycle_power_dyadic_half_monotone_of_middle_full_prune k x htight hexact hmid · intro p a b hab hb hx have ha : a < 2^k := by omega have hh := (hpruned p).1 a b hab hb (by simpa only [cycle_power_dyadic_b_lift, if_pos hb] using hx) simpa only [cycle_power_dyadic_b_lift, if_pos ha] using hh · intro p a b ha₀ hab hbD hx have ha' : 2^k ≤ a-2^(k+1) := by omega have hab' : a-2^(k+1) ≤ b-2^(k+1) := by omega have hb' : b-2^(k+1) < 2^(k+1) := by omega have hna : ¬a-2^(k+1) < 2^k := by omega have hnb : ¬b-2^(k+1) < 2^k := by omega have hea : a-2^(k+1)+2^(k+1) = a := by omega have heb : b-2^(k+1)+2^(k+1) = b := by omega have hh := (hpruned p).2 (a-2^(k+1)) (b-2^(k+1)) ha' hab' hb' (by simpa only [cycle_power_dyadic_b_lift, if_neg hna, hea] using hx) simpa only [cycle_power_dyadic_b_lift, if_neg hnb, heb] using hh · exact hcover