We need a special pair of points such that at every point in the recursion we have positive-negative pairs. These are the roots of unity. The $n$-th roots of unity are simply the solutions to the equation $x^n = 1$. For example, the square roots of unity are the solutions to the equation $x^2 = 1$: $+1$ and $-1$. In the case where we need to evaluate at four points (two pairs of points: $\pm x_1$ and $\pm x_2$), we can choose the fourth roots of unity to obtain a pair of points at every step of the recursion.

The fourth roots of unity are $\left[ 1, -1, i, -i \right]$. In general, for the equation $x^n = 1$, there are $n$ distinct complex roots $[\omega^0, \omega^1, ..., \omega^{(n-1)}]$ where $$ \omega = e^{\frac{2\pi i}{n}} = \cos \left(\frac{2\pi}{n}\right) + i\sin\left(\frac{2\pi}{n}\right). $$ These points can be represented on a complex plane, with the roots on the unit circle equally spaced with an angle of $\frac{2\pi}{n}$, as depicted below.

For any polynomial of degree $d$, we choose $n \geq (d + 1)$ roots of unity so that the polynomial can be evaluated at these points. For the sake of convenience, since we keep halving the number of evaluations at every step of the FFT recursion, we choose $n$ to be a power of $2$. Let us now understand some properties of the roots of unity that are useful for Fourier transforms. --- ***Exercise F.1.3.*** (a) Prove that $\omega^0 + \omega^1 + ... + \omega^{(n-1)} = 0$.

Solution.

Geometrically, this just means adding up all the vectors in different directions, so it makes sense that they cancel out resulting in 0. To prove it analytically, we express this as a geometric series: $$ \begin{align*} 1 + \omega^1 + ... + \omega^{(n-1)} &= \frac{\omega^n -1}{\omega -1} &= 0 \end{align*} $$ since $\omega = e^{\frac{2\pi i}{n}}$ and $\omega^n = 1$.▢

--- (b) Prove that $$ \sum_{k=0}^{n-1} \omega^{xk} = 0, \label{sum_ji} \tag{1} $$ for $x \neq 0$.

Solution.

Expressing this as a geometric series we have, $$ \begin{align*} \sum_{k=0}^{n-1} \omega^{xk} &= 1 + \omega^x + \omega^{2x}... + \omega^{(n-1)x} \\ &= \frac{\omega^{xn} -1}{\omega^x -1} \\ &= 0 \end{align*} $$ since we know $\omega^n = 1$ ▢

--- We've discussed *selection* and *evaluation* so far. We chose the complex $n$-th roots of unity and evaluated polynomials at these points using the FFT algorithm. After this, *multiplication* of two polynomials in the value representation is straightforward: we just multiply each value of the polynomials element-wise, corresponding to the same roots of unity. The next step is to convert this *value* representation back to *coefficient* representation.

Codercise F.1.1 - Converting to value representation

Codercise F.1.2 - Coverting to coefficient representation

Codercise F.1.3 - The nearest power of 2

Codercise F.1.4 - Multiplying polynomials

How difficult is it to multiply polynomials?

Can we do better?

Divide and conquer

The roots of unity

Interpolation

The DFT matrix and its inverse

Step by step