cycle_power_dyadic_prune_single_distance_cover
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
- 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_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.
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.
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).
uses
cycle_power_dyadic_tight_class_middle_parentintro 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 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.
uses
pow_succobtain ⟨a, ha, h0, h1⟩ := hcover v have hH : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega refine ⟨a, by omega, ?_, ?_⟩
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.
· dsimp [cycle_power_dyadic_b_lift] split_ifs with hal · exact h0 · exact hleft _ a (by omega) (by omega) h0
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.
· 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
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_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