AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_as_tree_edges

theoremverified

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).

  1. 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.

    lines 10–13

    uses pow_zero, sum_range_one, zero_add, Bool.true_and, Bool.toNat_true

      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]
  2. 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.

    lines 14–15

      have hi : (range m).sum (fun j => if j = 0 then 1 else 0) = 1 := by
        simp [show 0 < m by omega]
  3. 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).

    lines 16–20

    uses if_neg, add_zero

      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]
  4. ∑_{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.

    lines 21–22

    uses sum_congr, sum_add_distrib

      have hs := sum_congr rfl (fun j (hj : j ∈ range m) => hp j)
      rw [sum_add_distrib, hi] at hs
  5. 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.

    lines 23–25

    uses cycle_power_dyadic_class_weight, Bool.true_and, Bool.toNat_true, mul_one

      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
  6. 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.

    line 26

      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

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
See it in the graphDiscuss this resultChallenge it