Sturm's Theorem - Sturm Chains

Sturm Chains

A Sturm chain or Sturm sequence is a finite sequence of polynomials

of decreasing degree with these following properties:

• is square free (no square factors, i.e., no repeated roots);
• if, then
• if for then
• does not change its sign.

It can be noted that 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:

where rem and are the remainder and the quotient of the polynomial long division of by, and where m is the minimal number of polynomial divisions (never greater than the degree of p(x)) needed to obtain a zero remainder. That is, successively take the remainders with polynomial division and change their signs. Since for, 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 non-zero constant polynomial. The Sturm chain, called the canonical Sturm chain, then is

If p is not square-free, this sequence does not formally satisfy the definition of a Sturm chain above; nevertheless it still satisfies the conclusion of Sturm's theorem (see below).