cycle_power_dyadic_class_weight_reflect
The dyadic class weight is invariant under reversing the offset interval.
Statement
theorem cycle_power_dyadic_class_weight_reflect (t : ℕ) (b : ℕ → Bool) : cycle_power_dyadic_class_weight t (fun a => b (2^t-1-a)) = cycle_power_dyadic_class_weight t b
- Source
- Defective half-model reduction for research thread RT-1.
- Verified
- 10 Nov 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_reflect_defective_half_modelReflecting a defective half model reverses its defect function and changes its top-owner phase from shift to half-span minus shift.
The proof, explained
The proof unfolds the definition of dyadic class weight into a boundary term and a sum of inner sums over dyadic offsets. Reflection swaps the boundary indices 0 and 2^t - 1, leaving the boundary term invariant by commutativity of boolean conjunction. For each dyadic scale j < t, reversing the inner sum over [0, 2^j) via Finset.sum_range_reflect interchanges the two sampled evaluation points a and a + 2^t - 2^j, so each summand is likewise invariant by boolean commutativity.
The boundary terms match, reducing the equality to the summation over dyadic scales j ∈ [0, t).
Unfolding the definition of cycle_power_dyadic_class_weight, the boundary term for the reflected function is 2 * (b(2^t - 1 - 0) && b(2^t - 1 - (2^t - 1))). Evaluating 2^t - 1 - 0 = 2^t - 1 using Nat.sub_zero and 2^t - 1 - (2^t - 1) = 0 via linear arithmetic, this becomes 2 * (b(2^t - 1) && b(0)). By Bool.and_comm, this equals the boundary term 2 * (b(0) && b(2^t - 1)) of the original function. Canceling these identical terms leaves only the sums over j ∈ [0, t).
uses
Nat.two_pow_pos,Nat.sub_zero,Bool.and_commhave hpos : 0 < (2:ℕ)^t := Nat.two_pow_pos t unfold cycle_power_dyadic_class_weight simp only [Nat.sub_zero] have he : 2^t-1-(2^t-1)=0 := by omega rw [he, Bool.and_comm (b (2^t-1)) (b 0)] congr 1
It suffices to show the inner sums agree for each non-zero scale j < t.
Using Finset.sum_congr, the equality of the outer sums reduces to showing that their summands match for each j ∈ [0, t). When j = 0, both summands are 0 by definition, which holds trivially.
uses
Finset.sum_congrapply Finset.sum_congr rfl intro j hj split_ifs with hj0 · rfl
Reversing the inner summation over [0, 2^j) reduces the goal to matching summands pointwise for each index a < 2^j.
For j > 0 with j < t (from Finset.mem_range.mp), we have 2^j ≤ 2^t (by Nat.pow_le_pow_right) and 0 < 2^j (by Nat.two_pow_pos). Applying Finset.sum_range_reflect reverses the inner sum over [0, 2^j), substituting 2^j - 1 - a for the index. By Finset.sum_congr, it now suffices to show that each term of this reversed sum equals the corresponding original term.
uses
Finset.mem_range.mp,Nat.pow_le_pow_right,Nat.two_pow_pos,Finset.sum_range_reflect,Finset.sum_congr· have hjt : j < t := Finset.mem_range.mp hj have hjpow : (2:ℕ)^j ≤ 2^t := Nat.pow_le_pow_right (by norm_num) (by omega) have hL : 0 < (2:ℕ)^j := Nat.two_pow_pos j rw [← Finset.sum_range_reflect] apply Finset.sum_congr rfl
Each term in the reversed inner sum equals the corresponding original term.
For each a < 2^j (from Finset.mem_range.mp), index arithmetic simplifies 2^t - 1 - (2^j - 1 - a) to a + 2^t - 2^j and 2^t - 1 - ((2^j - 1 - a) + 2^t - 2^j) to a. Rewriting the reflected summand with these identities yields b(a + 2^t - 2^j) && b(a), which equals b(a) && b(a + 2^t - 2^j) by Bool.and_comm, matching the original summand.
uses
Finset.mem_range.mp,Bool.and_commintro a ha have haL : a < 2^j := Finset.mem_range.mp ha have hidx₁ : 2^t-1-(2^j-1-a)=a+2^t-2^j := by omega have hidx₂ : 2^t-1-((2^j-1-a)+2^t-2^j)=a := by omega rw [hidx₁,hidx₂,Bool.and_comm]
Nat.two_pow_pos- For any natural number w, 2^w is strictly positive.
Nat.sub_zero- Subtracting zero from any natural number n leaves n unchanged.
Bool.and_comm- Boolean conjunction is commutative: x && y = y && x.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summand functions agree on every element of the set.
Finset.mem_range.mp- An element x belongs to range n if and only if x < n.
Nat.pow_le_pow_right- For a positive base n > 0, exponentiation preserves non-strict inequality: if i ≤ j then n^i ≤ n^j.
Finset.sum_range_reflect- Reversing the summation order over range n preserves the sum: summing f(n - 1 - j) for j ∈ range n equals summing f(j).
- The index arithmetic identities on lines 9, 23, and 24 involve truncated subtraction on natural numbers, handled by the `omega` decision procedure.
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 Finsettheorem cycle_power_dyadic_class_weight_reflect (t : ℕ) (b : ℕ → Bool) : cycle_power_dyadic_class_weight t (fun a => b (2^t-1-a)) = cycle_power_dyadic_class_weight t b := by have hpos : 0 < (2:ℕ)^t := Nat.two_pow_pos t unfold cycle_power_dyadic_class_weight simp only [Nat.sub_zero] have he : 2^t-1-(2^t-1)=0 := by omega rw [he, Bool.and_comm (b (2^t-1)) (b 0)] congr 1 apply Finset.sum_congr rfl intro j hj split_ifs with hj0 · rfl · have hjt : j < t := Finset.mem_range.mp hj have hjpow : (2:ℕ)^j ≤ 2^t := Nat.pow_le_pow_right (by norm_num) (by omega) have hL : 0 < (2:ℕ)^j := Nat.two_pow_pos j rw [← Finset.sum_range_reflect] apply Finset.sum_congr rfl intro a ha have haL : a < 2^j := Finset.mem_range.mp ha have hidx₁ : 2^t-1-(2^j-1-a)=a+2^t-2^j := by omega have hidx₂ : 2^t-1-((2^j-1-a)+2^t-2^j)=a := by omega rw [hidx₁,hidx₂,Bool.and_comm]