In mathematics, the Sturm sequence of a univariate polynomial is a sequence of polynomials associated with and its derivative by a variant of Euclid's algorithm for polynomials. Sturm's theorem expresses the number of distinct real roots of located in an interval in terms of the number of changes of signs of the values of the Sturm 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 .

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 arbitrarily small intervals, each containing exactly one root. This yields the oldest real-root isolation algorithm, and arbitrary-precision root-finding algorithm for univariate polynomials.

Sturm's theorem

For computing over the reals, Sturm's theorem is less efficient than other methods based on Descartes' rule of signs. However, it works on every real closed field, and, therefore, remains fundamental for the theoretical study of the computational complexity of decidability and quantifier elimination in the first order theory of real numbers.

Sturm's theorem

The Sturm sequence and Sturm's theorem are named after Jacques Charles François Sturm, who discovered the theorem in 1829.

Sturm's theorem

The theorem

The Sturm chain or Sturm sequence of a univariate polynomial with real coefficients is the sequence of polynomials such that

for , where is the derivative of , and is the remainder of the Euclidean division of by The length of the Sturm sequence is at most the degree of .

The number of sign variations at of the Sturm sequence of is the number of sign changes–ignoring zeros—in the sequence of real numbers

This number of sign variations is denoted here .

Sturm's theorem states that, if is a square-free polynomial, the number of distinct real roots of in the half-open interval is (here, and are real numbers such that ).

The theorem extends to unbounded intervals by defining the sign at of a polynomial as the sign of its leading coefficient (that is, the coefficient of the term of highest degree). At the sign of a polynomial is the sign of its leading coefficient for a polynomial of even degree, and the opposite sign for a polynomial of odd degree.

In the case of a non-square-free polynomial, if neither nor is a multiple root of , then is the number of distinct real roots of .

The proof of the theorem is as follows: when the value of increases from to , it may pass through a zero of some (); when this occurs, the number of sign variations of does not change. When passes through a root of the number of sign variations of decreases from 1 to 0. These are the only values of where some sign may change.

Example

Suppose we wish to find the number of roots in some range for the polynomial . So

The remainder of the Euclidean division of by is multiplying it by we obtain

. Next dividing by and multiplying the remainder by , we obtain . Now dividing by and multiplying the remainder by , we obtain . As this is a constant, this finishes the computation of the Sturm sequence.

To find the number of real roots of one has to evaluate the sequences of the signs of these polynomials at and , which are respectively and . Thus

where denotes the number of sign changes in the sequence, which shows that has two real roots.

This can be verified by noting that can be factored as , where the first factor has the roots and , and second factor has no real roots. This last assertion results from the quadratic formula, and also from Sturm's theorem, which gives the sign sequences at and at .

Generalization

Sturm sequences have been generalized in two directions. To define each polynomial in the sequence, Sturm used the negative of the remainder of the Euclidean division of the two preceding ones. The theorem remains true if one replaces the negative of the remainder by its product or quotient by a positive constant or the square of a polynomial. It is also useful (see below) to consider sequences where the second polynomial is not the derivative of the first one.

A generalized Sturm sequence is a finite sequence of polynomials with real coefficients

such that

the degrees are decreasing after the first one: for ; does not have any real root or has no sign changes near its real roots. if for and a real number, then .