Budan's theorem

Let ${\displaystyle 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 ${\displaystyle c_{i}c_{j}<0,}$ and either j = i + 1 or ${\displaystyle 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 Fourier's 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.

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) ≤ 1, then one has #₊(p) = v(p).

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₀(p) with the notation of the preceding section.

Budan's theorem is the following:

${\displaystyle v_{\ell }(p)-v_{r}(p)-\#_{(\ell ,r]}}$ is a nonnegative even integer.

As ${\displaystyle \#_{(\ell ,r]}}$ is non negative, this implies ${\displaystyle 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 ${\displaystyle p_{r}(x)}$ are positive, that is ${\displaystyle v_{r}(p)=0.}$ Thus ${\displaystyle v_{0}(p)=v_{0}(p)-v_{r}(p),}$ and ${\displaystyle \#_{+}=\#_{(0,r)},}$ which makes Descartes' rule of signs a special case of Budan's theorem.

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

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

${\displaystyle 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ⁱ in p(x + h) is the quotient of ${\displaystyle 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.

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

Proof:

Let ${\displaystyle n}$ be the degree of ${\displaystyle f}$, so that ${\displaystyle f,f',...,f^{(n-1)}}$ are nonconstant polynomials, ${\displaystyle f^{(n)}}$ is a nonzero constant, and ${\displaystyle f^{(n+1)},...}$ are all identically zero.

As a function of ${\displaystyle t,}$ the sign variation ${\displaystyle v_{t}(f)}$ can only varies at a root of at least one of ${\displaystyle f,f',...,f^{(n-1)}.}$

If ${\displaystyle v_{t}(f)}$ varies at ${\displaystyle t=r}$, then for some ${\displaystyle k}$, ${\displaystyle f^{(k)}(x)}$ has a root at ${\displaystyle t}$, and each of ${\displaystyle f,f',...,f^{(k-1)}}$ has no root at ${\displaystyle t}$.

If ${\displaystyle k=0}$, then ${\displaystyle f(x)=(x-r)^{s}p(x-r)}$ for some ${\displaystyle s\geq 1}$ and some polynomial ${\displaystyle p}$ that satisfies ${\displaystyle p(0)\neq 0}$. By explicitly computing ${\displaystyle f,f',...,f^{(n)}}$ at ${\displaystyle r}$ and ${\displaystyle r-\epsilon }$ for a small ${\displaystyle \epsilon }$, we have ${\displaystyle v_{r}(f)=v_{r-\epsilon }(f)-s-2s',\quad \exists s'\geq 0.}$

In this equation, the term ${\displaystyle -s}$ is due to the signs of ${\displaystyle f,f',...,f^{(s)}}$ changing from ${\displaystyle (-1)^{s}\operatorname {sign} (p(0)),(-1)^{s-1}\operatorname {sign} (p(0)),...,-\operatorname {sign} (p(0)),\operatorname {sign} (p(0))}$ to ${\displaystyle 0,0,...,0,\operatorname {sign} (p(0))}$. The term ${\displaystyle -2s',\quad \exists s'\geq 0}$ is due to the higher derivative signs possibly becoming zero.

If ${\displaystyle k\geq 1}$, then since some derivatives are zeroed at ${\displaystyle r}$, but both ${\displaystyle f^{(k-1)}(x)}$ and ${\displaystyle f^{(n)}(x)}$ remain nonzero, we only lose an even number of sign changes:

$${\displaystyle v_{r}(f)=v_{r-\epsilon }(f)-2s',\quad \exists s'\geq 0}$$

If ${\displaystyle v_{t}(f)}$ varies at ${\displaystyle t=l}$, then arguing similarly, we find that for both cases, we can take a small ${\displaystyle \epsilon }$ such that ${\displaystyle v_{l+\epsilon }(f)=v_{l}(f)}$.

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.

In 1807, François Budan de Boislaurent discovered a method for extending Descartes' rule of signs—valid for the interval (0, +∞)—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.

• Properties of polynomial roots
• Root-finding algorithm

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