2.2 Roots of unity and discrete Fourier analysis

The \(N\)-th roots of unity are the solutions to \(z^N = 1\) in \(\mathbb {C}\):

\begin{equation} \omega _k = \mathrm{e}^{2\pi i k/N}, \quad k = 0, 1, \ldots , N-1. \end{equation}

These form a cyclic group under multiplication, isomorphic to \(\mathbb {Z}/N\mathbb {Z}\). A primitive \(N\)-th root of unity is one that generates the cyclic group of all \(N\)-th roots under multiplication; \(\omega = \mathrm{e}^{2\pi i/N}\) is primitive, and \(\omega _k = \omega ^k\).

Geometrically, the \(N\)-th roots of unity are equally-spaced points on the unit circle in the complex plane, with angular separation \(2\pi /N\). Their symmetry under rotation by \(2\pi /N\) is the source of all discrete orthogonality relations we exploit.

The fundamental orthogonality relation is:

Lemma 2.2.1 Discrete orthogonality

✓

For any integer \(m\),

\begin{equation} \sum _{k=0}^{N-1} \mathrm{e}^{2\pi i m k/N} = \begin{cases} N & \text{if } N \mid m, \\ 0 & \text{otherwise.} \end{cases} \end{equation}

(See ../docs/ChebyshevCircles/Proofs/ChebyshevOrthogonality.htmlAPI Documentation | ../paper/chebyshev_circles.pdfPaper Lemma 2.2)

Proof ▶

If \(N \mid m\), then \(\mathrm{e}^{2\pi i m k/N} = 1\) for all \(k\), so the sum equals \(N\).

If \(N \nmid m\), let \(\omega = \mathrm{e}^{2\pi i m/N} \neq 1\). Then the sum is a geometric series:

\begin{equation} \sum _{k=0}^{N-1} \omega ^k = \frac{\omega ^N - 1}{\omega - 1} = \frac{1 - 1}{\omega - 1} = 0, \end{equation}

since \(\omega ^N = \mathrm{e}^{2\pi i m} = 1\).

This lemma is the discrete analog of the orthogonality relation for continuous exponentials:

\begin{equation} \frac{1}{2\pi }\int _0^{2\pi } \mathrm{e}^{i m \theta } \, d\theta = \begin{cases} 1 & \text{if } m = 0, \\ 0 & \text{otherwise.} \end{cases} \end{equation}

The discrete sum with \(N\) terms approximates the integral as \(N \to \infty \), providing a bridge between discrete and continuous Fourier analysis.