__Fast Fourier Transform__

__For: Faster polynomial multiplication in \( O(N\lg{N}) \) time using a divide and conquer strategy, which makes us of a technique called polynomial interpolation, and a fact about the root of unity.__

__1. Polynomial Interpolation:__

A polynomial \(P(x)\) of degree \(n\) can be represented by choosing \(n\) distinct point on the curve \(P(x)\). In other words, \(P(x)\) can be constructed back solely by using \(n\) points \((x_0,y_0),(x_1,y_1),\ldots,(x_{n-1},y_{n-1})\) where \(y_k = P(x_k)\).

Proof that \(P(x)\) constructed will be unique: Examine the Vandermonde matrix and its especially cool determinant to derive at the proof.

__2. Root of unity__

Given \(x^n = 1\), there is a complex number \(w\) the root of unity such that \(w = e^{\frac{2\pi k}{n}} \) for \(k = 0,1,2,3,\ldots,n-1\). Then further we have the Cancellation Lemma: \(w_{in}^{ik} = w_{n}^{k} \) (direct substitution proof). In particular we have the Halving Lemma: \( (w_{n}^{2k+\frac{n}{2}})^2 = (w_{n}^{2k})^2\) (Proof also by direct substitution and making use of the previous relationship).

__3. FFT__

A polynomial can be partitioned based on even-odd parity of its coefficient index:

\(P(x) = a_0+a_1x+a_2x^2+\ldots + a_{n-1}x^{n-1} \)

\(P(x) = A(x^2) + xB(x^2)\)

where

\(A(x) = a_0+a_2x+a_4x^2+\ldots \) (even indexed coefficients)

\(B(x) = a_1+a_3x+a_5x^2+\ldots \) (odd indexed coefficients)

Therefore we end up with a recursive relationship: to interpolate P(x), we can recursively interpolate A(x) and B(x) and combine its result in \(O(N)\) thanks to the Cancellation Lemma and the Halving Lemma which gives rise to a convenient relationship between P and the results from A and B.

4. Pseudo-code:

rec_FFT( polynomial P ): (return interpolated P)

set n = deg(P)

if n == 1:

return P

set w_k = 1

set w = \(e^{\frac{2\pi}{n}}\) (first root of unity)

set A = polynomial from even coefficient of P

set B = polynomial from odd coefficient of P

a[] = rec_FFT( A )

b[] = rec_FFT( B )

for i = 0 to floor(n/2):

p[i] = a[i] + w_k * b[i]

p[i + n/2] = a[i] - w_k * b[i]

w_k = w * w_k

return p