Geometrical properties of polynomial roots

Lagrange and Cauchy were the first to provide upper bounds on all complex roots.[1] Lagrange's bound is[2]

${\displaystyle \max \left\{1,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|\right\},}$

and Cauchy's bound is[3]

${\displaystyle 1+\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|,\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|\right\}}$

Lagrange's bound is sharper (smaller) than Cauchy's bound only when 1 is larger than the sum of all ${\displaystyle \left|{\frac {a_{i}}{a_{n}}}\right|}$ but the largest. This is relatively rare in practice, and explains why Cauchy's bound is more widely used than Lagrange's.

Both bounds result from the Gershgorin circle theorem applied to the companion matrix of the polynomial and its transpose. They can also be proved by elementary methods.

These bounds are not invariant by scaling. That is, the roots of the polynomial p(sx) are the quotient by s of the root of p, and the bounds given for the roots of p(sx) are not the quotient by s of the bounds of p. Thus, one may get sharper bounds by minimizing over possible scalings. This gives

${\displaystyle \min _{s\in \mathbb {R} _{+}}\left(\max \left\{s,\sum _{i=0}^{n-1}\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n+1}\right\}\right),}$

and

${\displaystyle \min _{s\in \mathbb {R} _{+}}\left(s+\max _{0\leq i\leq n-1}\left(\left|{\frac {a_{i}}{a_{n}}}\right|s^{i-n+1}\right)\right),}$

for Lagrange's and Cauchy's bounds respectively.

Another bound, originally given by Lagrange, but attributed to Zassenhaus by Donald Knuth, is [4]

${\displaystyle 2\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right\}.}$

This bound is invariant by scaling.

Lagrange improved this latter bound into the sum of the two largest values (possibly equal) in the sequence[4]

${\displaystyle \left[\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{1/2},\ldots ,\left|{\frac {a_{0}}{a_{n}}}\right|^{1/n}\right].}$

Lagrange also provided the bound

${\displaystyle \sum _{i}\left|{\frac {a_{i}}{a_{i+1}}}\right|,}$

where ${\displaystyle a_{i}}$ denotes the ith nonzero coefficient when the terms of the polynomials are sorted by increasing degrees.

Hölder's inequality allows the extension of Lagrange's and Cauchy's bounds to every h-norm. The h-norm of a sequence

${\displaystyle s=(a_{0},\ldots ,a_{n})}$

is

${\displaystyle \|s\|_{h}=\left(\sum _{i=1}^{n}|a_{i}|^{h}\right)^{1/h},}$

for any real number h ≥ 1, and

${\displaystyle \|s\|_{\infty }=\textstyle {\max _{i=1}^{n}}|a_{i}|.}$

If ${\displaystyle {\frac {1}{h}}+{\frac {1}{k}}=1,}$ with 1 ≤ h, k ≤ ∞, and 1 / ∞ = 0, an upper bound on the absolute values of the roots of p is

${\displaystyle {\frac {1}{|a_{n}|}}\left\|(|a_{n}|,\left\|(|a_{n-1}|,\ldots ,|a_{0}|\right)\|_{h}\right)\|_{k}.}$

For k = 1 and k = ∞, one gets respectively Cauchy's and Lagrange's bounds.

For h = k = 2, one has the bound

${\displaystyle {\frac {1}{|a_{n}|}}{\sqrt {|a_{n}|^{2}+|a_{n-1}|^{2}+\cdots +|a_{0}|^{2}}}.}$

This is not only a bound of the absolute values of the roots, but also a bound of the product of their absolute values larger than 1; see § Landau's inequality, below.

Many other upper bounds for the magnitudes of all roots have been given.[5]

Fujiwara's bound[6]

${\displaystyle 2\,\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n}}}\right|^{\frac {1}{2}},\ldots ,\left|{\frac {a_{1}}{a_{n}}}\right|^{\frac {1}{n-1}},\left|{\frac {a_{0}}{2a_{n}}}\right|^{\frac {1}{n}}\right\},}$

slightly improves the bound given above by dividing the last argument of the maximum by two.

Kojima's bound is[7]

${\displaystyle 2\,\max \left\{\left|{\frac {a_{n-1}}{a_{n}}}\right|,\left|{\frac {a_{n-2}}{a_{n-1}}}\right|,\ldots ,\left|{\frac {a_{0}}{2a_{1}}}\right|\right\},}$

where ${\displaystyle a_{i}}$ denotes the ith nonzero coefficient when the terms of the polynomials are sorted by increasing degrees. If all coefficients are nonzero, Fujiwara's bound is sharper, since each element in Fujiwara's bound is the geometric mean of first elements in Kojima's bound.

Sun and Hsieh obtained another improvement on Cauchy's bound.[8] Assume the polynomial is monic with general term a_ixⁱ. Sun and Hsieh showed that upper bounds 1 + d₁ and 1 + d₂ could be obtained from the following equations.

${\displaystyle d_{1}={\tfrac {1}{2}}\left((|a_{n-1}|-1)+{\sqrt {(|a_{n-1}|-1)^{2}+4a}}\right),\qquad a=\max\{|a_{i}|\}.}$

d₂ is the positive root of the cubic equation

${\displaystyle Q(x)=x^{3}+(2-|a_{n-1}|)x^{2}+(1-|a_{n-1}|-|a_{n-2}|)x-a,\qquad a=\max\{|a_{i}|\}}$

They also noted that d₂ ≤ d₁.

Rouché's theorem allows defining discs centered at zero and containing a given number of roots. More precisely, if there is a positive real number R and an integer 0 ≤ k ≤ n such that

${\displaystyle |a_{k}|R^{k}>|a_{0}|+\cdots +|a_{k-1}|R^{k-1}+|a_{k+1}|R^{k+1}+\cdots +|a_{n}|R^{n},}$

then there are exactly k roots, counted with multiplicity, of absolute value less than R.

The above result may be applied if the polynomial

${\displaystyle h_{k}(x)=|a_{0}|+\cdots +|a_{k-1}|x^{k-1}-|a_{k}|x^{k}+|a_{k+1}|x^{k+1}+\cdots +|a_{n}|x^{n}.}$

takes a negative value for some positive real value of x.

In the remaining of the section, suppose that a₀ ≠ 0. If it is not the case, zero is a root, and the localization of the other roots may be studied by dividing the polynomial by a power of the indeterminate, getting a polynomial with a nonzero constant term.

For k = 0 and k = n, Descartes' rule of signs shows that the polynomial has exactly one positive real root. If ${\displaystyle R_{0}}$ and ${\displaystyle R_{n}}$ are these roots, the above result shows that all the roots satisfy

${\displaystyle R_{0}\leq |z|\leq R_{1}.}$

As these inequalities apply also to ${\displaystyle h_{0}}$ and ${\displaystyle h_{n},}$ these bounds are optimal for polynomials with a given sequence of the absolute values of their coefficients. They are thus sharper than all bounds given in the preceding sections.

For 0 < k < n, Descartes' rule of signs implies that ${\displaystyle h_{k}(x)}$ either has two positive real roots that are not multiple, or is nonnegative for every positive value of x. So, the above result may be applied only in the first case. If ${\displaystyle R_{k,1}<R_{k,2}}$ are these two roots, the above result implies that

${\displaystyle |z|\leq R_{k,1}}$

for k roots of p, and that

${\displaystyle |z|\geq R_{k,2}}$

for the n – k other roots.

Instead of explicitly computing ${\displaystyle R_{k,1}}$ and ${\displaystyle R_{k,2},}$ it is generally sufficient to compute a value ${\displaystyle R_{k}}$ such that ${\displaystyle h_{k}(R_{k})<0}$ (necessarily ${\displaystyle R_{k,1}<R_{k}<R_{k,2}}$). These ${\displaystyle R_{k}}$ have the property of separating roots in terms of their absolute values: if, for h < k, both ${\displaystyle R_{h}}$ and ${\displaystyle R_{k}}$ exist, there are exactly k – h roots z such that ${\displaystyle R_{h}<|z|<R_{k}.}$

For computing ${\displaystyle R_{k},}$ one can use the fact that ${\displaystyle {\frac {h(x)}{x^{k}}}}$ is a convex function (its second derivative is positive). Thus ${\displaystyle R_{k}}$ exists if and only if ${\displaystyle {\frac {h(x)}{x^{k}}}}$ is negative at its unique minimum. For computing this minimum, one can use any optimization method, or, alternatively, Newton's method for computing the unique positive zero of the derivative of ${\displaystyle {\frac {h(x)}{x^{k}}}}$ (it converges rapidly, as the derivative is a monotonic function).

One can increase the number of existing ${\displaystyle R_{k}}$'s by applying the root squaring operation of the Dandelin–Graeffe iteration. If the roots have distinct absolute values, one can eventually completely separate the roots in terms of their absolute values, that is, compute n + 1 positive numbers ${\displaystyle R_{0}<R_{1}<\dots <R_{n}}$ such there is exactly one root with an absolute value in the open interval ${\displaystyle (R_{k-1},R_{k}),}$ for k = 1, ..., n.

The Gershgorin circle theorem applies the companion matrix of the polynomial on a basis related to Lagrange interpolation to define discs centered at the interpolation points, each containing a root of the polynomial; see Durand–Kerner method § Root inclusion via Gerschgorin's circles for details.

If the interpolation points are close to the roots of the roots of the polynomial, the radii of the discs are small, and this is a key ingredient of Durand–Kerner method for computing polynomial roots.

To give a bound of the positive roots, one can assume ${\displaystyle a_{n}>0}$ without loss of generality, as changing the signs of all coefficients does not change the roots.

Every upper bound of the positive roots of

${\displaystyle q(x)=a_{n}x^{n}+\sum _{i=0}^{n-1}\min(0,a_{i})x^{i}}$

is also a bound of the real zeros of

${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}}$.

In fact, if B is such a bound, for all x > B, one has p(x) ≥ q(x) > 0.

Applied to Cauchy's bound, this gives the upper bound

${\displaystyle 1+{\textstyle \max _{i=0}^{n-1}}{\frac {-a_{i}}{a_{n}}}}$

for the real roots of a polynomial with real coefficients. If this bound is not greater than 1, this means that all nonzero coefficients have the same sign, and that there is no positive root.

Similarly, another upper bound of the positive roots is

${\displaystyle 2\,{\max _{a_{i}a_{n}<0}}\left({\frac {-a_{i}}{a_{n}}}\right)^{\frac {1}{n-i}}.}$

If all nonzero coefficients have the same sign, there is no positive root, and the maximum must be zero.

Other bounds have been recently developed, mainly for the method of continued fractions for real-root isolation.[15][16]

If all roots of a polynomial are real, Laguerre proved the following lower and upper bounds of the roots, by using what is now called Samuelson's inequality.[17]

Let ${\displaystyle \sum _{k=0}^{n}a_{k}x^{k}}$ be a polynomial with all real roots. Then its roots are located in the interval with endpoints

${\displaystyle -{\frac {a_{n-1}}{na_{n}}}\pm {\frac {n-1}{na_{n}}}{\sqrt {a_{n-1}^{2}-{\frac {2n}{n-1}}a_{n}a_{n-2}}}.}$

For example, the roots of the polynomial ${\displaystyle x^{4}+5x^{3}+5x^{2}-5x-6=(x+3)(x+2)(x+1)(x-1)}$ satisfy

${\displaystyle -3.8118<-{\frac {5}{4}}-{\frac {3}{4}}{\sqrt {\frac {35}{3}}}\leq x\leq -{\frac {5}{4}}+{\frac {3}{4}}{\sqrt {\frac {35}{3}}}<1.3118.}$

For large n, the mean density of real roots near x is asymptotically

${\displaystyle m(x)={\frac {1}{\pi |1-x^{2}|}}}$

if ${\displaystyle x^{2}-1\neq 0,}$ and

${\displaystyle m(\pm 1)={\frac {1}{\pi }}{\sqrt {\frac {n^{2}-1}{12}}}}$

It follows that the expected number of real roots is, using big O notation

${\displaystyle N_{n}={\frac {2}{\pi }}\ln n+C+{\frac {2}{\pi n}}+O(n^{-2})}$

where C is a constant approximately equal to 0.6257358072.[23]

In other words, the expected number of real roots of a random polynomial of high degree is lower than the natural logarithm of the degree.

Kac, Erdős and others have shown that these results are insensitive to the distribution of the coefficients, if they are independent and have the same distribution with mean zero. However, if the variance of the ith coefficient is equal to ${\displaystyle {\binom {n}{i}},}$ the expected number of real roots is ${\displaystyle {\sqrt {n}}.}$[23]