36
$\begingroup$

Given a polynomial equation $x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0=0$, where $n$ is even and all the coefficients $a_i$ are real, what is the best way to determine whether it has a real root or not?

I know Sturm's theorem, but I am wondering if it's possible to determine this by the sign of some form of resolvent (e.g., discriminant works for $n=2$, but not 4 or beyond)?

Please point me to some reference if this has already been studied. Thanks for your time!


I apologize for not searching hard enough - I just realized there is a similar question discussed here before, and has already got lots of useful comments. My hope is to find a function of these real coefficients and whether the polynomial has real root or not is determined by its sign.

$\endgroup$
4
  • 1
    $\begingroup$ See Jacobson, Basic Algebra I, Chapter 5. $\endgroup$ Apr 10, 2010 at 19:34
  • 2
    $\begingroup$ (He discusses the theorems of Sturm, Seidenberg, and Tarski with amazing detail.) $\endgroup$ Apr 10, 2010 at 19:39
  • $\begingroup$ @François G. Dorais, thanks for the interesting reference! $\endgroup$
    – Wiley
    Apr 10, 2010 at 22:49
  • $\begingroup$ Just a thought: This set is probably not a Zariski closed set of the polynomials since it is a union of infinitely many codim 1 sets which intersect in codim 2 or more. So probably there is no algebraic condition for belonging to it. $\endgroup$
    – Adam Gal
    Apr 10, 2010 at 23:50

5 Answers 5

50
$\begingroup$

There is indeed an easy way to check if a univariate poly with real coefficients has a real root, without computing the roots.

Note that the answer for odd degree polynomials is always yes. For an even degree polynomial $p(x)$ do the following:

  1. Compute the Hermite form of the polynomial. This is a symmetric matrix defined e.g. here: (on page 4, near the bottom denoted by $H_1(p)$). The entries of this matrix can be filled using Newton identities.

  2. The number of real roots of $p(x)$ is equal to the signature of the Hermite matrix $H_1(p)$, i.e., the number of positive eigenvalues minus the number of negative eigenvalues.

  3. Since the Hermite form is symmetric, its characteristic poly has only real roots. Therefore, we can apply Descartes' rule of signs to its char. polynomial, which would give us exactly the number of positive and negative eigenvalues of the Hermite form.

This process gives you the exact number of real roots of $p(x)$ without computing the roots, and in particular you can see if the polynomial has a real root.

Hope this helps.

-Amirali Ahmadi

$\endgroup$
4
  • 15
    $\begingroup$ For those who have an interest in implementing this numerically: you don't need to expand the symmetric matrix to its characteristic polynomial only for the sole purpose of counting positive and negative eigenvalues (as J.H. Wilkinson has demonstrated, this is a numerically unstable process): due to Sylvester's inertia theorem, one can just perform an $LDL^T$ decomposition of the Hermite form matrix, and then the signature is just the number of positive elements of D minus the number of negative elements of D. $\endgroup$ Aug 17, 2010 at 2:00
  • 1
    $\begingroup$ Too bad the procedure isn't computable... (in the sense of computing with exact real arithmetic) $\endgroup$ Mar 15, 2013 at 20:30
  • 1
    $\begingroup$ The first link seems to be dead, but I think it was to this file. $\endgroup$ Feb 28, 2020 at 18:09
  • $\begingroup$ Tell me, can this method be used for non-monic polynomials? $\endgroup$
    – dtn
    Jan 20, 2022 at 4:35
9
$\begingroup$

Let $P$ be the space of all real monic polynomials of degree $n$; it is isomorphic to $\mathbb{R}^n$. There is a hypersurface $\Delta$ in $P$, cut out by the equation of the discriminant. As you cross $\Delta$, the number of real roots goes up or down by $2$. Also, every time you cross $\Delta$, the discriminant switches signs.

When $n$ is $2$ or $3$, then $P \setminus \Delta$ only has two connected components. On one of these components, all roots are real, and on the other two roots are imaginary. So you can tell which component you are in just be looking at the sign of the discriminant. Once $n$ is $4$ or larger, there are more than two connected components to $P \setminus \Delta$. So the sign of the discriminant can't tell you which component you are in. I don't know a formula for the number of connected components of $P \setminus \Delta$, but one could be extracted from the description of the toplogy of $(P, \Delta)$ in Gelfand, Kapranov and Zelevinsky, Discriminants, Resultants and Multidimensional Determinants.

One way to interpret your question is

Is there a polynomial $F$ on $P$ which is positive on the polynomials with $n$ real roots, and negative otherwise?

The answer is "no". The variety $\Delta$ is irreducible (by the Horn uniformization). By a standard lemma, any nonempty open subset of the real points of $\Delta$ is Zariski dense in $\Delta$. So, if $F$ vanishes on the part of $\Delta$ which forms the boundary of {Polynomials with all roots real}, then $F$ also vanishes on all of $\Delta$. Working a little harder, we can show that if $F$ vanishes to odd order on the boundary of {Polynomials with all roots real}, then it also vanishes to odd order on the other connected components of $\Delta(\mathbb{R})$.

On the other hand, there are many good ways to determine the number of real roots by polynomial computations, such as Sturm's method.

$\endgroup$
9
$\begingroup$

The following may be useful:

Kurtz (1992) proves that if all the $a_i$ are positive, and $a_i^2 - 4a_{i-1}a_{i+1} >0$ for $1\leqslant i\leqslant n-1$, then all the roots are real (and thus negative) and distinct.

$\endgroup$
1
  • 3
    $\begingroup$ Hutchinson (1923) seemed to be the first one who found such sufficient conditions for polynomials and entire functions to have only real zeros. (J. I. Hutchinson, On a Remarkable Class of Entire Functions , Transactions of the American Mathematical Society, Vol. 25, No. 3 (Jul., 1923), pp.325-332) $\endgroup$
    – mike
    Feb 18, 2014 at 6:39
5
$\begingroup$

Here is (a sketch of) my own solution to the Sturm problem, answering the question on a number of real roots of a polynomial on a given segment. The notion of the discriminant plays the central role in it. Here is a solution:

We can assume that equation $f=0$ has only simple roots (after the division by the gcd of $f$ and $f'$). Then

  1. Find an a priory estimate from above on an absolute value of a root. Denote this number by $C(f)$.

  2. Find a discriminant $\Delta(f)$ in terms of coefficients of $f$.

  3. In terms of $C(f)$ and $\Delta(f)$ one can find explicitly an a priory estimate $\varepsilon(f)>0$ from below on the absolute value of a difference of distinct roots of $f$: $|x_i-x_j|>\varepsilon(f)$ ($x_i$, $x_j$ are roots of $f$).

  4. For a given segment $[a,b]$ let $a=z_1 < z_2 < ... < z_N(f)=b$ be a sequence satisfying $|z_{i}-z_{i+1}|<\varepsilon(f)$ for any $i$ (in your case $a=-C, b=C$). We can assume without lost of generality that $f(z_i)\ne 0$. In that case the number of roots of $f$ on $[a,b]$ is equal to the number of changes of sign in the sequence $f(z_1), f(z_2), ..., f(z_N)$.

$\endgroup$
2
  • $\begingroup$ @Petya, thanks for your reply! Unfortunately I am mainly interested in whether a polynomial has real roots or not. I was hoping there could be a function of the coefficients whose sign can determine this. $\endgroup$
    – Wiley
    Apr 10, 2010 at 22:55
  • $\begingroup$ I am not sure that there exists such a good function. A closed expression for the number of real roots of square-free polynomial $f$ is, for example, $\frac{1}{2\pi i}\int_\gamma df/f$, where $\gamma$ is a boundary of $\varepsilon(f)/2$-neighborhood of a real segment $[-C(f),C(f)]$ in the complex line. $\endgroup$
    – Petya
    Apr 10, 2010 at 23:55
2
$\begingroup$

Please refer to "L. Yang, X. Hou, and Z. Zeng. A complete discriminant system for polynomials. Science in China, Ser.E, 39(6):628–646, 1996." Your answer may find in the paper. It is very intricate.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.