Intuition for why the fourier tranform of a polynomial is its pointwise evaluation?

Question

Polynomials in coefficient representation can be multiplied in $O(n \, log \,n)$ time by using a fast fourier transform to convolute the coefficients. The DFT of the coefficients correspond to the evaluation at the complex roots of unity. Is there an Intuition to this fact? I have previously only known fourier transforms as transforming a signal from the time domain to the frequency domain, so this connection is very strange to me.

Answer 1

Let

$$ p(x) = \sum_{n=0}^{N} a_n x^n. $$

Now consider setting $x$ to each of the $N$ complex roots of unity. For $x=\exp\left({j2\pi/N\cdot 0}\right)$, we get

$$ p(e^{j2\pi/N\cdot 0}) = \sum_{n=0}^{N} a_n \left( e^{j2\pi/N\cdot 0 } \right)^n. $$

For $x=\exp\left({j2\pi/N\cdot 1}\right)$, we get

$$ p(e^{j2\pi/N\cdot 1}) = \sum_{n=0}^{N} a_n \left( e^{j2\pi/N\cdot 1 } \right)^n. $$

In general, the polynomial evaluated at the $m^\mathrm{th}$ complex root of unity is

$$ p(e^{j2\pi/N\cdot m}) = \sum_{n=0}^{N} a_n \left( e^{j2\pi/N\cdot m } \right)^n = \sum_{n=0}^{N} a_n e^{j2\pi n m /N } $$

Note that the right hand side of this is the definition of the DFT of the sequence $a_n$.