Cambiar los signos de los coeficientes de un polinomio para hacer que todas las raíces sean reales

Question

Se nos da un polinomio$$P_n(x):=a_nx^n + a_{n-1}x^{n-1}+\cdots+a_1x+a_0 con coeficientes reales.

Preguntas

$\boldsymbol{(i)}$ ¿Cómo podemos determinar si hay$\epsilon_1,\ldots,\epsilon_n\in\{-1,+1\}$ de modo que$$P_n(x;\pmb{\epsilon}):=\epsilon_n a_nx^n + \epsilon_{n-1} a_{n-1}x^{n-1}+\cdots+\epsilon_1 a_1x+a_0 solo tenga raíces reales? Aquí $\pmb{\epsilon}=(\epsilon_1,\dots,\epsilon_n)$.

$\boldsymbol{(ii)}$ Si hay una solución, ¿cómo podemos encontrarla?

Obviamente, una búsqueda exhaustiva es irremediablemente lenta. Esta pregunta podría posiblemente (en un buen día) ser relevante para un problema en polinomios de grafos.

Answer 1

Al menos en principio, una solución es el siguiente resultado, debido a J. Sylvester:

Teorema (Sylvester). Para cada número natural $n \geq 2$ existe un conjunto de más de $n-1$ polinomios con coeficientes enteros $$R_{n, \, 1}(X_1, \ldots, X_n), \ldots, R_{n, \, k(n)}(X_1, \ldots, X_n)$$ tal que el monic real de los polinomios de grado $n$ $$P(x)=x^n+a_{1}x^{n-1}+ \cdots + a_n$$ tener sólo las raíces reales son precisamente aquellos para los que $$R_{n, \, 1}(a_1, \ldots, a_n) \geq 0, \ldots, R_{n, \, k(n)}(a_1, \ldots, a_n) \geq 0.$$

Esto puede ser visto como una generalización del hecho bien conocido de que un verdadero cuadrática monic polinomio $x^2+a_1x+a_2$ sólo tiene raíces reales si y solo si su discriminante $$D_2(1, \, a_1, \, a_2)=a_1^2-4 a_2$$ es no negativo. De hecho, para todos los enteros positivos $n$ tenemos $$R_{n, \, 1}(a_1, \ldots, a_n) = D_n(1, \, a_1, \ldots, a_n),$$ donde $D_n$ es el discriminante de $P(x)$, mientras que los otros polinomios $R_{n, \,i}$ puede ser explícitamente calculada en términos de determinantes extraído de la matriz de Sylvester $P$ e $P'$.

Así, con el fin de responder a su pregunta, se debe verificar si $$R_{n, \, 1}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0, \ldots, R_{n, \, k(n)}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0$$ para algunos la elección de $\epsilon_1, \ldots, \epsilon_n \in \{-1, \, 1 \}.$ Desde el punto de vista computacional, el problema es que el número de no-cero de los coeficientes en nuestro polinomios aumenta rápidamente con el grado: por ejemplo, $R_{9, \,1}=D_9$ ha $26095$ términos.

Para más detalles, ver

C. Niculescu, L. E. Persson: Funciones Convexas y sus Aplicaciones: Un Enfoque Contemporáneo, el Apéndice B.

Answer 2

Quizás sea útil observar que si$P_n$ solo tiene raíces reales, ¿lo mismo es cierto para su derivada?

Answer 3

Un pequeño complemento a Francesco la respuesta: Una discusión a fondo de las $R$ polinomios (llamado subdiscriminants que son casos especiales de subresultants) está en el Capítulo 4 del libro "los Algoritmos en la Geometría Algebraica Real" por Basu, Pollack y Coste-Roy. Pueden usarse por ejemplo para dar una (muy complicado) la prueba de los autovalores de una real simétrica real (ver este MO respuesta).