A somewhat information theoretical paradox occurred to me, and I was wondering if anyone could resolve it.
Let $p(x) = x^n + c_{n-1} x^{n-1} + \cdots + c_0 = (x – r_0) \cdots (x – r_{n-1})$ be a degree $n$ polynomial with leading coefficient $1$. Clearly, the polynomial can be specified exactly by its $n$ coefficients $c=\{c_{n-1}, \ldots, c_0\}$ OR by its $n$ roots $r=\{r_{n-1}, \ldots, r_0\}$.
So the roots and the coefficients contain the same information. However, it takes less information to specify the roots, because their order doesn't matter. (i.e. the roots of the polynomial require $\lg(n!)$ bits less information to specify than the coefficients).
Isn't this a paradox? Or is my logic off somewhere?
Edit: To clarify, all values belong to any algebraically closed field (such as the complex numbers). And note that the leading coefficient is specified to be 1, meaning that there is absolutely a one-to-one correspondence between the $n$ remaining coefficients $c$ and the $n$ roots $r$.
Best Answer
What is happening here is just a consequence that an infinite set and a proper subset can be in bijective correspondence. That's an well known fact about infinite sets. And it is a paradox in the sense that it is anti-intuitive, but not in the sense that it leads to a contradiction.