AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_exact

theoremverified

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

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.

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

    lines 14–16

    uses Eq.trans, sum_congr

      intro j hj v
      refine Eq.trans ?_ (hexact j (by omega) v)
      apply sum_congr rfl
  2. 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.

    lines 17–23

    uses Nat.pow_le_pow_right, pow_succ

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

    lines 24–27

    uses if_pos, if_neg

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

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