Books in black and white
 Books 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
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.
6. SEPARATION OF THE ROOTS OF A POLYNOMIAL

167

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.

Proof

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 > (²Ä²1/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 > ²Ä²1/4 21-^-1')/4 M(P)-(^-I)/2.

Proof

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.

O-^Id

Therefore,

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