AFTD Auto-Formalizing Theoretical Domains

energy_filter_centered_row_sum

theoremverified

For any real integer function, summing it over offsets from −k to k equals summing it at j−k over j from 0 through 2k.

Statement

theorem energy_filter_centered_row_sum (k : ℕ) (f : ℤ → ℝ) :
    (∑ t ∈ Finset.Icc (-(k:ℤ)) (k:ℤ), f t) =
      ∑ j ∈ Finset.range (2*k+1), f ((j:ℤ)-(k:ℤ))
Source
OP-892: binomial-row specialization of the exact trace reindexing.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The sum equality is proved by reindexing via a bijection between the index sets using `Finset.sum_bij`. The map t ↦ (k + t).toNat shifts the interval of integers [-k, k] onto the natural numbers {0, ..., 2k}, with inverse j ↦ j - k. Linear integer arithmetic (`omega`) verifies that this shift is well-defined, injective, surjective, and leaves the evaluated function terms unchanged.

  1. The sum equality reduces to showing that t ↦ (k + t).toNat is a summand-preserving bijection from the integer interval [-k, k] to {0, ..., 2k}.

    Applying `Finset.sum_bij` with index mapping t ↦ (k + t).toNat reduces the equality of the two sums to four obligations: the map lands in the target set, it is injective, it is surjective, and the summands agree under the mapping.

    line 4

    uses Finset.sum_bij

      apply Finset.sum_bij (fun t _ => ((k:ℤ)+t).toNat)
  2. For every t ∈ [-k, k], the index (k + t).toNat belongs to Finset.range (2*k + 1).

    Rewriting the assumption t ∈ [-k, k] with `Finset.mem_Icc` gives -k ≤ t ≤ k, and rewriting the goal with `Finset.mem_range` gives (k + t).toNat < 2*k + 1. Since k + t ≥ 0, (k + t).toNat = k + t ≤ 2k < 2k + 1, which `omega` verifies by linear arithmetic.

    lines 5–8

    uses Finset.mem_Icc, Finset.mem_range

      · intro t ht
        rw [Finset.mem_Icc] at ht
        rw [Finset.mem_range]
        omega
  3. The index mapping is injective on [-k, k].

    Given a, b ∈ [-k, k] such that (k + a).toNat = (k + b).toNat, rewriting the interval bounds with `Finset.mem_Icc` ensures that k + a ≥ 0 and k + b ≥ 0. Hence the non-negative integers coincide, giving k + a = k + b and thus a = b via linear arithmetic (`omega`).

    lines 9–11

    uses Finset.mem_Icc

      · intro a ha b hb hab
        rw [Finset.mem_Icc] at ha hb
        omega
  4. The index mapping is surjective onto Finset.range (2*k + 1).

    Given j ∈ Finset.range (2*k + 1), rewriting with `Finset.mem_range` gives j < 2*k + 1. Choosing the preimage witness t = (j : ℤ) - (k : ℤ), `omega` confirms via `Finset.mem_Icc` that -k ≤ j - k ≤ k (since 0 ≤ j ≤ 2k) and that (k + (j - k)).toNat = j.

    lines 12–16

    uses Finset.mem_range, Finset.mem_Icc

      · intro j hj
        rw [Finset.mem_range] at hj
        refine ⟨(j:ℤ)-(k:ℤ), ?_, ?_⟩
        · rw [Finset.mem_Icc]; omega
        · omega
  5. The summand values agree under the bijection: f t = f (((k + t).toNat : ℤ) - k).

    For t ∈ [-k, k], `Finset.mem_Icc` gives -k ≤ t, so k + t ≥ 0. Thus ((k + t).toNat : ℤ) - k = (k + t) - k = t, proven as an auxiliary identity `he` by `omega`. Rewriting by `he` establishes that the summands match.

    lines 17–20

    uses Finset.mem_Icc

      · intro t ht
        rw [Finset.mem_Icc] at ht
        have he : ((((k:ℤ)+t).toNat:ℤ)-(k:ℤ)) = t := by omega
        rw [he]
Finset.sum_bij
Two finite sums are equal if there is a bijection between their index sets such that corresponding summands are equal.
Finset.mem_Icc
An element x belongs to the closed interval Finset.Icc a b if and only if a ≤ x and x ≤ b.
Finset.mem_range
A natural number m belongs to Finset.range n if and only if m < n.

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 energy_filter_centered_row_sum (k : ℕ) (f : ℤ → ℝ) :    (∑ t ∈ Finset.Icc (-(k:ℤ)) (k:ℤ), f t) =      ∑ j ∈ Finset.range (2*k+1), f ((j:ℤ)-(k:ℤ)) := by  apply Finset.sum_bij (fun t _ => ((k:ℤ)+t).toNat)  · intro t ht    rw [Finset.mem_Icc] at ht    rw [Finset.mem_range]    omega  · intro a ha b hb hab    rw [Finset.mem_Icc] at ha hb    omega  · intro j hj    rw [Finset.mem_range] at hj    refine ⟨(j:ℤ)-(k:ℤ), ?_, ?_⟩    · rw [Finset.mem_Icc]; omega    · omega  · intro t ht    rw [Finset.mem_Icc] at ht    have he : ((((k:ℤ)+t).toNat:ℤ)-(k:ℤ)) = t := by omega    rw [he]
See it in the graphDiscuss this resultChallenge it