Budan's theorem

In mathematics, Budan's theorem, named for François Budan de Boislaurent, is an early 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 Joseph Fourier, and the latter has been referred to under various names, including Budan's. Budan's original theorem forms the basis of the fastest known method for the isolation of the real roots of polynomials.

Sign variation

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$.

For a univariate polynomial $p(x)$, the number of sign variations of $p(x)$ is defined as the number of sign variations in the sequence of its coefficients.

Budan's theorem

Budan's theorem is equivalent to Fourier's theorem. Though Budan's formulation preceded Fourier's, the name Fourier has usually been associated with it.

Statement of Budan's theorem

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}_+$.

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

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$ give:

$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^2+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$ give:

$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^2-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

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

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

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

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

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

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 formulation is rarely cited. Instead, Fourier's formulation is usually used, and named the Fourier, Fourier–Budan, Budan–Fourier, or even 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", whereas Fourier's theorem was first published in 1820 in the "Bulletin des Sciences, par la Société Philomatique de Paris". Due to the importance of these two theorems, there was a great controversy regarding priority rights.

Early applications of Budan's theorem

In "Nouvelle méthode pour la résolution des équations numériques", 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 Budan's theorem states that $p(x)$ has no real roots in the interval $(a,a+1)$.

Furthermore, in his book, 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. Uspensky was the one who kept Vincent's theorem alive carrying the torch (so to speak) from Serret.,)

In 1831, Bourdon, 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 papers, and 1836 Bourdon used (in his book) a joint presentation of theirs.

Disappearance of Budan's theorem

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 and 1836 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, 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 present.» 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.

Consequently, Budan's theorem (but not his name) was pushed into oblivion. In Serret's book 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, 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

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.

Equivalence between the theorems by Budan and Fourier

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=0}^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, 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:

• Fourier's theorem led Sturm to his theorems and method, whereas
• Budan's theorem is the basis of the Vincent–Akritas–Strzeboński (VAS) method.

The most significant application of Budan's theorem

Vincent's (exponential) method for the isolation of the real roots of polynomials (which is based on Vincent's theorem of 1834 and 1836) 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, pp. 127–137).

Vincent's theorem (1834 and 1836)

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:

$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; for a clearer understanding see the remarks in the Wikipedia article Vincent's theorem

Vincent's implementation of his own theorem

File:Vincent method.jpg

450px

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).

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

According to Alexei Uteshev of St. Petersburg University, Russia, Uspensky came upon the statement (and proof) of Vincent's theorem in the 20th century in Serret's Algebra, 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 and 1836, 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, 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, pp. 127–137).

File:Uspensky attempt.jpg

450px

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.

See also

• Properties of polynomial roots
• Root-finding algorithm
• Sturm's theorem
• Vieta's formulas
• Newton's method

External links

• Budan, F.: extended Biography http://www-history.mcs.st-andrews.ac.uk/Biographies/Budan_de_Boislaurent.html
• Encyclopedia of Mathematics http://www.encyclopediaofmath.org/index.php/Budan-Fourier_theorem