AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_defect_family_missing_distance

theoremverified

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

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

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

    lines 5–7

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

    lines 8–11

    uses Nat.pow_le_pow_right

      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)
  3. 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.

    lines 12–17

    uses pow_add

      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
  4. 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).

    lines 18–22

    uses pow_succ

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

    line 23

    uses cycle_power_dyadic_sparse_two_band_gap

      apply cycle_power_dyadic_sparse_two_band_gap q hq S
  6. Any 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.

    lines 24–29

    uses Finset.mem_union, Finset.mem_insert, Finset.mem_singleton, Finset.mem_image, Finset.mem_range, Or.inl, Or.inr

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

    lines 30–35

    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

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