AFTD Auto-Formalizing Theoretical Domains

cycle_power_middle_quarter_prune_count_balance

theoremverified

For a four-quarter class model with parent implications, constant original active count t+1, and exact half-distance coverage, pruning gives C_pruned(v)+R(v)=t+R(v+H).

Statement

theorem cycle_power_middle_quarter_prune_count_balance
    (q t : ℕ) (x : ℤ → ℕ → Bool)
    (hleft : ∀ (p : ℤ) (a : ℕ), q ≤ a → a < 2 * q →
      x p a = true → x p (a + 2 * q) = true)
    (hright : ∀ (p : ℤ) (a : ℕ), 2 * q ≤ a → a < 3 * q →
      x p a = true → x p (a - 2 * q) = true)
    (hcount : ∀ v : ℤ, (range (4 * q)).sum
      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1)
    (hhalf : ∀ v : ℤ, (range (2 * q)).sum
      (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = 1) :
    ∀ v : ℤ,
      (range (2 * q)).sum (fun a =>
        ((if a < q then x (v - (a : ℤ)) a else
          x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) +
      (range (2 * q)).sum (fun a =>
        (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) =
      t + (range (2 * q)).sum (fun a =>
        (x (v - (a : ℤ)) (2 * q + 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 1
Used by 1

The proof, explained

The proof decomposes the active counts across a range of length 4*q into four quarters of size q, denoted A, B, C, D, whose sum is t + 1 by the total count hypothesis. Using the half-distance coverage hypothesis and the directional implications between quarters, the conjunctions simplify to show that the shifted count E and the second quarter B satisfy E + B = 1. The pruned sum evaluates to A + F while the remaining sums decompose as C + D and E + F, reducing the balance equation (A + F) + (C + D) = t + (E + F) to the linear arithmetic identity (A + B + C + D) - (E + B) = t.

  1. Fix v and establish helper lemmas for splitting length-2q sums and simplifying Boolean conjunctions under implication.

    We fix an arbitrary integer v. We first prove a helper lemma htwo stating that any sum over range (2 * q) splits into two sums of length q via sum_range_add and two_mul (2 * q = q + q). We then prove two Boolean lemmas (handr and handl): if b = true implies a = true, then a && b simplifies to b; symmetrically, if a = true implies b = true, then a && b simplifies to a.

    lines 21–31

    uses two_mul, sum_range_add

      intro v
      have htwo (f : ℕ → ℕ) :
          (range (2 * q)).sum f = (range q).sum f +
            (range q).sum (fun a => f (q + a)) := by
        simpa only [two_mul] using (sum_range_add f q q)
      have handr (a b : Bool) (h : b = true → a = true) :
          (a && b).toNat = b.toNat := by
        cases a <;> cases b <;> simp_all
      have handl (a b : Bool) (h : a = true → b = true) :
          (a && b).toNat = a.toNat := by
        cases a <;> cases b <;> simp_all
  2. Define the six quarter-range sums A, B, C, D, E, F.

    We partition the active points into blocks of length q: A, B, C, D denote the active counts in the four quarters of the original interval of length 4 * q (offsets a, q + a, 2 * q + a, and 2 * q + (q + a) for a < q), while E and F denote the active counts in the first two quarters when shifted by 2 * q.

    lines 32–39

      let A := (range q).sum (fun a => (x (v - (a : ℤ)) a).toNat)
      let B := (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat)
      let C := (range q).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat)
      let D := (range q).sum (fun a =>
        (x (v - ((2 * q + (q + a) : ℕ) : ℤ)) (2 * q + (q + a))).toNat)
      let E := (range q).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat)
      let F := (range q).sum (fun a =>
        (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat)
  3. The sum of the four quarters equals t + 1, that is, A + B + C + D = t + 1.

    By hypothesis hcount, the total active count over range (4 * q) is t + 1. Applying cycle_power_dyadic_sum_range_four_blocks splits this into four blocks of length q. The first three blocks match the definitions of A, B, C, and using sum_congr with the index equality 2 * q + (q + a) = 3 * q + a shows the fourth block matches D.

    lines 40–52

    uses cycle_power_dyadic_sum_range_four_blocks, sum_congr

      have hfull : A + B + C + D = t + 1 := by
        have hh := hcount v
        have hs := cycle_power_dyadic_sum_range_four_blocks q
          (fun a => (x (v - (a : ℤ)) a).toNat)
        change (range (4 * q)).sum (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1 at hh
        rw [hs] at hh
        have hD : D = (range q).sum (fun a =>
            (x (v - ((3 * q + a : ℕ) : ℤ)) (3 * q + a)).toNat) := by
          apply sum_congr rfl
          intro a ha
          rw [show 2 * q + (q + a) = 3 * q + a by omega]
        rw [hD]
        exact hh
  4. The half-distance overlap sum gives E + B = 1.

    Hypothesis hhalf asserts that the pairwise conjunction sum over range (2 * q) equals 1. Splitting this range into two blocks of length q using htwo: for the first block (a < q), index a + 2 * q is in [2 * q, 3 * q), so by hright and Nat.add_sub_cancel_right, x (v - a) (a + 2 * q) = true implies x (v - a) a = true, simplifying the conjunction to x (v - a) (2 * q + a) (via Nat.add_comm and handr), which sums to E; for the second block (q + a), by hleft, x (v - (q + a)) (q + a) = true implies x (v - (q + a)) (q + a + 2 * q) = true, simplifying the conjunction to x (v - (q + a)) (q + a) via handl, which sums to B. Both block simplifications use sum_congr. Hence E + B = 1.

    lines 53–77

    uses sum_congr, Nat.add_sub_cancel_right, Nat.add_comm

      have hmid : E + B = 1 := by
        have hh := hhalf v
        rw [htwo] at hh
        have hfirst :
            (range q).sum (fun a =>
              (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = E := by
          apply sum_congr rfl
          intro a ha
          have haq : a < q := mem_range.mp ha
          have hp : x (v - (a : ℤ)) (a + 2 * q) = true →
              x (v - (a : ℤ)) a = true := by
            intro hx
            have hh := hright (v - (a : ℤ)) (a + 2 * q) (by omega) (by omega) hx
            simpa only [Nat.add_sub_cancel_right] using hh
          simpa only [Nat.add_comm a (2 * q)] using handr _ _ hp
        have hsecond :
            (range q).sum (fun a =>
              (x (v - ((q + a : ℕ) : ℤ)) (q + a) &&
                x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat) = B := by
          apply sum_congr rfl
          intro a ha
          have haq : a < q := mem_range.mp ha
          exact handl _ _ (hleft _ _ (by omega) (by omega))
        rw [hfirst, hsecond] at hh
        exact hh
  5. The pruned sum over range (2 * q) decomposes as A + F.

    Splitting the pruned sum into two blocks of length q via htwo: for the first block (a < q), if_pos simplifies the summand to x (v - a) a, summing to A; for the second block (offset q + a), since q + a < q is false, if_neg selects the shifted component x (v - (q + a)) (q + a + 2 * q), which by index arithmetic matches the definition of F. Both steps use sum_congr.

    lines 78–92

    uses sum_congr, if_pos, if_neg

      have hprune :
          (range (2 * q)).sum (fun a =>
            ((if a < q then x (v - (a : ℤ)) a else
              x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) = A + F := by
        rw [htwo]
        congr 1
        · apply sum_congr rfl
          intro a ha
          rw [if_pos (mem_range.mp ha)]
        · apply sum_congr rfl
          intro a ha
          rw [if_neg (by omega : ¬q + a < q)]
          change (x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat =
            (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat
          rw [show q + a + 2 * q = 2 * q + (q + a) by omega]
  6. The remaining two sums decompose as C + D and E + F, respectively.

    Applying the splitting lemma htwo directly to the second sum on the left-hand side yields C + D, and applying it to the sum on the right-hand side yields E + F.

    lines 93–96

      have hrightcount : (range (2 * q)).sum (fun a =>
          (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) = C + D := htwo _
      have hshiftcount : (range (2 * q)).sum (fun a =>
          (x (v - (a : ℤ)) (2 * q + a)).toNat) = E + F := htwo _
  7. The balance equation holds by linear integer arithmetic.

    Rewriting with the decompositions from the previous steps reduces the theorem to (A + F) + (C + D) = t + (E + F). Linear arithmetic (omega) closes this from A + B + C + D = t + 1 and E + B = 1, as (A + F + C + D) - (t + E + F) = (A + B + C + D) - (t + 1) + 1 - (E + B) = 0.

    lines 97–98

      rw [hprune, hrightcount, hshiftcount]
      omega
two_mul
Multiplication by 2 equals addition to self: 2 * n = n + n.
sum_range_add
A sum over range (n + m) splits into the sum over range n and the sum over range m shifted by n.
cycle_power_dyadic_sum_range_four_blocks
A sum over range (4 * L) splits into four sums over range L with offsets 0, L, 2 * L, and 3 * L.
sum_congr
Two sums over the same finite set are equal if their summands agree on every element.
Nat.add_sub_cancel_right
Subtracting m from n + m yields n: n + m - m = n.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.
if_pos
An if-then-else evaluates to the then-branch when the condition is true.
if_neg
An if-then-else evaluates to the else-branch when the condition is false.

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_middle_quarter_prune_count_balance    (q t : ℕ) (x : ℤ → ℕ → Bool)    (hleft : ∀ (p : ℤ) (a : ℕ), q ≤ a → a < 2 * q →      x p a = true → x p (a + 2 * q) = true)    (hright : ∀ (p : ℤ) (a : ℕ), 2 * q ≤ a → a < 3 * q →      x p a = true → x p (a - 2 * q) = true)    (hcount : ∀ v : ℤ, (range (4 * q)).sum      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1)    (hhalf : ∀ v : ℤ, (range (2 * q)).sum      (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = 1) :    ∀ v : ℤ,      (range (2 * q)).sum (fun a =>        ((if a < q then x (v - (a : ℤ)) a else          x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) +      (range (2 * q)).sum (fun a =>        (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) =      t + (range (2 * q)).sum (fun a =>        (x (v - (a : ℤ)) (2 * q + a)).toNat) := by  intro v  have htwo (f : ℕ → ℕ) :      (range (2 * q)).sum f = (range q).sum f +        (range q).sum (fun a => f (q + a)) := by    simpa only [two_mul] using (sum_range_add f q q)  have handr (a b : Bool) (h : b = true → a = true) :      (a && b).toNat = b.toNat := by    cases a <;> cases b <;> simp_all  have handl (a b : Bool) (h : a = true → b = true) :      (a && b).toNat = a.toNat := by    cases a <;> cases b <;> simp_all  let A := (range q).sum (fun a => (x (v - (a : ℤ)) a).toNat)  let B := (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat)  let C := (range q).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat)  let D := (range q).sum (fun a =>    (x (v - ((2 * q + (q + a) : ℕ) : ℤ)) (2 * q + (q + a))).toNat)  let E := (range q).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat)  let F := (range q).sum (fun a =>    (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat)  have hfull : A + B + C + D = t + 1 := by    have hh := hcount v    have hs := cycle_power_dyadic_sum_range_four_blocks q      (fun a => (x (v - (a : ℤ)) a).toNat)    change (range (4 * q)).sum (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1 at hh    rw [hs] at hh    have hD : D = (range q).sum (fun a =>        (x (v - ((3 * q + a : ℕ) : ℤ)) (3 * q + a)).toNat) := by      apply sum_congr rfl      intro a ha      rw [show 2 * q + (q + a) = 3 * q + a by omega]    rw [hD]    exact hh  have hmid : E + B = 1 := by    have hh := hhalf v    rw [htwo] at hh    have hfirst :        (range q).sum (fun a =>          (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = E := by      apply sum_congr rfl      intro a ha      have haq : a < q := mem_range.mp ha      have hp : x (v - (a : ℤ)) (a + 2 * q) = true →          x (v - (a : ℤ)) a = true := by        intro hx        have hh := hright (v - (a : ℤ)) (a + 2 * q) (by omega) (by omega) hx        simpa only [Nat.add_sub_cancel_right] using hh      simpa only [Nat.add_comm a (2 * q)] using handr _ _ hp    have hsecond :        (range q).sum (fun a =>          (x (v - ((q + a : ℕ) : ℤ)) (q + a) &&            x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat) = B := by      apply sum_congr rfl      intro a ha      have haq : a < q := mem_range.mp ha      exact handl _ _ (hleft _ _ (by omega) (by omega))    rw [hfirst, hsecond] at hh    exact hh  have hprune :      (range (2 * q)).sum (fun a =>        ((if a < q then x (v - (a : ℤ)) a else          x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) = A + F := by    rw [htwo]    congr 1    · apply sum_congr rfl      intro a ha      rw [if_pos (mem_range.mp ha)]    · apply sum_congr rfl      intro a ha      rw [if_neg (by omega : ¬q + a < q)]      change (x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat =        (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat      rw [show q + a + 2 * q = 2 * q + (q + a) by omega]  have hrightcount : (range (2 * q)).sum (fun a =>      (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) = C + D := htwo _  have hshiftcount : (range (2 * q)).sum (fun a =>      (x (v - (a : ℤ)) (2 * q + a)).toNat) = E + F := htwo _  rw [hprune, hrightcount, hshiftcount]  omega
See it in the graphDiscuss this resultChallenge it