AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_neighbour_pair_count_top_bound

theoremverified

The largest neighbour pair count of a tight rooted class is controlled by its middle-quarter leaves and the two central bits.

Statement

theorem cycle_power_dyadic_neighbour_pair_count_top_bound
    (k : ℕ) (b : ℕ → Bool)
    (hroot : b 0 = true ∧ b (2 ^ (k + 2) - 1) = true)
    (htight : cycle_power_dyadic_class_weight (k + 2) b =
      (range (2 ^ (k + 2))).sum (fun a => (b a).toNat)) :
    2 * cycle_power_dyadic_neighbour_pair_count (k + 2) (k + 1) b +
        (b (3 * 2 ^ k - 1)).toNat + (b (2 ^ k)).toNat ≤
      2 * cycle_power_dyadic_pair_count (k + 2) (k + 1) b +
        2 * ((b (2 ^ (k + 1) - 1)).toNat + (b (2 ^ (k + 1))).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 5
Used by 1

The proof, explained

The proof decomposes both the neighbour pair count and the pair count at scale k+1 into blocks over quarter-intervals of size q = 2^k. Using the middle-parent implications given by tightness, every conjunction in the pair count reduces to a single bit, while the root conditions determine the boundary terms. Each term of the neighbour pair count is then bounded by the corresponding single-bit term of the pair count using elementary boolean inequalities (x ∧ y ≤ x, x ∧ y ≤ y, and 2(x ∧ y) ≤ x + y). Linear arithmetic over the resulting algebraic decompositions establishes the required upper bound.

  1. Let q = 2^k, so that 2^(k+1) = 2q and 2^(k+2) = 4q, with boundary conditions b 0 = true and b (4q - 1) = true.

    We introduce the quarter-interval size q = 2^k, which is strictly positive by Nat.two_pow_pos. Using pow_succ, the dyadic periods are expressed as 2q and 4q. Under these abbreviations, the boundary hypothesis hroot provides b 0 = true and b (4q - 1) = true.

    lines 12–17

    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. Tightness provides parent implications on the middle quarters, and summation helpers isolate the first or last term of a sum of length q.

    By cycle_power_dyadic_tight_class_middle_parent, the tightness assumption implies that an active bit at index a ∈ [q, 2q) forces b (a + 2q) = true, and an active bit at a ∈ [2q, 3q) forces b (a - 2q) = true. Furthermore, using sum_range_succ' and sum_range_succ, we establish two splitting formulas (hsfirst and hslast) that separate the first term f 0 or the last term f (q - 1) from a sum of length q.

    lines 18–25

    uses cycle_power_dyadic_tight_class_middle_parent, sum_range_succ', sum_range_succ

      have hp := cycle_power_dyadic_tight_class_middle_parent k b htight
      have hsfirst (f : ℕ → ℕ) : (range q).sum f =
          f 0 + (range (q-1)).sum (fun a => f (a+1)) := by
        rw [show range q = range ((q-1)+1) by congr 1; omega, sum_range_succ']
        omega
      have hslast (f : ℕ → ℕ) : (range q).sum f =
          (range (q-1)).sum f + f (q-1) := by
        rw [show range q = range ((q-1)+1) by congr 1; omega, sum_range_succ]
  3. For every a < q, the pair conjunctions simplify to single bits: b a && b (a + 2q) = b (a + 2q) and b (q + a) && b (q + a + 2q) = b (q + a).

    When a < q, the index a + 2q falls in the third quarter [2q, 3q), so tightness implies b (a + 2q) = true → b a = true (using Nat.add_sub_cancel_right). Hence b a && b (a + 2q) simplifies to b (a + 2q). Similarly, q + a is in the second quarter [q, 2q), so b (q + a) = true → b (q + a + 2q) = true, reducing that conjunction to b (q + a). Both equalities are verified by case analysis on the boolean values.

    lines 26–36

    uses Nat.add_sub_cancel_right

      have hNL (a : ℕ) (ha : a < q) :
          (b a && b (a + 2 * q)).toNat = (b (a + 2 * q)).toNat := by
        have hh : b (a+2*q) = true → b a = true := by
          have hh := hp.2 (a+2*q) (by omega) (by omega)
          simpa only [hH, Nat.add_sub_cancel_right] using hh
        cases hba : b a <;> cases hbb : b (a+2*q) <;> simp_all
      have hNR (a : ℕ) (ha : a < q) :
          (b (q+a) && b (q+a+2*q)).toNat = (b (q+a)).toNat := by
        have hh : b (q+a) = true → b (q+a+2*q) = true := by
          simpa only [hH] using hp.1 (q+a) (by omega) (by omega)
        cases hba : b (q+a) <;> cases hbb : b (q+a+2*q) <;> simp_all
  4. The pair count at scale k+1 decomposes as the sum of two interior (q-1)-sums and the two central bits b (3q - 1) and b q.

    Unfolding cycle_power_dyadic_pair_count, the sum over 2q elements splits via sum_range_add into two sums of length q. By hNL and hNR, the conjunctions simplify to single bits. Applying hslast to the first block isolates b (3q - 1), and hsfirst to the second block isolates b q, leaving two sums of length q - 1: one over b (a + 2q) and one over b (q + a + 1).

    lines 37–61

    uses sum_range_add, sum_congr, Nat.add_zero

      have hN : cycle_power_dyadic_pair_count (k+2) (k+1) b =
          (range (q-1)).sum (fun a => (b (a+2*q)).toNat) +
            (b (3*q-1)).toNat + (b q).toNat +
            (range (q-1)).sum (fun a => (b (q+a+1)).toNat) := by
        unfold cycle_power_dyadic_pair_count
        rw [hH, hD, show range (2*q)=range (q+q) by congr 1; omega, sum_range_add]
        have hl : (range q).sum (fun a => (b a && b (a+4*q-2*q)).toNat) =
            (range q).sum (fun a => (b (a+2*q)).toNat) := by
          apply sum_congr rfl
          intro a ha
          have he : a+4*q-2*q=a+2*q := by omega
          rw [he]; exact hNL a (mem_range.mp ha)
        have hr : (range q).sum (fun a => (b (q+a) && b (q+a+4*q-2*q)).toNat) =
            (range q).sum (fun a => (b (q+a)).toNat) := by
          apply sum_congr rfl
          intro a ha
          have he : q+a+4*q-2*q=q+a+2*q := by omega
          rw [he]; exact hNR a (mem_range.mp ha)
        rw [hl, hr]
        rw [hslast, hsfirst]
        have he : q-1+2*q=3*q-1 := by omega
        simp only [he, Nat.add_zero]
        have heq : (fun a => (b (q+(a+1))).toNat) = (fun a => (b (q+a+1)).toNat) := by
          funext a; congr 2 <;> omega
        rw [heq]; omega
  5. The interior conjunction sums in the neighbour pair count are bounded above by the corresponding single-bit sums in the pair count.

    By cycle_power_dyadic_bool_and_toNat_le_right and cycle_power_dyadic_bool_and_toNat_le_left, each conjunction term (x && y).toNat is bounded by y.toNat on the left and by x.toNat on the right. Summing these termwise bounds with sum_le_sum shows that the inner sums of neighbour pairs are bounded above by the single-bit sums appearing in the pair count.

    lines 62–69

    uses sum_le_sum, cycle_power_dyadic_bool_and_toNat_le_right, cycle_power_dyadic_bool_and_toNat_le_left

      have hML : (range (q-1)).sum
          (fun a => (b (a+1) && b (a+2*q)).toNat) ≤
            (range (q-1)).sum (fun a => (b (a+2*q)).toNat) := by
        exact sum_le_sum (fun a _ => cycle_power_dyadic_bool_and_toNat_le_right _ _)
      have hMR : (range (q-1)).sum
          (fun a => (b (q+a+1) && b (3*q+a)).toNat) ≤
            (range (q-1)).sum (fun a => (b (q+a+1)).toNat) := by
        exact sum_le_sum (fun a _ => cycle_power_dyadic_bool_and_toNat_le_left _ _)
  6. The neighbour pair count decomposes into the boundary bits b (2q - 1) and b (2q), two interior sums of conjunctions, and the cross-term conjunction b q && b (3q - 1).

    Unfolding cycle_power_dyadic_neighbour_pair_count, the sum over 2q + 1 terms has its final term (a = 2q) peeled off via sum_range_succ; since b (4q - 1) = true, this term simplifies to b (2q) by Bool.and_true. The remaining 2q terms split into two blocks of length q via sum_range_add. Applying hsfirst to each block isolates the leading terms: the first block yields b (2q - 1) because b 0 = true (via Bool.true_and), while the second block yields b q && b (3q - 1).

    lines 70–104

    uses sum_range_succ, Bool.and_true, sum_range_add, Nat.zero_add, Bool.true_and, sum_congr, Nat.add_zero

      have hM : cycle_power_dyadic_neighbour_pair_count (k+2) (k+1) b =
          (b (2*q-1)).toNat +
            (range (q-1)).sum (fun a => (b (a+1) && b (a+2*q)).toNat) +
            (b q && b (3*q-1)).toNat +
            (range (q-1)).sum (fun a => (b (q+a+1) && b (3*q+a)).toNat) +
            (b (2*q)).toNat := by
        unfold cycle_power_dyadic_neighbour_pair_count
        rw [hH, hD, sum_range_succ]
        have hlast : 2*q+4*q-2*q-1=4*q-1 := by omega
        rw [hlast, hr1, Bool.and_true]
        rw [show range (2*q)=range (q+q) by congr 1; omega, sum_range_add]
        have hl : (range q).sum (fun a => (b a && b (a+4*q-2*q-1)).toNat) =
            (b (2*q-1)).toNat +
              (range (q-1)).sum (fun a => (b (a+1) && b (a+2*q)).toNat) := by
          rw [hsfirst]
          simp only [Nat.zero_add, hr0, Bool.true_and]
          have he : 4*q-2*q-1=2*q-1 := by omega
          rw [he]
          congr 1
          apply sum_congr rfl
          intro a ha
          congr 2; congr 1; omega
        have hr : (range q).sum (fun a => (b (q+a) && b (q+a+4*q-2*q-1)).toNat) =
            (b q && b (3*q-1)).toNat +
              (range (q-1)).sum (fun a => (b (q+a+1) && b (3*q+a)).toNat) := by
          rw [hsfirst]
          simp only [Nat.add_zero]
          have he : q+4*q-2*q-1=3*q-1 := by omega
          rw [he]
          congr 1
          apply sum_congr rfl
          intro a ha
          congr 2 <;> congr 1 <;> omega
        rw [hl, hr]
        omega
  7. Twice the neighbour pair count plus b (3q - 1) and b q is bounded by twice the pair count plus twice the central bits b (2q - 1) and b (2q). automation

    For any booleans a and c, case analysis confirms 2 * (a && c).toNat ≤ a.toNat + c.toNat. Applied to b q and b (3q - 1), this bounds twice their conjunction by their sum. Combining this with the exact decompositions of both counts and the termwise bounds hML and hMR, linear arithmetic over ℕ (handled by omega) closes the goal.

    lines 105–111

      have hbits (a c : Bool) : 2 * (a && c).toNat ≤ a.toNat+c.toNat := by
        cases a <;> cases c <;> decide
      have hb := hbits (b q) (b (3*q-1))
      rw [hH]
      change 2 * cycle_power_dyadic_neighbour_pair_count (k+2) (k+1) b +
          (b (3*q-1)).toNat + (b q).toNat ≤ _
      omega
Nat.two_pow_pos
For any natural number w, 2^w is strictly positive.
pow_succ
The successor power rule in a monoid: a^(n + 1) = a^n * a.
cycle_power_dyadic_tight_class_middle_parent
In a tight rooted dyadic class, active bits in the second quarter imply active bits in the fourth quarter, and active bits in the third quarter imply active bits in the first quarter.
sum_range_succ'
Splitting the first term from a sum over a range: the sum over n + 1 equals the first term plus the shifted sum over n.
sum_range_succ
Splitting the last term from a sum over a range: the sum over n + 1 equals the sum over n plus the (n+1)-th term.
Nat.add_sub_cancel_right
Adding and then subtracting the same natural number is the identity: (n + m) - m = n.
sum_range_add
Splitting a sum over a range of length n + m into a sum over n plus a shifted sum over m.
sum_congr
Two sums are equal if their index ranges are equal and their summands agree on every element of the range.
Nat.add_zero
Adding zero to a natural number on the right leaves it unchanged: n + 0 = n.
sum_le_sum
A sum of termwise smaller quantities is less than or equal to the sum of the larger quantities.
cycle_power_dyadic_bool_and_toNat_le_right
The integer value of a boolean conjunction (x && y) is at most the integer value of y.
cycle_power_dyadic_bool_and_toNat_le_left
The integer value of a boolean conjunction (x && y) is at most the integer value of x.
Bool.and_true
Conjunction with true on the right is the identity: (x && true) = x.
Nat.zero_add
Adding zero on the left leaves a natural number unchanged: 0 + n = n.
Bool.true_and
Conjunction with true on the left is the identity: (true && x) = x.

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_top_bound    (k : ℕ) (b : ℕ → Bool)    (hroot : b 0 = true ∧ b (2 ^ (k + 2) - 1) = true)    (htight : cycle_power_dyadic_class_weight (k + 2) b =      (range (2 ^ (k + 2))).sum (fun a => (b a).toNat)) :    2 * cycle_power_dyadic_neighbour_pair_count (k + 2) (k + 1) b +        (b (3 * 2 ^ k - 1)).toNat + (b (2 ^ k)).toNat ≤      2 * cycle_power_dyadic_pair_count (k + 2) (k + 1) b +        2 * ((b (2 ^ (k + 1) - 1)).toNat + (b (2 ^ (k + 1))).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 hp := cycle_power_dyadic_tight_class_middle_parent k b htight  have hsfirst (f : ℕ → ℕ) : (range q).sum f =      f 0 + (range (q-1)).sum (fun a => f (a+1)) := by    rw [show range q = range ((q-1)+1) by congr 1; omega, sum_range_succ']    omega  have hslast (f : ℕ → ℕ) : (range q).sum f =      (range (q-1)).sum f + f (q-1) := by    rw [show range q = range ((q-1)+1) by congr 1; omega, sum_range_succ]  have hNL (a : ℕ) (ha : a < q) :      (b a && b (a + 2 * q)).toNat = (b (a + 2 * q)).toNat := by    have hh : b (a+2*q) = true → b a = true := by      have hh := hp.2 (a+2*q) (by omega) (by omega)      simpa only [hH, Nat.add_sub_cancel_right] using hh    cases hba : b a <;> cases hbb : b (a+2*q) <;> simp_all  have hNR (a : ℕ) (ha : a < q) :      (b (q+a) && b (q+a+2*q)).toNat = (b (q+a)).toNat := by    have hh : b (q+a) = true → b (q+a+2*q) = true := by      simpa only [hH] using hp.1 (q+a) (by omega) (by omega)    cases hba : b (q+a) <;> cases hbb : b (q+a+2*q) <;> simp_all  have hN : cycle_power_dyadic_pair_count (k+2) (k+1) b =      (range (q-1)).sum (fun a => (b (a+2*q)).toNat) +        (b (3*q-1)).toNat + (b q).toNat +        (range (q-1)).sum (fun a => (b (q+a+1)).toNat) := by    unfold cycle_power_dyadic_pair_count    rw [hH, hD, show range (2*q)=range (q+q) by congr 1; omega, sum_range_add]    have hl : (range q).sum (fun a => (b a && b (a+4*q-2*q)).toNat) =        (range q).sum (fun a => (b (a+2*q)).toNat) := by      apply sum_congr rfl      intro a ha      have he : a+4*q-2*q=a+2*q := by omega      rw [he]; exact hNL a (mem_range.mp ha)    have hr : (range q).sum (fun a => (b (q+a) && b (q+a+4*q-2*q)).toNat) =        (range q).sum (fun a => (b (q+a)).toNat) := by      apply sum_congr rfl      intro a ha      have he : q+a+4*q-2*q=q+a+2*q := by omega      rw [he]; exact hNR a (mem_range.mp ha)    rw [hl, hr]    rw [hslast, hsfirst]    have he : q-1+2*q=3*q-1 := by omega    simp only [he, Nat.add_zero]    have heq : (fun a => (b (q+(a+1))).toNat) = (fun a => (b (q+a+1)).toNat) := by      funext a; congr 2 <;> omega    rw [heq]; omega  have hML : (range (q-1)).sum      (fun a => (b (a+1) && b (a+2*q)).toNat) ≤        (range (q-1)).sum (fun a => (b (a+2*q)).toNat) := by    exact sum_le_sum (fun a _ => cycle_power_dyadic_bool_and_toNat_le_right _ _)  have hMR : (range (q-1)).sum      (fun a => (b (q+a+1) && b (3*q+a)).toNat) ≤        (range (q-1)).sum (fun a => (b (q+a+1)).toNat) := by    exact sum_le_sum (fun a _ => cycle_power_dyadic_bool_and_toNat_le_left _ _)  have hM : cycle_power_dyadic_neighbour_pair_count (k+2) (k+1) b =      (b (2*q-1)).toNat +        (range (q-1)).sum (fun a => (b (a+1) && b (a+2*q)).toNat) +        (b q && b (3*q-1)).toNat +        (range (q-1)).sum (fun a => (b (q+a+1) && b (3*q+a)).toNat) +        (b (2*q)).toNat := by    unfold cycle_power_dyadic_neighbour_pair_count    rw [hH, hD, sum_range_succ]    have hlast : 2*q+4*q-2*q-1=4*q-1 := by omega    rw [hlast, hr1, Bool.and_true]    rw [show range (2*q)=range (q+q) by congr 1; omega, sum_range_add]    have hl : (range q).sum (fun a => (b a && b (a+4*q-2*q-1)).toNat) =        (b (2*q-1)).toNat +          (range (q-1)).sum (fun a => (b (a+1) && b (a+2*q)).toNat) := by      rw [hsfirst]      simp only [Nat.zero_add, hr0, Bool.true_and]      have he : 4*q-2*q-1=2*q-1 := by omega      rw [he]      congr 1      apply sum_congr rfl      intro a ha      congr 2; congr 1; omega    have hr : (range q).sum (fun a => (b (q+a) && b (q+a+4*q-2*q-1)).toNat) =        (b q && b (3*q-1)).toNat +          (range (q-1)).sum (fun a => (b (q+a+1) && b (3*q+a)).toNat) := by      rw [hsfirst]      simp only [Nat.add_zero]      have he : q+4*q-2*q-1=3*q-1 := by omega      rw [he]      congr 1      apply sum_congr rfl      intro a ha      congr 2 <;> congr 1 <;> omega    rw [hl, hr]    omega  have hbits (a c : Bool) : 2 * (a && c).toNat ≤ a.toNat+c.toNat := by    cases a <;> cases c <;> decide  have hb := hbits (b q) (b (3*q-1))  rw [hH]  change 2 * cycle_power_dyadic_neighbour_pair_count (k+2) (k+1) b +      (b (3*q-1)).toNat + (b q).toNat ≤ _  omega
See it in the graphDiscuss this resultChallenge it