# 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\phantom{\rule{veryverythickmathspace}{0ex}}(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 |