Saturday, January 31, 2009

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

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) R1 = Q3R2 + R3

(b) R2 = Q4R3 + R4

...

(c) Rn-2 = QnRn-1 + Rn

(d) Rn-1 = Qn+1Rn + Rn+1

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

(a) R1 = Q3R2 - R3

(b) R2 = Q4R3 - R4

...

(c) Rn-2 = QnRn-1 - Rn

(d) Rn-1 = Qn+1Rn - Rn+1

Definition 1: Divisor for Polynomials


Let P1, P2 ∈ F[X].

We say that P2 divides P1 if there exists Q ∈ F[X] such that P1 = P2Q

Definition 2: GCD for Polynomials

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

(a) D divides P1 and P2
(b) If S is a polynomial which divides P1 and P2, then S divides D.

Definition 3: Relatively prime polynomials

If 1 is the GCD for polynomials P1, P2, then P1, P2 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 Xn 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 P1, P2, there exists a GCD

Proof:

(1) Let P1, P2 be any two polynomials such that deg P1 ≥ deg P2

(2) If P2 = 0, then P1 is the GCD of P1, P2 [See Definition 2 above]

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

(4) Then there exists two polynomials Q1, R1 such that:

P1 = Q1P2 - R1

and deg R1 is less than deg P2.

(5) If R1 = 0, then P2 is the GCD of P1, P2

(6) Next, we divide P2 by R1 to get:

P2 = Q2R1 - R2

and deg R2 is less than deg R1

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

(a) R1 = Q3R2 - R3

(b) R2 = Q4R3 - R4

...

(c) Rn-2 = QnRn-1 - Rn

(d) Rn-1 = Qn+1Rn - Rn+1

(8) Since deg P2 is greater than deg R1 which is greater than deg R2 which is greater than ... deg Rn which is greater deg Rn+1, this sequence cannot extend indefinitely.

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

(10) Rn divides P1, P2 since:

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

Because Rn divides Rn-1, from equation 7c, Rn divides Rn+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 Rn divides R2 and R3 before it, it is clear from 7a, that Rn divides R1

It is clear from step #6 that Rn divides P2 and clear from step #4 that Rn divides P1

(11) Assume that P1 and P2 are both divisible by a polynomial S.

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

(13) By step #6, S must divide R2

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

(15) This proves that Rn is the GCD for P1,P2 [See Definition 2 above]

QED

References

Thursday, January 29, 2009

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 : Pn ≠ 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:

anxn + an-1xn-1 + ... + a1x + a0

where n ∈ N.

Example 1:

5x2 + 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 = Pn + Qn

Example 2:

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

Definition 3: Polynomial Multiplication

(PQ)n = ∑(i+j=n) Pi*Qj

Example 3:

(5x2 + 3x + 2)(3x2 + x + 5) = (5*3)x(2+2) + (5*1 + 3*3)x(2+1) + (5*5 + 3*1 + 2*3)x(2+0) + (3*5 + 2*1)x(1+0) + (2*5)x0

Definition 4: A[X]

The set of all polynomials with coefficients in A

Example 4:

5x2 + 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:

Pn + Qn = (P + Q)n = (Q + P)n = Qn + Pn

(3) Associative Property for Addition

(Pn + Qn) + Rn = (P + Q)n + Rn = ([P + Q] + R)n = (P + [Q + R])n

= Pn + (Q + R)n = Pn + (Qn + Rn)

(4) Additive Identity

This is the 0 polynomial. Pn + 0 = (P + 0)n = Pn

(5) Additive Inverse

Pn + -Pn = (P + -P)n = 0

(6) Associative Property for Multiplication

∑(i+j+k=n) (Pi*Qj)*Rk = [(P*Q)*R]n = [P*(Q*R)]n = ∑ (i+j+k=n)Pi*(Qj*Rk)

(7) Distributive Property for Multiplication

∑(i+j=n) Pi(Qj + Rj) = ∑(i+j=n)Pi(Q + R)j = [P(Q+R)]n
= (PQ + PR)
n = ∑(i+j=n)(PiQj) + ∑(i+j=n)(PiRj)

We can use the same argument to prove:

∑(i+j=n) (Qj + Rj)Pi = ∑(i+j=n)(QjPi) + ∑(i+j=n)(RjPi)

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

Assume that A is commutative.

∑(i+j=n)PiQj = (PQ)n = (QP)n = ∑(i+j=n)QjPi

QED

References

Degree of a Polynomial

Definition 1: Degree of a polynomial

The highest nonzero exponent is the degree of the polynomial.

As a convention, the degree of a zero polynomial is said to be -∞.

Lemma 1: deg(A+B) ≤ max(degA,degB)

Proof:

(1) We start with with deg A = 0, deg B=0 where A ≠ -B [We can ignore deg = - ∞ since by the Additive Identity Property (see here), it is true]

(2) A+B ≠ 0, so deg(A+B) = 0

(3) Assume that this is true up to deg A, deg B ≤ n-1.

(4) Let:

A = anxn + ... + a0

B = bnxn-1 + ... + b0

(5) We can assume that an ≠ -bn [Since if this is the case, the n degrees cancels out and the proposition is true by the inductive hypothesis.]

(6) an + bn = (a+b)n [See here for Additive Rule for Polynomials]

(7) So the deg(A+B) = n

QED

Lemma 2: deg(AB) = deg(A) + deg(B)

Proof:

(1) Assume deg A = 0, deg B = 0

(2) Then deg(AB) = 0 = 0 + 0

(3) Assume that the proposition is true up to n-1

(4) Let:

A = anxn + ... + a0

B = bnxn-1 + ... + b0

(5) The highest exponent will be an*bn = (a*b)n+n

(6) deg(a*b)n+n = 2n = deg(a) + deg(b)

QED

References

Alternate Form of the Division Algorithm for Polynomials

Theorem: Alternative Form of the Division Algorithm for Polynomials

Let F be a field

Let f(x),g(x) be polynomials of F[x] where g(x) ≠ 0

Then:

There exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) - r(x) and r(x)=0 or deg r(x) is less than deg g(x)

Proof:

(1) Let f(x),g(x) be two polynomials such that g(x) ≠ 0

(2) We can assume that deg f(x) ≥ deg g(x) since:

if deg f(x) = 0, then f(x) = g(x)(0) - 0.

if deg f(x) is less than deg g(x), then f(x) = g(x)(0) - [-f(x)]

(3) Let:

f(x) = anxn + ... + a0

g(x) = bmxm + ... + b0

where an and bm are nonzero.

[We can make this assumption since g(x) ≠ 0 and deg f(x) ≥ deg g(x).]

(4) I will use induction to establish the existence of q(x), r(x).

(5) q(x),r(x) exist if deg f(x) = 0 since:

(a) Assume deg f(x) = 0

(b) Then there exists C such that f(x)=C

(c) Since deg f(x) ≥ deg g(x), it follows that deg g(x)= 0 and there exists D such that g(x)=D

(d) Let q(x) = C/D

(e) Then it follows that f(x) = g(x)*q(x) - 0

(6) Assume that our assumption holds true up to deg f(x) = n-1

(7) Let:

f1(x) = f(x) - anbm-1xn-mg(x)

(8) So, deg f1(x) is less than deg f(x)

(9) By the induction hypothesis, there exists q1(x) and r1(x) such that:

f1(x) = q1(x)g(x) - r1(x)

where deg r1 is less than deg g(x) or deg r1(x) = 0

(10) So, then:

f1(x) + anbm-1xn-mg(x) = anbm-1xn-mg(x) + q1(x)g(x) - r1(x)

= [anbm-1xn-m + q1(x)]g(x) - r1(x)

where deg r1 is less than deg g(x) or deg r1(x) = 0

(11) This proves the first part of the theorem. To complete it, we need to prove uniqueness.

(12) Assume that:

f(x) = g(x)q(x) - r(x) = g(x)q'(x) - r'(x)

where deg r(x), deg r'(x) = 0 or is less then deg g(x)

(13) So that:

0 = g(x)q(x) - r(x) - g(x)q'(x) + r'(x)

(14) Then:

r(x) - r'(x) = g(x)[q(x) - q'(x)]

(15) Assume that q(x) - q'(x) is nonzero.

(16) Then, deg g(x)[q(x)-q'(x)] = deg g(x) + deg (q(x) - q'(x)) [See Lemma 2, here]

(17) And, deg(r(x) - r'(x)) ≤ max(deg r(x),deg r'(x)) [See Lemma 1, here]

(18) But this is impossible since deg(r(x)) is less than deg g(x)

(19) So, we have a contradiction and we reject our assumption in step #15.

(20) So, if q(x) - q'(x) is 0, then it follows that r(x) - r'(x) is also 0.

(21) Then q(x) = q'(x) and r(x) = r'(x)

QED

Reference

Wednesday, January 28, 2009

Inequality lemmas

Lemma 1: abs(a/b) ≤ 1 if and only if abs(a) ≤ abs(b)

Proof:

Case I: a,b are both positive

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) a ≤ b

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) a ≤ b

(7) a/b ≤ 1

(8) abs(a/b) ≤ 1

Case II: a,b are both negative

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) -a ≤ -b [since -b is positive]

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ -b

(7) a/b ≤ 1 [since -b is positive]

(8) abs(a/b) ≤ 1

Case III: Only b is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) (a/b) ≤ -1

(4) a ≤ -b [since b is negative and -b is positive]

(5) abs(a) ≤ abs(b) [ since abs(b) = -b ]

(6) Assume abs(a) ≤ abs(b)

(7) a ≤ -b

(8) a/b ≥ -1 [since b is negative]

(9) -(a/b) ≤ 1

(10) abs(a/b) ≤ 1

Case IV: Only a is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) -a ≤ b [since b is positive]

(4) abs(a) ≤ abs(b) [since abs(a) = -a and abs(b) = b]

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ b

(7) -a/b ≤ 1

(8) abs(a/b) ≤ 1

QED

Corollary 1.1: abs(a) is greater than abs(b) if and only if abs(a/b) greater than 1

Proof:

(1) Assume that abs(a) is greater than abs(b)

(2) Assume that abs(a/b) is not greater than 1

(3) Then abs(a/b) ≤ 1

(4) Then abs(a) ≤ abs(b) [From Lemma 1 above]

(5) But this contradicts step #1 so we reject our assumption in step #2.

(6) Assume that abs(a/b) is greater than 1.

(7) Assume that abs(a) is not greater than abs(b)

(8) Then abs(a) ≤ abs(b)

(9) Then abs(a/b) ≤ 1 [From Lemma 1 above]

(10) But this contradicts step #6 so we reject our assumption in step #7.

QED

Lemma 2:

if a,b,q are integers such that abs(a/b - q) is less than 1

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a/b - q) is greater than (1/2) [Otherwise, set c = q and we are done]

(2) if (a/b - q) is less than -1/2, then [a/b - (q-1)] is less than 1/2 and [a/b - (q-1)] is greater than 0

(3) if (a/b - q) is greater than 1/2, then [a/b - (q+1)] is greater than -1/2 and [a/b - (q+1)] is less than 0

QED

Corollary 2.1:

Let a,b be integers

if abs(a) abs(b)

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a) ≤ abs(b)

(2) Then abs(a/b) ≤ 1. [See Lemma 1 above]

(3) If (a/b) = 0, then c = 0 and the conclusion follows.

(4) if (a/b) ≥ -1, then abs(a/b + 1) is less than 1.

(5) if (a/b) ≤ 1, then abs(a/b - 1) is greater than -1.

(6) So, the conclusion follows from Lemma 2 above.

QED