AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_count_iff_right_half_period

theoremverified

Under the dyadic pruning balance hypotheses, preservation of active count t is equivalent to half-radius periodicity of right-half memberships.

Statement

theorem cycle_power_dyadic_prune_count_iff_right_half_period
    (k t : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (k + 2) (x p) =
      (range (2 ^ (k + 2))).sum (fun a => (x p a).toNat))
    (hcount : ∀ v, (range (2 ^ (k + 2))).sum
      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1)
    (hhalf : ∀ v, (range (2 ^ (k + 1))).sum
      (fun a => (x (v - (a : ℤ)) a &&
        x (v - (a : ℤ)) (a + 2 ^ (k + 1))).toNat) = 1) :
    (∀ v, (range (2 ^ (k + 1))).sum (fun a =>
      (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat) = t) ↔
    (∀ v, (range (2 ^ (k + 1))).sum (fun a =>
      (x ((v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ))
        (2 ^ (k + 1) + a)).toNat) =
      (range (2 ^ (k + 1))).sum (fun a =>
        (x (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat))
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

Under the dyadic pruning balance hypotheses, the pruning balance identity establishes that for every shift v, the lifted active count sum L(v) plus the right-half membership sum S(v) equals t + S(v + 2^(k+1)). The equivalence between active count preservation (L(v) = t for all v) and half-radius periodicity (S(v + 2^(k+1)) = S(v) for all v) follows immediately: substituting either equality into the balance identity reduces it to the other by additive cancellation in ℕ.

  1. For every coordinate v ∈ ℤ, the balance equation L(v) + S(v) = t + S(v + 2^(k+1)) holds between the lifted active count sum L(v) and the right-half membership sums S(v) and S(v + 2^(k+1)); proving the equivalence reduces to verifying both implications.

    We invoke cycle_power_dyadic_prune_count_balance with the tightness (htight), diagonal count (hcount), and overlap (hhalf) hypotheses to obtain the balance relation hb for all shifts v. We then split the if-and-only-if goal into forward and reverse implications.

    lines 19–20

    uses cycle_power_dyadic_prune_count_balance

      have hb := cycle_power_dyadic_prune_count_balance k t x htight hcount hhalf
      constructor
  2. If the lifted active count is t for all shifts, then the right-half membership sum is periodic with period 2^(k+1).

    Assuming L(v) = t for all v (hypothesis hc), fix an arbitrary shift v ∈ ℤ. Specializing the balance equation hb to v gives L(v) + S(v) = t + S(v + 2^(k+1)). Rewriting with hc v replaces L(v) with t, yielding t + S(v) = t + S(v + 2^(k+1)). Linear integer arithmetic (omega) cancels t from both sides, concluding S(v + 2^(k+1)) = S(v).

    lines 21–24

      · intro hc v
        have hh := hb v
        rw [hc v] at hh
        omega
  3. Conversely, if the right-half membership sum is periodic with period 2^(k+1), then the lifted active count is t for all shifts.

    Assuming S(v + 2^(k+1)) = S(v) for all v (hypothesis hr), fix an arbitrary shift v ∈ ℤ. Specializing the balance equation hb to v gives L(v) + S(v) = t + S(v + 2^(k+1)). Rewriting with hr v replaces S(v + 2^(k+1)) with S(v), yielding L(v) + S(v) = t + S(v). Linear integer arithmetic (omega) cancels S(v) from both sides, concluding L(v) = t.

    lines 25–28

      · intro hr v
        have hh := hb v
        rw [hr v] at hh
        omega
cycle_power_dyadic_prune_count_balance
Under the dyadic pruning tightness, active count, and overlap hypotheses, for every shift v, the sum of the lifted active indicators plus the right-half membership sum at v equals t plus the shifted right-half membership sum at v + 2^(k+1).

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_count_iff_right_half_period    (k t : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (k + 2) (x p) =      (range (2 ^ (k + 2))).sum (fun a => (x p a).toNat))    (hcount : ∀ v, (range (2 ^ (k + 2))).sum      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1)    (hhalf : ∀ v, (range (2 ^ (k + 1))).sum      (fun a => (x (v - (a : ℤ)) a &&        x (v - (a : ℤ)) (a + 2 ^ (k + 1))).toNat) = 1) :    (∀ v, (range (2 ^ (k + 1))).sum (fun a =>      (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat) = t) ↔    (∀ v, (range (2 ^ (k + 1))).sum (fun a =>      (x ((v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ))        (2 ^ (k + 1) + a)).toNat) =      (range (2 ^ (k + 1))).sum (fun a =>        (x (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat)) := by  have hb := cycle_power_dyadic_prune_count_balance k t x htight hcount hhalf  constructor  · intro hc v    have hh := hb v    rw [hc v] at hh    omega  · intro hr v    have hh := hb v    rw [hr v] at hh    omega
See it in the graphDiscuss this resultChallenge it