Geometrical properties of polynomial roots

In mathematics, a univariate polynomial of degree with real or complex coefficients has complex roots, if counted with their multiplicities. They form a set of 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 algorithms 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 with real coefficients, which is less than formula_1 for sufficiently large.
In this article, a polynomial that is considered is always denoted 
where formula_3 are real or complex numbers and formula_4; thus is the degree of the polynomial.
Continuous dependence on coefficients.
The roots of a polynomial of degree depend 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 algorithms, the problem of approximating the roots given the coefficients is ill-conditioned.
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 .
It follows that the roots of a polynomial with real coefficients are mirror-symmetric with respect to the real axis.
This can be extended to algebraic conjugation: the roots of a polynomial with 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 algorithms, 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 formula_5 and is an upper bound of the absolute values of the roots of 
then is a lower bound of the absolute values of 
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 firsts to provide upper bounds on all complex roots. Lagrange's bound is
 formula_8
and Cauchy's bound is
 formula_9
Lagrange's bound is sharper (smaller) than Cauchy's bound only when 1 is larger than the sum of all formula_10 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.
If is a root of the polynomial, and one has 
Dividing by formula_12 one gets 
for , where formula_14 is a binomial coefficient. Thus 
and 
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 and an integer such that
then there are exactly roots, counted with multiplicity, of absolute value less than . 
If formula_18 then
By Rouché's theorem, this implies directly that formula_20 and formula_21 have the same number of roots of absolute values less than , counted with multiplicities. As this number is , the result is proved.
The above result may be applied if the polynomial
takes a negative value for some positive real value of .
In the remaining of the section, with suppose that . 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, for getting a polynomial with a nonzero constant term.
For and , Descartes' rule of signs shows that the polynomial has exactly one positive real root. If formula_23 and formula_24 are these roots, the above result shows that all the roots verifies 
A these inequalities apply also to formula_26 and formula_27 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 , Descartes' rule of signs implies that formula_28 either has two positive real roots that are not multiple, or is nonnegative for every positive value of . So, the above result may be applied only in the first case. If formula_29 are these two roots, the above result implies that
for roots of , and that 
for the other roots.
Instead of computing explicitly formula_32 and formula_33 it is generally sufficient to compute a value formula_34 such that formula_35 (necessarily formula_36). These formula_34 have the property of separating roots in terms of their absolute values: if, for , both formula_38 and formula_34 exist, there are exactly roots such that formula_40
For computing formula_41 one can use that formula_42 is a convex function (its second derivative is positive). Thus formula_34 exists if and only if formula_42 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 formula_42 (it converges rapidly, as the derivative is a monotonic function).
One can increase the number of existing formula_34's by applying the root squaring operation of the Dandelin–Graeffe iteration. If the roots have distinct absolute values, one can eventually separate completely the roots in terms of their absolute values, that is compute positive numbers formula_47 such there is exactly one root with an absolute value in the open interval formula_48 for .
From Gershgorin circle theorem.
The Gershgorin circle theorem applied the companion matrix of the polynomial on a basis related to Lagrange interpolation provides discs centered at the interpolation points and each containing a root of the polynomial; see for details.
If the interpolation points are close to the roots of the roots of the polynomial, the radiuses 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 are the positive roots of .
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 method of continued fractions for real-root isolation strongly depends on tightness of a bound of positive roots. This has led to establish 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.
For giving a bound of the positive roots, one can suppose formula_49 without loss of generality, as changing the signs of all coefficients does not change the roots.
Every upper bound of the positive roots of 
is also a bound for the real zeros of 
In fact, if is such a bound, for all , one has
Applied to Cauchy's bound, this gives the upper bound 
for the real roots of a polynomial with real coefficients. If this bound is not greater than , 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 defined as being zero.
Other bounds have been recently developed, mainly for the need of the method of continued fractions for real-root isolation.
Polynomials whose roots are all real.
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.
Let formula_54 be a polynomial with all real roots. Then its roots are located in the interval with endpoints
For example, the roots of the polynomial formula_56 satisfy
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:
The root separation is a fundamental parameter of the computational complexity of root-finding algorithms for polynomials. In fact, the root separation determines the precision of number representation that is needed for being sure of distinguishing different 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 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 in 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 lower than . This allows lower bounds for root separation that are independent from the discriminant.
Mignotte's separation bound is
where formula_60 is the discriminant, and formula_61 
For a square free polynomial with integer coefficients, this implies 
where is the bit size of , that is the sum of the bitsize of its coefficients.
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. It states that for a polynomial "P" of degree "n" with derivative "P′" we have
Statistical distribution of the roots.
If the coefficients 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 , and, moreover, their expected number is, for a large degree, less than the natural logarithm of the degree.
If the coefficients are Gaussian distributed with a mean of zero and variance of "σ" then the mean density of real roots is given by the Kac formula
where
When the coefficients are Gaussian distributed with a non-zero mean and variance of "σ", a similar but more complex formula is known.
Real roots.
For large , the mean density of real roots near is asymptotically
if formula_67
and
It follows that the expected number of real roots is, using big notation
where is a constant approximately equal to .
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 th coefficient is equal to formula_70 the expected number of real roots is formula_71