op_153_root_of_unity_orthogonality
For 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.
Statement
theorem op_153_root_of_unity_orthogonality (M : ℕ) (hM : 0 < M) (k : ℤ) : (∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (k : ℂ) / (M : ℂ))) = if (M : ℤ) ∣ k then (M : ℂ) else 0
- Source
- step towards op_153_eventually_subexp_bound_positive_quadratic
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- 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…
- op_153_fourier_mean_eq_constant_termFor 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…
The proof, explained
The proof rewrites the sum as a geometric series $\sum_{n=0}^{M-1} w^n$ with ratio $w = \exp(2\pi i k / M)$, which satisfies $w^M = 1$. It proves that $w = 1$ if and only if $M \mid k$. It then splits into two cases: if $M \mid k$, then $w = 1$ and the sum adds $1$ exactly $M$ times to give $M$; if $M \nmid k$, then $w \neq 1$ and the geometric sum formula yields $(w^M - 1)/(w - 1) = 0$.
The original sum rewrites as the geometric sum $\sum_{n=0}^{M-1} w^n$, where $w = \exp(2\pi i k / M)$.
Since $M > 0$, its image in $\mathbb{C}$ is nonzero (`Nat.cast_ne_zero.mpr`, `ne_of_gt`). Setting $w = \exp(2\pi i k / M)$, each summand $\exp(2\pi i n k / M)$ simplifies to $w^n$ by the power rule for the complex exponential (`Complex.exp_nat_mul`) and algebraic rearrangement of the exponent. Summing term-by-term (`Finset.sum_congr`) turns the sum into $\sum_{n=0}^{M-1} w^n$.
uses
Nat.cast_ne_zero.mpr,ne_of_gt,Complex.exp_nat_mul,Finset.sum_congrhave hM_c : (M : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr (ne_of_gt hM) set w : ℂ := Complex.exp (2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ)) with hw_def have h_term (n : ℕ) : Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (k : ℂ) / (M : ℂ)) = w ^ n := by rw [hw_def, ← Complex.exp_nat_mul] congr 1 ring have h_sum : (∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (k : ℂ) / (M : ℂ))) = ∑ n ∈ Finset.range M, w ^ n := by apply Finset.sum_congr rfl intro n _ exact h_term n rw [h_sum]
$w^M = 1$, so $w$ is an $M$-th root of unity.
Raising $w$ to the power $M$ multiplies the exponent by $M$ (`Complex.exp_nat_mul`). Associating multiplication and division (`mul_div_assoc'`) and cancelling the nonzero factor $M$ in the denominator (`mul_div_cancel_right₀`) reduces the exponent to $2\pi i k$. Since the complex exponential equals $1$ precisely at integer multiples of $2\pi i$ (`Complex.exp_eq_one_iff`), $w^M = 1$.
uses
Complex.exp_nat_mul,mul_div_assoc',mul_div_cancel_right₀,Complex.exp_eq_one_iffhave hwM : w ^ M = 1 := by rw [hw_def, ← Complex.exp_nat_mul] have h_mul : (M : ℂ) * (2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ)) = (k : ℂ) * (2 * Real.pi * Complex.I) := by calc (M : ℂ) * (2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ)) _ = (M : ℂ) * (2 * Real.pi * Complex.I * (k : ℂ)) / (M : ℂ) := mul_div_assoc' (M : ℂ) _ _ _ = (2 * Real.pi * Complex.I * (k : ℂ)) * (M : ℂ) / (M : ℂ) := by ring_nf _ = (2 * Real.pi * Complex.I * (k : ℂ)) := mul_div_cancel_right₀ _ hM_c _ = (k : ℂ) * (2 * Real.pi * Complex.I) := by ring rw [h_mul, Complex.exp_eq_one_iff] exact ⟨k, rfl⟩
$w = 1$ if and only if $M \mid k$ in $\mathbb{Z}$.
By `Complex.exp_eq_one_iff`, $w = 1$ holds if and only if $(2\pi i k)/M = 2\pi i m$ for some integer $m$. In the forward direction, cancelling the nonzero factor $2\pi i$ (`Complex.two_pi_I_ne_zero`, `mul_left_cancel₀`) yields $k / M = m$, and multiplying by $M$ (`div_mul_cancel₀`) gives $k = m M = M m$ (`mul_comm`), which casts to the integers to show $M \mid k$. In the reverse direction, if $k = M m$, cancelling $M$ (`mul_div_cancel_left₀`) directly shows the exponent is $2\pi i m$, whence $w = 1$.
uses
Complex.exp_eq_one_iff,Complex.two_pi_I_ne_zero,mul_left_cancel₀,div_mul_cancel₀,mul_comm,mul_div_cancel_left₀have hw_iff : w = 1 ↔ (M : ℤ) ∣ k := by rw [hw_def, Complex.exp_eq_one_iff] constructor · rintro ⟨m, hm⟩ have hm2 : (2 * Real.pi * Complex.I) * ((k : ℂ) / (M : ℂ)) = (2 * Real.pi * Complex.I) * (m : ℂ) := by calc (2 * Real.pi * Complex.I) * ((k : ℂ) / (M : ℂ)) _ = 2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ) := by ring _ = (m : ℂ) * (2 * Real.pi * Complex.I) := hm _ = (2 * Real.pi * Complex.I) * (m : ℂ) := by ring have hm3 := mul_left_cancel₀ Complex.two_pi_I_ne_zero hm2 have hm4 : (k : ℂ) = (m : ℂ) * (M : ℂ) := by calc (k : ℂ) = ((k : ℂ) / (M : ℂ)) * (M : ℂ) := by rw [div_mul_cancel₀ (k : ℂ) hM_c] _ = (m : ℂ) * (M : ℂ) := by rw [hm3] have hm5 : (k : ℂ) = ((m * (M : ℤ) : ℤ) : ℂ) := by push_cast exact hm4 have hm6 : k = m * (M : ℤ) := by exact_mod_cast hm5 exact ⟨m, by rw [hm6, mul_comm]⟩ · rintro ⟨m, rfl⟩ use m push_cast have : (M : ℂ) * (m : ℂ) / (M : ℂ) = (m : ℂ) := by rw [mul_div_cancel_left₀ (m : ℂ) hM_c] calc 2 * Real.pi * Complex.I * ((M : ℂ) * (m : ℂ)) / (M : ℂ) _ = (2 * Real.pi * Complex.I) * ((M : ℂ) * (m : ℂ) / (M : ℂ)) := by ring _ = (2 * Real.pi * Complex.I) * (m : ℂ) := by rw [this] _ = (m : ℂ) * (2 * Real.pi * Complex.I) := by ring
If $M \mid k$, the sum evaluates to $M$.
When $M \mid k$, the conditional chooses the positive branch (`if_pos`). The characterization gives $w = 1$, so every term in the sum is $1^n = 1$, and summing $1$ over the $M$ terms yields $M$.
uses
if_posby_cases h : (M : ℤ) ∣ k · rw [if_pos h] have hw1 : w = 1 := hw_iff.mpr h rw [hw1] simp
If $M \nmid k$, the sum evaluates to $0$.
When $M \nmid k$, the conditional chooses the negative branch (`if_neg`). By contraposition (`mt`), $w \neq 1$. Applying the finite geometric series summation formula (`geom_sum_eq`), the sum equals $(w^M - 1) / (w - 1)$. Since $w^M = 1$, the numerator is $1 - 1 = 0$ (`sub_self`), and dividing zero by $w - 1$ gives $0$ (`zero_div`).
uses
if_neg,mt,geom_sum_eq,sub_self,zero_div· rw [if_neg h] have hw_ne1 : w ≠ 1 := mt hw_iff.mp h rw [geom_sum_eq hw_ne1 M, hwM, sub_self, zero_div]
Nat.cast_ne_zero.mpr- A natural number that is nonzero remains nonzero when cast to a semiring such as $\mathbb{C}$.
ne_of_gt- If $b < a$, then $a \neq b$.
Complex.exp_nat_mul- For any complex number $x$ and natural number $n$, $\exp(n x) = (\exp x)^n$.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element.
mul_div_assoc'- In a group with division, $a (b / c) = (a b) / c$.
mul_div_cancel_right₀- In a monoid with zero, $(a \cdot b) / b = a$ whenever $b \neq 0$.
Complex.exp_eq_one_iff- For any complex number $x$, $\exp(x) = 1$ if and only if $x = 2\pi i n$ for some integer $n$.
Complex.two_pi_I_ne_zero- The complex number $2\pi i$ is nonzero.
mul_left_cancel₀- If $a \neq 0$ and $a b = a c$, then $b = c$.
div_mul_cancel₀- In a group with zero, $(a / b) \cdot b = a$ whenever $b \neq 0$.
mul_comm- Multiplication is commutative: $a b = b a$.
mul_div_cancel_left₀- In a commutative monoid with zero, $(a \cdot b) / a = b$ whenever $a \neq 0$.
if_pos- If a proposition $c$ holds, then $\text{if } c \text{ then } t \text{ else } e = t$.
if_neg- If a proposition $c$ is false, then $\text{if } c \text{ then } t \text{ else } e = e$.
mt- By contraposition (modus tollens), $(a \implies b) \implies (\neg b \implies \neg a)$.
geom_sum_eq- For any element $x \neq 1$ in a division ring, $\sum_{i=0}^{n-1} x^i = (x^n - 1) / (x - 1)$.
sub_self- In any additive group, $a - a = 0$.
zero_div- In a group with zero, $0 / a = 0$.
- Translating the equality $k / M = m$ from $\mathbb{C}$ back to the divisibility $M \mid k$ in $\mathbb{Z}$ requires explicit casts between the integers and complex numbers (`push_cast`, `exact_mod_cast`).
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.
/-- Root-of-unity orthogonality in the finite cyclic group of order M: \u03a3_{n<M} e(nk/M) = M when M \u2223 k and 0 otherwise. -/theorem op_153_root_of_unity_orthogonality (M : ℕ) (hM : 0 < M) (k : ℤ) : (∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (k : ℂ) / (M : ℂ))) = if (M : ℤ) ∣ k then (M : ℂ) else 0 := by have hM_c : (M : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr (ne_of_gt hM) set w : ℂ := Complex.exp (2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ)) with hw_def have h_term (n : ℕ) : Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (k : ℂ) / (M : ℂ)) = w ^ n := by rw [hw_def, ← Complex.exp_nat_mul] congr 1 ring have h_sum : (∑ n ∈ Finset.range M, Complex.exp (2 * Real.pi * Complex.I * (n : ℂ) * (k : ℂ) / (M : ℂ))) = ∑ n ∈ Finset.range M, w ^ n := by apply Finset.sum_congr rfl intro n _ exact h_term n rw [h_sum] have hwM : w ^ M = 1 := by rw [hw_def, ← Complex.exp_nat_mul] have h_mul : (M : ℂ) * (2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ)) = (k : ℂ) * (2 * Real.pi * Complex.I) := by calc (M : ℂ) * (2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ)) _ = (M : ℂ) * (2 * Real.pi * Complex.I * (k : ℂ)) / (M : ℂ) := mul_div_assoc' (M : ℂ) _ _ _ = (2 * Real.pi * Complex.I * (k : ℂ)) * (M : ℂ) / (M : ℂ) := by ring_nf _ = (2 * Real.pi * Complex.I * (k : ℂ)) := mul_div_cancel_right₀ _ hM_c _ = (k : ℂ) * (2 * Real.pi * Complex.I) := by ring rw [h_mul, Complex.exp_eq_one_iff] exact ⟨k, rfl⟩ have hw_iff : w = 1 ↔ (M : ℤ) ∣ k := by rw [hw_def, Complex.exp_eq_one_iff] constructor · rintro ⟨m, hm⟩ have hm2 : (2 * Real.pi * Complex.I) * ((k : ℂ) / (M : ℂ)) = (2 * Real.pi * Complex.I) * (m : ℂ) := by calc (2 * Real.pi * Complex.I) * ((k : ℂ) / (M : ℂ)) _ = 2 * Real.pi * Complex.I * (k : ℂ) / (M : ℂ) := by ring _ = (m : ℂ) * (2 * Real.pi * Complex.I) := hm _ = (2 * Real.pi * Complex.I) * (m : ℂ) := by ring have hm3 := mul_left_cancel₀ Complex.two_pi_I_ne_zero hm2 have hm4 : (k : ℂ) = (m : ℂ) * (M : ℂ) := by calc (k : ℂ) = ((k : ℂ) / (M : ℂ)) * (M : ℂ) := by rw [div_mul_cancel₀ (k : ℂ) hM_c] _ = (m : ℂ) * (M : ℂ) := by rw [hm3] have hm5 : (k : ℂ) = ((m * (M : ℤ) : ℤ) : ℂ) := by push_cast exact hm4 have hm6 : k = m * (M : ℤ) := by exact_mod_cast hm5 exact ⟨m, by rw [hm6, mul_comm]⟩ · rintro ⟨m, rfl⟩ use m push_cast have : (M : ℂ) * (m : ℂ) / (M : ℂ) = (m : ℂ) := by rw [mul_div_cancel_left₀ (m : ℂ) hM_c] calc 2 * Real.pi * Complex.I * ((M : ℂ) * (m : ℂ)) / (M : ℂ) _ = (2 * Real.pi * Complex.I) * ((M : ℂ) * (m : ℂ) / (M : ℂ)) := by ring _ = (2 * Real.pi * Complex.I) * (m : ℂ) := by rw [this] _ = (m : ℂ) * (2 * Real.pi * Complex.I) := by ring by_cases h : (M : ℤ) ∣ k · rw [if_pos h] have hw1 : w = 1 := hw_iff.mpr h rw [hw1] simp · rw [if_neg h] have hw_ne1 : w ≠ 1 := mt hw_iff.mp h rw [geom_sum_eq hw_ne1 M, hwM, sub_self, zero_div]