cycle_power_dyadic_neighbour_pair_count_top_bound
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
- cycle_power_dyadic_pair_countThe finite dyadic pair sum. For ranks j at most m, it counts selected pairs at distance 2^m minus 2^j in the dyadic arc.
- cycle_power_dyadic_neighbour_pair_countThe finite neighbour pair sum. For ranks j strictly below m, it counts selected pairs at distance 2^m minus 2^j minus one in the dyadic arc.
- cycle_power_dyadic_tight_class_middle_parentEquality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent…
- 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.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- Used by 1
- cycle_power_dyadic_neighbour_weight_boundA tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a…
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.
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.
uses
Nat.two_pow_pos,pow_succlet 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
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.
uses
cycle_power_dyadic_tight_class_middle_parent,sum_range_succ',sum_range_succhave 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]
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.
uses
Nat.add_sub_cancel_righthave 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
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).
uses
sum_range_add,sum_congr,Nat.add_zerohave 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
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.
uses
sum_le_sum,cycle_power_dyadic_bool_and_toNat_le_right,cycle_power_dyadic_bool_and_toNat_le_lefthave 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 _ _)
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).
uses
sum_range_succ,Bool.and_true,sum_range_add,Nat.zero_add,Bool.true_and,sum_congr,Nat.add_zerohave 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
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.
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.
- The final arithmetic inequality is discharged automatically by `omega` using Presburger linear arithmetic on ℕ, combining the decompositions of the two counts with the boolean bounds.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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