AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_neighbour_pair_count_prune_low

theoremverified

Deleting the middle two quarters preserves each strictly smaller neighbour pair count.

Statement

theorem cycle_power_dyadic_neighbour_pair_count_prune_low
    (k j : ℕ) (hj : j < k) (b : ℕ → Bool) :
    cycle_power_dyadic_neighbour_pair_count (k + 2) j b =
      cycle_power_dyadic_neighbour_pair_count (k + 1) j (cycle_power_dyadic_b_lift k b)
Source
Uniform helpers for OP-205 / RT-1 following arXiv:2610.15635, Section 3. The neighbour-weight induction and central occurrence are class-model helpers; they do not prove the unresolved covering number. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem states that pruning the middle two quarters of a sequence of length 2 ^ (k + 2) down to length 2 ^ (k + 1) (via cycle_power_dyadic_b_lift) preserves each dyadic neighbour pair count at strictly smaller scales j < k. Both counts are defined as sums over indices a ≤ 2 ^ j of the product of two sequence values. The proof establishes equality term-by-term using sum_congr: since 2 ^ j < 2 ^ k, the first index a lies in the first quarter [0, 2 ^ k) where the lifted sequence coincides with the original, while the second index falls into the fourth quarter, where the lift shifts the argument by 2 ^ (k + 1) to match the original index at scale k + 2.

  1. 2 ^ j < 2 ^ k

    Because 1 < 2 and j < k, the base-2 exponential function is strictly increasing, so 2 ^ j < 2 ^ k by Nat.pow_lt_pow_right.

    line 7

    uses Nat.pow_lt_pow_right

      have hpow : 2 ^ j < 2 ^ k := Nat.pow_lt_pow_right (by decide) hj
  2. 2 ^ (k + 1) = 2 * 2 ^ k and 2 ^ (k + 2) = 2 * 2 ^ (k + 1)

    Each power identity is obtained by rewriting the successor power into 2 ^ m * 2 using pow_succ and commuting the factors with linear arithmetic.

    lines 8–9

    uses pow_succ

      have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega
      have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega
  3. It suffices to show that the summands coincide for each index a ≤ 2 ^ j.

    By sum_congr, equality of the two sums follows if their summands agree across the index set. The summation domain is range (2 ^ j + 1), which means a < 2 ^ j + 1 by mem_range, or equivalently a ≤ 2 ^ j by Nat.lt_succ_iff.

    lines 10–12

    uses sum_congr, mem_range, Nat.lt_succ_iff

      apply sum_congr rfl
      intro a ha
      have ha : a ≤ 2 ^ j := by simpa only [mem_range, Nat.lt_succ_iff] using ha
  4. cycle_power_dyadic_b_lift k b a = b a

    Unfolding cycle_power_dyadic_b_lift, the value at a is given by testing whether a < 2 ^ k. Since a ≤ 2 ^ j and 2 ^ j < 2 ^ k, this inequality holds, so if_pos selects the first branch b a.

    lines 13–14

    uses if_pos

      have hlo : cycle_power_dyadic_b_lift k b a = b a := by
        dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)]
  5. cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j - 1) = b (a + 2 ^ (k + 2) - 2 ^ j - 1)

    Unfolding cycle_power_dyadic_b_lift at the shifted index, the branch condition is a + 2 ^ (k + 1) - 2 ^ j - 1 < 2 ^ k. Because 2 ^ (k + 1) = 2 * 2 ^ k and 2 ^ j < 2 ^ k, this index is at least 2 ^ k, making the condition false. Applying if_neg selects the second branch, evaluating b at (a + 2 ^ (k + 1) - 2 ^ j - 1) + 2 ^ (k + 1). Linear arithmetic then verifies that this argument equals a + 2 ^ (k + 2) - 2 ^ j - 1.

    lines 15–19

    uses if_neg

      have hhi : cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j - 1) =
          b (a + 2 ^ (k + 2) - 2 ^ j - 1) := by
        dsimp [cycle_power_dyadic_b_lift]
        rw [if_neg (by omega)]
        congr 1; omega
  6. The summands are equal, completing the proof.

    Rewriting the lifted terms using the identities established in the previous two steps transforms the summand of the lifted count into that of the original count.

    line 20

      rw [hlo, hhi]
Nat.pow_lt_pow_right
For a base greater than 1, strictly smaller exponents give strictly smaller powers: if 1 < a and m < n, then a ^ m < a ^ n.
pow_succ
Powers in a monoid satisfy a ^ (n + 1) = a ^ n * a.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every element of the index set.
mem_range
A natural number m belongs to range n if and only if m < n.
Nat.lt_succ_iff
A natural number m is strictly less than n + 1 if and only if m ≤ n.
if_pos
If condition c is true, then if c then t else e evaluates to t.
if_neg
If condition c is false, then if c then t else e evaluates to e.

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_neighbour_pair_count_prune_low    (k j : ℕ) (hj : j < k) (b : ℕ → Bool) :    cycle_power_dyadic_neighbour_pair_count (k + 2) j b =      cycle_power_dyadic_neighbour_pair_count (k + 1) j (cycle_power_dyadic_b_lift k b) := by  have hpow : 2 ^ j < 2 ^ k := Nat.pow_lt_pow_right (by decide) hj  have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega  have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega  apply sum_congr rfl  intro a ha  have ha : a ≤ 2 ^ j := by simpa only [mem_range, Nat.lt_succ_iff] using ha  have hlo : cycle_power_dyadic_b_lift k b a = b a := by    dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)]  have hhi : cycle_power_dyadic_b_lift k b (a + 2 ^ (k + 1) - 2 ^ j - 1) =      b (a + 2 ^ (k + 2) - 2 ^ j - 1) := by    dsimp [cycle_power_dyadic_b_lift]    rw [if_neg (by omega)]    congr 1; omega  rw [hlo, hhi]
See it in the graphDiscuss this resultChallenge it