Jump to content

Budan's theorem: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Rescuing 1 sources and tagging 0 as dead. #IABot (v2.0beta10)
(29 intermediate revisions by 2 users not shown)
Line 1: Line 1:
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 [[sequence]]s of coefficients.
In mathematics, '''Budan's theorem''' is a theorem for bounding the number of real roots a polynomial in interval, and computing the [[parity (mathematics)|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
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.

Budan's original formulation is used in fast modern algorithms for isolating real roots of polynomials.


==Sign variation==
==Sign variation==
:Let <math>c_0, c_1, c_2, \ldots </math> be a finite or infinite sequence of real numbers. Suppose <math>l < r</math> and the following conditions hold:
Let <math>c_0, c_1, c_2, \ldots c_k</math> be a finite sequence of real numbers. A ''sign variation'' or ''sign change'' in the sequence is a pair of indices {{math|''i'' < ''j''}} such that <math>c_ic_j<0,</math> and either {{math|1=''j'' = ''i'' + 1}} or <math>c_k=0</math> for all {{mvar|k}} such that {{math|''i'' < ''k'' < ''j''}}.
# If <math>r = l + 1</math> the numbers <math>c_l</math> and <math>c_r</math> have opposite signs.
# If <math>r \ge l + 2</math> the numbers <math>c_{l+1}, \ldots, c_{r-1}</math> are all zero and the numbers <math>c_l</math> and <math>c_r</math> have opposite signs.
: This is called a ''sign variation'' or ''sign change'' between the numbers <math>c_l</math> and <math>c_r</math>.
: For a univariate polynomial <math>p(x)</math>, the number of sign variations of <math>p(x)</math> is defined as the number of sign variations in the sequence of its coefficients.

==Budan's theorem==
Budan's theorem is equivalent to [[Budan's theorem#Fourier's theorem|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 <math>x</math>, <math>p(x) = 0</math> of degree <math>n > 0</math>, it is possible to make two substitutions <math>x \leftarrow x + l</math> and <math>x \leftarrow x + r</math> where <math>l</math> and <math>r</math> are real numbers so that <math>l < r</math>. If <math>v_l</math> and <math>v_r</math> are the [[Budan's theorem#Sign variation|sign variations]] in the sequences of the coefficients of <math>p(x+l)</math> and <math>p(x+r)</math> respectively then, provided <math>p(r) \ne 0</math>, the following applies:

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

Making use of the substitutions <math>x \leftarrow x + l</math> and <math>x \leftarrow x + r</math>, the exact number of real roots in the interval <math>(l,r)</math> can be found in only two cases:

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

=== Examples of Budan's theorem ===
1. Given the polynomial <math>p(x)=x^3 -7x + 7 </math> and the open interval <math>(0,2)</math>, the substitutions <math>x \leftarrow x + 0</math> and <math>x \leftarrow x + 2</math> give:

: <math>p(x+0)=(x+0)^3 -7(x+0) + 7\Rightarrow p(x+0)=x^3 -7x + 7 , v_0=2</math>

: <math>p(x+2)=(x+2)^3 -7(x+2) + 7\Rightarrow p(x+2)=x^3+6x^2+5x+1, v_2=0</math>

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

2. Given the same polynomial <math>p(x)=x^3 -7x + 7 </math> and the open interval <math>(0,1)</math> the substitutions <math>x \leftarrow x + 0</math> and <math>x \leftarrow x + 1</math> give:

: <math>p(x+0)=(x+0)^3 -7(x+0) + 7\Rightarrow p(x+0)=x^3 -7x + 7 , v_0=2</math>

: <math>p(x+1)=(x+1)^3 -7(x+1) + 7\Rightarrow p(x+1)=x^3+3x^2-4x+1, v_2=2</math>

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

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 <math>x</math>, <math>p(x) = 0</math> of degree <math>n > 0</math> , the '''Fourier sequence''' of <math>p(x)</math>, <math>F_\text{seq}(x)</math>, is defined as the sequence of the <math> n + 1 </math> functions <math>p(x), p^{(1)}(x),\ldots,p^{(n)}(x)</math> where <math>p^{(i)}</math> is the ith derivative of <math>p(x)</math>.Thus, <math>F_\text{seq}(x)=\big\{ p(x), p^{(1)}(x),\ldots,p^{(n)}(x)\big\}</math>.

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

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

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

====Example of Fourier's theorem====
Given the previously mentioned polynomial <math>p(x)=x^3 -7x + 7 </math> and the open interval <math>(0,2)</math>, the following finite sequences and the corresponding [[Budan's theorem#Sign variation|sign variations]] can be computed:

: <math>F_\text{seq}(0)=\big\{7,-7,0,6\big\},v_0=2</math>

: <math>F_\text{seq}(2)=\big\{1,5,12,6\big\},v_2=0</math>

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

==Historical background==
In the beginning of the 19th century, [[François Budan de Boislaurent|F. D. Budan]] and [[Joseph Fourier|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",<ref name=nmethode>{{cite book|last=Budan|first=François D.|title=Nouvelle méthode pour la résolution des équations numériques|year=1807|publisher=Courcier|location=Paris|url=https://books.google.com/books?id=VyMOAAAAQAAJ&redir_esc=y}}</ref> whereas Fourier's theorem was first published in 1820 in the "Bulletin des Sciences, par la Société Philomatique de Paris".<ref name=Fourier>{{cite journal|last=Fourier|first=Jean Baptiste Joseph|title=Sur l'usage du théorème de Descartes dans la recherche des limites des racines|year=1820|journal=Bulletin des Sciences, par la Société Philomatique de Paris|pages=156–165|url=https://archive.org/details/bulletindesscien20soci}}</ref> Due to the importance of these two theorems, there was a great controversy regarding priority rights.<ref name=BF>{{cite journal|last=Akritas|first=Alkiviadis G.|title=On the Budan–Fourier Controversy|url=http://dl.acm.org/citation.cfm?id=1089243|journal=ACM SIGSAM Bulletin|year=1981|volume=15|number=1|pages=8–10|doi=10.1145/1089242.1089243}}</ref><ref name=Reflections>{{cite journal|last=Akritas|first=Alkiviadis G.|title=Reflections on a Pair of Theorems by Budan and Fourier|jstor=2690097|year=1982|journal=Mathematics Magazine|volume=55|number=5|pages=292–298|doi=10.2307/2690097}}</ref><ref>{{citation|last=Arago|first=François|title=Biographies of distinguished scientific men|year=1859|publisher=Ticknor and Fields (English Translation)|page=383|location=Boston|url=https://books.google.com/books?id=xGgSAAAAIAAJ&redir_esc=y}}</ref>


In other words, a sign variation occurs in the sequence at each place where the signs change, when ignoring zeros.
=== Early applications of Budan's theorem ===
In "Nouvelle méthode pour la résolution des équations numériques",<ref name="nmethode"/> 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 <math>p(x+a)</math> and <math>p(x +a+ 1)</math> have (in the sequence of their coefficients) the same number of sign variations, then Budan's theorem states that <math>p(x)</math> has no real roots in the interval <math>(a,a+1)</math>.


For studying the real roots of a polynomial, the number of sign variations of several sequences may used. For Budan's theorem, its 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]].
Furthermore, in his book,<ref name="nmethode"/> p.&nbsp;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:


==Descartes' rule of signs==
Perform on <math>p(x)</math> the substitution <math>x \longleftarrow \frac{1}{x +1} </math> 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 <math>p(x)</math> has inside the open interval <math>(0,1)</math>. More precisely, the number <math>\rho_{01}(p)</math> of real roots in the open interval <math>(0,1)</math> — multiplicities counted — of the polynomial <math>p(x) \in \mathbb{R}[x]</math>, of degree <math>\deg(p)</math>, is bounded above by the number of sign variations <math>\operatorname{var}_{01}(p)</math>, where
{{main|Descartes' rule of signs}}


All results described in this articles are based on Descartes' rule of signs.
:<math>\operatorname{var}_{01}(p) = \operatorname{var}((x+1)^{\deg(p)}p(\frac{1}{x+1}))</math>


If {{math|''p''(''x'')}} is a [[univariate polynomial]] with real coefficients, let us denote by {{math|#<sub>+</sub>(''p'')}} the number of its positive real roots and by {{math|''v''(''p'')}} the number of sign variations in the sequence of its coefficients. [[Descartes]]'s rule of signs asserts that
and <math>\operatorname{var}_{01}(p) \ge \rho_{01}(p)</math>. As in the case of [[Descartes' rule of signs]] if <math>\operatorname{var}_{01}(p)=0</math> it follows that <math>\rho_{01}(p)=0</math> and if <math>\operatorname{var}_{01}(p)=1</math> it follows that <math>\rho_{01}(p)=1</math>.
:{{math|''v''(''p'') – #<sub>+</sub>(''p'')}} is a nonnegative even integer.


In particular, if {{math|''v''(''p'') ≤ 1}}, then one has {{math|1=#<sub>+</sub>(''p'') = ''v''(''p'')}}.
This test (which is a special case of the more general [[Vincent's theorem#The Alesina–Galuzzi "a b roots test"|Alesina–Galuzzi "'''a_b roots test'''"]]) was subsequently used by [[J. V. Uspensky|Uspensky]] in the 20th century.<ref name="akritas">{{cite book|last=Akritas|first=Alkiviadis G.|title=There is no "Uspensky's Method"|url=http://dl.acm.org/citation.cfm?id=32457|year=1986|publisher=In: Proceedings of the fifth ACM Symposium on Symbolic and Algebraic Computation (SYMSAC '86, Waterloo, Ontario, Canada), pp. 88–90}}</ref> [[J. V. Uspensky|Uspensky]] was the one who kept [[Budan's theorem#Vincent's theorem (1834 and 1836)|Vincent's theorem]] alive carrying the torch (so to speak) from Serret.,<ref name=Uspensky>{{cite book|last=Uspensky|first=James Victor|title=Theory of Equations|year=1948|publisher=McGraw–Hill Book Company|location=New York|url=http://www.google.com/search?q=uspensky+theory+of+equations&btnG=Search+Books&tbm=bks&tbo=1}}, pp.&nbsp;298–303</ref><ref name=Serret>{{cite book|last=Serret|first=Joseph A.|title=Cours d'algèbre supérieure. Tome I|year=1877|publisher=Gauthier-Villars|url=https://archive.org/details/coursdalgbresu01serruoft}}</ref>)


==Budan's statement ==
In 1831, Bourdon,<ref>{{cite book|last=Bourdon|first=Louis Pierre Marie|title=Éléments d'Algèbre|year=1831|publisher=Bachelier Père et Fils (6th edition)|location=Paris|url=https://archive.org/details/elementsalgebra00bourgoog}}, pp.&nbsp;717–760</ref> combined Budan's theorem and [[Joseph Louis Lagrange|Lagrange's]] [[Joseph Louis Lagrange#Continued fractions|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,<ref name=paper_1834>{{cite journal|last=Vincent|first=Alexandre Joseph Hidulph|title=Mémoire sur la résolution des équations numériques|url=http://gallica.bnf.fr/ark:/12148/bpt6k57787134/f4.image.r=Agence%20Rol.langEN|journal=Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille|year=1834|pages=1–34}}</ref> and 1836<ref name=paper_1836>{{cite journal|last=Vincent|first=Alexandre Joseph Hidulph|title=Sur la résolution des équations numériques|url=http://www-mathdoc.ujf-grenoble.fr/JMPA/PDF/JMPA_1836_1_1_A28_0.pdf|journal=Journal de Mathématiques Pures et Appliquées|volume=1|year=1836|pages=341–372|access-date=2012-04-09|archive-url=https://web.archive.org/web/20110902192058/http://www-mathdoc.ujf-grenoble.fr/JMPA/PDF/JMPA_1836_1_1_A28_0.pdf#|archive-date=2011-09-02|dead-url=yes|df=}}</ref> Bourdon used (in his book) a joint presentation of theirs.
Given a [[univariate polynomial]] {{math|''p''(''x'')}} with real coefficients, let us denote by {{math|#<sub>(''l'',''r'')</sub>(''p'')}} the number of real roots of {{mvar|p}} in an [[open interval]] {{math|(''l'', ''r'')}} (with {{math|''l'' < ''r''}} real numbers). Let us denote also by {{math|''v''<sub>''h''</sub>(''p'')}} the number of sign variations in the sequence of the coefficients of the polynomial {{math|1=''p''<sub>''h''</sub>(''x'') = ''p''(''x'' + ''h'')}}. In particular one has {{math|1=''v''(''p'') = ''v''<sub>0</sub>(''p'')}} with the notation of the preceding section.


=== Disappearance of Budan's theorem ===
Budan's theorem is the following:
:<math>v_l(p)-v_r(p)-\#_{(l,r)}</math> is a nonnegative even integer.
Budan's theorem forms the basis for [[Budan's theorem#Vincent's theorem (1834 and 1836)|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<ref name="paper_1834"/> and 1836<ref name="paper_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.


As <math>\#_{(l,r)}</math> is non negative, this implies <math>v_l(p)\ge v_r(p).</math>
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 [[Vincent's theorem#Real root isolation methods derived from Vincent's theorem|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,<ref name=Sturm>{{cite journal|last=Hourya|first=Benis-Sinaceur|title=Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm|journal= Revue d'histoire des sciences|year=1988|volume=41|number=2|pages=99–132|url=http://www.persee.fr/web/revues/home/prescript/article/rhs_0151-4105_1988_num_41_2_4093}}</ref> p.&nbsp;108, acknowledges the great influence [[Budan's theorem#Fourier's theorem|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 system]]s) by [[Vincent's theorem#Real root isolation methods derived from Vincent's theorem|methods derived from Vincent's theorem]], the fastest one being the [[Vincent's theorem#Vincent–Akritas–Strzeboński (VAS, 2005)|Vincent–Akritas–Strzeboński]] (VAS) method.<ref name=VAS>{{cite journal|last=Akritas|first=Alkiviadis G. |author2=A.W. Strzeboński |author3=P.S. Vigklas|title=Improving the performance of the continued fractions method using new bounds of positive roots|journal=Nonlinear Analysis: Modelling and Control|year=2008|volume=13|pages=265–279|url=http://www.lana.lt/journal/30/Akritas.pdf}}</ref>


This is a generalization of Descartes' rule of signs, as, if one chooses {{mvar|r}} sufficiently large, it is larger than all real roots of {{mvar|p}}, and all the coefficients of <math>p_r(x)</math> are positive, that is <math>v_r(p)=0.</math> Thus <math>v_0(p)= v_0(p)- v_r(p),</math> and <math>\#_{(0,+\infty)} = \#_{(0,r)},</math> which makes Descartes' rule of signs as special case of Budan's theorem.
Consequently, Budan's theorem (but not his name) was pushed into oblivion. In [[Joseph Alfred Serret|Serret]]'s book<ref name="Serret"/> there is section 121 (p.&nbsp;266) on Budan's theorem but the statement is the one due to Fourier, because, as the author explains in the footnote of p.&nbsp;267, the two theorems are equivalent and Budan had clear priority. To his credit, Serret included in his Algebra,<ref name="Serret"/> pp 363–368, [[Budan's theorem#Vincent's theorem (1834 and 1836)|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 [[Budan's theorem#Vincent's theorem (1834 and 1836)|Vincent's theorem]] in the 19th century.


As for Descartes' rule of signs, if <math>v_l(p)-v_r(p)\le 1,</math> one has <math>\#_{(l,r)}=v_l(p)-v_r(p).</math> This means that, if <math>v_l(p)-v_r(p)\le 1</math> one has a "zero-root test" and a "one-root test".
=== Comeback of Budan's theorem ===


=== Examples ===
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.<ref name="BF"/><ref name="Reflections"/><ref name="paper_1836"/>
1. Given the polynomial <math>p(x)=x^3 -7x + 7,</math> and the open interval <math>(0,2)</math>, one has


: <math>\begin{align}p(x+0)&=p(x)=x^3 -7x + 7\\
==Equivalence between the theorems by Budan and Fourier==
p(x+2)&=(x+2)^3 -7(x+2) + 7=x^3+6x^2+5x+1
Budan's theorem is equivalent to the one by Fourier. This equivalence is obvious from the fact that, given the polynomial <math>p(x)</math> of degree <math>n > 0 </math>, the <math>n+1</math> terms of the Fourier sequence <math>F_\text{seq}(a)</math> (obtained by substituting <math>x \leftarrow a</math> in <math>F_\text{seq}(x)</math>) have the same signs with (and are proportional to) the corresponding coefficients of the polynomial <math>p(x+a)=\sum_{i=0}^n \frac{p^{(i)}(a)}{i!}\ x^i</math>, obtained from [[Taylor series|Taylor's expansion theorem]].
\end{align}.</math>


Thus, <math>v_0(p)-v_2(p)= 2-0=2,</math> and Budan's theorem asserts that the polynomial <math>p(x)</math> has either two or zero real roots in the open interval <math>(0,2).</math>
As Alesina and Galuzzi point out in Footnote 9, p.&nbsp;222 of their paper,<ref>{{cite journal|last=Alesina|first=Alberto|author2=Massimo Galuzzi|title=A new proof of Vincent's theorem|url=http://retro.seals.ch/cntmng?type=pdf&rid=ensmat-001:1998:44::149&subp=hires|journal=L'Enseignement Mathématique|year=1998|volume=44|number=3-4|pages=219–256}}</ref> 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 <math>x \leftarrow x+p</math>, where <math>p</math> is an integer, to simple additions".


2. With the same polynomial <math>p(x)=x^3 -7x + 7 </math> one has
Despite their equivalence, the two theorems are quite distinct concerning the impact they had on the [[Vincent's theorem#Real root isolation methods derived from Vincent's theorem|isolation of the real roots]] of polynomials with rational coefficients. To wit:
: <math>p(x+1)=(x+1)^3 -7(x+1) + 7=x^3+3x^2-4x+1.</math>
* Fourier's theorem led Sturm to his theorems and [[Sturm's theorem|method]],<ref name="Sturm"/> whereas
Thus, <math>v_0(p)-v_1(p)= 2-2=0,</math> and Budan's theorem asserts that the polynomial <math>p(x)</math> has no real root in the open interval <math>(0,1).</math> This is an example of the use of Budan's theorem as a zero-root test.
* Budan's theorem is the basis of the [[Vincent's theorem#Vincent–Akritas–Strzeboński (VAS, 2005)|Vincent–Akritas–Strzeboński]] (VAS) method.<ref name="VAS"/>


==Fourier's statement {{anchor|Fourier's theorem}}==<!-- This anchor is linked from five redirects (in bold in the text, and with - instead of –. -->
==The most significant application of Budan's theorem==
The '''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 {{math|1=''h'' = ''l''}} and {{mvar|r}}, the sequence of the coefficients of {{math|''p''(''x'' + ''h'')}} is replaced by the sequence of the derivatives of {{mvar|p}} at {{mvar|h}}.


Each theorem is a corollary of the other. This results from the [[Taylor expansion]]
Vincent's (exponential) method for the [[Vincent's theorem#Real root isolation methods derived from Vincent's theorem|isolation of the real roots]] of polynomials (which is based on Vincent's theorem of 1834 and 1836)<ref name="paper_1834"/><ref name="paper_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 [[J. V. Uspensky|Uspensky]] realize that there are no roots of <math>p(x)</math> in the open interval <math>(a, a+1)</math> if <math>p(x + a)</math> and <math>p(x + a + 1)</math> have the same number of [[Budan's theorem#Sign variation|sign variations]] in the sequence of their coefficients (see,<ref name="Uspensky"/> pp.&nbsp;127–137).
:<math>p(x)=\sum_{i=0}^{\deg p} \frac {p^{(i)}(h)}{i!} (x-h)^i</math>
of the polynomial {{mvar|p}} at {{mvar|h}}, which implies that the coefficient of {{math|''x^i''}} in {{math|''p''(''x'' + ''h'')}} is the quotient of <math>p^{(i)}(h)</math> by {{math|''i''!}}, a positive number. Thus the sequences considered in Sturm'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.
===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


==History==
: <math>x = a + \frac{1}{x'},\quad x' = b + \frac{1}{x''},\quad x'' = c + \frac{1}{x'''}, \ldots</math>
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]] a method for extending [[Descartes' rule of signs]]—valid for the interval {{math|(0, +∞)}}—to any interval.<ref name=nmethode>{{cite book|last=Budan|first=François D.|title=Nouvelle méthode pour la résolution des équations numériques|year=1807|publisher=Courcier|location=Paris|url=https://books.google.com/books?id=VyMOAAAAQAAJ&redir_esc=y}}</ref>
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 [[Budan's theorem#Sign variation|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:<ref name="paper_1834"/><ref name="paper_1836"/><ref name=paper_1838>{{cite journal|last=Vincent|first=Alexandre Joseph Hidulph|title=Addition à une précédente note relative à la résolution des équations numériques|url=http://math-doc.ujf-grenoble.fr/JMPA/PDF/JMPA_1838_1_3_A19_0.pdf|journal=Journal de Mathématiques Pures et Appliquées|volume=3|year=1838|pages=235–243}}</ref>


[[Joseph Fourier]] published a similar theorem in 1820,<ref name=Fourier>{{cite journal|last=Fourier|first=Jean Baptiste Joseph|title=Sur l'usage du théorème de Descartes dans la recherche des limites des racines|year=1820|journal=Bulletin des Sciences, par la Société Philomatique de Paris|pages=156–165|url=https://archive.org/details/bulletindesscien20soci}}</ref> on which he worked since more than twenty years.<ref name=arago>{{citation|last=Arago|first=François|title=Biographies of distinguished scientific men|year=1859|publisher=Ticknor and Fields (English Translation)|page=383|location=Boston|url=https://books.google.com/books?id=xGgSAAAAIAAJ&redir_esc=y}}</ref>
: <math>a + \cfrac{1}{b + \cfrac{1}{c + \cfrac{1}{\ddots}}} </math>


Because of the similarity between the two theorems, there was a priority controversy,<ref name=BF>{{cite journal|last=Akritas|first=Alkiviadis G.|title=On the Budan–Fourier Controversy|url=http://dl.acm.org/citation.cfm?id=1089243|journal=ACM SIGSAM Bulletin|year=1981|volume=15|number=1|pages=8–10|doi=10.1145/1089242.1089243}}</ref><ref name=Reflections>{{cite journal|last=Akritas|first=Alkiviadis G.|title=Reflections on a Pair of Theorems by Budan and Fourier|jstor=2690097|year=1982|journal=Mathematics Magazine|volume=55|number=5|pages=292–298|doi=10.2307/2690097}}</ref> despite the fact that two theorems were discovered independently.<ref name=arago /> It was generally Fourier's formulation and proof that were used, during 19th century, in textbooks on [[theory of equations]].
Finally, if infinitely many numbers satisfying this property can be found, then the root is represented by the (infinite) corresponding continuous fraction.


=== Use in 19th century ===
The above statement is an exact translation of the theorem found in Vincent's original papers;<ref name="paper_1834"/><ref name="paper_1836"/><ref name="paper_1838"/> for a clearer understanding see the remarks in the Wikipedia article [[Vincent's theorem#Vincent's theorem: Continued fractions version (1834 and 1836)|Vincent's theorem]]


Budan's and Sturm 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
===Vincent's implementation of his own theorem===
in 1827 by [[Jacques Charles François Sturm|Sturm]].
[[File:Vincent method.jpg|thumb|Vincent's search for a root (applying Budan's theorem)|right|450px]]
Vincent uses Budan's theorem exclusively as a [[Budan's theorem#Early applications of Budan's theorem|"no roots test"]] to locate where the roots lie on the ''x''-axis (to compute the quantities <math>a,b,c ,\ldots</math> of his [[Budan's theorem#Vincent's theorem (1834 and 1836)|theorem]]); that is, to find the integer part of a root Vincent performs successively substitutions of the form <math>x \leftarrow x + 1</math> and stops only when the polynomials <math>p(x)</math> and <math>p(x + 1)</math> differ in the number of [[Budan's theorem#Sign variation|sign variations]] in the sequence of their coefficients (i.e. when the number of [[Budan's theorem#Sign variation|sign variations]] of <math>p(x + 1)</math> is decreased).<ref name="paper_1834"/><ref name="paper_1836"/>


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:<ref name=Sturm>{{cite journal|last=Hourya|first=Benis-Sinaceur|title=Deux moments dans l'histoire du Théorème d'algèbre de Ch. F. Sturm|journal= Revue d'histoire des sciences |year=1988|volume=41|number=2|page=108| url=http://www.persee.fr/web/revues/home/prescript/article/rhs_0151-4105_1988_num_41_2_4093}}</ref> ''« 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. »''
See the corresponding diagram where the root lies in the interval <math>(5,6)</math>. 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 [[Budan's theorem#Sign variation|sign variations]]; that is, the polynomial <math>p(x+6)</math> has fewer [[Budan's theorem#Sign variation|sign variations]] than the polynomial <math>p(x+5)</math>. Vincent then easily obtains a first continued fraction approximation to this root as <math>x = 5 +\frac{1}{x'}</math> as stated in his theorem. Vincent performs those, and only those, transformations that are described in his theorem.


Because of this, during the 19th century, Fourier's and Sturm's theorems appeared together in almost all books on the theory of equations.
===Uspensky's implementation of Vincent's theorem===


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.<ref name=paper_1834>{{cite journal|last=Vincent|first=Alexandre Joseph Hidulph
According to Alexei Uteshev<ref name=Descartes>{{cite book|last=Akritas|first=Alkiviadis G.|title=There is no "Descartes' method"|url=https://books.google.com/books?id=SJR2ybQdZFgC&lpg=PR1&pg=PR1#v=onepage&q&f=false|year=2008|publisher=In: M.J.Wester and M. Beaudin (Eds), Computer Algebra in Education, AullonaPress, USA, pp. 19–35}}</ref> of St. Petersburg University, Russia, [[J. V. Uspensky|Uspensky]] came upon the statement (and proof) of [[Budan's theorem#Vincent's theorem (1834 and 1836)|Vincent's theorem]] in the 20th century in Serret's Algebra,<ref name="Serret"/> 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 [[J. V. Uspensky|Uspensky]] never saw Vincent's papers of 1834<ref name="paper_1834"/> and 1836,<ref name="paper_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,<ref name="Uspensky"/> [[J. V. Uspensky|Uspensky]] erroneously claimed that, based on [[Budan's theorem#Vincent's theorem (1834 and 1836)|Vincent's theorem]], he had discovered a method for isolating the real roots "much superior in practice to that based on Sturm's Theorem". [[J. V. Uspensky|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,<ref name="Uspensky"/> pp.&nbsp;127–137).
|title=Mémoire sur la résolution des équations numériques |url=http://gallica.bnf.fr/ark:/12148/bpt6k57787134/f4.image.r=Agence%20Rol.langEN
[[File:Uspensky attempt.jpg|thumb|Uspensky's search for a root (not applying Budan's theorem)|450px]]
|journal=Mémoires de la Société Royale des Sciences, de l' Agriculture et des Arts, de Lille|year=1834|pages=1–34}}</ref> Roughly speaking, [[Vincent's theorem]] consists of using [[continuous fraction]]s for replacing Budan's linear transformations of the variable by [[Möbius transformation]]s.
[[J. V. Uspensky|Uspensky]] does not know Budan's theorem and, hence, he cannot use it as a [[Budan's theorem#Early applications of Budan's theorem|"no roots test"]]. So, for him it does not suffice that <math> p(x + 1) </math> has the same number of [[Budan's theorem#Sign variation|sign variations]] as <math>p(x)</math> in order to conclude that <math>p(x)</math> has no roots inside <math>(0,1)</math>; to make sure, he also performs the redundant substitution (Budan's [[Budan's theorem#Early applications of Budan's theorem|"0_1 roots test"]]) <math>x \leftarrow \frac{1}{1+x}</math> in <math>p(x)</math>, which unfailingly results in a polynomial with no [[Budan's theorem#Sign variation|sign variations]] and hence no positive roots.
[[J. V. Uspensky|Uspensky]] uses the information obtained from both the needed transformation <math>x \leftarrow x + 1</math> and the not needed one <math>x \leftarrow \frac{1}{1+x}</math> to realize that <math>p(x)</math> has no roots in the interval <math>(0,1)</math>. In other words, searching for a root, Uspensky advances as illustrated in the corresponding figure.


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]].<ref name=Serret>{{cite book|last=Serret|first=Joseph A.|title=Cours d'algèbre supérieure. Tome I|year=1877|publisher=Gauthier-Villars|pages=363–368|url=https://archive.org/details/coursdalgbresu01serruoft}}</ref> There were introduced again in 1976 by Collins and Akritas, for providing, in [[computer algebra]], an efficient algorithm for real roots isolation on computers.<ref>Collins, G. E., & Akritas, A. G. (1976, August). Polynomial real root isolation using Descarte's rule of signs. In ''Proceedings of the third ACM symposium on Symbolic and algebraic computation'' (pp. 272-275). ACM.</ref>
[[J. V. Uspensky|Uspensky]]'s transformations are not the ones described in [[Budan's theorem#Vincent's theorem (1834 and 1836)|Vincent's theorem]], and consequently, his transformations take twice as much computation time as the ones needed for Vincent's method.<ref name="akritas"/><ref name="Descartes"/>


==See also==
==See also==
*[[Properties of polynomial roots]]
*[[Properties of polynomial roots]]
*[[Root-finding algorithm]]
*[[Root-finding algorithm]]
*[[Sturm's theorem]]
*[[Vieta's formulas]]
*[[Newton's method]]


==References==
==References==
Line 153: Line 89:


==External links==
==External links==
{{MacTutor|title=Budan de Boislaurent}}
* 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


[[Category:Mathematical theorems]]
[[Category:Mathematical theorems]]
[[Category:Root-finding algorithms]]
[[Category:Real algebraic geometry]]

Revision as of 12:36, 21 November 2018

In mathematics, Budan's theorem is a theorem for bounding the number of real roots a polynomial in 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 isolating real roots of polynomials.

Sign variation

Let 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 and either j = i + 1 or 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 used. For Budan's theorem, its 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

Main article: Descartes' rule of signs

All results described in this articles 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 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) ≤ 1, then one has #+(p) = v(p).

Budan's statement

Given a univariate polynomial p(x) with real coefficients, let us denote by #(l,r)(p) the number of real roots of p in an open interval (l, r) (with l < r real numbers). Let us denote also by vh(p) the number of sign variations in the sequence of the coefficients of the polynomial ph(x) = p(x + h). In particular one has v(p) = v0(p) with the notation of the preceding section.

Budan's theorem is the following:

is a nonnegative even integer.

As is non negative, this implies

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 are positive, that is Thus and which makes Descartes' rule of signs as special case of Budan's theorem.

As for Descartes' rule of signs, if one has This means that, if one has a "zero-root test" and a "one-root test".

Examples

1. Given the polynomial and the open interval , one has

Thus, and Budan's theorem asserts that the polynomial has either two or zero real roots in the open interval

2. With the same polynomial one has

Thus, and Budan's theorem asserts that the polynomial has no real root in the open interval This is an example of the use of Budan's theorem as a zero-root test.

Fourier's statement

The 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

of the polynomial p at h, which implies that the coefficient of x^i in p(x + h) is the quotient of by i!, a positive number. Thus the sequences considered in Sturm'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.

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 a method for extending Descartes' rule of signs—valid for the interval (0, +∞)—to any interval.[1]

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

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

Use in 19th century

Budan's and Sturm 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:[6] « 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.[7] Roughly speaking, Vincent's theorem consists of using continuous 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.[8] There were introduced again in 1976 by Collins and Akritas, for providing, in computer algebra, an efficient algorithm for real roots isolation on computers.[9]

See also

References

  1. ^ 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 Arago, François (1859), Biographies of distinguished scientific men, Boston: Ticknor and Fields (English Translation), p. 383
  4. ^ Akritas, Alkiviadis G. (1981). "On the Budan–Fourier Controversy". ACM SIGSAM Bulletin. 15 (1): 8–10. doi:10.1145/1089242.1089243.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ Serret, Joseph A. (1877). Cours d'algèbre supérieure. Tome I. Gauthier-Villars. pp. 363–368.
  9. ^ Collins, G. E., & Akritas, A. G. (1976, August). Polynomial real root isolation using Descarte's rule of signs. In Proceedings of the third ACM symposium on Symbolic and algebraic computation (pp. 272-275). ACM.

External links

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Budan%27s_theorem&oldid=869953321"