cycle_power_dyadic_sparse_two_band_gap
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
- cycle_power_dyadic_sparse_defect_family_missing_distanceFor every t≥4, no two support points differ by 2^(t−2)−2.
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).
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.
intro a ha b hb habIn 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.
rcases hS a ha with ha0 | ha1 | hat <;> rcases hS b hb with hb0 | hb1 | hbt <;> omega
- The entire case analysis is closed by `omega`, which handles Presburger arithmetic including integer division by constants (here `q / 2`).
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.
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