39
$\begingroup$

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

$\endgroup$
15
  • 3
    $\begingroup$ the point that you forgot in here is you must also include leading coefficient $a$ to roots.It will create uncertainity if you do not.For example both $2(x-2)(x-1)$ and $(x-2)(x-1)$ have same roots but they are not same polynomial. When you try to express this 2 polynomial with your "root" method you will get same result which is wrong $\endgroup$ – Nevzat Eren Akkaya Mar 10 at 8:31
  • 2
    $\begingroup$ The number of bits required to specify a root or a coefficient is a complicated sort of a thing. Are you requiring one or the other to be an integer? To be bounded? I think you'd need to specify what the domain of each set was quite carefully before saying that you could specify one set with fewer bits than the other. $\endgroup$ – Blitzer Mar 10 at 8:36
  • 1
    $\begingroup$ Interesting responses. I think there is a legitimate paradox, re [1] you can specify the constraint of leftmost coefficient $= 1$, and still preserve the paradox [2] While Coefficients are a by-product of roots, you can for example specify $\mathbb{C}$ as the field that supplies both the coefficients and the roots. Then, roots are also a by-product of the coefficients. Finally, the number of bits required for computer storage is not the issue. Instead, the issue is that the polynomial+roots can be completely determined either by $n$ ordered coefficients, or $n$ unordered roots. $\endgroup$ – user2661923 Mar 10 at 9:04
  • 2
    $\begingroup$ @NevzatErenAkkaya Your argument does not work because the polynomials in question are monic. $\endgroup$ – user Mar 10 at 9:29
  • 2
    $\begingroup$ We can represent integers as: unordered lists of factors, ordered lists of digits. $\endgroup$ – Vepir Mar 10 at 9:34
22
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Ultimately, I think this is prolly all it is. Thanks! $\endgroup$ – chausies Mar 10 at 11:32
  • 1
    $\begingroup$ @user We are not dealing with a single polynomial, but with all of them. $\endgroup$ – jjagmath Mar 10 at 11:57
  • 4
    $\begingroup$ @user That is correct. But the amount of information to specify a single polynomial is dependent upon the size of all polynomials under consideration. For example if we have a set $S$ of only 4 polynomials, then a single number 0, 1, 2 or 3 is sufficient to specify the polynomial. A larger set will require more information. The basic idea is that there are many different ways to specify a polynomial, e.g. indexing them (as with $S$), ordered n-tuples via their coefficients, or unordered multisets via their roots. $\endgroup$ – Matt Mar 10 at 16:28
  • 4
    $\begingroup$ @Matt Such an explanation I would expect to be present in the answer. $\endgroup$ – user Mar 10 at 16:42
  • 3
    $\begingroup$ Sorry for the negative vibes, but I disagree with this answer being the most upvoted one. IMO The complexity of this problem lies not in realizing that the pigeonhole principle fails for infinite sets, but in realizing how this relates to polynomials and their roots. The answer does not adress this one bit. Just briefly, but explicitly, mentioning what the subset or function in question is would have improved this answer substantially. $\endgroup$ – Lukas Juhrich Mar 10 at 21:48
16
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ For anyone missing the obvious like me, the map Adam talks about to is $(r_1, \ldots, r_n)\mapsto$ coefficients of $(x-r_1)\cdots (x-r_n)$. $\endgroup$ – Lukas Juhrich Mar 10 at 21:52
  • $\begingroup$ I think this is equivalent to saying that each allowable ordering is a separate representation, rather than there being a single "unordered roots" representation. $\endgroup$ – Kevin P. Barry Mar 12 at 5:47
2
$\begingroup$

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 .

$\endgroup$
1
  • $\begingroup$ For part 2, I like to use the language of multiset: $\{ \rho_1^{k_1}, \ldots, \rho_m^{k_m} \}$. $\endgroup$ – Sammy Black Mar 16 at 20:35
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.