in black and white
Main menu
Share a book About us Home
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

Mathematics for computer algebra - Mignotte M.

Mignotte M. Mathematics for computer algebra - New York, 1992. - 92 p.
ISBN 0-387-97675-2
Download (direct link): mathforcomputer1992.djvu
Previous << 1 .. 2 3 4 5 6 7 < 8 > 9 10 11 12 13 14 .. 25 >> Next

6. Separation of the roots of a polynomial

jI. Notations

In this section, we consider a polynomial P, of degree d, where d is at least equal to two, with complex coefficients and with complex roots ax,..., ad, which is given by

P(X) = adXd H--------1- O0 = ad(X - ai) (X a^), ^a0 0,

and whose roots are numbered so that we have |ai| > > |ay|.

The minimal distance between two distinct roots of P is the quantity

sep(P) := min {Ia, - aj|; { a,-},

f On the distribution of the roots of polynomials, Ann. Math., 51, 1950, p. 105-119.

I T. Ganelius, Sequences of analytic functions and their zeros, Arkiv for Math., 3, 1958, p. 1-50.


where, by convention, sep (P) = oo if P does not have two distinct roots. The discriminant of the polynomial P is given by the formula

A = af~2 JJ(Qi-Oi)2. i<j

If the coefficients Cii are all integers, then the discriminant is also an integer.

2. A lower bound for sep (P)

The useful quantity to consider to get a lower bound for sep (P) is the discriminant of the polynomial. We know that the discriminant is also given by the expression

A = a% jdet (afc)o<fc<d,o</*<d}

With an elementary manipulation of the determinant D, which is in the right-hand side and the inequality of Hadamard, we easily get the inequalities

|D| ? (? Iof - Ojhlfl (1 + M2 + ' ' + ۓ-2)1/!

h=l '

< Iai - ctj| d(d+2)/2 max {I, IctiI)-1 (M(P)/|ad|)

for any choice of distinct indices and j. By taking two indices and j such that Iai ctj| = sep (P), we get the following result.

Proposition 4.10. Let P be a polynomial tuiih complex coefficients of discriminant . Then, the minimal distance between two of its distinct roots, denoted sep (P), satisfies the inequality

sep(P) > d~(d+2)/2 ||1/2 M(P)1"1 > cT(<1+2)/2 ||1/2 ||P||1-<1.

The most frequent case for the estimate of sep (P) is the case of polynomials with integer coefficients. Then Proposition 4.10 can be dramatically simplified.
Theorem 4.6. Let P be a nonconstant polynomial with integer coefficients, then sep (P) satisfies

sep(P) > d-^+2)/2 M(P)1_d > d~(<1+2>/2 ||P||1_<1.


When the polynomial P has no multiple root, we only have to notice that the discriminant of P is a nonzero integer, and hence we have | A| > I. However, if P admits multiple roots, there exists a polynomial Q, with integer coefficients, that divides P and for which sep (Q) = sep (P). We conclude by applying the estimate of the corollary to the polynomial Q, using the trivial inequalities M(Q) < M(P) and deg(Q) < deg(P). []

3. Other lower bounds for the distance between two roots

Let us again study the discriminant .

Let Cl be a set of indices (i,j) such that Cl C {(i,j); I < < j < d} and Cl' = {j : (i,j) fi}. By using the trivial inequality

Iz z'\ <2 max{l, \z\} max{l, \z'\}, we get the estimate

IAI = N2d-2 l^-^-l2 1^-?!2

< 2d(d-l)/2-k . |ad|2<i-2 Iai-Qj-I2


X |ai|2(<l-1) |a2|2(d_2) Iad-II-2 IT2, where = Card Cl and = Iljefi' IaJ I-

Hence we obtain the following result.

Proposition 4.11. Let Cl be a set of couples of indices (i,j) that satisfy the inequalities I < < j < d.

We designate by Cl' the set of indices j such that (i,j) belongs to fi. We suppose that P is a polynomial with real coefficients. Using the above notations for the polynomial P and its roots, we have

Iai - cy| > |.|1/2 2*-^-1)/2 Iaal1-1 (ij)eto

X ^-^^-'--1 |a,-|.
This proposition has the following applications.

Corollary. The notations are the same as in Proposition 4-11- Let Qi and ctj be two distinct roots of the polynomial P. Then, we have the following estimates :

(i) If Cti is real and ctj is not, then

K-OiI > Kl IodI1-1 Io1I1-1-.-1?-!!-1)1'3,

which implies

Iai-Qj-I > (IJ1/2 22-^"1)/2 M(P)1"*1)173.

(U) If oti and ctj are both imaginary and nonconjugate then

Iai-OjI > ||1/4 21_d(<1_1)/4 I a j-1 (|ad|1-<1|a1|1-<1 la^-1)172, which implies

Iai-OjI > IJ1/4 21-^-1')/4 M(P)-(^-I)/2.


In case (i), take fi = {(i, j), (i,j'), (j,j')}, where j' is the index of the complex conjugate of ctj. Then, use the proposition and the inequality

Ictj otj< I < 2|aj -QjI-

In case (ii), we choose = {(i, j), (i,j')} where i' and j1 are the indices of the complex conjugates of Oi and Qj. []

4- Use of Galois properties

Suppose that the polynomial P with integer coefficients is irreducible on the field Q of rational numbers. Let d be the degree of P and let 6 be the degree of the field Q(Qi) over the field Q. Then consider the number q defined by the formula q = 2 <(* ~ aj)> where a runs over the set E of the embeddings of the field QKai, ctj) in the field C. This number q is a nonzero rational integer, hence

I < M < k - OijI |ad|25 Icr(Qi) + Cr(Qj)I.



I < Iai-OjI IadI25 ^2 max {|()|, |<(_,-)|} Id
Previous << 1 .. 2 3 4 5 6 7 < 8 > 9 10 11 12 13 14 .. 25 >> Next