Paradox: Roots of a polynomial require less information to express than coefficients?

Question

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

Answer 1

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.

Answer 2

The ordering of the roots doesn't give you any new information about the polynomial. You have a map $$ {\mathbb C}^n \ni (r_1,r_2,\dots r_n) \mapsto (c_0,c_1\dots c_{n-1}) \in \mathbb{C}^n$$ This map is surjective, but not injective. That kind of things may happen because $\mathbb{C}^n$ is an infinte set. It is also true for other algebraically closed fields - no algebraically closed field is finite.

Answer 3

The core of your paradox seems to be that you claim that in some sense there are "more" (ordered) tuples $(c_{n-1},\dots,c_0)$ than (unordered) sets $\{r_{n-1},\dots,r_0\}$. This is not true for infinite sets like $\mathbb C$, only for finite sets, and even then it would not be significant for your problem as will be seen below.

In the sequel we only consider polynomials having leading coefficient $1$ to avoid a "trival non-uniqueness".

1. It is in general not true that the set $R(p)$ of roots of a polynomial $p = p(x)$ allows to reconstruct $p$. Note that $R(p)$ is nothing else than a set and does not contain information about the multiplicity of the roots. The number $m(p)$ of elements of $R(p)$ may be anything between $1$ and $n = \deg(p)$, i.e. we have $1 \le m(p) \le n$. [Note that for $\deg(p) = 0$ this says that the set $R(p)$ is empty.] The notation $R(p) = \{r_{n-1},\dots,r_0\}$ is misleading since it suggests that the set $R(p)$ has $n$-elements. Instead we have $R(p) = \{ \rho_1, \dots, \rho_{m(p)}\}$ with $\rho_i \ne \rho_j$ for $i \ne j$.
   Therefore the problem is this: To each ordered tuple $\tau = (c_{n-1},\dots,c_0)$ of finite length we can associate a unique polynomial $p_\tau$ having the $c_i$ as coefficients, but to a finite set $R$ we can associate infinitely many polynomials having $R$ as a root set. There is exactly one such polynomial with minimal degree (in which each $\rho \in R$ occurs with multiplicity $1$, i.e.the degree equals the number of elements of $R$), but if we associate it to $R$, we do not get all polynomials having $R(p) = R$. The only exception is $R =\emptyset$; in that case $p(x) = 1$.

2. What we really need to consider is the set of pairs $\{ (\rho_1,k_1) \dots, (\rho_m,k_m) \}$ where $k_i \ge 1$ is the multiplicity of the root $\rho_i$. Then we get a unique polynomial $p$ of degree $n = \sum k_i$ such that $R(p) = \{ \rho_1, \dots, \rho_{m(p)}\}$.
   Alternatively we can consider $\mathbb C^n/\mathfrak S_n$, the quotient of $\mathbb C^n$ by the operation of the symmetric group of $n$ elements. That is, tupels are identified if they are related by permuting their components. One might be tempted to think of the elements of $\mathbb C^n/\mathfrak S_n$ as simple (unordered) sets, but it is not true. In fact, $\mathbb C^n/\mathfrak S_n$ can be identified with the collection of pairs $\{ (\rho_1,k_1) \dots, (\rho_m,k_m) \}$ with $k_i \ge 1$ and $n = \sum k_i$.

See also How to show symmetric product of complex space is homeomorphic to the complex space .

Answer 4

There is no paradox.

You cannot reason with real coefficients, because they convey infinite information and you can add them extra bits at no cost. You have to reason with coefficients having a finite representation, hence a finite number of polynomials. Let $p$ this number.

The information content of a polynomial chosen among $p$ is not the total number of bits of the coefficients, but just $\lg(p)$, assuming equiprobable polynomials.

There is only one way to produce the roots in sorted order, then this yields $\lg(p)$ bits of information again. If you enforce a specific order, you increase the amount of information by $\lg(n!)$. So supplying the roots as a tuple in fact takes more information than as a set.

Answer 5

I do not think any of the current answers actually address the question. So, let me add my two cents.

The keyword is Commutativity. It kills the information of the order of multiplication: $$ab=ba.$$ The field of complex numbers $\mathbb{C}$ has this property over multiplication. The coefficients $\{c_{n-1}, c_{n-2}, \cdots, c_0\}$ are elementary symmetric polynomials of the roots. Over a field, elementary symmetric functions are not sensitive to the order of variables.

However, the situation will drastically change in a (multiplicative) non-commutative setting, such as square matrices or quaternions. The first thing is distributive laws. See answers in here and here for some extreme cases. To continue our discussion let's suppose both distributive laws hold. In that situation, you can unambiguously write $$(x-a)(x-b)=x^2-ax-xb+ab$$ and clearly, this is different from $(x-b)(x-a)=x^2-xa-bx+ba$ for $a\neq b.$
Now, as you can see both sides contain the same amount of information, i.e., both zeros $a, b$ and the order in the factors appear.