cycle_power_dyadic_class_weight_as_tree_edges
For a positive-exponent dyadic profile containing both endpoints, its weighted class count is one plus its unweighted number of selected dyadic pairs over all ranks.
Statement
theorem cycle_power_dyadic_class_weight_as_tree_edges (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) (hends : b 0 = true ∧ b (2^m-1) = true) : cycle_power_dyadic_class_weight m b = 1 + (range m).sum (fun j => (range (2^j)).sum (fun a => (b a && b (a+2^m-2^j)).toNat))
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- Used by 1
- cycle_power_dyadic_gap_side_treeBetween two full roots at distance g at most the radius, the compressed sides of every interior tight class satisfy the tree identity:…
The proof, explained
The definition of cycle_power_dyadic_class_weight treats rank j = 0 specially: it weights the single dyadic pair at rank 0 by 2 in a separate leading term, while replacing the j = 0 term with 0 inside the rank summation. Since both endpoints are active, that rank 0 pair is present, so f(0) = 1 and the leading term is 2. The proof decomposes f(j) into the zeroed-out summand plus an indicator for j = 0, sums over j < m, and concludes by linear arithmetic that 2 + ∑_{j=1}^{m-1} f(j) = 1 + ∑_{j=0}^{m-1} f(j).
Define f(j) as the number of matching dyadic pairs at rank j, and establish that f(0) = 1.
For each rank j, f(j) is defined as the sum over a < 2^j of the indicators that both b(a) and b(a + 2^m - 2^j) are true. At rank j = 0, 2^0 = 1, so the sum contains only the a = 0 term: b(0) && b(2^m - 1). Because both endpoints are assumed to be true, this term evaluates to 1.
uses
pow_zero,sum_range_one,zero_add,Bool.true_and,Bool.toNat_truelet f : ℕ → ℕ := fun j => (range (2^j)).sum (fun a => (b a && b (a+2^m-2^j)).toNat) have hf₀ : f 0 = 1 := by simp only [f, pow_zero, sum_range_one, zero_add, hends.1, hends.2, Bool.true_and, Bool.toNat_true]
The sum over j < m of the indicator [j = 0] equals 1. automation
Since 1 ≤ m, we have 0 < m, so 0 is contained in the range {0, ..., m - 1}. The summand is 1 at j = 0 and 0 for all other j, so the total sum is 1.
have hi : (range m).sum (fun j => if j = 0 then 1 else 0) = 1 := by simp [show 0 < m by omega]
For every j, (if j = 0 then 0 else f(j)) + [j = 0] = f(j).
We split into cases on whether j = 0. When j = 0, the sum is 0 + 1 = 1, which equals f(0). When j ≠ 0, the sum is f(j) + 0 = f(j).
uses
if_neg,add_zerohave hp (j : ℕ) : (if j = 0 then 0 else f j) + (if j = 0 then 1 else 0) = f j := by by_cases hj : j = 0 · subst j simp [hf₀] · simp only [if_neg hj, add_zero]
∑_{j < m} (if j = 0 then 0 else f(j)) + 1 = ∑_{j < m} f(j).
Summing the pointwise identity from the previous step over all j < m and distributing the sum over addition yields the modified sum plus the indicator sum. Substituting the indicator sum value of 1 produces the identity.
uses
sum_congr,sum_add_distribhave hs := sum_congr rfl (fun j (hj : j ∈ range m) => hp j) rw [sum_add_distrib, hi] at hs
The goal simplifies to 2 + ∑_{j < m} (if j = 0 then 0 else f(j)) = 1 + ∑_{j < m} f(j).
Unfolding the definition of cycle_power_dyadic_class_weight, the leading boundary term 2 * (b(0) && b(2^m - 1)).toNat simplifies to 2 * 1 = 2 using the endpoint hypotheses, while the remaining summation matches the modified sum of f where the j = 0 rank is replaced by 0.
uses
cycle_power_dyadic_class_weight,Bool.true_and,Bool.toNat_true,mul_onesimp only [cycle_power_dyadic_class_weight, hends.1, hends.2, Bool.true_and, Bool.toNat_true, mul_one] change 2 + (range m).sum (fun j => if j = 0 then 0 else f j) = 1 + (range m).sum f
The equality holds, concluding the proof. automation
The identity from Step 4 shows that ∑_{j < m} f(j) = (∑_{j < m} (if j = 0 then 0 else f(j))) + 1. Substituting this into the right-hand side gives 1 + (∑_{j < m} ... + 1) = 2 + ∑_{j < m} ..., which closes the goal by linear arithmetic.
omega
pow_zero- Any element raised to the power 0 equals 1 (a ^ 0 = 1).
sum_range_one- The sum of a function over the singleton range {0} has a single term, f(0).
zero_add- Adding 0 on the left is the identity (0 + a = a).
Bool.true_and- Boolean conjunction with true on the left preserves the boolean value (true && b = b).
Bool.toNat_true- The boolean value true converts to the natural number 1.
if_neg- If the condition c is false, then (if c then t else e) evaluates to the else-branch e.
add_zero- Adding 0 on the right is the identity (a + 0 = a).
sum_congr- Two sums over the same finite set are equal if their summands agree on every element of the set.
sum_add_distrib- The sum of a pointwise sum of two functions equals the sum of their individual sums.
cycle_power_dyadic_class_weight- The weighted dyadic class count of profile b: twice the indicator that both endpoints are true, plus the sum over ranks 1 ≤ j < m of matching dyadic pairs.
mul_one- Multiplying by 1 on the right is the identity (a * 1 = a).
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_class_weight_as_tree_edges (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) (hends : b 0 = true ∧ b (2^m-1) = true) : cycle_power_dyadic_class_weight m b = 1 + (range m).sum (fun j => (range (2^j)).sum (fun a => (b a && b (a+2^m-2^j)).toNat)) := by let f : ℕ → ℕ := fun j => (range (2^j)).sum (fun a => (b a && b (a+2^m-2^j)).toNat) have hf₀ : f 0 = 1 := by simp only [f, pow_zero, sum_range_one, zero_add, hends.1, hends.2, Bool.true_and, Bool.toNat_true] have hi : (range m).sum (fun j => if j = 0 then 1 else 0) = 1 := by simp [show 0 < m by omega] have hp (j : ℕ) : (if j = 0 then 0 else f j) + (if j = 0 then 1 else 0) = f j := by by_cases hj : j = 0 · subst j simp [hf₀] · simp only [if_neg hj, add_zero] have hs := sum_congr rfl (fun j (hj : j ∈ range m) => hp j) rw [sum_add_distrib, hi] at hs simp only [cycle_power_dyadic_class_weight, hends.1, hends.2, Bool.true_and, Bool.toNat_true, mul_one] change 2 + (range m).sum (fun j => if j = 0 then 0 else f j) = 1 + (range m).sum f omega