AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_defect_top_rank

theoremverified

At t≥4, the sparse support has no pair at the top dyadic distance 2^(t−1).

Statement

theorem cycle_power_dyadic_sparse_defect_top_rank (t : ℕ) (ht : 4 ≤ t) :
  (Finset.range (2^(t-1))).sum (fun a =>
    (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&
     decide (a + 2^t - 2^(t-1) ∈ cycle_power_dyadic_sparse_defect_support t)).toNat) = 0
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
Used by 1

The proof, explained

To show that the sparse defect support contains no pairs at the top dyadic distance 2^(t-1) for t ≥ 4, we express the distance and cycle length in terms of q = 2^(t-2), so that 2^(t-1) = 2*q and 2^t = 4*q. A preliminary lemma shows that any support element at most 3*q must be either 0 or q - 1, since the remaining elements of the support all exceed 3*q. The theorem expresses the count as a sum over a < 2*q of indicator products checking whether both a and a + 2*q lie in the support. Whenever a is in the support, it must be 0 or q - 1, which forces a + 2*q into the range [2*q, 3*q - 1], where no support elements exist; thus every term in the sum is zero.

  1. 4 ≤ q, where q = 2^(t-2).

    Since t ≥ 4, we have 2 ≤ t - 2, so 4 = 2^2 ≤ 2^(t-2) = q by monotonicity of powers of 2 (`Nat.pow_le_pow_right`).

    lines 5–9

    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, the power decomposes as 2^t = 2^((t-2)+2) = 2^(t-2) * 2^2 = q * 4 = 4*q by exponent addition (`pow_add`) and ring arithmetic.

    lines 10–14

    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. Any element a ≤ 3*q in the lower part {0, q-1} of the support satisfies a = 0 or a = q - 1.

    After supplying the bounds 4 ≤ q and 2^t = 4*q, we let a ≤ 3*q be an element of the defect support. Decomposing the union definition of the support (`Finset.mem_union.mp`), we consider the case where a ∈ {0, q-1}; unfolding insert and singleton membership (`Finset.mem_insert`, `Finset.mem_singleton`) yields a = 0 ∨ a = q - 1.

    lines 15–19

    uses Finset.mem_union.mp, Finset.mem_insert, Finset.mem_singleton

      refine ⟨hq,hD,?_⟩
      intro a ha hmem
      change a ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r) at hmem
      rcases Finset.mem_union.mp hmem with hsmall | hlarge
      · simpa only [Finset.mem_insert, Finset.mem_singleton] using hsmall
  4. No element from the upper part of the support can be at most 3*q.

    In the remaining case of the union, a = 2^t - 2^r for some r < t - 2 (`Finset.mem_image.mp`, `Finset.mem_range.mp`). Strict monotonicity of powers (`Nat.pow_lt_pow_right`) gives 2^r < 2^(t-2) = q. Hence a = 2^t - 2^r = 4*q - 2^r > 3*q, which contradicts the hypothesis a ≤ 3*q.

    lines 20–25

    uses Finset.mem_image.mp, Finset.mem_range.mp, Nat.pow_lt_pow_right

      · obtain ⟨r,hr,rfl⟩ := Finset.mem_image.mp hlarge
        have hr' : r < t-2 := Finset.mem_range.mp hr
        have hp : 2^r < q := by
          dsimp [q]
          exact Nat.pow_lt_pow_right (by decide) hr'
        omega
  5. For q = 2^(t-2), we have 4 ≤ q, 2^t = 4*q, and every support element at most 3*q is either 0 or q - 1.

    Setting q = 2^(t-2), we apply the helper lemma `rt1_sparse_bounds_top865` with t ≥ 4 to obtain the size bounds and the classification of small support elements.

    lines 31–33

    uses rt1_sparse_bounds_top865

      classical
      let q : ℕ := 2^(t-2)
      obtain ⟨hq,hD,hsmall⟩ := rt1_sparse_bounds_top865 t ht
  6. 2^(t-1) = 2*q, rewriting the summation bound.

    Since (t-2) + 1 = t - 1, we have 2^(t-1) = 2^((t-2)+1) = 2^(t-2) * 2 = 2*q using `pow_succ`. We rewrite 2^(t-1) to 2*q in the summation range.

    lines 34–39

    uses pow_succ

      have hhalf : 2^(t-1) = 2*q := by
        have ht' : t-2+1=t-1 := by omega
        calc
          2^(t-1) = 2^(t-2+1) := by rw [ht']
          _ = 2*q := by simp [pow_succ,q]; omega
      rw [hhalf]
  7. It suffices to show that each summand vanishes for every a < 2*q.

    By `Finset.sum_eq_zero`, a sum vanishes if every term is zero. We introduce an index a ∈ range(2*q), which satisfies a < 2*q by `Finset.mem_range.mp`.

    lines 40–42

    uses Finset.sum_eq_zero, Finset.mem_range.mp

      apply Finset.sum_eq_zero
      intro a ha
      have ha' : a < 2*q := Finset.mem_range.mp ha
  8. For any a < 2*q, the summand is zero.

    We split into cases on whether a is in the defect support. If a ∉ support, the first boolean factor is false, so the term is 0. If a ∈ support, then since a < 2*q ≤ 3*q, the helper lemma guarantees a = 0 or a = q - 1. The second element tested is b = a + 2^t - 2*q = a + 2*q, which satisfies 2*q ≤ b ≤ 3*q - 1 ≤ 3*q. If b were in the support, the helper lemma would imply b = 0 or b = q - 1, contradicting b ≥ 2*q > q - 1 ≥ 3. Hence b ∉ support, the second boolean factor is false, and the term is 0 in either case.

    lines 43–50

      by_cases hm : a ∈ cycle_power_dyadic_sparse_defect_support t
      · have hs := hsmall a (by omega) hm
        have hbnot : a+2^t-2*q ∉ cycle_power_dyadic_sparse_defect_support t := by
          intro hb
          have hh := hsmall (a+2^t-2*q) (by omega) hb
          omega
        simp [hbnot]
      · simp [hm]
Nat.pow_le_pow_right
For any positive base n, if i ≤ j, then n^i ≤ n^j.
pow_add
Powers add under multiplication: a^(m+n) = a^m * a^n.
Finset.mem_union.mp
An element of a union A ∪ B belongs to A or to B.
Finset.mem_insert
An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_image.mp
If an element belongs to the image f(s), then it equals f(a) for some a ∈ s.
Finset.mem_range.mp
An element of `range n` is strictly less than n.
Nat.pow_lt_pow_right
For a base a > 1, if m < n, then a^m < a^n.
rt1_sparse_bounds_top865
For t ≥ 4 and q = 2^(t-2), we have 4 ≤ q, 2^t = 4q, and any element of the defect support that is at most 3q must be either 0 or q - 1.
pow_succ
Successor power rule: a^(n+1) = a^n * a.
Finset.sum_eq_zero
A finite sum is zero if every term is zero.

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

private theorem rt1_sparse_bounds_top865 (t : ℕ) (ht : 4 ≤ t) :    let q := 2^(t-2)    4 ≤ q ∧ 2^t = 4*q ∧      ∀ a, a ≤ 3*q → a ∈ cycle_power_dyadic_sparse_defect_support t → a = 0 ∨ a = q-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  refine ⟨hq,hD,?_⟩  intro a ha hmem  change a ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r) at hmem  rcases Finset.mem_union.mp hmem with hsmall | hlarge  · simpa only [Finset.mem_insert, Finset.mem_singleton] using hsmall  · obtain ⟨r,hr,rfl⟩ := Finset.mem_image.mp hlarge    have hr' : r < t-2 := Finset.mem_range.mp hr    have hp : 2^r < q := by      dsimp [q]      exact Nat.pow_lt_pow_right (by decide) hr'    omegatheorem cycle_power_dyadic_sparse_defect_top_rank (t : ℕ) (ht : 4 ≤ t) :  (Finset.range (2^(t-1))).sum (fun a =>    (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&     decide (a + 2^t - 2^(t-1) ∈ cycle_power_dyadic_sparse_defect_support t)).toNat) = 0 := by  classical  let q : ℕ := 2^(t-2)  obtain ⟨hq,hD,hsmall⟩ := rt1_sparse_bounds_top865 t ht  have hhalf : 2^(t-1) = 2*q := by    have ht' : t-2+1=t-1 := by omega    calc      2^(t-1) = 2^(t-2+1) := by rw [ht']      _ = 2*q := by simp [pow_succ,q]; omega  rw [hhalf]  apply Finset.sum_eq_zero  intro a ha  have ha' : a < 2*q := Finset.mem_range.mp ha  by_cases hm : a ∈ cycle_power_dyadic_sparse_defect_support t  · have hs := hsmall a (by omega) hm    have hbnot : a+2^t-2*q ∉ cycle_power_dyadic_sparse_defect_support t := by      intro hb      have hh := hsmall (a+2^t-2*q) (by omega) hb      omega    simp [hbnot]  · simp [hm]
See it in the graphDiscuss this resultChallenge it