cycle_power_aligned_end_blocks_endpoint_overlap
For nested aligned end-block widths, every class through the last point of a different old class intersects the translated new class one full arc later.
Statement
theorem cycle_power_aligned_end_blocks_endpoint_overlap
(D a b p q c : ℤ) (ha : 0 < a) (hb : 0 < b)
(hA : 2 * a ≤ D) (hB : 2 * b ≤ D)
(hDa : 2 * a ∣ D) (hDb : 2 * b ∣ D)
(hchain : a = b ∨ 2 * a ∣ b ∨ 2 * b ∣ a)
(hp : a ∣ p + c) (hpo : 2 * a < D → 2 * a ∣ p + c - a)
(hq : b ∣ q + c) (hqo : 2 * b < D → 2 * b ∣ q + c - b)
(hact : cycle_power_end_blocks D b q (p + D - 1)) (hqp : q ≠ p) :
∃ u, cycle_power_end_blocks D b q u ∧ cycle_power_end_blocks D a (p + D) u- Source
- Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- cycle_power_end_blocksThe union of the first and last a integer positions of a class with origin p and arc length D.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 2
- cycle_power_aligned_terminal_blocks_endpoint_overlapFor the uniform nested block family with a three-quarter terminal class, every other class through the old endpoint intersects the class…
- cycle_power_aligned_end_blocks_label_periodIn an aligned nested end-block family of arbitrary arc length, complete palettes at each vertex and separation of classes sharing a label…
The proof, explained
The theorem is proved by case analysis on whether the block width $a$ is maximal ($D = 2a$) or strictly smaller ($2a < D$), and on which end block of $q$ contains the boundary point $p + D - 1$. When $D = 2a$, the translated end blocks of $p + D$ cover the entire period $[p + D, p + 2D)$, so the upper end point $u = q + D - 1$ of $q$ immediately falls into one of them. When $2a < D$, if $p + D - 1$ is in the second block of $q$, the point $u = p + D$ directly witnesses the overlap. If $p + D - 1$ is in the first block of $q$, the chain condition $a = b \lor 2a \mid b \lor 2b \mid a$ is used: $a = b$ is ruled out because it forces an integer in the interval $[a, 2a)$ to be divisible by $2a$, while $2a \mid b$ and $2b \mid a$ provide the witnesses $u = p + D$ and $u = q + D - 1$ respectively.
The offset $q$ is strictly between $p$ and $p + D$ ($p < q < p + D$).
Unfolding the definition of end blocks shows that $p + D - 1$ lies in either $[q, q + b)$ or $[q + D - b, q + D)$. Since $q \ne p$, $0 < b$, and $2b \le D$, linear integer arithmetic (`omega`) deduces $p < q < p + D$ in both branches.
unfold cycle_power_end_blocks at hact ⊢ have hRange : p < q ∧ q < p + D := by rcases hact with h | h <;> constructor <;> omega
When $D = 2a$, the point $u = q + D - 1$ lies in the end blocks of both $q$ and $p + D$.
When $D = 2a$, the two end blocks of $(D, a, p + D)$, $[p + D, p + D + a)$ and $[p + 2D - a, p + 2D)$, meet at $p + D + a$ and cover the full period $[p + D, p + 2D)$. Since $b > 0$, the candidate point $u = q + D - 1$ lies in the upper block $[q + D - b, q + D)$ of $q$. Since $p < q < p + D$, $u$ belongs to $[p + D, p + 2D)$, and a case split on whether $u < p + D + a$ places $u$ in either the first or the second end block of $p + D$.
uses
Or.inr,Or.inlby_cases hfull : D = 2 * a · refine ⟨q + D - 1, Or.inr ⟨by omega, by omega⟩, ?_⟩ by_cases hh : q + D - 1 < p + D + a · exact Or.inl ⟨by omega, hh⟩ · exact Or.inr ⟨by omega, by omega⟩
When $D \ne 2a$, the inequality $2a < D$ is strict.
Linear arithmetic deduces $2a < D$ from the hypothesis $2a \le D$ and the assumption that $D \ne 2a$.
have hstrict : 2 * a < D := by omega
If $p + D - 1$ lies in the first block of $q$, the subcase $a = b$ is impossible.
Assuming $p + D - 1 \in [q, q + b)$ and $a = b$, the alignment conditions with $2a < D$ yield $2a \mid q + c - a$ and $2a \mid p + c - a$. Subtracting them gives $2a \mid q - p$. Combining this with $2a \mid D$ yields $2a \mid q - p - D + 2a$. But the assumption $q \le p + D - 1 < q + a$ restricts this quantity to $0 \le q - p - D + 2a < 2a$. By Int.eq_zero_of_dvd_of_nonneg_of_lt, this forces $q - p - D + 2a = 0$, which contradicts the strict lower bound $q - p - D + 2a \ge a > 0$.
uses
dvd_sub,dvd_add,dvd_refl,Int.eq_zero_of_dvd_of_nonneg_of_ltrcases hact with hfirst | hlast · rcases hchain with heq | hab | hba · subst b have hd : 2 * a ∣ q - p := by have hh : 2 * a ∣ (q + c - a) - (p + c - a) := dvd_sub (hqo hstrict) (hpo hstrict) have he : (q + c - a) - (p + c - a) = q - p := by ring rwa [he] at hh have hz : 2 * a ∣ q - p - D + 2 * a := dvd_add (dvd_sub hd hDa) (dvd_refl _) have hzero := Int.eq_zero_of_dvd_of_nonneg_of_lt (by omega : 0 ≤ q - p - D + 2 * a) (by omega : q - p - D + 2 * a < 2 * a) hz omega
If $p + D - 1$ lies in the first block of $q$ and $2a \mid b$, the point $u = p + D$ is in the first block of both systems.
If $p + D - 1 = q + b - 1$, then $p + D = q + b$. Since $2a \mid b$ and $b \mid q + c$, transitivity gives $2a \mid q + c$. Together with $2a \mid D$ and $2a \mid b$, this gives $2a \mid p + c$. Subtracting the alignment condition $2a \mid p + c - a$ forces $2a \mid a$, which by Int.eq_zero_of_dvd_of_nonneg_of_lt implies $a = 0$, contradicting $a > 0$. Hence $p + D - 1 \ne q + b - 1$, which strengthens the bound to $p + D < q + b$. Thus $u = p + D$ lies in $[q, q + b)$ as well as in $[p + D, p + D + a)$.
uses
dvd_trans,dvd_add,dvd_sub,dvd_sub,Int.eq_zero_of_dvd_of_nonneg_of_lt,Or.inl· have hne : p + D - 1 ≠ q + b - 1 := by intro he have hdq : 2 * a ∣ q + c := dvd_trans hab hq have hdp : 2 * a ∣ p + c := by have hh : 2 * a ∣ (q + c - D) + b := dvd_add (dvd_sub hdq hDa) hab have heq : (q + c - D) + b = p + c := by omega rwa [heq] at hh have hda : 2 * a ∣ a := by have hh : 2 * a ∣ (p + c) - (p + c - a) := dvd_sub hdp (hpo hstrict) have heq : (p + c) - (p + c - a) = a := by ring rwa [heq] at hh have hzero := Int.eq_zero_of_dvd_of_nonneg_of_lt ha.le (by omega : a < 2 * a) hda omega exact ⟨p + D, Or.inl ⟨by omega, by omega⟩, Or.inl ⟨by omega, by omega⟩⟩
If $p + D - 1$ lies in the first block of $q$ and $2b \mid a$, the point $u = q + D - 1$ is in the second block of both systems.
From $2b \mid a$ and $a > 0$, we have $2b \le a$, which implies $2b < D$. Transitivity yields $2b \mid p + c$, and alignment gives $2b \mid q + c - b$. Subtracting $p + c$ and $D$, and adding $2b$, gives $2b \mid q - p - D + b$. The containment $q \le p + D - 1 < q + b$ bounds $0 \le q - p - D + b < 2b$, so Int.eq_zero_of_dvd_of_nonneg_of_lt forces $q = p + D - b$. Then $u = q + D - 1$ lies in the upper block $[q + D - b, q + D)$ of $q$, and since $b \le 2b \le a$, $u = p + 2D - b - 1$ also falls into the upper block $[p + 2D - a, p + 2D)$ of $p + D$.
uses
Int.le_of_dvd,dvd_trans,dvd_add,dvd_sub,dvd_refl,Int.eq_zero_of_dvd_of_nonneg_of_lt,Or.inr· have hba_le : 2 * b ≤ a := Int.le_of_dvd ha hba have hbstrict : 2 * b < D := by omega have hdp : 2 * b ∣ p + c := dvd_trans hba hp have hz : 2 * b ∣ q - p - D + b := by have hh : 2 * b ∣ ((q + c - b) - (p + c) - D) + (2 * b) := dvd_add (dvd_sub (dvd_sub (hqo hbstrict) hdp) hDb) (dvd_refl (2 * b)) have heq : ((q + c - b) - (p + c) - D) + (2 * b) = q - p - D + b := by ring rwa [heq] at hh have hzero := Int.eq_zero_of_dvd_of_nonneg_of_lt (by omega : 0 ≤ q - p - D + b) (by omega : q - p - D + b < 2 * b) hz have hqeq : q = p + D - b := by omega exact ⟨q + D - 1, Or.inr ⟨by omega, by omega⟩, Or.inr ⟨by omega, by omega⟩⟩
If $p + D - 1$ lies in the second block of $q$, the point $u = p + D$ is in the end blocks of both systems.
When $q + D - b \le p + D - 1 < q + D$, we have $q + D - b \le p + D$. Together with $p + D < q + D$ (which follows from $p < q$), $u = p + D$ falls into the second block of $q$. Since $a > 0$, $u$ also trivially lies in the first block $[p + D, p + D + a)$ of $p + D$.
uses
Or.inr,Or.inl· exact ⟨p + D, Or.inr ⟨by omega, by omega⟩, Or.inl ⟨by omega, by omega⟩⟩
Or.inl- If a proposition $A$ holds, then the disjunction $A \lor B$ holds.
Or.inr- If a proposition $B$ holds, then the disjunction $A \lor B$ holds.
dvd_sub- If $a$ divides $b$ and $c$, then $a$ divides their difference $b - c$.
dvd_add- If $a$ divides $b$ and $c$, then $a$ divides their sum $b + c$.
dvd_refl- Every integer divides itself ($a \mid a$).
Int.eq_zero_of_dvd_of_nonneg_of_lt- If an integer $m$ satisfies $0 \le m < n$ and $n \mid m$, then $m = 0$.
dvd_trans- Divisibility is transitive: if $a \mid b$ and $b \mid c$, then $a \mid c$.
Int.le_of_dvd- If an integer $a$ divides a positive integer $b$, then $a \le b$.
- The proof relies heavily on the `omega` tactic to discharge linear integer arithmetic inequalities for interval bounds and modular arithmetic constraints.
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 Finsettheorem cycle_power_aligned_end_blocks_endpoint_overlap (D a b p q c : ℤ) (ha : 0 < a) (hb : 0 < b) (hA : 2 * a ≤ D) (hB : 2 * b ≤ D) (hDa : 2 * a ∣ D) (hDb : 2 * b ∣ D) (hchain : a = b ∨ 2 * a ∣ b ∨ 2 * b ∣ a) (hp : a ∣ p + c) (hpo : 2 * a < D → 2 * a ∣ p + c - a) (hq : b ∣ q + c) (hqo : 2 * b < D → 2 * b ∣ q + c - b) (hact : cycle_power_end_blocks D b q (p + D - 1)) (hqp : q ≠ p) : ∃ u, cycle_power_end_blocks D b q u ∧ cycle_power_end_blocks D a (p + D) u := by unfold cycle_power_end_blocks at hact ⊢ have hRange : p < q ∧ q < p + D := by rcases hact with h | h <;> constructor <;> omega by_cases hfull : D = 2 * a · refine ⟨q + D - 1, Or.inr ⟨by omega, by omega⟩, ?_⟩ by_cases hh : q + D - 1 < p + D + a · exact Or.inl ⟨by omega, hh⟩ · exact Or.inr ⟨by omega, by omega⟩ have hstrict : 2 * a < D := by omega rcases hact with hfirst | hlast · rcases hchain with heq | hab | hba · subst b have hd : 2 * a ∣ q - p := by have hh : 2 * a ∣ (q + c - a) - (p + c - a) := dvd_sub (hqo hstrict) (hpo hstrict) have he : (q + c - a) - (p + c - a) = q - p := by ring rwa [he] at hh have hz : 2 * a ∣ q - p - D + 2 * a := dvd_add (dvd_sub hd hDa) (dvd_refl _) have hzero := Int.eq_zero_of_dvd_of_nonneg_of_lt (by omega : 0 ≤ q - p - D + 2 * a) (by omega : q - p - D + 2 * a < 2 * a) hz omega · have hne : p + D - 1 ≠ q + b - 1 := by intro he have hdq : 2 * a ∣ q + c := dvd_trans hab hq have hdp : 2 * a ∣ p + c := by have hh : 2 * a ∣ (q + c - D) + b := dvd_add (dvd_sub hdq hDa) hab have heq : (q + c - D) + b = p + c := by omega rwa [heq] at hh have hda : 2 * a ∣ a := by have hh : 2 * a ∣ (p + c) - (p + c - a) := dvd_sub hdp (hpo hstrict) have heq : (p + c) - (p + c - a) = a := by ring rwa [heq] at hh have hzero := Int.eq_zero_of_dvd_of_nonneg_of_lt ha.le (by omega : a < 2 * a) hda omega exact ⟨p + D, Or.inl ⟨by omega, by omega⟩, Or.inl ⟨by omega, by omega⟩⟩ · have hba_le : 2 * b ≤ a := Int.le_of_dvd ha hba have hbstrict : 2 * b < D := by omega have hdp : 2 * b ∣ p + c := dvd_trans hba hp have hz : 2 * b ∣ q - p - D + b := by have hh : 2 * b ∣ ((q + c - b) - (p + c) - D) + (2 * b) := dvd_add (dvd_sub (dvd_sub (hqo hbstrict) hdp) hDb) (dvd_refl (2 * b)) have heq : ((q + c - b) - (p + c) - D) + (2 * b) = q - p - D + b := by ring rwa [heq] at hh have hzero := Int.eq_zero_of_dvd_of_nonneg_of_lt (by omega : 0 ≤ q - p - D + b) (by omega : q - p - D + b < 2 * b) hz have hqeq : q = p + D - b := by omega exact ⟨q + D - 1, Or.inr ⟨by omega, by omega⟩, Or.inr ⟨by omega, by omega⟩⟩ · exact ⟨p + D, Or.inr ⟨by omega, by omega⟩, Or.inl ⟨by omega, by omega⟩⟩