Inmathematics, aunivariate polynomial of degreen with real or complex coefficients hasn complexroots, if counted with theirmultiplicities. They form a multiset ofn points in thecomplex plane. This article concerns thegeometry 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 forroot-finding algorithms for polynomials, either for tuning them, or for computing theircomputational complexity.

Some other properties are probabilistic, such as the expected number of real roots of a random polynomial of degreen with real coefficients, which is less than${\displaystyle 1+\frac{2}{\pi }\ln (n)}$ forn sufficiently large.

In this article, a polynomial that is considered is always denoted

${\displaystyle p(x)=a_0+a_{1}x+\cdots +a_n{x}^n,}$

where${\displaystyle a_0,\dots ,a_n}$ are real orcomplex numbers and${\displaystyle a_n\ne 0}$; thus${\displaystyle n}$ is the degree of the polynomial.

Then roots of a polynomial of degreen dependcontinuously on the coefficients. For simple roots, this results immediately from theimplicit 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 (seeWilkinson's polynomial). A consequence is that, for classical numericroot-finding algorithms, the problem of approximating the roots given the coefficients can beill-conditioned for many inputs.

Thecomplex conjugate root theorem states that if the coefficientsof a polynomial are real, then the non-real roots appear in pairs of the form(a +ib,a –ib).

It follows that the roots of a polynomial with real coefficients aremirror-symmetric with respect to the real axis.

This can be extended toalgebraic conjugation: the roots of a polynomial withrational coefficients areconjugate (that is, invariant) under the action of theGalois group of the polynomial. However, this symmetry can rarely be interpreted geometrically.

Upper bounds on the absolute values of polynomial roots are widely used forroot-finding algorithms, either for limiting the regions where roots should be searched, or for the computation of thecomputational 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${\displaystyle a_n\ne 0,}$ andU is an upper bound of the absolute values of the roots of

${\displaystyle a_0+a_{1}x+\cdots +a_n{x}^n,}$

then1/U is a lower bound of the absolute values of the roots of

${\displaystyle a_n+a_{n-1}x+\cdots +a_0{x}^n,}$

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 andCauchy 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|,\dots ,\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 theGershgorin circle theorem applied to thecompanion matrix of the polynomial and itstranspose. They can also be proved by elementary methods.

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

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

and

${\displaystyle \underset{s\in {\mathbb{R}}_{+}}{min}\left(s+\underset{0\le i\le n-1}{max}\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 byDonald Knuth, is^[4]

${\displaystyle 2max\left\{\left|\frac{a_{n-1}}{a_n}\right|,{\left|\frac{a_{n-2}}{a_n}\right|}^{1/2},\dots ,{\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},\dots ,{\left|\frac{a_0}{a_n}\right|}^{1/n}\right].}$

Lagrange also provided the bound^{[citation needed]}

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

where${\displaystyle a_i}$ denotes theithnonzero 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 everyh-norm. Theh-norm of a sequence

${\displaystyle s=(a_0,\dots ,a_n)}$

is

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

for any real numberh ≥ 1, and

${\displaystyle \Vert s{\Vert }_{\mathrm{\infty }}=\underset{i=0}{\overset{n}{max}}|a_i|.}$

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

${\displaystyle \frac{1}{|a_n|}\Vert (|a_n|,\Vert (|a_{n-1}|,\dots ,|a_0|){\Vert }_h){\Vert }_k.}$

Fork = 1 andk = ∞, one gets respectively Cauchy's and Lagrange's bounds.

Forh =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 2max\left\{\left|\frac{a_{n-1}}{a_n}\right|,{\left|\frac{a_{n-2}}{a_n}\right|}^{\frac{1}{2}},\dots ,{\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][verification needed]}

${\displaystyle 2max\left\{\left|\frac{a_{n-1}}{a_n}\right|,\left|\frac{a_{n-2}}{a_{n-1}}\right|,\dots ,\left|\frac{a_0}{2a_1}\right|\right\},}$

where${\displaystyle a_i}$ denotes theithnonzero 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 thegeometric 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 terma_ixⁱ. Sun and Hsieh showed that upper bounds1 +d₁ and1 +d₂ could be obtained from the following equations.

${\displaystyle d_1=\frac{1}{2}\left((|a_{n-1}|-1)+\sqrt{(|a_{n-1}|-1{)}^2+4a}\right),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,a=max\{|a_i|\}}$

They also noted thatd₂ ≤d₁.

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 byEdmund Landau,^[9] has been forgotten and rediscovered at least three times during the 20th century.^[10][11][12]

This bound of the product of roots is not much greater than the best preceding bounds of each root separately.^[13]Let${\displaystyle z_1,\dots ,z_n}$ be then roots of the polynomialp. If

${\displaystyle M(p)=|a_n|\prod _{j=1}^{n}max(1,|z_j|)}$

is theMahler measure ofp,then

${\displaystyle M(p)\le \sqrt{\sum _{k=0}^n|a_k{|}^2}.}$

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

This bound is also useful to bound the coefficients of a divisor of a polynomial with integer coefficients:^[14] if

${\displaystyle q=\sum _{k=0}^m{b}_k{x}^k}$

is a divisor ofp, then

${\displaystyle |b_m|\le |a_n|,}$

and, byVieta's formulas,

${\displaystyle \frac{|b_i|}{|b_m|}\le (\genfrac{}{}{0ex}{}{m}{i})\frac{M(p)}{|a_n|},}$

fori = 0, ...,m, where${\displaystyle (\genfrac{}{}{0ex}{}{m}{i})}$ is abinomial coefficient. Thus

${\displaystyle |b_i|\le (\genfrac{}{}{0ex}{}{m}{i})M(p)\le (\genfrac{}{}{0ex}{}{m}{i})\sqrt{\sum _{k=0}^n|a_k{|}^2},}$

and

${\displaystyle \sum _{i=0}^m|b_i|\le 2^{m}M(p)\le 2^m\sqrt{\sum _{k=0}^n|a_k{|}^2}.}$

Rouché's theorem allows defining discs centered at zero and containing a given number of roots. More precisely, if there is a positive real numberR and an integer0 ≤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 exactlyk roots, counted with multiplicity, of absolute value less thanR.

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 ofx.

In the remaining of the section, suppose thata₀ ≠ 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.

Fork = 0 andk =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\le |z|\le 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.

For0 <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 ofx. So, the above result may be applied only in the first case. If are these two roots, the above result implies that

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

fork roots ofp, and that

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

for then –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 (necessarily). These${\displaystyle R_k}$ have the property of separating roots in terms of their absolute values: if, forh <k, both${\displaystyle R_h}$ and${\displaystyle R_k}$ exist, there are exactlyk –h rootsz such that

For computing${\displaystyle R_k,}$ one can use the fact that${\displaystyle \frac{h(x)}{x^k}}$ is aconvex 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 anyoptimization 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 amonotonic function).

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

TheGershgorin circle theorem applies thecompanion matrix of the polynomial on a basis related toLagrange interpolation to define discs centered at the interpolation points, each containing a root of the polynomial; seeDurand–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.

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 ofp(x) are the positive roots ofp(–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 themethod of continued fractions forreal-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).

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, ifB is such a bound, for allx >B, one hasp(x) ≥q(x) > 0.

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

${\displaystyle 1+\underset{i=0}{\overset{n-1}{max}}\frac{-a_i}{a_n}}$

for the real roots of a polynomial with real coefficients. If this bound is not greater than1, 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

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 themethod of continued fractions forreal-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 calledSamuelson'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}}{n{a}_n}\pm \frac{n-1}{n{a}_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

Theroot 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:

${\displaystyle \mathrm{sep}(p)=min\{|\alpha -\beta |;\alpha \ne \beta \text{ and }p(\alpha )=p(\beta )=0\}}$

The root separation is a fundamental parameter of thecomputational complexity ofroot-finding algorithms for polynomials. In fact, the root separation determines the precision of number representation that is needed for being certain of distinguishing distinct roots. Also, forreal-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 asquare-free polynomial with a small root separation, and essentially the same absolute values of the coefficient. However, involving thediscriminant 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 than1. This allows lower bounds for root separation that are independent from the discriminant.

Mignotte's separation bound is^[18][19][20]

${\displaystyle \mathrm{sep}(p)>\frac{\sqrt{3|\mathrm{\Delta }(p)|}}{n^{(n+1)/2}(\Vert p{\Vert }_2{)}^{n-1}},}$

where${\displaystyle \mathrm{\Delta }(p)}$ is the discriminant, and${\displaystyle \Vert p{\Vert }_2=\sqrt{a_0^2+a_1^2+\cdots +a_n^2}.}$

For a square free polynomial with integer coefficients, this implies

${\displaystyle \mathrm{sep}(p)>\frac{\sqrt{3}}{n^{n/2+1}(\Vert p{\Vert }_2{)}^{n-1}}>\frac{1}{2^{2s^2}},}$

wheres is thebit size ofp, that is the sum of the bitsize of its coefficients.

The Gauss–Lucas theorem states that theconvex hull of the roots of a polynomial contains the roots of thederivative 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 isBernstein's inequality. It states that for a polynomialP of degreen with derivativeP′ we have

${\displaystyle \underset{|z|\le 1}{max}|P^{\prime }(z)|\le n\underset{|z|\le 1}{max}|P(z)|.}$

If the coefficientsa_i of a random polynomial are independently and identically distributed with amean of zero, most complex roots are on the unit circle or close to it. In particular, the real roots are mostly located near±1, and, moreover, their expected number is, for a large degree, less than thenatural logarithm of the degree.

If the coefficients areGaussian distributed with a mean of zero andvariance ofσ then the mean density of real roots is given by the Kac formula^[21][22]

${\displaystyle m(x)=\frac{\sqrt{A(x)C(x)-B(x{)}^2}}{\pi A(x)}}$

where

When the coefficients are Gaussian distributed with a non-zero mean and variance ofσ, a similar but more complex formula is known.^{[citation needed]}

For largen, the mean density of real roots nearx is asymptotically

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

if${\displaystyle x^2-1\ne 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, usingbigO notation

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

whereC is a constant approximately equal to0.6257358072.^[23]

In other words,the expected number of real roots of a random polynomial of high degree is lower than thenatural 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 theith coefficient is equal to${\displaystyle (\genfrac{}{}{0ex}{}{n}{i}),}$ the expected number of real roots is${\displaystyle \sqrt{n}.}$^[23]

A polynomial${\displaystyle p}$ can be written in the form of

${\displaystyle p(x)=a(x-z_1{)}^{m_1}\cdots (x-z_k{)}^{m_k}}$

with distinct roots${\displaystyle z_1,\dots ,z_k}$ and correspondingmultiplicities${\displaystyle m_1,\dots ,m_k}$. A root${\displaystyle z_j}$ is asimple root if${\displaystyle m_j=1}$ or amultiple root if${\displaystyle m_j\ge 2}$. Simple roots areLipschitz 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.^[24] Kahan discovered that polynomials with a particular set of multiplicities form what he called apejorative manifold and proved that a multiple root isLipschitz continuous if the perturbation maintains its multiplicity.

This geometric property of multiple roots is crucial innumerical computation of multiple roots.

• Descartes' rule of signs – Counting polynomial real roots based on coefficients
• Marden's theorem – On zeros of derivatives of cubic polynomials
• Newton's identities – Relations between power sums and elementary symmetric functions
• Quadratic function#Upper bound on the magnitude of the roots
• Real-root isolation – Methods for locating real roots of a polynomial
• Root-finding of polynomials – Algorithms for finding zeros of polynomials
• Square-free polynomial – Polynomial with no repeated root
• Vieta's formulas – Relating coefficients and roots of a polynomial
• Cohn's theorem relating the roots of a self-inversive polynomial with the roots of the reciprocal polynomial of its derivative.

• Rahman, Q. I.; Schmeisser, G. (2002).Analytic theory of polynomials. London Mathematical Society Monographs. New Series. Vol. 26. Oxford:Oxford University Press.ISBN 0-19-853493-0.Zbl 1072.30006.
• Yap, Chee-Keng (2000).Fundamental problems of algorithmic algebra(PDF).Oxford University Press.ISBN 978-0195125160..

• The beauty of the roots, a visualization of the distribution of all roots of all polynomials with degree and integer coefficients in some range.

• Polynomials

• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from March 2019
• All pages needing factual verification
• Wikipedia articles needing factual verification from March 2019
• Articles with unsourced statements from June 2013