AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_cover

theoremverified

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

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

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

    line 14

    uses cycle_power_dyadic_tight_class_middle_parent

      have hp := fun p => cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)
  2. 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.

    line 15

    uses cycle_power_dyadic_prune_cover_of_middle_parent

      exact 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

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