Polynomials of an odd degree have at least one real root

Today, I present a proof taken from Edwards & Penney's Calculus and Analytic Geometry and PlanetMath.org.

I show that any polynomial of odd degree must have at least one root that is real.

Lemma 1:

lim (x → ∞) c/x = 0

where c is a nonzero constant

NOTE: This means that for any positive number ε, we can find a number δ such that:

for all abs(x) ≥ δ, abs(c/x) is less than ε

[See Definition 1, here for definition of mathematical limits]

Proof:

(1) Let ε be any positive number

(2) Assume c is positive.

(3) Let δ = 1 + c/ε

(4) So, then δ is greater than c/ε

(5) Which means that 1/δ is less than ε/c

(6) Which means that c/δ is less than ε

(7) For all n ≥ δ, it follows that:

c/n ≤ c/δ [which is less than ε from step #5 above]

(8) -c/δ is greater than -ε [this follows directly from step #5 from multiplying -1 to both sides]

(9) For all n ≤ -δ, it follows that:

c/n ≥ -c/δ [which is greater than -ε from step #7 above]

(10) Assume that c is negative

(11) Let δ = c/ε - 1

(12) So δ is less than c/ε

(13) So 1/δ is greater than ε/c

(14) Since c is negative, c/δ is less than ε [from multiplying a negative number to both sides]

(15) So for all n ≥ δ, it follows that:

c/n ≤ c/δ [which is less than ε from step #14 above]

(16) -c/δ is greater than -ε [this follows directly from step #14 from multiplying -1 to both sides]

(17) For all n ≤ -δ, it follows that:

c/n ≥ -c/δ [which is greater than -ε from step #16 above]

QED

Corollary 1.1:

limit (c/xⁱ) = 0

where c is a constant and i is a positive integer

Proof:

(1) For i=1, it is true from Lemma 1 above

(2) Let δ be the same δ from Lemma 1 above which depends on the sign of c.

(3) For all n ≥ δ, we have:

c/nⁱ ≤ c/n ≤ c/δ which is less than ε

(4) For all -n ≤ -δ, we have:

c/nⁱ ≥ c/n ≥ -c/δ which is greater than -ε

QED

Corollary 1.2:

Let g(x) = a₁/x + a₂/x² + ... + a_n-1/xⁿ

limit (x → ∞) g(x) = 0

Proof:

(1) For each a_i/xⁱ, the limit is 0. [From Corollary 1.1 above]

(2) Since g(x) is the sum of these values, we apply the Addition Rule [see Corollary 8.1, here] to get:

limit (x → ∞) g(x) = 0

QED

Lemma 2:

If f(x) is a polynomial of odd degree, there exists values a,b such that:

f(a) is less than 0 and f(b) is greater than 0

Proof:

(1) Let f(x) be a polynomial of an odd degree n such that:

f(x) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

(2) We can make f(x) monic (where xⁿ does not have a coefficient) by dividing both sides by a₀.

So, we can assume the following monic form:

xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

(3) Let g(x) = (1/xⁿ)[a₁x^n-1 + ... + a_n-1x + a_n] =

= a₁/x + a₂/x² + ... + a_n-1/x^n-1 + a_n/xⁿ

(4) Then:

f(x) = xⁿ[1 + g(x)]

(5) Using Corollary 1.2 above, we know that there exists δ such that:

for all abs(x) ≥ δ, abs(g(x)) is less than 1 [where ε = 1]

(6) So, it follows that 1 + g(x) is greater than 0.

(7) Let b be any positive number greater than δ.

(8) It follows that f(b) is greater than 0 since bⁿ*[1 + g(x)] is greater than 0.

(9) Let a be any negative number where a is less than -δ.

(10) It follows that f(a) is less than 0 since aⁿ*[1 + g(x)] is less than 0.

QED


Theorem 3: A polynomial of odd degree has at least one real root

Proof:

(1) Let f(x) be a polynomial of odd degree.

(2) All polynomials are continuous [see Corollary 1.1, here], so f(x) is continuous.

(3) There exists a number a such that f(a) is less than 0. [see Lemma 2 above]

(4) There exists a number b such that f(b) is greater than 0. [see Lemma 2 above]

(5) Therefore, there exists at least one real root [see Weierstrass Intermediate Value Theorem, here]

QED

References

• "polynomial equation of odd degree", PlanetMath.Org
• Edwards, Jr. C. H. & Penney, David E., Calculus and Analytic Geometry, Prentice Hall, 1990
  

Elementary Symmetric Polynomials

If we look at Girard's Theorem, we see that:

xⁿ + a₁x^n-1 + a₂x^x-2 + ... + a_n = (x - x₁)*...*(x - x_n)

Now if we solve for each a_i in terms of x_i, we can restate the equation in terms of the elementary symmetric polynomials. In today's blog, I will show a proof of this using induction.


Definition 1: Elementary Symmetric Polynomials

s₁, ..., s_n such that:

s₁ = x₁ + ... + x_n

s₂ = x₁x₂ + ... + x_n-1x_n

s₃ = x₁x₂x₃ + ... + x_n-2x_n-1x_n

...

s_n = x₁x₂*...*x_n

So, let get down to showing the theorem.

Theorem 1: Restatement of Girard's Theorem in terms of the Elementary Symmetric Polynomials:

Xⁿ - s₁X^n-1 + s₂X^n-2 - ... + (-1)ⁿs_n = (X - x₁)(X - x₂)*...*(X-x_n)

Proof:

(1) xⁿ + a₁x^n-1 + a₂x^x-2 + ... + a_n = (x - x₁)*...*(x - x_n) [see Girard's Theorem]

(2) Assume n=1

(3) x + a₁ = x - x₁ = x - s₁

(4) Assume that the theorem holds true up until n.

(5) So that we have:

Xⁿ - (x₁ + ... + x_n)X^n-1 + (x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n) = (X - x₁)(X - x₂)*...*(X-x_n)

(6) Multiplying (X - x_n+1) to both sides gives us:

(X - x₁)(X - x₂)*...*(X-x_n)*(X - x_n+1) = (X - x_n+1)[Xⁿ - (x₁ + ... + x_n)X^n-1 + (x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n)] =

[Xⁿ⁺¹ - (x₁ + ... + x_n)Xⁿ + (x₁x₂ + ... + x_n-1x_n)X^n-1 - ... + (-1)ⁿX(x₁x₂*...*x_n)] - [Xⁿ(x_n+1) - (x_n+1)(x₁ + ... + x_n)X^n-1 + (x_n+1)(x₁x₂ + ... + x_n-1x_n)X^n-2 - ... + (-1)ⁿ(x₁x₂*...*x_n*x_n+1)]

= Xⁿ⁺¹ - (x₁ + ... + x_n + x_n+1)Xⁿ + (x₁x₂ + ... + x_nx_n+1)X^n-1 ... + (-1)ⁿ⁺¹(x₁*...*x_n+1) =

= Xⁿ⁺¹ - s₁Xⁿ + s₂X^n-1 - ... + (-1)ⁿ⁺¹s_n+1

QED

Quotient Rings

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

In a previous blogs, I wrote about cosets and ideals. In today's blog, I will show how we can bring these ideas together to define quotient rings. Here are links to review the properties of groups, subgroups, or commutative rings.

Definition 1: A/I

A/I = { a + I such that a ∈ A}

Note: This is a set of sets. For example, if a + I is a coset, then A/I is the set of distinct cosets. For review of the a + I notation, see here.

Example 1.1: Modular sets

The sets Z/nZ are all examples of A/I.

Z/2Z = { 0+2z, 1+2z } since { 0 + 2z = 2 + 2z = 2z + 2z, 1 + 2z = 3 + 2z = ... }

Z/3Z = { 0 + 3z, 1 + 3z, 2 + 3z }

A/I becomes especially interesting when A is a Commutative Ring and I is in an Ideal. I will assume both of these properties for the rest of this article.

Definition 2: Addition for A/I

(a + I) + (b + I) = (a + b) + I

Definition 3: Multiplication for A/I

(a + I) * (b + I) = ab + I

Lemma 1: Addition for A/I is well defined

Proof:

(1) Let:

s + I = s' + I

t + I = t' + I

(2) Using Lemma 1, here, it follows that:

s -s' ∈ I

and

t - t' ∈ I

(3) So, there exists a,b such that a, b ∈ I and:

s = s' + a

t = t' + b

(4) s + t = (s' + a) + (t' + b) = s' + a + t' + b

(5) s + t + I = s' + t' + (a + b) + I

(6) Since a ∈ I and b ∈ I, it follows that a + b ∈ I (from Closure)

(7) Using Lemma 2, here, we then have:

(a+b) + I = I

(8) So that:

s + t + I = s' + t' + I

QED

Lemma 2: Multiplication for A/I is well defined

Proof:

(1) Assume that I is an ideal.

(2) Let:

s + I = s' + I t + I = t' + I

(3) Using Lemma 1, here, it follows that:

s -s' ∈ I

and

t - t' ∈ I

(4) There exists a,b such that a, b ∈ I and:

s = s' + a t = t' + b

(5) st = (s' + a)(t' + b) = s't' + at' + s'b + ab

(6) st + I = s't' + at' + s'b + ab + I

(7) Since a,t',s',b ∈ I, we have (see Definition 2, here, and Definition 1, here for details):

at' ∈ I

s'b ∈ I

ab ∈ I

(8) So, at' + s'b + ab + I = I [See Lemma 2, here]

(9) And:

st + I = s't' + I

QED

Lemma 3: If A is a Commutative Ring and I is an Ideal, then A/I is a ring

Proof:

(1) Commutative Rule for Addition

(a + I) + (b + I) = (a + b) + I = (b + a) + I = (b + I) + (a + I)

(2) Associative Rule for Addition

[(a + I) + (b + I)] + (c + I) = (a + b) + I + c + I = (a + b + c) + I = a + I + (b + c) + I = (a + I) + [(b + I) + (c + I)]

(3) Additive Identity

0+I is the additive identity since 0 ∈ A and for all a, (a + I) + (0 + I) = (a + 0) + I = a + I

(4) Additive Inverse

-a+I is the additive inverse since a ∈ A → -a ∈ A and (a + I) + (-a + I) = (a + -a) + I = 0 + I

(5) Associative Rule for Multiplication

[(a + I)*(b+I)](c + I) = (ab + I)(c + I) = (abc + I) = (a + I)(bc + I) = (a+I)[(b+I)(c+I)]

(6) Distributive Rule

(a + I)[(b + I) + (c + I) ] = [(a + I)(b+I)] + [(a+I)(c+I)] = (ab + I) + (ac + I)

QED

Definition 5: Quotient Ring

The ring A/I is called the quotient ring of A by the ideal I.

Example 5.1: Sets that form quotient rings

Z/2Z and Z/3Z are factor rings [See Example 1.1 above for details]

Reference

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Cosets

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

Definition 1: g + H

Let g + H = { g + h such that h ∈ H }.

Example 1.1:

Let G be the set { 0, 1, 2, 3 }

Let H be the set { 9, 10, 11 }

Then:

0 + H = { 9, 10, 11 }

1 + H = { 10, 11, 12 }

2 + H = { 11, 12, 13 }

3 + H = { 12, 13, 14 }


Definition 2: coset of H in G

The set g + H is a coset if and only if there exists a group G such that g ∈ G and H is a subgroup of G.

Note: Technically, definition 3 above describes a left coset. A coset can also be defined as H + g which is called a right coset. The notation of g + H defines a coset based on addition. Cosets can also be defined on multiplication and represented as gH or Hg.

Example 2.1:

Let G = the set of integers Z
Let H = 2Z = the set of even integers

1 ∈ Z
1+H = odd integers = { ... -3, -1, 1, 3, ... }

Example 2.2: Cyclic Group Z₄

Z₄ = { 0, 1, 2, 3}

It is a group since:

(1) Closure

Since Z₄ is always modulo 4, it is clear that that operation of addition is closed (for example: 3 + 2 = 1)

(2) Associativity

For any elements a,b,c ∈ Z₄, (a + b) + c = a + (b + c)

(3) Identity Element

0 is the identity element

(4) Inverse Element

Since it is modulo 4, each element has an inverse: 0+0=0, 1+3=0, 2+2=0

Let H = { 0 , 2 }

H is a subset and H is itself a group since:

(1) It has closure: 0+2=2, 0+0=0, 2+2=0

(2) It has associativity.

(3) It has a identity element: 0

(4) From #1, it is clear that each element is its own inverse.

From Z₄ and H, there are 2 distinct cosets:

0 + H = { 0, 2}
1 + H = { 1, 3}
2 + H = { 2, 0} = 0 + H
3 + H = { 3, 1} = 1 + H

Lemma 1:

For the coset H in G:

For all a,b ∈ G:

a + H = b + H if and only if a - b ∈ H

Proof:

(1) Assume that a + H = b + H

(2) So, for all x ∈ (a + H) → x ∈ (b + H)

(3) a ∈ a + H, b ∈ b + H [since H is a group and therefore 0 ∈ H]

(4) a ∈ b + H [follows directly from step #2]

(5) Let c = a - b

(6) b + c ∈ b + H [since b + c = a and a ∈ b + H]

(7) So c ∈ H [from step #6 and Definition 3 above]

(8) Assume that (a-b) ∈ H

(9) Assume that x ∈ a + H

(10) Let y = x - a

(11) y ∈ H [since x = a + y]

(12) y + (a - b) ∈ H since H is a group

(13) x - b ∈ H [since y + (a - b) = (x - a) + (a - b) = x - b]

(14) Then x ∈ b + H since [b + x-b = x]

(15) We can make the same argument if x ∈ b + H so this shows that a + H = b + H.

QED

Lemma 2:

For the coset H in G:

a ∈ H → a + H = H

Proof:

(1) Assume that a ∈ H

(2) Assume that x ∈ a + H

(3) Then there exists h such that x = a + h where h ∈ H [See Definition 1 above]

(4) But if a ∈ H and h ∈ H, then a + h ∈ H. [since H is a group, see Definition 2 above and the Closure property of groups]

(5) So x ∈ H

(6) Assume that x ∈ H

(7) Let b = x - a

(8) Since a ∈ H, it follows that -a ∈ H [See Definition 2 above and the Inverse property of groups]

(9) Since x ∈ H and -a ∈ H, it follows that b ∈ H [from the Closure property of groups]

(10) So then, x ∈ a + H [since b ∈ H and x = a + b from Definition 1 above]

QED

Reference

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Ideals

The following definitions and lemmas are taken from Jean Tignol's Galois' Theory of Algebraic Equations.

Definition 1: stable under multiplication

a set I is stable under multiplication by the elements in A if and only if:

a ∈ A and x ∈ I ↔ ax ∈ I.

Example 1.1: set that is stable under multiplication

A = {1}

I = {1}

Example 1.2: set that is not stable under multiplication

A= {1,2}

I = {2}

2 ∈ A and 2 ∈ I but 2*2=4 is not in I.

Definition 2: An ideal I

Let A be a commutative ring.

a set I is an ideal if and only if I is a subgroup of the additive group of A which is stable under multiplication by the elements in A (see Definition 1 above).

Example 2.1: Example of a set that is an ideal: 2Z

The set 2Z is the set of even integers.

2Z = { ... -2, 0, 2, 4, 6, ... }

2Z is a subset of the set of integers Z and Z is a commutative ring and a group.

2Z is a group on the operation of addition so it is a subgroup of Z.

2Z is stable under multiplication by elements of Z since an even integer multiplied by any integer is an even integer.

Example 2.2: Example of a set that is not an ideal: 2W

Let 2W be the set of even whole numbers = { 0, 2, 4, ... }

2W is a subset of the set of integers Z which is a commutative ring and a group.

2W is not a group on the operation of addition since there is no inverse element.

2W is not stable under multiplication by the elements of Z since -1 ∈ Z and 2 ∈ 2W but -2 is not in 2W.

Lemma 1:

The set of multiples for a given polynomial is an ideal of the set of all polynomials for a given field

Proof:

(1) Let F[X] be the set of all polynomials in the field F

(2) Let (P) be the set of multiples of polynomials for a given polynomial P so that:

(P) = { PQ where Q ∈ F[X] }

(3) All fields are commutative rings so F[X] is a Commutative Ring. [See Definition 3, here for Fields]

(4) (P) is itself a group since:

(a) Closure on addition

If pq, pq' ∈ (P), then (pq+pq')=p(q+q') ∈ (P) since (q+q') ∈ F[X]

(b) Associativity on Addition

(pq + pq') + pq'' = p([q + q'] + q'') = p(q + [q' + q'']) = pq + (pq' + pq'')

(c) Identity Element

0 = P*0 ∈ (P) since 0 ∈ F[X]

(d) Inverse Element

For all pq, there exists -pq since -pq = p(-q) and -q ∈ F[X] if q ∈ F[X]

(5) Finally, (P) is stable under multiplication since:

(a) Assume pq, pq' ∈ (P)

(b) Then q,q' ∈ F[X]

(c) p ∈ F[X]

(d) So pqq' ∈ F[X] since F[X] is closed on multiplication.

(e) So p*(pqq') ∈ (P)

QED

Reference

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Derivative of Increasing and Decreasing Functions

Lemma: Derivative of Increasing and Decreasing Functions

Let f be a continuous function on (a,b) where the at no point f'(x)=0.

If for all x on [a,b], f(x) is increasing, then f'(x) is positive.

If for all x on [a,b], f(x) is decreasing, then f'(x) is negative.

Proof:

(1) From the definition of derivatives (see Definition 1, here):

f'(x) = lim (Δx → 0) [f(x + Δx) - f(x)]/(Δx)

So, the sign of f'(x) is the sign of [f(x + Δx) - f(x)]/Δx and we can assume that is is nonzero.

(2) Case I: Δx is positive

If f(x) is strictly increasing, then f(x + Δx) - f(x) is positive and f'(x) is positive.

If f(x) is striclty decreasing, then f(x + Δx) - f(x) is negative and f'(x) is negative.

(3) Case II: Δx is negative

If f(x) is strictly increasing, then f(x + Δx) - f(x) is negative and f'(x) is positive

If f(x) is strictly decreasing, then f(x + Δx) - f(x) is positive and f'(x) is negative.

QED

An Inequality Lemma for the Cauchy Bound of Real Roots

The following result is used my proof of Cauchy's Bound for real roots.

Lemma 1: abs(c)ⁿ = abs(cⁿ)

Proof:

(1) Assume that c is nonnegative

(2) Then, cⁿ is nonnegative

(3) Then, abs(cⁿ) = cⁿ

(4) Since abs(c) = c, it follows that: cⁿ = abs(c)ⁿ

(5) Assume that c is negative

(6) We can assume that n is odd

[Otherwise, cⁿ = (-c)ⁿ = abs(c)ⁿ = abs(cⁿ) ]

(8) abs(cⁿ) = -cⁿ = (-1)ⁿ*cⁿ = (-c)ⁿ = abs(c)ⁿ

QED

Lemma 2:

Let:

a_ncⁿ = -a_n-1c^n-1 + .... + -a₀

Then:

abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

Proof:

(1) Using the Triangle Inequality (see Lemma 4, here), we know that:

abs(-a_n-1c^n-1 + .... + -a₀) ≤ abs(-a_n-1c^n-1) + ... + abs(-a₀)

so that:

abs(a_ncⁿ) ≤ abs(-a_n-1c^n-1) + ... + abs(-a₀)

(2) Using a basic property of inequalities (see Lemma 1, here):

abs(a_n)*abs(cⁿ) = abs(a_ncⁿ)

and likewise:

abs(-a_n-1)*abs(c^n-1) = abs(-a_n-1c^n-1)

...

(3) So we have:

abs(a_n)*abs(cⁿ) ≤ abs(-a_n-1)*abs(c^n-1) + ... + abs(-a₀)

(4) Using Lemma 1 above, we have:

abs(a_n)*abs(c)ⁿ ≤ abs(a_n-1)*abs(c)^n-1 + ... + abs(a₀)

QED

Triangle Inequality

Definition 1: Absolute Value

abs(a) = a if a is nonnegative or abs(a)=-a if a is negative.

So for example:

abs(5) = 5

abs(0) = 0

abs(-1) = 1

Now, let's look at some basic properties

Lemma 1: abs(ab) = abs(a)*abs(b)

Proof:

Case I: both a,b positive

abs(ab) = ab = abs(a)*abs(b)

Case II: both a,b negative

abs(ab) = ab = (-a)*(-b) = abs(a)*abs(b)

Case III: one negative, one positive

Assume a is positive, b is negative (since a,b are symmetrical, we can switch them as necessary)

abs(ab) = -ab = a*(-b) = abs(a)*abs(b)

QED

Lemma 2: -abs(a) ≤ a ≤ abs(a)

Proof:

Case I: a is nonnegative

-a ≤ a ≤ a

so

-abs(a) ≤ a ≤ abs(a)

Case II: a is negative

a ≤ a ≤ -a

so

-abs(a) ≤ a ≤ abs(a)

QED

Lemma 3: abs(a) ≤ b if and only if -b ≤ a and a ≤ b.

Proof:

(1) Assume abs(a) ≤ b

Case I: a is nonnegative

abs(a) = a

Since abs(a) ≤ b, it follows that a ≤ b and b is nonnegative

Since b is nonnegative and a is nonnegative, then it -b ≤ a.

Case II: a is negative

Since abs(a) ≤ b, it follows that -a ≤ b which is the same as -b ≤ a and therefore b must be nonnegative.

Since b is nonnegative, it follows that a ≤ b.

(2) Assume that -b ≤ a and a ≤ b.

Case I: a is nonnegative

Since a ≤ b, it follows that b is nonnegative

So abs(a) ≤ b.

Case II: a is negative

Since -b ≤ a, it follows that b ≥ -a.

Since a is negative, -a is positive, and we have:

abs(a) ≤ b.

QED

Lemma 4: Triangle Inequality

For all real numbers a,b

abs(a + b) ≤ abs(a) + abs(b)

Proof:

(1) For all real numbers a,b (from Lemma 1 above)

-abs(a) ≤ a ≤ abs(a)

-abs(b) ≤ b ≤ abs(b)

(2) Adding these two conditions together gives us:

-[abs(a) + abs(b)] ≤ a + b ≤ abs(a) + abs(b)

(3) Let c = a+b and d =abs(a) + abs(b)

(4) Using Lemma 3, we know that:

abs(c) ≤ d if and only if -d ≤ c and c ≤ d.

(5) But using step #2, we know that:

-d = -[abs(a) + abs(b)] ≤ c = a + b

and

c = a + b ≤ d = abs(a) + abs(b)

(6) So, using step #4 we get:

abs(c) ≤ d

which is equivalent to:

abs(a + b) ≤ abs(a) + abs(b)

QED

Polynomials are continuous

For a definition of polynomials, see Definition 1, here. For a definition of continuous functions, see Definition 1, here.

Lemma 1: f(x)=x is continuous

Proof:

(1) Let ε be any arbitrary value.

(2) Let δ = ε

(3) For any point c, it is clear that if x lies in (c - δ, c + δ), then f(x)=x lies in (f(c) - ε, f(c) + ε )

QED

Corollary 1.1 : Polynomials are continuous

Proof:

(1) The function f(x)=x is continuous. [See Lemma 1 above]

(2) Since the product of continuous functions is continuous [See Lemma 3, here], then f(x)=xⁿ where n is a positive integer is also continuous.

(3) Since f(x)=C is continuous [See Lemma 1, here], it follows that any function of the form cxⁿ is also continuous.

(4) Since the addition of continuous functions is continuous [See Lemma 2, here], it follows that any polynomial function is continuous since it consists of the form:

f(x) = c₀ + c₁x + c₂x² + ... + c_nxⁿ

where each c_i is a constant.

QED

Lemma 2: The Derivative of a polynomial is itself a polynomial

Proof

(1) The derivative of each term of a polynomial is itself a term of a polynomial [See the Lemma 2, here]

(2) So, it follows that the derivative itself is also a polynomial. [See Definition 1, here]

QED

Corollary 2.1: The derivative of a polynomial is a continuous function.

Proof:

This follows directly from Lemma 2 above and Corollary 1.1 above.

QED

Interval of a Function with Simple Roots

Lemma: Interval of a Function with Simple Roots

Let f be a function with simple roots such that f(c)=0

Then there exists an interval (a,b) such that:

c is in (a,b)

for all x in (a,b), f'(x) is all positive or all negative

Proof:

(1) Since f has only simple roots and f(c)=0, then it follows that f'(c) ≠ 0. [See Corollary 1.1, here]

(2) Since f is a polynomial, we know that f'(x) is continuous. [See Corollary 2.1, here]

(3) Since f'(c) is nonzero, let ε be nonzero and less than abs{ f'(c) }.

(4) Since f'(x) is continuous at c, there exists a number δ such that if x is in the (c - δ, c + δ), then f'(x) is in (f'(c)-ε, f'(c)+ε). [By the definition of a continuous function]

(5) Since ε is less than abs{f'(c) }, it follows that for x in (c -δ, c + δ), f'(x) is either entirely positive or entirely negative.

QED

Greatest Common Divisor of a Polynomial and its First Derivative

Lemma 1:

Let a be a root of a polynomial P.

Then:

a is a multiple root of P if and only if a is also a root of P' (the first derivative of P)

Proof:

(1) Since a is a root of P, there exists a polynomial Q such that (see Theorem, here):

P = (x - a)Q

(2) Using the Product Rule of Derivatives (see Lemma 4, here), we know that:

P' = Q + (x-a)Q'

(3) But then (x-a) only divides P' if and only if it also divides Q.

QED

Corollary 1.1:

If a polynomial has only simple roots

Then:

Its first derivative does not share any of those roots.

Proof

(1) Assume that a polynomial P has only simple roots.

(2) Assume that a root a divides both P and P'

(3) Then by Lemma 1 above, a is a multiple root of P.

(4) But by step #1 this is impossible so we reject our assumption in step #2.

QED

Lemma 2:

If a polynomial P has only simple roots

Then P,P' are relatively prime.

Proof:

(1) Assume that P,P' are not relatively prime.

(2) Then, they have a common irreducible factor of degree 1.

[Since by definition, two polynomials are relatively prime if their only common factor is of degree 0]

(3) Then there exists a polynomial of the form X-a that divides both P and P' (See Thereom, here)

(4) Then from Lemma 1 above, a is a multiple root of P

(5) But this is impossible, so we reject our assumption in step #1.

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Alternate Form of the Greatest Common Divisor Algorithm for Polynomials

The usual form of the Greatest Common Divisor for Polynomials uses a series of steps of the form (see the proof for the usual form, here):

(a) R₁ = Q₃R₂ + R₃

(b) R₂ = Q₄R₃ + R₄

...

(c) R_n-2 = Q_nR_n-1 + R_n

(d) R_n-1 = Q_n+1R_n + R_n+1

But for Sturm's Theorem, I need to use an alternate form.

(a) R₁ = Q₃R₂ - R₃

(b) R₂ = Q₄R₃ - R₄

...

(c) R_n-2 = Q_nR_n-1 - R_n

(d) R_n-1 = Q_n+1R_n - R_n+1

Definition 1: Divisor for Polynomials

Let P₁, P₂ ∈ F[X].

We say that P₂ divides P₁ if there exists Q ∈ F[X] such that P₁ = P₂Q

Definition 2: GCD for Polynomials

A greatest common divisor (GCD) of P₁, P₂ is a polynomial D ∈ F[X] which has the following properties:

(a) D divides P₁ and P₂
(b) If S is a polynomial which divides P₁ and P₂, then S divides D.

Definition 3: Relatively prime polynomials

If 1 is the GCD for polynomials P₁, P₂, then P₁, P₂ are said to relatively prime polynomials.

Definition 4: degree: deg

The deg of a polynomial P is the greatest integer n for which the coefficient Xⁿ in the expression of P is not zero.

Theorem 1: Alternate Form of Euclid's Algorithm for Greatest Common Divisor for Polynomials

For any two polynomials P₁, P₂, there exists a GCD

Proof:

(1) Let P₁, P₂ be any two polynomials such that deg P₁ ≥ deg P₂

(2) If P₂ = 0, then P₁ is the GCD of P₁, P₂ [See Definition 2 above]

(3) Otherwise, we divide P₁ by P₂ using the the alternate form of Euclidean Division Algorithm for Polynomials. [See Theorem, here]

(4) Then there exists two polynomials Q₁, R₁ such that:

P₁ = Q₁P₂ - R₁

and deg R₁ is less than deg P₂.

(5) If R₁ = 0, then P₂ is the GCD of P₁, P₂

(6) Next, we divide P₂ by R₁ to get:

P₂ = Q₂R₁ - R₂

and deg R₂ is less than deg R₁

(7) If R₂ ≠ 0, then we can set up the following equations:

(a) R₁ = Q₃R₂ - R₃

(b) R₂ = Q₄R₃ - R₄

...

(c) R_n-2 = Q_nR_n-1 - R_n

(d) R_n-1 = Q_n+1R_n - R_n+1

(8) Since deg P₂ is greater than deg R₁ which is greater than deg R₂ which is greater than ... deg R_n which is greater deg R_n+1, this sequence cannot extend indefinitely.

(9) Therefore, R_n+1 = 0 for some n.

(10) R_n divides P₁, P₂ since:

Because R_n+1=0, R_n divides R_n-1

Because R_n divides R_n-1, from equation 7c, R_n divides R_n+1

We can now proceed up each of these implied equations in the same way until we get to 7b.

Since we have shown that R_n divides R₂ and R₃ before it, it is clear from 7a, that R_n divides R₁

It is clear from step #6 that R_n divides P₂ and clear from step #4 that R_n divides P₁

(11) Assume that P₁ and P₂ are both divisible by a polynomial S.

(12) Then by step #4, S must divide R₁.

(13) By step #6, S must divide R₂

(14) We can now use the same argument to go through the equations in step #7 to conclude that S must likewise divide R_n.

(15) This proves that R_n is the GCD for P₁,P₂ [See Definition 2 above]

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

Ring of Polynomials

If you are not comfortable with the idea of rings, start here.

Definition 1: Polynomial in one indeterminate with coefficients in a ring A

P : N → A such that P = { n ∈ N : P_n ≠ 0 }

where N is the set of natural numbers (that is, 0, 1, 2, ... )

As a convention, this mapping is usually represented in the form:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

where n ∈ N.

Example 1:

5x² + 3x + 2 is a polynomial.

5,3,2 are all integers which is a ring (see here for details on integers)

{ 2 → 5, 1 → 3, 0 → 2 }

Definition 2: Polynomial Addition

(P + Q)_n = P_n + Q_n

Example 2:

(5x² + 3x + 2) + (3x² + x + 5) = (5 + 3)x² + (3+1)x + (2+5) = 8x² + 4x + 7

Definition 3: Polynomial Multiplication

(PQ)_n = ∑(i+j=n) P_i*Q_j

Example 3:

(5x² + 3x + 2)(3x² + x + 5) = (5*3)x⁽²⁺²⁾ + (5*1 + 3*3)x⁽²⁺¹⁾ + (5*5 + 3*1 + 2*3)x⁽²⁺⁰⁾ + (3*5 + 2*1)x⁽¹⁺⁰⁾ + (2*5)x⁰

Definition 4: A[X]

The set of all polynomials with coefficients in A

Example 4:

5x² + 3x + 2 ∈ Z[X] where Z is the set of all integers.

Lemma 1:

If A is a ring, then A[X] is a ring. If A is a commutative ring, then A[X] is a commutative ring.

Proof:

(1) I will show that A[X] has all the properties of a ring.

(2) Commutative Property for Addition:

P_n + Q_n = (P + Q)_n = (Q + P)_n = Q_n + P_n

(3) Associative Property for Addition

(P_n + Q_n) + R_n = (P + Q)_n + R_n = ([P + Q] + R)_n = (P + [Q + R])_n

= P_n + (Q + R)_n = P_n + (Q_n + R_n)

(4) Additive Identity

This is the 0 polynomial. P_n + 0 = (P + 0)_n = P_n

(5) Additive Inverse

P_n + -P_n = (P + -P)_n = 0

(6) Associative Property for Multiplication

∑(i+j+k=n) (P_i*Q_j)*R_k = [(P*Q)*R]_n = [P*(Q*R)]_n = ∑ (i+j+k=n)P_i*(Q_j*R_k)

(7) Distributive Property for Multiplication

∑(i+j=n) P_i(Q_j + R_j) = ∑(i+j=n)P_i(Q + R)_j = [P(Q+R)]_n
= (PQ + PR)_n = ∑(i+j=n)(P_iQ_j) + ∑(i+j=n)(P_iR_j)

We can use the same argument to prove:

∑(i+j=n) (Q_j + R_j)P_i = ∑(i+j=n)(Q_jP_i) + ∑(i+j=n)(R_jP_i)

(8) Commutative Property for Multiplication is true if A has the Commutative Property for Multiplication

Assume that A is commutative.

∑(i+j=n)P_iQ_j = (PQ)_n = (QP)_n = ∑(i+j=n)Q_jP_i

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001