cycle_power_dyadic_sparse_defect_penultimate_rank
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
- 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 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.
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.
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 = 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.
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
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.
uses
Finset.mem_union.mp,Finset.mem_insert,Finset.mem_singleton,Finset.mem_image.mp,Finset.mem_range.mp,Nat.pow_lt_pow_rightrefine ⟨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
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.
uses
rt1_sparse_bounds865classical 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
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.
uses
Finset.mem_union_right,Finset.mem_image.mpr,Finset.mem_range.mprhave 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
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 ℕ.
have hnot3q : 3*q ∉ cycle_power_dyadic_sparse_defect_support t := by intro hm have h := hsmall (3*q) (by omega) hm omega
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.
uses
Finset.sum_eq_singlerw [Finset.sum_eq_single (q-1)] · have heq : (q-1)+2^t-q = 2^t-1 := by omega simp [hsmallmem, heq, htopmem]
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.
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]
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.
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.
- The indicator function for pairs in the defect support is formalized as a product of boolean tests cast to natural numbers via Bool.toNat.
- Applying Finset.sum_eq_single introduces an extra condition that the singled-out index q - 1 lies in the summation domain Finset.range q, which is discharged at the end of the proof by linear arithmetic.
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.
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