Counting the number of real roots in an interval with Vincent's theorem

Abstract

It is well known that, in 1829, the French mathematician Jacques Charles Francois Sturm (1803-1855) solved the problem of finding the number of real roots of a polynomial equation f(x) = 0, with rational coefficients and without multiple roots, over a given interval, say ]a, b[. As a byproduct, he also solved the related problem of isolating the real roots of (x). In 1835 Sturm published another theorem for counting the number of complex roots of f (x); this theorem applies only to complete Sturm sequences and was recently extended to Sturm sequences with at least one missing term. Less known, however, is the fact that Sturm's fellow countryman and contemporary Alexandre Joseph Hidulphe Vincent (1797-1868) also presented, in 1836, another theorem for the isolation (only) of the positive roots of f(x) using continued fractions. In its latest implementation, the Vincent-Akritas-Strzebonski (VAS) continued fractions method for the isolation of real roots of polynomials turns out to be the fastest method derived from Vincent's theorem, by far outperformes the one by Sturm, and has been implemented in major computer algebra systems. In this paper we use the VAS real root isolation method to count the number of real and complex roots of f(x) as well as the number of real roots f(x) has in an open interval ]a, b[.