cycle_power_dyadic_model_dvd_of_endpoint_overlap
A periodic optimal dyadic class model whose old active classes intersect the next endpoint class has period divisible by the dyadic radius. The overlap condition remains an explicit hypothesis.
Statement
theorem cycle_power_dyadic_model_dvd_of_endpoint_overlap (m n : ℕ) (hm : 2 ≤ m) (hn : 0 < n) (x : ℤ → ℕ → Bool) (ell : ℤ → Fin (m+1)) (hperiod : ∀ p a, x (p+(n : ℤ)) a = x p a) (hell : ∀ p, ell (p+(n : ℤ)) = ell p) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun a => (x p a).toNat)) (hcount : ∀ v : ℤ, (range (2^m)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = m+1) (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) (hsep : ∀ (v : ℤ) (a b : ℕ), a < 2^m → b < 2^m → a ≠ b → x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true → ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ))) (hoverlap : ∀ (p : ℤ) (q : ℕ), 1 ≤ q → q < 2^m → x (p+(q : ℤ)) (2^m-1-q) = true → ∃ a : ℕ, a < q ∧ x (p+(q : ℤ)) (2^m-q+a) = true ∧ x (p+((2^m : ℕ) : ℤ)) a = true) : 2^m ∣ n
- Source
- Uniform helpers for OP-205 / RT-1 following arXiv:2610.15635, Section 3. The neighbour-weight induction and central occurrence are class-model helpers; they do not prove the unresolved covering number. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- cycle_power_dyadic_central_position_existsIn a periodic tight dyadic class model with exact dyadic coverage and coverage at all lower neighbour distances, some class uses one of…
- periodic_dyadic_dvd_of_half_shift_neIf a function on the integers has periods n and 2^(m+1), and some values differ after shifting by 2^m, then 2^(m+1) divides n.
- cycle_power_class_label_period_of_bounded_endpoint_overlapFor bounded Boolean classes with complete distinct palettes, endpoint overlap forces the root labels to repeat after the class radius.
- cycle_power_dyadic_model_dvd_of_label_periodA finite-period tight dyadic class model with proper labels, exact dyadic edges, neighbour coverage, and full-radius label period has…
- 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.
- Used by 1
- cycle_power_dyadic_model_dvd_of_no_islandA periodic optimally counted tight dyadic class model with proper class labels, exact dyadic edges and full ordinary coverage has period…
The proof, explained
The proof establishes that the dyadic radius 2^m divides the period n by reducing to `cycle_power_dyadic_model_dvd_of_label_period`. First, the endpoint overlap hypothesis ensures that the class labeling function ell is periodic with period 2^m via `cycle_power_class_label_period_of_bounded_endpoint_overlap`. To discharge the remaining premise of the divisibility theorem, it suffices to prove a coverage condition at each dyadic scale 1 ≤ j < m. This is achieved by specializing the general coverage hypothesis `hcover` to the distance d = 2^m - 2^j - 1, using bounds on powers of two to verify that 1 ≤ d < 2^m and that the resulting bound on the index simplifies to 2^j + 1.
The class labeling function ell is periodic with period 2^m.
We apply `cycle_power_class_label_period_of_bounded_endpoint_overlap` with diameter D = 2^m and fiber size t = m + 1. The hypotheses are provided by the theorem's assumptions: `hcount` ensures the fiber sum condition, `hsep` ensures that active classes receive distinct labels, and `hoverlap` guarantees the endpoint overlap condition.
uses
cycle_power_class_label_period_of_bounded_endpoint_overlaphave hlabel := cycle_power_class_label_period_of_bounded_endpoint_overlap (2^m) (m+1) x ell hcount hsep hoverlapIt suffices to verify the dyadic scale coverage condition: for every scale 1 ≤ j < m and vertex v, there exists a < 2^j + 1 such that x(v - a, a) = true and x(v - a, a + 2^m - 2^j - 1) = true.
We apply `cycle_power_dyadic_model_dvd_of_label_period`. All of its required hypotheses—the dimension bound 2 ≤ m, positivity 0 < n, n-periodicity of x and ell, 2^m-periodicity of ell (`hlabel`), weight tightness (`htight`), exactness of dyadic intersections (`hexact`), and label separation (`hsep`)—are satisfied, leaving only the scale-specific coverage property to be proved.
uses
cycle_power_dyadic_model_dvd_of_label_periodapply cycle_power_dyadic_model_dvd_of_label_period m n hm hn x ell hperiod hell hlabel htight hexact _ hsepFor any scale 1 ≤ j < m and vertex v, the distance d = 2^m - 2^j - 1 satisfies 1 ≤ d < 2^m.
Fix j with 1 ≤ j < m and a vertex v. Since j ≤ m - 1, power monotonicity (`Nat.pow_le_pow_right`) yields 2^j ≤ 2^(m - 1). Factoring 2^m = 2 * 2^(m - 1) via `pow_succ` and using 2 ≤ 2^(m - 1), linear arithmetic confirms 1 ≤ 2^m - 2^j - 1. For the upper bound, since 2^m > 0 and 2^j > 0 (`Nat.two_pow_pos`), subtracting 2^j strictly decreases 2^m (`Nat.sub_lt`), and subtracting 1 further preserves being strictly less than 2^m by transitivity with `Nat.sub_le` and `lt_of_le_of_lt`.
uses
Nat.pow_le_pow_right,pow_succ,Nat.two_pow_pos,Nat.sub_lt,Nat.sub_le,lt_of_le_of_ltintro j hj0 hj v have hjp : 2^j ≤ 2^(m-1) := Nat.pow_le_pow_right (by decide) (by omega) have hpow : 2^m=2*2^(m-1) := by conv_lhs => rw [show m=(m-1)+1 by omega] rw [pow_succ]; omega have htwo : 2 ≤ 2^(m-1) := by calc 2 = 2^1 := rfl _ ≤ _ := Nat.pow_le_pow_right (by decide) (by omega) have hdpos : 1 ≤ 2^m-2^j-1 := by rw [hpow]; omega have hdlt : 2^m-2^j-1 < 2^m := lt_of_le_of_lt (Nat.sub_le _ _) (Nat.sub_lt (Nat.two_pow_pos m) (Nat.two_pow_pos j))
There exists an index a < 2^m - (2^m - 2^j - 1) such that x(v - a, a) = true and x(v - a, a + (2^m - 2^j - 1)) = true.
We instantiate the general coverage hypothesis `hcover` at distance d = 2^m - 2^j - 1 and vertex v, which is valid because 1 ≤ d < 2^m was just verified.
obtain ⟨a, ha, hx0, hx1⟩ := hcover (2^m-2^j-1) hdpos hdlt vThe index a witnesses the dyadic scale coverage condition at scale j.
Because 2^j + 1 ≤ 2^m, natural number subtraction simplifies 2^m - (2^m - 2^j - 1) to 2^j + 1, so the bound on a becomes a < 2^j + 1. Associativity of addition and subtraction gives a + 2^m - 2^j - 1 = a + (2^m - 2^j - 1). Substituting this into the second truth condition confirms that a satisfies both requirements.
have hlarge : 2^j+1 ≤ 2^m := by rw [hpow]; omega have hrange : 2^m-(2^m-2^j-1)=2^j+1 := by omega rw [hrange] at ha refine ⟨a, ha, hx0, ?_⟩ have hi : a+2^m-2^j-1=a+(2^m-2^j-1) := by omega rw [hi] exact hx1
cycle_power_class_label_period_of_bounded_endpoint_overlap- For a configuration with diameter D and fiber count t, if column sums equal t, distinct active classes have distinct labels, and boundary active classes overlap with the next endpoint class, then the label function is periodic with period D.
cycle_power_dyadic_model_dvd_of_label_period- In an m-dimensional dyadic model (m ≥ 2) with period n > 0, if the model has tight weights, exact dyadic intersections, dyadic coverage at scales 1 ≤ j < m, label separation, and the label function has period 2^m, then 2^m divides n.
Nat.pow_le_pow_right- For a base n > 0, exponentiation is monotonically increasing: if i ≤ j, then n^i ≤ n^j.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
lt_of_le_of_lt- In a preorder, if a ≤ b and b < c, then a < c.
Nat.sub_le- For any natural numbers n and m, n - m ≤ n.
Nat.sub_lt- Subtracting a strictly positive natural number from another strictly positive natural number yields a strictly smaller result: if 0 < n and 0 < m, then n - m < n.
Nat.two_pow_pos- For every natural number w, 2^w > 0.
- Natural number subtraction in Lean truncates at zero, so algebraic simplifications such as $2^m - (2^m - 2^j - 1) = 2^j + 1$ and $a + 2^m - 2^j - 1 = a + (2^m - 2^j - 1)$ require explicit inequality bounds verified by linear arithmetic automation (`omega`).
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_model_dvd_of_endpoint_overlap (m n : ℕ) (hm : 2 ≤ m) (hn : 0 < n) (x : ℤ → ℕ → Bool) (ell : ℤ → Fin (m+1)) (hperiod : ∀ p a, x (p+(n : ℤ)) a = x p a) (hell : ∀ p, ell (p+(n : ℤ)) = ell p) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun a => (x p a).toNat)) (hcount : ∀ v : ℤ, (range (2^m)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = m+1) (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) (hsep : ∀ (v : ℤ) (a b : ℕ), a < 2^m → b < 2^m → a ≠ b → x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true → ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ))) (hoverlap : ∀ (p : ℤ) (q : ℕ), 1 ≤ q → q < 2^m → x (p+(q : ℤ)) (2^m-1-q) = true → ∃ a : ℕ, a < q ∧ x (p+(q : ℤ)) (2^m-q+a) = true ∧ x (p+((2^m : ℕ) : ℤ)) a = true) : 2^m ∣ n := by have hlabel := cycle_power_class_label_period_of_bounded_endpoint_overlap (2^m) (m+1) x ell hcount hsep hoverlap apply cycle_power_dyadic_model_dvd_of_label_period m n hm hn x ell hperiod hell hlabel htight hexact _ hsep intro j hj0 hj v have hjp : 2^j ≤ 2^(m-1) := Nat.pow_le_pow_right (by decide) (by omega) have hpow : 2^m=2*2^(m-1) := by conv_lhs => rw [show m=(m-1)+1 by omega] rw [pow_succ]; omega have htwo : 2 ≤ 2^(m-1) := by calc 2 = 2^1 := rfl _ ≤ _ := Nat.pow_le_pow_right (by decide) (by omega) have hdpos : 1 ≤ 2^m-2^j-1 := by rw [hpow]; omega have hdlt : 2^m-2^j-1 < 2^m := lt_of_le_of_lt (Nat.sub_le _ _) (Nat.sub_lt (Nat.two_pow_pos m) (Nat.two_pow_pos j)) obtain ⟨a, ha, hx0, hx1⟩ := hcover (2^m-2^j-1) hdpos hdlt v have hlarge : 2^j+1 ≤ 2^m := by rw [hpow]; omega have hrange : 2^m-(2^m-2^j-1)=2^j+1 := by omega rw [hrange] at ha refine ⟨a, ha, hx0, ?_⟩ have hi : a+2^m-2^j-1=a+(2^m-2^j-1) := by omega rw [hi] exact hx1