cycle_power_dyadic_prune_cover
Deleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than the new radius, keeping the original class start indices.
Statement
theorem cycle_power_dyadic_prune_cover (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k + 2) (x p) = (range (2 ^ (k + 2))).sum (fun i => (x p i).toNat)) (hcover : ∀ (d : ℕ), 1 ≤ d → d < 2 ^ (k + 2) → ∀ v : ℤ, ∃ a < 2 ^ (k + 2) - d, x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true) : ∀ (d : ℕ), 1 ≤ d → d < 2 ^ (k + 1) → ∀ v : ℤ, ∃ a < 2 ^ (k + 1) - d, cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a = true ∧ cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) (a + d) = 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 4
- 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.
- 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_prune_cover_of_middle_parentIf every selected middle-quarter position has its matched outer-quarter parent selected, deleting and compressing the middle quarters…
- Used by 9
- 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_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_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…
The proof, explained
The theorem reduces the preservation of distance coverage after pruning the middle two quarters of tight dyadic classes to a general pruning lemma, cycle_power_dyadic_prune_cover_of_middle_parent. The tightness hypothesis on each fiber implies, via cycle_power_dyadic_tight_class_middle_parent, that every active bit in the middle quarters has a corresponding counterpart in the outer quarters. Combining these middle-parent implications with the original coverage hypothesis immediately yields coverage for all distances below 2^(k+1).
For every shift p, the fiber x(p) satisfies the middle-parent property: active bits in the middle two quarters imply corresponding active bits in the outer quarters.
Applying cycle_power_dyadic_tight_class_middle_parent to x(p) using the tightness assumption htight p deduces that any bit set in the second quarter [2^k, 2^(k+1)) has a counterpart set in the fourth quarter at offset 2^(k+1), and any bit set in the third quarter [2^(k+1), 3 · 2^k) has a counterpart set in the first quarter at offset -2^(k+1).
uses
cycle_power_dyadic_tight_class_middle_parenthave hp := fun p => cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)
The pruned and compressed lift covers every distance d strictly less than 2^(k+1).
The lemma cycle_power_dyadic_prune_cover_of_middle_parent shows that whenever the middle-parent conditions hold on every fiber and the original configuration covers all distances up to 2^(k+2), the pruned lift cycle_power_dyadic_b_lift k preserves coverage of all distances up to 2^(k+1). Supplying the two middle-parent components from hp and the original coverage hypothesis hcover completes the proof.
uses
cycle_power_dyadic_prune_cover_of_middle_parentexact cycle_power_dyadic_prune_cover_of_middle_parent k x (fun p => (hp p).1) (fun p => (hp p).2) hcover
cycle_power_dyadic_tight_class_middle_parent- For any bit sequence whose dyadic class weight at level k + 2 equals its Hamming weight, any active bit in the second quarter [2^k, 2^(k+1)) is matched by an active bit at index a + 2^(k+1), and any active bit in the third quarter [2^(k+1), 3 · 2^k) is matched by an active bit at index a - 2^(k+1).
cycle_power_dyadic_prune_cover_of_middle_parent- If each fiber x(p) satisfies the middle-parent conditions (middle quarter bits imply outer quarter bits) and x covers all distances up to 2^(k+2), then the compressed configuration after pruning the middle two quarters covers all distances up to 2^(k+1).
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_prune_cover (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k + 2) (x p) = (range (2 ^ (k + 2))).sum (fun i => (x p i).toNat)) (hcover : ∀ (d : ℕ), 1 ≤ d → d < 2 ^ (k + 2) → ∀ v : ℤ, ∃ a < 2 ^ (k + 2) - d, x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true) : ∀ (d : ℕ), 1 ≤ d → d < 2 ^ (k + 1) → ∀ v : ℤ, ∃ a < 2 ^ (k + 1) - d, cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a = true ∧ cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) (a + d) = true := by have hp := fun p => cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p) exact cycle_power_dyadic_prune_cover_of_middle_parent k x (fun p => (hp p).1) (fun p => (hp p).2) hcover