cycle_power_dyadic_tight_class_prune
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
- 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 12
- cycle_power_dyadic_no_island_cornerConditional uniform strong corner law for every cut of every dyadic radius in a tight two-interval full-cover model with exact dyadic…
- cycle_power_dyadic_no_island_of_middle_full_pruneIn a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no…
- cycle_power_dyadic_half_monotone_of_full_class_coverA tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately…
- cycle_power_dyadic_outer_quarter_monotone_of_sixteen_block_coreConditional on upper-vertical exclusion only at dyadic block sizes h=2^j, every tight all-rank-exact fully ordinarily covered dyadic model…
- 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…
- cycle_power_dyadic_outer_eighth_owner_orderIn a tight exact fully ordinarily covered dyadic model of radius2^(k+3), monotone outer eighths imply that roots owning consecutive edges…
- cycle_power_dyadic_outer_eighth_cornerIn a tight exact fully ordinarily covered dyadic model of radius2^(k+3), suppose all outer eighths are monotone. For every root p and…
- 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_outer_quarter_monotone_of_eight_block_extensionAssuming the local eight-block extension predicate at every positive block size, every tight exact fully ordinarily covered dyadic model…
- cycle_power_dyadic_no_island_rank_owner_orderUnder no-island class shape, tightness, exact dyadic edges and full ordinary coverage, the unique owner roots of consecutive edges are…
- cycle_power_dyadic_outer_projection_modelEvery valid direct outer projection preserves tight dyadic weight, exact dyadic edges and full ordinary coverage. No scalar active-count…
- 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…
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.
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.
uses
cycle_power_dyadic_class_weight_succ,cycle_power_dyadic_class_weight_le_aux,cycle_power_dyadic_sum_lift_and_cross_lehave 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
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.
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
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_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