AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_tight_class_middle_parent

theoremverified

Equality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent selected.

Statement

theorem cycle_power_dyadic_tight_class_middle_parent
    (k : ℕ) (b : ℕ → Bool)
    (htight : cycle_power_dyadic_class_weight (k + 2) b =
      (range (2 ^ (k + 2))).sum (fun i => (b i).toNat)) :
    (∀ a, 2 ^ k ≤ a → a < 2 ^ (k + 1) →
      b a = true → b (a + 2 ^ (k + 1)) = true) ∧
    (∀ a, 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k →
      b a = true → b (a - 2 ^ (k + 1)) = true)
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635, Section 3. These conditional class-system and pruning lemmas do not establish the unresolved graph covering bound. The earlier fixed-radius helpers handle radii eight and sixteen; this session works with arbitrary dyadic radii. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 9

The proof, explained

With L = 2^k, the domain of length 4L splits into four quarters of size L. By pruning tightness down one dimension and applying the dyadic class weight recurrence, the total weight identity forces the sum of all cross-terms b(i) ∧ b(i + 2L) to equal the sum of b over the two middle quarters [L, 2L) and [2L, 3L). Because each cross term is bounded above by the corresponding middle-quarter term, this sum equality forces pointwise equality everywhere. Consequently, if b is true at any middle-quarter index, its matched parent in the corresponding outer quarter must also be true.

  1. Express the intermediate scale 2^(k+1) and full scale 2^(k+2) in terms of the quarter-block length L = 2^k.

    Defining L = 2^k, arithmetic of powers of two shows 2^(k+1) = 2L = L + L and 2^(k+2) = 4L.

    lines 11–13

    uses pow_succ, pow_add

      let L := 2 ^ k
      have hH : 2 ^ (k + 1) = L + L := by dsimp [L]; rw [pow_succ]; omega
      have hD : 2 ^ (k + 2) = 4 * L := by dsimp [L]; rw [pow_add]; norm_num; omega
  2. The sum of the lifted bit-vector over [0, 2L) equals the sum of b over the first quarter [0, L) plus the fourth quarter [3L, 4L).

    Decomposing the range 2L into two blocks of length L via sum_range_add, the lifted bit-vector cycle_power_dyadic_b_lift evaluates to b(i) on the first block i < L (since i < 2^k), and evaluates to b((L + i) + 2L) = b(3L + i) on the second block L + i (since L + i ≥ 2^k).

    lines 14–29

    uses sum_range_add, sum_congr, if_pos, if_neg

      have hlift :
          (range (2 ^ (k + 1))).sum (fun i => (cycle_power_dyadic_b_lift k b i).toNat) =
          (range L).sum (fun i => (b i).toNat) +
          (range L).sum (fun i => (b (3 * L + i)).toNat) := by
        rw [hH, sum_range_add]
        congr 1
        · apply sum_congr rfl
          intro i hi
          dsimp [cycle_power_dyadic_b_lift]
          rw [if_pos (show i < 2 ^ k from mem_range.mp hi)]
        · apply sum_congr rfl
          intro i hi
          dsimp [cycle_power_dyadic_b_lift]
          rw [if_neg (show ¬L + i < 2 ^ k by dsimp [L]; omega)]
          have he : L + i + 2 ^ (k + 1) = 3 * L + i := by omega
          rw [he]
  3. The sum of the cross terms b(i) ∧ b(i + 2L) over i < 2L splits into the sum over the first quarter and the sum over the second quarter.

    Splitting the range 2L into [0, L) and [L, 2L) using sum_range_add, the terms on the second block become b(L + i) ∧ b(L + i + 2L) = b(L + i) ∧ b(3L + i).

    lines 30–39

    uses sum_range_add, sum_congr

      have hcross :
          (range (2 ^ (k + 1))).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) =
          (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) +
          (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) := by
        rw [hH, sum_range_add]
        congr 1
        apply sum_congr rfl
        intro i hi
        have he : L + i + (L + L) = 3 * L + i := by omega
        rw [he]
  4. The sum of b over the full domain [0, 4L) decomposes into the sum over the four quarter blocks of length L.

    Rewriting 2^(k+2) as 4L and invoking cycle_power_dyadic_sum_range_four_blocks splits the sum over range (4 * L) into the four consecutive blocks starting at 0, L, 2L, and 3L.

    lines 40–47

    uses cycle_power_dyadic_sum_range_four_blocks

      have hfull :
          (range (2 ^ (k + 2))).sum (fun i => (b i).toNat) =
          (range L).sum (fun i => (b i).toNat) +
          (range L).sum (fun i => (b (L + i)).toNat) +
          (range L).sum (fun i => (b (2 * L + i)).toNat) +
          (range L).sum (fun i => (b (3 * L + i)).toNat) := by
        rw [hD]
        exact cycle_power_dyadic_sum_range_four_blocks L (fun i => (b i).toNat)
  5. The sum of the two cross-term blocks equals the sum of b over the two middle quarters [L, 2L) and [2L, 3L).

    Tightness at scale k + 2 transfers to tightness of the lift at scale k + 1 by cycle_power_dyadic_tight_class_prune, and the weight recurrence cycle_power_dyadic_class_weight_succ equates the total weight to the lifted weight plus the cross-term sum. Subtracting the lifted sum (quarters 0 and 3) from the full sum (quarters 0, 1, 2, 3) leaves the cross terms equal to the sum of quarters 1 and 2.

    lines 48–54

    uses cycle_power_dyadic_tight_class_prune, cycle_power_dyadic_class_weight_succ

      have hsmall := cycle_power_dyadic_tight_class_prune k b htight
      have hsplit := cycle_power_dyadic_class_weight_succ k b
      have hsum :
          (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) +
          (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) =
          (range L).sum (fun i => (b (2 * L + i)).toNat) +
          (range L).sum (fun i => (b (L + i)).toNat) := by omega
  6. Each cross-term block sum is bounded above by the corresponding middle-quarter block sum.

    Pointwise, (b(i) ∧ b(2L + i)) ≤ b(2L + i) and (b(L + i) ∧ b(3L + i)) ≤ b(L + i) by the basic bounds on boolean conjunction. Summing over range L via sum_le_sum bounds each cross-term block sum by its respective middle-quarter block sum.

    lines 55–66

    uses cycle_power_dyadic_bool_and_toNat_le_right, cycle_power_dyadic_bool_and_toNat_le_left, sum_le_sum

      have hle0 : ∀ i ∈ range L,
          (b i && b (i + 2 ^ (k + 1))).toNat ≤ (b (2 * L + i)).toNat := by
        intro i hi
        have he : i + 2 ^ (k + 1) = 2 * L + i := by omega
        rw [he]
        exact cycle_power_dyadic_bool_and_toNat_le_right _ _
      have hle1 : ∀ i ∈ range L,
          (b (L + i) && b (3 * L + i)).toNat ≤ (b (L + i)).toNat := by
        intro i hi
        exact cycle_power_dyadic_bool_and_toNat_le_left _ _
      have hs0 := sum_le_sum hle0
      have hs1 := sum_le_sum hle1
  7. Both block-level inequalities are equalities, which implies pointwise equality for every index i < L.

    Since the sum of the two cross-term blocks equals the sum of the two middle-quarter blocks, neither individual inequality can be strict; both block sums must equal their upper bounds. By sum_eq_sum_iff_of_le, equality of sums with pointwise inequalities forces pointwise equality: (b(i) ∧ b(2L + i)) = b(2L + i) and (b(L + i) ∧ b(3L + i)) = b(L + i) for every i < L.

    lines 67–74

    uses sum_eq_sum_iff_of_le

      have he0 :
          (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) =
          (range L).sum (fun i => (b (2 * L + i)).toNat) := by omega
      have he1 :
          (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) =
          (range L).sum (fun i => (b (L + i)).toNat) := by omega
      have heq0 := (sum_eq_sum_iff_of_le hle0).mp he0
      have heq1 := (sum_eq_sum_iff_of_le hle1).mp he1
  8. For boolean values, if a conjunction equals one of its operands and that operand is true, the other operand must also be true.

    Two truth-table facts are recorded: if (a ∧ b) = b and b = true, then a = true; and if (a ∧ b) = a and a = true, then b = true. Both are verified by finite case checking.

    lines 75–76

      have hbool0 : ∀ a b : Bool, (a && b).toNat = b.toNat → b = true → a = true := by decide
      have hbool1 : ∀ a b : Bool, (a && b).toNat = a.toNat → a = true → b = true := by decide
  9. Any selected position in the second quarter [L, 2L) forces its matched parent in the fourth quarter [3L, 4L) to be selected.

    Given a ∈ [L, 2L) with b(a) = true, set i = a - L < L. The pointwise equality on the second block gives b(a) ∧ b(a + 2L) = b(a). Since b(a) = true, the boolean implication forces b(a + 2L) = true.

    lines 77–84

      constructor
      · intro a ha0 ha1 hab
        have hi : a - L < L := by omega
        have he := heq1 (a - L) (mem_range.mpr hi)
        have hei : L + (a - L) = a := by omega
        have hep : 3 * L + (a - L) = a + 2 ^ (k + 1) := by omega
        rw [hei, hep] at he
        exact hbool1 _ _ he hab
  10. Any selected position in the third quarter [2L, 3L) forces its matched parent in the first quarter [0, L) to be selected.

    Given a ∈ [2L, 3L) with b(a) = true, set i = a - 2L < L. The pointwise equality on the first block gives b(a - 2L) ∧ b(a) = b(a). Since b(a) = true, the boolean implication forces b(a - 2L) = true.

    lines 85–91

      · intro a ha0 ha1 hab
        have hi : a - 2 ^ (k + 1) < L := by omega
        have he := heq0 (a - 2 ^ (k + 1)) (mem_range.mpr hi)
        have hei : a - 2 ^ (k + 1) + 2 ^ (k + 1) = a := by omega
        have hep : 2 * L + (a - 2 ^ (k + 1)) = a := by omega
        rw [hei, hep] at he
        exact hbool0 _ _ he hab
pow_succ
For any element a of a monoid, a^(n + 1) = a^n * a.
pow_add
For any element a of a monoid, a^(m + n) = a^m * a^n.
sum_range_add
The sum of a function over Finset.range (n + m) splits into the sum over Finset.range n plus the sum of the shifted function over Finset.range m.
sum_congr
Two finite sums over equal index sets are equal if their terms agree at every index in the set.
if_pos
An if-then-else expression evaluates to its then branch when the condition is true.
if_neg
An if-then-else expression evaluates to its else branch when the condition is false.
cycle_power_dyadic_sum_range_four_blocks
A sum over Finset.range (4 * L) decomposes into the sum of four consecutive blocks of length L.
cycle_power_dyadic_tight_class_prune
Tightness of the dyadic class weight bound at scale k + 2 implies tightness for the lifted bit-vector at scale k + 1.
cycle_power_dyadic_class_weight_succ
The dyadic class weight at scale k + 2 equals the weight of its lift at scale k + 1 plus the sum of cross-term conjunctions b(i) ∧ b(i + 2^(k+1)) over i < 2^(k+1).
cycle_power_dyadic_bool_and_toNat_le_right
The natural number value of a boolean conjunction x ∧ y is at most the natural number value of y.
cycle_power_dyadic_bool_and_toNat_le_left
The natural number value of a boolean conjunction x ∧ y is at most the natural number value of x.
sum_le_sum
If f(i) ≤ g(i) pointwise for all i in a finite set s, then the sum of f over s is at most the sum of g over s.
sum_eq_sum_iff_of_le
Given f(i) ≤ g(i) pointwise for all i in a finite set s, the sum of f over s equals the sum of g over s if and only if f(i) = g(i) holds pointwise for all i ∈ s.

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_tight_class_middle_parent    (k : ℕ) (b : ℕ → Bool)    (htight : cycle_power_dyadic_class_weight (k + 2) b =      (range (2 ^ (k + 2))).sum (fun i => (b i).toNat)) :    (∀ a, 2 ^ k ≤ a → a < 2 ^ (k + 1) →      b a = true → b (a + 2 ^ (k + 1)) = true) ∧    (∀ a, 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k →      b a = true → b (a - 2 ^ (k + 1)) = true) := by  let L := 2 ^ k  have hH : 2 ^ (k + 1) = L + L := by dsimp [L]; rw [pow_succ]; omega  have hD : 2 ^ (k + 2) = 4 * L := by dsimp [L]; rw [pow_add]; norm_num; omega  have hlift :      (range (2 ^ (k + 1))).sum (fun i => (cycle_power_dyadic_b_lift k b i).toNat) =      (range L).sum (fun i => (b i).toNat) +      (range L).sum (fun i => (b (3 * L + i)).toNat) := by    rw [hH, sum_range_add]    congr 1    · apply sum_congr rfl      intro i hi      dsimp [cycle_power_dyadic_b_lift]      rw [if_pos (show i < 2 ^ k from mem_range.mp hi)]    · apply sum_congr rfl      intro i hi      dsimp [cycle_power_dyadic_b_lift]      rw [if_neg (show ¬L + i < 2 ^ k by dsimp [L]; omega)]      have he : L + i + 2 ^ (k + 1) = 3 * L + i := by omega      rw [he]  have hcross :      (range (2 ^ (k + 1))).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) =      (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) +      (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) := by    rw [hH, sum_range_add]    congr 1    apply sum_congr rfl    intro i hi    have he : L + i + (L + L) = 3 * L + i := by omega    rw [he]  have hfull :      (range (2 ^ (k + 2))).sum (fun i => (b i).toNat) =      (range L).sum (fun i => (b i).toNat) +      (range L).sum (fun i => (b (L + i)).toNat) +      (range L).sum (fun i => (b (2 * L + i)).toNat) +      (range L).sum (fun i => (b (3 * L + i)).toNat) := by    rw [hD]    exact cycle_power_dyadic_sum_range_four_blocks L (fun i => (b i).toNat)  have hsmall := cycle_power_dyadic_tight_class_prune k b htight  have hsplit := cycle_power_dyadic_class_weight_succ k b  have hsum :      (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) +      (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) =      (range L).sum (fun i => (b (2 * L + i)).toNat) +      (range L).sum (fun i => (b (L + i)).toNat) := by omega  have hle0 : ∀ i ∈ range L,      (b i && b (i + 2 ^ (k + 1))).toNat ≤ (b (2 * L + i)).toNat := by    intro i hi    have he : i + 2 ^ (k + 1) = 2 * L + i := by omega    rw [he]    exact cycle_power_dyadic_bool_and_toNat_le_right _ _  have hle1 : ∀ i ∈ range L,      (b (L + i) && b (3 * L + i)).toNat ≤ (b (L + i)).toNat := by    intro i hi    exact cycle_power_dyadic_bool_and_toNat_le_left _ _  have hs0 := sum_le_sum hle0  have hs1 := sum_le_sum hle1  have he0 :      (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) =      (range L).sum (fun i => (b (2 * L + i)).toNat) := by omega  have he1 :      (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) =      (range L).sum (fun i => (b (L + i)).toNat) := by omega  have heq0 := (sum_eq_sum_iff_of_le hle0).mp he0  have heq1 := (sum_eq_sum_iff_of_le hle1).mp he1  have hbool0 : ∀ a b : Bool, (a && b).toNat = b.toNat → b = true → a = true := by decide  have hbool1 : ∀ a b : Bool, (a && b).toNat = a.toNat → a = true → b = true := by decide  constructor  · intro a ha0 ha1 hab    have hi : a - L < L := by omega    have he := heq1 (a - L) (mem_range.mpr hi)    have hei : L + (a - L) = a := by omega    have hep : 3 * L + (a - L) = a + 2 ^ (k + 1) := by omega    rw [hei, hep] at he    exact hbool1 _ _ he hab  · intro a ha0 ha1 hab    have hi : a - 2 ^ (k + 1) < L := by omega    have he := heq0 (a - 2 ^ (k + 1)) (mem_range.mpr hi)    have hei : a - 2 ^ (k + 1) + 2 ^ (k + 1) = a := by omega    have hep : 2 * L + (a - 2 ^ (k + 1)) = a := by omega    rw [hei, hep] at he    exact hbool0 _ _ he hab
See it in the graphDiscuss this resultChallenge it