Budan's theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, Budan's theorem, named after F. D. Budan, is a little-known theorem for computing an upper bound on the number of real roots a polynomial has inside an open interval by counting the number of sign variations or sign changes in the sequences of coefficients.

Since 1836, the statement of Budan's theorem has been replaced in the literature by the statement of an equivalent theorem by Fourier, and the latter has been referred to under various names, including Budan's. However, it is only the statement of Budan's theorem that forms the basis of the fastest method for the isolation of the real roots of polynomials and hence it deserves its own place in the history of mathematics.

Sign variation[edit]

Let c_0, c_1, c_2, \ldots be a finite or infinite sequence of real numbers. Suppose l < r and the following conditions hold:
  1. If r = l + 1 the numbers c_l and c_r have opposite signs.
  2. If r \ge l + 2 the numbers c_{l+1}, \ldots, c_{r-1} are all zero and the numbers c_l and c_r have opposite signs.
This is called a sign variation or sign change between the numbers c_l and c_r.
When dealing with the polynomial p(x) in one variable, one defines the number of sign variations of p(x) as the number of sign variations in the sequence of its coefficients.

Budan's theorem[edit]

The following statement of Budan's theorem had disappeared from the literature (for about 150 years) due to its equivalence to the statement of Fourier's theorem.

Statement of Budan's theorem[edit]

Given an equation in x, p(x) = 0 of degree n > 0 it is possible to make two substitutions x \leftarrow x + l and x \leftarrow x + r where l and r are real numbers so that l < r. If v_l and v_r are the sign variations in the sequences of the coefficients of p(x+l) and p(x+r) respectively then, provided p(r) \ne 0, the following applies:

  1. The polynomial p(x+l) cannot have fewer sign variations than those of p(x+r). In short v_l \ge v_r
  2. The number \rho of the real roots of the equation p(x) = 0 located in the open interval (l,r) can never be more than the number of sign variations lost in passing from the transformed polynomial p(x+l) to the transformed polynomial p(x+r). In short, \rho \le v_l - v_r
  3. When the number \rho of the real roots of the equation p(x) = 0 located in the open interval (l,r) is strictly less than the number of the sign variations lost in passing from the transformed polynomial p(x+l) to the transformed polynomial p(x+r) then the difference is always an even number. In short, \rho = v_l - v_r -2\lambda where \lambda \mathbb{Z}_+.

It should also be mentioned that making use of the substitutions x \leftarrow x + l and x \leftarrow x + r, the exact number of real roots in the interval (l,r) can be found in only two cases:

  1. If there is no sign variation loss, then there are no real roots in the interval (l,r).
  2. If there is one sign variation loss, then there is exactly one real root in the interval (l,r). The inverse statement does not hold in this case.

Examples of Budan's theorem[edit]

1. Given the polynomial p(x)=x^3 -7x + 7 and the open interval (0,2), the substitutions x \leftarrow x + 0 and x \leftarrow x + 2 can be made. The resulting polynomials and the respective sign variations are:

p(x+0)=(x+0)^3 -7(x+0) + 7\Rightarrow p(x+0)=x^3 -7x + 7 , v_0=2
p(x+2)=(x+2)^3 -7(x+2) + 7\Rightarrow p(x+2)=x^3+6x+5x+1, v_2=0

Thus, from Budan's theorem \rho \le  v_0 - v_2 = 2 . Therefore, the polynomial p(x) has either two or no real roots in the open interval (0,2), a case that must be further investigated.

2. Given the same polynomial p(x)=x^3 -7x + 7 and the open interval (0,1) the substitutions x \leftarrow x + 0 and x \leftarrow x + 1 can be made. The resulting polynomials and the respective sign variations are:

p(x+0)=(x+0)^3 -7(x+0) + 7\Rightarrow p(x+0)=x^3 -7x + 7 , v_0=2
p(x+1)=(x+1)^3 -7(x+1) + 7\Rightarrow p(x+1)=x^3+3x-4x+1, v_2=2

By Budan's theorem \rho = v_0 - v_2 = 0 , i.e. there are no real roots in the open interval (0,1).

The last example indicates the main use of Budan's theorem as a "no roots test".

Fourier's theorem[edit]

The statement of Fourier's theorem (for Polynomials) which also appears as Fourier–Budan theorem or as the Budan–Fourier theorem or just as Budan's theorem can be found in almost all texts and articles on the subject.

Fourier's sequence[edit]

Given an equation in x, p(x) = 0 of degree n > 0 , the Fourier sequence of p(x), F_\text{seq}(x), is defined as the sequence of the  n + 1 functions p(x), p^{(1)}(x),\ldots,p^{(n)}(x) where p^{(i)} is the ith derivative of p(x).Thus, F_\text{seq}(x)=\big\{ p(x), p^{(1)}(x),\ldots,p^{(n)}(x)\big\}.

Example of Fourier's sequence[edit]

The Fourier sequence of the polynomial p(x)=x^3 -7x + 7 is F_\text{seq}(x)=\big\{x^3 -7x + 7,3x^2-7,6x,6\big\}.

Statement of Fourier's theorem[edit]

Given the polynomial equation x, p(x) = 0 of degree n > 0 with real coefficients and its corresponding Fourier sequence F_\text{seq}(x)=\big\{ p(x), p^{(1)}(x),\ldots,p^{(n)}(x)\big\},  x can be replaced by any two real numbers l,r (l<r). If the two resulting arithmetic sequences are represented by F_\text{seq}(l) and F_\text{seq}(r) respectively, and their corresponding sign variations by v_l, v_r, then, provided p(r) \ne 0, the following applies:

  1. The sequence F_\text{seq}(l) cannot present fewer sign variations than the sequence F_\text{seq}(r). In short, v_l \ge v_r
  2. The number \rho of the real roots of the equation p(x) = 0 located in the open interval (l,r) can never be more than the number of sign variations lost in passing from the sequence F_\text{seq}(l) to the sequence F_\text{seq}(r). In short, \rho \le v_l - v_r
  3. When the number \rho of the real roots of the equation p(x) = 0 located in the open interval (l,r) is strictly less than the number of the sign variations lost in passing from the sequence F_\text{seq}(l) to the sequence F_\text{seq}(r) then the difference is always an even number. In short, \rho = v_l - v_r -2\lambda where \lambda \in \mathbb{Z}_+

Example of Fourier's theorem[edit]

Given the previously mentioned polynomial p(x)=x^3 -7x + 7 and the open interval (0,2), the following finite sequences and the corresponding sign variations can be computed:

F_\text{seq}(0)=\big\{7,-7,0,6\big\},v_0=2
F_\text{seq}(2)=\big\{1,5,12,6\big\},v_2=0

Thus, from Fourier's theorem \rho \le v_0 - v_2 =  2 . Therefore, the polynomial p(x) has either two or no real roots in the open interval (0,2), a case which should be further investigated.

Historical background[edit]

In the beginning of the 19th century F. D. Budan and J. B. J. Fourier presented two different (but equivalent) theorems which enable us to determine the maximum possible number of real roots that an equation has within a given interval.

Budan's statement can hardly be found in the bibliography. Instead, it was replaced by Fourier's statement which is usually referred to as Fourier's theorem, or as Fourier–Budan or as Budan–Fourier or even as Budan's theorem. The actual statement of Budan's theorem appeared in 1807 in the memoir "Nouvelle méthode pour la résolution des équations numériques",[1] whereas Fourier's theorem was first published in 1820 in the "Bulletin des Sciences, par la Société Philomatique de Paris".[2] Due to the importance of these two theorems, there was a great controversy regarding priority rights; on this see [3][4] and especially Arago's book[5] p. 383.

Early applications of Budan's theorem[edit]

In "Nouvelle méthode pour la résolution des équations numériques",[1] Budan himself used his theorem to compute the roots of any polynomial equation by calculating the decimal digits of the roots. More precisely, Budan used his theorem as a "no roots test", which can be stated as follows: if the polynomials p(x+a) and p(x +a+ 1) have (in the sequence of their coefficients) the same number of sign variations then it follows (from Budan's theorem) that p(x) has no real roots in the interval (a,a+1).

Furthermore, in his book,[1] p. 37, Budan presents, independently of his theorem, a "0_1 roots test", that is a criterion for determining whether a polynomial has any roots in the interval (0,1). This test can be stated as follows:

Perform on p(x) the substitution x \longleftarrow \frac{1}{x +1} and count the number of sign variations in the sequence of coefficients of the transformed polynomial; this number gives an upper bound on the number of real roots p(x) has inside the open interval (0,1). More precisely, the number \rho_{01}(p) of real roots in the open interval (0,1) — multiplicities counted — of the polynomial p(x) \in \mathbb{R}[x], of degree deg(p), is bounded above by the number of sign variations var_{01}(p), where

var_{01}(p) = var((x+1)^{deg(p)}p(\frac{1}{x+1}))

and var_{01}(p) \ge \rho_{01}(p). As in the case of Descartes' rule of signs if var_{01}(p)=0 it follows that \rho_{01}(p)=0 and if var_{01}(p)=1 it follows that \rho_{01}(p)=1.

This test (which is a special case of the more general Alesina-Galuzzi "a_b roots test") was subsequently used by Uspensky in the 20th century.[6] (Uspensky,[7] pp. 298–303, was the one who kept Vincent's theorem alive carrying the torch (so to speak) from Serret.[8])

Bourdon,[9] in the last chapter of his 1831 Algebra (6th edition), pp. 717–760, combined Budan's theorem and Lagrange's continued fraction method for approximating real roots of polynomials and, thus, gave a preview of Vincent's method, without actually giving credit to him. As Vincent mentions in the very first sentence of his 1834[10] and 1836[11] papers, Bourdon used (in his book) a joint presentation of theirs.

Disappearance of Budan's theorem[edit]

Budan's theorem forms the basis for Vincent's theorem and Vincent's (exponential) method for the isolation of the real roots of polynomials. Therefore, there is no wonder that Vincent in both of his papers of 1834[10] and 1836[11] states Budan's theorem and contrasts it with the one by Fourier. Vincent was the last author in the 19th century to state Budan's theorem in its original form.

Despite the fact that Budan's theorem was of such great importance, the appearance of Sturm's theorem in 1827 gave it (and Vincent's theorem) the death blow. Sturm's theorem solved the real root isolation problem, by defining the precise number of real roots a polynomial has in a real open interval (a, b); moreover, Sturm himself,[12] p. 108, acknowledges the great influence Fourier's theorem had on him: « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer. » which translates to «It is by relying upon the principles he has laid out and by imitating his proofs that I have found the new theorems which I am about to announce.» . Because of the above, the theorems by Fourier and Sturm appear in almost all the books on the theory of equations and Sturm's method for computing the real roots of polynomials has been the only one widely known and used ever since – up to about 1980, when it was replaced (in almost all computer algebra systems) by methods derived from Vincent's theorem, the fastest one being the Vincent–Akritas–Strzeboński (VAS) method.[13]

Consequently Budan's theorem (but not his name) was pushed into oblivion. Referentially, in Serret's book[8] there is section 121 (p. 266) on Budan's theorem but the statement is the one due to Fourier, because, as the author explains in the footnote of p. 267 , the two theorems are equivalent and Budan had clear priority. To his credit, Serret included in his Algebra,[8] pp 363–368, Vincent's theorem along with its proof and directed all interested readers to Vincent's papers for examples on how it is used. Serret was the last author to mention Vincent's theorem in the 19th century.

Comeback of Budan's theorem[edit]

Budan's theorem reappeared, after almost 150 years, in Akritas' Ph.D. Thesis "Vincent's Theorem in Algebraic Manipulation", North Carolina State University, USA, 1978, and in several publications that resulted from that dissertation.[3][4] Akritas found the statement of Budan's theorem in Vincent's paper of 1836,[11] which was made available to him through the efforts of a librarian in the Library of the University of Wisconsin–Madison, USA.

Equivalence between the theorems by Budan and Fourier[edit]

Budan's theorem is equivalent to the one by Fourier. This equivalence is obvious from the fact that, given the polynomial p(x) of degree n > 0 , the n+1 terms of the Fourier sequence F_\text{seq}(a) (obtained by substituting x \leftarrow a in F_\text{seq}(x)) have the same signs with (and are proportional to) the corresponding coefficients of the polynomial p(x+a)=\sum_{i=1}^n \frac{p^{(i)}(a)}{i!}\ x^i, obtained from Taylor's expansion theorem.

As Alesina and Galuzzi point out in Footnote 9, p. 222 of their paper,[14] the controversy over priority rights of Budan or Fourier is rather pointless from a modern point of view. The two authors think that Budan has an "amazingly modern understanding of the relevance of reducing the algorithm (his own word) to translate a polynomial by x \leftarrow x+p, where p is an integer, to simple additions".

Despite their equivalence, the two theorems are quite distinct concerning the impact they had on the isolation of the real roots of polynomials with rational coefficients. To wit:

Xcas is a computer algebra system where Sturm's method and VAS are both implemented and can be compared; to do so use the functions realroot(poly) and time(realroot(poly)). By default, to isolate the real roots of poly realroot uses the VAS method; to use Sturm's method write realroot(sturm, poly). See also the External links for two applications that do the same thing: one for Android devices by A. Berkakis and another one for the Apple devices iPhone/iPod/iPad by S. Kehagias.

The most significant application of Budan's theorem[edit]

Vincent's (exponential) method for the isolation of the real roots of polynomials (which is based on Vincent's theorem of 1834 and 1836)[10][11] is the most significant application of Budan's theorem. Moreover, it is the most representative example of the importance of the statement of Budan's theorem. As explained below, knowing the statement of Fourier's theorem did not help Uspensky realize that there are no roots of p(x) in the open interval (a, a+1) if p(x + a) and p(x + a + 1) have the same number of sign variations in the sequence of their coefficients (see,[7] pp. 127–137).

Vincent's theorem (1834 and 1836)[edit]

If in a polynomial equation with rational coefficients and without multiple roots, one makes successive transformations of the form

x = a + \frac{1}{x'},\quad x' = b + \frac{1}{x''},\quad x'' = c + \frac{1}{x'''}, \ldots

where a, b, and c are any positive numbers greater than or equal to one, then after a number of such transformations, the resulting transformed equation either has zero sign variations or it has a single sign variation. In the first case there is no root, whereas in the second case there is a single positive real root. Furthermore, the corresponding root of the proposed equation is approximated by the finite continued fraction:[10][11][15]

a + \cfrac{1}{b + \cfrac{1}{c + \cfrac{1}{\ddots}}}

Finally, if infinitely many numbers satisfying this property can be found, then the root is represented by the (infinite) corresponding continuous fraction.


The above statement is an exact translation of the theorem found in Vincent's original papers;[10][11][15] for a clearer understanding see the remarks in the Wikipedia article Vincent's theorem

Vincent's implementation of his own theorem[edit]

Vincent's search for a root (applying Budan's theorem)

Vincent uses Budan's theorem exclusively as a "no roots test" to locate where the roots lie on the x-axis (to compute the quantities a,b,c ,\ldots of his theorem); that is, to find the integer part of a root Vincent performs successively substitutions of the form x \leftarrow 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).[10][11]

See the corresponding diagram where the root lies in the interval (5,6). Since in general the location of the root is not known in advance, the root can be found (with the help of Budan's theorem) only by this decrease in the number of sign variations; that is, the polynomial p(x+6) has fewer sign variations than the polynomial p(x+5). Vincent then easily obtains a first continued fraction approximation to this root as x = 5 +\frac{1}{x'} as stated in his theorem. Vincent performs those, and only those, transformations that are described in his theorem.

Uspensky's implementation of Vincent's theorem[edit]

According to Alexei Uteshev[16] of St. Petersburg University, Russia, Uspensky came upon the statement (and proof) of Vincent's theorem in the 20th century in Serret's Algebra,[8] pp 363–368, which means that he was not aware of the statement of Budan's theorem (because Serret included in his book Fourier's theorem). Moreover, this means that Uspensky never saw Vincent's papers of 1834[10] and 1836,[11] where Budan's theorem is stated and Vincent's method is explained with several examples (because Serret directed all interested readers to Vincent's papers for examples on how the theorem is used). Therefore, in the preface of his book that came out in 1949,[7] Uspensky erroneously claimed that, based on Vincent's theorem, he had discovered a method for isolating the real roots "much superior in practice to that based on Sturm's Theorem". Uspensky's statement is erroneous because, since he is not using Budan's theorem, he is isolating the real roots doing twice the amount of work done by Vincent (see,[7] pp. 127–137). Despite this misunderstanding, kudos to Uspensky for keeping Vincent's theorem alive.
Uspensky's search for a root (not applying Budan's theorem)

Uspensky does not know Budan's theorem and, hence, he cannot use it as a "no roots test". So, for him it does not suffice that  p(x + 1) has the same number of sign variations as p(x) in order to conclude that p(x) has no roots inside (0,1); to make sure, he also performs the redundant substitution (Budan's "0_1 roots test") x \leftarrow \frac{1}{1+x} in p(x), which unfailingly results in a polynomial with no sign variations and hence no positive roots. Uspensky uses the information obtained from both the needed transformation x \leftarrow x + 1 and the not needed one x \leftarrow \frac{1}{1+x} to realize that p(x) has no roots in the interval (0,1). In other words, searching for a root, Uspensky advances as illustrated in the corresponding figure.

Uspensky's transformations are not the ones described in Vincent's theorem, and consequently, his transformations take twice as much computation time as the ones needed for Vincent's method.[6][16]

See also[edit]

References[edit]

  1. ^ a b c Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier. 
  2. ^ Fourier, Jean Baptiste Joseph (1820). "Sur l'usage du théorème de Descartes dans la recherche des limites des racines". Bulletin des Sciences, par la Société Philomatique de Paris: 156–165. 
  3. ^ a b Akritas, Alkiviadis G. (1981). "On the Budan–Fourier Controversy". ACM-SIGSAM Bulletin 15 (1): 8–10. doi:10.1145/1089242.1089243. 
  4. ^ a b Akritas, Alkiviadis G. (1982). "Reflections on a Pair of Theorems by Budan and Fourier". Mathematics Magazine 55 (5): 292–298. doi:10.2307/2690097. 
  5. ^ Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation) 
  6. ^ a b Akritas, Alkiviadis G. (1986). There is no "Uspensky's Method". In: Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86, Waterloo, Ontario, Canada), pp. 88–90. 
  7. ^ a b c d Uspensky, James Victor (1948). Theory of Equations. New York: McGraw–Hill Book Company. 
  8. ^ a b c d Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. 
  9. ^ Bourdon, Louis Pierre Marie (1831). Éléments d'Algèbre. Paris: Bachelier Père et Fils (6th edition). 
  10. ^ a b c d e f g Vincent, Alexandre Joseph Hidulph (1834). "Mémoire sur la résolution des équations numériques". Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille: 1–34. 
  11. ^ a b c d e f g h Vincent, Alexandre Joseph Hidulph (1836). "Sur la résolution des équations numériques". Journal de Mathématiques Pures et Appliquées 1: 341–372. 
  12. ^ a b Hourya, Benis-Sinaceur (1988). "Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm". Revue d'histoire des sciences 41 (2): 99–132. 
  13. ^ a b Akritas, Alkiviadis G.; A.W. Strzeboński, P.S. Vigklas (2008). "Improving the performance of the continued fractions method using new bounds of positive roots". Nonlinear Analysis: Modelling and Control 13: 265–279. 
  14. ^ Alesina, Alberto; Massimo Galuzzi (1998). "A new proof of Vincent's theorem". L'Enseignement Mathématique 44 (3-4): 219–256. 
  15. ^ a b Vincent, Alexandre Joseph Hidulph (1838). "Addition à une précédente note relative à la résolution des équations numériques". Journal de Mathématiques Pures et Appliquées 3: 235–243. 
  16. ^ a b Akritas, Alkiviadis G. (2008). There is no "Descartes' method". In: M.J.Wester and M. Beaudin (Eds), Computer Algebra in Education, AullonaPress, USA, pp. 19–35. 

External links[edit]