Paradoja: ¿Las raíces de un polinomio requieren menos información para expresarse que los coeficientes?

Question

Se me ha ocurrido una paradoja teórica un tanto informativa y me preguntaba si alguien podría resolverla.

Sea $p(x) = x^n + c_{n-1} x^{n-1} + \cdots + c_0 = (x - r_0) \cdots (x - r_{n-1})$ ser un grado $n$ polinomio con coeficiente principal $1$ . Claramente, el polinomio se puede especificar exactamente por su $n$ coeficientes $c=\{c_{n-1}, \ldots, c_0\}$ O por su $n$ raíces $r=\{r_{n-1}, \ldots, r_0\}$ .

Por tanto, las raíces y los coeficientes contienen la misma información. Sin embargo, se necesita menos información para especificar las raíces, porque sus el orden no importa . (es decir, las raíces del polinomio requieren $\lg(n!)$ bits menos de información que especificar que los coeficientes).

¿No es una paradoja? ¿O mi lógica no funciona?

Edición: Para aclarar, todos los valores pertenecen a cualquier campo algebraicamente cerrado (como los números complejos). Y tenga en cuenta que el coeficiente principal se especifica para ser 1, lo que significa que no hay absolutamente una correspondencia uno a uno entre el $n$ coeficientes restantes $c$ y el $n$ raíces $r$ .

Answer 1

Lo que ocurre aquí es sólo una consecuencia de que un conjunto infinito y un subconjunto propio pueden estar en correspondencia biyectiva. Es un hecho bien conocido sobre los conjuntos infinitos. Y es una paradoja en el sentido de que es antiintuitiva, pero no en el sentido de que lleve a una contradicción.

Answer 2

La ordenación de las raíces no aporta ninguna información nueva sobre el polinomio. Tienes un mapa $$ {\mathbb C}^n \ni (r_1,r_2,\dots r_n) \mapsto (c_0,c_1\dots c_{n-1}) \in \mathbb{C}^n$$ Este mapa es suryectivo, pero no inyectivo. Esto puede ocurrir porque $\mathbb{C}^n$ es un conjunto infinito. También es cierto para otros campos algebraicamente cerrados - ningún campo algebraicamente cerrado es finito .

Answer 3

No hay paradoja.

No se puede razonar con coeficientes reales, porque transmiten información infinita y se les pueden añadir bits adicionales sin coste alguno. Hay que razonar con coeficientes que tengan una representación finita, es decir, un número finito de polinomios. Sea $p$ este número.

El contenido informativo de un polinomio elegido entre $p$ no es el número total de bits de los coeficientes, sino sólo $\lg(p)$ suponiendo polinomios equiprobables.

Sólo hay una manera de producir las raíces en orden ordenado, entonces esto produce $\lg(p)$ bits de información de nuevo. Si impone un orden específico, aumenta la cantidad de información en $\lg(n!)$ . Por tanto, proporcionar las raíces como tupla requiere más información que como conjunto.