AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_neighbour_weight_bound

theoremverified

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
Used by 1

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.

  1. 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.

    lines 14–22

    uses sum_range_succ, sum_range_zero, add_zero, zero_add, Bool.true_and, Bool.and_true

      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
  2. 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.

    lines 23–38

    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 hbtight
  3. Neighbour 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.

    lines 39–48

    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_low

        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)]
  4. 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.

    lines 49–62

    uses sum_range_succ, congrArg

        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]
  5. 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.

    lines 63–81

    uses sum_congr, cycle_power_dyadic_pair_count_prune, if_pos, Nat.two_pow_pos, if_neg, Nat.lt_irrefl

        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
  6. 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.

    lines 82–93

    uses Nat.mul_le_mul_left, sum_range_succ

        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]
  7. 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.

    lines 108–109

    uses cycle_power_dyadic_neighbour_weight_bound_aux

      obtain ⟨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.

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 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
See it in the graphDiscuss this resultChallenge it