24
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Dec 20 '16 at 0:51
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is known about the sequence $k(n)$ (=minimum number of required inequalities for degree $n$)? $\endgroup$ – Pietro Majer Dec 19 '16 at 16:43
  • $\begingroup$ 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. $\endgroup$ – Abdelmalek Abdesselam Dec 19 '16 at 17:21
  • 2
    $\begingroup$ 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$. $\endgroup$ – Francesco Polizzi Dec 19 '16 at 17:41
  • $\begingroup$ @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. $\endgroup$ – Abdelmalek Abdesselam Dec 19 '16 at 18:48
9
$\begingroup$

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

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

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

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