AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_two_band_gap

theoremverified

For q at least four, a finite set contained in {0, q-1} together with the half-open interval from 4q-floor(q/2) to 4q contains no pair at distance q-2.

Statement

theorem cycle_power_dyadic_sparse_two_band_gap
    (q : ℕ) (hq : 4 ≤ q) (S : Finset ℕ)
    (hS : ∀ a ∈ S, a = 0 ∨ a = q-1 ∨
      (4*q-q/2 ≤ a ∧ a < 4*q)) :
    ∀ a ∈ S, ∀ b ∈ S, a < b → b-a ≠ q-2
Source
Sparse defective profiles related to arXiv:2610.15635 and research thread RT-1.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof proceeds by a 3 × 3 case analysis on the location of a and b among the three allowed parts of S: {0}, {q - 1}, and the upper band [4q - ⌊q/2⌋, 4q). For each case, assuming a < b and q ≥ 4, linear integer arithmetic shows that b - a cannot equal q - 2 because the difference is either equal to q - 1, strictly larger than q - 2 (across bands), or strictly smaller than q - 2 (within the upper band).

  1. Fix elements a, b ∈ S with a < b.

    We introduce arbitrary elements a, b ∈ S and the hypothesis that a < b, leaving the goal of showing that b - a ≠ q - 2.

    line 6

      intro a ha b hb hab
  2. In all nine combinations of regions for a and b, b - a ≠ q - 2. automation

    By the hypothesis on S, each of a and b must be 0, q - 1, or in the interval [4q - ⌊q/2⌋, 4q). Splitting into 3 × 3 = 9 cases: any case with b ≤ a contradicts a < b; if a = 0 and b = q - 1, then b - a = q - 1 ≠ q - 2; if a ∈ {0, q - 1} and b is in the upper interval, then b - a ≥ 3q - ⌊q/2⌋ + 1 > q - 2; and if both a and b lie in the upper interval, their difference is at most ⌊q/2⌋ - 1, which is strictly less than q - 2 since q ≥ 4. The Presburger arithmetic decision procedure `omega` closes all nine subgoals automatically.

    lines 7–8

      rcases hS a ha with ha0 | ha1 | hat <;>
        rcases hS b hb with hb0 | hb1 | hbt <;> omega

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

theorem cycle_power_dyadic_sparse_two_band_gap    (q : ℕ) (hq : 4 ≤ q) (S : Finset ℕ)    (hS : ∀ a ∈ S, a = 0 ∨ a = q-1 ∨      (4*q-q/2 ≤ a ∧ a < 4*q)) :    ∀ a ∈ S, ∀ b ∈ S, a < b → b-a ≠ q-2 := by  intro a ha b hb hab  rcases hS a ha with ha0 | ha1 | hat <;>    rcases hS b hb with hb0 | hb1 | hbt <;> omega
See it in the graphDiscuss this resultChallenge it