cycle_power_dyadic_no_island_of_middle_full_prune
In a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no selected island between missing offsets. Smaller-scale fullness and active-count hypotheses are not assumed.
Statement
theorem cycle_power_dyadic_no_island_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) (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) : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) → x p a = false → x p b = true → x p c = 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 10
- 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_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
- cycle_power_dyadic_prune_exactDeleting the middle two quarters of every class preserves every smaller-scale exact dyadic long-edge count, without changing the class…
- cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
- cycle_power_dyadic_prune_full_class_cover_of_middle_fullnessCurrent-scale middle-bit fullness ensures that every vertex of the pruned model lies in a full pruned class. Fullness and half-distance…
- cycle_power_no_island_of_half_monotoneA Boolean class which is monotone toward the left endpoint on the left half and toward the right endpoint on the right half has no…
- cycle_power_dyadic_exact_half_coverExact dyadic pair ownership supplies a witness covering every edge at half the radius, with the distance normalized to a power of two.
- 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…
- 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…
- 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.
The proof, explained
The proof reduces the problem from scale k + 2 to scale k + 1 by considering the pruned lift y(p) = cycle_power_dyadic_b_lift k (x p). The pruned model inherits tightness, exactness, and ordinary cover, while middle-bit fullness converts the half-distance exact cover of the original model into a full class cover for y. Applying a classification theorem establishes that the pruned model is half-monotone, which lifts back to half-monotonicity of x at scale k + 2; from half-monotonicity, the absence of isolated true islands is immediate.
The pruned model y at scale k + 1 inherits tightness, exactness, and the ordinary cover property from x.
We define y(p) = cycle_power_dyadic_b_lift k (x p) as the pruned lift of each class at scale k + 1 (line 17). By cycle_power_dyadic_tight_class_prune, each class of y inherits tightness from the tightness of x at scale k + 2 (line 18). By cycle_power_dyadic_prune_exact, y inherits exactness for all scales j < k + 1 (line 19). By cycle_power_dyadic_prune_cover, the ordinary cover property for all distances 1 ≤ d < 2^(k + 1) transfers from x to y (line 20).
uses
cycle_power_dyadic_tight_class_prune,cycle_power_dyadic_prune_exact,cycle_power_dyadic_prune_coverlet y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p) have hyt := fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p) have hye := cycle_power_dyadic_prune_exact k x hexact have hyc := cycle_power_dyadic_prune_cover k x htight hcover
The pruned model y satisfies the full class cover property at scale k + 1.
By cycle_power_dyadic_exact_half_cover, the exactness of x guarantees that every line v contains an active pair separated by distance 2^(k + 1) (line 22). Because this separation reaches into the middle range, cycle_power_dyadic_prune_full_class_cover_of_middle_fullness uses the middle-bit fullness hypothesis (hmid) to deduce that every line v intersects a class whose pruned lift is identically true across the entire range [0, 2^(k + 1)) (line 21).
uses
cycle_power_dyadic_prune_full_class_cover_of_middle_fullness,cycle_power_dyadic_exact_half_coverhave hyf := cycle_power_dyadic_prune_full_class_cover_of_middle_fullness k x hmid (cycle_power_dyadic_exact_half_cover k x hexact)The pruned model y is half-monotone at scale k + 1.
With 1 ≤ k + 1 verified by linear arithmetic (omega on line 24), y satisfies all hypotheses of cycle_power_dyadic_half_monotone_of_full_class_cover: tightness (hyt), exactness (hye), ordinary cover (hyc), and full class cover (hyf). Therefore, for every class p, y(p) is decreasing on [0, 2^k) and increasing on [2^k, 2^(k + 1)) (line 23).
uses
cycle_power_dyadic_half_monotone_of_full_class_coverhave hprev := cycle_power_dyadic_half_monotone_of_full_class_cover (k+1) (by omega) y hyt hye hyc hyf
The pruned lift cycle_power_dyadic_b_lift k (x p) is explicitly decreasing on [0, 2^k) and increasing on [2^k, 2^(k + 1)).
We unfold the definition of y and simplify the exponent (k + 1) - 1 to k using Nat.add_sub_cancel via simpa, restating the half-monotonicity directly in terms of the lift of x (lines 25–30).
uses
Nat.add_sub_cancelhave hprev' : ∀ 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) := by simpa only [y, Nat.add_sub_cancel] using hprev
For every class p and offsets a < b < c < 2^(k + 2), if x(p, a) = false and x(p, b) = true, then x(p, c) = true.
Using cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono, the half-monotonicity of the pruned lift (hprev') combines with middle-bit fullness and the scale k + 2 properties to prove that x itself is half-monotone at scale k + 2, split at 2^(k + 1) (lines 32–33). Then cycle_power_no_island_of_half_monotone with threshold H = 2^(k + 1) and length D = 2^(k + 2) concludes that no class can possess an isolated true value: once a value becomes true after a false bit, all subsequent bits must remain true (line 31).
uses
cycle_power_no_island_of_half_monotone,cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_monoexact cycle_power_no_island_of_half_monotone (2^(k+1)) (2^(k+2)) x (cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono k x htight hexact hmid hcover hprev')
cycle_power_dyadic_tight_class_prune- If a class is tight at scale k + 2, its pruned lift at scale k is tight at scale k + 1.
cycle_power_dyadic_prune_exact- If a model is exact at scale k + 2, its pruned lift is exact at scale k + 1.
cycle_power_dyadic_prune_cover- If a model is tight and satisfies ordinary cover at scale k + 2, its pruned lift satisfies ordinary cover at scale k + 1.
cycle_power_dyadic_exact_half_cover- In an exact model at scale k + 2, every line contains a pair of active bits separated by distance 2^(k + 1).
cycle_power_dyadic_prune_full_class_cover_of_middle_fullness- In a model with middle-bit fullness and a half-distance cover, every line intersects a class whose pruned lift is identically true on all offsets up to 2^(k + 1).
cycle_power_dyadic_half_monotone_of_full_class_cover- A tight, exact model at scale m ≥ 1 with ordinary cover and full class cover is half-monotone (decreasing on [0, 2^(m - 1)) and increasing on [2^(m - 1), 2^m)).
Nat.add_sub_cancel- For natural numbers n and m, (n + m) - m = n.
cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono- If the pruned lift of a tight, exact, cover-satisfying model with middle-bit fullness is half-monotone at scale k + 1, then the model itself is half-monotone at scale k + 2.
cycle_power_no_island_of_half_monotone- A sequence that is decreasing on [0, H) and increasing on [H, D) cannot contain an isolated true bit between false bits: if a < b < c < D with x(a) = false and x(b) = true, then x(c) = true.
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_no_island_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) (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) : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) → x p a = false → x p b = true → x p c = true := by let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p) have hyt := fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p) have hye := cycle_power_dyadic_prune_exact k x hexact have hyc := cycle_power_dyadic_prune_cover k x htight hcover have hyf := cycle_power_dyadic_prune_full_class_cover_of_middle_fullness k x hmid (cycle_power_dyadic_exact_half_cover k x hexact) have hprev := cycle_power_dyadic_half_monotone_of_full_class_cover (k+1) (by omega) y hyt hye hyc hyf have hprev' : ∀ 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) := by simpa only [y, Nat.add_sub_cancel] using hprev exact cycle_power_no_island_of_half_monotone (2^(k+1)) (2^(k+2)) x (cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono k x htight hexact hmid hcover hprev')