§1. Elementary Properties  Lecture VI  Page 1

Lecture VI Roots of Polynomials

From a historical viewpoint, it is quite appropriate to call root finding for polynomials the Fundamental Computational Problem of algebra. It occupied mathematicians continuously from the earliest days, and was until the 19th century one of their major preoccupations. Descartes, Newton, Euler, Lagrange and Gauss all wrote on this subject. This interest has always been intensely computational in nature, which strikes a chord with modern computer science. The various extensions of natural numbers (negative^{1}, rational, algebraic and complex numbers) were but attempts to furnish entities as roots. Group theory, for instance, originated in this study of roots.

After the introduction of algebra through the Arab mathematicians in the 13th century, Italian algebraists attacked the problem of solving equations of degree 3 and 4, culminating in Cardan’s “Ars Magna” (The Great Art, 1545). Descartes’ treatise (1637) and Euler’s Algebra (1770) can be seen as attempts to generalize these solutions. The algebraic approach to solving polynomial equations reached a new level of sophistication with the impossibility demonstrations of Abel and Wantzel. By “algebraic approach” we mean the determination of roots in terms of radical expressions.

The numerical approximation of roots represent the other approach to the Fundamental Problem. Here, Vieta (1600) published the first solution. These were improved by others, culminating in the well known method of Newton (1669). Horner’s contribution was to organize Newton’s method for polynomials in a very efficiently hand-calculable form. One ought not minimize such a contribution! Indeed contemporary research in algorithms follows the same spirit. The main difference is that whereas we are precise about our computational models, Horner’s implicit model was the “human-hand-calculator”. Simpson, the Benoullis, Lagrange and others continued this line of research.

Modern treatment of the fundamental problem may be found in Henrici [5], Obreschkoff [10], Ostrowski [11] and Marden [7]. Unlike these references, our treatment here is slanted towards an emphasis on real roots. Although complex roots include real roots, we will see that one can also reduce the problem of finding complex roots to real roots. But more pertinent, we are interested in “infallible methods”. Collins [3], an early advocate of this approach, noted that we prefer to make infallible algorithms faster, whereas others have sought to make fast algorithms less fallible (cf. [6]). Along this tradition, recent work of Schönhage (1981), Pan (1985) and Renegar (1988) show how to approximate all complex roots of a polynomial to any prescribed accuracy ϵ > 0, in time O(n^{2} log n(n log n + log \frac{1}{ϵ})). Recently, Neff (1990) proved that the problem of root finding is “parallelizable” (in NC).

§1. Elementary Properties of Polynomials

There is an amazing wealth of material on roots of polynomials (cf. [7,10]). Here we only review some basic facts.

1The term “imaginary numbers” shows the well-known bias in favor of real numbers. Today, the term “negative numbers” has hardly any lingering negative (!) connotation but a bias was evident in the time of Descartes: his terms for positive and negative roots are (respectively) “true” and “false” roots [15, p. 90].

Complex Polynomials. Consider a complex polynomial,

A(X) = ∑_{i=0}^{n} a_{i}X^{i}, a_{n} ≠ 0.

C1. Let c ∈ . Then for some B(X) ∈ [X],

A(X) = B(X) · (X − c) + A(c).

Thus c is a root of A(X) iff A(c) = 0, iff A(X) = B(X)·(X −c). Since deg B = deg(A)−1, we conclude by induction that A(X) has at most deg A roots. This is the easy half of the fundamental theorem of algebra.

C2. Taylor’s expansion of A(X) at c ∈ :

A(X) = A(c) + \frac{A′(c)}{1!}(X − c) + \frac{A′′(c)}{2!}(X − c)^{2} + ⋯ + \frac{A^{(n)}(c)}{n!}(X − c)^{n}.

C3. A(X) is determined by its value at n + 1 distinct values of X. This was seen as a consequence of the Chinese Remainder Theorem in Lecture IV.1

C4. (The Fundamental Theorem of Algebra) A(X) has exactly n (not necessarily distinct) complex roots, α_{1},…, α_{n} ∈ . This was proved in the last lecture. By repeated application of Property C1, we can write

A(X) = a_{n} ∏_{i=1}^{n}(X − α_{i}).  (1)

Definition: If α occurs m ≥ 0 times among the roots α_{1},…, α_{n}, we say α is a root of multiplicity m of A(X). Alternatively, we say α is an m-fold root of A(X). However, when we say “α is a root of A” without qualification about its multiplicity, we presuppose the multiplicity is positive, m ≥ 1. A root is simple or multiple according as m = 1 or m ≥ 2. We say A is square-free it it has no multiple roots.

C5. If α is a root of A(X) of multiplicity m ≥ 1 then α is a root of its derivative A′(X) of multiplicity m − 1. Proof. Write A(X) = (X − α)^{m}B(X) where B(α) ≠ 0. Then A′(X) = m(X − α)^{m−1}B(X) + (X − α)^{m}B′(X). Clearly α has multiplicity ≥ m − 1 as a root of A′(X). Writing

C(X) = \frac{A′(X)}{(X − α)^{m−1}} = mB(X) + (X − α)B′(X),

we conclude C(α) = mB(α) ≠ 0. Hence α has multiplicity exactly m − 1 as a root of A′(X). Q.E.D.

Corollary 1 The polynomial

\frac{A(X)}{GCD(A(X), A′(X))}  (2)

is square-free and contains exactly the distinct roots of A(X).

C6. The derivative A′(X) can be expressed in the form

\frac{A′(X)}{A(X)} = \frac{1}{X − α_{1}} + \frac{1}{X − α_{2}} + ⋯ + \frac{1}{X − α_{n}} .

This follows by taking derivatives on both sides of equation (1) and dividing by A(X). The rational function A′(X)/A(X) is also called the logarithmic derivative since it is equal to \frac{d log A(X)}{dX}. There are very interesting physical interpretations of A′/A. See [7, p. 6].

C7. A(X) is a continuous function of X. This follows from the continuity of the multiplication and addition functions.

C8. The roots A(X) are continuous functions of the coefficients of A(X). We need to state this precisely: suppose α_{1},…, α_{k} are the distinct roots of A(X) where α_{i} has multiplicity m_{i} ≥ 1, and let D_{1},…, D_{k} be any set of discs such that each D_{i} contains α_{i} but not α_{j} if j ≠ i. Then there exists an ϵ > 0 such that for all ϵ_{0},…, ϵ_{n} with |ϵ_{i}| < ϵ, the polynomial

B(X) = ∑_{i=0}^{n}(a_{i} + ϵ_{i})X^{i}

has exactly m_{i} roots (counted with multiplicity) inside D_{i} for i = 1,…, k. For proof, see [7, p. 3].

C9. For any c ∈ , there is a root α^{∗} ∈ such that

|c − α^{∗}| ≤ (|A(c)|/|a_{n}|)^{1/n}.

In proof, observe that |A(c)| = |a_{n}| ∏_{i=1}^{n} |c − α_{i}| in the notation of equation (1). We just choose α^{∗} to minimize |c − α_{i}|. As a corollary, the root α^{∗} of smallest modulus satisfies

|α^{∗}| ≤ (\frac{|a_{0}|}{|a_{n}|})^{1/n} .

Real Polynomials. The remaining properties assume that A(X) ∈ [X].

R1. The non-real roots of A(X) appear in conjugate pairs.

Proof. A real polynomial A(X) is either a constant or is recursively constructed as A(X) = c + XB(X) for some real c and B(X) ∈ [X]. If X = a + bı is any complex number then A(a + bı) = A_{1}(a, b) + ıA_{2}(a, b) for some real bivariate polynomials A_{1}, A_{2}. It is easy to check recursively that A(a − bı) = A_{1}(a, b) − ıA_{2}(a, b). Hence a − bı is a root if a + bı is a root. Q.E.D.

Corollary 2

1) A(X) can be written as a product of real factors that are linear or quadratic.

2) If n = deg A is odd, then A(X) has at least one real root.

R2. Let X range over the reals. The sign of A(X) as |X| → ∞ is the sign of a_{n}X^{n}. The sign of A(X) as |X| → 0 is the sign of a_{i}X^{i} where i is the smallest index such that a_{i} ≠ 0.

R3. If α < β are two real numbers such that A(α)A(β) < 0 then there exists γ (α < γ < β) such that A(γ) = 0.

R4. Let ϵ > 0 approach 0. Then for any real root α,

\frac{A′(α − ϵ)}{A(α − ϵ)} → −∞, \frac{A′(α + ϵ)}{A(α + ϵ)} → +∞.

In other words, when X is just slightly smaller than α, A′(X) and A(X) have different signs and when X is just slightly greater than α, they have the same signs. See Figure 1.

Figure 1. Illustrating the function A′(X)/A(X).

Proof. From Property C6. we see that of \frac{A′(α−ϵ)}{A(α−ϵ)} approaches \frac{1}{−ϵ} as ϵ approaches 0+. But \frac{1}{−ϵ} → −∞. Similarly for the other case. Q.E.D.

R5. Theorem 3 (Rolle’s theorem) Between two consecutive real roots of A(X) there is an odd number of real roots of A′(X). Proof. Apply the previous property: if α < β are two consecutive real roots then A(X) has constant sign in the interval (α, β). However A′(X) has the same sign as A(X) near α^{+} and has a different sign from A(X) near β^{−}. By continuity of A′(X), it must be zero an odd number of times. Q.E.D.

Corollary 4 Between any two consecutive real roots of A′(X) there is at most one real root of A(X).

Exercise 1.1: (Lucas, 1874) Any convex region K of the complex plane containing all the complex roots of A(X) also contains all the complex roots of A′(X). Note: So this is the complex analogue of Rolle’s theorem for real roots. Much is known about the location of the roots of the derivative of a polynomial; see [7].

Exercise 1.2: (Jensen, 1912) Let A(X) be a real polynomial, so its non-real roots occur in conjugate pairs. A Jensen circle of A(X) is a circle with diameter determined by one of these conjugate pair of roots. Then all the non-real zeroes of A′(X) lies on or inside the union of the Jensen circles of A(X).

Exercise 1.3: (Rouché, 1862) Suppose P (Z), Q(Z) are analytic inside a Jordan curve C, are continuous on C, and satisfies |P (Z)| < |Q(Z)| on C. Then F (Z) = P (Z) + Q(Z) has the same number of zeroes inside C as Q(Z).

§2. Root Bounds  Lecture VI  Page 5

Exercise 1.4: (Champagne) We improve the root bound in Property C9. Suppose the roots α_{1},…, α_{k} (k = 0,…, n − 1) have been “isolated”: this means that for there are discs D_{i} (i = 1,…, k) centered in c_{i} with radii r_{i} > 0 such that each D_{i} contains α_{i} and no other roots and the D_{i}’s are pairwise disjoint. Then for any c chosen outside the union ∪_{i=1}^{k}D_{i} of these discs, there is a root α^{∗} ∈ {α_{k+1},…, α_{n}} such that

|c − α^{∗}| ≤ \frac{|A(c)|}{|a_{n}|} ∏_{i=2}^{n}(|c − c_{i}| − r_{i})^{−1}.

Exercise 1.5: Give a lower bound on |α_{i}| using the same technique as Property C9.

§2. Root Bounds

Let

A(X) = ∑_{i=0}^{n} a_{i}X^{i}

where a_{i} ∈ , |a_{n}| ≠ 0, and let α ∈ denote any root of A(X). This section gives upper and lower bounds on |α|. In Lecture IV, we had shown the Landau bound, |α| ≤ ∥A∥_{2}/a_{n}. Knuth attributes the following to Zassenhaus:

Lemma 5 We have |α| < 2β where

β:= max \{\frac{|a_{n−1}|}{|a_{n}|}, \sqrt{\frac{|a_{n−2}|}{|a_{n}|}}, ^{3} \sqrt{\frac{|a_{n−3}|}{|a_{n}|}},…, ^{n} \sqrt{\frac{|a_{0}|}{|a_{n}|}}\} .

Proof. Since A(α) = 0,

a_{n}α^{n} = −(a_{n−1}α^{n−1} + ⋯ + a_{0}).

Hence

|a_{n}| · |α|^{n} ≤ |a_{n−1}| · |α|^{n−1} + |a_{n−2}| · |α|^{n−2} + ⋯ + |a_{0}|.
1 ≤ \frac{|a_{n−1}|}{|a_{n}|} · \frac{1}{|α|} + \frac{|a_{n−2}|}{|a_{n}|} · \frac{1}{|α|^{2}} + ⋯ + \frac{|a_{0}|}{|a_{n}|} · \frac{1}{|α|^{n}}
≤ \frac{β}{|α|} + \frac{β^{2}}{|α|^{2}} + ⋯ + \frac{β^{n}}{|α|^{n}}
< \frac{β/|α|}{1 − (β/|α|)}.

This yields the bound |α| < 2β Q.E.D.

Assuming |a_{n}| ≥ 1 (as when A(X) ∈ [X]), we get

|α| < 2∥A∥_{∞}.  (3)

Similarly, by applying this result to the polynomial X^{n}A(1/X), assuming |a_{0}| ≥ 1, we get

|α| > \frac{1}{2∥A∥_{∞}}  (4)

Lemma 6 (Cauchy)

\frac{|a_{0}|}{|a_{0}| + max\{|a_{1}|,…, |a_{n}|\}} < |α| < 1 + \frac{max\{|a_{0}|,…, |a_{n−1}|\}}{|a_{n}|}

Proof. We first show the upper bound for |α|. If |α| ≤ 1 then the desired upper bound is immediate. So assume |α| > 1. As in the previous proof

|a_{n}||α|^{n} ≤ |a_{n−1}| · |α|^{n−1} + |a_{n−2}| · |α|^{n−2} + ⋯ + |a_{0}|
≤ max{|a_{0}|,…, |a_{n−1}|} ∑_{i=0}^{n−1} |α|^{i}

≤ max\{|a_{0}|,…, |a_{n−1}|\} · \frac{(|α|^{n} − 1)}{|α| − 1},
|α| − 1 < \frac{max\{|a_{0}|,…, |a_{n−1}|\}}{|a_{n}|}.

This shows the upper bound. The lower bound is obtained by applying the upper bound to the polynomial X^{n}A (\frac{1}{X} ) which has \frac{1}{α} as root. We get

|\frac{1}{α}| < 1 + \frac{max\{|a_{1}|,…, |a_{n}|\}}{|a_{0}|}

from which the lower bound follows. Q.E.D.

Corollary 7

\frac{|a_{0}|}{|a_{0}| + ∥A∥_{∞}} < |α| < 1 + \frac{∥A∥_{∞}}{|a_{n}|} .

In particular, if A(X) is an integer polynomial,

\frac{1}{|a_{0}| + ∥A∥_{∞}} < |α| < 1 + ∥A∥_{∞}.

Lemma 8 (Cauchy)

|α| ≤ max \{\frac{n|a_{n−1}|}{|a_{n}|}, \sqrt{\frac{n|a_{n−2}|}{|a_{n}|}}, ^{3} \sqrt{\frac{n|a_{n−3}|}{|a_{n}|}},…, ^{n} \sqrt{\frac{n|a_{0}|}{|a_{n}|}}\}

Proof. If k is the index such that

|a_{k}| · |α|^{k}

is maximum among all |a_{i}| · |α|^{i} (i = 0,…, n − 1) then the initial inequality of the previous proof yields

\begin{aligned}|a_{n}| · |α|^{n} & ≤ & n|a_{k}| · |α|^{k} \\ |α| & ≤ & ^{n−k} \sqrt{\frac{n·|a_{k}|}{|a_{n}|}}. \end{aligned}

§3. Algebraic Numbers  Lecture VI  Page 7

The lemma follows. Q.E.D.

Many other types of root bounds are known. For example, bounds on the product of the absolute values of the roots of a polynomial [9]. See also [8].

Exercise 2.1: (Mignotte) Consider the following polynomial A(X) = X^{n} − 2(aX − 1)^{2} where n ≥ 3, a ≥ 3 are integers.

i) Show that A(X) is irreducible (using Eisenstein’s criterion).

ii) Show that A(X) has two real roots close to 1/a and their separation is at most 2a^{−(n+2)/2}. iii) Compute bounds for the absolute value of the roots and root separation, using the above formulas.

§3. Algebraic Numbers

Our original interest was finding roots of polynomials in [X]. By extending from to , every integer polynomial has a solution in . But it is not necessary to go so far: every integer polynomial has a root in the algebraic closure \overline{}of . In general, we let \overline{D} denote the algebraic closure of a domain D. If D = \overline{D}, we say D is algebraically closed. Note that \overline{D} is necessarily a field. An algebraically closed domain is one in which the Fundamental Theorem of Algebra holds. We call \overline{}the field of algebraic numbers; elements on \ \overline{D} are called transcendental numbers. By Cantor’s diagonalization argument, it is easy to see that transcendental numbers exist in abundance. Unfortunately, proofs that special numbers such π (circumference of the circle with unit diameter) and e (base of the natural logarithm) are transcendental are invariably non-trivial.

All the computations in our lectures take place exclusively in \overline{}. In fact, in any particular instance of a problem, all computations occur in a subfield of the form

(α) ⊆ \overline{}

for some α ∈ \overline{}. Such subfields are called number fields. The Primitive Element Theorem assures us that any finite algebraic extension field of is a number field. By definition, an algebraic number α is the root of some non-zero integer polynomial P (X); we call P (X) a minimal polynomial of α if the degree of P (X) is minimum among polynomials such that P (α) = 0, P (X) is primitive and its leading coefficient is distinguished among its associates. Note that minimal polynomials must be irreducible. Below we will prove that a minimal polynomial is unique. The degree of α is the degree of a minimal polynomial. By definition, if α = 0, its unique minimal polynomial is 0 with degree −∞.

Exercise 3.1: Prove that if α is an algebraic number then the smallest subring R ⊆ \overline{}containing {α} ∪ is in fact the number field (α). In particular, every non-zero element in R has an inverse. Hint: R is a finite-dimensional vector space with basis 1, α, α^{2},…, α^{n−1} where α has degree n ≥ 0.

Arithmetical Structure of Number fields. An algebraic number α is integral (or, an algebraic integer) if α is the root of a monic integer polynomial. The set of algebraic integers is denoted . As expected, ordinary integers are algebraic integers:

⊆ .

For emphasis, we may call elements of the rational integers (more colloquially, ordinary integers). In the next section, we prove that is a subring of \overline{}. This subring plays a role analogous to that of inside (or, as we say, gives the algebraic numbers its “arithmetical structure”). Denote the set of algebraic integers in a number field (α) by

α:= (α) ∩ ,

which we call number rings. For example, \frac{1}{2}(1 − \sqrt{5}) is an algebraic integer since it is the root of X^{2} − X − 1. Note that if α is an algebraic integer of degree n, then it is the root of some monic polynomial P (X); we next show that P (X) can be assumed to have degree n.

Lemma 9 Let P (X) be the minimal polynomial of α and Q(X) ∈ [X].

a) If Q(α) = 0 then P (X) divides Q(X).

b) The minimal polynomial of an algebraic integer is monic.

c) The minimal polynomial of an algebraic number is unique.

Proof. a) By the Division Property for Polynomials (§II.2), Q(X) = b(X)P (X) + r(X) for some rational polynomials b(X), r(X) ∈ [X] where deg(r) < deg(P). Hence Q(α) = r(α) = 0. Since P is the minimal polynomial, this means r(X) = 0 and we have Q(X) = b(X)P (X). We may choose ξ ∈ such that ξb(X) is a primitive integral polynomial. Thus ξQ(X) = ξb(X)P (X). By Gauss’ lemma (Lecture III.1), ξb(X)P (X) is a primitive polynomial. Thus P (X) divides cont(ξQ(X))prim(ξQ(X)). By the unique factorization of [X] (Lecture II.1), we conclude that P (X) divides prim(Q(X)) which in turn divides Q(X). Hence P (X) divides Q(X).

b) If Q(X) is also primitive, then unique factorization implies ξ = 1. In particular, if Q(X) is monic then P (X) is monic. This proves b).

c) If deg Q = deg P this means P, Q are associates. This proves c). Q.E.D.

Part b) implies that

∩ = .

This justifies the terminology ‘rational integers’.

Lemma 10 Every algebraic number has the form α = β/n where β is an algebraic integer and n ∈ .

Proof. Say α is a root of P (X) ∈ [X]. If P (X) = ∑_{i=0}^{n} a_{i}X^{i} where a = a_{n} then

a^{n−1}P (X) = ∑_{i=0}^{n} a_{i}a^{n−1−i}(aX)^{i}
= Q(aX)

where Q(Y) = ∑_{i=0}^{n}(a_{i}a^{n−1−i})Y^{i} is a monic polynomial. So aα is an algebraic integer since it is a root of Q(Y). Q.E.D.

§4. Resultants  Lecture VI  Page 9

We extend in a routine way the basic arithmetical concepts to number rings. Let us fix a number ring _{α} and simply say “integer” for an element of this ring. For integers a, b, we say a divides b (denoted a|b) if there exists an integer c such that ac = b. A unit u is an integer that divides 1 (and hence every integer in the number ring). Alternatively, u and u^{−1} are both integers iff they are both units. It is easy to see that u is the root of a monic polynomial P (X) whose constant term is unity, 1. Two integers a, b are associates if a = ub for some unit u. An integer is irreducible if it is only divisible by units and its associates.

Just a number field is a vector space, its underlying number ring is a lattice. A basic property about _{α} is that it has a integral basis, ω_{1},…, ω_{n}, meaning that ω_{i} are integers and every integer is a rational integral combination of these ω_{i}’s.

Zimmer [16] contains more information about computational problems in number fields.

Exercise 3.2: Let R ⊆ R′ be rings. An element α ∈ R′ that satisfies a monic polynomial in R[X] is said to be integral over R. The set R^{∗} of elements in R′ that are integral over R′ is called the integral closure of R in R′. Show that the integral closure R^{∗} is a ring that contains R. Note:: _{α} can thus be defined to be the integral closure of in (α).

Exercise 3.3:

a) A root of a polynomial with algebraic coefficients is an algebraic number.

b) A root of a monic polynomial with coefficients that are algebraic integers is an algebraic integer.

Exercise 3.4:

a) Show that \sqrt{−1} = [ı] (the Gaussian integers).

b) Show that \sqrt{−3} = [ω] = \{m + nω : m, n ∈ \} where ω = \frac{1+\sqrt{−3}}{2}. Note:: ω^{2} = ω − 1.

c) Determine quadratic integers. More precisely, determine \sqrt{d} for all square-free d ∈ , d ≠ 1. Hint:: \sqrt{d} = [\sqrt{d}] if d ≡ 2 or d ≡ 3 (mod 4) and \sqrt{d} = [\frac{\sqrt{d}−1}{2}] if d ≡ 1(mod 4).

d) Prove that _{α} is a subring of (α).

Exercise 3.5: (see [1])

a) Show that α ∈ (\sqrt{d}) is integer iff the trace T r(α) = α + \overline{α} and the norm N(α) = α\overline{α} are ordinary integers.

b) Every ideal I ⊆ \sqrt{d} is a module, i.e., has the form [α, β] :=\{mα + nβ : m, n ∈ \}, for some α, β ∈ (\sqrt{d}).

c) A module M = [α, β] is an ideal iff its coefficient ring \{x ∈ (\sqrt{d}) : xM ⊆ M\} is precisely \sqrt{d}.

Exercise 3.6: (H. Mann) Let θ be a root of X^{3} + 4X + 7. Show that 1, θ, θ^{2} is an integral basis for (θ).

§4. Resultants

There are two alternative methods for obtaining basic properties of algebraic numbers, namely the theory of symmetric functions and the theory of resultants (§III.2). Here we take the latter approach. We first develop some properties of the resultant.

The results in this section are valid in any algebraically closed field. We fix such a field D = \overline{D}.

Proposition 11 Let α, β ∈ D, A, B ∈ D[X], deg A = m, deg B = n.

(i) res(α, B) = α^{n}. In particular, we may define res(α, β) = 1.

(ii) res(X − α, B) = B(α).

(iii) res(A, B) = (−1)^{mn}res(B, A)

(iv) res(αA, B) = α^{n}res(A, B)

These are obtained directly by manipulating the definitions: the proof of (ii) is instructive.

Lemma 12 res(A, B) = 0 if and only if deg(GCD(A, B)) > 0.

Proof. Although this is a special case of the Fundamental theorem of subresultants, it is instructive to give a direct proof. Suppose res(A, B) = 0. Consider the matrix equation

U · S = 0  (5)

where S is the (n + m)–square Sylvester matrix of A, B and U is a row (m + n)–vector of unknowns. Thus U has a non-trivial solution since det(S) = res(A, B) = 0. We can view U as the sequence of coefficients of the two polynomials F, G ∈ D[X] of degrees n − 1 and m − 1 respectively. Then (5) becomes the polynomial equation

F A + GB = 0.

But by the unique factorization theorem for D[X], A has a factor of degree at most m − 1 in G and hence a factor of at least 1 in B. This show deg(GCD(A, B)) > 0 as desired. Conversely, if GCD(A, B) has positive degree, then the equation

B̂ A − Â B = 0

holds where B̂ = B/GCD(A, B), Â = A/GCD(A, B). This can be written in the matrix form (5) as before, and implies det(S) = 0. But det(S) is equal to res(A, B). Q.E.D.

Proposition 11(ii) is a special case of the following ([2, p. 177]):

Lemma 13 Let A, B ∈ D[X], α ∈ D, deg B > 0. Then

res((X − α) · A, B) = B(α)res(A, B).

Proof. Let A′ = (X −α)A, m = deg A′, n = deg B and M the Sylvester matrix of A′, B. Writing A(X) = ∑_{i=0}^{m−1} a_{i}X^{i} and B(X) = ∑_{i=0}^{n} b_{i}X^{i}, then M is given by

[ \begin{matrix}a_{m−1} & a_{m−2} − αa_{m−1} & a_{m−3} − αa_{m−2} & ⋯ & a_{0} − αa_{1} & −αa_{0} \\ & a_{m−1} & a_{m−2} − αa_{m−1} & ⋯ & a_{1} − αa_{2} & a_{0} − αa_{1} & −αa_{0} \\ & & ... & & & & & ... \\ & & & a_{m−1} & ⋯ & & & a_{0} − αa_{1} & −αa_{0} \\ b_{n} & b_{n−1} & ⋯ & b_{1} & b_{0} \\ & b_{n} & ⋯ & b_{2} & b_{1} & b_{0} \\ & & ... & & & & ... \\ & & & b_{n} & b_{n−1} & ⋯ & & b_{1} & b_{0} \end{matrix} ]

We now apply the following operations to M, in the indicated order: add α times column 1 to column 2, then add α times column 2 to column 3, etc. In general, we add α times column i to column i + 1, for i = 1,…, m + n − 1. The resulting matrix M′ can be succinctly described by introducing the notation

B/X^{i}, (i ∈ )

to denote the integral part of B(X) divided by X^{i}. For instance, B/X^{n} = b_{n}, B/X^{n−1} = b_{n}X + b_{n−1} and B/X = b_{n}X^{n−1} + b_{n−1}X^{n−2} + ⋯ + b_{2}X + b_{1}. Note that if i ≤ 0, then we are just multiplying B(X) by X^{−i}, as in B/X^{0} = B(X) and B/X^{−2} = X^{2}B(X).

M′ = [ \begin{matrix}a_{m−1} & a_{m−2} & a_{m−3} & ⋯ & a_{0} & 0 \\ & a_{m−1} & a_{m−2} & ⋯ & a_{1} & a_{0} & 0 \\ & & ... & & & & ... \\ & & & a_{m−1} & ⋯ & & & a_{0} & 0 \\ B/X^{n} & B/X^{n−1} & ⋯ & B/X^{1} & B & B/X^{−1} & ⋯ & B/X^{−m+2} & B/X^{−m+1} \\ & B/X^{n} & ⋯ & & B/X^{1} & B & ⋯ & B/X^{−m+3} & B/X^{−m+2} \\ & & ... & & & & ... & & ⋮ \\ & & & B/X^{n} & B/X^{n−1} & ⋯ & B/X^{1} & B & B/X^{−1} \\ & & & & B/X^{n} & B/X^{n−1} & ⋯ & B/X^{1} & B \end{matrix} ]

Note that if we add α times the last row to the last but one row, we transform that row into

(0,…, 0, b_{n}, b_{n−1},…, b_{1}, b_{0}, 0).

In general, we add α^{i} (for each i = 1,…, m − 1) times the last row to the (m + n − i)th row, we obtain the matrix

M′′ = [ \begin{matrix}a_{m−1} & a_{m−2} & a_{m−3} & ⋯ & a_{0} & 0 \\ & a_{m−1} & a_{m−2} & ⋯ & a_{1} & a_{0} & 0 \\ & & ... & & & & ... & ... \\ & & & a_{m−1} & ⋯ & & a_{1} & a_{0} & 0 \\ b_{n} & b_{n−1} & ⋯ & b_{1} & b_{0} & 0 & ⋯ & 0 & 0 \\ & b_{n} & ⋯ & & b_{1} & b_{0} & & 0 & 0 \\ & & ... & & & & ... & & ⋮ \\ & & & b_{n} & b_{n−1} & ⋯ & & b_{0} & 0 \\ & & & & B/X^{n} & B/X^{n−1} & ⋯ & B/X^{1} & B \end{matrix} ]

But the last column of M′′ contains only one non-zero entry B(X) at the bottom right corner, and the co-factor of this entry is the Sylvester matrix of A, B. Hence det M′′ = B(X)res(A, B). Q.E.D.

§4. Resultants  Lecture VI  Page 12

Theorem 14 Let A, B ∈ D[X], a = lead(A), b = lead(B), deg A = m, deg B = n with

α_{1},…, α_{m}, β_{1},…, β_{n} ∈ D

as roots: A(α_{i}) = 0, B(β_{j}) = 0.

(i) res(A, B) = a^{n} ∏_{i=1}^{m} B(α_{i})

(ii) = (−1)^{mn}b^{m} ∏_{j=1}^{n} A(β_{j})

(iii) = a^{n}b^{m} ∏_{i=1}^{m} ∏_{j=1}^{n}(α_{i} − β_{j})

Proof. Writing A = a ∏_{i=1}^{n}(X − α_{i}), we get from the previous lemma,

res(A, B) = a^{n}res (∏_{i=1}^{m}(X − α_{i}), B)
= a^{n}B(α_{1})res (∏_{i=2}^{m}(X − α_{i}), B)
= ⋯
= a^{n}B(α_{1}) ⋯ B(α_{m}).

This shows (i), and (ii) is similar. We deduce (iii) from (i) immediately since

A(β_{j}) = b ∏_{i=1}^{n}(α_{i} − β_{j}).

Q.E.D.

§5. Symmetric Functions  Lecture VI  Page 13

The identity in part (i) of the theorem is also known as Poisson’s definition of the resultant. Exercise 4.1: res(AB, C) = res(A, C) · res(B, C). If A, B are multivariate polynomials, we can take their resultant by viewing them as univariate polynomials in any one of the variables Y. To indicate this, we write res_{Y} (A, B). Lemma 15 Let A, B ∈ D[X] and α, β ∈ D such that A(α) = B(β) = 0 and deg A = m, deg B = n. \begin{matrix}c \\ ◯ \end{matrix} Chee-Keng Yap September 11, 1993 (i) α + β is a root of C(X) = res_{Y} (A(Y), B(X − Y))

(ii) αβ is a root of C(X) = res_{Y} (A(Y), Y^{n}B(\frac{X}{Y}))

Proof.

(i) res_{Y} (A(Y), B(X − Y)) = a^{n} ∏_{i=1}^{m} B(X − α_{i})

= a^{n}b^{m} ∏_{i=1}^{m} ∏_{j=1}^{n}(X − α_{i} − β_{j})

(ii) res_{Y} (A(Y), Y^{n}B(\frac{X}{Y}) = a^{n} ∏_{i=1}^{m}(α_{i}^{n}B(\frac{X}{α_{i}}))

= a^{n} ∏_{i=1}^{m}(bα_{i}^{n} ∏_{j=1}^{n}(\frac{X}{α_{i}} − β_{j}))

= a^{n}b^{m} ∏_{i=1}^{m} ∏_{j=1}^{n}(X − α_{i}β_{j})

Q.E.D.

This proves that the algebraic integers form a ring:

Corollary 16 If α, β are algebraic integers, so are α−β and αβ. Moreover, if α, β have degrees ≤ m and ≤ n respectively then both α + β and αβ have degrees ≤ m + n.

§5. Symmetric Functions

The other approach to the basic properties of algebraic numbers is via the theory of symmetric (polynomial) functions. The advantage of this approach is that it is often the simplest way to show existence results; but it is by nature non-constructive.

Let S_{n} denote the set of all permutations on the set {1, 2,…, n}. This is often called the symmetric group on n-symbols. A polynomial A(X_{1},…, X_{n}) is symmetric in X_{1},…, X_{n} if for all permutations π ∈ S_{n}, we have A(X_{1},…, X_{n}) = A(X_{π(1)},…, X_{π(n)}). For example, the following set of functions are symmetric:

σ_{1}(X_{1},…, X_{n}) = ∑_{i=1}^{n} X_{i},
σ_{2}(X_{1},…, X_{n}) = ∑_{1≤i<j≤n} X_{i}X_{j},

⋮

σ_{k}(X_{1},…, X_{n}) = ∑_{1≤i_{1}<i_{2}<···<i_{k}≤n} X_{i_{1}}X_{i_{2}} ⋯ X_{i_{k}},

⋮
σ_{n}(X_{1},…, X_{n}) = X_{1}X_{2} ⋯ X_{n}.

We call σ_{i} the ith elementary symmetric function (on X_{1},…, X_{n}).

We now introduce two simple classes of symmetric polynomials: for integers e_{1} ≥ e_{2} ≥ ⋯ ≥ e_{n} ≥ 0, define

G_{e_{1},...,e_{n}} := ∑_{π∈S_{n}} X_{π(1)}^{e_{1}} ⋯ X_{π(1)}^{e_{1}},
Γ_{e_{1},...,e_{n}} := σ_{1}^{e_{1}−e_{2}}σ_{2}^{e_{2}−e_{3}} ⋯ σ_{n−1}^{e_{n−1}−e_{n}}σ_{n}^{e_{n}}.

A basic polynomial is one of the form a · G_{e_{1},...,e_{n}} for some a ∈ D; similar a σ-basic polynomial is one of the form a · Γ_{e_{1},...,e_{n}}. Clearly a symmetric polynomial A(X_{1},…, X_{n}) can be written as a sum E of basic polynomials; moreover, we can make the indices (e_{1},…, e_{n}) of the basic polynomials in E distinct in a unique way. Call the resulting expression E the basic decomposition of A(X_{1},…, X_{n}). Similarly we can define the σ-basic decomposition of a symmetric polynomial. It is less clear that every symmetric polynomial has^{2} a σ-basic decomposition. This will be our next result.

For the purposes of our inductive proof below, recall the lexicographic ordering on n-tuples of numbers:

(d_{1},…, d_{n}) ≥_{LEX}(e_{1},…, e_{n})

is defined to mean (d_{1} − e_{1},…, d_{n} − e_{n}) is either all zero or else the first non-zero entry is positive. We extend this to a quasi-order^{3} on the basic polynomials

aG_{d_{1},...,d_{n}} ≥_{LEX} bG_{e_{1},...,d_{n}} iff (d_{1},…, d_{n}) ≥_{LEX}(e_{1},…, e_{n}).

In fact, >_{LEX} is a linear quasi-ordering on basic polynomials, meaning that it is a quasi-ordering

in which every two elements are comparable. Thus linear quasi-orderings satisfies the usual laws of linear orderings, save the symmetry law.

We are ready to prove:

Theorem 17 (σ-Basic Decomposition of symmetric polynomials) Every symmetric polynomial A(X_{1},…, X_{n}) ∈ D[X_{1},…, X_{n}] has a σ-basic decomposition.

Proof. For some e_{1} ≥ ⋯ e_{n} ≥ 0, the basic decomposition of A(X_{1},…, X_{n}) has the form

A(X_{1},…, X_{n}) = a · G_{e_{1},...,e_{n}} + A′, (a ∈ D)

2These definitions were invented mainly for our indirect proof of the Fundamental Theorem, but they may have more general interest.

3A binary relation ≤ on a set S is a quasi-order if for all x, y, z ∈ S, we have x ≤ x and if x ≤ y and y ≤ z then x ≤ z. This this is like a partial-order except that the symmetry law is omitted: x ≤ y and y ≤ x implies x = y.

where A′ has a basic decomposition involving basic polynomials that are lexicographically less than G_{e_{1},...,e_{n}}. Now consider Γ_{e_{1},...,e_{n}}: expanding the σ_{i} terms in its definition into sums of monomials in X_{1},…, X_{n},

Γ_{e_{1},...,e_{n}} = (X_{1} + ⋯ + X_{n})^{e_{1}−e_{2}}(X_{1}X_{2} + ⋯ + X_{n−1}X_{n})^{e_{2}−e_{3}} ⋯ (X_{1}X_{2} ⋯ X_{n})
= {(X_{1})^{e_{1}−e_{2}}(X_{1}X_{2})^{e_{2}−e_{3}} ⋯ (X_{1} ⋯ X_{n})^{e_{n}}}  (6)
+ ⋯ + {(X_{n})^{e_{1}−e_{2}}(X_{n−1}X_{n})^{e_{2}−e_{3}} ⋯ (X_{1} ⋯ X_{n})^{e_{n}}}
= {X_{1}^{e_{1}}X_{2}^{e_{2}} ⋯ X_{n}^{e_{n}}} + ⋯ + {X_{n}^{e_{1}}X_{n−1}^{e_{2}} ⋯ X_{1}^{e_{n}}} .  (7)

The basic decomposition of Γ_{e_{1},...,e_{n}} contains the basic polynomial G_{e_{1},...,e_{n}}: this is clear from the presence of the term X_{1}^{e_{1}}X_{2}^{e_{2}} ⋯ X_{n}^{e_{n}} in equation (6). Thus

Γ_{e_{1},...,e_{n}} = G_{e_{1},...,e_{n}} + G′

for some symmetric polynomial G′. Moreover, the basic decomposition of G′ involves only basic polynomials that are lexicographically less than G_{e_{1},...,e_{n}}: again this is clear since the other terms X_{1}^{d_{1}}X_{2}^{d_{2}} ⋯ X_{n}^{d_{n}} of the expansion in equation (6) are each “lexicographically” no greater than X_{1}^{e_{1}}X_{2}^{e_{2}} ⋯ X_{n}^{e_{n}} in the sense that (d_{1},…, d_{n}) ≤_{LEX}(e_{1},…, e_{n}). This proves that

A(X_{1},…, X_{n}) = a · Γ_{e_{1},...,e_{n}} − a · G′ + A′

where −a · G′ + A′ has a basic decomposition involving basic polynomials that are lexicographically less than G_{e_{1},...,e_{n}}. By induction of the lexicographic ordering, −a · G′ + A′ has a σ-basic decomposition. The theorem follows. Q.E.D.

Since a σ-basic polynomial is a polynomial in the elementary symmetric functions, we conclude:

Corollary 18 (Fundamental Theorem on Symmetric Functions) Every symmetric polynomial A(X_{1},…, X_{n}) with coefficients from a domain D can be expressed as a polynomial in D[σ_{1},…, σ_{n}] where σ_{i} is the ith elementary symmetric function on X_{1},…, X_{n}.

For example, A(X, Y) = X^{2} + Y^{2} can be expressed as A(X, Y) = (X + Y)^{2} − 2XY = σ_{1}^{2} − 2σ_{2}.

Let

α^{(1)}, α^{(2)},…, α^{(n)}

be all the roots (not necessarily distinct) of a polynomial

A(X) = ∑_{i=0}^{n} a_{i}X^{i}, (a_{i} ∈ D).

In case A(X) is irreducible, we call the α^{(i)} conjugates of each other. Then we see that A(X) can also be written as

A(X) = a_{0} ∏_{i=1}^{n}(X − α^{(i)}).

Equating coefficients in the two expressions for A(X),

(−1)^{i}a_{n−i} = a_{0} · σ_{i}(α^{(1)},…, α^{(n)})

for all i = 1,…, n. That is, the coefficient of X^{n−i} in A(X) is similar (Lecture III, §1) to the ith elementary symmetric function on the roots of A(X). We conclude from the Fundamental Theorem:

§6. Discriminant  Lecture VI  Page 16

Lemma 19 If B(X_{1},…, X_{n}) is any symmetric polynomial and α^{(1)}, α^{(2)},…, α^{(n)} are all the roots of a polynomial A(X) = ∑_{i=0} a_{i}X^{i}, then B(α^{(1)},…, α^{(n)}) is a polynomial in the coefficients a_{0},…, a_{n}.

In particular, if A(X), B(X) have coefficients from D then B(α^{(1)},…, α^{(n)}) belongs to D.

We give another application of the Fundamental Theorem:

Theorem 20 If α is algebraic over E, and E is an algebraic extension of a domain D, then α is algebraic over D.

Proof. Let α be the root of the polynomial B(X) = ∑_{i=0}^{n} β_{i}X^{i} where β_{i} ∈ E. Let

β_{i}^{(j_{i})}, j_{i} = 1,…, d_{i}

be the set of conjugates of β_{i} over D. For all j_{0}, j_{1},…, j_{n}, let

B_{j_{0},...,j_{n}}(X) := ∑_{i=0}^{n} β_{i}^{(j_{i})}X^{i}.

Consider the polynomial

A(X) := ∏_{j_{0},j_{1},...,j_{n}} B_{j_{0},...,j_{n}}(X).

Note that B(X)|A(X) and hence α is a root of A(X). The algorithm follows if we show that A(X) ∈ D[X]. But each coefficient of A(X) is a symmetric function in β_{i}^{(1)},…, β_{i}^{(d_{i})}, for each i = 0,…, n. By the preceding lemma, the coefficients of A(X) are polynomials (over D) in the coefficients of the minimial polynomials of the β_{i} (over D). The result follows since the coefficients of minimal polynomials of β_{i} are elements of D. Q.E.D.

Exercise 5.1: Let s_{k}(X_{1},…, X_{n}) = ∑_{i=1}^{n} X_{i}^{k} for k = 1,…, n. Express s_{k} in terms of σ_{1},…, σ_{k}. Conversely, express σ_{k} in terms of s_{1},…, s_{k}.

§6. Discriminant

For any non-constant polynomial A(X) ∈ [X], we define its minimum root separation to be

sep(A) := min_{1≤i<j≤k} |α_{i} − α_{j}|

where the distinct roots of A(X) are α_{1},…, α_{k} ∈ . Clearly k ≥ 1 and if k = 1, then sep(A) = ∞ by definition. In order to get a bound on sep(A), we introduce a classical tool in the study of polynomials.

Definition 1 Let D be any domain. The discriminant of A ∈ D[X] is

disc(A) = a^{2m−2} ∏_{1≤i<j≤m}(α_{i} − α_{j})^{2}

where α_{1},…, α_{m} ∈ \overline{D} are the roots (not necessarily distinct) of A, deg(A) = m ≥ 2, a = lead(A).

If A(X) = aX^{2} + bx + c, then its discriminant is the familar disc(A) = b^{2} − 4ac. It is clear from this definition that disc(A) = 0 if A has repeated roots. To see that disc(A) ∈ D, we only have to note that it is a symmetric function of all the roots of A(X). But this gives no indication about how to compute it. The following result gives the remedy:

Lemma 21 a · disc(A) = (−1)^{\binom{m}{2}}res(A, A′).

Proof.

res(A, A′) = a^{m−1} ∏_{i=1}^{m} A′(α_{i}) (by a previous theorem)

= a^{m−1} ∏_{i=1}^{m} (a ∏_{j=1}^{m}(X − α_{j}))′|_{X=α_{i}}

= a^{2m−1} ∏_{i=1}^{m} (∑_{k=1}^{m} ∏_{j≠k^{j=1}}^{m}(X − α_{j}))|_{X=α_{i}}

= a^{2m−1} ∏_{i=1}^{m} (∏_{j≠i^{j=1}}^{m}(α_{i} − α_{j}))

= a^{2m−1} ∏_{1≤i<j≤m}(−1)(α_{i} − α_{j})^{2}

= (−1)^{\binom{m}{2}}a · disc(A).

Q.E.D.

The following matrix

V_{m} = V_{m}(α_{1}, α_{2},…, α_{m}) := ( \begin{matrix}1 & 1 & ⋯ & 1 \\ α_{1} & α_{2} & ⋯ & α_{m} \\ α_{1}^{2} & α_{2}^{2} & ⋯ & α_{m}^{2} \\ ⋮ & ⋮ & & ⋮ \\ α_{1}^{m−1} & α_{2}^{m−1} & ⋯ & α_{m}^{m−1} \end{matrix} )

is called a Vandermonde matrix, and its determinant is a Vandermonde determinant.

Lemma 22

∏_{1≤i<j≤m}(α_{i} − α_{j}) = (−1)^{\binom{m}{2}} det V_{m}(α_{1}, α_{2},…, α_{m}).

Proof. One can evaluate det V_{m} recursively as follows. View det V_{m} as a polynomial P_{m}(α_{m}) in the variable α_{m}. The degree of α_{m} in P_{m} is m − 1, as seen by expanding the determinant by the last column. If we replace α_{m} in P_{m}(α_{m}) by α_{i} (i = 1,…, m − 1), we get the value P_{m}(α_{i}) = 0. Hence α_{i} is a root and by basic properties of polynomials (§2),

P_{m}(α_{m}) = U · (α_{m} − α_{1})(α_{m} − α_{2}) ⋯ (α_{m} − α_{m−1})

where U is the coefficient of α_{m}^{m−1} in P_{m}. But U is another Vandermond determinant P_{m−1}:

P_{m−1} = det ( \begin{matrix}1 & 1 & ⋯ & 1 \\ α_{1} & α_{2} & ⋯ & α_{m−1} \\ α_{1}^{2} & α_{2}^{2} & ⋯ & α_{m−1}^{2} \\ ⋮ & ⋮ & & ⋮ \\ α_{1}^{m−2} & α_{2}^{m−2} & ⋯ & α_{m−1}^{m−2} \end{matrix} ) = det V_{m−1}(α_{1},…, α_{m−1}).

Inductively, let

(−1)^{\binom{m−1}{2}}P_{m−1} = ∏_{1≤i<j≤m−1}(α_{i} − α_{j}).

Hence

P_{m} = U · ∏_{i=1}^{m−1}(α_{m} − α_{i})

= (−1)^{\binom{m−1}{2}}P_{m−1} · (−1)^{m−1} ∏_{i=1}^{m−1}(α_{i} − α_{m})

= (−1)^{\binom{m}{2}} ∏_{1≤i<j≤m−1}(α_{i} − α_{j}) · ∏_{i=1}^{m−1}(α_{i} − α_{m})
= (−1)^{\binom{m}{2}} ∏_{1≤i<j≤m}(α_{i} − α_{j}).

Q.E.D.

Thus \sqrt{disc(A)} for monic polynomial A is equal to a Vandermonde determinant, up to sign.

Exercise 6.1: disc(AB) = disc(A)disc(B)(res(A, B))^{2}.

Exercise 6.2: Show that

disc(A) = det ( s_{0}  s_{1} ⋯ s_{m−1} ; s_{1}  s_{2} ⋯ s_{m} ; ⋮ ; s_{m−1} s_{m} ⋯ s_{2m−2} )

where s_{i} = ∑_{j=1}^{m} α_{j}^{i} (i = 0,…, 2m − 2).

Exercise 6.3*: (Siegel [14, p. 27]) Let P (X) be an irreducible monic polynomial with integral coefficients. If all the zeros of P are real then

disc(P) ≥ (\frac{m^{m}}{m!} )^{2} , m = deg P.

§7. Root Separation  Lecture VI  Page 19

§7. Root Separation

We are ready to prove a root separation bound. But first we quote Hadamard’s bound whose proof is delayed to a later chapter.

Lemma 23 (Hadamard’s determinantal inequality) Let M be an n-square matrix with entries in . Then | det(M)| ≤ ∏_{i=1}^{n} ∥R_{i}∥_{2} where R_{i} is the i^{th} row of M.

Recall (Lecture IV.4) that the measure M(A) of a complex polynomial A is equal to the product lead(A) ∏_{i=1} |α_{i}| where i range over all complex roots of A that has absolute value |α_{i}| ≥ 1. (If i ranges over an empty set, we define M(A) = lead(A).

Theorem 24 (Davenport-Mahler) Assume A(X) ∈ [X] has roots α_{1},… α_{m} ∈ . For any k + 1 of these roots, say α_{1},…, α_{k+1} (k = 1,…, m − 1), we reorder them so that

|α_{1}| ≥ |α_{2}| ≥ ⋯ ≥ |α_{k+1}|.

Then

∏_{i=1}^{k} |α_{i} − α_{i+1}| > \sqrt{disc(A)} · M(A)^{−m+1} · m^{−m/2} · (\frac{\sqrt{3}}{m})^{k} .

Proof. First let us assume A is monic. Let us give an upper bound on \sqrt{disc(A)} which, by the previous lemma, (is up to sign) given by the Vandermonde determinant

det V_{m} = det ( \begin{matrix}1 & 1 & ⋯ & 1 \\ α_{1} & α_{2} & ⋯ & α_{m} \\ α_{1}^{2} & α_{2}^{2} & ⋯ & α_{m}^{2} \\ ⋮ & ⋮ & & ⋮ \\ α_{1}^{m−1} & α_{2}^{m−1} & ⋯ & α_{m}^{m−1} \end{matrix} ) .

We modify Vandermonde’s matrix by subtracting the 2nd from the 1st column, the 3rd column from the 2nd, and so on, and finally the (k + 1)st column from the kth column. Hence the first k column becomes (for i = 1,…, k):

(α_{i} − α_{i+1}) ( 0 ; 1 ; β_{i}^{(2)} ; β_{i}^{(3)} ; ⋮ ; β_{i}^{(m−1)} )

where β_{i}^{(j)} = \frac{α_{i}^{j}−α_{i+1}^{j}}{α_{i}−α_{i+1}} = ∑_{ℓ=0}^{j−1} α_{i}^{ℓ}α_{i+1}^{j−1−ℓ}. Hence

det V_{m} = ∏_{i=1}^{k}(α_{i} − α_{i+1}) · det ( \begin{matrix}0 & 0 & ⋯ & 0 & 1 & ⋯ & 1 \\ 1 & 1 & & 1 & α_{k+1} & & α_{m} \\ β_{1}^{(2)} & β_{2}^{(2)} & ⋯ & β_{k}^{(2)} & α_{k+1}^{2} & & α_{m}^{2} \\ ⋮ & ⋮ & & ⋮ & ⋮ & & ⋮ \\ β_{1}^{(m−1)} & β_{2}^{(m−1)} & ⋯ & β_{k}^{(m−1)} & α_{k+1}^{m−1} & & α_{m}^{m−1} \end{matrix} ) (8)

Let us upper bound the 2-norm of each column in this last matrix. There are two cases to consider:

Case 1: The column is (0, 1, β_{i}^{(2)},…, β_{i}^{(m−1)})^{T}. Each β_{i}^{(j)} satisfies

|β_{i}^{(j)}|^{2} ≤ (∑_{ℓ=0}^{j−1} |α_{i}|^{ℓ}|α_{i+1}|^{j−1−ℓ})^{2}
≤ (j|α_{i}|^{j−1})^{2}
≤ j^{2}(max{1, |α_{i}|})^{2(m−1)}

So the 2-norm of the column is less than

( ∑_{j=1}^{m−1} |β_{i}^{(j)}|^{2})^{\frac{1}{2}} < \sqrt{\frac{m^{3}}{3}} · (max\{1, |α_{i}|\})^{m−1},

using the fact that ∑_{j=1}^{m} j^{2} = \frac{m^{3}}{3} + \frac{m^{2}}{2} + \frac{m}{6}.

Case 2: The column is (1, α_{i}, α_{i}^{2},…, α_{i}^{m−1})^{T}. The 2-norm is at most

( ∑_{ℓ=0}^{m−1} |α_{i}|^{2ℓ})^{1/2} < \sqrt{m} · (max\{1, |α_{i}|\})^{m−1}

The product of all the m-columns, is therefore less than

(\sqrt{\frac{m^{3}}{3}} )^{k} (\sqrt{m})^{m−k} ∏_{i=1}^{m} max\{1, |α_{i}|\}^{m−1} = (\frac{m}{\sqrt{3}})^{k} · m^{m/2} · (M(A))^{m−1}.

where M(A) is the measure of A.

By Hadamard’s inequality, this product is an upper bound on the determinant in (8). Hence

\sqrt{disc(A)} = | det V_{m}| < (∏_{i=1}^{k} |α_{i} − α_{i+1}|) · (\frac{m}{\sqrt{3}})^{k} m^{m/2}(M(A))^{m−1}.

This proves the theorem for monic A. It remains to remove the assumption that A is monic. Suppose lead(A) = a ≠ 1. Then clearly we have proved that

∏_{i=1}^{k} |α_{i} − α_{i+1}| > \sqrt{disc(A/a)} · M(A/a)^{−m+1} · m^{−m/2} · (\frac{\sqrt{3}}{m})^{k} .

But \sqrt{disc(A/a)} = ^{\frac{\sqrt{disc(A)}}{a^{m−1}}} and M(A/a)^{−m+1} = a^{m−1}M(A)^{−m+1}. Hence the extraneous factors involving a cancel out, as desired.

Q.E.D.

The preceding proof for k = 1 is from Mahler (1964), generalized here to k > 1 by Davenport (1985). Recall that M(A) ≤ ∥A∥_{2} (Lecture IV.4).

Corollary 25

(i) sep(A) > \sqrt{3 disc(A)} · ∥A∥_{2}^{−m+1} · m^{−(m+2)/2}. (ii) |disc(A)| ≤ m^{m+2}(M(A))^{2m−2} ≤ m^{m+2}∥A∥_{2}^{2m−2}.

Proof. Part (i) comes from the theorem with k = 1. Part (ii) is a corollary of the proof of the main theorem. Q.E.D.

For integer polynomials, let us express part (i) in more memorizable, if cruder, terms. Recall that the “bit-size” of an integer polynomial is simply the sum of the bit-sizes of its coefficients in the dense representation.

Lemma 26 If A ∈ [X] is square-free and has bit-size s ≥ 4 then sep(A) > 2^{−2s^{2}}

Proof. Note that \sqrt{disc(A)} ≥ 1, ∥A∥_{2} ≤ 2^{s}, and m ≤ s. Q.E.D.

In other words, with O(s^{2}) bits of accuracy we can separate the roots of A.

It is often useful to bound the root α of a polynomial A(X) away from 0:

Lemma 27 If A ∈ [X] has a root α and if A(0) ≠ 0 then |alpha| > \sqrt{3 disc(A)} · ∥A∥_{2}^{−m} · (m + 1)^{−(m+3)/2}.

§8. Generalized Hadamard Bound  Lecture VI  Page 22

Proof. This is an application of corollary (i) to the polynomial B(X) = X · A(X). We only have to note that if α_{j}’s are the roots of A then

\sqrt{disc(B)} = \sqrt{disc(A)}lead(A) ∏_{j} |α_{j}| ≥ \sqrt{disc(A)},

since lead(A) ∏_{j} α_{j} = res(X, A(X)) (cf. Exercise 6.1). Q.E.D.

Remark: The above bound is useless when A has multiple root, since the discriminant is zero. Of course, we can still obtain a bound indirectly, by computing the root separation of A/GCD(A, A′). A direct argument of Rump [12] (as corrected by Schwartz [13]) shows that sep(A) > (2 · d^{(d/2)+2}(|A|_{∞} + 1)^{d})^{−1}.

Exercise 7.1: [Mahler] Show that the root separation bound is essentially tight up to some constant (which is not \sqrt{3} as in the result here). Consider the polynomial X^{m} − 1. Show that the minimum root separation here is

\frac{m^{m/2}}{2 sin(π/m)} ∼ \frac{m^{(m+2)/2}}{2π} .

§8. A Generalized Hadamard Bound

We are given A(X), B(X) ∈ [X] where A(X)B(X) has only simple roots, and n = max{deg A, deg B}. We want a lower bound on |α − β| where α, β are roots of (respectively) A(X), B(X). Using the fact that |α − β| ≥ sep(AB), we derive a bound from our previous results. If s is the sum of the bit sizes of A(X) and B(X) then

∥A∥_{2} · ∥B∥_{2} ≤ 2^{s}

and 2n ≤ s.

|α − β| ≥ sep(A(X)B(X))
≥ \sqrt{disc(A(X)B(X))} · ∥AB∥_{2}^{−(2n−1)}(2n)^{−(2n+2)/2}
≥ (∥A∥_{2}∥B∥_{2})^{−s}s^{−s}
≥ 2^{−s^{2}}s^{−s}
≥ 2^{−2s^{2}}.

This section gives another proof, based on a generalization of the Hadamard bound [4]. Let W = (w_{ij}), w_{ij} ∈ , be an n-square matrix. Define

H(W) :=(∏_{i=1}^{n} ∑_{j=1}^{n} |w_{ij}|^{2})^{\frac{1}{2}} .

Then the Hadamard’s determinantal bound (Lemma 23) gives | det(W)| ≤ H(W). The following generalizes this.

Theorem 28 (Goldstein-Graham) Let M(X) = (M_{ij}(X)) be an n-square matrix whose entries M_{ij}(X) are polynomials in [X]. Let W = (w_{ij}) be the matrix where w_{ij} = ∥M_{ij}(X)∥_{1}. Then det(M(X)) ∈ [X] satisfies

∥ det(M(X))∥_{2} ≤ H(W).

Proof. For any real t,

|M_{ij}(e^{ı t})| ≤ w_{ij}

where ı = \sqrt{−1}. Hence Hadamard’s inequality implies

| det(M(e^{ı t}))|^{2} ≤ ∏_{k=1}^{n} ∑_{ℓ=1}^{n} |M_{kℓ}(e^{ı t})|^{2}

≤ ∏_{k=1}^{n} ∑_{ℓ=1}^{n} w_{kℓ}^{2}
= (H(W))^{2}.

But, if the coefficients of the polynomial det(M(X)) are {a_{0}, a_{1},…}, then

\frac{1}{2π} ∫_{0}^{2π} | det(M(e^{ı t}))|^{2}dt = \frac{1}{2π} ∫_{0}^{2π}((∑_{k} a_{k}e^{ı kt})(∑_{ℓ} \overline{a}_{ℓ}\overline{e}^{ı ℓt}))dt
= ∑_{k} |a_{k}|^{2}

since \frac{1}{2π} ∫_{0}^{2π} e^{−ı kt}dt = δ_{k,0} (Kronecker’s delta). Hence

∥ det(M(X))∥_{2} = ∑_{k} |a_{k}|^{2}

= \frac{1}{2π} ∫_{0}^{2π} | det(M(e^{ı t}))|^{2}dt
≤ \frac{1}{2π} ∫_{0}^{2π}(H(W))^{2}dt
= (H(W))^{2}.

Q.E.D.

Let us apply the generalized Hadamard’s bound to

C(X) = res_{Y} (A(Y), B(X + Y)).

Clearly |α − β| is at least the minimum absolute value of a root of C(X), since α − β is a root of C(X). Let

B(X) = ∑_{i=0}^{n} b_{i}X^{i}

where n = max{deg(A), deg(B)}. So,

B(X + Y) = ∑_{i=0}^{n} b_{i}(X + Y)^{i}

= ∑_{i=0}^{n} b_{i} ∑_{j=0}^{i} \binom{i}{j}X^{i−j}Y^{j}

= ∑_{j=0}^{n} Y^{j} (∑_{i=j}^{n} b_{i}\binom{i}{j}X^{i−j}) .

Let S(X) be the Sylvester matrix corresponding to res_{Y} (A(Y), B(X + Y)). Consider a row of S(X) corresponding to B(X + Y). Each non-zero entry is a polynomial of the form

B_{j}(X) := ∑_{i=j}^{n} b_{i}\binom{i}{j}X^{i−j}.

The 1-norm is bounded as ∥B_{j}(X)∥_{1} ≤ ∥B∥_{∞} ∑_{i=j}^{n} \binom{i}{j}. Thus the 2-norm of such a row is at most

∥B∥_{∞} (∑_{j=0}^{n} (∑_{i=j}^{n} \binom{i}{j})^{2})^{\frac{1}{2}} ≤ ∥B∥_{∞} ∑_{j=0}^{n} ∑_{i=j}^{n} \binom{i}{j}

= ∥B∥_{∞} ∑_{i=0}^{n} ∑_{j=0}^{i} \binom{i}{j}

= ∥B∥_{∞} ∑_{i=0}^{n} 2^{i}
= ∥B∥_{∞}2^{n+1}.

Since there are at most n such rows, the product of all these 2-norms is

∥B∥_{∞}^{n}2^{n(n+1)}.

The remaining rows of S(X) has as non-zero entries the coefficients of A(X). Their 2-norms are clearly ∥A∥_{2}. Again, there are ≤ n such rows, so their product is ∥A∥_{2}^{n}. The generalized Hadamard bound yield

∥C(X)∥_{2} ≤ ∥B∥_{∞}^{n}2^{n(n+1)} · ∥A∥_{2}^{n}
≤ (2^{n+1}∥A∥_{2} · ∥B∥_{2})^{n}.

By Cauchy’s lower bound on roots (§3, Lemma 6), we get

|α − β| ≥ \frac{1}{2(2^{n+1}∥A∥_{2} · ∥B∥_{2})^{n}} .

If s is the sum of the bit sizes of A(X) and B(X) then

|α − β| > \frac{1}{2(2^{s} · 2^{s})^{s−1}}
≥ 2^{−2s^{2}}.

It follows that if α ≠ β then they are separated by a binary rational number with at most 2s^{2} places of binary precision.

§10. Isolating Interval  Lecture VI  Page 25

§9. Isolating Intervals

The existence of a root separation bound is fundamental in justifying the following representation of real algebraic numbers.

Definition 2

i) Let I be an interval, I = [a, b], (a, b ∈ ). For any polynomial A(X) ∈ [X], we call I an isolating interval of A if I contains exactly one distinct real root α of A. The width of I is b − a. ii) Let α ∈ \overline{}∩ be a real algebraic number. An isolating interval representation of α is a pair

(A(X), I)

where A ∈ [X] is square-free and primitive, A(α) = 0, and I is an isolating interval of A that contains α and has rational endpoints: I = [a, b], a < α < b, (a, b ∈ ). As a special case, we allow a = b = α. We write

α ≅ (A, I)

to denote this relationship.

It is clear that this representation is highly redundant, both in the choice of A(X) and of I. We do not insist that A(X) be the minimal polynomial of α because this is too expensive computationally. We also note that the rational endpoints of I are usually binary rationals i.e., they have finite binary expansions. Note that once A is fixed, then minimum root separation tells us I need not have more than O(s^{2}) bits to isolate any root of interest (s=bit-size A). The interval I serves to distinguish the root of A(X) from the others. This is not the main function of I, however – otherwise we could as well represent α as (A(X), i) if α is the i^{th} smallest real root of A(X). The advantage of isolating interval is that it facilitates numerical computations.

(A) We can compute α ≅ (A, I) to any desired degree of accuracy using repeated bisections of I: if I = [a, b] is not degenerate then clearly A(a) · B(b) < 0. We begin by evaluating A(\frac{a+b}{2}). If A(\frac{a+b}{2}) = 0 then we have found α exactly. Otherwise, either [a, \frac{a+b}{2}] or [\frac{a+b}{2} b] contains α. It is easy to determine exactly which half-interval contains α: a < α < \frac{a+b}{2} iff A(a)A((a + b)/2) < 0. Note that if a, b are binary rationals, then \frac{a+b}{2} is still a binary rational.

(B) We can compare two real algebraic numbers α, β to see, which is bigger: if α ≅ (A, I), β ≅ (B, J) then this comparison is immediate if I ∩ J = 0\. Otherwise, we could repeatedly refine I and J using bisections until they are disjoint. But what if α = β? In other words, when do we stop bisecting in case α = β? If s is a bound on the sum of the bit sizes of A and B, then the previous section says we can stop when I and J have widths ≤ 4^{−s^{2}}, concluding α = β iff I ∩ J ≠ ∅.

The above methods are both simple to implement. In the next section, we consider a more efficient alternative to (A) using Newton’s iteration. Later we show how a generalization of Sturm sequence can be used more effectively than (B).

The use of isolating interval representation motivates the root isolation problem: given a real polynomial P (X), determine an isolating interval for each real root of P (X). This problem is easily solved in principle: we know a lower L and an upper U bound on all real roots of P (X).

§10. Newton’s Method  Lecture VI  Page 26

We partition the interval [L, B] into subintervals of width at most 4^{−s^{2}} where s is the usual “composite” size bound on P (X). We evaluate P (X) at the end points of these subintervals. We conclude that a subinterval is an isolating interval of P (X) iff P (X) does not vanish at both end points but have opposite signs. Of course, this procedure is grossly inefficient. The next lecture introduces Sturm sequences to perform this efficiently.

§10. On Newton’s Method

Newton’s method gives a faster approximation for roots the bisection method when one has a good initial approximation. In this section, assume f(X) is a real function whose zeroes we want to approximate.

We view Newton’s method as giving a suitable transformation of f(X) into another function F (X), such that a fixed point X^{∗} of F (X) is a root of f(X):

X^{∗} = F (X^{∗}) ⇒ f(X^{∗}) = 0.

The rest of the method amounts to finding a fixed point of F (X) via an iterative process: begin with an initial value X_{0} ∈ and generate the sequence X_{1}, X_{2},… where

X_{i+1} = F (X_{i}).  (9)

We say the iternative process converges from X_{0} if the sequence of X_{i}’s converges to some value X^{∗}. Clearly, F (X_{i}) also converges to X^{∗}. Assuming that F (X) is continuous at X^{∗}, we may conclude that F (X^{∗}) = X^{∗}. Thus X^{∗} is a root of f(X).

As a simple example of a transformation of f(X), we can let F (X) = X −f(X). More generally, let

F (X) = X − g(X) · f(X)  (10)

for a suitable function g(X). We study the standard Newton method where g(X) = \frac{1}{f′(X)}, so

F (X) = X − \frac{f(X)}{f′(X)}.

When does the iterative process converge? Let us assume that F is n-fold differentiable and the process converges to X^{∗} starting at X_{0}. Using Taylor’s expansion of F at X^{∗} with error term,

F (X) = F (X^{∗}) + (X − X^{∗}) · F′(X^{∗}) + (X − X^{∗})^{2} · \frac{F′′(X^{∗})}{2!} + ⋯ +  (11)

(X − X^{∗})^{n−1} · \frac{F^{(n−1)}(X^{∗})}{(n − 1)!} + (X − X^{∗})^{n} · \frac{F^{(n)}(ξ)}{n!},

where F^{(i)} denotes the i-fold differentiation of F (X) and ξ denotes some value between X and X^{∗}:

ξ = X + θ(X^{∗} − X), 0 ≤ θ ≤ 1.

We say F (X) gives an n^{th} order iteration at X^{∗} if F^{(i)}(X^{∗}) = 0 for i = 1,…, n − 1. We do not rule out the possibility that F^{(i)}(X^{∗}) = 0 for i ≥ n. In this case, since F (X^{∗}) = X^{∗}, we have

F (X) − X^{∗} = (X − X^{∗})^{n} · \frac{F^{(n)}(ξ)}{n!}.  (12)

§11. Guaranteed Convergence  Lecture VI  Page 27

Let us suppose that for some real k_{0} > 0,

|\frac{F^{(n)}(ξ)}{n!}| < k_{0}  (13)

for all ξ where |X^{∗} − ξ| ≤ 1/k_{0}. Then equation (12) yields:

|X_{1} − X^{∗}| < k_{0}|X_{0} − X^{∗}|^{n}
|X_{2} − X^{∗}| < k_{0}|X_{1} − X^{∗}|^{n} < k_{0}^{n+1}|X_{0} − X^{∗}|^{n^{2}}
⋮
|X_{i} − X^{∗}| < \{ \begin{matrix}k_{0}^{(\frac{n^{i}−1}{n−1})}|X_{0} − X^{∗}|^{n^{i}} & if & n > 1, \\ k_{0}^{i}|X_{0} − X^{∗}| & if & n = 1. \end{matrix}

Let us assume n > 1. So

|X_{i} − X^{∗}| < (k0^{\frac{1}{n−1}} |X_{0} − X^{∗}|)^{n^{i}} · k0^{\frac{1}{1−n}}

and a sufficient condition for convergence is

k0^{\frac{1}{n−1}} |X_{0} − X^{∗}| < 1.  (14)

Note: Newton’s method works in very general settings. In particular, it applies when f(X) is a complex function. But if f(X) is a real polynomial and X^{∗} is a complex root, it is clear that the initial value X_{0} must be complex if convergence to X^{∗} is to happen. More generally, Newton’s method can be used to solve a system of equations, i.e., f(X) is a vector-valued multivariate function, f : ^{n} → ^{m}, X = (X_{1},…, X_{n}).

Exercise 10.1: Apply Newton’s method to finding the square-root of an integer n. Illustrate it for n = 9, 10.

§11. Guaranteed Convergence of Newton Iteration

Most books on Numerical Analysis inform us that when X_{0} is sufficiently close to a root X^{∗}, Newton iteration gives a second order rate of convergence. What we seek now is an explicit a priori upper bound on the distance from X_{0} to a root X^{∗} which guarantees the said rate of convergence.^{4}

We carry out the estimates in the case of F (X) = X − \frac{f(X)}{f′(X)} where f(X) is a square-free polynomial of degree m with integer coefficients. Further assume X_{0} satisfies |X_{0} − X^{∗}| ≤ 1. It is easily checked that

F′(X) = \frac{f_{0}f_{2}}{f_{1}^{2}}  (15)
F′′(X) = \frac{f_{0}f_{1}f_{3} + f_{1}^{2}f_{2} − 2f_{0}f_{2}^{2}}{f_{1}^{3}}  (16)

4Recent work of Smale gives implicit conditions for convergence.

where we write f_{i} for f^{(i)}(X). For any root X^{∗}, equation (15) shows that F′(X^{∗}) = 0 since X^{∗} is a simple root. Hence Newton’s method gives rise to a second order iteration. Our goal is to find a real bound δ_{0} > 0 such that for any real number ξ satisfying |ξ − X^{∗}| ≤ δ_{0},

|\frac{F′′(ξ)}{2!}δ_{0}| < 1.  (17)

Note that this implies (13) and (14) with the choice k_{0} = \frac{1}{δ_{0}} .

Lemma 29 If |ξ − X^{∗}| ≤ 1 and f(X^{∗}) = 0 then for all i = 0, 1,…, m,

|f^{(i)}(ξ)| ≤ \frac{m!}{(m − i)!}(1 + M)^{1+m},

where M = 1 + ∥f∥_{∞}.

Proof. By Cauchy’s bound (§3, Lemma 6), |X^{∗}| < M. Then

|f^{(i)}(ξ)| ≤ \frac{m!}{(m − i)!}∥f∥_{∞} ∑_{j=0}^{m−i} |ξ|^{j}

≤ \frac{m!}{(m − i)!}∥f∥_{∞} ∑_{j=0}^{m}(1 + M)^{j}

< \frac{m!}{(m − i)!}(1 + M)^{1+m}.

Q.E.D.

Lemma 30 Let f(X) ∈ [X] be square-free, and X^{∗} a root of f(X). If m = deg f then

|f′(X^{∗})| ≥ \frac{1}{m^{m}∥f∥_{∞}^{m−1}} .

Proof. Let g(X) = \frac{f(X)}{X−X^{∗}}. Then we see that f′(X^{∗}) = g(X^{∗}) and from the definition of discriminant,

disc(f) = disc(g) · f′(X^{∗})^{2} · a^{2} (a = lead(f)).

By Corollary 25(b) of Mahler (§6) we see that

disc(g) ≤ (m − 1)^{m+1}M(g)^{2m−4}

where M(g) is the measure of g. Also M(g) ≤ M(f) ≤ ∥f∥_{2}. This implies

a^{2} · disc(g) ≤ (m − 1)^{m+1}∥f∥_{2}^{2m−2}  (since |a| ≤ ∥f∥_{2})
< m^{m+1} (m^{\frac{1}{2}} ∥f∥_{∞})^{2m−2}
= m^{2m}∥f∥_{∞}^{2m−2}.

Hence |f′(X^{∗})| ≥ \sqrt{disc(f)}m^{−m}∥f∥_{∞}^{−m+1} and the lemma follows. Q.E.D.

Let us now pick

δ_{0} := \frac{1}{16m^{3m+9}(1 + M)^{6m}} .

We first derive a lower bound on

|f(ξ)|, where |X^{∗} − ξ| ≤ δ_{0}.

We have

f′(ξ) = f′(X^{∗}) + (X^{∗} − ξ)f′′(η)

for some η between X^{∗} and ξ, so |X^{∗} − η| ≤ δ_{0}. Using the preceding two lemmas,

|f′(ξ)| ≥ |f′(X^{∗})| − |X^{∗} − ξ| · |f′′(η)|
≥ \frac{1}{m^{m}(M − 1)^{m−1}} − |δ_{0}| · m^{2}(1 + M)^{1+m}
≥ \frac{1}{m^{m}(M − 1)^{m−1}} − \frac{m^{2}(1 + M)^{1+m}}{16m^{3m+9}(1 + M)^{6m}}
≥ \frac{1}{2m^{m}(M − 1)^{m−1}}

From (16) we see that

|F′′(ξ)| ≤ \frac{4 · K^{3}}{|f′(ξ)|^{3}}

where K ≥ max_{i=0,...,3}{|f^{(i)}(ξ)|}. It suffices to choose K = m^{3}(1+M)^{1+m} by Lemma 29. Thus

|F′′(ξ)| ≤ 4(m^{3}(1 + M)^{1+m})^{3} · (2m^{m}(M − 1)^{m−1})^{3}
< 32m^{3m+9}(1 + M)^{6m}
= 2δ_{0}^{−1}.

Our goal, inequality (17) is thus achieved, and we have proved:

Theorem 31 Let f(X) ∈ [X] be square-free with m = deg f and M = 1 + ∥f∥_{∞}. Then Newton iteration for the root of f(X) is guaranteed to converge provided the initial approximate root is at most

δ_{0} = (16m^{2m+9}(1 + M)^{6m})^{−1}

from a root.

If s is the bit-size of f(X) then δ_{0} has about 6s^{2} bits of accuracy.

Remark: It is of practical interest to “dynamically” check when an approximate root is close enough for Newton iteration, since in practice one expects the effective δ_{0} is much larger than the one guaranteed by this theorem.

Exercise 11.1: (a) Let f(X) ∈ [X] be square-free with roots α_{1},…, α_{m}. Show that

∏_{i=1}^{m} f′(α_{i}) = (−1)^{\binom{m}{2}}a^{−m+2}disc(f).

Deduce a lower bound on |f′(α_{i})| from this.

(b) By modifying the proof of the Davenport-Mahler root separation bound show

±\sqrt{\frac{disc(f)}{a^{2m−2}}} = ∏_{j=2}^{n}(α_{j} − α_{1}) · det ( \begin{matrix}1 & 0 & ⋯ & 0 \\ α_{1} & 1 & & 1 \\ α_{1}^{2} & β_{2}^{(2)} & & β_{m}^{(2)} \\ ⋮ & ⋮ & & ⋮ \\ α_{1}^{m−1} & β_{2}^{(m−1)} & & β_{m}^{(m−1)} \end{matrix} )

where β_{j}^{(k)} = (α_{j}^{k} −α_{1}^{k})/(α_{j} −α_{1}). Note that |a ∏_{j=2}^{n}(α_{j} − α_{1})| = |f′(α_{1})|. If f(X) is monic,

deduce that a lower bound for |f′(α)|.

(c) Consider the resultant R(f, g) of f(X), g(X). Show that

R(f, g) = ( \begin{matrix}f_{m} & f_{m−1} & ⋯ & & f_{0} \\ & f_{m} & f_{m−1} & ⋯ & & f_{0} \\ & & ... & & & & ... \\ & & & f_{m} & f_{m−1} & ⋯ & & f_{0} \\ g_{n} & g_{n−1} & ⋯ & g_{0} \\ & g_{n} & g_{n−1} & ⋯ & g_{0} \\ & & ... & & & & ... \\ & & & & g_{n} & ⋯ & & g_{0} \end{matrix} )

is equal to

( \begin{matrix}f_{m} & f_{m−1} & ⋯ & & f_{0} & & & α^{n−1}f(α) \\ & f_{m} & f_{m−1} & ⋯ & & f_{0} & & α^{n−2}f(α) \\ & & ... & & & & ... \\ & & & f_{m} & f_{m−1} & ⋯ & f_{1} & f(α) \\ g_{n} & g_{n−1} & ⋯ & g_{0} & & & α^{m−1}g(α) \\ & g_{n} & g_{n−1} & ⋯ & g_{0} & & α^{m−2}g(α) \\ & & ... & & & & ... \\ & & & & g_{n} & ⋯ & g_{1} & g(α) \end{matrix} )

for any value z. Derive from this a lower bound for |f′(α)| where α is a root of f(X).

(d) (Lang) Show that if f(X) has only simple roots α_{i} (i = 1,…, n), and ω is any complex number then

min_{i} |ω − α_{i}| ≤ |f(ω)|e^{5n(log n+h+4)}

where h = ∥f∥_{∞}.

References

[1] W. W. Adam and L. J. Goldstein. Introduction to Number Theory. Prentice-Hall, Inc, Englewood Cliffs, New Jersey, 1976.

[2] B. Buchberger, G. E. Collins, and R. Loos (eds.). Computer Algebra. Springer-Verlag, 1983.

[3] George E. Collins. Infallible calculation of polynomial zeros to specified precision. In John R. Rice, editor, Mathematical Software III, pages 35–68. Academic Press, New York, 1977.

[4] A. J. Goldstein and R. L. Graham. A Hadamard-type bound on the coefficients of a determinant of polynomials. SIAM Review, 16:394–395, 1974.

[5] Peter Henrici. Elements of numerical analysis. John Wiley, New York, 1964.

[6] M. A. Jenkins and J. F. Traub. Principles for testing polynomial zerofinding programs. ACM Transaction on Mathematical Software, 1:26–34, 1975.

[7] Morris Marden. The geometry of zeros of a polynomial in a complex variable. Math. Surveys. American Math. Soc., New York, 1949.

[8] Maurice Mignotte. Mathematics for Computer Algebra. Springer-Verlag, 1992.

[9] Maurice Mignotte. On the product of the largest roots of a polynomial. Journal of Symbolic Computation, 13:605–611, 1992.

[10] Nikola Obreschkoff. Verteilung and Berechnung der Nullstellen Reeller Polynome. VEB Deutscher Verlag der Wissenschaften, Berlin, German Democratic Republic, 1963.

[11] A. M. Ostrowski. Solution of equations and systems of equations. Academic Press, New York, 1960.

[12] S.M. Rump. Polynomial minimum root separation. Math. Comp., 33:327–336, 1979.

[13] Jacob T. Schwartz. Polynomial minimum root separation (Note to a paper of S.M. Rump). Techical Report 39, NYU-Courant Institute, Robotics Laboratory, February 1985.

[14] Carl Ludwig Siegel. Lectures on the Geometry of Numbers. Springer-Verlag, 1988. Notes by B. Friedman, rewritten by K. Chandrasekharan, with assistance of R. Suter.

[15] D.J. Struik, editor. A source book in Mathematics, 1200-1800. Princeton University Press, 1986.

[16] Horst G. Zimmer. Computational Problems, Methods, and Results in Algebraic Number Theory. Lecture Notes in Mathematics, Volume 262. Springer-Verlag, 1972.