AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_congr

theoremverified

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

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

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

    lines 4–7

    uses Nat.two_pow_pos

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

    lines 8–12

    uses sum_congr, Nat.pow_le_pow_right, le_of_lt, mem_range.mp

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

    lines 13–16

    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.

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

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