AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_single_distance_cover

theoremverified

Deleting and compressing the middle quarters preserves coverage at one fixed distance d below the new radius, using only original coverage at half the old radius plus d. Tight dyadic class weight is assumed. There is no coverage assumption at any other distance and no claim of active-count preservation.

Statement

theorem cycle_power_dyadic_prune_single_distance_cover
    (k d : ℕ) (x : ℤ → ℕ → Bool) (hd : 1 ≤ d) (hdH : d < 2^(k+1))
    (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) =
      (range (2^(k+2))).sum (fun a => (x p a).toNat))
    (hcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+2)-(2^(k+1)+d) ∧
      x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+(2^(k+1)+d)) = true) :
    ∀ v : ℤ, ∃ a : ℕ, 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
Routine localized pruning bridge for OP-205 / RT-1, arXiv:2610.15635 Section 3. Experiments6709 and6726 suggest a smaller pruning-stable signed dyadic-perturbation coverage family; they do not prove that family forces fullness. This helper only formalizes how any single shifted distance survives pruning.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

To show that the pruned configuration covers every vertex v ∈ ℤ at distance d < 2^(k+1), the proof reuses the exact same witness a guaranteed by the original coverage hypothesis at distance 2^(k+1) + d. The bound a < 2^(k+1) - d follows by arithmetic since 2^(k+2) = 2 * 2^(k+1). Coverage at index a holds because if a < 2^k the lift samples a directly, while if a ≥ 2^k the tightness assumption propagates the active bit from quarter 1 to quarter 3. Similarly, coverage at index a + d holds because if a + d < 2^k the active bit at a + 2^(k+1) + d lies in quarter 2 and propagates backward to a + d by tightness, while if a + d ≥ 2^k the lift samples index a + 2^(k+1) + d directly.

  1. Fix a vertex v and deduce the middle-quarter propagation properties for x from the tightness hypothesis.

    We introduce the arbitrary vertex v ∈ ℤ to be covered. By applying cycle_power_dyadic_tight_class_middle_parent to the tightness hypothesis htight p for each shift p, we establish two propagation rules: any active bit in the second quarter [2^k, 2^(k+1)) implies that the corresponding bit shifted forward by 2^(k+1) into the fourth quarter is active (hleft), and any active bit in the third quarter [2^(k+1), 3 * 2^k) implies that the bit shifted backward by 2^(k+1) into the first quarter is active (hright).

    lines 12–18

    uses cycle_power_dyadic_tight_class_middle_parent

      intro v
      have hleft : ∀ (p : ℤ) (a : ℕ), 2 ^ k ≤ a → a < 2 ^ (k + 1) →
          x p a = true → x p (a + 2 ^ (k + 1)) = true :=
        fun p => (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).1
      have hright : ∀ (p : ℤ) (a : ℕ), 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k →
          x p a = true → x p (a - 2 ^ (k + 1)) = true :=
        fun p => (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).2
  2. Obtain the witness a from the original coverage hypothesis at distance 2^(k+1) + d, and verify the bound a < 2^(k+1) - d.

    The hypothesis hcover v provides an index a < 2^(k+2) - (2^(k+1) + d) such that both a and a + 2^(k+1) + d are active in x(v - a). Rewriting 2^(k+2) as 2 * 2^(k+1) using pow_succ, linear arithmetic (omega) verifies that a < 2^(k+1) - d. We choose this same index a as our witness for the existential goal in the pruned configuration, leaving two goals: proving that the lifted configuration is active at index a and at index a + d.

    lines 19–21

    uses pow_succ

      obtain ⟨a, ha, h0, h1⟩ := hcover v
      have hH : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega
      refine ⟨a, by omega, ?_, ?_⟩
  3. The lifted configuration cycle_power_dyadic_b_lift k (x(v - a)) is active at index a.

    Unfolding the definition of cycle_power_dyadic_b_lift at index a, we split into cases based on whether a < 2^k: 1. If a < 2^k, the definition evaluates to x(v - a, a), which is true by the first coverage condition h0. 2. If a ≥ 2^k, the definition evaluates to x(v - a, a + 2^(k+1)). Since a < 2^(k+1) - d < 2^(k+1), the index a lies in [2^k, 2^(k+1)), so the forward propagation lemma hleft applies to h0 to conclude that x(v - a, a + 2^(k+1)) = true.

    lines 22–25

      · dsimp [cycle_power_dyadic_b_lift]
        split_ifs with hal
        · exact h0
        · exact hleft _ a (by omega) (by omega) h0
  4. The lifted configuration cycle_power_dyadic_b_lift k (x(v - a)) is active at index a + d.

    Unfolding the definition of cycle_power_dyadic_b_lift at index a + d, we split into cases based on whether a + d < 2^k: 1. If a + d < 2^k, the lifted configuration evaluates to x(v - a, a + d). The original second active point at a + 2^(k+1) + d lies in the third quarter [2^(k+1), 3 * 2^k) because a + d < 2^k. Thus the backward propagation lemma hright applies to h1, showing that x(v - a, a + (2^(k+1) + d) - 2^(k+1)) = x(v - a, a + d) is true. 2. If a + d ≥ 2^k, the lifted configuration evaluates to x(v - a, a + d + 2^(k+1)). Since a + d + 2^(k+1) = a + (2^(k+1) + d), this is true directly by h1.

    lines 26–32

      · dsimp [cycle_power_dyadic_b_lift]
        split_ifs with hal
        · have hb := hright (v - (a : ℤ)) (a + (2 ^ (k + 1) + d)) (by omega) (by omega) h1
          have he : a + (2 ^ (k + 1) + d) - 2 ^ (k + 1) = a + d := by omega
          simpa only [he] using hb
        · have he : a + d + 2 ^ (k + 1) = a + (2 ^ (k + 1) + d) := by omega
          simpa only [he] using h1
cycle_power_dyadic_tight_class_middle_parent
For any configuration of length 2^(k+2) with tight dyadic class weight, an active bit in the second quarter [2^k, 2^(k+1)) implies the corresponding bit in the fourth quarter (shifted by +2^(k+1)) is active, and an active bit in the third quarter [2^(k+1), 3 * 2^k) implies the corresponding bit in the first quarter (shifted by -2^(k+1)) is active.
pow_succ
In any monoid, a^(n+1) = a^n * a.

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_single_distance_cover    (k d : ℕ) (x : ℤ → ℕ → Bool) (hd : 1 ≤ d) (hdH : d < 2^(k+1))    (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) =      (range (2^(k+2))).sum (fun a => (x p a).toNat))    (hcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+2)-(2^(k+1)+d) ∧      x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+(2^(k+1)+d)) = true) :    ∀ v : ℤ, ∃ a : ℕ, 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  intro v  have hleft : ∀ (p : ℤ) (a : ℕ), 2 ^ k ≤ a → a < 2 ^ (k + 1) →      x p a = true → x p (a + 2 ^ (k + 1)) = true :=    fun p => (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).1  have hright : ∀ (p : ℤ) (a : ℕ), 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k →      x p a = true → x p (a - 2 ^ (k + 1)) = true :=    fun p => (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).2  obtain ⟨a, ha, h0, h1⟩ := hcover v  have hH : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega  refine ⟨a, by omega, ?_, ?_⟩  · dsimp [cycle_power_dyadic_b_lift]    split_ifs with hal    · exact h0    · exact hleft _ a (by omega) (by omega) h0  · dsimp [cycle_power_dyadic_b_lift]    split_ifs with hal    · have hb := hright (v - (a : ℤ)) (a + (2 ^ (k + 1) + d)) (by omega) (by omega) h1      have he : a + (2 ^ (k + 1) + d) - 2 ^ (k + 1) = a + d := by omega      simpa only [he] using hb    · have he : a + d + 2 ^ (k + 1) = a + (2 ^ (k + 1) + d) := by omega      simpa only [he] using h1
See it in the graphDiscuss this resultChallenge it