View source for Geometrical properties of polynomial roots

{{short description|Geometry of the location of polynomial roots}}
{{for|the computation of polynomial roots|Polynomial root-finding algorithms}}
In [[mathematics]], a [[univariate polynomial]] of degree {{mvar|n}} with real or complex coefficients has {{mvar|n}} complex '''[[zero of a function|roots]]''', if counted with their [[multiplicities]]. They form a multiset of {{mvar|n}} points in the [[complex plane]]. This article concerns the '''geometry''' of these points, that is the information about their localization in the complex plane that can be deduced from the degree and the coefficients of the polynomial.

Some of these geometrical properties are related to a single polynomial, such as upper bounds on the absolute values of the roots, which define a disk containing all roots, or lower bounds on the distance between two roots. Such bounds are widely used for [[root-finding algorithm]]s for polynomials, either for tuning them, or for computing their [[computational complexity]].

Some other properties are probabilistic, such as the expected number of real roots of a random polynomial of degree {{mvar|n}} with real coefficients, which is less than  <math> 1+\frac 2\pi \ln (n) </math> for {{mvar|n}} sufficiently large.

In this article, a polynomial that is considered is always denoted 
:<math>
  p(x)=a_0 + a_1 x + \cdots + a_n x^n,
</math>
where <math>a_0, \dots, a_n</math> are real or [[complex number]]s and <math>a_n \neq 0</math>; thus <math>n</math> is the degree of the polynomial.

==Continuous dependence on coefficients==
The {{math|''n''}} roots of a polynomial of degree {{math|''n''}} depend [[continuous function|continuously]] on the coefficients. For simple roots, this results immediately from the [[implicit function theorem]]. This is true also for multiple roots, but some care is needed for the proof.

A small change of coefficients may induce a dramatic change of the roots, including the change of a real root into a complex root with a rather large imaginary part (see [[Wilkinson's polynomial]]). A consequence is that, for classical numeric [[root-finding algorithm]]s, the problem of approximating the roots given the coefficients can be [[ill-conditioned]] for many inputs.

==Conjugation==

The [[complex conjugate root theorem]] states that if the coefficients
of a polynomial are real, then the non-real roots appear in pairs of the form  {{math|(''a'' + ''ib'', ''a'' – ''ib'')}}.

It follows that the roots of a polynomial with real coefficients are [[reflection symmetry|mirror-symmetric]] with respect to the real axis.

This can be extended to [[algebraic conjugate|algebraic conjugation]]: the roots of a polynomial with [[rational number|rational]] coefficients are ''conjugate'' (that is, invariant) under the action of the [[Galois group]] of the polynomial. However, this symmetry can rarely be interpreted geometrically.

==Bounds on all roots==
Upper bounds on the absolute values of polynomial roots are widely used for [[root-finding algorithm]]s, either for limiting the regions where roots should be searched, or for the computation of the [[computational complexity]] of these algorithms. 

Many such bounds have been given, and the sharper one depends generally on the specific sequence of coefficient that are considered. Most bounds are greater or equal to one, and are thus not sharp for a polynomial which have only roots of absolute values lower than one. However, such polynomials are very rare, as shown below.

Any upper bound on the absolute values of roots provides a corresponding lower bound. In fact, if <math>a_n\ne 0,</math> and {{mvar|U}} is an upper bound of the absolute values of the roots of 
:<math>
a_0 + a_1 x + \cdots + a_n x^n,
</math>
then {{math|1/''U''}} is a lower bound of the absolute values of the roots of
:<math>
a_n + a_{n-1} x + \cdots + a_0 x^n,
</math>
since the roots of either polynomial are the multiplicative inverses of the roots of the other. ''Therefore, in the remainder of the article lower bounds will not be given explicitly''.

===Lagrange's and Cauchy's bounds===
[[Lagrange]] and [[Cauchy]] were the first to provide upper bounds on all complex roots.<ref name=Hirst1997>{{cite journal |first1=Holly P. |last1=Hirst |first2=Wade T. |last2=Macey |title=Bounding the Roots of Polynomials |journal=[[The College Mathematics Journal]] |volume=28 |issue=4 |year=1997 |pages=292–295 |doi=10.1080/07468342.1997.11973878 |jstor=2687152 }}</ref> Lagrange's bound is<ref>Lagrange J–L (1798) Traité de la résolution des équations numériques. Paris.</ref>
:<math>\max\left\{1,\sum_{i=0}^{n-1} \left|\frac{a_i}{a_n}\right|\right\},</math>
and Cauchy's bound is<ref name=Cauchy1829>Cauchy Augustin-Louis (1829). ''Exercices de mathématique''. Œuvres 2 (9) p.122</ref>
:<math>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\}</math>

Lagrange's bound is sharper (smaller) than Cauchy's bound only when 1 is larger than the sum of all <math>\left|\frac{a_i}{a_n}\right|</math> 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.

{{cot|Proof of Lagrange's and Cauchy's bounds}}
If {{mvar|z}} is a root of the polynomial, and {{math|{{!}}''z''{{!}} ≥ 1}} one has 
:<math>|a_n||z^n| = \left|\sum_{i=0}^{n-1}a_iz^i\right|
\le \sum_{i=0}^{n-1}|a_iz^i|
\le \sum_{i=0}^{n-1}|a_i||z|^{n-1}.
</math>

Dividing by <math>|a_n||z|^{n-1},</math> one gets 
:<math>|z|\le \sum_{i=0}^{n-1}\frac{|a_i|}{|a_n|},</math>
which is Lagrange's bound when there is at least one root of absolute value larger than 1. Otherwise, 1 is a bound on the roots, and is not larger than Lagrange's bound.

Similarly, for Cauchy's bound, one has, if {{math|{{!}}''z''{{!}} ≥ 1}},
:<math>|a_n||z^n| = \left|\sum_{i=0}^{n-1}a_iz^i\right|
\le \sum_{i=0}^{n-1}|a_iz^i|
\le \max |a_i|\sum_{i=0}^{n-1}|z|^i
= \frac{|z|^n-1}{|z|-1}\max |a_i|
\le  \frac{|z|^n}{|z|-1}\max |a_i|.
</math>
Thus 
:<math>
|a_n|(|z|-1) \le \max |a_i|.
</math>
Solving in {{math|{{!}}''z''{{!}}}}, one gets Cauchy's bound if there is a root of absolute value larger than 1. Otherwise the bound is also correct, as Cauchy's bound is larger than 1.
{{cob}}

These bounds are not invariant by scaling. That is, the roots of the polynomial {{math|''p''(''sx'')}} are the quotient by {{mvar|s}} of the root of {{mvar|p}}, and the bounds given for the roots of {{math|''p''(''sx'')}} are not the quotient by {{mvar|s}} of the bounds of {{mvar|p}}. Thus, one may get sharper bounds by minimizing over possible scalings. This gives 
 <math>\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),</math>
and
 <math>\min_{s\in \mathbb R_+}\left(s+\max_{0\le i\le n-1}\left(\left|\frac{a_i}{a_n}\right| s^{i-n+1}\right)\right),</math>
for Lagrange's and Cauchy's bounds respectively.

Another bound, originally given by Lagrange, but attributed to Zassenhaus by [[Donald Knuth]], is  <ref name =yap145>{{harvnb|Yap|2000|loc=§VI.2}}</ref>
 <math>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\}.</math>
This bound is invariant by scaling.

{{cot|Proof of the preceding bound}}
Let {{mvar|A}} be the largest <math>\left|\frac{a_i}{a_n}\right|^\frac 1{n-i}</math> for {{math|0 ≤ ''i'' < ''n''}}. Thus one has
:<math>\frac {|a_{i}|}{|a_n|} \le A^{n-i}</math>
for <math>0\le i <n.</math>
If {{mvar|z}} is a root of {{mvar|p}}, one has 
:<math>-a_nz^n=\sum_{i=0}^{n-1}a_i z^i,</math>
and thus, after dividing by <math>a_n,</math>
:<math>\begin{align}
|z|^n&\le\sum_{i=0}^{n-1}A^{n-i}|z|^i\\
&=A\frac{|z|^{n}-A^{n}}{|z|-A}.
\end{align}</math>
As we want to prove {{math|{{!}}''z''{{!}} ≤ 2''A''}}, we may suppose that {{math|{{!}}''z''{{!}} > A}} (otherwise there is nothing to prove).
Thus 
:<math>|z|^n \le A\frac{|z|^n}{|z|-A},</math>
which gives the result, since <math>|z|>A.</math>
{{cob}}

Lagrange improved this latter bound into the sum of the two largest values (possibly equal) in the sequence<ref name =yap145/>
 <math>\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].</math>

Lagrange also provided the bound {{cn|date=March 2019}}
 <math>\sum_i \left|\frac{a_i}{a_{i+1}}\right|,</math>
where <math>a_i</math> denotes the {{mvar|i}}th ''nonzero'' coefficient when the terms of the polynomials are sorted by increasing degrees.

===Using Hölder's inequality===
[[Hölder's inequality]] allows the extension of Lagrange's and Cauchy's bounds to every [[p-norm|{{mvar|h}}-norm]]. The {{mvar|h}}-norm of a sequence
:<math>s=(a_0, \ldots, a_n)</math>
is 
:<math>\|s\|_h = \left(\sum_{i=0}^n |a_i|^h\right)^{1/h},</math>
for any real number {{math|''h'' ≥ 1}}, and 
:<math>\|s\|_\infty = \textstyle{\max_{i=0}^n} |a_i|.</math>

If <math>\frac 1h+ \frac 1k=1,</math> with {{math|1 ≤ ''h'', ''k'' ≤ ∞}}, and {{math|1=1 / ∞ = 0}}, an upper bound on the absolute values of the roots of {{mvar|p}} is 
 <math>\frac 1{|a_n|}\left\|(|a_n|, \left\|(|a_{n-1}|, \ldots, |a_0| \right)\|_h\right)\|_k.</math>

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

For {{math|1=''h'' = ''k'' = 2}}, one has the bound
 <math>\frac 1{|a_n|}\sqrt{|a_n|^2+|a_{n-1}|^2+ \cdots +|a_0|^2 }.</math>
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 {{slink||Landau's inequality}}, below.

{{cot|Proof}}
Let {{mvar|z}} be a root of the polynomial

:<math>p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x +a_0.</math>

Setting 
:<math>A=\left(\frac{|a_{n-1}|}{|a_n|},\ldots, \frac{|a_1|}{|a_n|},\frac{|a_0|}{|a_n|}\right),</math>
we have to prove that every root {{mvar|z }} of {{mvar|p}} satisfies
:<math>z\le \left\|(1, \left\|A\right\|_h\right)\|_k.</math>

If <math>|z| \le 1,</math> the inequality is true; so, one may suppose <math>|z| > 1</math> for the remainder of the proof.

Writing the equation as
:<math>-z^n=\frac{a_{n-1}}{a_n}z^{n-1}+\cdots+\frac{a_1}{a_n}z+\frac{a_0}{a_n},</math>
[[Hölder's inequality]] implies
:<math>|z|^n\leq \|A\|_h \cdot\left \|(z^{n-1},\ldots,z, 1) \right \|_k.</math>

If {{math|''k'' {{=}} ∞}}, this is
:<math>|z|^n\leq\|A\|_1\max \left \{|z|^{n-1},\ldots,|z|,1 \right \} =\|A\|_1|z|^{n-1}.</math>
Thus
:<math>|z|\leq \max\{1,\|A\|_1\}.</math>

In the case {{math|1 ≤ ''k'' < ∞}}, the summation formula for a [[geometric progression]], gives

:<math>|z|^n\leq \|A\|_h \left(|z|^{k(n-1)}+\cdots+|z|^k +1\right)^{\frac{1}{k}}=\|A\|_h \left(\frac{|z|^{kn}-1}{|z|^k-1}\right)^{\frac{1}{k}}\leq\|A\|_h \left(\frac{|z|^{kn}}{|z|^k-1}\right)^\frac{1}{k}.</math>
Thus
:<math>|z|^{kn}\leq \left(\|A\|_h\right)^k \frac{|z|^{kn}}{|z|^k-1},</math>
which simplifies to
:<math>|z|^k\leq 1+\left(\|A\|_h\right)^k.</math>

Thus, in all cases
:<math>|z|\leq \left \| \left (1,\|A\|_h \right ) \right \|_k,</math>
which finishes the proof.
{{cob}}

===Other bounds===
Many other upper bounds for the magnitudes of all roots have been given.<ref>{{cite book |first=M. |last=Marden |title=Geometry of Polynomials |publisher=Amer. Math. Soc. |year=1966 |isbn=0-8218-1503-2 }}</ref>

Fujiwara's bound<ref name=Fujiwara1916>{{cite journal |last=Fujiwara |first=M. |year=1916 |title=Über die obere Schranke des absoluten Betrages der Wurzeln einer algebraischen Gleichung |journal=[[Tohoku Mathematical Journal]] |series=First series |volume=10 |pages=167–171 |url=https://www.jstage.jst.go.jp/article/tmj1911/10/0/10_0_167/_pdf }}</ref>
:<math>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\}, </math> 
slightly improves the bound given above by dividing the last argument of the maximum by two.

Kojima's bound is<ref name=Kojima1917>{{cite journal |last=Kojima |first=T. |year=1917 |title=On the limits of the roots of an algebraic equation |journal=Tohoku Mathematical Journal |series=First series |volume=11 |pages=119–127 |url=https://www.jstage.jst.go.jp/article/tmj1911/11/0/11_0_119/_pdf }}</ref>{{check|date=March 2019}}
:<math>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\},</math>
where <math>a_i</math> denotes the {{mvar|i}}th ''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.<ref name=Sun1996>{{cite journal |last1=Sun |first1=Y. J. |last2=Hsieh |first2=J. G. |year=1996 |title=A note on circular bound of polynomial zeros |journal=IEEE Trans Circuits Syst. I |volume=43 |issue=6 |pages=476–478 |doi=10.1109/81.503258 }}</ref> Assume the polynomial is monic with general term {{mvar|a<sub>i</sub>x<sup>i</sup>}}. Sun and Hsieh showed that upper bounds {{math|1 + ''d''<sub>1</sub>}} and {{math|1 + ''d''<sub>2</sub>}} could be obtained from the following equations.

:<math>d_1 = \tfrac{1}{2} \left((| a_{n-1}| - 1) + \sqrt{(|a_{n-1}| - 1 )^2 + 4a } \right), \qquad a = \max \{ |a_i | \}.</math>

{{math|''d''<sub>2</sub>}} is the positive root of the cubic equation

:<math>Q(x) = x^3 + (2 - |a_{n-1}|) x^2 + (1 - |a_{n-1}| - |a_{n-2}| ) x - a, \qquad a = \max \{ |a_i | \}</math>

They also noted that {{math|''d''<sub>2</sub> ≤ ''d''<sub>1</sub>}}.

==Landau's inequality==
The previous bounds are upper bounds for each root separately. '''Landau's inequality''' provides an upper bound for the absolute values of the product of the roots that have an absolute value greater than one. This inequality, discovered in 1905 by [[Edmund Landau]],<ref>E. Landeau, Sur quelques th&or&mes de M. Petrovic relatifs aux zéros des fonctions analytiques, ''Bull. Sot. Math. France'' 33 (1905), 251-261.</ref> has been forgotten and rediscovered at least three times during the 20th century.<ref>M. Mignotte. An inequality about factors of polynomials, ''Math. Comp.'' 28 (1974). 1153-1157.</ref><ref>W. Specht, Abschätzungen der Wurzeln algebraischer Gleichungen, Math. Z. 52 (1949). 310-321.</ref><ref>J. Vincente Gonçalves, L’inégalité de W. Specht. ''Univ. Lisboa Revista Fac. Ci A. Ci. Mat.'' 1 (195O), 167-171.</ref>

This bound of the product of roots is not much greater than the best preceding bounds of each root separately.<ref>{{cite book |last=Mignotte |first=Maurice |chapter=Some useful bounds |title=Computer Algebra : Symbolic and Algebraic Computation |pages=259–263 |publisher=Springer |location=Vienna |year=1983 |isbn=0-387-81776-X |chapter-url=https://books.google.com/books?id=qCX4CAAAQBAJ&pg=PA259 }}</ref>
Let <math>z_1, \ldots, z_n</math> be the {{mvar|n}} roots of the polynomial {{mvar|p}}. If
:<math>M(p)=|a_n|\prod_{j=1}^n \max(1,|z_j|)</math>
is the [[Mahler measure]] of {{mvar|p}},
then 
:<math>M(p)\le \sqrt{\sum_{k=0}^n |a_k|^2}.</math>

Surprisingly, this bound of the product of the absolute values larger than 1 of the roots is not much larger than the best bounds of ''one'' root that have been given above for a single root. This bound is even exactly equal to one of the bounds that are obtained [[#Using Hölder's inequality|using Hölder's inequality]].

This bound is also useful to bound the coefficients of a divisor of a polynomial with integer coefficients:<ref>Mignotte, M. (1988). An inequality about irreducible factors of integer polynomials. ''Journal of number theory'', 30(2), 156-166.</ref> if
:<math>q= \sum_{k=0}^m  b_k x^k</math>
is a divisor of {{math|''p''}}, then
:<math>|b_m|\le|a_n|,</math>
and, by [[Vieta's formulas]],
:<math>\frac{|b_i|}{|b_m|}\le \binom mi \frac{M(p)}{|a_n|},</math>
for {{math|1=''i'' = 0, ..., ''m''}}, where <math>\binom mi</math> is a [[binomial coefficient]]. Thus 
:<math>|b_i|\le \binom mi M(p)\le \binom mi \sqrt{\sum_{k=0}^n |a_k|^2},</math>
and 
:<math>\sum_{i=0}^m |b_i| \le 2^m M(p) \le 2^m \sqrt{\sum_{k=0}^n |a_k|^2}.</math>

==Discs containing some roots==

===From Rouché theorem===

[[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 {{mvar|''R''}} and an integer {{math|0 ≤ ''k'' ≤ ''n''}} such that
:<math>|a_k| R^k > |a_0|+\cdots+|a_{k-1}| R^{k-1}+|a_{k+1}| R^{k+1}+\cdots+|a_n| R^n,</math>
then there are exactly {{math|''k''}} roots, counted with multiplicity, of absolute value less than {{math|''R''}}. 
{{cot|Proof}}
If <math>|z|=R,</math> then
:<math>\begin{align}
|a_0 &+\cdots+a_{k-1}z^{k-1}+a_{k+1} z^{k+1}+\cdots+a_n z^n|\\
&\le |a_0|+\cdots+|a_{k-1}| R^{k-1}+|a_{k+1}| R^{k+1}+\cdots+|a_n| R^n\\
&\le |a_k| R^k \le |a_k z^k|.
\end{align}</math>
By Rouché's theorem, this implies directly that <math>p(z)</math> and <math>z^k</math> have the same number of roots of absolute values less than {{mvar|R}}, counted with multiplicities. As this number is {{mvar|k}}, the result is proved.
{{cob}}

The above result may be applied if the polynomial
:<math>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.</math>
takes a negative value for some positive real value of {{mvar|x}}.

In the remaining of the section, suppose that {{math|''a''<sub>''0''</sub> ≠ 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 {{math|1=''k'' = 0}} and {{math|1=''k'' = ''n''}}, [[Descartes' rule of signs]] shows that the polynomial has exactly one positive real root. If <math>R_0</math> and <math>R_n</math> are these roots, the above result shows that all the roots satisfy 
:<math>R_0\le |z| \le R_1.</math>
As these inequalities apply also to <math>h_0</math> and <math>h_n,</math> 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 {{math|0 < ''k'' < ''n''}}, Descartes' rule of signs implies that <math>h_k(x)</math> either has two positive real roots that are not multiple, or is nonnegative for every positive value of {{mvar|x}}. So, the above result may be applied only in the first case. If <math>R_{k,1}<R_{k,2}</math> are these two roots, the above result implies that
:<math>|z| \le R_{k,1}</math> 
for {{mvar|k}} roots of {{mvar|p}}, and that 
:<math>|z| \ge R_{k,2}</math> 
for the {{math|''n'' – ''k''}} other roots.

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

For computing <math>R_k,</math> one can use the fact that <math>\frac{h(x)}{x^k}</math> is a [[convex function]] (its second derivative is positive). Thus <math>R_k</math> exists if and only if <math>\frac{h(x)}{x^k}</math> 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 <math>\frac{h(x)}{x^k}</math> (it converges rapidly, as the derivative is a [[monotonic function]]).

One can increase the number of existing <math>R_k</math>'s by applying the root squaring operation of the [[Graeffe's method|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 {{math|''n'' + 1}} positive numbers <math>R_0 < R_1 <\dots <R_n</math> such there is exactly one root with an absolute value in the open interval <math>(R_{k-1},R_k),</math> for {{math|1=''k'' = 1, ..., ''n''}}.

===From Gershgorin circle theorem ===
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 {{slink|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.

==Bounds of real roots==

For polynomials with real coefficients, it is often useful to bound only the real roots. It suffices to bound the positive roots, as the negative roots of {{math|''p''(''x'')}} are the positive roots of {{math|''p''(–''x'')}}.

Clearly, every bound of all roots applies also for real roots. But in some contexts, tighter bounds of real roots are useful. For example, the efficiency of the [[Real-root isolation#Method of continued fractions|method of continued fractions]] for [[real-root isolation]] strongly depends on tightness of a bound of positive roots. This has led to establishing new bounds that are tighter than the general bounds of all roots. These bounds are generally expressed not only in terms of the absolute values of the coefficients, but also in terms of their signs.

Other bounds apply only to polynomials whose all roots are reals (see below).

===Bounds of positive real roots===

To give a bound of the positive roots, one can assume <math>a_n >0</math> without loss of generality, as changing the signs of all coefficients does not change the roots.

Every upper bound of the positive roots of 
:<math>q(x)=a_nx^n + \sum_{i=0}^{n-1} \min(0,a_i)x^i</math>
is also a bound of the real zeros of 
:<math>p(x)=\sum_{i=0}^n a_ix^i</math>. 
In fact, if {{mvar|B}} is such a bound, for all {{math|''x'' > ''B''}}, one has {{math|''p''(''x'') ≥ ''q''(''x'') > 0}}.

Applied to Cauchy's bound, this gives the upper bound 
:<math>1+{\textstyle\max_{i=0}^{n-1}} \frac{-a_i}{a_n}</math>
for the real roots of a polynomial with real coefficients. If this bound is not greater than {{val|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 
:<math>2\,{\max_{a_ia_n<0}}\left(\frac{-a_i}{a_n}\right)^{\frac 1{n-i}}.</math>
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 [[Real-root isolation#Method of continued fractions|method of continued fractions]] for [[real-root isolation]].<ref>{{cite journal |last1=Akritas |first1=Alkiviadis G. |first2=A. W. |last2=Strzeboński |first3=P. S. |last3=Vigklas |title=Improving the performance of the continued fractions method using new bounds of positive roots |journal=Nonlinear Analysis: Modelling and Control |year=2008 |volume=13 |issue=3 |pages=265–279 |doi=10.15388/NA.2008.13.3.14557 |doi-access=free }}</ref><ref>Ştefănescu, D. ''Bounds for Real Roots and Applications to Orthogonal Polynomials''. In: V. G. Ganzha, E. W. Mayr and E. V. Vorozhtsov (Editors): Proceedings of the 10th International Workshop on Computer Algebra in Scientific Computing, CASC 2007, pp. 377 – 391, Bonn, Germany, September 16-20, 2007. LNCS 4770, Springer Verlag, Berlin, Heidelberg.</ref>

===Polynomials whose roots are all real===

If all roots of a polynomial are real, [[Edmond Laguerre|Laguerre]] proved the following lower and upper bounds of the roots, by using what is now called [[Samuelson's inequality]].<ref name=Laguerre1880>{{cite journal | author = Laguerre E | title = Sur une méthode pour obtenir par approximation les racines d'une équation algébrique qui a toutes ses racines réelles | pages = 161–172, 193–202 | year = 1880 | journal = [[Nouvelles Annales de Mathématiques]] | series = 2 | volume = 19 | url = http://www.numdam.org/numdam-bin/browse?id=NAM_1880_2_19_ | access-date = 2013-09-03 | archive-date = 2014-07-15 | archive-url = https://web.archive.org/web/20140715062246/http://www.numdam.org/numdam-bin/browse?id=NAM_1880_2_19_ | url-status = dead }}.</ref>

Let <math>\sum_{k=0}^n a_k x^k</math> be a polynomial with all real roots. Then its roots are located in the interval with endpoints
:<math>-\frac{a_{n-1}}{na_n} \pm \frac{n-1}{na_n}\sqrt{a^2_{n-1} - \frac{2n}{n-1}a_n a_{n-2}}.</math>

For example, the roots of the polynomial <math>x^4+5x^3+5x^2-5x-6=(x+3)(x+2)(x+1)(x-1)</math> satisfy
:<math>-3.8118<-\frac{5}{4} - \frac{3}{4}\sqrt{\frac{35}{3}}\le x\le -\frac{5}{4} + \frac{3}{4}\sqrt{\frac{35}{3}}<1.3118.</math>

==Root separation==

The '''root separation''' of a polynomial is the minimal distance between two roots, that is the minimum of the absolute values of the difference of two roots:
:<math>\operatorname{sep}(p) = \min\{|\alpha-\beta|\;;\; \alpha \neq \beta \text{ and } p(\alpha)=p(\beta)=0\}</math>

The root separation is a fundamental parameter of the [[computational complexity]] of [[root-finding algorithm]]s for polynomials. In fact, the root separation determines the precision of number representation that is needed for being certain of distinguishing distinct roots. Also, for [[real-root isolation]], it allows bounding the number of interval divisions that are needed for isolating all roots.

For polynomials with real or complex coefficients, it is not possible to express a lower bound of the root separation in terms of the degree and the absolute values of the coefficients only, because a small change on a single coefficient transforms a polynomial with multiple roots into a [[square-free polynomial]] with a small root separation, and essentially the same absolute values of the coefficient. However, involving the [[discriminant]] of the polynomial allows a lower bound.

For square-free polynomials with integer coefficients, the discriminant is an integer, and has thus an absolute value  that is not smaller than {{val|1}}. This allows lower bounds for root separation that are independent from the discriminant.

Mignotte's separation bound is<ref>{{cite book |last=Mignotte |first=Maurice |date=1982 |title=Some Useful Bounds |url=http://people.dm.unipi.it/gianni/AC-EAG/Mignotte.pdf |publisher=Springer |page=262}}</ref><ref>{{harvnb|Yap|2000|loc=§ VI.7, Proposition 29}}</ref><ref>{{cite journal|first=George E.|last=Collins|author-link=George E. Collins|title=Polynomial minimum root separation|journal=Journal of Symbolic Computation|year=2001|volume= 32|issue=5|pages= 467–473| doi=10.1006/jsco.2001.0481|url=https://core.ac.uk/download/pdf/82808521.pdf |doi-access=free}}</ref>

:<math>\operatorname{sep}(p) >  \frac {\sqrt{3|\Delta(p)|}}{n^{(n+1)/2}(\|p\|_2)^{n-1}},</math>
where <math>\Delta(p)</math> is the discriminant, and <math>\textstyle\|p\|_2=\sqrt{a_0^2+a_1^2+\dots+a_n^2}.</math> 

For a square free polynomial with integer coefficients, this implies 
:<math>\operatorname{sep}(p) >  \frac {\sqrt 3}{n^{n/2+1}(\|p\|_2)^{n-1}}> \frac 1{2^{2s^2}},</math>
where {{mvar|s}} is the [[bit]] size of {{mvar|p}}, that is the sum of the bitsize of its coefficients.

==Gauss–Lucas theorem==
{{main|Gauss–Lucas theorem}}
The Gauss–Lucas theorem states that the [[convex hull]] of the roots of a polynomial contains the roots of the [[derivative]] of the polynomial.

A sometimes useful corollary is that, if all roots of a polynomial have positive real part, then so do the roots of all derivatives of the polynomial.

A related result is [[Bernstein's inequality in mathematical analysis|Bernstein's inequality]]. It states that for a polynomial ''P'' of degree ''n'' with derivative ''P′'' we have
:<math>\max_{|z| \leq 1} \big|P'(z)\big| \le n \max_{|z| \leq 1} \big|P(z)\big|.</math>

==Statistical distribution of the roots==

If the coefficients {{math|''a''<sub>''i''</sub>}} of a random polynomial are independently and identically distributed with a [[mean]] of zero, most complex roots are on the unit circle or close to it. In particular, the real roots are mostly located near {{math|±1}}, and, moreover, their expected number is, for a large degree, less than the [[natural logarithm]] of the degree.

If the coefficients are [[Gaussian distribution|Gaussian distributed]] with a mean of zero and [[variance]] of ''σ'' then the mean density of real roots is given by the Kac formula<ref name=Kac1943>{{cite journal |last=Kac |first=M. |author-link=Mark Kac |year=1943 |title=On the average number of real roots of a random algebraic equation |journal=[[Bulletin of the American Mathematical Society]] |volume=49 |issue=4 |pages=314–320 |doi=10.1090/S0002-9904-1943-07912-8 |doi-access=free }}</ref><ref name=Kac1948>{{cite journal |last=Kac |first=M. |year=1948 |title=On the Average Number of Real Roots of a Random Algebraic Equation (II) |journal=[[Proceedings of the London Mathematical Society]] |series=Second Series |volume=50 |issue=1 |pages=390–408 |doi=10.1112/plms/s2-50.5.390 }}</ref>

: <math> m( x ) = \frac { \sqrt{ A( x ) C( x ) - B( x )^2 }} {\pi A( x )} </math>

where

: <math> \begin{align}
A(x) &= \sigma \sum_{i=0}^{n-1} x^{2i} = \sigma \frac{x^{2n} - 1}{x^2-1}, \\
B(x) &= \frac 1 2 \frac{ d } { dx } A( x ), \\
C(x) &= \frac 1 4 \frac{d^2} {dx^2} A(x) + \frac 1 { 4x } \frac d {dx} A(x).
\end{align} </math>

When the coefficients are Gaussian distributed with a non-zero mean and variance of ''σ'', a similar but more complex formula is known.{{Citation needed|date=June 2013}}

===Real roots===
For large {{math|''n''}}, the mean density of real roots near {{mvar|x}} is asymptotically

: <math> m( x ) = \frac{ 1 } { \pi | 1 - x^2 | } </math>
if <math>x^2-1\ne 0,</math>
and
: <math> m(\pm 1) = \frac 1 \pi \sqrt {\frac{n^2 - 1}{12}} </math>

It follows that the expected number of real roots is, using [[big O notation|big {{mvar|O}} notation]]
: <math> N_n = \frac 2 \pi \ln n + C + \frac 2 {\pi n} +O( n^{ -2 } ) </math>
where {{math|''C''}} is a constant approximately equal to {{val|0.6257358072}}.<ref name=ek>{{cite journal|last1=Edelman|first1=Alan|last2=Kostlan|first2=Eric|title=How many zeros of a random polynomial are real?| journal=Bulletin of the American Mathematical Society|year=1995|volume=32|pages=1–37|doi=10.1090/S0273-0979-1995-00571-9 |issue=1|url=https://www.ams.org/journals/bull/1995-32-01/S0273-0979-1995-00571-9/S0273-0979-1995-00571-9.pdf|doi-access=free}}</ref>

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 {{mvar|i}}th coefficient is equal to <math>\binom ni,</math> the expected number of real roots is <math>\sqrt n.</math><ref name=ek/>

== Geometry of multiple roots ==

A polynomial <math>p</math> can be written in the form of

<math>p(x) = a (x-z_1)^{m_1} \cdots (x-z_k)^{m_k} </math>

with distinct roots <math>z_1,\ldots,z_k</math> and corresponding [[Multiplicity (mathematics)|multiplicities]] <math>m_1,\ldots,m_k</math>. A root <math>z_j</math> is a '''simple root''' if <math>m_j=1</math> or a '''multiple root''' if <math>m_j\ge 2</math>. Simple roots are [[Lipschitz_continuity|Lipschitz continuous]] with respect to coefficients but multiple roots are not. In other words, simple roots have bounded sensitivities but multiple roots are infinitely sensitive if the coefficients are perturbed arbitrarily. As a result, most root-finding algorithms suffer substantial loss of accuracy on multiple roots in numerical computation.

In 1972, [[William Kahan]] proved that there is an inherent stability of multiple roots.<ref name="kah">{{cite journal |last1=Kahan |first1=W. |title=Conserving confluence curbs ill-condition |journal=Technical Report 6, Computer Science, Univ. Of California |date=1972}}</ref> Kahan discovered that polynomials with a particular set of multiplicities form what he called a ''pejorative manifold'' and proved that a multiple root is [[Lipschitz continuity|Lipschitz continuous]] if the perturbation maintains its multiplicity.

This geometric property of multiple roots is crucial in [[Polynomial_root-finding_algorithms#Numerical_computation_of_multiple_roots|numerical computation of multiple roots]].

==See also==
* {{annotated link|Descartes' rule of signs}}
* {{annotated link|Marden's theorem}}
* {{annotated link|Newton's identities}}
* [[Quadratic function#Upper bound on the magnitude of the roots]]
* {{annotated link|Real-root isolation}}
* {{annotated link|Root-finding of polynomials}}
* {{annotated link|Square-free polynomial}}
* {{annotated link|Vieta's formulas}}
* [[Cohn's theorem]] relating the roots of a self-inversive polynomial with the roots of the reciprocal polynomial of its derivative.

==Notes==
{{Reflist|30em}}

==References==
* {{cite book | last1=Rahman | first1=Q. I. | last2=Schmeisser | first2=G. | title=Analytic theory of polynomials | series=London Mathematical Society Monographs. New Series | volume=26 | location=Oxford | publisher=[[Oxford University Press]] | year=2002 | isbn=0-19-853493-0 | zbl=1072.30006 }}
* {{cite book | last=Yap | first= Chee-Keng| title=Fundamental problems of algorithmic algebra| publisher=[[Oxford University Press]]| year = 2000|isbn=978-0195125160|
url=http://160592857366.free.fr/joe/ebooks/ShareData/Fundamental%20Problems%20in%20Algorithmic%20Algebra%201993%20Yap.pdf}}.

==External links==
*[http://math.ucr.edu/home/baez/roots/ The beauty of the roots], a visualization of the distribution of all roots of all polynomials with degree and integer coefficients in some range.

[[Category:Polynomials]]