AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_defect_two_covered_distances

theoremverified

For each t≥4, the support covers distances 1 and 3·2^(t−2)−1.

Statement

theorem cycle_power_dyadic_sparse_defect_two_covered_distances (t : ℕ) (ht : 4 ≤ t) :
  (∃ a ∈ cycle_power_dyadic_sparse_defect_support t, ∃ b ∈ cycle_power_dyadic_sparse_defect_support t, a < b ∧ b-a = 1) ∧
  (∃ a ∈ cycle_power_dyadic_sparse_defect_support t, ∃ b ∈ cycle_power_dyadic_sparse_defect_support t, a < b ∧ b-a = 3 * 2^(t-2)-1)
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
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem is proved by explicitly exhibiting two pairs of elements in the support that realize the required differences. Letting q = 2^(t-2), the support contains q - 1 from its initial set {0, q - 1}, as well as 2^t - 1 (for r = 0) and 2^t - 2 (for r = 1) from its dyadic image component. The distance 1 is realized by the adjacent pair 2^t - 2 and 2^t - 1, while the distance 3*2^(t-2) - 1 = 3q - 1 is realized by the pair q - 1 and 2^t - 2, using the identity 2^t = 4q.

  1. Setting q = 2^(t-2), we have 4 ≤ q.

    We define the abbreviation q = 2^(t-2). Because t ≥ 4, we have 2 ≤ t - 2. By monotonicity of powers with base 2 (Nat.pow_le_pow_right), 2^2 ≤ 2^(t-2), which simplifies to 4 ≤ q.

    lines 4–8

    uses Nat.pow_le_pow_right

      classical
      let q : ℕ := 2^(t-2)
      have hq : 4 ≤ q := by
        have h := Nat.pow_le_pow_right (by decide : 0 < (2 : ℕ)) (show 2 ≤ t-2 by omega)
        simpa [q] using h
  2. 2^t = 4 * q

    Since (t - 2) + 2 = t, we rewrite 2^t as 2^((t-2)+2). Using the exponent addition law pow_add, this factors as 2^(t-2) * 2^2, which ring arithmetic rewrites as 4 * q.

    lines 9–13

    uses pow_add

      have hD : 2^t = 4*q := by
        have ht' : t-2+2 = t := by omega
        calc
          2^t = 2^(t-2+2) := by rw [ht']
          _ = 4*q := by simp [pow_add, q]; ring
  3. q - 1 belongs to the support.

    By definition, cycle_power_dyadic_sparse_defect_support t is the union of {0, q - 1} and an image set. The element q - 1 is explicitly in the first set, hence in the union.

    lines 14–16

      have hsmall : q-1 ∈ cycle_power_dyadic_sparse_defect_support t := by
        change q-1 ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)
        simp
  4. 2^t - 1 belongs to the support.

    We show 2^t - 1 belongs to the right-hand component of the union (Finset.mem_union_right), which is the image of {0, ..., t-3} under r ↦ 2^t - 2^r. Setting r = 0, we have 0 < t - 2 since t ≥ 4 (Finset.mem_range.mpr), and 2^t - 2^0 = 2^t - 1 (Finset.mem_image.mpr).

    lines 17–21

    uses Finset.mem_union_right, Finset.mem_image.mpr, Finset.mem_range.mpr

      have hD1 : 2^t-1 ∈ cycle_power_dyadic_sparse_defect_support t := by
        change 2^t-1 ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)
        apply Finset.mem_union_right
        refine Finset.mem_image.mpr ⟨0, Finset.mem_range.mpr (by omega), ?_⟩
        simp
  5. 2^t - 2 belongs to the support.

    Similarly, 2^t - 2 belongs to the right-hand component of the union (Finset.mem_union_right). Setting r = 1, we have 1 < t - 2 since t ≥ 4 (Finset.mem_range.mpr), and 2^t - 2^1 = 2^t - 2 (Finset.mem_image.mpr).

    lines 22–26

    uses Finset.mem_union_right, Finset.mem_image.mpr, Finset.mem_range.mpr

      have hD2 : 2^t-2 ∈ cycle_power_dyadic_sparse_defect_support t := by
        change 2^t-2 ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)
        apply Finset.mem_union_right
        refine Finset.mem_image.mpr ⟨1, Finset.mem_range.mpr (by omega), ?_⟩
        norm_num
  6. Distance 1 is covered by two elements in the support.

    Splitting the conjunction, we witness the pair a = 2^t - 2 and b = 2^t - 1. Both were shown to be in the support, and linear integer arithmetic verifies that 2^t - 2 < 2^t - 1 with difference (2^t - 1) - (2^t - 2) = 1.

    lines 27–28

      constructor
      · exact ⟨2^t-2, hD2, 2^t-1, hD1, by omega, by omega⟩
  7. Distance 3 · 2^(t-2) - 1 is covered by two elements in the support.

    Rewriting the target difference as 3*q - 1, we witness the pair a = q - 1 and b = 2^t - 2. Both belong to the support. Using 2^t = 4*q and 4 ≤ q, linear arithmetic verifies that q - 1 < 2^t - 2 and (2^t - 2) - (q - 1) = (4*q - 2) - (q - 1) = 3*q - 1.

    lines 29–30

      · change ∃ a ∈ cycle_power_dyadic_sparse_defect_support t, ∃ b ∈ cycle_power_dyadic_sparse_defect_support t, a < b ∧ b-a = 3*q-1
        exact ⟨q-1, hsmall, 2^t-2, hD2, by omega, by omega⟩
Nat.pow_le_pow_right
for a positive base, exponentiation on natural numbers preserves non-strict inequality
pow_add
in a monoid (such as ℕ under multiplication), powers satisfy a^(m+n) = a^m * a^n
Finset.mem_union_right
an element belonging to a set t also belongs to the union s ∪ t
Finset.mem_image.mpr
an element y belongs to the image f(s) if there is some x ∈ s with f(x) = y
Finset.mem_range.mpr
a natural number i belongs to Finset.range n if and only if i < n

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_two_covered_distances (t : ℕ) (ht : 4 ≤ t) :  (∃ a ∈ cycle_power_dyadic_sparse_defect_support t, ∃ b ∈ cycle_power_dyadic_sparse_defect_support t, a < b ∧ b-a = 1) ∧  (∃ a ∈ cycle_power_dyadic_sparse_defect_support t, ∃ b ∈ cycle_power_dyadic_sparse_defect_support t, a < b ∧ b-a = 3 * 2^(t-2)-1) := by  classical  let q : ℕ := 2^(t-2)  have hq : 4 ≤ q := by    have h := Nat.pow_le_pow_right (by decide : 0 < (2 : ℕ)) (show 2 ≤ t-2 by omega)    simpa [q] using h  have hD : 2^t = 4*q := by    have ht' : t-2+2 = t := by omega    calc      2^t = 2^(t-2+2) := by rw [ht']      _ = 4*q := by simp [pow_add, q]; ring  have hsmall : q-1 ∈ cycle_power_dyadic_sparse_defect_support t := by    change q-1 ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)    simp  have hD1 : 2^t-1 ∈ cycle_power_dyadic_sparse_defect_support t := by    change 2^t-1 ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)    apply Finset.mem_union_right    refine Finset.mem_image.mpr ⟨0, Finset.mem_range.mpr (by omega), ?_⟩    simp  have hD2 : 2^t-2 ∈ cycle_power_dyadic_sparse_defect_support t := by    change 2^t-2 ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)    apply Finset.mem_union_right    refine Finset.mem_image.mpr ⟨1, Finset.mem_range.mpr (by omega), ?_⟩    norm_num  constructor  · exact ⟨2^t-2, hD2, 2^t-1, hD1, by omega, by omega⟩  · change ∃ a ∈ cycle_power_dyadic_sparse_defect_support t, ∃ b ∈ cycle_power_dyadic_sparse_defect_support t, a < b ∧ b-a = 3*q-1    exact ⟨q-1, hsmall, 2^t-2, hD2, by omega, by omega⟩
See it in the graphDiscuss this resultChallenge it