The Budan-Fourier Theorem

The Budan-Fourier Theorem gives an upper bound on the number of real roots (counting multiplicity) of a real polynomial in a given interval $I=(a,b]$, where $a=-\infty$ and/or $b=\infty$ are allowed. The algorithm is simple. Take a (nonzero) polynomial and compute all of its derivatives. Evaluate this list of derivatives at $x=a$ and create a list of results. After ignoring all zeros, count the number of times the list of numbers switches from positive to negative numbers or vice-versa (we include "$\pm\infty$" as possible "numbers"). Next, do the same for $x=b$.

Budan and Fourier showed that the number of sign changes at $x=a$ minus the number of sign changes at $x=b$ provides an upper bound on the number of real roots of that polynomial (counting multiplicity). In fact, if the difference in sign changes is $s$, then this polynomial has $s-2k$ real roots (counting multiplicity) for some positive integer $k$.

For example, if $s=3$, then there are either 3 or 1 real roots. On the other hand, if $s=4$, then there are either 4, 2, or no real roots.

It is interesting to note that Descartes' Rule of Signs is a special case of this result. If we set $a=0$, the sign changes in $f(0),f'(0),f''(0),\dots$ is the same as the sign changes in the coefficients of $f(x)$. If $b=\infty$, then all of signs of $f(\infty),f'(\infty),f''(\infty),\dots$ will be the same. Thus Descartes' Rule of Signs counts the same thing as Budan-Fourier for $a=0$ and $b=\infty$: the roots in $I=(0,\infty)$ (i.e. the positive real roots).

The computation above is powered by SageMath. The Sage code is embedded in this webpage's html file. To view the code instruct your browser to show you this page's source. For example, in Chrome, right-click and choose "View page source".

Wikipedia entry for the Budan-Fourier Theorem.