# Changing the signs of the coefficients of a polynomial to make all the roots real

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.

• I wonder what is the probability, if the $a_i \in [-1,1]$ are uniformly distributed, that one of the $2^n$ polynomials $P_n(x;\pmb{\epsilon})$ has all real roots? For $n=3$, it appears that all real roots occur for about $59$% of the coefficient vectors. – Joseph O'Rourke Dec 20 '16 at 0:51

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.

• What is known about the sequence $k(n)$ (=minimum number of required inequalities for degree $n$)? – Pietro Majer Dec 19 '16 at 16:43
• I think $k(n)=n-1$, that's the number of nontrivial subdiscriminants. Although I may be wrong because if I remember correctly the cubic has only one condition. – Abdelmalek Abdesselam Dec 19 '16 at 17:21
• In general $k(n) \leq n-1$, because some of the inequalities coming from the subdiscriminants might be redundant. For instance, for $n=3$ we have $k(3)=1$ (a monic cubic polynomial has only real roots if and only if its discriminant $D_3$ is non negative). For $n=4$ an explicit Sylvester family made of $3$ polynomials can be found in Nicolescu's paper A new look at Newton's inequalities, see emis.u-strasbg.fr/journals/JIPAM/images/014_99_JIPAM/014_99.pdf However, I do not know whether $k(4)=3$. And I do not even know any result about the precise value of $k(n)$ for general $n$. – Francesco Polizzi Dec 19 '16 at 17:41
• @Francesco: thanks for the infos. The example about the cubic raised a flag for my initial guess. It's intriguing, that such fundamental inequalities are not yet understood. I believe this is related to the conjecture by G.-C. Rota in mathoverflow.net/questions/107526/… and one of his 12 problems in probability theory about inequalities for cumulants. – Abdelmalek Abdesselam Dec 19 '16 at 18:48

Perhaps it is useful to observe that if $P_n$ has only real roots, the same is true for its derivative?

• good point! One should also put the "s" for plural. – Abdelmalek Abdesselam Dec 19 '16 at 18:55

A small complement to Francesco's answer: A thorough discussion of the $R$ polynomials (called subdiscriminants which are special cases of subresultants) is in Chapter 4 of the book "Algorithms in Real Algebraic Geometry" by Basu, Pollack and Coste-Roy. They can be used for instance to give a (very complicated) proof of the eigenvalues of a real symmetric being real (see this MO answer).