In mathematics, a univariate polynomial of degree with real or complex coefficients has complex roots (if counted with their multiplicities). They form a multiset of points in the complex plane, whose geometry 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 for sufficiently large.
Notation In this article, a polynomial is always denoted
where are real or complex numbers and ; 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 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 .
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 and is an upper bound of the absolute values of the roots of
then is a lower bound of the absolute values of the roots 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 first to provide upper bounds on all complex roots. Lagrange's bound isLagrange J–L (1798) Traité de la résolution des équations numériques. Paris.
and Cauchy's bound isCauchy Augustin-Louis (1829). Exercices de mathématique. Œuvres 2 (9) p.122
Lagrange's bound is sharper (smaller) than Cauchy's bound only when 1 is larger than the sum of all 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 one gets
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 ,
Thus
Solving in , 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.
These bounds are not invariant by scaling. That is, the roots of the polynomial are the quotient by of the root of , and the bounds given for the roots of are not the quotient by of the bounds of . Thus, one may get sharper bounds by minimizing over possible scalings. This gives
and
for Lagrange's and Cauchy's bounds respectively.
Another bound, originally given by Lagrange, but attributed to Zassenhaus by Donald Knuth, is
This bound is invariant by scaling.
Let be the largest for . Thus one has
for If is a root of , one has
and thus, after dividing by
As we want to prove , we may suppose that (otherwise there is nothing to prove). Thus
which gives the result, since
Lagrange improved this latter bound into the sum of the two largest values (possibly equal) in the sequence
Lagrange also provided the bound
where denotes the 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 -norm. The -norm of a sequence
is
for any real number , and
If with , and , an upper bound on the absolute values of the roots of is
For and , one gets respectively Cauchy's and Lagrange's bounds.
For , one has the bound
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 , below.
Let be a root of the polynomial
Setting
we have to prove that every root of satisfies
If the inequality is true; so, one may suppose for the remainder of the proof.
Writing the equation as
Hölder's inequality implies
If , this is
Thus
In the case , the summation formula for a geometric progression, gives
Thus
which simplifies to
Thus, in all cases
which finishes the proof.
Other bounds Many other upper bounds for the magnitudes of all roots have been given.
Fujiwara's bound
slightly improves the bound given above by dividing the last argument of the maximum by two.
Kojima's bound is
where denotes the 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. Assume the polynomial is monic with general term . Sun and Hsieh showed that upper bounds and could be obtained from the following equations.
is the positive root of the cubic equation
They also noted that .
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,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. has been forgotten and rediscovered at least three times during the 20th century.M. Mignotte. An inequality about factors of polynomials, Math. Comp. 28 (1974). 1153-1157.W. Specht, Abschätzungen der Wurzeln algebraischer Gleichungen, Math. Z. 52 (1949). 310-321.J. Vincente Gonçalves, L’inégalité de W. Specht. Univ. Lisboa Revista Fac. Ci A. Ci. Mat. 1 (195O), 167-171.
This bound of the product of roots is not much greater than the best preceding bounds of each root separately. Let be the roots of the polynomial . If
is the Mahler measure of , then
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.
This bound is also useful to bound the coefficients of a divisor of a polynomial with integer coefficients:Mignotte, M. (1988). An inequality about irreducible factors of integer polynomials. Journal of number theory, 30(2), 156-166. if
is a divisor of , then
and, by Vieta's formulas,
for , where 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 then
By Rouché's theorem, this implies directly that and 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, 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, 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 and are these roots, the above result shows that all the roots satisfy
As these inequalities apply also to and 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 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 are these two roots, the above result implies that
for roots of , and that
for the other roots.
Instead of explicitly computing and it is generally sufficient to compute a value such that (necessarily ). These have the property of separating roots in terms of their absolute values: if, for , both and exist, there are exactly roots such that
For computing one can use the fact that is a convex function (its second derivative is positive). Thus exists if and only if 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 (it converges rapidly, as the derivative is a monotonic function).
One can increase the number of existing '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 positive numbers such there is exactly one root with an absolute value in the open interval for .
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 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 are the positive roots of .