periodic_dyadic_dvd_of_half_shift_ne
If 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.
Statement
theorem periodic_dyadic_dvd_of_half_shift_ne {α : Type*} (m n : ℕ) (σ : ℤ → α) (hperiod : Function.Periodic σ (n : ℤ)) (hdyadic : Function.Periodic σ ((2^(m+1) : ℕ) : ℤ)) (hhalf : ∃ p : ℤ, σ (p + ((2^m : ℕ) : ℤ)) ≠ σ p) : 2^(m+1) ∣ 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- Used by 2
- 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…
- 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…
The proof, explained
We argue by contradiction, assuming 2^(m+1) does not divide n. The greatest common divisor g = gcd(2^(m+1), n) divides 2^(m+1), hence is a power of 2, and since it cannot be 2^(m+1), it must divide 2^m. Using Bézout's identity, 2^m can then be expressed as an integer linear combination of the two known periods 2^(m+1) and n. This makes 2^m a period of σ, directly contradicting the hypothesis that σ is not invariant under shifting by 2^m.
Assume for contradiction that 2^(m+1) does not divide n, and introduce shorthand notation.
We define D = 2^(m+1) and H = 2^m for brevity. We then assume for contradiction that D does not divide n (hypothesis hnd).
let D := 2^(m+1) let H := 2^m by_contra hnd
The greatest common divisor g = gcd(D, n) divides both D and n.
Let g = gcd(D, n). By Nat.gcd_dvd_left, g divides D, and by Nat.gcd_dvd_right, g divides n.
uses
Nat.gcd_dvd_left,Nat.gcd_dvd_rightlet g := Nat.gcd D n have hgD : g ∣ D := Nat.gcd_dvd_left D n have hgn : g ∣ n := Nat.gcd_dvd_right D n
The divisor g divides H = 2^m.
Since g divides D = 2^(m+1) and 2 is prime (Nat.prime_two), Nat.dvd_prime_pow implies g = 2^k for some k ≤ m + 1. If k were greater than m, we would have k = m + 1, so g = D, which would imply D divides n via g ∣ n, contradicting our assumption. Hence k ≤ m. Using pow_add, 2^m = 2^k * 2^(m - k), so g = 2^k divides H = 2^m.
uses
Nat.dvd_prime_pow,Nat.prime_two,pow_addhave hgH : g ∣ H := by obtain ⟨k, hk, hg⟩ := (Nat.dvd_prime_pow Nat.prime_two).mp hgD have hk' : k ≤ m := by by_contra hn have hke : k = m+1 := by omega have hge : g = D := by simpa only [hke] using hg apply hnd change D ∣ n rw [← hge] exact hgn rw [hg] exact ⟨2^(m-k), by dsimp [H]; rw [← pow_add]; congr 1; omega⟩
H can be expressed as an integer linear combination of D and n.
Since g divides H, we have H = g * w for some natural number w. By Bézout's identity (Nat.gcd_eq_gcd_ab), g = D * gcdA(D, n) + n * gcdB(D, n) in the integers. Multiplying by w gives H = (gcdA(D, n) * w) * D + (gcdB(D, n) * w) * n.
uses
Nat.gcd_eq_gcd_abobtain ⟨w, hw⟩ := hgH have hb : ((Nat.gcd D n : ℕ) : ℤ) = D * Nat.gcdA D n + n * Nat.gcdB D n := Nat.gcd_eq_gcd_ab D n have hHz : (H : ℤ) = (Nat.gcdA D n * w) * (D : ℤ) + (Nat.gcdB D n * w) * (n : ℤ) := by calc (H : ℤ) = (g : ℤ)*(w : ℤ) := by exact_mod_cast hw _ = _ := by dsimp [g]; rw [hb]; ring
The function σ is periodic with period H.
Because H is an integer linear combination of D and n, and σ has periods D and n, σ is periodic under each summand. By add_period, the sum of two periods is again a period, so H is a period of σ.
uses
add_periodhave hpH : Function.Periodic σ (H : ℤ) := by rw [hHz] exact (hdyadic.int_mul (Nat.gcdA D n*w)).add_period (hperiod.int_mul (Nat.gcdB D n*w))
A contradiction is reached with the non-periodicity assumption at H.
Hypothesis hhalf asserts there is some integer p where σ(p + 2^m) ≠ σ p. But H = 2^m was just proven to be a period of σ, so σ(p + H) = σ p, yielding a contradiction that completes the proof.
obtain ⟨p, hp⟩ := hhalf exact hp (hpH p)
Nat.gcd_dvd_left- The greatest common divisor gcd(m, n) divides m.
Nat.gcd_dvd_right- The greatest common divisor gcd(m, n) divides n.
Nat.dvd_prime_pow- For a prime p, a divisor of p^m must be of the form p^k for some k ≤ m.
Nat.prime_two- The number 2 is prime.
pow_add- Powers add under multiplication: a^(m + n) = a^m * a^n.
Nat.gcd_eq_gcd_ab- Bézout's identity: gcd(x, y) = x * gcdA(x, y) + y * gcdB(x, y) as integers.
add_period- The sum of two periods of a function is also a period.
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 periodic_dyadic_dvd_of_half_shift_ne {α : Type*} (m n : ℕ) (σ : ℤ → α) (hperiod : Function.Periodic σ (n : ℤ)) (hdyadic : Function.Periodic σ ((2^(m+1) : ℕ) : ℤ)) (hhalf : ∃ p : ℤ, σ (p + ((2^m : ℕ) : ℤ)) ≠ σ p) : 2^(m+1) ∣ n := by let D := 2^(m+1) let H := 2^m by_contra hnd let g := Nat.gcd D n have hgD : g ∣ D := Nat.gcd_dvd_left D n have hgn : g ∣ n := Nat.gcd_dvd_right D n have hgH : g ∣ H := by obtain ⟨k, hk, hg⟩ := (Nat.dvd_prime_pow Nat.prime_two).mp hgD have hk' : k ≤ m := by by_contra hn have hke : k = m+1 := by omega have hge : g = D := by simpa only [hke] using hg apply hnd change D ∣ n rw [← hge] exact hgn rw [hg] exact ⟨2^(m-k), by dsimp [H]; rw [← pow_add]; congr 1; omega⟩ obtain ⟨w, hw⟩ := hgH have hb : ((Nat.gcd D n : ℕ) : ℤ) = D * Nat.gcdA D n + n * Nat.gcdB D n := Nat.gcd_eq_gcd_ab D n have hHz : (H : ℤ) = (Nat.gcdA D n * w) * (D : ℤ) + (Nat.gcdB D n * w) * (n : ℤ) := by calc (H : ℤ) = (g : ℤ)*(w : ℤ) := by exact_mod_cast hw _ = _ := by dsimp [g]; rw [hb]; ring have hpH : Function.Periodic σ (H : ℤ) := by rw [hHz] exact (hdyadic.int_mul (Nat.gcdA D n*w)).add_period (hperiod.int_mul (Nat.gcdB D n*w)) obtain ⟨p, hp⟩ := hhalf exact hp (hpH p)