AFTD Auto-Formalizing Theoretical Domains

cycle_power_two_full_roots_half_separated

theoremverified

When D is twice R and every distance-R pair has a unique root owner, distinct full classes rooted at zero and a positive g must have g at least R.

Statement

theorem cycle_power_two_full_roots_half_separated
    (D R : ℕ) (hD : D = 2*R) (x : ℤ → ℕ → Bool)
    (hexact : ∀ v : ℤ, (range R).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1)
    (g : ℕ) (hg₀ : 0 < g)
    (hfull₀ : ∀ i < D, x 0 i = true)
    (hfullg : ∀ i < D, x (g : ℤ) i = true) : R ≤ g
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by contradiction: if g < R, then the two distinct root classes at 0 and g both claim ownership of the distance-(D - R) pair at vertex v = g. Because root 0 is full up to D, it supports the pair at offset g; because root g is full up to D, it supports the pair at offset 0. The hypothesis that every vertex has a unique root owner then forces g = 0, directly contradicting the assumption that g > 0.

  1. Assuming for contradiction that g < R, the index offsets g, g + D - R, and D - R are all strictly less than D.

    We proceed by contradiction, assuming ¬(R ≤ g), which means g < R. Since D = 2 * R and g > 0, linear arithmetic establishes that g < D, g + D - R = g + R < 2 * R = D, and D - R = R < D.

    lines 12–16

      by_contra hn
      have hgR : g < R := by omega
      have hgD : g < D := by omega
      have hhiD : g+D-R < D := by omega
      have hRD : D-R < D := by omega
  2. The uniqueness of root owners implies g = 0.

    We apply cycle_power_exact_pair_unique to vertex v = g with candidate offsets a = g and b = 0. Both candidates satisfy the distance-(D - R) pair condition: for a = g, the row index is g - g = 0, where both columns g and g + D - R are true because root 0 is full up to D; for b = 0, the row index is g - 0 = g, where both columns 0 and 0 + D - R = D - R are true because root g is full up to D. Because at most one offset in range R can satisfy this condition at vertex g, the two offsets must coincide, forcing g = 0.

    lines 17–21

    uses cycle_power_exact_pair_unique, sub_self, Nat.cast_zero, sub_zero, zero_add

      have he := cycle_power_exact_pair_unique D R x hexact (g : ℤ) g 0 hgR (by omega)
        (by simpa only [sub_self] using hfull₀ g hgD)
        (by simpa only [sub_self] using hfull₀ (g+D-R) hhiD)
        (by simpa only [Nat.cast_zero, sub_zero] using hfullg 0 (by omega))
        (by simpa only [Nat.cast_zero, sub_zero, zero_add] using hfullg (D-R) hRD)
  3. A contradiction is reached, proving R ≤ g.

    Linear arithmetic detects the contradiction between the derived equality g = 0 and the hypothesis 0 < g, closing the contradiction branch.

    line 22

      omega
cycle_power_exact_pair_unique
For any vertex v, if exactly one offset a < R satisfies x(v - a, a) = true and x(v - a, a + D - R) = true, then any two offsets a, b < R satisfying this condition for the same v must be equal.
sub_self
Subtracting an element of an additive group from itself yields zero (a - a = 0).
Nat.cast_zero
The coercion of the natural number 0 into an additive monoid with one is 0.
sub_zero
Subtracting zero from an element leaves it unchanged (a - 0 = a).
zero_add
Adding zero to an element on the left leaves it unchanged (0 + a = a).

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_two_full_roots_half_separated    (D R : ℕ) (hD : D = 2*R) (x : ℤ → ℕ → Bool)    (hexact : ∀ v : ℤ, (range R).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1)    (g : ℕ) (hg₀ : 0 < g)    (hfull₀ : ∀ i < D, x 0 i = true)    (hfullg : ∀ i < D, x (g : ℤ) i = true) : R ≤ g := by  by_contra hn  have hgR : g < R := by omega  have hgD : g < D := by omega  have hhiD : g+D-R < D := by omega  have hRD : D-R < D := by omega  have he := cycle_power_exact_pair_unique D R x hexact (g : ℤ) g 0 hgR (by omega)    (by simpa only [sub_self] using hfull₀ g hgD)    (by simpa only [sub_self] using hfull₀ (g+D-R) hhiD)    (by simpa only [Nat.cast_zero, sub_zero] using hfullg 0 (by omega))    (by simpa only [Nat.cast_zero, sub_zero, zero_add] using hfullg (D-R) hRD)  omega
See it in the graphDiscuss this resultChallenge it