AFTD Auto-Formalizing Theoretical Domains

cycle_power_defective_fold_count_balance

theoremverified

Folding a defective model yields an exact identity relating folded count, lower-half counts and shifted defects.

Statement

theorem cycle_power_defective_fold_count_balance
    (L k : ℕ) (y : ℤ → ℕ → Bool) (e : ℤ → Bool) (shift : ℤ)
    (hcount : ∀ v : ℤ, (Finset.range (L+L)).sum (fun a =>
      (y (v-(a : ℤ)) a).toNat) + (e v).toNat = k+1)
    (htop : ∀ v : ℤ, (Finset.range L).sum (fun a =>
      (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+L)).toNat) + (e (v+shift)).toNat = 1) :
    ∀ v : ℤ,
      (Finset.range L).sum (fun a =>
        (y (v-(a : ℤ)) a || y (v-(a : ℤ)) (a+L)).toNat) +
      (Finset.range L).sum (fun a => (y (v+(L:ℤ)-(a:ℤ)) a).toNat) +
      (e (v+(L:ℤ))).toNat =
      (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) + k + (e (v+shift)).toNat
Source
Defective half-model reduction for research thread RT-1.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof establishes the balance identity by evaluating the count hypothesis at v + L and splitting the 2L terms into two ranges of length L. The upper-half range is re-indexed to match the defective coordinates, and a boolean inclusion-exclusion identity—that (p || q) + (p && q) = p + q—is summed to relate the folded OR terms to the AND terms. Finally, substituting the hypothesis on AND terms evaluated at v into these relations leaves a linear system over ℕ that is resolved by linear arithmetic.

  1. Fix an arbitrary vertex v ∈ ℤ.

    We introduce the vertex v for which the balance identity is to be shown.

    line 13

      intro v
  2. The count hypothesis evaluated at v + L splits into a sum over [0, L) and a sum over [L, 2L) plus the defect at v + L, equaling k + 1.

    We specialize the count hypothesis hcount at v + L and split the summation over [0, 2L) into two ranges of length L using Finset.sum_range_add.

    lines 14–15

    uses Finset.sum_range_add

      have hc := hcount (v+(L:ℤ))
      rw [Finset.sum_range_add] at hc
  3. The second sum of length L re-indexes to ∑_{a < L} y(v - a, a + L), updating the count equation.

    For each i < L, the index simplifies as v + L - (L + i) = v - i and L + i = i + L via Nat.add_comm. Using Finset.sum_congr, the second sum rewrites to ∑_{a < L} y(v - a, a + L), so the count hypothesis at v + L becomes ∑_{a < L} y(v + L - a, a) + ∑_{a < L} y(v - a, a + L) + e(v + L) = k + 1.

    lines 16–22

    uses Finset.sum_congr, Nat.add_comm

      have hB : (Finset.range L).sum (fun i =>
          (y (v+(L:ℤ)-((L+i:ℕ):ℤ)) (L+i)).toNat) =
          (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by
        refine Finset.sum_congr rfl fun i _ => ?_
        have hp : v+(L:ℤ)-((L+i:ℕ):ℤ) = v-(i:ℤ) := by push_cast; ring
        rw [hp, Nat.add_comm L i]
      rw [hB] at hc
  4. The sum of the boolean disjunctions and conjunctions equals the sum of the individual component sums.

    For any Booleans p and q, the identity (p || q).toNat + (p && q).toNat = p.toNat + q.toNat holds by exhaustion over the four boolean cases. Combining this pointwise equality across the sum via Finset.sum_add_distrib and Finset.sum_congr gives the inclusion-exclusion relation between the OR sum, AND sum, and component sums.

    lines 23–31

    uses Finset.sum_add_distrib, Finset.sum_congr

      have hF : (Finset.range L).sum (fun a =>
          (y (v-(a:ℤ)) a || y (v-(a:ℤ)) (a+L)).toNat) +
          (Finset.range L).sum (fun a =>
            (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+L)).toNat) =
          (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) +
          (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by
        rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib]
        refine Finset.sum_congr rfl fun a _ => ?_
        cases y (v-(a:ℤ)) a <;> cases y (v-(a:ℤ)) (a+L) <;> rfl
  5. The overlap hypothesis at v relates the conjunction sum and shifted defect to 1.

    Specializing htop at vertex v yields ∑_{a < L} (y(v - a, a) && y(v - a, a + L)).toNat + e(v + shift).toNat = 1.

    line 32

      have hp := htop v
  6. The balance identity holds.

    Linear arithmetic over ℕ (omega) combines the split count equation, the inclusion-exclusion identity, and the overlap equation to eliminate the conjunction sum and the upper-half component sum, completing the proof.

    line 33

      omega
Finset.sum_range_add
Splits a sum over the range [0, n + m) into a sum over [0, n) and a sum over [0, m) with indices shifted by n.
Finset.sum_congr
Two sums over the same finite set are equal if their summands agree at every element.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.
Finset.sum_add_distrib
The sum of a pointwise sum f(x) + g(x) over a finite set equals the sum of f plus the sum of g.

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

theorem cycle_power_defective_fold_count_balance    (L k : ℕ) (y : ℤ → ℕ → Bool) (e : ℤ → Bool) (shift : ℤ)    (hcount : ∀ v : ℤ, (Finset.range (L+L)).sum (fun a =>      (y (v-(a : ℤ)) a).toNat) + (e v).toNat = k+1)    (htop : ∀ v : ℤ, (Finset.range L).sum (fun a =>      (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+L)).toNat) + (e (v+shift)).toNat = 1) :    ∀ v : ℤ,      (Finset.range L).sum (fun a =>        (y (v-(a : ℤ)) a || y (v-(a : ℤ)) (a+L)).toNat) +      (Finset.range L).sum (fun a => (y (v+(L:ℤ)-(a:ℤ)) a).toNat) +      (e (v+(L:ℤ))).toNat =      (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) + k + (e (v+shift)).toNat := by  intro v  have hc := hcount (v+(L:ℤ))  rw [Finset.sum_range_add] at hc  have hB : (Finset.range L).sum (fun i =>      (y (v+(L:ℤ)-((L+i:ℕ):ℤ)) (L+i)).toNat) =      (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by    refine Finset.sum_congr rfl fun i _ => ?_    have hp : v+(L:ℤ)-((L+i:ℕ):ℤ) = v-(i:ℤ) := by push_cast; ring    rw [hp, Nat.add_comm L i]  rw [hB] at hc  have hF : (Finset.range L).sum (fun a =>      (y (v-(a:ℤ)) a || y (v-(a:ℤ)) (a+L)).toNat) +      (Finset.range L).sum (fun a =>        (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+L)).toNat) =      (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) +      (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by    rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib]    refine Finset.sum_congr rfl fun a _ => ?_    cases y (v-(a:ℤ)) a <;> cases y (v-(a:ℤ)) (a+L) <;> rfl  have hp := htop v  omega
See it in the graphDiscuss this resultChallenge it