# 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”

Type of Math Object:
Theorem
Major Section:
Reference

## Mathematics Subject Classification

11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors
26A06 One-variable calculus

## Recent Activity

May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden
new question: Solving the word problem for isomorphic groups by mairiwalker
new image: LineDiagrams.jpg by m759
new image: ProjPoints.jpg by m759
new image: AbstrExample3.jpg by m759
new image: four-diamond_figure.jpg by m759
May 16
new problem: Curve fitting using the Exchange Algorithm. by jeremyboden
new question: Undirected graphs and their Chromatic Number by Serchinnho

## Info

Owner: rspuzio
Added: 2004-07-22 - 20:04
Author(s): rspuzio

## Corrections

theorem? by CWoo ✓

## Versions

(v14) by rspuzio 2013-03-22
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 31, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8531388640403748, "perplexity_flag": "middle"}