AFTD Auto-Formalizing Theoretical Domains

op_153_root_of_unity_orthogonality

theoremverified

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$.

  1. 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$.

    lines 5–17

    uses Nat.cast_ne_zero.mpr, ne_of_gt, Complex.exp_nat_mul, Finset.sum_congr

      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]
  2. $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$.

    lines 18–27

    uses Complex.exp_nat_mul, mul_div_assoc', mul_div_cancel_right₀, Complex.exp_eq_one_iff

      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⟩
  3. $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$.

    lines 28–55

    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
  4. 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$.

    lines 56–60

    uses if_pos

      by_cases h : (M : ℤ) ∣ k
      · rw [if_pos h]
        have hw1 : w = 1 := hw_iff.mpr h
        rw [hw1]
        simp
  5. 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`).

    lines 61–63

    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$.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it