Descartes' rule of signs

In mathematics, Descartes' rule of signs, first described by René Descartes in his work La Géométrie, is a technique for getting information on the number of positive real roots of a polynomial. It asserts that the number of positive roots is at most the number of sign changes in the sequence of polynomial's coefficients (omitting the zero coefficients), and that the difference between these two numbers is always even. This implies, in particular, that if the number of sign changes is zero or one, then there are exactly zero or one positive roots, respectively.

By a linear fractional transformation of the variable, one may use Descartes' rule of signs for getting a similar information on the number of roots in any interval. This is the basic idea of Budan's theorem and Budan–Fourier theorem. By repeating the division of an interval into two intervals, one gets eventually a list of disjoint intervals containing together all real roots of the polynomial, and containing each exactly one real root. Descartes rule of signs and linear fractional transformations of the variable are, nowadays, the basis of the fastest algorithms for computer computation of real roots of polynomials (see real-root isolation).

Descartes himself used the transformation $x \to - x$ for using his rule for getting information of the number of negative roots.

Descartes' rule of signs

Positive roots

The rule states that if the nonzero terms of a single-variable polynomial with real coefficients are ordered by descending variable exponent, then the number of positive roots of the polynomial is either equal to the number of sign changes between consecutive (nonzero) coefficients, or is less than it by an even number. A root of multiplicity $k$ is counted as $k$ roots.

In particular, if the number of sign changes is zero or one, the number of positive roots equals the number of sign changes.

Negative roots

As a corollary of the rule, the number of negative roots is the number of sign changes after multiplying the coefficients of odd-power terms by −1, or fewer than it by an even number. This procedure is equivalent to substituting the negation of the variable for the variable itself. For example, the negative roots of $ax^{3}+bx^{2}+cx+d$ are the positive roots of

a(-x)^{3}+b(-x)^{2}+c(-x)+d=-ax^{3}+bx^{2}-cx+d.

Thus, applying Descartes' rule of signs to this polynomial gives the maximum number of negative roots of the original polynomial.

Example: cubic polynomial

The polynomial

f(x)=+x^{3}+x^{2}-x-1

has one sign change between the second and third terms, as the sequence of signs is $(+, +, -, -)$ . Therefore, it has exactly one positive root. To find the number of negative roots, change the signs of the coefficients of the terms with odd exponents, i.e., apply Descartes' rule of signs to the polynomial $f(-x)=-x^{3}+x^{2}+x-1.$

This polynomial has two sign changes, as the sequence of signs is $(-, +, +, -)$ , meaning that this second polynomial has two or zero positive roots; thus the original polynomial has two or zero negative roots.

In fact, the factorization of the first polynomial is

f(x)=(x+1)^{2}(x-1),

so the roots are −1 (twice) and +1 (once).

The factorization of the second polynomial is

f(-x)=-(x-1)^{2}(x+1).

So here, the roots are +1 (twice) and −1 (once), the negation of the roots of the original polynomial.

Proof

The following is a rough outline of a proof.[1] First, some preliminary definitions:

Write the polynomial $f(x)$ as $\sum _{i=0}^{n}a_{i}x^{b_{i}}$ where we have integer powers $0\leq b_{0}<b_{1}<\cdots <b_{n}$ , and nonzero coefficients $a_{i}\neq 0$ .

Let $V(f)$ be the number of sign changes of the coefficients of $f$ , meaning the number of $k$ such that $a_{k}a_{k+1}<0$ .

Let $Z(f)$ be the number of strictly positive roots (counting multiplicity).

With these, we can formally state Descartes' rule as follows:

Theorem — The number of strictly positive roots (counting multiplicity) of $f$ is equal to the number of sign changes in the coefficients of $f$ , minus a nonnegative even number.

If $b_{0}>0$ , then we can divide the polynomial by $x^{b_{0}}$ , which would not change its number of strictly positive roots. Thus WLOG, let $b_{0}=0$ .

Lemma — If $a_{n}a_{0}>0$ , then $Z(f)$ is even. If $a_{0}a_{n}<0$ , then $Z(f)$ is odd.

Proof of Lemma

$f(x)$ starts at $f(0)=a_{0}>0$ and ends at $f(+\infty )=+\infty >0$ , so it must cross the positive x-axis an even number of times (each of which contributes an odd number of roots), and glance (without crossing) the positive x-axis an arbitrary number of times (each of which contributes an even number of roots).

The other case is similar.

Proof of main theorem

From the lemma, it follows that $Z(f)$ and $V(f)$ always have the same parity. It remains to show $Z(f)\leq V(f)$ .

We induct on $n$ . If $n=0,1$ , then it is obvious. Now assume $n\geq 2$ .

By induction hypothesis, $Z(f')=V(f')-2s$ for some integer $s\geq 0$ .

By Rolle's theorem, there exists at least one positive root of $f'$ between any two different positive roots of $f$ . Also, any $k$ -multiple positive root of $f$ is a $k-1$ -multiple root of $f'$ . Thus $Z(f')\geq Z(f)-1$ .

If $a_{0}a_{1}>0$ , then $V(f')=V(f)$ , else $V(f')=V(f)-1$ . In both cases, $V(f')\leq V(f)$

Together, we have

Z(f)\leq Z(f')+1=V(f')-2s+1\leq V(f)-2s+1\leq V(f)+1

Further, since $Z(f)$ and $V(f)$ have the same parity, we have $Z(f)\leq V(f)$ .

Nonreal roots

Any nth degree polynomial has exactly n roots in the complex plane, if counted according to multiplicity. So if f(x) is a polynomial with real coefficients which does not have a root at 0 (that is a polynomial with a nonzero constant term) then the minimum number of nonreal roots is equal to

n-(p+q),

where p denotes the maximum number of positive roots, q denotes the maximum number of negative roots (both of which can be found using Descartes' rule of signs), and n denotes the degree of the equation.

Example: some zero coefficients and nonreal roots

The polynomial

f(x)=x^{3}-1,

has one sign change; so the maximum number of positive real roots is one. As

f(-x)=-x^{3}-1,

has no sign change, the original polynomial has no negative real roots. So the minimum number of nonreal roots is

3-(1+0)=2.

Since nonreal roots of a polynomial with real coefficients must occur in conjugate pairs, it means that $x 3 - 1$ has exactly two nonreal roots and one real root, which is positive.

Special case

The subtraction of only multiples of 2 from the maximal number of positive roots occurs because the polynomial may have nonreal roots, which always come in pairs since the rule applies to polynomials whose coefficients are real. Thus if the polynomial is known to have all real roots, this rule allows one to find the exact number of positive and negative roots. Since it is easy to determine the multiplicity of zero as a root, the sign of all roots can be determined in this case.

Generalizations

If the real polynomial P has k real positive roots counted with multiplicity, then for every a > 0 there are at least k changes of sign in the sequence of coefficients of the Taylor series of the function e^axP(x). For sufficiently large a, there are exactly k such changes of sign.[2][3]

In the 1970s Askold Khovanskii developed the theory of fewnomials that generalises Descartes' rule.[4] The rule of signs can be thought of as stating that the number of real roots of a polynomial is dependent on the polynomial's complexity, and that this complexity is proportional to the number of monomials it has, not its degree. Khovanskiǐ showed that this holds true not just for polynomials but for algebraic combinations of many transcendental functions, the so-called Pfaffian functions.

Notes

Wang, Xiaoshen (June–July 2004). "A Simple Proof of Descartes's Rule of Signs". The American Mathematical Monthly. 111 (6): 525. doi:10.2307/4145072. ISSN 0002-9890.
D. R. Curtiss, Recent extensions of Descartes' rule of signs, Annals of Mathematics., Vol. 19, No. 4, 1918, pp. 251–278.
Vladimir P. Kostov, A mapping defined by the Schur–Szegő composition, Comptes Rendus Acad. Bulg. Sci. tome 63, No. 7, 2010, pp. 943–952.
Khovanskiǐ, A.G. (1991). Fewnomials. Translations of Mathematical Monographs. Translated from the Russian by Smilka Zdravkovska. Providence, RI: American Mathematical Society. p. 88. ISBN 0-8218-4547-0. Zbl 0728.12002.

External links

This article incorporates material from Descartes' rule of signs on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Descartes' Rule of Signs – Proof of the rule
Descartes' Rule of Signs – Basic explanation

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Wang, Xiaoshen (June–July 2004). "A Simple Proof of Descartes's Rule of Signs". The American Mathematical Monthly. 111 (6): 525. doi:10.2307/4145072. ISSN 0002-9890.

[2] D. R. Curtiss, Recent extensions of Descartes' rule of signs, Annals of Mathematics., Vol. 19, No. 4, 1918, pp. 251–278.

[3] Vladimir P. Kostov, A mapping defined by the Schur–Szegő composition, Comptes Rendus Acad. Bulg. Sci. tome 63, No. 7, 2010, pp. 943–952.

[4] Khovanskiǐ, A.G. (1991). Fewnomials. Translations of Mathematical Monographs. Translated from the Russian by Smilka Zdravkovska. Providence, RI: American Mathematical Society. p. 88. ISBN 0-8218-4547-0. Zbl 0728.12002.

Descartes' rule of signs