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 theSturm sequence of polynomials $\\big{(}P_{0}(x),P_{1}(x),\\ldots\\big{)}$ by

$\\displaystyle P_{0}(x)$	$\\displaystyle=$	$\\displaystyle P(x)$
$\\displaystyle P_{1}(x)$	$\\displaystyle=$	$\\displaystyle P^{\\prime}(x)$
$\\displaystyle P_{n}(x)$	$\\displaystyle=$	$\\displaystyle-\\mathrm{rem}(P_{n-2},P_{n-1}),n\\geq 2$

Here $\\mathrm{rem}(P_{n-2},P_{n-1})$ denotes the remainder of thepolynomial $P_{n-2}$ upon division by the polynomial $P_{n-1}$ . Thesequence terminates once one of the $P_{i}$ is zero.

Definition 2.

For any number $t$ , let $var_{P}(t)$ denote the number of sign changes in thesequence $P_{0}(t),P_{1}(t),\\ldots$ .

Theorem 1.

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

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

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

Note that deg $P_{n}<$ deg $P_{n-1}$ , and so the longest possibleSturm sequence has deg $P+1$ terms.

Also, note that this sequence is very closely related to the sequence of remainders generated by the Euclidean Algorithm; in fact, the term $P_{i}$ is the exact same except with a sign changed when $i\\equiv 2$ or $3\\pmod{4}$ . 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., “http://web.archive.org/web/20050412175929/http://www.mpi-sb.mpg.de/ nicola/Vorlesung/sturm.psProof of Sturm’s Theorem”