§1. Sturm Sequences  Lecture VII  Page 1

Lecture VII Sturm Theory

We owe to Descartes the problem of counting the number of real roots of a polynomial, and to Waring (1762) and Lagrange (1773) the problem of separating these roots. Lagrange gave the first complete algorithm for separating roots, which Burnside and Panton (1912) declared “practically useless” (a testimony to the implicit efficiency criteria). The decisive technique was found by Sturm in 1829. It superceded the research of his contemporaries, Budan (1807) and Fourier (1831) who independently improved on Descartes and Lagrange. In one sense, Sturm’s work culminated a line of research that began with Descartes’ rule of sign. According to Burnside and Panton, the combination of Horner and Sturm gives the best root separation algorithm of their day. Hurwitz, Hermite and Routh all made major contributions to the subject. Sylvester was especially interested in Sturm’s work, as part of his interest in elimination theory and theory of equations [10]. In [8], he alludes to a general theory encompassing Sturm theory [10]. This is apparently the tome of an article [9]. Uspensky [11] rated highly a method of root separation based on a theorem of Vincent (1836). Of course, all these subjective evaluations of computational methods are based on some implicit model of the human-hand-computer. With the advent of complexity theory we have more objective methods of evaluating algorithms.

One profound generalization of Sturm’s theorem is obtained by Tarski, in his famous result showing the decidability of elementary algebra and geometry (see [3]). Hermite had interest in generalizing Sturm’s theory to higher dimensions, and considered some special cases; the general case has recently been achieved in the theses of Pedersen [5] and Milne [4], independently.

The polynomials and the roots of interest are generally assumed real unless otherwise stated.

§1. Sturm Sequences from PRS

We introduce Sturm’s a remarkable computational tool for counting the real zeroes of a real function. We also show a systematic construction of such sequences from a PRS (Lecture III.2).

Definition 1 Let A(X), B(X) ∈ [X] be non-zero polynomials. By a (generalized) Sturm sequence for A(X), B(X) we mean a PRS

\overline{A} = (A_{0}, A_{1},…, A_{h}), h ≥ 1,

for A(X), B(X) such that for all i = 1,…, h − 1, if

α_{i} A_{i+1} = β_{i} A_{i−1} + Q_{i} A_{i}  (1)

(α_{i}, β_{i} ∈ , Q_{i} ∈ [X]) then α_{i} β_{i} < 0.

We call \overline{A} a Sturm sequence for A(X) if it is a Sturm sequence for A(X), A′(X).

Note that the degrees of A(X) and B(X) are arbitrary, that is, we do not assume deg A ≥ deg B in this definition. However, by the nature of the remaindering process, the degrees of all subsequent polynomials are strictly decreasing (terminating when A_{h} divides A_{h−1}). Note that the relation (1) exists by the definition of PRS.

Connection between a PRS and a Sturm sequence. It is clear that a Sturm sequence differs from a PRS only by virtue of the special sign requirements on the coefficients of similarity α_{i}, β_{i}. Our goal now is to construct a Sturm sequence from a PRS.

Assume that we are given a PRS \overline{A} = (A_{0},…, A_{h}). We need not know the values α_{i}, β_{i} or Q_{i} in equation (1), but we do require knowledge of the product

s_{i}:= sign(α_{i}β_{i})

of signs, for i = 1,…, h − 1. Here sign(x) is a real function that returns +1 if x > 0, −1 if x < 0, and 0 otherwise. In any of the known PRS algorithms, these signs can be easily obtained as a byproduct of computing the PRS. We will now construct a sequence

(σ_{0}, σ_{1},…, σ_{h}),

of signs where σ_{0} = σ_{1} = +1 and σ_{i} ∈ {−1, 0, +1} such that

(σ_{0} A_{0}, σ_{1} A_{1},…, σ_{h} A_{h})  (2)

is a Sturm sequence. From (1) we see that

(α_{i}σ_{i+1})(σ_{i+1}A_{i+1}) = (β_{i}σ_{i−1})(σ_{i−1}A_{i−1}) + Q_{i}A_{i}.

Hence (2) is a Sturm sequence provided that sign(α_{i}σ_{i+1}β_{i}σ_{i−1}) = −1 or

sign(s_{i}σ_{i+1}σ_{i−1}) = 1.

Multiplying together j (2 ≤ 2j ≤ h) of these equations,

(σ_{0}s_{1}σ_{2})(σ_{2}s_{3}σ_{4})(σ_{4}σ_{5}σ_{6}) ⋯ (σ_{2j−2}s_{2j−1}σ_{2j}) = 1.

Telescoping, we obtain the desired formula for σ_{2j}:

σ_{2j} = ∏_{i=1}^{j} s_{2i−1}  (3)

Similarly, we have the formula for σ_{2j+1} (2 ≤ 2j + 1 ≤ h):

σ_{2j+1} = ∏_{i=1}^{j} s_{2i}  (4)

Thus the sequence (σ_{1},…, σ_{h}) of signs splits into two alternating subsequences whose computation depends on two disjoint subsets of {s_{1},…, s_{h−1}}. Also (3) and (4) can be rapidly computed in parallel, using the so-called parallel prefix algorithm.

Exercise 1.1: Modify the Brown-Collins subresultant algorithm to produce a Sturm Sequence.

Exercise 1.2: (Descartes’ rule of sign) Prove that the sign variation in the sequence (a_{n}, a_{n−1},…, a_{1}, a_{0}) of coefficients of a real polynomial P (X) = ∑_{i=0}^{n} a_{i}X^{i} is an upper bound on the number of positive real roots of P (X). In fact, it is more that the number of positive real roots by some even number. Hint: let Q(X) be a real polynomial and α is a positive real number. Show that the number of sign variations in the coefficient sequence of (X − α)Q(X) is bigger than that in the coefficient sequence of Q(X) by an odd number.

§2. Generalized Sturm Theorem  Lecture VII  Page 3

Exercise 1.3: a) Give the analogue of Descartes’ rule of sign for negative real roots. b) Prove that if P (X) has only real roots, then the number of sign variations in P (X) and P (−X) is exactly n.

c) Let (a_{n},…, a_{1}, a_{0}) be the sequence of coefficients of P (X). If a_{n}a_{0} ≠ 0 and P (X) has only real roots, then the sequence has the property that a_{i} = 0 implies a_{i−1}a_{i+1} < 0.

Exercise 1.4: (Budan-Fourier) Let A_{0}(X) be a polynomial, α < β and A_{0}(α)A_{0}(β) ≠ 0. Let \overline{A} = (A_{0}, A_{1},…, A_{h}) be the sequence of non-zero derivatives of A_{0}, viz., A_{i} is the ith derivative of A_{0}. Then the number of real zeros of A_{0}(X) in [α, β] is less than the Var\overline{A}[α, β] by an even number. Hint: Relate the location of zeros of A(X) and its derivative A′(X). Use induction on deg A_{0}.

Exercise 1.5: a) Deduce Descartes’ rule from the Budan-Fourier rule.

b) (Barbeau) Show that Descartes’ rule gives a sharper estimate for the number of negative zeros than Budan-Fourier for the polynomial X^{4} + X^{2} + 4X − 3.

§2. A Generalized Sturm Theorem

Definition: Let \overline{α} = (α_{0},…, α_{h}) be a sequence of real numbers. Say there is a sign variation in \overline{α} at position i (i = 1,…, h) if for some j = 0,…, i − 1 we have

(i) α_{j} α_{i} < 0

(ii) α_{j+1} = α_{j+2} = ⋯ = α_{i−1} = 0.

The (number of) sign variation of \overline{α} is the number of positions in \overline{α} where there is a sign variation. For instance, the sign variation of (0, −1, 0, 3, 8, −7, 9, 0, 0, 8) is 3.

For any sequence \overline{A} = (A_{0},…, A_{h}) of polynomials and α ∈ , let \overline{A}(α) denote the sequence (A_{0}(α),…, A_{h}(α)). Then the sign variation of \overline{A}(α) is denoted

Var\overline{A}(α),

where we may omit the subscript when \overline{A} is understood. If \overline{A} is the Sturm sequence for A, B, we may write Var_{A,B}(α) instead of Var\overline{A}(α). If α < β, we define the sign variation difference over the interval [α, β] to be

Var\overline{A}[α, β] := Var\overline{A}(α) − Var\overline{A}(β).  (5)

There are different forms of “Sturm theory”. Each form of Sturm theory amounts to giving an interpretation to the sign variation difference (5), for a suitable notion of the “Sturm sequence” \overline{A}. In this section, our goal is to prove a general theorem that encompasses several known Sturm theories.

Since it is a difference in sign variation that we need in (5), we could truncate away any prefix of a Sturm sequence if each polynomials in this prefix maintains a constant sign for X = α in the range of interest.

Exercise 2.1: Suppose \overline{A} and \overline{B} are both Sturm sequences for A, B ∈ [X]. Then they have the same length and corresponding elements of \overline{A} and \overline{B} are related by positive factors: A_{i} = α_{i}B_{i} where α_{i} is a positive real number.

In terms of counting sign variations, it is clear from this exercise that all Sturm sequences for A, B are equivalent. Hence, we may loosely refer to the Sturm sequence of A, B.

Let r ≥ 0 be a non-negative integer. Recall that α is a root of multiplicity r (equivalently, α is an r-fold root) of an r-fold differentiable funtion f(X) if

f^{(0)}(α) = f^{(1)}(α) = ⋯ = f^{(r−1)}(α) = 0, f^{(r)}(α) ≠ 0.

If we simply say ‘α is a root of f(X)’ then it is understood that the multiplicity r is positive. If h is sufficiently small and α is an r-fold root, then Taylor’s theorem with remainder gives us

f(α + h) = \frac{h^{r}}{r!} · f^{(r)}(α + θh)

for some θ, 0 ≤ θ ≤ 1. So for h > 0, f(α + h) has the sign of f^{(r)}(α); for h < 0, f(α + h) has the sign of (−1)^{r}f^{(r)}(α). Hence:

If r is odd, f(X) changes sign in the neighborhood of α;

If r is even, f(X) maintains its sign in the neighborhood of α.

Definition 2 Let \overline{A} = (A_{0},…, A_{h}) be a sequence of non-zero polynomials and α a real value.

i) We say α is regular for \overline{A} if each A_{i}(X) ∈ \overline{A} is non-vanishing at X = α. ii) We say α is degenerate for \overline{A} if each A_{i}(X) ∈ \overline{A} vanishes at X = α. We say α is irregular or nondegenerate as negations of the corresponding concepts. iii) A closed interval [α, β] where α < β is called a fundamental interval (at γ_{0}) for \overline{A} if α, β are non-roots of A_{0} and there exists γ_{0} ∈ [α, β] such that for all γ ∈ [α, β], if γ ≠ γ_{0} then γ is regular for \overline{A}. Note that γ_{0} can be equal to α or β.

Hence α may be neither regular nor degenerate for \overline{A}. In fact, there are only a finite number of irregular values for any Sturm sequence.

The importance of fundamental interval arises as follows. Suppose we want to evaluate Var_{A,B}[α, β] where α, β are non-roots of A. Clearly there are only a finite number of irregular values in the interval [α, β]. If there are no irregular values in the interval, then trivially Var_{A,B}[α, β] = 0. Otherwise, we can find values

α = α_{0} < α_{1} < ⋯ < α_{k} = β

such that each [α_{i−1}, α_{i}] is a fundamental interval. Clearly

Var_{A,B}[α, β] = ∑_{i=1}^{k} Var_{A,B}[α_{i−1}, α_{i}].

So we have reduced our problem to sign variation difference on fundamental intervals.

Lemma 1 Let \overline{A} = (A_{0},…, A_{h}) be a Sturm sequence.

a) The following are equivalent:

(i) α is degenerate for \overline{A}.

(ii) two consecutive polynomials in \overline{A} vanishes at α. (iii) A_{h} vanishes at α.

b) If α is nondegenerate and A_{i}(α) = 0 (i = 1,…, h − 1) then A_{i−1}(α)A_{i+1}(α) < 0.

Proof.

a) If α is degenerate for \overline{A} then clearly any two consecutive polynomials would vanish at α. Conversely, if A_{i−1}(α) = A_{i}(α) = 0, then from equation (1), we see that A_{i+1}(α) = 0 (i+1 ≤ h) and A_{i−2}(α) = 0 (i − 2 ≥ 0). Repeating this argument, we see that all A_{j} vanishes at α. Thus α is degenerate for \overline{A}. This proves the equivalence of (i) and (ii). The equivalence of (ii) and (iii) is easy once we recall that A_{h} divides A_{h−1}, by definition of a PRS. Hence A_{h} vanishes at α implies A_{h−1} vanishes at α.

b) This follows from the fact that α_{i}β_{i} < 0 in equation (1). Q.E.D.

Definition 3 Given real polynomials A(X), B(X), we say A(X) dominates B(X) if for each root α of A(X), we have

r ≥ s ≥ 0

where α is an r-fold root of A(X) and an s-fold root of B(X).

Note that r ≥ 1 since α is a root of A(X). Despite the suggestion of the terminology, “domination” is neither transitive nor asymmetric as a binary relation on real polynomials. We use the concept of domination in the following four situations, where in each case A(X) dominates B(X):

• B(X) is the derivative of A(X)

• A(X) and B(X) are relatively prime

• A(X) and B(X) are both square-free

• B(X) divides A(X)

We come to our key lemma. Here, we use the real function sign(x) which is defined thus

sign(x) = \{ \begin{matrix}−1 & if x < 0 \\ 0 & if x = 0 \\ +1 & if x > 0 \end{matrix}

Lemma 2 Let \overline{A} = (A_{0},…, A_{h}) be a Sturm sequence for A, B where A dominates B. If [α, β] is a fundamental interval at γ_{0} for \overline{A} then

Var\overline{A}[α, β] = \{ \begin{matrix}0 & if r = 0 or r + s is even \\ sign(A^{(r)}(γ_{0})B^{(s)}(γ_{0})) & if r ≥ 1 and r + s is odd, \end{matrix}

where γ_{0} is an r-fold root of A(X) and also an s-fold root of B(X).

Proof. I. First consider the case where γ_{0} is nondegenerate for \overline{A}. Then A_{h}(γ_{0}) ≠ 0. We may define the unique sequence

0 = π(0) < π(1) < ⋯ < π(k) = h, (k ≥ 1)

such that for all i ≠ 0, A_{i}(γ_{0}) ≠ 0 iff i ∈ {π(1), π(2),…, π(k)}. Note that π(0) = 0 has special treatment in this definition. Define for each j = 1,…, k, the subsequence \overline{B}_{j} of \overline{A}:

\overline{B}_{j} :=(A_{π(j−1)}, A_{π(j−1)+1},…, A_{π(j)}).

Since two consecutive polynomials of \overline{A} cannot vanish at a nondegenerate γ_{0}, it follows that since π(j)−π(j −1) equals 1 or 2 (i.e., each \overline{B}_{j} has 2 or 3 members). Indeed, \overline{B}_{j} has 3 members iff its middle member vanishes at γ_{0}. Then the sign variation difference can be expressed as

Var_{A,B}[α, β] = ∑_{i=1}^{k} Var_{\overline{B}_{i}}[α, β].  (6)

Let us evaluate Var_{\overline{B}_{i}}[α, β] in two cases:

CASE 1: Var_{\overline{B}_{i}}[α, β] has three members. Note that the signs of the first and third member do not vary in the entire interval [α, β]. In fact, the signs of the first and third member must be opposite. On the other hand, the sign of the middle member at α and at β are different (one of them can be the zero sign). But regardless, it is now easy to conclude Var_{\overline{B}_{i}}[α, β] = 1 − 1 = 0.

CASE 2: Var_{\overline{B}_{i}}[α, β] has two members. There are two possibilities, depending on whether the first member of the sequence \overline{B}_{i} vanishes at γ_{0} or not. In fact, the first member vanish iff i = 1 (so \overline{B}_{1} = (A, B) and A(γ_{0}) = 0). If A(γ_{0}) ≠ 0, then the signs of both members in \overline{B}_{i} do not vary in the entire interval [α, β]. Hence, this possibility implies Var_{\overline{B}_{i}}[α, β] = 0.

Before we consider the remaining possibility where A(γ_{0}) = 0, we may simplify equation (6), using the fact that all the cases we have considered until now yields Var_{\overline{B}_{i}}[α, β] = 0:

Var_{A,B}[α, β] = \{ \begin{matrix}Var_{\overline{B}_{1}}[α, β] & if A(γ_{0}) = 0 \\ 0 & else. \end{matrix}  (7)

Note that if A(γ_{0}) ≠ 0 then r = 0. Thus equation (7) verifies our lemma for the case r = 0.

It remains to consider the subcase A(γ_{0}) = 0, i.e., r ≥ 1. We have s = 0 because γ_{0} is assumed to be nondegenerate for \overline{A}. Also α < γ_{0} < β. There are two subcases.

SUBCASE: r is even. Then A(X) and B(X) both maintain their signs in the neighborhood of γ_{0} (except temporarily vanishing at γ_{0}). Then we see that

Var_{\overline{B}_{1}}(α) = Var_{\overline{B}_{1}}(β),

proving the lemma when s = 0 and r ≥ 1 is even.

SUBCASE: r is odd. Then A(X) changes sign at γ_{0} while B(X) maintains its sign in [α, β]. Hence Var_{\overline{B}_{1}}[α, β] = ±1. In fact, the following holds:

Var_{\overline{B}_{1}}[α, β] = sign(A^{(r)}(γ_{0})B^{(s)}(γ_{0})),  (8)

proving the lemma when s = 0 and r ≥ 1 is odd. [Let us verify equation (8) in case B(X) > 0 throughout the interval. There are two cases: if A^{(r)}(γ_{0}) < 0 then we get Var_{\overline{B}_{1}}(α) = 0 and Var_{\overline{B}_{1}}(β) = 1 so that Var_{\overline{B}_{1}}[α, β] = sign(A^{(r)}(γ_{0})). If A^{(r)}(γ_{0}) > 0 then Var_{\overline{B}_{1}}(α) = 1 and Var_{\overline{B}_{1}}(β) = 0, and again Var_{\overline{B}_{1}}[α, β] = sign(A^{(r)}(γ_{0})).]

II. It remains to consider the case where γ_{0} is degenerate. This means α < γ_{0} < β. Let

\overline{C} = (A_{0}/A_{h}, A_{1}/A_{h},…, A_{h}/A_{h})

be the depressed sequence derived from \overline{A}. This is a Sturm sequence for C_{0} = A_{0}/A_{h}, C_{1} = A_{1}/A_{h}. Moreover, γ_{0} is no longer degenerate for \overline{C}, and we have

Var\overline{A}(γ) = Var\overline{C}(γ),

for all γ ∈ [α, β]. Since C_{0} dominates C_{1} and [α, β] remains a fundamental interval at γ_{0} for \overline{C}, the result of part I in this proof can now be applied to \overline{C}, showing

Var\overline{C}[α, β] = \{ \begin{matrix}0 & if r^{∗} = 0 or r^{∗} + s^{∗} = even, \\ sign(C_{0}^{(r^{∗})}(γ_{0})C_{1}^{(s^{∗})}(γ_{0})) & if r^{∗} ≥ 1 and r^{∗} + s^{∗} = odd. \end{matrix}  (9)

Here r^{∗}, s^{∗} are the multiplicities of γ_{0} as roots of C_{0}, C_{1} (respectively). First assume r^{∗} ≥ 1. Clearly, if γ_{0} is an m-fold root of A_{h}(X), then r = r^{∗} + m, s = s^{∗} + m. Hence r^{∗} + s^{∗} = even iff r + s = even. This shows

Var\overline{A}[α, β] = Var\overline{C}[α, β] = 0

when r + s = even, as desired. If r + s = odd, we must show

sign(C_{0}^{(r^{∗})}(γ_{0})C_{1}^{∗(s^{∗})}(γ_{0})) = sign(A^{(r)}(γ_{0})B^{(s)}(γ_{0})).  (10)

For clarity, let A_{h}(X) be rewritten as D(X) so that

A(X) = C_{0}(X) · D(X)
A^{(r)}(X) = ∑_{i=0}^{r} \binom{r}{i}C_{0}^{(i)}(X)D^{(r−i)}(X)

A^{(r)}(γ_{0}) = \binom{r}{r^{∗}}C_{0}^{(r^{∗})}(γ_{0})D^{(m)}(γ_{0})

since C_{0}^{(i)}(γ_{0}) = 0 for i < r^{∗}, and D^{(r−i)}(γ_{0}) = 0 for i > r^{∗}. Similarly,

B^{(s)}(γ_{0}) = \binom{s}{s^{∗}}C_{1}^{(s^{∗})}(γ_{0})D^{(m)}(γ_{0}).

This proves (10).

Finally suppose r^{∗} = 0. But the assumption that A dominates B implies s^{∗} = 0. Hence s^{∗} + r^{∗} is even and Var\overline{C}[α, β] = 0. Hence s + r is also even and Var\overline{A}[α, β] = 0. This completes the proof. Q.E.D.

This lemma immediately yields the following:

§3. Corollaries and Applications  Lecture VII  Page 8

Theorem 3 (Generalized Sturm) Let A dominate B and let α < β so that A(α)A(β) ≠ 0. Then

Var_{A,B}[α, β] = ∑_{γ,r,s} sign(A^{(r)}(γ)B^{(s)}(γ))

where γ range over all roots of A in [α, β] of multiplicity r ≥ 1, and B has multiplicity s at γ, and r + s = odd.

§3. Corollaries and Applications

We obtain four useful corollaries to the generalized Sturm theorem. The first is the classic theorem of Sturm.

Corollary 4 (Sturm) Let A(X) ∈ [X] and suppose α < β are both non-roots of A. Then the number of distinct real roots of A(X) in the interval [α, β] is given by Var_{A,A′}[α, β].

Proof. With B(X) = A′(X), we see that A(X) dominates B(X) so that the generalized Sturm theorem gives:

Var_{A,B}[α, β] = ∑_{γ,r,s} sign(A^{(r)}(γ)B^{(s)}(γ)),

where γ is an r-fold root of A in (α, β), γ is an s-fold root of B and r ≥ 1, r + s = odd. But at every root of A, these conditions are satisfied since r = s + 1. Hence the summation applies to every root γ of A. Furthermore, we see that A^{(r)}(γ) = B^{(s)}(γ) so that sign (A^{(r)}(γ)B^{(s)}(γ)) = 1. So the summation yields the number of roots of A in [α, β]. Q.E.D.

Note that it is computationally convenient that our version of Sturm’s theorem does not assume A(X) is square-free (which is often imposed).

Corollary 5 (Schwartz-Scharir) Let A(X), B(X) ∈ [X] be square-free polynomials. If α < β are both non-roots of A then

Var_{A,B}[α, β] = ∑_{γ} sign(A′(γ)B(γ))

where γ ranges over all roots of A(X) in [α, β].

Proof. Since A dominates B, we may apply the generalized Sturm theorem, which says

Var\overline{A}[α, β] = ∑ sign(A^{(r)}(γ)B^{(s)}(γ)),

summed over all roots γ of A(X) in [α, β] of multiplicity r ≥ 1 and γ is a root of B(X) of multiplicity s ≥ 0 and r + s is odd. Since A(X) is square-free, r = 1. Since B(X) is square-free, s ≤ 1, so s = 0. Hence,

Var\overline{A}[α, β] = ∑_{γ} sign(A′(γ)B(γ))

where the summation is over roots γ of A in [α, β] which are not roots of B. But if γ is both a root of A and of B then sign(A′(γ)B(γ)) = 0 and we may add these terms to the summation without any effect. This final summation is that sought in the corollary. Q.E.D.

Another corollary (which will be useful in a parallel algorithm for decomposing semi-algebraic sets) is the following:

Corollary 6 (Sylvester, revisited by Ben-Or, Kozen, Reif) If \overline{A} is a Sturm sequence for A, A′B where A(X) is square-free and A(X), B(X) are relatively prime. Then for all α < β which are non-roots of A,

Var\overline{A}[α, β] = ∑_{γ} sign(B(γ))

where γ range over the roots of A(X) in [α, β].

Proof. Again note that A dominates A′B and we can proceed as in the proof of the previous corollary. But now, we get

Var\overline{A}[α, β] = ∑_{γ} sign(A′(X) · A′(X)B(X))
= ∑_{γ} sign(B(X)),

as desired. Q.E.D.

In this corollary, the degree of A_{0} = A is generally less than the degree of A_{1} = A′B so that the remainder sequence typically looks like this: \overline{A} = (A, A′B, −A,…).

Our final corollary concerns the concept of the Cauchy index of a rational function. Let f(X) be a real continuous function defined in an open interval (α, β) where −∞ ≤ α < β ≤ +∞. We allow f(X) to have isolated poles γ ∈ (α, β), i.e., 1/f(γ) = 0. The Cauchy index of f at a pole γ is defined to be

\frac{sign(f(γ^{−})) − sign(f(γ^{+}))}{2}.

For instance, the index is 1 if f(X) changes from −∞ to +∞ as X increases through γ, and 0 is the sign of f(X) does not change in passing through γ. The Cauchy index of f over an interval (α, β) is then

I_{α}^{β}f(X) := ∑_{γ} \frac{sign(f(γ^{−})) − sign(f(γ^{+}))}{2}

where the sum is taken over all poles γ ∈ (α, β). Typically, f(X) is a rational function A(X)/B(X) where A(X), B(X) are relatively prime polynomials.

Corollary 7 (Cauchy Index) Let A(X), B(X) ∈ [X] be relatively prime and f(X) = A(X)/B(X). Then

I_{α}^{β}f(X) = −Var_{A,B}[α, β].

Proof. By the generalized Sturm sequence theorem,

Var_{A,B}[α, β] = ∑_{γ,r,s} sign(A^{(r)}(γ)B^{(s)}(γ))

where γ range over the roots of A such that r + s is odd, r ≥ 1 is the multiplicity of A at γ and s ≥ 0 is the multiplicity of B at γ. This means that s = 0 and r is odd. Thus:

sign(A^{(r)}(γ)) = \frac{sign(A(γ^{+})) − sign(A(γ^{−}))}{2}
sign(A^{(r)}(γ)B^{(0)}(γ)) = \frac{sign(A(γ^{+})B(γ^{+})) − sign(A(γ^{−})B(γ^{−}))}{2}
= \frac{sign(f(γ^{+})) − sign(f(γ^{−}))}{2}.

The desired result follows by summing over each γ. Q.E.D.

This result will be used in a later section. For now, we give two applications of the corollary of Schwartz-Scharir (cf. [7]).

A. The sign of a real algebraic number. The first problem is to determine the sign of a number β in a real number field (α). We assume that β is represented by a rational polynomial B(X) ∈ [X]: β = B(α). Assume α is represented by the isolating interval representation

α ≅ (A, [a, b])

where A ∈ [X] is a square-free polynomial. First let us assume B(X) is square-free. To determine the sign of β, first observe that

sign(A′(α)) = sign(A(b) − A(a)).  (11)

Using the corollary of Schwartz-Sharir,

Var_{A,B}[a, b] = sign(A′(α) · B(α)).

Hence,

sign(B(α)) = sign((Var_{A,B}[a, b]) · A′(α))
= sign((Var_{A,B}[a, b]) · (A(b) − A(a))).

If B(X) is not square-free, we can first decompose it into a product of square-free polynomials, and we proceed in the obvious manner.

Exercise 3.1: Alternatively, use the Sylvester corollary to obtain the sign of B(α).

B. Comparing two real algebraic numbers. Given two real algebraic numbers

α ≅ (A, I), β ≅ (B, J)

represented as indicated by isolating intervals, we wish to compare them. Of course, one method is to determine the sign of α−β, by a suitable reduction to problem A. But we give a more direct reduction. If I ∩ J = ∅ then the comparison is trivially done. Otherwise, if either α ∉ I ∩ J or β ∉ I ∩ J then again we can easily determine which of α or β is bigger. Hence assume α and β are both in a common isolating interval I ∩ J = [a, b].

Figure 1. Conditions for α > β in isolating interval [a, b].

It is not hard to verify (see Figure 1) that

α ≥ β ⇔ B(α) · B′(β) ≥ 0,

with equality on the left-hand side if and only if equality is attained on the right-hand side (note that B′(β) ≠ 0 by square-freeness of B). Since we already know how to obtain the signs of B(α) and of B′(β) (problem A), we are done:

B(α) · B′(β) ≥ 0 ⇔ (Var_{A,B}[a, b]) · (A(b) − A(a)) · (B(b) − B(a)) ≥ 0.

Exercise 3.2: Isolate all the roots of

(X^{2} + 7)^{2} − 8X = X^{4} + 14X^{2} − 8X + 49.

Exercise 3.3: Give an algorithm to do a square-free factorization of a polynomial P (X) ∈ [X]: P (X) = P_{1}P_{2} ⋯ P_{k} where each P_{i} is a square-free polynomial with positive degree. Analyze the complexity of your algorithm.

.

Exercise 3.4: Without using the primitive element theorem, we may represent elements of a number field F = (α_{1},…, α_{k}) as follows: (a) Show that α_{1},…, α_{k} are algebraic numbers, there is a rational integer N such that every algebraic integer of F is represented as an element of \frac{1}{N} [α_{1},…, α_{k}]. Note that each element of F is represented as an algebraic integer divided by a rational integer.

(b) Give an efficient method of testing a number for zero under the first representation (we do not make any assumptions about the α_{1},…, α_{k}, and assume that the α_{i} are represented by just their minimal polynomials).

§4. Integer and Complex Roots  Lecture VII  Page 12

Exercise 3.5: (a) Let q(y) ∈ (α)[y], where α is a real root of p(X) ∈ [X]. Assuming that we have an isolating interval representation for α (relative to p(X) and the coefficients of q(y) are represented by rational polynomials in α. Show how to carry out a Sturm sequence computation to isolate the real roots of q(y). Analyse the complexity of your algorithm.

(b) This gives us a method of representing elements of the double extension (α)(β). Extend the method to multiple (real) extensions: (α_{1}) ⋯ (α_{k}). Explain how arithmetic in such representations might be carried out.

Exercise 3.6: (Schwartz-Sharir) Given an integer polynomial P (X) (not necessarily squarefree) and an isolating interval I of P (X) for one of its real roots α, determine the multiplicity of P (X) at α.

Exercise 3.7: Give a version of the generalized Sturm’s theorem where we replace the condition that α, β are non-roots of A by the condition that these are nondegenerate.

Exercise 3.8*: Is there a simple method to decide if an integer polynomial has only real roots?

§4. Integer and Complex Roots

We discuss the special cases of integer and rational roots, and the more general case of complex roots.

Integer and Rational Roots. Let A(X) = ∑_{i=0}^{n} a_{i}X^{i} be an integer polynomial of degree n. We observe that if u is an integer root of A(X) then

a_{0} = − ∑_{i=1}^{n} a_{i}u^{i} = −u (∑_{i=1}^{n} a_{i}u^{i−1})

and hence u divides a_{0}. Hence, checking if A(u) has any integer roots it can be reduced to factorization of integers: we simply factor a_{0} and for each integer factor b, we can quickly check if A(b) = 0.

Similarly, if u/v is a rational root of A(X) with (u, v) = 1 it is easily checked that u divides a_{0} and v divides a_{n}. As a corollary, if u/v is a rational root of a monic integer polynomial then v = 1 (i.e., the algebraic integers that are rational is precisely ).

Remark: The complexity of integer roots for multivariate polynomials is undecidable, being many-one equivalent to the halting problem. This is the famous 10th problem of Hilbert that was proved undecidable by Matiyasevič 1970. For an exposition of this result, see the book of Davis [1, Appendix 2]. It is an open problem whether finding rational zeroes in this case is decidable.

Complex Roots. We reduce the extraction of complex roots to the real case. The real and complex component of a complex algebraic number may be represented using isolating intervals.

In this setting, it is reasonable to assume that our polynomials have complex coefficients. In practice, these coefficients will be Gaussian integers [i] or Gaussian rationals (i).

If F (X) ∈ [X] and α + iβ ∈ (α, β ∈ ) is a root of F (X) then we may write

F (α + iβ) = P (α, β) + iQ(α, β)

where P (X, Y), Q(X, Y) are bivariate polynomials determined by F. This reduces the problem of finding α, β to solving the simultaneous system

P (α, β) = 0
Q(α, β) = 0.

We solve for α using resultants:

R(X) := res_{Y} (P (X, Y), Q(X, Y)).

For each real root α of R(X), we can plug α into P (α, Y) to solve for Y = β. (We have not explicitly described how to handle polynomials with algebraic coefficients but in principle we know how to perform arithmetic operations for algebraic numbers.) Alternatively, we can solve find β as the real roots of res_{X}(P, Q) and check for each pair α, β that may serve as a root α + iβ of F (X). This will be taken up again in the next section.

It is instructive to examine the above polynomials P, Q in greater detail. To this end, let us write F (X) as

F (X) = A(X) + iB(X), A(X), B(X) ∈ [X].

Then by Taylor’s expansion,

A(α + iβ) = A(α) + \frac{A′(α)}{1!} · (iβ) + \frac{A′′(α)}{2!} · (iβ)^{2} + ⋯ + \frac{A^{(n)}(α)}{n!}(iβ)^{n}

where n = max{deg A, deg B}. Similarly,

B(α + iβ) = B(α) + \frac{B′(α)}{1!}(iβ) + ⋯ + \frac{B^{(n)}}{n!} (iβ)^{n}.

Hence the real and imaginary parts of F (α + iβ) is

P (α, β) = A(α) + \frac{B′(α)}{1!}(−β) + \frac{A^{(2)}(α)}{2!}(−β^{2}) + …,
Q(α, β) = B(α) + \frac{A′(α)}{1!}(β) + \frac{B^{(2)}(α)}{2!}(−β^{2}) + ….

Hence P (α, β) and Q(α, β) are polynomials of degree ≤ n in β with coefficients that are polynomials in α of degree ≤ n. Hence R(α) is a polynomial of degree \frac{n(n+1)}{2} in α. Moreover, the bit-size of R(X) remains a polynomial in the bit-size of A(X), B(X). Hence, any polynomial time solution to real root isolation would lead to a polynomial time solution to complex root isolation.

Remarks: We refer to Householder [2] for more details on this approach.

Exercise 4.1: Work out the algorithmic details of the two methods for finding complex roots as outlined above. Determine their complexity.

§5. Routh-Hurwitz Theorem  Lecture VII  Page 14

Exercise 4.2: Express P (α, β) and Q(α, β) directly in terms of F^{(i)}(α) and β^{i} by a different Taylor expansion, F (α + iβ) = F (α) + F′(α)(iβ) + · · ·.

§5. The Routh-Hurwitz Theorem

We now present an alternative method for reducing the problem of isolating complex zeros to Sturm’s theory. First we consider a special subproblem: to count the number of complex roots in the upper complex plane. This problem has independent interest in the theory of stability of dynamical systems, and was first solved by Routh in 1877, using Sturm sequences. Independently, Hurwitz in 1895 gave a solution based on the theory of residues and quadratic forms. Pinkert [6] exploited this theory to give an algorithm for isolating complex roots. Here, we present a variant of Pinkert’s solution.

In this section we consider complex polynomials as well as real polynomials.

We begin with an elementary result, a variant of the so-called principle of argument. Let F (Z) ∈ [Z] and L be a directed line in the complex plane. Consider the increase in the argument of F (Z) as Z moves along the entire length of L, denoted

Δ_{L} arg F (Z).

Lemma 8 Suppose no root of F (Z) lies on L, p ≥ 0 of the complex roots of F (Z) lie to the left-hand side of L, and q ≥ 0 of the roots lie to the right-hand side, multiplicity counted. Then Δ_{L} arg F (Z) = π(p − q).

Proof. Without loss of generality, let F (Z) = ∏_{i=1}^{p+q}(Z − α_{i}) where α_{i} ∈ are the roots of F (Z). Then arg F (Z) = ∑_{i=1}^{p+q} arg(Z − α_{i}). Suppose α_{i} lies to the left of L. Then as Z moves along the entire length of L, arg(Z − α_{i}) increases by π i.e., Δ_{L} arg(Z − α_{i}) = π. Similarly, if α_{i} lies to the right of L, Δ_{L} arg(Z − α_{i}) = −π. The lemma follows by summing over each root. Q.E.D.

Since p + q = deg F (Z), we conclude:

Corollary 9

p = \frac{1}{2} [deg F + \frac{1}{π} Δ_{L} arg F (Z)] ,
q = \frac{1}{2} [deg F − \frac{1}{π} Δ_{L} arg F (Z)] .

Number of roots in the upper half-plane. Our immediate goal is to count the number of roots above the real axis. Hence we now let L be the real axis. By the foregoing, the problem amounts to deriving a convenient expression for Δ_{L} arg F (Z). Since Z is going to vary over the reals L, we prefer to use a real variable X instead of the complex variable Z. We also use ‘F (X)’ instead of ‘F (Z)’. Let

F (X) =: F_{0}(X) + iF_{1}(X), (F_{0}(X), F_{1}(X) ∈ [X]).

Without loss of generality, we may assume that F (X) is monic so that deg F_{0} = deg F = n and deg F_{1} ≤ n − 1. We will assume F (X) has no real roots and further, F (X) is not a real polynomial (i.e., F_{1} is not the zero polynomial). Let

ρ(X) := \frac{F_{0}(X)}{F_{1}(X)}

and hence arg F (X) = cot^{−1}ρ(X). Let

α_{1} < α_{2} < ⋯ < α_{k}

be the real roots of F_{0}(X). They divide the real axis L into k + 1 segments,

L = L_{0} ∪ L_{1} ∪ ⋯ ∪ L_{k}, (L_{i} = [x_{i}, x_{i+1}])

where x_{0} = −∞ and x_{k+1} = +∞. Thus,

Δ_{L} arg F (X) = ∑_{i=0}^{k} Δ_{α_{i}}^{α_{i+1}}cot^{−1}ρ(X).

Here the notation

Δ_{α}^{β}f(Z)

denotes the increase in the argument of f(Z) as Z moves along the line segment from α to β. The assumption that F (X) has no real roots implies that that ρ(X) is defined for all X (we do not get 0/0) and ρ(X) = 0 iff X ∈ {α_{i} : i = 1,…, k}. We will be examining the signs of ρ(α_{i}^{−}) and ρ(α_{i}^{+}), and the following graph of the cotangent function is helpful:

Figure 2. The cotangent function.

Note that cot^{−1}ρ(α_{i}) = cot^{−1}0 = ±π/2 (taking principal values), and

Δ_{α_{i}}^{α_{i+1}}cot^{−1}ρ(X) lim_{ϵ→0} = Δ_{α_{i}+ϵ}^{α_{i+1}−ϵ}cot^{−1}ρ(X).

But ρ(X) does not vanish in the interval [α_{i} + ϵ, α_{i+1} − ϵ]. Hence for i = 1,…, k − 1,

Δ_{α_{i}}^{α_{i+1}}cot^{−1}ρ(X) = \{ \begin{matrix}0 & if ρ(α_{i}^{+})ρ(α_{i+1}^{−}) > 0 \\ π & if ρ(α_{i}^{+}) < 0, ρ(α_{i+1}^{−}) > 0 \\ −π & if ρ(α_{i}^{+}) > 0, ρ(α_{i+1}^{−}) < 0 \end{matrix}

= π [\frac{sign(ρ(α_{i+1}^{−})) − sign(ρ(α_{i}^{+}))}{2}] .  (12)

This is seen by an examination of the graph of cot ϕ. For i = 0, k, we first note that ρ(−∞) = ±∞ and ρ(+∞) = ±∞ since deg F_{0} > deg F_{1}. It follows that

Δ_{−∞}^{α_{1}}cot^{−1}ρ(X) = \frac{π}{2} sign(ρ(α_{0}^{−}))  (13)
Δ_{α_{k}}^{+∞}cot^{−1}ρ(X) = −\frac{π}{2} sign(ρ(α_{k}^{+}))  (14)

Combining equations (12), (13) and (14):

Lemma 10

Δ_{L} arg F (X) = π ∑_{i=1}^{k} \frac{sign(ρ(α_{i}^{−})) − sign(ρ(α_{i}^{+}))}{2}

Recall that expression \frac{sign(ρ(α_{i}^{−}))−sign(ρ(α_{i}^{+}))}{2} is the Cauchy index of ρ at α_{i}. By Corollary 7 (§3), −Var_{F_{0},F_{1}}[−∞, +∞] counts the Cauchy index of ρ over the real line L. We have proved:

Theorem 11 (Routh) Let F (X) = F_{0}(X) + iF_{1}(X) be monic with no real roots and F_{1} ≠ 0. The number of roots of F (X) lying above the real axis L is given by

\frac{1}{2} (deg F − Var_{F_{0},F_{1}}[−∞, +∞]) .

To exploit this result for a complex root isolation method, we proceed as follows.

1. Presence of real roots. In case F (Z) = F_{0}(Z) + iF_{1}(Z) has a real root, say α, we note that α must also be a real root of G(Z) = GCD(F_{0}(Z), F_{1}(Z)). [In fact, the converse also holds: if α is a real root of G(Z) then F (α) = 0.] Hence, Routh’s theorem can be applied to F′(Z) = F′_{0}(Z) + iF′_{1}(Z) where F′_{i}(Z) = F_{i}(Z)/G(Z). We can recursively apply the procedure on G(Z).

2. Counting Roots to one side of the imaginary axis. Suppose we want to count the number p of roots of F (Z) to the right of the imaginary axis, assuming F (Z) does not have any purely imaginary roots. Note that α is a root of F (Z) to the right of the imaginary axis iff iα is a root of F (Z/i) = F (−iZ) lying above the real axis. It is easy (previous section) to construct the polynomial G(Z) := F (−iZ) from F (Z).

3. Roots in two opposite quadrants. We can count the number to roots in the first and third quadrant as follows: from F (Z) construct a polynomial F^{∗}(Z) whose roots are precisely the squares of roots of F (Z). This means that if α is a root of F (Z) in the first (I) or third (III) quadrant then α^{2} is a root of F^{∗}(Z) in the upper half-plane (which we know how to count). Similarly, the roots of F (Z) in (II) and (IV) quadrants are sent into the lower half-plane. It remains to construct F^{∗}(Z). This is easily done as follows: Let F (Z) = F_{o}(Z) + F_{e}(Z) where F_{o}(Z) consists of those monomials of odd degree and F_{e}(Z) consisting of those monomials of even degree. This means F_{o}(Z) is an odd function (i.e., F_{o}(−Z) = −F_{o}(Z)), and F_{e}(Z) is an even function (i.e., F_{e}(−Z) = F_{e}(Z)). Consider

G(Z) = F_{e}(Z)^{2} − F_{o}(Z)^{2}
= (F_{e}(Z) + F_{o}(Z))(F_{e}(Z) − F_{o}(Z))
= F (Z)(F_{e}(−Z) + F_{o}(−Z))
= F (Z)F (−Z).

If F (Z) = c ∏_{i=1}^{n}(Z − β_{i}) where β_{i} are the roots of F (Z) then

F (Z)F (−Z) = c^{2} ∏_{i=1}^{n}(Z − β_{i})(−Z − β_{i}) = (−1)^{n}c^{2} ∏_{i=1}^{n}(Z^{2} − β_{i}^{2}).

Hence, we may define our desired polynomial F^{∗}(Y) by the relation F^{∗}(Z^{2}) = G(Z). In fact, F^{∗}(Y) is trivially obtained from the coefficients of G(Z).

4. Roots inside a quadrant. We can count the number of roots in the first quadrant, thus

#(I) = \frac{1}{2} [(#(I) + #(II)) + (#(I) + #(IV)) − (#(II) + #(IV))]

where #(I) + #(II) and #(I) + #(IV) are half-plane counting queries, and #(II) + #(IV) is a counting query for an opposite pair of quadrants. But we have shown how to answer such queries.

5. Roots in a translated quadrant. If the origin is translated to a point α ∈ , we can count the number of roots of F (Z) in any of the four quadrants whose origin is at α, by counting the number of roots of F (Z + α) in the corresponding quadrant.

6. Putting these together. In the last section, we have shown how to isolate a sequence x_{1} < x_{2} < ⋯ < x_{k} of real numbers that contain among them all the real parts of complex roots of F (Z). Similarly, we can isolate a sequence y_{1} < y_{2} < ⋯ < y_{ℓ} of real numbers that contains among them all the imaginary parts of complex roots of F (Z). So finding all roots of F (Z) is reduced to testing if each x_{i} + iy_{j} is a root. We may assume from the root isolation that we know (rational) numbers a_{i}, b_{j} such that

x_{1} < a_{1} < x_{2} < a_{2} < ⋯ < a_{k−1} < x_{k} < a_{k}, y_{1} < b_{1} < y_{2} < b_{2} < ⋯ < b_{ℓ−1} < y_{ℓ} < b_{ℓ}.

Then for j = 1,…, ℓ and for i = 1,…, k, we determine the number n(i, j) of roots of F (Z) in the quadrant (III) based at a_{i} + ib_{j}. Note that n(1, 1) = 1 or 0 depending on whether x_{1} + iy_{1} is a root or not. It is easy to work out a simple scheme to similarly determine whether each x_{i} + iy_{j} is a root or not.

Exercise 5.1: Determine the complexity of this procedure. You should exploit the fact that the testing of the various x_{i} + iy_{j}’s are related.

Exercise 5.2: Isolate the roots of F (Z) = (Z^{2} − 1)(Z^{2} + 0.16) using this procedure. [This polynomial has two real and two non-real roots. Newton iteration will fail in certain open neighborhoods (attractor regions).]

Exercise 5.3: If F (X) is a real polynomial whose roots has no positive real parts then the coefficients of F (X) has no sign variation.

Exercise 5.4: Let F_{n}(X), F_{n−1}(X),…, F_{0}(X) be a sequence of real polynomials where each F_{i}(X) has degree i and positive leading coefficient. Moreover, if F_{i}(x) = 0 (i = 1, 2,…, n− 1) for any x ∈ , then F_{i−1}(x)F_{i+1}(x) < 0. Then each F_{i}(X) (i = 1,…, n) has i simple real roots and between any two consecutive roots is a root of F_{i−1}.

Exercise 5.5: (Hermite, Biehler) If all the roots of F (X) = A(X) + iB(X) (A(X), B(X) ∈ [X]) lies on one side of the real axis of the complex plane, then A(X) and B(X) have only simple real roots, and conversely.

References

[1] Martin Davis. Computability and Unsolvability. Dover Publications, Inc, New York, 1982.

[2] Alston S. Householder. Principles of Numerical Analysis. McGraw-Hill Book Company, Inc., 1953.

[3] Nathan Jacobson. Basic Algebra 1. W. H. Freeman and Company, San Francisco, 1974.

[4] P. Milne. On the solutions of a set of polynomial equations, 1990. Unpublished preprint, Bath University.

[5] Paul Pedersen. Counting real zeroes. Technical Report 243, NYU-Courant Institute, Robotics Laboratory, 1990. PhD Thesis, Courant Institute, New York University.

[6] James R. Pinkert. An exact method for finding the roots of a complex polynomial. ACM Transaction on Mathematical Software, 2:351–363, 1976.

[7] S. Rump. On the sign of a real algebraic number. Proceedings of 1976 ACM Symp. on Symbolic and Algebraic Computation (SYMSAC 76), pages 238–241, 1976. Yorktown Heights, New York.

[8] J. J. Sylvester. On a remarkable modication of Sturm’s theorem. Philosophical Magazine, pages 446–456, 1853.

[9] J. J. Sylvester. On a theory of the syzegetic relations of two rational integral functions, comprising an application to the theory of sturm’s functions, and that of the greatest algebraical common measure. Philosophical Transactions, 143:407–584, 1853.

[10] J. J. Sylvester. The Collected Mathematical Papers of James Joseph Sylvester, volume 1. Cambridge University Press, 1904.

[11] J. V. Uspensky. Theory of Equations. McGraw-Hill Book Co., New York, 1948.