AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_reflect

theoremverified

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

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.

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

    lines 6–11

    uses Nat.two_pow_pos, Nat.sub_zero, Bool.and_comm

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

    lines 12–15

    uses Finset.sum_congr

      apply Finset.sum_congr rfl
      intro j hj
      split_ifs with hj0
      · rfl
  3. 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.

    lines 16–20

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

    lines 21–25

    uses Finset.mem_range.mp, Bool.and_comm

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

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