Sturm root counting
Sign changes of the signed Euclidean remainder sequence count the distinct real roots of a polynomial in an interval. This gives an exact, finite test for real-rootedness, and the Hermite–Sylvester criterion gives a second one through a positive semidefinite matrix of power sums.
Results
For a real polynomial $p$, the Sturm sequence is the signed Euclidean remainder sequence of $p$ and $p'$; its sign variation at $x$ is the number of sign changes of its values at $x$, zero values omitted. For arbitrary $p$ we apply it to its radical (the squarefree part, with the repeated factors removed), and write $V_p(x)$ for the resulting variation.
Theorem (Sturm). Let $p\ne0$ and $a<b$ with $p(b)\ne0$. Then the number of distinct real roots of $p$ in the open interval $(a,b)$ is $V_p(a)-V_p(b)$.
Theorem (real-rootedness by sign changes). Let $p\ne0$ and $a<b$, and suppose every real root of $p$ lies in $(a,b)$. Then $p$ is real-rooted if and only if $V_p(a)-V_p(b)$ equals the degree of the squarefree part of $p$.
Hermite–Sylvester criterion [Syl53]. Let $f$ be a monic real polynomial of degree $n$ and $s_k=\sum_zz^k$ the power sums of its complex roots, counted with multiplicity. Put $H_f=(s_{i+j})_{0\le i,j\le n-1}$. Then $f$ is real-rooted if and only if $H_f$ is positive semidefinite.
Proposition (degree at most three). A real polynomial of degree at most three is real-rooted if and only if its cubic discriminant is nonnegative.
References
- J. C. F. Sturm, “Mémoire sur la résolution des équations numériques,” Bulletin des Sciences de Férussac 11 (1829), 419–422.
- C. Hermite, “Remarques sur le théorème de M. Sturm,” Comptes rendus de l’Académie des sciences 36 (1853), 52–54.
- [Syl53]
- On symmetricfunctions.com: Sturm root counting and the Hermite–Sylvester theorem.
- [Syl53] XVIII. On a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm's functions, and that of the greatest algebraical common measure. Philosophical Transactions of the Royal Society of London, (143), 407-548, 1853.
BibTeX
@article{Sylvester1853, author = {Sylvester, James Joseph}, title = {{XVIII}. {O}n a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of {S}turm's functions, and that of the greatest algebraical common measure}, year = {1853}, journal = {Philosophical Transactions of the Royal Society of London}, number = {143}, pages = {407--548}, doi = {10.1098/rstl.1853.0018}, url = {https://doi.org/10.1098/rstl.1853.0018} }