cycle_power_dyadic_neighbour_weight_bound
A tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a penalty supported only at the two central positions.
Statement
theorem cycle_power_dyadic_neighbour_weight_bound (m : ℕ) (hm : 2 ≤ m) (b : ℕ → Bool) (hroot : b 0 = true ∧ b (2 ^ m - 1) = true) (htight : cycle_power_dyadic_class_weight m b = (Finset.range (2 ^ m)).sum (fun a => (b a).toNat)) : let D : ℕ := 2 ^ m let N : ℕ → ℕ := fun j => (Finset.range (2 ^ j)).sum (fun a => (b a && b (a + D - 2 ^ j)).toNat) let M : ℕ → ℕ := fun j => (Finset.range (2 ^ j + 1)).sum (fun a => (b a && b (a + D - 2 ^ j - 1)).toNat) (Finset.range m).sum (fun j => if 1 ≤ j then 2 ^ j * M j else 0) ≤ N 1 + (Finset.range m).sum (fun j => if 2 ≤ j then 2 ^ j * N j else 0) + 2 ^ (m - 1) * ((b (2 ^ (m - 1) - 1)).toNat + (b (2 ^ (m - 1))).toNat)
- Source
- Proposed uniform induction lemma for OP-205 / RT-1, arXiv:2610.15635. Closed-form weights were recovered from experiments6432,6434,6435 and an explicit pruning induction is recorded. The statement remains unproved until Lean checks that induction; no advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- 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_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
- cycle_power_dyadic_tight_class_parentEquality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc…
- 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_pair_count_pruneDeleting the middle two quarters preserves each smaller dyadic pair count.
- cycle_power_dyadic_neighbour_pair_count_prune_lowDeleting the middle two quarters preserves each strictly smaller neighbour pair count.
- cycle_power_dyadic_neighbour_pair_count_prune_topAt the boundary rank of middle-quarter pruning, the neighbour pair count changes by exactly four boundary bits.
- cycle_power_dyadic_neighbour_pair_count_top_boundThe largest neighbour pair count of a tight rooted class is controlled by its middle-quarter leaves and the two central bits.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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_central_position_existsIn a periodic tight dyadic class model with exact dyadic coverage and coverage at all lower neighbour distances, some class uses one of…
The proof, explained
The theorem is proved by induction on k = m - 2 ≥ 0 in an auxiliary lemma. The base case m = 2 simplifies to an inequality over the two interior boolean values, verified by exhaustive case evaluation. In the inductive step, the configuration b on 2^(k+3) elements is pruned to bb on 2^(k+2) elements via dyadic lifting, preserving tightness and the root condition. The induction hypothesis bounds the lower-scale neighbour counts of bb, and an auxiliary bound controls the top scale; combining them algebraically cancels the intermediate boundary penalties at 2^(k+1) and 3 * 2^(k+1), leaving only the central penalty at 2^(k+2). The main theorem then follows immediately by specializing to k = m - 2.
The weighted neighbour bound holds in the base case k = 0 (corresponding to m = 2). automation
We induct on k. When k = 0, the domain size is 2^2 = 4, and the root condition fixes b 0 = true and b 3 = true. Expanding the definitions and sums over the two-element range simplifies the left-hand side to 2 * (b 1 + (b 1 && b 2) + b 2) and the right-hand side to 3 * (b 1 + b 2). Exhaustive evaluation over the four possible boolean assignments to b 1 and b 2 confirms that the inequality holds in all cases.
uses
sum_range_succ,sum_range_zero,add_zero,zero_add,Bool.true_and,Bool.and_trueinduction k generalizing b with | zero => norm_num only [Nat.reduceAdd, Nat.reducePow, Nat.reduceSub] at hroot ⊢ simp only [cycle_power_dyadic_pair_count, cycle_power_dyadic_neighbour_pair_count, sum_range_succ, sum_range_zero, Nat.reduceAdd, Nat.reducePow, Nat.reduceSub, Nat.le_refl, Nat.reduceLeDiff, ↓reduceIte, Nat.zero_le, Nat.not_succ_le_zero, add_zero, zero_add, hroot.1, hroot.2, Bool.true_and, Bool.and_true] cases b 1 <;> cases b 2 <;> decide
The pruned configuration bb satisfies the root and tightness conditions, so the induction hypothesis applies to it.
In the inductive step, with q = 2^(k+1), the domain size is 2^(k+3) = 4q. We prune b to a configuration bb on 2^(k+2) = 2q elements by dropping the central interval of length 2q. The root condition holds for bb because bb 0 = b 0 = true and bb (2q - 1) = b (4q - 1) = true. By cycle_power_dyadic_tight_class_prune, tightness transfers from b to bb. We can therefore apply the induction hypothesis to bb, obtaining the weighted neighbour bound at scale k+2.
uses
Nat.two_pow_pos,pow_succ,if_pos,if_neg,cycle_power_dyadic_tight_class_prune| succ k ih => let q := 2^(k+1) let bb := cycle_power_dyadic_b_lift (k+1) b have hq : 0 < q := Nat.two_pow_pos (k+1) have hH : 2^(k+2)=2*q := by dsimp [q]; rw [show k+2=(k+1)+1 by omega, pow_succ]; omega have hD : 2^(k+3)=4*q := by rw [show k+3=(k+2)+1 by omega, pow_succ, hH]; omega have hD' : 2^(k+1+2)=4*q := hD have hbroot : bb 0 = true ∧ bb (2^(k+2)-1) = true := by constructor · dsimp [bb, cycle_power_dyadic_b_lift]; rw [if_pos hq]; exact hroot.1 · dsimp [bb, cycle_power_dyadic_b_lift] rw [if_neg (by omega)] have he : 2^(k+2)-1+2^(k+2)=2^(k+1+2)-1 := by omega rw [he]; exact hroot.2 have hbtight := cycle_power_dyadic_tight_class_prune (k+1) b htight have hi := ih bb hbroot hbtightNeighbour pair counts are invariant under pruning for all scales j < k+1, and structural relations hold at the top scales.
Pruning leaves neighbour counts unaffected at every scale j < k+1 (cycle_power_dyadic_neighbour_pair_count_prune_low), so the partial sums over j < k+1 are identical for b and bb. We also record the top-scale relations: cycle_power_dyadic_neighbour_pair_count_prune_top relates neighbour counts across pruning at scale k+1, while cycle_power_dyadic_neighbour_pair_count_top_bound bounds the top neighbour count at scale k+2 in terms of dyadic pairs and central values.
uses
cycle_power_dyadic_neighbour_pair_count_prune_top,cycle_power_dyadic_neighbour_pair_count_top_bound,sum_congr,cycle_power_dyadic_neighbour_pair_count_prune_lowhave hrel := cycle_power_dyadic_neighbour_pair_count_prune_top (k+1) b hroot have htop := cycle_power_dyadic_neighbour_pair_count_top_bound (k+1) b hroot htight have hsmallM : (range (k+1)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+1+2) j b else 0) = (range (k+1)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+2) j bb else 0) := by apply sum_congr rfl intro j hj rw [cycle_power_dyadic_neighbour_pair_count_prune_low (k+1) j (mem_range.mp hj)]
The weighted neighbour sums up to scale k+1 for b and bb are related by boundary terms scaled by q. automation
We split the sum up to scale k+1 into the sum over j < k+1 and the boundary term at j = k+1 using sum_range_succ. Combining the equality on the lower scales with the scale-(k+1) neighbour relation multiplied by q = 2^(k+1) yields an equality relating the neighbour sums up to scale k+1 for b and bb, adjusted by boundary terms at q and 3q. Linear arithmetic closes the identity.
uses
sum_range_succ,congrArghave hsumM : (range (k+2)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+1+2) j b else 0) + q*((b (q-1)).toNat+(b (3*q)).toNat) = (range (k+2)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+2) j bb else 0) + q*((b (3*q-1)).toNat+(b q).toNat) := by have hs (f : ℕ → ℕ) : (range (k+2)).sum f = (range (k+1)).sum f + f (k+1) := sum_range_succ f (k+1) rw [hs, hsmallM, hs] simp only [show 1 ≤ k+1 by omega, ↓reduceIte] have hh := congrArg (fun v : ℕ => q*v) hrel dsimp only [q, bb] at hh ⊢ nlinarith only [hh]
Dyadic pair counts for j ≤ k+1 are invariant under pruning, and the central penalty of bb matches the boundary adjustment at scale k+1.
By cycle_power_dyadic_pair_count_prune, dyadic pair counts for all j ≤ k+1 are preserved under pruning, so the dyadic terms on the right-hand side match between b and bb. Moreover, evaluating bb at its central positions shows bb (q - 1) = b (q - 1) and bb q = b (3q), so bb's central penalty term in the induction hypothesis equals q * (b (q - 1) + b (3q)). We rewrite this identity into the induction hypothesis.
uses
sum_congr,cycle_power_dyadic_pair_count_prune,if_pos,Nat.two_pow_pos,if_neg,Nat.lt_irreflhave hsumN : (range (k+2)).sum (fun j => if 2 ≤ j then 2^j * cycle_power_dyadic_pair_count (k+1+2) j b else 0) = (range (k+2)).sum (fun j => if 2 ≤ j then 2^j * cycle_power_dyadic_pair_count (k+2) j bb else 0) := by apply sum_congr rfl intro j hj rw [cycle_power_dyadic_pair_count_prune (k+1) j (by have := mem_range.mp hj; omega)] have hN1 := cycle_power_dyadic_pair_count_prune (k+1) 1 (by omega) b have hcent : (bb (2^(k+1)-1)).toNat + (bb (2^(k+1))).toNat = (b (q-1)).toNat+(b (3*q)).toNat := by dsimp [bb, cycle_power_dyadic_b_lift] rw [if_pos (show 2^(k+1)-1 < 2^(k+1) by have := Nat.two_pow_pos (k+1); omega), if_neg (Nat.lt_irrefl (2^(k+1)))] have he : 2^(k+1)+2^(k+2)=3*q := by change q+2^(k+2)=3*q rw [hH]; omega rw [he] rw [hcent] at hi
Combining the induction hypothesis with the scaled top bound cancels intermediate boundary terms and proves the bound at level k+3. automation
We scale the top bound at scale k+2 by q and split the target sums at j = k+2 using sum_range_succ. Substituting the dyadic count equivalences leaves only the induction hypothesis on bb, the neighbour sum relation, and the scaled top bound. When these are combined, the intermediate boundary adjustments q * (b (q - 1) + b (3q)) and q * (b (3q - 1) + b q) cancel out entirely, leaving only the central penalty 2q * (b (2q - 1) + b (2q)). Nonlinear arithmetic automation verifies the cancellation and inequality.
uses
Nat.mul_le_mul_left,sum_range_succhave hscaled := Nat.mul_le_mul_left q htop have hs (f : ℕ → ℕ) : (range (k+1+2)).sum f = (range (k+2)).sum f + f (k+2) := sum_range_succ f (k+2) rw [hs, hs] simp only [show 1 ≤ k+2 by omega, show 2 ≤ k+2 by omega, ↓reduceIte] rw [hsumN, hN1] have hpow : 2^(k+1+1)=2*q := hH rw [hH] change _ ≤ _ + _ + (2*q)*((b (2*q-1)).toNat+(b (2*q)).toNat) rw [hpow] at hscaled dsimp only [bb, q] at hi hsumM hscaled ⊢ nlinarith only [hi, hsumM, hscaled]
The main theorem follows directly from the auxiliary lemma by setting k = m - 2.
Given m ≥ 2, we represent m as k + 2 with k = m - 2 in the natural numbers. Applying cycle_power_dyadic_neighbour_weight_bound_aux directly establishes the weighted neighbour bound for m.
uses
cycle_power_dyadic_neighbour_weight_bound_auxobtain ⟨k, rfl⟩ : ∃ k, m=k+2 := ⟨m-2, by omega⟩ exact cycle_power_dyadic_neighbour_weight_bound_aux k b hroot htight
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a.
zero_add- Adding zero on the left leaves an element unchanged: 0 + a = a.
Bool.true_and- Conjunction with true on the left is the identity on booleans: true && b = b.
Bool.and_true- Conjunction with true on the right is the identity on booleans: b && true = b.
sum_range_succ- The sum of a function over {0, ..., n} equals the sum over {0, ..., n-1} plus the value at n.
sum_range_zero- The sum over the empty range {0, ..., -1} is zero.
Nat.two_pow_pos- Powers of two with natural exponents are strictly positive: 0 < 2 ^ w.
pow_succ- The (n+1)-th power of an element equals its n-th power multiplied by the element: a ^ (n + 1) = a ^ n * a.
if_pos- An if-then-else expression evaluates to its then-branch when the condition holds.
if_neg- An if-then-else expression evaluates to its else-branch when the condition is false.
cycle_power_dyadic_tight_class_prune- Pruning the middle block preserves the tightness of the dyadic class weight from scale k+2 to scale k+1.
cycle_power_dyadic_neighbour_pair_count_prune_top- At scale k, the neighbour pair counts of b and its pruned configuration differ by explicit boundary terms at 2^k - 1, 2^k, 3 * 2^k - 1, and 3 * 2^k.
cycle_power_dyadic_neighbour_pair_count_top_bound- For a tight rooted class, the top-scale neighbour pair count plus intermediate boundary values is bounded by twice the dyadic pair count plus twice the central values.
sum_congr- If two finite sets are equal and two summands agree on every element, their sums are equal.
cycle_power_dyadic_neighbour_pair_count_prune_low- Pruning does not change the neighbour pair count at any scale j strictly below k.
congrArg- Applying a function to both sides of an equality preserves the equality: a₁ = a₂ implies f a₁ = f a₂.
cycle_power_dyadic_pair_count_prune- Pruning does not change the dyadic pair count at any scale j ≤ k.
Nat.lt_irrefl- No natural number is strictly less than itself: ¬n < n.
Nat.mul_le_mul_left- Multiplying both sides of an inequality by a natural factor preserves the inequality: n ≤ m implies k * n ≤ k * m.
cycle_power_dyadic_neighbour_weight_bound_aux- The weighted neighbour bound holds for any tight rooted configuration on 2^(k+2) elements, parametrized by k.
- The base case k = 0 (m = 2) is verified by exhaustive evaluation (decide) over all four boolean assignments to the interior values b 1 and b 2.
- In the inductive step, the algebraic cancellation of the boundary terms at 2^(k+1) and 3 * 2^(k+1) when combining the induction hypothesis, the scaled top bound, and the neighbour count relation is discharged by arithmetic automation (nlinarith).
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 Finsetlemma cycle_power_dyadic_neighbour_weight_bound_aux (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)) : (range (k+2)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+2) j b else 0) ≤ cycle_power_dyadic_pair_count (k+2) 1 b + (range (k+2)).sum (fun j => if 2 ≤ j then 2^j * cycle_power_dyadic_pair_count (k+2) j b else 0) + 2^(k+1) * ((b (2^(k+1)-1)).toNat + (b (2^(k+1))).toNat) := by induction k generalizing b with | zero => norm_num only [Nat.reduceAdd, Nat.reducePow, Nat.reduceSub] at hroot ⊢ simp only [cycle_power_dyadic_pair_count, cycle_power_dyadic_neighbour_pair_count, sum_range_succ, sum_range_zero, Nat.reduceAdd, Nat.reducePow, Nat.reduceSub, Nat.le_refl, Nat.reduceLeDiff, ↓reduceIte, Nat.zero_le, Nat.not_succ_le_zero, add_zero, zero_add, hroot.1, hroot.2, Bool.true_and, Bool.and_true] cases b 1 <;> cases b 2 <;> decide | succ k ih => let q := 2^(k+1) let bb := cycle_power_dyadic_b_lift (k+1) b have hq : 0 < q := Nat.two_pow_pos (k+1) have hH : 2^(k+2)=2*q := by dsimp [q]; rw [show k+2=(k+1)+1 by omega, pow_succ]; omega have hD : 2^(k+3)=4*q := by rw [show k+3=(k+2)+1 by omega, pow_succ, hH]; omega have hD' : 2^(k+1+2)=4*q := hD have hbroot : bb 0 = true ∧ bb (2^(k+2)-1) = true := by constructor · dsimp [bb, cycle_power_dyadic_b_lift]; rw [if_pos hq]; exact hroot.1 · dsimp [bb, cycle_power_dyadic_b_lift] rw [if_neg (by omega)] have he : 2^(k+2)-1+2^(k+2)=2^(k+1+2)-1 := by omega rw [he]; exact hroot.2 have hbtight := cycle_power_dyadic_tight_class_prune (k+1) b htight have hi := ih bb hbroot hbtight have hrel := cycle_power_dyadic_neighbour_pair_count_prune_top (k+1) b hroot have htop := cycle_power_dyadic_neighbour_pair_count_top_bound (k+1) b hroot htight have hsmallM : (range (k+1)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+1+2) j b else 0) = (range (k+1)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+2) j bb else 0) := by apply sum_congr rfl intro j hj rw [cycle_power_dyadic_neighbour_pair_count_prune_low (k+1) j (mem_range.mp hj)] have hsumM : (range (k+2)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+1+2) j b else 0) + q*((b (q-1)).toNat+(b (3*q)).toNat) = (range (k+2)).sum (fun j => if 1 ≤ j then 2^j * cycle_power_dyadic_neighbour_pair_count (k+2) j bb else 0) + q*((b (3*q-1)).toNat+(b q).toNat) := by have hs (f : ℕ → ℕ) : (range (k+2)).sum f = (range (k+1)).sum f + f (k+1) := sum_range_succ f (k+1) rw [hs, hsmallM, hs] simp only [show 1 ≤ k+1 by omega, ↓reduceIte] have hh := congrArg (fun v : ℕ => q*v) hrel dsimp only [q, bb] at hh ⊢ nlinarith only [hh] have hsumN : (range (k+2)).sum (fun j => if 2 ≤ j then 2^j * cycle_power_dyadic_pair_count (k+1+2) j b else 0) = (range (k+2)).sum (fun j => if 2 ≤ j then 2^j * cycle_power_dyadic_pair_count (k+2) j bb else 0) := by apply sum_congr rfl intro j hj rw [cycle_power_dyadic_pair_count_prune (k+1) j (by have := mem_range.mp hj; omega)] have hN1 := cycle_power_dyadic_pair_count_prune (k+1) 1 (by omega) b have hcent : (bb (2^(k+1)-1)).toNat + (bb (2^(k+1))).toNat = (b (q-1)).toNat+(b (3*q)).toNat := by dsimp [bb, cycle_power_dyadic_b_lift] rw [if_pos (show 2^(k+1)-1 < 2^(k+1) by have := Nat.two_pow_pos (k+1); omega), if_neg (Nat.lt_irrefl (2^(k+1)))] have he : 2^(k+1)+2^(k+2)=3*q := by change q+2^(k+2)=3*q rw [hH]; omega rw [he] rw [hcent] at hi have hscaled := Nat.mul_le_mul_left q htop have hs (f : ℕ → ℕ) : (range (k+1+2)).sum f = (range (k+2)).sum f + f (k+2) := sum_range_succ f (k+2) rw [hs, hs] simp only [show 1 ≤ k+2 by omega, show 2 ≤ k+2 by omega, ↓reduceIte] rw [hsumN, hN1] have hpow : 2^(k+1+1)=2*q := hH rw [hH] change _ ≤ _ + _ + (2*q)*((b (2*q-1)).toNat+(b (2*q)).toNat) rw [hpow] at hscaled dsimp only [bb, q] at hi hsumM hscaled ⊢ nlinarith only [hi, hsumM, hscaled]theorem cycle_power_dyadic_neighbour_weight_bound (m : ℕ) (hm : 2 ≤ m) (b : ℕ → Bool) (hroot : b 0 = true ∧ b (2 ^ m - 1) = true) (htight : cycle_power_dyadic_class_weight m b = (Finset.range (2 ^ m)).sum (fun a => (b a).toNat)) : let D : ℕ := 2 ^ m let N : ℕ → ℕ := fun j => (Finset.range (2 ^ j)).sum (fun a => (b a && b (a + D - 2 ^ j)).toNat) let M : ℕ → ℕ := fun j => (Finset.range (2 ^ j + 1)).sum (fun a => (b a && b (a + D - 2 ^ j - 1)).toNat) (Finset.range m).sum (fun j => if 1 ≤ j then 2 ^ j * M j else 0) ≤ N 1 + (Finset.range m).sum (fun j => if 2 ≤ j then 2 ^ j * N j else 0) + 2 ^ (m - 1) * ((b (2 ^ (m - 1) - 1)).toNat + (b (2 ^ (m - 1))).toNat) := by obtain ⟨k, rfl⟩ : ∃ k, m=k+2 := ⟨m-2, by omega⟩ exact cycle_power_dyadic_neighbour_weight_bound_aux k b hroot htight