AFTD Auto-Formalizing Theoretical Domains

periodic_dyadic_dvd_of_half_shift_ne

theoremverified

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

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.

  1. 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).

    lines 9–11

      let D := 2^(m+1)
      let H := 2^m
      by_contra hnd
  2. 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.

    lines 12–14

    uses Nat.gcd_dvd_left, Nat.gcd_dvd_right

      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
  3. 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.

    lines 15–26

    uses Nat.dvd_prime_pow, Nat.prime_two, pow_add

      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⟩
  4. 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.

    lines 27–35

    uses Nat.gcd_eq_gcd_ab

      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
  5. 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 σ.

    lines 36–39

    uses add_period

      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))
  6. 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.

    lines 40–41

      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

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)
See it in the graphDiscuss this resultChallenge it