op_153_fourier_mean_eq_constant_term
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
- op_153_root_of_unity_orthogonalityFor M > 0 and any integer k, the sum of exp(2*pi*I*n*k/M) over n = 0, 1, ..., M-1 equals M if M divides k and 0 otherwise.
- 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).
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.
uses
Nat.cast_ne_zero.mpr,Finset.sum_commhave hMne : (M : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr hM.ne' rw [Finset.sum_comm]
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.
uses
Finset.mul_sum,Finset.sum_congr,op_153_root_of_unity_orthogonalityhave 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]
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.
uses
Finset.sum_eq_single,Int.natAbs_le_of_dvd_ne_zerohave 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
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).
uses
mul_comm,mul_assoc,one_div,inv_mul_cancel₀,one_mulrw [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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]