AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_tight_class_prune

theoremverified

Deleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic weight and its cardinality.

Statement

theorem cycle_power_dyadic_tight_class_prune (k : ℕ) (b : ℕ → Bool)
    (htight : cycle_power_dyadic_class_weight (k + 2) b =
      (range (2 ^ (k + 2))).sum (fun i => (b i).toNat)) :
    cycle_power_dyadic_class_weight (k + 1) (cycle_power_dyadic_b_lift k b) =
      (range (2 ^ (k + 1))).sum (fun i => (cycle_power_dyadic_b_lift k b i).toNat)
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 2
Used by 12

The proof, explained

The proof establishes that pruning preserves tightness by sandwiching the pruned weight and cardinality between bounds that force equality. At scale k + 2, the weight of b decomposes into the weight of the pruned sequence b' at scale k + 1 plus a cross-term sum. Meanwhile, the weight of b' is bounded above by its cardinality, and the sum of that pruned cardinality and the cross terms is bounded above by the total cardinality of b. Because b is assumed tight (its weight equals its total cardinality), these inequalities leave no slack, forcing the pruned weight to equal the pruned cardinality.

  1. The original dyadic weight decomposes into the pruned weight plus the cross-term sum, the pruned weight is at most the pruned cardinality, and the pruned cardinality plus the cross-term sum is at most the original cardinality.

    Three structural relations are established relating b and its pruned version b' = cycle_power_dyadic_b_lift k b: 1. cycle_power_dyadic_class_weight_succ expresses the weight of b at scale k + 2 as the weight of b' at scale k + 1 plus the cross-term sum C = ∑ i < 2^(k+1), (b i && b (i + 2^(k+1))). 2. cycle_power_dyadic_class_weight_le_aux provides the general upper bound that the weight of b' is at most its cardinality |b'| = ∑ i < 2^(k+1), b' i. 3. cycle_power_dyadic_sum_lift_and_cross_le bounds the sum of the pruned cardinality |b'| and the cross-term sum C by the total cardinality |b| = ∑ i < 2^(k+2), b i.

    lines 8–10

    uses cycle_power_dyadic_class_weight_succ, cycle_power_dyadic_class_weight_le_aux, cycle_power_dyadic_sum_lift_and_cross_le

      have hsplit := cycle_power_dyadic_class_weight_succ k b
      have hsmall := cycle_power_dyadic_class_weight_le_aux k (cycle_power_dyadic_b_lift k b)
      have htotal := cycle_power_dyadic_sum_lift_and_cross_le k b
  2. The dyadic class weight of the pruned sequence equals its cardinality.

    By the tightness hypothesis htight, the original weight equals the total cardinality: W(b) = |b|. Combining this with the decomposition W(b) = W(b') + C and the bounds W(b') ≤ |b'| and |b'| + C ≤ |b|, we have |b| = W(b) = W(b') + C ≤ |b'| + C ≤ |b|. This sandwiches both inequalities between |b| and |b|, leaving no slack and forcing W(b') = |b'|. The linear integer arithmetic decision procedure omega closes the goal from these relations.

    line 11

      omega
cycle_power_dyadic_class_weight_succ
For any dimension parameter k and boolean sequence b, the dyadic class weight of b at scale k + 2 decomposes as the dyadic class weight of the pruned sequence (cycle_power_dyadic_b_lift k b) at scale k + 1 plus the cross-term sum ∑ i ∈ [0, 2^(k+1)), (b i && b (i + 2^(k+1))).toNat.
cycle_power_dyadic_class_weight_le_aux
For any dimension parameter k and boolean sequence b, the dyadic class weight at scale k + 1 is bounded above by the sequence's cardinality, ∑ i ∈ [0, 2^(k+1)), (b i).toNat.
cycle_power_dyadic_sum_lift_and_cross_le
For any dimension parameter k and boolean sequence b, the cardinality of the pruned sequence over [0, 2^(k+1)) plus the cross-term sum over [0, 2^(k+1)) is bounded above by the total cardinality of b over [0, 2^(k+2)).

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_prune (k : ℕ) (b : ℕ → Bool)    (htight : cycle_power_dyadic_class_weight (k + 2) b =      (range (2 ^ (k + 2))).sum (fun i => (b i).toNat)) :    cycle_power_dyadic_class_weight (k + 1) (cycle_power_dyadic_b_lift k b) =      (range (2 ^ (k + 1))).sum (fun i => (cycle_power_dyadic_b_lift k b i).toNat) := by  have hsplit := cycle_power_dyadic_class_weight_succ k b  have hsmall := cycle_power_dyadic_class_weight_le_aux k (cycle_power_dyadic_b_lift k b)  have htotal := cycle_power_dyadic_sum_lift_and_cross_le k b  omega
See it in the graphDiscuss this resultChallenge it