Budan's theorem

In mathematics, Budan's theorem is a theorem for bounding the number of real roots of a polynomial in an interval, and computing the parity of this number. It was published in 1807 by François Budan de Boislaurent.

A similar theorem was published independently by Joseph Fourier in 1820. Each of these theorems are a corollary of the other. Fourier's statement appears more often in the literature of 19th century and has been referred to as Fourier's, Budan–Fourier, Fourier–Budan, and even Budan's theorem

Budan's original formulation is used in fast modern algorithms for real-root isolation of polynomials.

Sign variation

Let $c_{0},c_{1},c_{2},\ldots c_{k}$ be a finite sequence of real numbers. A sign variation or sign change in the sequence is a pair of indices $i < j$ such that $c_{i}c_{j}<0,$ and either $j = i + 1$ or $c_{k}=0$ for all $k$ such that $i < k < j$ .

In other words, a sign variation occurs in the sequence at each place where the signs change, when ignoring zeros.

For studying the real roots of a polynomial, the number of sign variations of several sequences may be used. For Budan's theorem, it is the sequence of the coefficients. For the Budan–Fourier theorem, it is the sequence of values of the successive derivatives at a point. For Sturm's theorem it is the sequence of values at a point of the Sturm sequence.

Descartes' rule of signs

All results described in this article are based on Descartes' rule of signs.

If $p (x)$ is a univariate polynomial with real coefficients, let us denote by $# + (p)$ the number of its positive real roots, counted with their multiplicity,[1] and by $v (p)$ the number of sign variations in the sequence of its coefficients. Descartes's rule of signs asserts that

v (p) - # + (p)

is a nonnegative even integer.

In particular, if $v (p) \leq 1$ , then one has $# + (p) = v (p)$ .

Budan's statement

Given a univariate polynomial $p (x)$ with real coefficients, let us denote by $# (ℓ, r] (p)$ the number of real roots, counted with their multiplicities,[1] of $p$ in a half-open interval $(ℓ, r]$ (with $ℓ < r$ real numbers). Let us denote also by $v h (p)$ the number of sign variations in the sequence of the coefficients of the polynomial $p h (x) = p (x + h)$ . In particular, one has $v (p) = v 0 (p)$ with the notation of the preceding section.

Budan's theorem is the following:

v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}

is a nonnegative even integer.

As $\#_{(\ell ,r]}$ is non negative, this implies $v_{\ell }(p)\geq v_{r}(p).$

This is a generalization of Descartes' rule of signs, as, if one chooses $r$ sufficiently large, it is larger than all real roots of $p$ , and all the coefficients of $p_{r}(x)$ are positive, that is $v_{r}(p)=0.$ Thus $v_{0}(p)=v_{0}(p)-v_{r}(p),$ and $\#_{+}=\#_{(0,r)},$ which makes Descartes' rule of signs a special case of Budan's theorem.

As for Descartes' rule of signs, if $v_{\ell }(p)-v_{r}(p)\leq 1,$ one has $\#_{(\ell ,r]}=v_{\ell }(p)-v_{r}(p).$ This means that, if $v_{\ell }(p)-v_{r}(p)\leq 1$ one has a "zero-root test" and a "one-root test".

Examples

1. Given the polynomial $p(x)=x^{3}-7x+7,$ and the open interval $(0,2)$ , one has

{\begin{aligned}p(x+0)&=p(x)=x^{3}-7x+7\\p(x+2)&=(x+2)^{3}-7(x+2)+7=x^{3}+6x^{2}+5x+1\end{aligned}}.

Thus, $v_{0}(p)-v_{2}(p)=2-0=2,$ and Budan's theorem asserts that the polynomial $p(x)$ has either two or zero real roots in the open interval $(0,2).$

2. With the same polynomial $p(x)=x^{3}-7x+7$ one has

p(x+1)=(x+1)^{3}-7(x+1)+7=x^{3}+3x^{2}-4x+1.

Thus, $v_{0}(p)-v_{1}(p)=2-2=0,$ and Budan's theorem asserts that the polynomial $p(x)$ has no real root in the open interval $(0,1).$ This is an example of the use of Budan's theorem as a zero-root test.

Fourier's statement

Fourier's theorem on polynomial real roots, also called Fourier–Budan theorem or Budan–Fourier theorem (sometimes just Budan's theorem) is exactly the same as Budan's theorem, except that, for $h = l$ and $r$ , the sequence of the coefficients of $p (x + h)$ is replaced by the sequence of the derivatives of $p$ at $h$ .

Each theorem is a corollary of the other. This results from the Taylor expansion

p(x)=\sum _{i=0}^{\deg p}{\frac {p^{(i)}(h)}{i!}}(x-h)^{i}

of the polynomial $p$ at $h$ , which implies that the coefficient of $x i$ in $p (x + h)$ is the quotient of $p^{(i)}(h)$ by $i!$ , a positive number. Thus the sequences considered in Fourier's theorem and in Budan's theorem have the same number of sign variations.

This strong relationship between the two theorems may explain the priority controversy that occurred in 19th century, and the use of several names for the same theorem. In modern usage, for computer computation, Budan's theorem is generally preferred since the sequences have much larger coefficients in Fourier's theorem than in Budan's, because of the factorial factor.

Proof

As each theorem is a corollary of the other, it suffices to prove Fourier's theorem.

Thus, consider a polynomial $p (x)$ , and an interval $(l, r]$ . When the value of $x$ increases from $l$ to $r$ , the number of sign variations in the sequence of the derivatives of $p$ may change only when the value of $x$ pass through a root of $p$ or one of its derivatives.

Let us denote by $f$ either the polynomial $p$ or any of its derivatives. For any root $h$ of multiplicity $m$ of $f$ , this polynomial is well approximated near $h$ by $a(x-h)^{m}$ for some constant $a$ . Moreover, for $i = 1, ..., m$ , its $i$ th derivative is approximated by $\textstyle a(x-h)^{m-i}\prod _{j=1}^{i}(m-j+1).$ It follows that, in the sequence formed by $f$ and its $m$ first derivatives, there are $m$ sign variations for $x < h$ and zero for $x \geq h$ .

This shows that, when $x$ increases and passes through a root of $p$ of multiplicity $m$ , then the number of sign variations in the sequence of the derivative decreases by $m$ .

Now, for $i > 0$ , let $h$ be a root of the $i$ th derivative $f=p^{(i)}$ of $p$ , which is not a root of $p^{(i-1)}.$ There are two cases to be considered. If the multiplicity $m$ of the root $h$ is even, then $f=p^{(i)}$ and $p^{(i-1)}$ keep a constant sign when $x$ pass through $h$ . This implies that the number of sign of variation in the sequence of derivatives decrease by the even number $m$ . On the other hand, if $m$ is odd, $f=p^{(i)}$ changes of sign at $h$ , while $p^{(i-1)}$ does not. There are thus $m + 1$ sign variations. Thus, when $x$ pass through $h$ , the number of sign variation decrease either of $m$ or $m + 1$ , which are nonnegative even numbers in each case.

History

The problem of counting and locating the real roots of a polynomial started to be systematically studied only in the beginning of the 19th.

In 1807, François Budan de Boislaurent discovered a method for extending Descartes' rule of signs—valid for the interval $(0, +\infty)$ —to any interval.[2]

Joseph Fourier published a similar theorem in 1820,[3] on which he worked for more than twenty years.[4]

Because of the similarity between the two theorems, there was a priority controversy,[5][6] despite the fact that the two theorems were discovered independently.[4] It was generally Fourier's formulation and proof that were used, during the 19th century, in textbooks on the theory of equations.

Use in 19th century

Budan's and Fourier's theorems were soon considered of a great importance, although they do not solve completely the problem of counting the number of real roots of a polynomial in an interval. This problem was completely solved in 1827 by Sturm.

Although Sturm's theorem is not based on Descartes' rule of signs, Sturm's and Fourier's theorems are related not only by the use of the number of sign variations of a sequence of numbers, but also by a similar approach of the problem. Sturm himself acknowledged having been inspired by Fourier's methods:[7] « 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 into « 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 this, during the 19th century, Fourier's and Sturm's theorems appeared together in almost all books on the theory of equations.

Fourier and Budan left open the problem of reducing the size of the intervals in which roots are searched in a way that, eventually, the difference between the numbers of sign variations is at most one, allowing certifying that the final intervals contains at most one root each. This problem was solved in 1834 by Alexandre Joseph Hidulph Vincent.[8] Roughly speaking, Vincent's theorem consists of using continued fractions for replacing Budan's linear transformations of the variable by Möbius transformations.

Budan's, Fourier's and Vincent theorem sank into oblivion at the end of 19th century. The last author mentioning these theorems before the second half of 20th century Joseph Alfred Serret.[9] They were introduced again in 1976 by Collins and Akritas, for providing, in computer algebra, an efficient algorithm for real roots isolation on computers.[10]

References

This means that a root of multiplicity $m$ is counted as $m$ roots.
Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier.
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.
Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383
Akritas, Alkiviadis G. (1981). "On the Budan–Fourier Controversy". ACM SIGSAM Bulletin. 15 (1): 8–10. doi:10.1145/1089242.1089243.
Akritas, Alkiviadis G. (1982). "Reflections on a Pair of Theorems by Budan and Fourier". Mathematics Magazine. 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097.
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): 108.
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.
Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368.
Collins, G. E.; Akritas, A. G. (1976). Polynomial real root isolation using Descarte's rule of signs. Proceedings of the 1976 ACM symposium on Symbolic and Algebraic Computation. pp. 272–275.

External links

O'Connor, John J.; Robertson, Edmund F., "Budan de Boislaurent", MacTutor History of Mathematics archive, University of St Andrews.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[mult-1] This means that a root of multiplicity $m$ is counted as $m$ roots.

[nmethode-2] Budan, François D. (1807). Nouvelle méthode pour la résolution des équations numériques. Paris: Courcier.

[Fourier-3] 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.

[arago-4] Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383

[BF-5] Akritas, Alkiviadis G. (1981). "On the Budan–Fourier Controversy". ACM SIGSAM Bulletin. 15 (1): 8–10. doi:10.1145/1089242.1089243.

[Reflections-6] Akritas, Alkiviadis G. (1982). "Reflections on a Pair of Theorems by Budan and Fourier". Mathematics Magazine. 55 (5): 292–298. doi:10.2307/2690097. JSTOR 2690097.

[Sturm-7] 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): 108.

[paper_1834-8] 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.

[Serret-9] Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368.

[10] Collins, G. E.; Akritas, A. G. (1976). Polynomial real root isolation using Descarte's rule of signs. Proceedings of the 1976 ACM symposium on Symbolic and Algebraic Computation. pp. 272–275.