Sturm's theorem
In mathematics, the Sturm's sequence of a univariate polynomial p is a sequence of polynomials associated with p and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of p located in an interval in terms of the number of changes of signs of the values of the Sturm's sequence at the bounds of the interval. Applied to the interval of all the real numbers, it gives the total number of real roots of p.
Whereas the fundamental theorem of algebra readily yields the overall number of complex roots, counted with multiplicity, it does not provide a procedure for calculating them. Sturm's theorem counts the number of distinct real roots and locates them in intervals. By subdividing the intervals containing some roots, it can isolate the roots into arbitrary small intervals, each containing exactly one root. This yields an arbitraryprecision numeric root finding algorithm for univariate polynomials.
Sturm's sequence and Sturm's theorems are named after Jacques Charles François Sturm.
Contents
 Sturm chains 1

Statement 2
 The nonsquarefree case 2.1
 Example 3
 Proof 4
 History section and other related methods 5

Applications 6
 Number of real roots 6.1
 Quotient 6.2
 Generalized Sturm chains 7
 See also 8
 References 9
 External links 10
Sturm chains
A Sturm chain or Sturm sequence is a finite sequence of polynomials
 p_0, p_1, \dots, p_m
of decreasing degree with these following properties:
 p_{0} = p is square free (no square factors, i.e., no repeated roots);
 if p(ξ) = 0, then sign(p_{1}(ξ)) = sign(p′(ξ));
 if p_{i}(ξ) = 0 for 0 < i < m then sign(p_{i−1}(ξ)) = −sign(p_{i+1}(ξ));
 p_{m} does not change its sign.
Sturm's sequence is a modification of Fourier's sequence.
To obtain a Sturm chain, Sturm himself proposed to choose the intermediary results when applying Euclid's algorithm to p and its derivative:
 \begin{align} p_0(x) & := p(x),\\ p_1(x) & := p'(x),\\ p_2(x) & := {\rm rem}(p_0, p_1) = p_1(x) q_0(x) p_0(x),\\ p_3(x) & := {\rm rem}(p_1,p_2) = p_2(x) q_1(x)  p_1(x),\\ &{}\ \ \vdots\\ 0 & = \text{rem}(p_{m1}, p_m), \end{align}
where rem(p_{i}, p_{j}) and q_{i} are the remainder and the quotient of the polynomial long division of p_{i} by p_{j}, and where m is the minimal number of polynomial divisions (never greater than deg(p)) needed to obtain a zero remainder. That is, successively take the remainders with polynomial division and change their signs. Since deg(p_{i+1}) < deg(p_{i}) for 0 ≤ i < m, the algorithm terminates. The final polynomial, p_{m}, is the greatest common divisor of p and its derivative. If p is square free, it shares no roots with its derivative, hence p_{m} will be a nonzero constant polynomial. The Sturm chain, called the canonical Sturm chain, then is
 p_0,p_1,p_2,\ldots,p_m .
If p is not squarefree, this sequence does not formally satisfy the definition of a Sturm chain above; nevertheless it still satisfies the conclusion of Sturm's theorem (below).
Statement
Let p = p_{0}, ..., p_{m} be a Sturm chain, where p is a squarefree polynomial, and let σ(ξ) denote the number of sign changes (ignoring zeroes) in the sequence
 p_0(\xi), p_1(\xi), p_2(\xi),\ldots, p_m(\xi).
Sturm's theorem then states that for two real numbers a < b, the number of distinct roots of p in the halfopen interval (a, b] is σ(a) − σ(b).
The nonsquarefree case
Let p = p_{0}, ..., p_{m} be the canonical Sturm sequence of a polynomial p, not necessarily squarefree. Then σ(a) − σ(b) is the number of distinct roots of p in (a, b] whenever a < b are real numbers such that neither a nor b is a multiple root of p.
Example
Suppose we wish to find the number of roots in some range for the polynomial p(x)=x^4+x^3x1. So
 \begin{align} p_0(x) &=p(x)=x^4+x^3x1 \\ p_1(x)&=p'(x)=4x^3+3x^21 \end{align}
Using polynomial long division to divide p_{0} by p_{1} gives the remainder \tfrac{3}{16}x^2\tfrac{3}{4}x\tfrac{15}{16}, and upon multiplying this remainder by −1 we obtain p_2(x)=\tfrac{3}{16}x^2+\tfrac{3}{4}x+\tfrac{15}{16}. Next dividing p_{1} by p_{2} and multiplying the remainder by −1, we obtain p_3(x)=32x64. And dividing p_{2} by p_{3} and multiplying the remainder by −1, we obtain p_4(x)=\tfrac{3}{16}.
Thus the complete chain of Sturm polynomials is:
 p_0(x) = x^4+x^3x1
 p_1(x) = 4x^3+3x^21
 p_2(x) = \tfrac{3}{16}x^2+\tfrac{3}{4}x+\tfrac{15}{16}
 p_3(x) = 32x64
 p_4(x) = \tfrac{3}{16}
To find the number of roots between −∞ and ∞, first evaluate p_{0}, p_{1}, p_{2}, p_{3}, and p_{4} at −∞ and note the sequence of signs of the results: + − + + −, which contains three sign changes (+ to −, then − to +, then + to −). The same procedure for ∞ gives the sign sequence + + + − −, which contains just one sign change. Hence the number of roots of the original polynomial between −∞ and ∞ is 3 − 1 = 2. That this is correct can be seen by noting that p(x) = x^{4} + x^{3} − x − 1 can be factored as (x^{2} − 1)(x^{2} + x + 1), where it is readily verifiable that x^{2} − 1 has the two roots −1 and 1 while x^{2} + x + 1 has no real roots. In more complicated examples in which there is no advance knowledge of the roots because factoring is either impossible or impractical, one can experiment with various finite bounds for the range to be considered, thus narrowing down the locations of the roots.
Proof
Polynomials are continuous functions, and any sign change must occur at a root, so consider the behavior of a Sturm chain around the roots of its constituent polynomials.
First, note that two adjacent polynomials can share a common root only when it is a multiple root of p (in which case it is a root of every p_{i}). Indeed, if p_{i}(ξ) = p_{i−1} (ξ) = 0, then p_{i+1}(ξ) = 0, since sign(p_{i−1}(ξ)) = −sign(p_{i+1}(ξ)). The zero then propagates recursively up and down the chain, so that ξ is a root of all the polynomials p_{0}, ..., p_{m}.
Next, consider roots of polynomials in the interior (i.e., 0 < i < m) of the Sturm chain that are not multiple roots of p. If p_{i}(ξ) = 0, then from the previous paragraph it is true that p_{i−1}(ξ) ≠ 0 and p_{i+1}(ξ) ≠ 0. Furthermore, sign(p_{i−1}(ξ)) = −sign(p_{i+1}(ξ)). Since p_{i−1} and p_{i+1} are continuous, sign(p_{i+1}(x)) = −sign(p_{i−1}(x)) for every x in the vicinity of ξ. Similarly, the sign of p_{i}(x) is constant before and after ξ, and changes as x is crossing ξ. Thus, whenever x is crossing ξ, moving from left to right, the part p_{i−1}, p_{i}, p_{i+1} of the Sturm chain loses a sign change at one side, and acquires a new sign change at the other side. Consequently, the total number of sign changes is never affected by the polynomial variations in the interior of the chain, and only roots of the original polynomial, at the top of the chain, can affect the total number of sign changes.
Consider a root ξ, so p(ξ), and assume first that it is a simple root. Then the derivative of p, which is p_{1}, must be nonzero at ξ, so p must be either increasing or decreasing at ξ. If it's increasing, then its sign is changing from negative to positive when moving from left to right while its derivative (again, p_{1}) is positive, so the total number of sign changes decreases by one. Conversely, if it's decreasing, then its sign changes from positive to negative while its derivative is negative, so again the total number of sign changes decreases by one.
Finally, let ξ be a multiple root of p, and let p_{0}, ..., p_{m} be the canonical Sturm chain. Let d = gcd(p,p′), q = p/d, and let q_{0}, ..., q_{m′} be the canonical Sturm chain of q. Then m = m′ and p_{i} = q_{i}d for every i. In particular, σ(x) is the same for both chains whenever x is not a root of d. Then the number of sign changes (in either chain) around ξ decreases by one, since ξ is a simple root of q.
In summary, only sign changes at roots of the original polynomial affect the total number of sign changes across the chain, and the total number of sign changes always decreases by one as roots are passed. The theorem follows directly.
For counting and isolating the real roots, other methods are usually preferred, because they are computationally more efficient; these methods all use Descartes' rule of signs (just like Fourier^{[1]} did back in 1820) and Vincent's theorem. The very first one of those methods was initially called "modified Uspensky's algorithm" by its inventors,^{[2]} but it was later shown that there is no Uspensky's method;^{[3]} afterwards, people started calling it either "CollinsAkritas method"^{[4]} or "Descartes' method" only to be shown that there is no Descartes' method^{[4]} either. Finally, François Boulier, of the University of Lille,^{[5]} p. 24, gave it the name "VincentCollinsAkritas" (VCA for short) to also give credit to Vincent. VCA is a bisection method; there exists also a continued fractions method based on Vincent's theorem namely, the VincentAkritasStrzeboński (VAS) method.^{[6]}
VAS is based on Budan's theorem whereas Sturm's method was inspired by Fourier's theorem. In fact Sturm himself,^{[7]} p. 108, acknowledges the great influence Fourier's theorem had on him: « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer. » which translates to "It is by relying upon the principles he has laid out and by imitating his proofs that I have found the new theorems which I am about to announce."
Applications
Number of real roots
Sturm's theorem can be used to compute the total number of real roots of a polynomial.
This may be done by choosing −a = b = M where M is larger than the absolute value of every root. For example, a bound due to Cauchy says that all real roots of a polynomial with coefficients a_{i} are in the interval [−M, M], where
 M = 1 + \frac{\max_{i=0}^{n1} a_i}{a_n}.
Although theoretically the above approach is the simplest, in practice bounds on the positive (only) roots of polynomials are used and the positive roots are isolated and evaluated first; the negative roots are treated by first substituting x by −x, then compute a new (positive root) bound to isolate and evaluate the negative roots. Sturm's method and VCA need to compute only one bound to isolate the positive roots. In contrast, to isolate the positive roots VAS needs to compute various positive bounds, for the various polynomials that appear in the process.^{[8]}^{[9]}
Another method is computationally simpler. One can use the fact that for large x, the sign of
 p(x)=a_n x^n+\cdots
is sign(a_{n}), whereas sign(p(−x)) is (−1)^{n}a_{n}. In this way, simply counting the sign changes in the leading coefficients in the Sturm chain readily gives the number of distinct real roots of a polynomial.
Sturm's theorem allows also to determine the multiplicity of a given root, say ξ. Indeed, suppose that a < ξ < b, with σ(a) − σ(b) = 1. Then, ξ has multiplicity k precisely when ξ is a root with multiplicity k − 1 of p_{m} (since it is the GCD of p and its derivative). Thus the multiplicity of ξ may be computed by recursively applying Sturm's theorem to p_{m}. However, this method is rarely used, as squarefree factorization is computationally more efficient for this purpose.
Quotient
The remainder is needed to compute the chain using Euclid's algorithm. For two polynomials
 p(x)=\sum_{k=0}^i p_k x^k, \qquad \widetilde{p}(x)=\sum_{k=0}^{i1}\widetilde{p}_k x^k, \quad \widetilde{p}_{i1} \neq 0,
this is accomplished by
 \text{rem} \left (p, \widetilde{p} \right )= \widetilde{p}_{i1}\cdot p(x) p_i\cdot\widetilde{p}(x)\left(x+\frac{p_{i1}}{p_i}\frac{\widetilde{p}_{i2}}{\widetilde{p}_{i1}}\right),
where the quotient is built solely of the first two leading coefficients.
Generalized Sturm chains
Let ξ be in the compact interval [a, b]. A generalized Sturm chain over [a, b] is a finite sequence of real polynomials (X_{0}, X_{1}, ..., X_{r}) such that:
 X(a)X(b) ≠ 0
 sign(X_{r}) is constant on [a, b]
 If X_{i}(ξ) = 0 for 1 ≤ i ≤ r − 1, then X_{i−1}(ξ)X_{i+1}(ξ) < 0.
One can check that each Sturm chain is indeed a generalized Sturm chain.
See also
 Routh–Hurwitz theorem
 Hurwitz's theorem (complex analysis)
 Descartes' rule of signs
 Rouché's theorem
 Properties of polynomial roots
 Gauss–Lucas theorem
 Turán's inequalities
 D.G. Hook and P.R. McAree, "Using Sturm Sequences To Bracket Real Roots of Polynomial Equations" in Graphic Gems I (A. Glassner ed.), Academic Press, p. 416–422, 1990.
References
 ^
 ^
 ^
 ^ ^{a} ^{b}
 ^
 ^
 ^
 ^
 ^
 Baumol, William. Economic Dynamics, section "Sturm's Theorem"
External links
 C code from Graphic Gems by D.G. Hook and P.R. McAree.