What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

Question

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was:

Evaluate the following polynomial at all roots of unity of order 32 and see how many distinct values are obtained:

$x^{16} + 8x^8 + 1$

My guess would be that there are 16 distinct values (since, from what I can remember, a polynomial of degree n will have n distinct complex roots)? But I'm unsure how to actually evaluate these values. I am used to seeing things in terms of a single complex number in polar or exponential form, e.g., $e^{i\theta}$ then evaluating it at $e^{(i\theta \pi k)/n}$ for $k \in \{0..n-1\}$.

How do I evaluate the polynomial? What might be the significance of the result?

Answer 1

No there are only 4 values. The 32th roots of unity are $e^{\frac{2\pi i k}{32}}, k=0\dots 31$ and the values of the polynom $f(x) = x^{16} + 8x^8 + 1\,$at those roots are $$f(e^{\frac{\pi i k}{16}}) = (e^{\frac{\pi i k}{16}})^{16}+8(e^{\frac{\pi i k}{16}})^{8}+1 =e^{\pi i k}+8e^{\frac{\pi i k}{2}}+1 = (-1)^k+8i^k+1 $$ And these values are $10, 8i, -6, -8i, 10, 8i, -6, -8i, \dots\;$

Answer 2

The roots of unity you are dealing with satisfy:$$0=x^{32}-1=(x^{16}+1)(x^{16}-1)=(x^{16}+1)(x^8+1)(x^8-1)$$

So they are of three kinds $x^8=1$, $x^8=-1$, $x^{16}=-1$

Note that if $x^{16}=-1$ then $x^8=\pm i$

Note also that the polynomial you are asked to evaluate is a polynomial in $x^8$ and $32=4\cdot 8$ so you expect some simplification to express the values of the equation in terms of fourth roots of unity.