Sturm’s theorem

This root-counting theorem was produced by the French mathematician Jacques Sturm in 1829.

Definition 1.

Let P(x) be a real polynomial in x, and define the Sturm sequence of polynomialsPlanetmathPlanetmath (P0(x),P1(x),) by

P0(x) = P(x)
P1(x) = P(x)
Pn(x) = -rem(Pn-2,Pn-1),n2

Here rem(Pn-2,Pn-1) denotes the remainder of the polynomial Pn-2 upon division by the polynomial Pn-1. The sequence terminates once one of the Pi is zero.

Definition 2.

For any number t, let varP(t) denote the number of sign changes in the sequence P0(t),P1(t),.

Theorem 1.

For real numbers a and b that are both not roots of P(x),

#{distinct real roots of P in (a,b)}=varP(a)-varP(b)

In particular, we can count the total number of distinct real roots by looking at the limits as a- and b+. The total number of distinct real roots will depend only on the leading terms of the Sturm sequence polynomials.

Note that deg Pn< deg Pn-1, and so the longest possible Sturm sequence has deg P+1 terms.

Also, note that this sequence is very closely related to the sequence of remainders generated by the Euclidean AlgorithmMathworldPlanetmath; in fact, the term Pi is the exact same except with a sign changed when i2 or 3(mod4). Thus, the Half-GCD Algorithm may be used to compute this sequence. Be aware that some computer algebra systems may normalize remainders from the Euclidean Algorithm which messes up the sign.

For a proof, see Wolpert, N., “ nicola/Vorlesung/sturm.psProof of Sturm’s Theorem”

Title Sturm’s theorem
Canonical name SturmsTheorem
Date of creation 2013-03-22 14:28:49
Last modified on 2013-03-22 14:28:49
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 14
Author rspuzio (6075)
Entry type Theorem
Classification msc 11A05
Classification msc 26A06
Related topic EuclidsAlgorithm
Defines Sturm Sequence