cycle_power_dyadic_model_dvd_of_label_period
A finite-period tight dyadic class model with proper labels, exact dyadic edges, neighbour coverage, and full-radius label period has model period divisible by the radius. Full-radius label periodicity remains an explicit hypothesis; optimal scalar counts and shape periods are unnecessary.
Statement
theorem cycle_power_dyadic_model_dvd_of_label_period (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) (hlabel : ∀ p, ell (p+((2^m : ℕ) : ℤ)) = ell p) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun a => (x p a).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 : ∀ j : ℕ, 1 ≤ j → j < m → ∀ v : ℤ, ∃ a : ℕ, a < 2^j+1 ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+2^m-2^j-1) = 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 : ℤ))) : 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 4
- 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_half_shift_ne_of_central_occurrenceA central occurrence in bounded rooted classes with proper labels forces some two root labels to differ after a half-radius shift. The…
- 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_endpoint_overlapA periodic optimal dyadic class model whose old active classes intersect the next endpoint class has period divisible by the dyadic…
The proof, explained
To show that the model period n is divisible by 2^m, the proof shows that the labeling function ℓ has full dyadic period 2^m but cannot have the half-period 2^(m-1). An active central bit is guaranteed by `cycle_power_dyadic_central_position_exists`, which, combined with the boundary bits from exact dyadic edges and label separation, prevents ℓ from being invariant under a shift by 2^(m-1). Finally, `periodic_dyadic_dvd_of_half_shift_ne` forces the full dyadic period 2^m to divide n.
2^m = 2 * 2^(m-1)
Because m ≥ 2, we can write m = (m - 1) + 1. By the successor rule for powers (`pow_succ`), 2^((m-1)+1) = 2^(m-1) * 2 = 2 * 2^(m-1).
uses
pow_succhave hpow : 2^m=2*2^(m-1) := by conv_lhs => rw [show m=(m-1)+1 by omega] rw [pow_succ]; omega
For every position p ∈ ℤ, the boundary bits are set: x(p, 0) = true and x(p, 2 * 2^(m-1) - 1) = true.
Instantiating the exact dyadic edge hypothesis (`hexact`) at level j = 0 at position p, the sum over range(2^0) = {0} contains only the single term (x(p, 0) ∧ x(p, 2^m - 1)).toNat = 1. Rewriting 2^m as 2 * 2^(m-1) and performing case analysis on the boolean values, both bits must evaluate to true.
uses
pow_zero,sum_range_one,Nat.cast_zero,sub_zero,Nat.zero_addhave hroot (p : ℤ) : x p 0 = true ∧ x p (2*2^(m-1)-1) = true := by have hh := hexact 0 (by omega) p norm_num only [pow_zero, sum_range_one, Nat.cast_zero, sub_zero, Nat.zero_add] at hh rw [← hpow] cases h0 : x p 0 <;> cases h1 : x p (2^m-1) <;> simp_all
There exists an occurrence of an active central bit: ∃ p ∈ ℤ, x(p, 2^(m-1)-1) = true ∨ x(p, 2^(m-1)) = true.
By `cycle_power_dyadic_central_position_exists`, any model satisfying periodicity, tightness, exact edge counts, and neighbour coverage contains a position where at least one of the two central positions, 2^(m-1)-1 or 2^(m-1), is active.
uses
cycle_power_dyadic_central_position_existshave hc := cycle_power_dyadic_central_position_exists m n hm hn x hperiod htight hexact hcoverThe labeling function ℓ is not invariant under translation by the half-period 2^(m-1): ∃ p ∈ ℤ, ℓ(p + 2^(m-1)) ≠ ℓ(p).
We apply `cycle_power_class_half_shift_ne_of_central_occurrence` with half-period H = 2^(m-1) > 0. The boundary bits (`hroot`), separation of labels at distinct active positions (`hsep`), and the central occurrence (`hc`) jointly imply that ℓ(p + 2^(m-1)) ≠ ℓ(p) for some p.
uses
cycle_power_class_half_shift_ne_of_central_occurrence,Nat.two_pow_poshave hs := cycle_power_class_half_shift_ne_of_central_occurrence (2^(m-1)) (Nat.two_pow_pos _) x ell hroot (by simpa only [← hpow] using hsep) hc
2^m divides n.
Using 1 ≤ m, we express 2^m as 2^((m-1)+1). Hypothesis `hlabel` says that ℓ is periodic with period 2^m = 2^((m-1)+1). Since ℓ is also n-periodic (`hell`) and fails to be periodic with half-period 2^(m-1) (`hs`), `periodic_dyadic_dvd_of_half_shift_ne` applies with parameter m - 1 to conclude that 2^((m-1)+1) ∣ n. Rewriting (m - 1) + 1 back to m via `Nat.sub_add_cancel` completes the proof.
uses
Nat.sub_add_cancel,periodic_dyadic_dvd_of_half_shift_nehave hdy : Function.Periodic ell ((2^(m-1+1) : ℕ) : ℤ) := by rw [Nat.sub_add_cancel (show 1 ≤ m by omega)] exact hlabel have hd := periodic_dyadic_dvd_of_half_shift_ne (m-1) n ell hell hdy hs simpa only [Nat.sub_add_cancel (show 1 ≤ m by omega)] using hd
pow_succ- In any monoid, a^(n+1) = a^n * a.
pow_zero- In any monoid, a^0 = 1.
sum_range_one- The sum of a function over the singleton range {0} is f(0).
Nat.cast_zero- The natural number zero casts to 0 in any additive monoid with one.
sub_zero- Subtracting zero leaves an element unchanged (a - 0 = a).
Nat.zero_add- Adding zero on the left leaves a natural number unchanged (0 + n = n).
cycle_power_dyadic_central_position_exists- In a tight, periodic dyadic model satisfying exactness and neighbour coverage, there exists a position where a central bit at index 2^(m-1)-1 or 2^(m-1) is true.
cycle_power_class_half_shift_ne_of_central_occurrence- In a model with boundary bits set and label separation, an occurrence of a central bit guarantees that the label function is not invariant under translation by the half-period H.
Nat.two_pow_pos- Powers of two are strictly positive (2^w > 0 for any w).
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
periodic_dyadic_dvd_of_half_shift_ne- If a function has period n and dyadic period 2^(m+1), but is not periodic with half-period 2^m, then 2^(m+1) divides n.
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_label_period (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) (hlabel : ∀ p, ell (p+((2^m : ℕ) : ℤ)) = ell p) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun a => (x p a).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 : ∀ j : ℕ, 1 ≤ j → j < m → ∀ v : ℤ, ∃ a : ℕ, a < 2^j+1 ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+2^m-2^j-1) = 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 : ℤ))) : 2^m ∣ n := by have hpow : 2^m=2*2^(m-1) := by conv_lhs => rw [show m=(m-1)+1 by omega] rw [pow_succ]; omega have hroot (p : ℤ) : x p 0 = true ∧ x p (2*2^(m-1)-1) = true := by have hh := hexact 0 (by omega) p norm_num only [pow_zero, sum_range_one, Nat.cast_zero, sub_zero, Nat.zero_add] at hh rw [← hpow] cases h0 : x p 0 <;> cases h1 : x p (2^m-1) <;> simp_all have hc := cycle_power_dyadic_central_position_exists m n hm hn x hperiod htight hexact hcover have hs := cycle_power_class_half_shift_ne_of_central_occurrence (2^(m-1)) (Nat.two_pow_pos _) x ell hroot (by simpa only [← hpow] using hsep) hc have hdy : Function.Periodic ell ((2^(m-1+1) : ℕ) : ℤ) := by rw [Nat.sub_add_cancel (show 1 ≤ m by omega)] exact hlabel have hd := periodic_dyadic_dvd_of_half_shift_ne (m-1) n ell hell hdy hs simpa only [Nat.sub_add_cancel (show 1 ≤ m by omega)] using hd