cycle_power_dyadic_prune_exact
Deleting the middle two quarters of every class preserves every smaller-scale exact dyadic long-edge count, without changing the class start indices.
Statement
theorem cycle_power_dyadic_prune_exact (k : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ j < k + 2, ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ (k + 2) - 2 ^ j)).toNat) = 1) : ∀ j < k + 1, ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a && cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) (a + 2 ^ (k + 1) - 2 ^ j)).toNat) = 1
- 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 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 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 proves that pruning the middle two quarters of each length-2^(k+2) class using cycle_power_dyadic_b_lift preserves the exact dyadic long-edge condition for all smaller scales j < k + 1. By transitivity with the hypothesis hexact, it suffices to show that each summand of the pruned sum equals the original summand. For any a < 2^j ≤ 2^k, the first index a is strictly below 2^k and remains unshifted, while the second index a + 2^(k+1) - 2^j is at least 2^k and is shifted by 2^(k+1), producing a + 2^(k+2) - 2^j, which exactly recovers the summand from the original sum.
It suffices to show that each summand of the pruned dyadic sum equals the corresponding summand of the original exact sum.
Let j < k + 1 and v ∈ ℤ be given. Since j < k + 1 implies j < k + 2, the assumption hexact guarantees that the original sum over a ∈ range(2^j) equals 1. By transitivity of equality (Eq.trans), it suffices to show that the pruned sum equals the original sum. Applying congruence of finite sums (sum_congr), this reduces to proving that the summands agree pointwise for each a ∈ range(2^j).
uses
Eq.trans,sum_congrintro j hj v refine Eq.trans ?_ (hexact j (by omega) v) apply sum_congr rfl
For any index a < 2^j, the index a is strictly less than 2^k, whereas the second index a + 2^(k+1) - 2^j is at least 2^k.
Fix an index a ∈ range(2^j), so a < 2^j. From j < k + 1, we have j ≤ k, so monotonicity of powers of 2 (Nat.pow_le_pow_right) gives 2^j ≤ 2^k, and thus a < 2^k. Moreover, expanding 2^(k+1) = 2 * 2^k via pow_succ, the shifted index satisfies a + 2^(k+1) - 2^j = a + 2^k + (2^k - 2^j) ≥ 2^k, so it cannot be strictly less than 2^k.
uses
Nat.pow_le_pow_right,pow_succintro a ha have haj : a < 2 ^ j := mem_range.mp ha have hjk : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) (by omega) 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 have hl : a < 2 ^ k := by omega have hr : ¬a + 2 ^ (k + 1) - 2 ^ j < 2 ^ k := by omega
Each summand in the pruned sum equals the corresponding summand in the original sum, completing the proof.
Unfolding the definition of cycle_power_dyadic_b_lift, each term tests whether the index is strictly less than 2^k. Since a < 2^k, if_pos simplifies the first factor to x(v - a, a). Since the second index is not strictly less than 2^k, if_neg simplifies the second factor to x(v - a, a + 2^(k+1) - 2^j + 2^(k+1)). Using the arithmetic identity (a + 2^(k+1) - 2^j) + 2^(k+1) = a + 2^(k+2) - 2^j, rewriting with this equality matches the original summand exactly.
uses
if_pos,if_negdsimp [cycle_power_dyadic_b_lift] rw [if_pos hl, if_neg hr] have he : a + 2 ^ (k + 1) - 2 ^ j + 2 ^ (k + 1) = a + 2 ^ (k + 2) - 2 ^ j := by omega rw [he]
Eq.trans- Equality is transitive: if a = b and b = c, then a = c.
sum_congr- Two finite sums over the same index set are equal if their summands agree on every element of the index set.
Nat.pow_le_pow_right- For any base n > 0, the power function n^i is monotonic in the exponent: i ≤ j implies n^i ≤ n^j.
pow_succ- Raising an element to power n + 1 equals its n-th power multiplied by the element itself: a^(n+1) = a^n * a.
if_pos- A conditional expression `if c then t else e` reduces to the 'then' branch t when the condition c holds.
if_neg- A conditional expression `if c then t else e` reduces to the 'else' branch e when the condition c does not hold.
- Natural number arithmetic bounds and identities (such as deriving $j < k + 2$ from $j < k + 1$, and $(a + 2^{k+1} - 2^j) + 2^{k+1} = a + 2^{k+2} - 2^j$) are discharged automatically by Lean's Presburger arithmetic solver omega.
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_exact (k : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ j < k + 2, ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ (k + 2) - 2 ^ j)).toNat) = 1) : ∀ j < k + 1, ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a && cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) (a + 2 ^ (k + 1) - 2 ^ j)).toNat) = 1 := by intro j hj v refine Eq.trans ?_ (hexact j (by omega) v) apply sum_congr rfl intro a ha have haj : a < 2 ^ j := mem_range.mp ha have hjk : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) (by omega) 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 have hl : a < 2 ^ k := by omega have hr : ¬a + 2 ^ (k + 1) - 2 ^ j < 2 ^ k := by omega dsimp [cycle_power_dyadic_b_lift] rw [if_pos hl, if_neg hr] have he : a + 2 ^ (k + 1) - 2 ^ j + 2 ^ (k + 1) = a + 2 ^ (k + 2) - 2 ^ j := by omega rw [he]