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.
Budan's original formulation is used in fast modern algorithms for real-root isolation of polynomials.
For studying the real roots of a polynomial, the number of sign variations of several sequences may be used.
For the Fourier's theorem, it is the sequence of values of the successive derivatives at a point.
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.
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).
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
which makes Descartes' rule of signs a special case of Budan's theorem.
This results from the Taylor expansion of the polynomial p at h, which implies that the coefficient of xi in p(x + h) is the quotient of
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.
is due to the higher derivative signs possibly becoming zero.
remain nonzero, we only lose an even number of sign changes:
, then arguing similarly, we find that for both cases, we can take a small
The problem of counting and locating the real roots of a polynomial started to be systematically studied only in the beginning of the 19th century.
[2] Joseph Fourier published a similar theorem in 1820,[3] on which he worked for more than twenty years.
[4] It was generally Fourier's formulation and proof that were used, during the 19th century, in textbooks on the theory of equations.
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.
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.
[10] O'Connor, John J.; Robertson, Edmund F., "Budan de Boislaurent", MacTutor History of Mathematics Archive, University of St Andrews