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

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.

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

• I think in the last equality, in the middle part, you forgot to write the "power to n". Jan 12 at 6:32