## You are here

HomeSturm's theorem

## Primary tabs

# 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\;\;(\mathop{{\rm mod}}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., “ Proof of Sturm’s Theorem”

## Mathematics Subject Classification

11A05*no label found*26A06

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections