AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_model_dvd_of_label_period

theoremverified

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
Used by 1

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.

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

    lines 20–22

    uses pow_succ

      have hpow : 2^m=2*2^(m-1) := by
        conv_lhs => rw [show m=(m-1)+1 by omega]
        rw [pow_succ]; omega
  2. 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.

    lines 23–28

    uses pow_zero, sum_range_one, Nat.cast_zero, sub_zero, Nat.zero_add

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

    line 29

    uses cycle_power_dyadic_central_position_exists

      have hc := cycle_power_dyadic_central_position_exists m n hm hn x hperiod htight hexact hcover
  4. The 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.

    lines 30–31

    uses cycle_power_class_half_shift_ne_of_central_occurrence, Nat.two_pow_pos

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

    lines 32–36

    uses Nat.sub_add_cancel, periodic_dyadic_dvd_of_half_shift_ne

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

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