# 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 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 the polynomial $P_{n-2}$ upon division by the polynomial $P_{n-1}$. The sequence 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 the sequence $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 the total number of distinct real roots by looking at the limits as $a\rightarrow-\infty$ and $b\rightarrow+\infty$. The total number of distinct real roots will depend only on the leading terms of the Sturm sequence polynomials.

Note that deg $P_{n}<$ deg $P_{n-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 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”

Title Sturm’s theorem SturmsTheorem 2013-03-22 14:28:49 2013-03-22 14:28:49 rspuzio (6075) rspuzio (6075) 14 rspuzio (6075) Theorem msc 11A05 msc 26A06 EuclidsAlgorithm Sturm Sequence