cycle_power_dyadic_sparse_defect_family_missing_distance
For every t≥4, no two support points differ by 2^(t−2)−2.
Statement
theorem cycle_power_dyadic_sparse_defect_family_missing_distance (t : ℕ) (ht : 4 ≤ t) : let q := 2^(t-2) let S := cycle_power_dyadic_sparse_defect_support t ∀ a ∈ S, ∀ b ∈ S, a < b → b-a ≠ q-2
- Source
- RT-1 and OP-205, arXiv:2610.15635. The sparse constant family was identified in experiment 22695; it is a weakened-coverage obstruction, not a full graph-cover model.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_power_dyadic_sparse_defect_supportFor exponent t, the sparse constant defect support consists of 0, 2^(t−2)−1, and 2^t−2^j for all j<t−2.
- cycle_power_dyadic_sparse_two_band_gapFor 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…
The proof, explained
The proof reduces the missing-distance claim to a general two-band gap lemma, cycle_power_dyadic_sparse_two_band_gap, which states that no two elements in S differ by q - 2 provided every element of S is either 0, q - 1, or lies in [4q - q/2, 4q) with q ≥ 4. With q = 2^(t - 2), the bound 4 ≤ q holds since t ≥ 4. Unfolding the definition of the support S, its elements are 0, q - 1, or 2^t - 2^j for j < t - 2; the first two cases are immediate, while rewriting 2^t = 4q and bounding 2^j ≤ 2^(t - 3) = q/2 places every point 2^t - 2^j squarely in [4q - q/2, 4q).
Define q = 2^(t - 2) and S = cycle_power_dyadic_sparse_defect_support t, and restate the target goal.
We introduce the local abbreviations q = 2^(t - 2) and S for the defect support set. The theorem is to show that for any a, b ∈ S with a < b, the difference b - a is not equal to q - 2.
let q := 2^(t-2) let S := cycle_power_dyadic_sparse_defect_support t change ∀ a ∈ S, ∀ b ∈ S, a < b → b-a ≠ q-2
4 ≤ q.
Since t ≥ 4, we have t - 2 ≥ 2. Because base-2 exponentiation is monotonic (Nat.pow_le_pow_right), 4 = 2^2 ≤ 2^(t - 2) = q.
uses
Nat.pow_le_pow_righthave hq : 4 ≤ q := by dsimp [q] calc 4 = 2^2 := by norm_num _ ≤ 2^(t-2) := Nat.pow_le_pow_right (by norm_num) (by omega)
2^t = 4 * q.
Writing t = (t - 2) + 2, the power splits into 2^t = 2^(t - 2) * 2^2 using pow_add. Evaluating 2^2 = 4 and substituting q = 2^(t - 2) gives 2^t = 4 * q.
uses
pow_addhave h4 : 2^t = 4*q := by dsimp [q] have he : t = (t-2)+2 := by omega conv_lhs => rw [he, pow_add] norm_num ring
q / 2 = 2^(t - 3).
Since t - 2 = (t - 3) + 1, we write q = 2^(t - 2) = 2^(t - 3) * 2 via pow_succ. Dividing by 2 yields q / 2 = 2^(t - 3).
uses
pow_succhave hh : q/2 = 2^(t-3) := by dsimp [q] have he : t-2 = (t-3)+1 := by omega conv_lhs => rw [he, pow_succ] omega
It suffices to show that every element a ∈ S satisfies a = 0, a = q - 1, or 4q - q/2 ≤ a < 4q.
We apply the lemma cycle_power_dyadic_sparse_two_band_gap, which reduces the missing-distance property for S to checking that every element of S belongs to {0, q - 1} or to the upper interval [4q - q/2, 4q).
uses
cycle_power_dyadic_sparse_two_band_gapapply cycle_power_dyadic_sparse_two_band_gap q hq SAny element a ∈ S is either 0, q - 1, or 2^t - 2^j for some j < t - 2; the first two cases directly satisfy the condition.
Unfolding the definition of S with the membership lemmas for unions, insertions, singletons, images, and ranges (Finset.mem_union, Finset.mem_insert, Finset.mem_singleton, Finset.mem_image, Finset.mem_range), any a ∈ S is 0, q - 1, or 2^t - 2^j with j < t - 2. The cases a = 0 and a = q - 1 match the first two disjuncts directly via Or.inl and Or.inr.
uses
Finset.mem_union,Finset.mem_insert,Finset.mem_singleton,Finset.mem_image,Finset.mem_range,Or.inl,Or.inrintro a ha simp only [S, cycle_power_dyadic_sparse_defect_support, Finset.mem_union, Finset.mem_insert, Finset.mem_singleton, Finset.mem_image, Finset.mem_range] at ha rcases ha with (rfl | rfl) | ⟨j, hj, rfl⟩ · exact Or.inl rfl · exact Or.inr (Or.inl rfl)
For a = 2^t - 2^j with j < t - 2, the bounds 4q - q/2 ≤ a < 4q hold.
Selecting the third disjunct, from j < t - 2 we obtain j ≤ t - 3, which implies 2^j ≤ 2^(t - 3) = q / 2 by Nat.pow_le_pow_right. Rewriting 2^t as 4q gives a = 4q - 2^j. Since 2^j > 0 (Nat.two_pow_pos), we have 4q - 2^j < 4q; and since 2^j ≤ q / 2, subtracting 2^j leaves at least 4q - q / 2. Both linear inequalities are closed by integer arithmetic.
uses
Nat.pow_le_pow_right,Nat.two_pow_pos· right; right have hjle : 2^j ≤ 2^(t-3) := Nat.pow_le_pow_right (by norm_num) (by omega) rw [← hh] at hjle rw [h4] have hp : 0 < 2^j := Nat.two_pow_pos j constructor <;> omega
Nat.pow_le_pow_right- For any base n > 0 and exponents i ≤ j, n^i ≤ n^j.
pow_add- In any monoid, a^(m + n) = a^m * a^n.
pow_succ- In any monoid, a^(n + 1) = a^n * a.
cycle_power_dyadic_sparse_two_band_gap- For q ≥ 4, if every element of a finite set S ⊆ ℕ is 0, q - 1, or lies in [4q - q/2, 4q), then no two elements in S differ by q - 2.
Finset.mem_union- An element belongs to the union s ∪ t if and only if it belongs to s or to t.
Finset.mem_insert- An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_singleton- An element b belongs to the singleton {a} if and only if b = a.
Finset.mem_image- An element b belongs to the image of s under f if and only if there exists a ∈ s with f(a) = b.
Finset.mem_range- A natural number m belongs to range n if and only if m < n.
Or.inl- Given a proof of a, produces a proof of the disjunction a ∨ b.
Or.inr- Given a proof of b, produces a proof of the disjunction a ∨ b.
Nat.two_pow_pos- For any natural number w, 2^w > 0.
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_defect_family_missing_distance (t : ℕ) (ht : 4 ≤ t) : let q := 2^(t-2) let S := cycle_power_dyadic_sparse_defect_support t ∀ a ∈ S, ∀ b ∈ S, a < b → b-a ≠ q-2 := by let q := 2^(t-2) let S := cycle_power_dyadic_sparse_defect_support t change ∀ a ∈ S, ∀ b ∈ S, a < b → b-a ≠ q-2 have hq : 4 ≤ q := by dsimp [q] calc 4 = 2^2 := by norm_num _ ≤ 2^(t-2) := Nat.pow_le_pow_right (by norm_num) (by omega) have h4 : 2^t = 4*q := by dsimp [q] have he : t = (t-2)+2 := by omega conv_lhs => rw [he, pow_add] norm_num ring have hh : q/2 = 2^(t-3) := by dsimp [q] have he : t-2 = (t-3)+1 := by omega conv_lhs => rw [he, pow_succ] omega apply cycle_power_dyadic_sparse_two_band_gap q hq S intro a ha simp only [S, cycle_power_dyadic_sparse_defect_support, Finset.mem_union, Finset.mem_insert, Finset.mem_singleton, Finset.mem_image, Finset.mem_range] at ha rcases ha with (rfl | rfl) | ⟨j, hj, rfl⟩ · exact Or.inl rfl · exact Or.inr (Or.inl rfl) · right; right have hjle : 2^j ≤ 2^(t-3) := Nat.pow_le_pow_right (by norm_num) (by omega) rw [← hh] at hjle rw [h4] have hp : 0 < 2^j := Nat.two_pow_pos j constructor <;> omega