AFTD Auto-Formalizing Theoretical Domains

op_153_fourier_mean_eq_constant_term

theoremverified

For M > 0, weights phi : Z -> C supported on a finite set T containing 0, with every nonzero frequency x in T satisfying |x| < M: the average of the values sum_{x in T} phi(x)*exp(2*pi*I*x*n/M) over n = 0, ..., M-1 is the constant term phi(0).

Statement

theorem op_153_fourier_mean_eq_constant_term (M : ℕ) (hM : 0 < M) (φ : ℤ → ℂ) (T : Finset ℤ)
    (h0 : (0 : ℤ) ∈ T) (hlt : ∀ x ∈ T, x ≠ 0 → x.natAbs < M) :
    (1 / (M : ℂ)) * (∑ n ∈ Finset.range M,
        ∑ x ∈ T, φ x * Complex.exp (2 * Real.pi * Complex.I * (x : ℂ) * (n : ℂ) / (M : ℂ))) = φ 0
Source
step towards op_153_eventually_subexp_bound_positive_quadratic
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1
  • op_153_fourier_density_boundLet M > 2N, let S be a set of positive integers at most N, and let phi : Z -> C be supported on {0} \u222a S \u222a (-S) with sum of…

The proof, explained

We rewrite the average by interchanging the two finite summations so that the sum over frequencies x ∈ T is on the outside. For each frequency x, the inner sum over roots of unity evaluates to M if M ∣ x and 0 otherwise, by root-of-unity orthogonality. Because every nonzero frequency in T has absolute value strictly less than M, no nonzero frequency is divisible by M, so the outer sum collapses to the single term at x = 0. This single term equals φ(0) * M, and multiplying by 1 / M cancels M to leave φ(0).

  1. The cast of M to ℂ is nonzero, and interchanging the order of summation expresses the average with the sum over T on the outside.

    Since M > 0, its cast to the complex numbers is nonzero (Nat.cast_ne_zero.mpr). Using Finset.sum_comm, we swap the finite sum over n ∈ {0, ..., M-1} and the finite sum over x ∈ T so that the sum over frequencies x is the outer sum.

    lines 6–7

    uses Nat.cast_ne_zero.mpr, Finset.sum_comm

      have hMne : (M : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr hM.ne'
      rw [Finset.sum_comm]
  2. The inner sum over n simplifies using orthogonality of roots of unity, rewriting the total expression as (1 / M) * ∑_{x ∈ T} φ(x) * (M if M ∣ x else 0).

    For each fixed x ∈ T, we factor the coefficient φ(x) out of the sum over n using Finset.mul_sum. After commuting the product x * n to n * x in the exponential argument, the remaining sum ∑_{n=0}^{M-1} exp(2π i n x / M) is evaluated via op_153_root_of_unity_orthogonality to M if M ∣ x and 0 otherwise. Rewriting the inner sum using Finset.sum_congr yields the claim.

    lines 8–20

    uses Finset.mul_sum, Finset.sum_congr, op_153_root_of_unity_orthogonality

      have hinner : ∀ x ∈ T, (∑ n ∈ Finset.range M, φ x * Complex.exp (2 * Real.pi * Complex.I * (x : ℂ) * (n : ℂ) / (M : ℂ)))
          = φ x * (if (M : ℤ) ∣ x then (M : ℂ) else 0) := by
        intro x hx
        rw [← Finset.mul_sum]
        congr 1
        have hshift : (∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (x : ℂ) * (n : ℂ) / (M : ℂ)))
            = ∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (x : ℂ) / (M : ℂ)) := by
          apply Finset.sum_congr rfl
          intro n hn
          congr 1
          ring
        rw [hshift, op_153_root_of_unity_orthogonality M hM x]
      rw [Finset.sum_congr rfl hinner]
  3. The sum over x ∈ T collapses to its single nonzero term at x = 0, which evaluates to φ(0) * M.

    We apply Finset.sum_eq_single at 0 ∈ T. At x = 0, M ∣ 0 holds trivially, giving φ(0) * M. For any nonzero frequency b ∈ T, if M were to divide b, then Int.natAbs_le_of_dvd_ne_zero would imply M ≤ |b|, contradicting the hypothesis hlt that |b| < M; thus M ∤ b, and the term vanishes. Finally, the assumption h0 confirms 0 ∈ T.

    lines 21–33

    uses Finset.sum_eq_single, Int.natAbs_le_of_dvd_ne_zero

      have hsingle : (∑ x ∈ T, φ x * (if (M : ℤ) ∣ x then (M : ℂ) else 0)) = φ 0 * (M : ℂ) := by
        rw [Finset.sum_eq_single (0 : ℤ)]
        · simp
        · intro b hb hb0
          have hndvd : ¬ (M : ℤ) ∣ b := by
            intro hdvd
            have hle : (M : ℤ).natAbs ≤ b.natAbs := Int.natAbs_le_of_dvd_ne_zero hdvd hb0
            have hMabs : (M : ℤ).natAbs = M := by simp
            have := hlt b hb hb0
            omega
          simp [hndvd]
        · intro h
          exact absurd h0 h
  4. Substituting the single-term evaluation and canceling M yields φ(0).

    Replacing the sum over T with φ(0) * M leaves (1 / M) * (φ(0) * M). By mul_comm and mul_assoc, this rearranges to ((1 / M) * M) * φ(0). Since M ≠ 0, the factors cancel via one_div and inv_mul_cancel₀, and one_mul leaves φ(0).

    lines 34–35

    uses mul_comm, mul_assoc, one_div, inv_mul_cancel₀, one_mul

      rw [hsingle]
      rw [mul_comm (φ 0) (M : ℂ), ← mul_assoc, one_div, inv_mul_cancel₀ hMne, one_mul]
Nat.cast_ne_zero.mpr
A natural number cast into a semiring is nonzero if the natural number itself is nonzero.
Finset.sum_comm
The order of summation in a finite double sum can be interchanged.
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑ i, f i = ∑ i, a * f i.
Finset.sum_congr
Two sums over equal finite sets are equal if their summands are pointwise equal on the set.
op_153_root_of_unity_orthogonality
The sum of the k-th powers of the M-th roots of unity over n = 0, ..., M-1 equals M if M divides k, and 0 otherwise.
Finset.sum_eq_single
A finite sum equals the value of the summand at a single point a, provided the summand vanishes at all other elements of the set and is zero if a is not in the set.
Int.natAbs_le_of_dvd_ne_zero
If an integer m divides a nonzero integer n, then the absolute value |m| is at most |n|.
mul_comm
Multiplication in a commutative magma is commutative: a * b = b * a.
mul_assoc
Multiplication in a semigroup is associative: (a * b) * c = a * (b * c).
one_div
Division of 1 by a equals the multiplicative inverse a⁻¹.
inv_mul_cancel₀
In a group with zero, multiplying a nonzero element on the left by its inverse yields 1: a⁻¹ * a = 1.
one_mul
Multiplying an element on the left by 1 leaves it unchanged: 1 * a = a.

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

/-- The zero-th Fourier coefficient of a finitely supported trigonometric polynomial is the average of its values at the M-th roots of unity, provided no nonzero frequency is a multiple of M. -/theorem op_153_fourier_mean_eq_constant_term (M : ℕ) (hM : 0 < M) (φ : ℤ → ℂ) (T : Finset ℤ)    (h0 : (0 : ℤ) ∈ T) (hlt : ∀ x ∈ T, x ≠ 0 → x.natAbs < M) :    (1 / (M : ℂ)) * (∑ n ∈ Finset.range M,        ∑ x ∈ T, φ x * Complex.exp (2 * Real.pi * Complex.I * (x : ℂ) * (n : ℂ) / (M : ℂ))) = φ 0 := by  have hMne : (M : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr hM.ne'  rw [Finset.sum_comm]  have hinner : ∀ x ∈ T, (∑ n ∈ Finset.range M, φ x * Complex.exp (2 * Real.pi * Complex.I * (x : ℂ) * (n : ℂ) / (M : ℂ)))      = φ x * (if (M : ℤ) ∣ x then (M : ℂ) else 0) := by    intro x hx    rw [← Finset.mul_sum]    congr 1    have hshift : (∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (x : ℂ) * (n : ℂ) / (M : ℂ)))        = ∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (x : ℂ) / (M : ℂ)) := by      apply Finset.sum_congr rfl      intro n hn      congr 1      ring    rw [hshift, op_153_root_of_unity_orthogonality M hM x]  rw [Finset.sum_congr rfl hinner]  have hsingle : (∑ x ∈ T, φ x * (if (M : ℤ) ∣ x then (M : ℂ) else 0)) = φ 0 * (M : ℂ) := by    rw [Finset.sum_eq_single (0 : ℤ)]    · simp    · intro b hb hb0      have hndvd : ¬ (M : ℤ) ∣ b := by        intro hdvd        have hle : (M : ℤ).natAbs ≤ b.natAbs := Int.natAbs_le_of_dvd_ne_zero hdvd hb0        have hMabs : (M : ℤ).natAbs = M := by simp        have := hlt b hb hb0        omega      simp [hndvd]    · intro h      exact absurd h0 h  rw [hsingle]  rw [mul_comm (φ 0) (M : ℂ), ← mul_assoc, one_div, inv_mul_cancel₀ hMne, one_mul]
See it in the graphDiscuss this resultChallenge it