[Math] Changing the signs of the coefficients of a polynomial to make all the roots real

Question

We are given a polynomial
$$P_n(x):=a_nx^n + a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$
with real coefficients.

Questions.

$\boldsymbol{(i)}$ How can we determine if there are $\epsilon_1,\ldots,\epsilon_n\in\{-1,+1\}$ such that
$$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$$
has only real roots? Here $\pmb{\epsilon}=(\epsilon_1,\dots,\epsilon_n)$.

$\boldsymbol{(ii)}$ If there is a solution, how can we find it?

Obviously an exhaustive search is hopelessly slow. This question might just possibly (on a good day) be of relevance to a problem on graph polynomials.

Answer 1

At least in principle, a solution is provided by the following result due to J. Sylvester:

Theorem (Sylvester). For each natural number $n \geq 2$ there exists a set of at most $n-1$ polynomials with integer coefficients $$R_{n, \, 1}(X_1, \ldots, X_n), \ldots, R_{n, \, k(n)}(X_1, \ldots, X_n)$$ such that the monic real polynomials of degree $n$ $$P(x)=x^n+a_{1}x^{n-1}+ \cdots + a_n$$ having only real roots are precisely those for which $$R_{n, \, 1}(a_1, \ldots, a_n) \geq 0, \ldots, R_{n, \, k(n)}(a_1, \ldots, a_n) \geq 0.$$

This can be seen as a generalization of the well-known fact that a real quadratic monic polynomial $x^2+a_1x+a_2$ has only real roots if and only if its discriminant $$D_2(1, \, a_1, \, a_2)=a_1^2-4 a_2$$ is non-negative. In fact, for all positive integers $n$ we have $$R_{n, \, 1}(a_1, \ldots, a_n) = D_n(1, \, a_1, \ldots, a_n),$$ where $D_n$ is the discriminant of $P(x)$, whereas the other polynomials $R_{n, \,i}$ can be explicitly computed in terms of determinants extracted from the Sylvester matrix of $P$ and $P'$.

So, in order to answer your question, one must check whether $$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$$ for some choice of $\epsilon_1, \ldots, \epsilon_n \in \{-1, \, 1 \}.$ From the computational point of view, the problem is that the number of non-zero coefficients in our polynomials rapidly increases with the degree: for instance, $R_{9, \,1}=D_9$ has $26095$ terms.

For further details, see

C. Niculescu, L. E.Persson: Convex Functions and their Applications: A Contemporary Approach, Appendix B.