cycle_power_dyadic_sparse_defect_top_rank
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
- 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
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.
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`).
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-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.
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 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.
uses
Finset.mem_union.mp,Finset.mem_insert,Finset.mem_singletonrefine ⟨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
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.
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
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.
uses
rt1_sparse_bounds_top865classical let q : ℕ := 2^(t-2) obtain ⟨hq,hD,hsmall⟩ := rt1_sparse_bounds_top865 t ht
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.
uses
pow_succhave 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]
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`.
uses
Finset.sum_eq_zero,Finset.mem_range.mpapply Finset.sum_eq_zero intro a ha have ha' : a < 2*q := Finset.mem_range.mp ha
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.
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
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_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]