cycle_power_two_full_roots_half_separated
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
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- Used by 1
- cycle_power_dyadic_class_no_island_of_full_class_coverA positive-exponent integer dyadic rooted-class model with tight weights, exact dyadic pair ownership, all ordinary distance coverage, and…
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.
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.
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
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.
uses
cycle_power_exact_pair_unique,sub_self,Nat.cast_zero,sub_zero,zero_addhave 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)
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.
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
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 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