cycle_power_dyadic_prune_cover_of_middle_parent
If every selected middle-quarter position has its matched outer-quarter parent selected, deleting and compressing the middle quarters preserves coverage of every smaller distance. The class start indices are unchanged.
Statement
theorem cycle_power_dyadic_prune_cover_of_middle_parent
(k : ℕ) (x : ℤ → ℕ → Bool)
(hleft : ∀ (p : ℤ) (a : ℕ), 2 ^ k ≤ a → a < 2 ^ (k + 1) →
x p a = true → x p (a + 2 ^ (k + 1)) = true)
(hright : ∀ (p : ℤ) (a : ℕ), 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k →
x p a = true → x p (a - 2 ^ (k + 1)) = true)
(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
Quot.soundpropext- Built on 1
- 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 1
- cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
The proof, explained
To cover a distance d < 2^(k+1) after pruning the middle two quarters and compressing the outer quarters, the proof queries the original coverage hypothesis at the shifted distance 2^(k+1) + d < 2^(k+2), obtaining a valid witness position a. Checking that both a and a + d remain selected in the lifted configuration splits on whether each index falls into the first quarter [0, 2^k) or the lifted second half. In each case, either the point is directly selected by the coverage witness or it lies in a middle quarter whose selection is propagated to an outer quarter by the parent-selection hypotheses hleft and hright.
Given a target distance d with 1 ≤ d < 2^(k+1) and an integer offset v, the powers of two satisfy 2^(k+1) = 2 * 2^k and 2^(k+2) = 2 * 2^(k+1).
We introduce the distance d, the bounds 1 ≤ d and d < 2^(k+1), and the offset v. We then establish the dyadic doubling identities 2^(k+1) = 2 * 2^k and 2^(k+2) = 2 * 2^(k+1) using pow_succ and linear arithmetic.
uses
pow_succintro d hd hdh v have hp1 : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hp2 : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega
There exists an index a < 2^(k+1) - d such that x(v - a, a) = true and x(v - a, a + 2^(k+1) + d) = true.
We apply the coverage hypothesis hcover to the shifted distance 2^(k+1) + d. Since 1 ≤ d < 2^(k+1), linear arithmetic shows 1 ≤ 2^(k+1) + d < 2^(k+2). This yields an index a < 2^(k+2) - (2^(k+1) + d) where both a and a + 2^(k+1) + d are selected in row v - a. Since 2^(k+2) - (2^(k+1) + d) = 2^(k+1) - d, a satisfies the required upper bound, and we supply a as the witness.
obtain ⟨a, ha, h0, h1⟩ := hcover (2 ^ (k + 1) + d) (by omega) (by omega) v refine ⟨a, by omega, ?_, ?_⟩
The lifted configuration for row v - a is true at position a.
By definition, cycle_power_dyadic_b_lift evaluates to x(v - a, a) if a < 2^k, and to x(v - a, a + 2^(k+1)) if a ≥ 2^k. In the first case, x(v - a, a) = true is directly the witness condition h0. In the second case, since a < 2^(k+1) - d < 2^(k+1), the index a lies in the second quarter [2^k, 2^(k+1)); hypothesis hleft ensures that because x(v - a, a) = true, its matched point x(v - a, a + 2^(k+1)) is also true.
· dsimp [cycle_power_dyadic_b_lift] split_ifs with hal · exact h0 · exact hleft _ a (by omega) (by omega) h0
The lifted configuration for row v - a is true at position a + d.
By definition, cycle_power_dyadic_b_lift at a + d evaluates to x(v - a, a + d) if a + d < 2^k, and to x(v - a, a + d + 2^(k+1)) if a + d ≥ 2^k. When a + d < 2^k, the position a + 2^(k+1) + d lies in the third quarter [2^(k+1), 3 * 2^k); hypothesis hright shifts this selected point down by 2^(k+1), concluding x(v - a, a + d) = true. When a + d ≥ 2^k, the goal requires x(v - a, a + d + 2^(k+1)) = true, which matches the known condition x(v - a, a + 2^(k+1) + d) = true.
· 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
pow_succ- In any monoid, the successor power satisfies 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_cover_of_middle_parent (k : ℕ) (x : ℤ → ℕ → Bool) (hleft : ∀ (p : ℤ) (a : ℕ), 2 ^ k ≤ a → a < 2 ^ (k + 1) → x p a = true → x p (a + 2 ^ (k + 1)) = true) (hright : ∀ (p : ℤ) (a : ℕ), 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k → x p a = true → x p (a - 2 ^ (k + 1)) = true) (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 intro d hd hdh v have hp1 : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hp2 : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega obtain ⟨a, ha, h0, h1⟩ := hcover (2 ^ (k + 1) + d) (by omega) (by omega) v 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