AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_model_dvd_of_endpoint_overlap

theoremverified

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

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.

  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.

    lines 25–26

    uses cycle_power_class_label_period_of_bounded_endpoint_overlap

      have hlabel := cycle_power_class_label_period_of_bounded_endpoint_overlap
        (2^m) (m+1) x ell hcount hsep hoverlap
  2. It 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.

    lines 27–28

    uses cycle_power_dyadic_model_dvd_of_label_period

      apply cycle_power_dyadic_model_dvd_of_label_period m n hm hn x ell
        hperiod hell hlabel htight hexact _ hsep
  3. For 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`.

    lines 29–40

    uses Nat.pow_le_pow_right, pow_succ, Nat.two_pow_pos, Nat.sub_lt, Nat.sub_le, lt_of_le_of_lt

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

    line 41

      obtain ⟨a, ha, hx0, hx1⟩ := hcover (2^m-2^j-1) hdpos hdlt v
  5. The 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.

    lines 42–48

      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.

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