Sturm’s theorem

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

Definition 1.

Let $P\mathit{}\mathrm{(}x\mathrm{)}$ be a real polynomial in $x$, and define the Sturm sequence of polynomials $\mathrm{(}{P}_{\mathrm{0}}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}{P}_{\mathrm{1}}\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}\mathrm{\dots }\mathrm{)}$ by

$P_0(x)$ $=$ $P(x)$

$P_1(x)$ $=$ $P^{\prime }(x)$

$P_n(x)$ $=$ $-\mathrm{rem}(P_{n-2},P_{n-1}),n\ge 2$

Here $\mathrm{rem}\mathit{}\mathrm{(}{P}_{n\mathrm{-}\mathrm{2}}\mathrm{,}{P}_{n\mathrm{-}\mathrm{1}}\mathrm{)}$ denotes the remainder of the polynomial $P_{n\mathrm{-}\mathrm{2}}$ upon division by the polynomial $P_{n\mathrm{-}\mathrm{1}}$. The sequence terminates once one of the $P_i$ is zero.

Definition 2.

For any number $t$, let $v\mathit{}a\mathit{}{r}_P\mathit{}\mathrm{(}t\mathrm{)}$ denote the number of sign changes in the sequence $P_{\mathrm{0}}\mathit{}\mathrm{(}t\mathrm{)}\mathrm{,}{P}_{\mathrm{1}}\mathit{}\mathrm{(}t\mathrm{)}\mathrm{,}\mathrm{\dots }$.

Theorem 1.

For real numbers $a$ and $b$ that are both not roots of $P\mathit{}\mathrm{(}x\mathrm{)}$,

$$\mathrm{\#}\{\mathit{\text{distinct real roots of }}P\mathit{\text{ in }}(a,b)\}=va{r}_P(a)-va{r}_P(b)$$

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

Note that deg 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(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., “ http://web.archive.org/web/20050412175929/http://www.mpi-sb.mpg.de/ 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