Vincent's theorem
In mathematics, Vincent's theorem—named after Alexandre Joseph Hidulphe Vincent—is a theorem that isolates the real roots of polynomials with rational coefficients.
Even though Vincent's theorem is the basis of the fastest method for the isolation of the real roots of polynomials, it was almost totally forgotten, having been overshadowed by Sturm's theorem; consequently, it does not appear in any of the classical books on the theory of equations (of the 20th century), except for Uspensky's book.
Two variants of this theorem are presented, along with several (continued fractions and bisection) real root isolation methods derived from them.
[4][5] If in a polynomial equation with rational coefficients and without multiple roots, one makes successive transformations of the form where
Furthermore, the corresponding root of the proposed equation is approximated by the finite continued fraction:[1][2][3] Moreover, if infinitely many numbers
satisfying this property can be found, then the root is represented by the (infinite) corresponding continued fraction.
The above statement is an exact translation of the theorem found in Vincent's original papers;[1][2][3] however, the following remarks are needed for a clearer understanding: Let p(x) be a real polynomial of degree deg(p) that has only simple roots.
A detailed discussion of Vincent's theorem, its extension, the geometrical interpretation of the transformations involved and three different proofs can be found in the work by Alesina and Galuzzi.
[4][5] A fourth proof is due to Ostrowski[6] who rediscovered a special case of a theorem stated by Obreschkoff,[7] p. 81, in 1920–1923.
In his fundamental papers,[1][2][3] Vincent presented examples that show precisely how to use his theorem to isolate real roots of polynomials with continued fractions.
That is, to compute each partial quotient ai (that is, to locate where the roots lie on the x-axis) Vincent uses Budan's theorem as a "no roots test"; in other words, to find the integer part of a root Vincent performs successive substitutions of the form x ← x+1 and stops only when the polynomials p(x) and p(x+1) differ in the number of sign variations in the sequence of their coefficients (i.e. when the number of sign variations of p(x+1) is decreased).
It can be easily inferred that, if the root is far away from the origin, it takes a lot of time to find its integer part this way, hence the exponential nature of Vincent's method.
A major achievement at the time was getting hold of Vincent's original paper of 1836, something that had eluded Uspensky—resulting thus in a great misunderstanding.
Vincent's original paper of 1836 was made available to Akritas through the commendable efforts (interlibrary loan) of a librarian in the Library of the University of Wisconsin–Madison, USA.
The continued fractions version of Vincent's theorem can be used to isolate the positive roots of a given polynomial p(x) of degree deg(p).
the continued fraction that leads to a transformed polynomial with one sign variation in the sequence of its coefficients.
Crucial Observation: The variables a, b, c, d of a Möbius transformation (in Vincent's theorem) leading to a transformed polynomial—as in equation (2)—with one sign variation in the sequence of its coefficients can be computed: The "bisection part" of this all important observation appeared as a special theorem in the papers by Alesina and Galuzzi.
[4][5] All methods described below (see the article on Budan's theorem for their historical background) need to compute (once) an upper bound, ub, on the values of the positive roots of the polynomial under consideration.
Exception is the VAS method where additionally lower bounds, lb, must be computed at almost every cycle of the main loop.
Excellent (upper and lower) bounds on the values of just the positive roots of polynomials have been developed by Akritas, Strzeboński and Vigklas based on previous work by Doru Stefanescu.
As stated above, it started in the 1830s when Vincent presented, in the papers[1][2][3] several examples that show how to use his theorem to isolate the real roots of polynomials with continued fractions.
Vincent's method was converted into its polynomial complexity form by Akritas, who in his 1978 Ph.D. Thesis (Vincent's theorem in algebraic manipulation, North Carolina State University, USA) computed each partial quotient ai as the lower bound, lb, on the values of the positive roots of a polynomial.
Finally, since the ideal positive lower root bound does not exist, Strzeboński[15] introduced in 2005 the substitution
Moreover, it has been shown[15] that the VAS (continued fractions) method is faster than the fastest implementation of the VCA (bisection) method,[16] a fact that was confirmed[17] independently; more precisely, for the Mignotte polynomials of high degree VAS is about 50,000 times faster than the fastest implementation of VCA.
In 2007, Sharma[18] removed the hypothesis of the ideal positive lower bound and proved that VAS is still polynomial in time.
, of degree deg(p), and the Möbius transformation Output: A list of isolating intervals of the positive roots of p(x).
This was the first method developed to overcome the exponential nature of Vincent's original approach, and has had quite an interesting history as far as its name is concerned.
This method, which isolates the real roots, using Descartes' rule of signs and Vincent's theorem, had been originally called modified Uspensky's algorithm by its inventors Collins and Akritas.
This was developed last and is the simplest real root isolation method derived from Vincent's theorem.
Remarks Given the polynomial p(x) = x3 − 7x + 7 and considering as an upper bound[12][13] on the values of the positive roots ub = 4 the arguments of VAG are: p(x) = x3 − 7x + 7 and (a, b) = (0, 4).
