AFTD Auto-Formalizing Theoretical Domains

cycle_power_aligned_end_blocks_endpoint_overlap

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2

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.

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

    lines 12–14

      unfold cycle_power_end_blocks at hact ⊢
      have hRange : p < q ∧ q < p + D := by
        rcases hact with h | h <;> constructor <;> omega
  2. 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$.

    lines 15–19

    uses Or.inr, Or.inl

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

    line 20

      have hstrict : 2 * a < D := by omega
  4. 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$.

    lines 21–34

    uses dvd_sub, dvd_add, dvd_refl, Int.eq_zero_of_dvd_of_nonneg_of_lt

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

    lines 35–49

    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⟩⟩
  6. 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$.

    lines 50–63

    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⟩⟩
  7. 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$.

    lines 64–65

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

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