Sturm's Theorem: Sturm Chains

Before proceeding to Sturm's Theorem, let's talk about Sturm Chains.

Definition 1: Sturm Chain

A Sturm Chain is a series of polynomials P₀, ...., P_m

such that:

(1) For any value of i where i ≥ 1, if P_i(x)=0, then P_i-1(x) = -P_i+1(x)

(2) If P_i(x) = 0 then P_i+1(x) ≠ 0 and if i ≥ 1, then P_i-1(x) ≠ 0.

(3) For a sufficiently small area surrounding a zero point of P₀(x), P₁(x) is everywhere greater than 0 or everywhere smaller than 0.

Lemma 1: Constructibility of a Sturm Chain from a Polynomial

If a polynomial P is differentiable and has only simple roots, then it is possible to construct a Sturm Chain based on it.

Proof:

(1) Let P₀ be the polynomial and P₁ be the first derivative of P₀.

(2) We can now use an alternate form of Euclid's Algorithm for Greatest Common Divisor of Polynomials (see Theorem 1, here) to get the following:

P₀ = Q₁P₁ - P₂
...

P_m-2 = Q_m-1P_m-1 - P_m

where all deg P_i is less than deg P_i-1 and deg P_m = 0.

(3) Since P₀ is simple, we know that P₀ and P₁ are relatively prime [See Lemma 2, here].

(4) Therefore, P_m is degree 0. [See definition 3, here for the definition of relatively prime polynomials]

(5) Now, we can show that P₀, P₁, ..., P_m form a Sturm Chain. Here's the reasoning.

(6) Using step #2 above, we know for i, we have the following equation:

P_i-1 = Q_iP_i - P_i+1

(7) Assume that P_i(x) = 0.

(8) Then it follows that:

P_i-1 = -P_i+1

(9) Assume that P_i(x) = 0 and P_i+1(x) = 0

(10) Then it follows that P_i+2(x) = 0 and so on.

(12) So that P_m(x) = 0. But this is impossible since P_m is a constant (a polynomial of degree 0)

(13) Therefore, we reject our assumption in step #7 and conclude that P_i+1(x) ≠ 0.

(14) In the same way, we can show that if P_i(x) = 0, then it follows that P_i-1 ≠ 0.

(15) Finally, since P₀=P is a polynomial with only simple roots and P₁ = P' is its derivative, we know that (see Lemma, here), for a sufficiently small area surrounding a zero point of P₀(x), P₁(x) is everywhere negative or everywhere positive.

QED

References

• Heinrich Dorrie (Translated by David Antin), 100 Great Problems of Elementary Mathematics (Dover, 1965)