---
tag: 7THS519D4A
kind: statement
role: theorem
name: Budan's theorem
msc: [26C10, "12D10"]
uses: [0Q9EZS90GY, 00EHX6FWC0, 03XVP8Q4GY, R44CV0KD9T]
about: [019MA1VTR2]
sources:
  - url: https://en.wikipedia.org/wiki/Budan%27s_theorem
same_as:
  wikidata: Q3527026
  wikipedia: Budan's theorem
---

## Statement

Let $p$ be a nonzero polynomial with real coefficients, and let $l < r$ be real numbers.
For $c \in \R$, let $V_c$ be the number of sign changes in the sequence of nonzero coefficients of the polynomial $p(x + c)$.
Let $N$ be the number of [[roots|00EHX6FWC0]] of $p$ in the half-open interval $(l, r]$, counted with [[multiplicity|03XVP8Q4GY]].
Then $N \le V_l - V_r$, and $V_l - V_r - N$ is even.

## Remarks

The roots of $p(x + c)$ are the roots of $p$ shifted by $-c$.
So [[Descartes' rule of signs|T6DQQ36JZ5]] applied to $p(x + l)$ and $p(x + r)$ bounds the roots of $p$ greater than $l$ and greater than $r$.
The theorem says that the difference of the two bounds is again a bound, with the same parity rule.
Example: take $p = x^2 - 2$, $l = 0$ and $r = 2$.
Then $p(x) = x^2 - 2$ has $V_0 = 1$, and $p(x + 2) = x^2 + 4x + 2$ has $V_2 = 0$.
So there is exactly one root in $(0, 2]$, namely $\sqrt 2$.
Take $l = 0$ and $r$ larger than the real part of every complex root of $p$.
Then all coefficients of $p(x + r)$ have the same sign, so $V_r = 0$, and one gets back Descartes' rule.

## Explanations

### L1 human

Budan's theorem bounds the number of roots of a polynomial in an interval by counting sign changes of coefficients.
One shifts the polynomial so that each end of the interval moves to $0$, and then compares the two counts.
Like Descartes' rule, it can overcount, but only by an even number.

### L2 human

The theorem is used in root isolation: an interval with $V_l - V_r = 0$ has no root, and one with $V_l - V_r = 1$ has exactly one.
An equivalent form, due to Fourier, counts sign changes in the sequence $p(c), p'(c), \dots, p^{(n)}(c)$.
By Taylor's formula, these numbers are the coefficients of $p(x + c)$ up to positive factors.
Compared with [[Sturm's theorem|R44CV0KD9T]], it is cheaper to compute but gives only a bound.