cycle_power_dyadic_class_weight_congr
The dyadic class weight cycle_power_dyadic_class_weight m b depends only on the values b i for i < 2^m: if b i = b' i for every i < 2^m, the two weights are equal.
Statement
theorem cycle_power_dyadic_class_weight_congr (m : ℕ) (b b' : ℕ → Bool)
(hb : ∀ i < 2 ^ m, b i = b' i) :
cycle_power_dyadic_class_weight m b = cycle_power_dyadic_class_weight m b'- Source
- Research thread RT-1, OP-205 (arXiv:2610.15635, Theorems 1.3-1.4: eq(C_n^k) for k+1 = 2^m, n even, (k+1) not dividing n). Helper for cycle_power_dyadic_no_island_of_alternating_paired.
- Verified
- 31 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_no_island_of_alternating_pairedUniform induction step for the no-island class shape. Let m ≥ 1 and suppose every tight, exactly dyadically covered, fully ordinarily…
The proof, explained
The proof unfolds the definition of the dyadic class weight into a leading term and a summation over j < m. The leading terms match because the hypothesis hb equates b and b' on 0 and 2^m - 1. For the outer sum, the j = 0 case is trivially 0 on both sides, while for j > 0, every index accessed in the inner sum—namely i and i + 2^m - 2^j for i < 2^j—is strictly less than 2^m, allowing hb to rewrite all occurrences of b to b'.
The leading terms of the weight definition match, reducing the goal to showing equality of the sums over j < m.
We establish that 0 < 2^m via Nat.two_pow_pos and expand the definition of cycle_power_dyadic_class_weight. The leading term is 2 * (b 0 && b (2^m - 1)).toNat. Because 0 < 2^m and 2^m - 1 < 2^m, the hypothesis hb gives b 0 = b' 0 and b (2^m - 1) = b' (2^m - 1). Rewriting with these equalities makes the leading terms on both sides identical, so congruence reduces the goal to proving the equality of the remaining summations over j ∈ Finset.range m.
uses
Nat.two_pow_poshave hpos : 0 < 2 ^ m := Nat.two_pow_pos m unfold cycle_power_dyadic_class_weight rw [hb 0 hpos, hb (2 ^ m - 1) (by omega)] congr 1
For each j < m, it suffices to equate the j-th summands, which holds trivially when j = 0.
Using sum_congr, we reduce the equality of the outer sums to showing that their terms agree for each j < m. Using mem_range.mp and Nat.pow_le_pow_right, we note that j < m implies 2^j ≤ 2^m. We then split into cases on whether j = 0. When j = 0, both sides evaluate to 0 by definition and match by reflexivity.
uses
sum_congr,Nat.pow_le_pow_right,le_of_lt,mem_range.mpapply sum_congr rfl intro j hj have hjm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (le_of_lt (mem_range.mp hj)) split_ifs · rfl
When j ≠ 0, each term in the inner sum over i < 2^j evaluates to the same value for b and b'.
For j ≠ 0, the summand is an inner sum over i < 2^j. Applying sum_congr again, it suffices to show that each term (b i && b (i + 2^m - 2^j)).toNat equals (b' i && b' (i + 2^m - 2^j)).toNat. Since i < 2^j and 2^j ≤ 2^m, we have i < 2^m and i + 2^m - 2^j < 2^m. Thus hb applies to both index arguments, substituting b with b' and completing the proof.
uses
sum_congr,mem_range.mp· apply sum_congr rfl intro i hi have hi' := mem_range.mp hi rw [hb i (by omega), hb (i + 2 ^ m - 2 ^ j) (by omega)]
Nat.two_pow_pos- For any natural number w, 2^w is strictly positive.
sum_congr- If two finite sets are equal and their summands agree on every element, then the sums are equal.
Nat.pow_le_pow_right- For a base n > 0, exponentiation preserves order: if i ≤ j, then n^i ≤ n^j.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
mem_range.mp- If a natural number belongs to Finset.range n, then it is strictly less than n.
- The index bounds 2^m - 1 < 2^m, i < 2^m, and i + 2^m - 2^j < 2^m required to apply the hypothesis hb are discharged automatically by the Presburger arithmetic tactic `omega`.
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_class_weight_congr (m : ℕ) (b b' : ℕ → Bool) (hb : ∀ i < 2 ^ m, b i = b' i) : cycle_power_dyadic_class_weight m b = cycle_power_dyadic_class_weight m b' := open Finset in by have hpos : 0 < 2 ^ m := Nat.two_pow_pos m unfold cycle_power_dyadic_class_weight rw [hb 0 hpos, hb (2 ^ m - 1) (by omega)] congr 1 apply sum_congr rfl intro j hj have hjm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (le_of_lt (mem_range.mp hj)) split_ifs · rfl · apply sum_congr rfl intro i hi have hi' := mem_range.mp hi rw [hb i (by omega), hb (i + 2 ^ m - 2 ^ j) (by omega)]