cycle_power_dyadic_half_monotone_of_full_class_cover
A tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately on its two halves.
Statement
theorem cycle_power_dyadic_half_monotone_of_full_class_cover (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun i => (x p i).toNat)) (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^(m-1) → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2^(m-1) ≤ a → a ≤ b → b < 2^m → 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 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_no_island_middle_imp_full_pruneIf a tight dyadic two-interval class contains any middle-quarter vertex, deleting the middle two quarters leaves a full smaller class.…
- 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_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_class_no_island_of_full_class_coverA positive-exponent integer dyadic rooted-class model with tight weights, exact dyadic pair ownership, all ordinary distance coverage, and…
- 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_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_middle_full_pruneIn a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no…
The proof, explained
The theorem is proved by strong induction on m ≥ 1. The base case m = 1 holds immediately because each half of the domain consists of a single point, making monotonicity trivial. For m = k + 2 ≥ 2, a structural 'no-island' property guarantees that any true value in the middle range $[2^k, 3 \cdot 2^k)$ forces the pruned configuration of order k + 1 (which removes that middle range) to be identically true everywhere. This pruned model inherits tightness, exactness, covering, and full-class covering, allowing the induction hypothesis to establish that it is half-monotone. Finally, this pruned half-monotonicity is lifted back to deduce half-monotonicity for the original model of order k + 2.
The proof proceeds by strong induction on m, separating the base case m < 2 from the inductive step m ≥ 2.
We apply strong induction on m, generalizing over the configuration x. A case distinction on 2 ≤ m isolates the base case m < 2 (which means m = 1 given 1 ≤ m), which is swapped to be treated first.
uses
Nat.strong_induction_oninduction m using Nat.strong_induction_on generalizing x with | h m ih => by_cases hm₂ : 2 ≤ m swap
The configuration x is half-monotone when m = 1.
When m = 1, the lower half $[0, 2^{m-1}) = [0, 1)$ contains only 0, so a ≤ b < 1 forces a = b = 0. Similarly, the upper half $[2^{m-1}, 2^m) = [1, 2)$ contains only 1, so 1 ≤ a ≤ b < 2 forces a = b = 1. In both cases a = b, so the monotonicity implications x(p, b) = true → x(p, a) = true and x(p, a) = true → x(p, b) = true are trivial equalities.
· have he : m = 1 := by omega subst m intro p constructor · intro a b hab hb hx have heq : a = b := by norm_num at hb; omega simpa only [heq] using hx · intro a b ha hab hb hx have heq : a = b := by norm_num at ha hb; omega simpa only [heq] using hx
Writing m = k + 2, the configuration x satisfies the no-island property.
For m ≥ 2, we set k = m - 2 so that m = k + 2. Lemma cycle_power_dyadic_class_no_island_of_full_class_cover shows that the hypotheses of tightness, exactness, covering, and full-class covering ensure no slice has an isolated island: whenever a < b < c < 2^(k+2), if x(p, a) = false and x(p, b) = true, then x(p, c) must be true.
uses
cycle_power_dyadic_class_no_island_of_full_class_coverobtain ⟨k, rfl⟩ : ∃ k, m = k+2 := ⟨m-2, by omega⟩ have hshape := cycle_power_dyadic_class_no_island_of_full_class_cover (k+2) (by omega) x htight hexact hcover hfullcover
If any middle index a ∈ [2^k, 3 · 2^k) is true in slice p, then the pruned lift of x(p) is identically true everywhere on $[0, 2^{k+1})$.
By lemma cycle_power_dyadic_no_island_middle_imp_full_prune, the combination of tightness and the no-island property implies that any true value in the middle half $[2^k, 3 \cdot 2^k)$ forces the pruned lift of the slice to evaluate to true at every index i < 2^(k+1).
uses
cycle_power_dyadic_no_island_middle_imp_full_prunehave 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 := by intro p a ha hb hx exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p) (hshape p) a ha hb hx
The pruned model y(p) = lift_k(x(p)) satisfies tightness, exactness, covering, and full-class covering at order k + 1.
We define y(p) to be the pruned configuration cycle_power_dyadic_b_lift k (x(p)). Tightness transfers to order k+1 via cycle_power_dyadic_tight_class_prune, exactness transfers via cycle_power_dyadic_prune_exact, and ordinary covering transfers via cycle_power_dyadic_prune_cover. Full-class covering at order k+1 follows from cycle_power_dyadic_prune_full_class_cover_of_middle_fullness, which uses the middle-fullness property hmid together with the half-cover property derived from exactness by cycle_power_dyadic_exact_half_cover.
uses
cycle_power_dyadic_tight_class_prune,cycle_power_dyadic_prune_exact,cycle_power_dyadic_prune_cover,cycle_power_dyadic_prune_full_class_cover_of_middle_fullness,cycle_power_dyadic_exact_half_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 have 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 on each slice.
Because k + 1 < k + 2 = m and 1 ≤ k + 1, we invoke the strong induction hypothesis ih on k + 1 and the pruned configuration y with its verified model properties. Simplifying the index (k + 1) - 1 to k with Nat.add_sub_cancel gives the half-monotonicity of the pruned model on both halves $[0, 2^k)$ and $[2^k, 2^{k+1})$.
uses
Nat.add_sub_cancelhave hprev := ih (k+1) (by omega) (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
The original model x is half-monotone on each slice, completing the induction.
Lemma cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono transfers half-monotonicity from the pruned model of order k + 1 back to the original model x of order k + 2, using middle-fullness, tightness, exactness, and ordinary covering. Simplifying (k + 2) - 1 to k + 1 closes the goal.
uses
cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_monosimpa only [show k+2-1=k+1 by omega] using cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono k x htight hexact hmid hcover hprev'
Nat.strong_induction_on- The strong induction principle on ℕ: to prove a property holds for all n, it suffices to show it holds for n assuming it holds for all m < n.
cycle_power_dyadic_class_no_island_of_full_class_cover- In a tight, exact, covered dyadic model with a full-class cover, each slice has no 'islands': any true value occurring after a false value cannot be followed by a false value later in the range.
cycle_power_dyadic_no_island_middle_imp_full_prune- For a tight configuration of order k+2 satisfying the no-island property, having any true value in the middle range $[2^k, 3 \cdot 2^k)$ implies its pruned lift is identically true on all indices below $2^{k+1}$.
cycle_power_dyadic_tight_class_prune- Pruning a tight configuration of order k+2 yields a tight configuration of order k+1.
cycle_power_dyadic_prune_exact- The pruned model of an exact dyadic model of order k+2 is exact at order k+1.
cycle_power_dyadic_prune_cover- The pruned model of a tight and ordinary-covered dyadic model of order k+2 satisfies the ordinary covering condition at order k+1.
cycle_power_dyadic_exact_half_cover- In an exact dyadic model of order k+2, every vertex has a shift a < 2^(k+1) where both a and a + 2^(k+1) are true.
cycle_power_dyadic_prune_full_class_cover_of_middle_fullness- If middle-truth forces the pruned configuration to be everywhere true and every vertex has a half-distance pair of true values, then the pruned model has a full class covering every vertex.
Nat.add_sub_cancel- For any natural numbers n and m, (n + m) - m = n.
cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono- If a tight, exact, covered dyadic model of order k+2 satisfies middle-fullness and its pruned model of order k+1 is half-monotone, then the original model is half-monotone at order k+2.
- The pruning operation `cycle_power_dyadic_b_lift k b` removes the middle two quarters $[2^k, 3 \cdot 2^k)$ of a length-$2^{k+2}$ configuration and concatenates the first and fourth quarters into a length-$2^{k+1}$ configuration.
- Arithmetic simplifications such as `Nat.add_sub_cancel` handle the formal book-keeping for the index $(k+1)-1 = 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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_half_monotone_of_full_class_cover (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun i => (x p i).toNat)) (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^(m-1) → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2^(m-1) ≤ a → a ≤ b → b < 2^m → x p a = true → x p b = true) := by induction m using Nat.strong_induction_on generalizing x with | h m ih => by_cases hm₂ : 2 ≤ m swap · have he : m = 1 := by omega subst m intro p constructor · intro a b hab hb hx have heq : a = b := by norm_num at hb; omega simpa only [heq] using hx · intro a b ha hab hb hx have heq : a = b := by norm_num at ha hb; omega simpa only [heq] using hx obtain ⟨k, rfl⟩ : ∃ k, m = k+2 := ⟨m-2, by omega⟩ have hshape := cycle_power_dyadic_class_no_island_of_full_class_cover (k+2) (by omega) x htight hexact hcover hfullcover have 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 := by intro p a ha hb hx exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p) (hshape p) a ha hb hx 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 := ih (k+1) (by omega) (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 simpa only [show k+2-1=k+1 by omega] using cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono k x htight hexact hmid hcover hprev'