AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_defect_penultimate_rank

theoremverified

At t≥4, there is exactly one support pair at distance 2^t−2^(t−2).

Statement

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

The proof, explained

The theorem counts the number of elements a < q = 2^(t-2) such that both a and a + 2^t - q belong to the defect support. A helper lemma shows that 2^t = 4q and that the only elements of the support that are at most 3q are 0 and q - 1. The index a = q - 1 is a valid witness because q - 1 and (q - 1) + 2^t - q = 2^t - 1 both belong to the support. Conversely, any other candidate in range must be a = 0, but this would require 0 + 2^t - q = 3q to be in the support, which is impossible since q ≥ 4. Therefore, the sum collapses via Finset.sum_eq_single to the single nonzero term at a = q - 1, yielding 1.

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

    Since t ≥ 4, we have t - 2 ≥ 2. By monotonicity of exponentiation (Nat.pow_le_pow_right), q = 2^(t-2) ≥ 2^2 = 4.

    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 = 4q.

    Rewriting t as (t - 2) + 2, the exponent addition rule pow_add gives 2^t = 2^(t-2+2) = 2^(t-2) * 2^2 = 4q.

    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 in the defect support that is at most 3q must be either 0 or q - 1.

    By definition, the defect support is {0, q - 1} ∪ {2^t - 2^r | r < t - 2}. If an element a ≤ 3q belongs to the first component {0, q - 1}, then a = 0 or a = q - 1 via Finset.mem_union.mp, Finset.mem_insert, and Finset.mem_singleton. If instead a belongs to the second component, then a = 2^t - 2^r for some r < t - 2 via Finset.mem_image.mp and Finset.mem_range.mp. Since r < t - 2, strict monotonicity of powers (Nat.pow_lt_pow_right) gives 2^r < 2^(t-2) = q, so a = 4q - 2^r > 3q, which contradicts a ≤ 3q.

    lines 15–25

    uses Finset.mem_union.mp, Finset.mem_insert, Finset.mem_singleton, Finset.mem_image.mp, Finset.mem_range.mp, Nat.pow_lt_pow_right

      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'
        omega
  4. Set q = 2^(t-2) and express the goal as a sum of the pair indicator over a < q.

    We define q = 2^(t-2) and apply the helper theorem rt1_sparse_bounds865 to obtain 4 ≤ q, 2^t = 4q, and the characterization of support elements below 3q. The summation domain Finset.range (2^(t-2)) and the shift a + 2^t - 2^(t-2) are rephrased in terms of q.

    lines 31–36

    uses rt1_sparse_bounds865

      classical
      let q : ℕ := 2^(t-2)
      obtain ⟨hq,hD,hsmall⟩ := rt1_sparse_bounds865 t ht
      change (Finset.range q).sum (fun a =>
        (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&
         decide (a + 2^t - q ∈ cycle_power_dyadic_sparse_defect_support t)).toNat) = 1
  5. Both q - 1 and 2^t - 1 belong to the defect support.

    The element q - 1 belongs to the support because it is explicitly in {0, q - 1}. For 2^t - 1, choosing r = 0 gives 2^t - 2^0 = 2^t - 1; since t ≥ 4 implies 0 < t - 2, this element belongs to the image component of the support via Finset.mem_union_right, Finset.mem_image.mpr, and Finset.mem_range.mpr.

    lines 37–44

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

      have hsmallmem : 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 htopmem : 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
  6. 3q does not belong to the defect support.

    Suppose, for contradiction, that 3q were in the support. Since 3q ≤ 3q, the helper lemma would imply that 3q = 0 or 3q = q - 1. Because q ≥ 4, neither equation has a solution in ℕ.

    lines 45–48

      have hnot3q : 3*q ∉ cycle_power_dyadic_sparse_defect_support t := by
        intro hm
        have h := hsmall (3*q) (by omega) hm
        omega
  7. The summand at a = q - 1 evaluates to 1.

    We isolate the index a = q - 1 using Finset.sum_eq_single. The shifted term at this index is (q - 1) + 2^t - q = 2^t - 1. Because both q - 1 and 2^t - 1 belong to the defect support, both boolean conditions are true, so the product evaluates to 1.

    lines 49–51

    uses Finset.sum_eq_single

      rw [Finset.sum_eq_single (q-1)]
      · have heq : (q-1)+2^t-q = 2^t-1 := by omega
        simp [hsmallmem, heq, htopmem]
  8. For any a < q with a ≠ q - 1, the summand is 0.

    Let a ∈ Finset.range q with a ≠ q - 1, so a < q by Finset.mem_range.mp. We split into cases on whether a is in the defect support. If a ∉ support, the first factor is false and the summand is 0. If a ∈ support, then since a < q ≤ 3q, the helper lemma forces a = 0 or a = q - 1. Since a ≠ q - 1, we must have a = 0. The shifted value is then 0 + 2^t - q = 4q - q = 3q. Since 3q ∉ support, the second factor is false and the summand is 0.

    lines 52–59

    uses Finset.mem_range.mp

      · intro a ha hne
        have ha' : a < 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 ha0 : a=0 := by omega
          have heq : a+2^t-q = 3*q := by omega
          simp [heq,hnot3q]
        · simp [hm]
  9. The index q - 1 belongs to Finset.range q.

    Because q ≥ 4, we have q - 1 < q, so q - 1 ∈ Finset.range q by Finset.mem_range.mpr, eliminating the unused branch of Finset.sum_eq_single.

    lines 60–61

    uses Finset.mem_range.mpr

      · intro hnot
        exact (hnot (Finset.mem_range.mpr (by omega))).elim
Nat.pow_le_pow_right
If a base n > 0 and i ≤ j, then n^i ≤ n^j.
pow_add
In a monoid, a^(m + n) = a^m * a^n.
Finset.mem_union.mp
If an element belongs to the union s ∪ t, then it belongs to s or to t.
Finset.mem_insert
An element belongs to insert b into s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_image.mp
If y belongs to the image f(s), then y = f(x) for some x ∈ s.
Finset.mem_range.mp
If x belongs to Finset.range n, then x < n.
Nat.pow_lt_pow_right
If a > 1 and m < n, then a^m < a^n.
rt1_sparse_bounds865
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 is either 0 or q - 1.
Finset.mem_union_right
If an element belongs to t, then it belongs to the union s ∪ t.
Finset.mem_image.mpr
If x ∈ s and f(x) = y, then y belongs to the image f(s).
Finset.mem_range.mpr
If x < n, then x belongs to Finset.range n.
Finset.sum_eq_single
A finite sum reduces to the single term at a if the summand vanishes at all other elements of the domain and vanishes when a is outside the domain.

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_bounds865 (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_penultimate_rank (t : ℕ) (ht : 4 ≤ t) :  (Finset.range (2^(t-2))).sum (fun a =>    (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&     decide (a + 2^t - 2^(t-2) ∈ cycle_power_dyadic_sparse_defect_support t)).toNat) = 1 := by  classical  let q : ℕ := 2^(t-2)  obtain ⟨hq,hD,hsmall⟩ := rt1_sparse_bounds865 t ht  change (Finset.range q).sum (fun a =>    (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&     decide (a + 2^t - q ∈ cycle_power_dyadic_sparse_defect_support t)).toNat) = 1  have hsmallmem : 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 htopmem : 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 hnot3q : 3*q ∉ cycle_power_dyadic_sparse_defect_support t := by    intro hm    have h := hsmall (3*q) (by omega) hm    omega  rw [Finset.sum_eq_single (q-1)]  · have heq : (q-1)+2^t-q = 2^t-1 := by omega    simp [hsmallmem, heq, htopmem]  · intro a ha hne    have ha' : a < 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 ha0 : a=0 := by omega      have heq : a+2^t-q = 3*q := by omega      simp [heq,hnot3q]    · simp [hm]  · intro hnot    exact (hnot (Finset.mem_range.mpr (by omega))).elim
See it in the graphDiscuss this resultChallenge it