AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_sparse_defect_lower_rank

theoremverified

For t≥4 and j<t−2, the unique support pair at dyadic distance 2^t−2^j has first coordinate 0.

Statement

theorem cycle_power_dyadic_sparse_defect_lower_rank (t j : ℕ) (ht : 4 ≤ t) (hj : j + 2 < t) :
  (Finset.range (2^j)).sum (fun a =>
    (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&
     decide (a + 2^t - 2^j ∈ 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 computes the sum of the joint indicator that both a and a + 2^t - 2^j lie in the defect support set for a < 2^j. Using arithmetic bounds on powers of 2, the proof first shows that 0 is the only element of the defect support strictly smaller than 2^j, so all non-zero terms in the sum vanish. Since both 0 and 2^t - 2^j belong to the support, the single term at a = 0 evaluates to 1, and Finset.sum_eq_single concludes that the entire sum is 1.

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

    Define q = 2^(t - 2). Since t ≥ 4, we have 2 ≤ t - 2 by linear arithmetic, and therefore q = 2^(t - 2) ≥ 2^2 = 4 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 ≥ 4, we have t = (t - 2) + 2. Using exponent addition (pow_add), 2^t = 2^((t - 2) + 2) = 2^(t - 2) * 2^2 = q * 4 = 4 * q, which is rearranged by 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. 2 * 2^j ≤ q.

    From j + 2 < t, linear arithmetic gives j + 1 ≤ t - 2. Monotonicity of exponentiation (Nat.pow_le_pow_right) yields 2^(j + 1) ≤ 2^(t - 2) = q. Rewriting 2^(j + 1) as 2^j * 2 = 2 * 2^j via pow_succ and commutativity (Nat.mul_comm) gives 2 * 2^j ≤ q.

    lines 15–17

    uses Nat.pow_le_pow_right, pow_succ, Nat.mul_comm

      have h2j : 2 * 2^j ≤ q := by
        have h := Nat.pow_le_pow_right (by decide : 0 < (2 : ℕ)) (show j+1 ≤ t-2 by omega)
        simpa [q, pow_succ, Nat.mul_comm] using h
  4. Any element of the defect support strictly less than 2^j must be 0.

    Let a < 2^j be an element of the defect support, which is the union of {0, q - 1} and the differences 2^t - 2^r for r < t - 2. By Finset.mem_union.mp, a belongs to one of these two sets: - If a ∈ {0, q - 1} (via Finset.mem_insert and Finset.mem_singleton), then either a = 0 or a = q - 1. The latter is ruled out because a < 2^j ≤ q / 2 < q - 1 for q ≥ 4. - If a = 2^t - 2^r for some r < t - 2 (via Finset.mem_image.mp and Finset.mem_range.mp), then 2^r < 2^(t - 2) = q by Nat.pow_lt_pow_right. But then a = 4*q - 2^r > 3*q, whereas a < 2^j ≤ q / 2, an arithmetic contradiction. Hence, a = 0 is the only support element below 2^j.

    lines 18–29

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

      have hlower : ∀ a, a < 2^j → a ∈ cycle_power_dyadic_sparse_defect_support t → a = 0 := by
        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
        · simp only [Finset.mem_insert, Finset.mem_singleton] at hsmall
          rcases hsmall with h0 | hq' <;> omega
        · 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. Both 0 and 2^t - 2^j belong to the defect support.

    By definition of the defect support, 0 belongs to the first component {0, q - 1}. For 2^t - 2^j, since j + 2 < t, we have j < t - 2, so j ∈ Finset.range (t - 2) by Finset.mem_range.mpr. Thus 2^t - 2^j belongs to the image component by Finset.mem_image.mpr, and therefore to the whole support by Finset.mem_union_right.

    lines 30–35

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

      have hz : 0 ∈ cycle_power_dyadic_sparse_defect_support t := by
        simp [cycle_power_dyadic_sparse_defect_support]
      have htop : 2^t - 2^j ∈ cycle_power_dyadic_sparse_defect_support t := by
        change 2^t-2^j ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)
        apply Finset.mem_union_right
        exact Finset.mem_image.mpr ⟨j, Finset.mem_range.mpr (by omega), rfl⟩
  6. The sum over a ∈ Finset.range (2^j) collapses to the single term at a = 0, which evaluates to 1.

    Applying Finset.sum_eq_single at 0 reduces the summation to three verification goals: 1. At a = 0, both 0 and 0 + 2^t - 2^j = 2^t - 2^j are in the support, so both boolean indicators are true and the summand evaluates to 1. 2. For any non-zero index a ∈ Finset.range (2^j), we have a < 2^j (Finset.mem_range.mp). If a were in the defect support, Step 4 would force a = 0, contradicting a ≠ 0; hence a is not in the support and the summand evaluates to 0. 3. Finally, 0 < 2^j holds because powers of 2 are positive (pow_pos), so 0 ∈ Finset.range (2^j) by Finset.mem_range.mpr.

    lines 36–46

    uses Finset.sum_eq_single, Finset.mem_range.mp, pow_pos, Finset.mem_range.mpr

      rw [Finset.sum_eq_single 0]
      · simp [hz, htop]
      · intro a ha hne
        have ha' : a < 2^j := Finset.mem_range.mp ha
        have hnot : a ∉ cycle_power_dyadic_sparse_defect_support t := by
          intro hm
          exact hne (hlower a ha' hm)
        simp [hnot]
      · intro hnot
        have hpos : 0 < 2^j := pow_pos (by decide) _
        exact (hnot (Finset.mem_range.mpr hpos)).elim
Nat.pow_le_pow_right
For any base n > 0, if i ≤ j then n^i ≤ n^j.
pow_add
In any monoid, powers add under multiplication: a^(m + n) = a^m * a^n.
pow_succ
In any monoid, a^(n + 1) = a^n * a.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Finset.mem_union.mp
If an element is in the union of two finite sets, it belongs to the first or the second.
Finset.mem_insert
An element is in the insertion insert b s if and only if it equals b or is in s.
Finset.mem_singleton
An element is in the singleton {a} if and only if it equals a.
Finset.mem_image.mp
If an element is in the image of a set under a function, it is the image of some element of that set.
Finset.mem_range.mp
If a natural number is in Finset.range n, it is strictly less than n.
Nat.pow_lt_pow_right
For any base a > 1, if m < n then a^m < a^n.
Finset.mem_union_right
If an element belongs to t, then it belongs to s ∪ t.
Finset.mem_image.mpr
If an element is the image of some element in a set under a function, it belongs to the image of that set.
Finset.mem_range.mpr
If a natural number is strictly less than n, it belongs to Finset.range n.
Finset.sum_eq_single
A finite sum equals the single term f(a) if all other terms in the index set vanish and f(a) = 0 whenever a is not in the set.
pow_pos
Any natural power of a strictly positive element is strictly positive.

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_lower_rank (t j : ℕ) (ht : 4 ≤ t) (hj : j + 2 < t) :  (Finset.range (2^j)).sum (fun a =>    (decide (a ∈ cycle_power_dyadic_sparse_defect_support t) &&     decide (a + 2^t - 2^j ∈ cycle_power_dyadic_sparse_defect_support t)).toNat) = 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 h2j : 2 * 2^j ≤ q := by    have h := Nat.pow_le_pow_right (by decide : 0 < (2 : ℕ)) (show j+1 ≤ t-2 by omega)    simpa [q, pow_succ, Nat.mul_comm] using h  have hlower : ∀ a, a < 2^j → a ∈ cycle_power_dyadic_sparse_defect_support t → a = 0 := by    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    · simp only [Finset.mem_insert, Finset.mem_singleton] at hsmall      rcases hsmall with h0 | hq' <;> omega    · 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  have hz : 0 ∈ cycle_power_dyadic_sparse_defect_support t := by    simp [cycle_power_dyadic_sparse_defect_support]  have htop : 2^t - 2^j ∈ cycle_power_dyadic_sparse_defect_support t := by    change 2^t-2^j ∈ ({0,q-1} : Finset ℕ) ∪ (Finset.range (t-2)).image (fun r => 2^t-2^r)    apply Finset.mem_union_right    exact Finset.mem_image.mpr ⟨j, Finset.mem_range.mpr (by omega), rfl⟩  rw [Finset.sum_eq_single 0]  · simp [hz, htop]  · intro a ha hne    have ha' : a < 2^j := Finset.mem_range.mp ha    have hnot : a ∉ cycle_power_dyadic_sparse_defect_support t := by      intro hm      exact hne (hlower a ha' hm)    simp [hnot]  · intro hnot    have hpos : 0 < 2^j := pow_pos (by decide) _    exact (hnot (Finset.mem_range.mpr hpos)).elim
See it in the graphDiscuss this resultChallenge it