AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_neighbour_pair_count_prune_top

theoremverified

At the boundary rank of middle-quarter pruning, the neighbour pair count changes by exactly four boundary bits.

Statement

theorem cycle_power_dyadic_neighbour_pair_count_prune_top
    (k : ℕ) (b : ℕ → Bool) (hroot : b 0 = true ∧ b (2 ^ (k + 2) - 1) = true) :
    cycle_power_dyadic_neighbour_pair_count (k + 2) k b +
        (b (2 ^ k - 1)).toNat + (b (3 * 2 ^ k)).toNat =
      cycle_power_dyadic_neighbour_pair_count (k + 1) k (cycle_power_dyadic_b_lift k b) +
        (b (3 * 2 ^ k - 1)).toNat + (b (2 ^ k)).toNat
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

Letting q = 2^k, both neighbour pair sums range over indices a ∈ [0, q] and are split into their initial term (a = 0), their final term (a = q), and the interior sum (a ∈ [1, q - 1]). For all interior terms, the definition of the pruning lift shifts indices in such a way that the lifted summand exactly equals the original summand, making the two interior sums coincide. Evaluating the lifted bits at the boundaries using the root hypotheses b(0) = true and b(4*q - 1) = true shows that both sides reduce to the interior sum plus the exact same four boundary bits, establishing the identity.

  1. Setting q = 2^k, we have q > 0, 2^(k+1) = 2*q, 2^(k+2) = 4*q, b(0) = true, and b(4*q - 1) = true.

    We introduce the block size q = 2^k, establish the powers of 2 in terms of q by exponent induction, and extract the boundary root conditions b(0) = true and b(4*q - 1) = true from the hypothesis hroot.

    lines 9–14

    uses Nat.two_pow_pos, pow_succ

      let q := 2 ^ k
      have hq : 0 < q := Nat.two_pow_pos k
      have hH : 2 ^ (k + 1) = 2 * q := by dsimp [q]; rw [pow_succ]; omega
      have hD : 2 ^ (k + 2) = 4 * q := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega
      have hr0 : b 0 = true := hroot.1
      have hr1 : b (4 * q - 1) = true := by simpa only [hD] using hroot.2
  2. For any sequence f, the sum over range (q + 1) splits into the initial term f(0), the interior sum over a ∈ range (q - 1) of f(a + 1), and the final term f(q).

    We decompose the sum over range (q + 1) by peeling off the last element q via sum_range_succ and then peeling off the initial element 0 via sum_range_succ', leaving the interior sum over a + 1 for a < q - 1.

    lines 15–20

    uses sum_range_succ, sum_range_succ'

      have hsplit (f : ℕ → ℕ) :
          (range (q + 1)).sum f = f 0 + (range (q - 1)).sum (fun a => f (a+1)) + f q := by
        have hqr : q + 1 = (q - 1 + 1) + 1 := by omega
        rw [hqr, sum_range_succ, sum_range_succ']
        rw [show q-1+1=q by omega]
        omega
  3. For every interior index a < q - 1, the lifted summand equals the original summand.

    For a + 1 with a < q - 1, we have 1 ≤ a + 1 < q, so the lift condition a + 1 < q is satisfied and the first factor evaluates to b(a + 1). The paired index (a + 1) + 2*q - q - 1 = a + q satisfies ¬(a + q < q), so by definition of the lift it shifts by 2^(k+1) = 2*q, giving b(a + q + 2*q) = b(a + 3*q), which matches the original paired index (a + 1) + 4*q - q - 1 = a + 3*q.

    lines 21–28

    uses if_pos, if_neg

      have hb : ∀ a < q - 1,
          (cycle_power_dyadic_b_lift k b (a+1) &&
            cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat =
          (b (a+1) && b (a+1+4*q-q-1)).toNat := by
        intro a ha
        dsimp [cycle_power_dyadic_b_lift]
        rw [if_pos (by dsimp [q] at *; omega), if_neg (by dsimp [q] at *; omega)]
        congr 2; congr 1; omega
  4. Unfolding neighbour pair counts and decomposing both sums isolates the boundary terms from the interior sums.

    We unfold the definition of cycle_power_dyadic_neighbour_pair_count, replace 2^k by q, 2^(k+1) by 2*q, and 2^(k+2) by 4*q, and apply the splitting lemma hsplit to both sides.

    lines 29–30

      unfold cycle_power_dyadic_neighbour_pair_count
      rw [show 2^k=q from rfl, hD, hH, hsplit, hsplit]
  5. The interior sums on both sides are identical and can be equated.

    By sum_congr and lemma hb, since each interior term in the lifted sum equals the corresponding term in the unlifted sum, the two interior sums are equal and simplify against each other.

    lines 31–36

    uses sum_congr, mem_range.mp

      have hmid : (range (q-1)).sum (fun a =>
          (cycle_power_dyadic_b_lift k b (a+1) &&
            cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat) =
          (range (q-1)).sum (fun a => (b (a+1) && b (a+1+4*q-q-1)).toNat) :=
        sum_congr rfl (fun a ha => hb a (mem_range.mp ha))
      rw [hmid]
  6. The boundary values of the lifted function evaluate to b(0), b(3*q), b(q - 1), and b(4*q - 1).

    We evaluate cycle_power_dyadic_b_lift at each boundary index by checking whether the index is strictly less than q: at 0 (< q) it gives b(0); at q (≥ q) it shifts by 2*q to give b(3*q); at 0 + 2*q - q - 1 = q - 1 (< q) it gives b(q - 1); and at q + 2*q - q - 1 = 2*q - 1 (≥ q) it shifts by 2*q to give b(4*q - 1).

    lines 37–47

    uses if_pos, if_neg

      have hz : cycle_power_dyadic_b_lift k b 0 = b 0 := by
        dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hq]
      have hqlo : cycle_power_dyadic_b_lift k b q = b (3*q) := by
        dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)]
        congr 1; omega
      have hleft : cycle_power_dyadic_b_lift k b (0 + 2*q-q-1) = b (q-1) := by
        dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)]
        congr 1; omega
      have hright : cycle_power_dyadic_b_lift k b (q + 2*q-q-1) = b (4*q-1) := by
        dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)]
        congr 1; omega
  7. Substituting the boundary values and simplifying boolean conjunctions balances the equation. automation

    We substitute the boundary evaluations and the root conditions b(0) = true and b(4*q - 1) = true. Using Bool.true_and and Bool.and_true, the conjunctions with true simplify away. Both sides of the equation then consist of the same five terms (the interior sum and four boundary bit values: b(3*q - 1), b(q), b(q - 1), and b(3*q)), so linear integer arithmetic closes the goal.

    lines 48–53

    uses Bool.true_and, Bool.and_true

      rw [hz, hqlo, hleft, hright, hr0, hr1]
      have he0 : 0 + 4*q-q-1=3*q-1 := by omega
      have he1 : q+4*q-q-1=4*q-1 := by omega
      rw [he0, he1, hr1]
      simp only [Bool.true_and, Bool.and_true]
      omega
Nat.two_pow_pos
For any natural number w, 2^w is strictly positive.
pow_succ
In any monoid, a^(n+1) = a^n * a.
sum_range_succ
Peeling the last term off a sum: the sum of f over range (n+1) is the sum over range n plus f(n).
sum_range_succ'
Peeling the first term off a sum: the sum of f over range (n+1) is the sum of f(k+1) over range n plus f(0).
if_pos
If condition c holds, the conditional expression (if c then t else e) evaluates to t.
if_neg
If condition c is false, the conditional expression (if c then t else e) evaluates to e.
sum_congr
If two index sets are equal and their summands agree on all elements, the sums are equal.
mem_range.mp
If m is in range n, then m < n.
Bool.true_and
For any boolean b, true && b is equal to b.
Bool.and_true
For any boolean b, b && true is equal to b.

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_top    (k : ℕ) (b : ℕ → Bool) (hroot : b 0 = true ∧ b (2 ^ (k + 2) - 1) = true) :    cycle_power_dyadic_neighbour_pair_count (k + 2) k b +        (b (2 ^ k - 1)).toNat + (b (3 * 2 ^ k)).toNat =      cycle_power_dyadic_neighbour_pair_count (k + 1) k (cycle_power_dyadic_b_lift k b) +        (b (3 * 2 ^ k - 1)).toNat + (b (2 ^ k)).toNat := by  let q := 2 ^ k  have hq : 0 < q := Nat.two_pow_pos k  have hH : 2 ^ (k + 1) = 2 * q := by dsimp [q]; rw [pow_succ]; omega  have hD : 2 ^ (k + 2) = 4 * q := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega  have hr0 : b 0 = true := hroot.1  have hr1 : b (4 * q - 1) = true := by simpa only [hD] using hroot.2  have hsplit (f : ℕ → ℕ) :      (range (q + 1)).sum f = f 0 + (range (q - 1)).sum (fun a => f (a+1)) + f q := by    have hqr : q + 1 = (q - 1 + 1) + 1 := by omega    rw [hqr, sum_range_succ, sum_range_succ']    rw [show q-1+1=q by omega]    omega  have hb : ∀ a < q - 1,      (cycle_power_dyadic_b_lift k b (a+1) &&        cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat =      (b (a+1) && b (a+1+4*q-q-1)).toNat := by    intro a ha    dsimp [cycle_power_dyadic_b_lift]    rw [if_pos (by dsimp [q] at *; omega), if_neg (by dsimp [q] at *; omega)]    congr 2; congr 1; omega  unfold cycle_power_dyadic_neighbour_pair_count  rw [show 2^k=q from rfl, hD, hH, hsplit, hsplit]  have hmid : (range (q-1)).sum (fun a =>      (cycle_power_dyadic_b_lift k b (a+1) &&        cycle_power_dyadic_b_lift k b (a+1+2*q-q-1)).toNat) =      (range (q-1)).sum (fun a => (b (a+1) && b (a+1+4*q-q-1)).toNat) :=    sum_congr rfl (fun a ha => hb a (mem_range.mp ha))  rw [hmid]  have hz : cycle_power_dyadic_b_lift k b 0 = b 0 := by    dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hq]  have hqlo : cycle_power_dyadic_b_lift k b q = b (3*q) := by    dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)]    congr 1; omega  have hleft : cycle_power_dyadic_b_lift k b (0 + 2*q-q-1) = b (q-1) := by    dsimp [cycle_power_dyadic_b_lift]; rw [if_pos (by omega)]    congr 1; omega  have hright : cycle_power_dyadic_b_lift k b (q + 2*q-q-1) = b (4*q-1) := by    dsimp [cycle_power_dyadic_b_lift]; rw [if_neg (by omega)]    congr 1; omega  rw [hz, hqlo, hleft, hright, hr0, hr1]  have he0 : 0 + 4*q-q-1=3*q-1 := by omega  have he1 : q+4*q-q-1=4*q-1 := by omega  rw [he0, he1, hr1]  simp only [Bool.true_and, Bool.and_true]  omega
See it in the graphDiscuss this resultChallenge it