Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
@Tran Chieu Minh, thanks! link fixed. –  kiasncp Apr 10 '10 at 19:30
    
See Jacobson, Basic Algebra I, Chapter 5. –  François G. Dorais Apr 10 '10 at 19:34
1  
(He discusses the theorems of Sturm, Seidenberg, and Tarski with amazing detail.) –  François G. Dorais Apr 10 '10 at 19:39
    
@François G. Dorais, thanks for the interesting reference! –  kiasncp Apr 10 '10 at 22:49
    
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. –  Adam Gal Apr 10 '10 at 23:50

5 Answers 5

up vote 17 down vote accepted

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

share|improve this answer
7  
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. –  J. M. Aug 17 '10 at 2:00
    
Too bad the procedure isn't computable... (in the sense of computing with exact real arithmetic) –  Andrej Bauer Mar 15 '13 at 20:30

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.

share|improve this answer

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

share|improve this answer
    
@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. –  kiasncp Apr 10 '10 at 22:55
    
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. –  Petya Apr 10 '10 at 23:55

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.

share|improve this answer
    
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) –  mike Feb 18 at 6:39

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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