cycle_power_dyadic_sparse_defect_lower_rank
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
- cycle_power_dyadic_sparse_defect_supportFor exponent t, the sparse constant defect support consists of 0, 2^(t−2)−1, and 2^t−2^j for all j<t−2.
- Used by 1
- cycle_power_dyadic_sparse_defect_weightThe dyadic class weight of the sparse defect support is t for every t≥4.
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.
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).
uses
Nat.pow_le_pow_rightclassical 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^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.
uses
pow_addhave 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
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.
uses
Nat.pow_le_pow_right,pow_succ,Nat.mul_commhave 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
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.
uses
Finset.mem_union.mp,Finset.mem_insert,Finset.mem_singleton,Finset.mem_image.mp,Finset.mem_range.mp,Nat.pow_lt_pow_righthave 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
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.
uses
Finset.mem_union_right,Finset.mem_image.mpr,Finset.mem_range.mprhave 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⟩
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.
uses
Finset.sum_eq_single,Finset.mem_range.mp,pow_pos,Finset.mem_range.mprrw [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.
- Lines 44–46 discharge the formal requirement of Finset.sum_eq_single that a ∉ s → f(a) = 0 by showing 0 < 2^j, a detail that is typically implicit on paper.
- Line 5 activates classical reasoning so that decidability of set membership can be used freely for boolean evaluation.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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