Saturday, December 08, 2007

Irreducible Polynomials

Definition 1: Irreducible Polynomials

A polynomial P ∈ F[X] is irreducible in F[X] if deg P is greater than 0 and P is not divisible by any polynomial Q ∈ F[X] such that 0 is less than deg Q is less than deg P.

NOTE: See Definition 1, here, for definition of polynomials and Definition 4, here, for definition of deg of a polynomial.

Lemma 1:

If a polynomial D divides an irreducible polynomial P,

Then, either D is a constant or deg D = deg P.

Proof:

(1) Let P be an irreducible polynomial

(2) Let D be a polynomial that divides P.

(3) Assume that D is not a constant and that deg D is less than deg P.

(4) Then D cannot divide P [by Definition 1 above]

(5) So we have a contradiction and we must reject our assumption at step #3.

QED

Corollary 1.1: Every polynomial of degree 1 is irreducible

(1) Assume that there exists a polynomial D of degree 1 that is not irreducible.

(2) Then there exists a polynomial P that divides D where deg P is less than deg D and deg P is greater than 0.

(3) But this is impossible since deg D = 1 (either deg P = 0 or deg P ≥ 1).

(4) So we reject our assumption at step #1.

QED

Theorem 2: Euclid's Lemma for Polynomials

For polynomials S,T,U if S divides TU and S is relatively prime to T, then S divides U.

Proof:

(1) Since GCD(S,T)=1, there exists polynomials V,W such that [See Corollary 3.1, here]:

SV + TW = 1

(2) Multiplying both sides by U gives us:

S(UV) + (TU)W = U

(3) This proves that S divides U since S divides TU.

QED

Corollary 2.1: Generalized Euclid's Lemma for Polynomials

If a polynomial S divides a product of r factors and is relatively prime to the first r-1 factors, then it divides the last one.

Proof:

(1) Let T = the first r-1 factors.

(2) Let U = the last factor

(3) Then S divides TU and GCD(S,T)=1 so using Theorem 2 above, we can conclude that S divides U.

QED

Corollary 2.2: If a polynomial is divisible by pairwise relatively prime polynomials, then it is divisible by their product

Proof:

(1) Let P1, ..., Pr be relatively prime polynomials which divide a polynomial P.

(2) For r=1, P1 = P so the corollary is true.

(3) Assume that it is true up to r-1.

(4) So, then we have:

P = P1*..*Pr-1*Q

(5) By Corollary 2.1 above, since Pr divides P, it follows that Pr must divide Q.

(6) So, then it follows that P1...*...*Pr must divide P.

QED

Theorem 3: Every non constant polynomial P ∈ F[X] is a finite product:

P = cP1P2...Pn

where c ∈ Fx and P1, P2, ..., Pn are monic irreducible polynomials where this factorization is unique. Order of these polynomials is not unique and there may include repeats of the same polynomial more than once.

Proof:

(1) If P is irreducible, then P = c*P1 where c is the leading coefficient of P and P1 = c-1P is irreducible and monic. [See Definition 1 above and Theorem 2, here]

(2) If P is reducible, then it can be written as a product of two polynomials of degree less than deg P.

(3) If the two polynomials less than P are irreducible, then we are done. If not, then we can continue to break each reducible polynomial into a product of reducible polynomials and then using step #1, we break this product into the desired result.

(4) The next step is to prove that this product independent of order is unique.

(5) Assume that:

P = cP1*...*Pn = dQ1*...*Qm

where c,d ∈ Fx and P1, ..., Pn, Q1, ..., Qm are irreducible polynomials.

(6) c = d since both equal the leading coefficient of P.

(7) So, we have:

P1*...*Pn = Q1*...*Qm

(8) Using Corollary 2.1 above, we know that P1 cannot be relatively prime to all Qi

(9) So, let's assume that there exists a Qi such that GCD(P1,Qi) ≠ 1. Let's label it Q1

(10) Let D be the unique monic GCD of P1,Q1. [See Theorem 2, here]

(11) Since P1 is irreducible, then P1 = cD for some c.

(12) Since P1 is monic, then c = 1 and P1 = D.

(13) Since Q1 is monic and irreducible, we can use the same argument as in steps #11 and steps #12 to establish that Q1 = D.

(14) Therefore, it follows that Q1 = P1

(15) We can make the same argument for all n elements of Pi so that we have P2 = Q2, P3 = Q3, ..., Pn = Qn

(16) Since there must be a matched element for each Pi, it follows that n ≤ m.

(17) But we can also make the same line of argument for Qj so that we also know that m ≤ n

(18) Therefore n = m.

QED

References

Friday, December 07, 2007

Greatest Common Divisor for Polynomials

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

Two polynomials P1, P2, then P1, P2 are said to relatively prime polynomials if the only factors they have in common are of degree 0.

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

Definition 5: monic polynomial

A polynomial is monic if and only if its leading coefficient is 1.

Theorem 2:

Any two polynomials P1, P2 ∈ F[X] which are not both 0 have a unique monic greatest common divisor D1 and a polynomial D ∈ F[X] is a greatest common divisor of P1, P2 if and only if D=cD1 for some c ∈ Fx (= F - {0}).

Proof:

(1) Let P1 ∈ F[X] be polynomials such that deg P1 is greater than deg P2

(2) Using Theorem 1 above, we know that there exists Rn such that Rn is the GCD of P1, P2

(3) Dividing Rn by its leading coefficient gives us a monic GCD of P1,P2

(4) Assume that D, D' are GCD's of P1, P2

(5) Then D divides D' and D' divides D. [See Definition 2 above]

(6) Then there exists polynomials Q,Q' ∈ F[X] such that:

D' = DQ
D = D'Q'

(7) So that:

Q = D'/D
Q' = D/D'

QQ' = (D'/D)(D/D') = 1

(8) But since Q'Q=1, they must both be constants which are inverses of each other.

(9) So, if D and D' are monic, then Q=Q'=1 and D=D' [Otherwise if Q ≠ 1, then D'=DQ would imply that D' is not be monic]

(10) Suppose D is any GCD of P1, P2

(11) Let D' be the unique monic GCD of P1, P2

(12) Let a = the leading coefficient of D.

(13) It is clear that (1/a)D = D' since the monic GCD is unique [see Step #9 above]

QED

Theorem 3:

If D is the GCD of P1, P2, then there exists polynomials U1, U2 such that:

D = P1U1 + P2U2 where U1, U2 ∈ F[X]

Proof #1:

(1) Using step #7c from Theorem 1 above, we have:

Rn-2 = QnRn-1 + Rn

which gives us:

Rn = Rn-2 - QnRn-1

and likewise:

Rn-1 = Rn-3 - Qn-1Rn-2

(2) We can then use the same type of equation to resolve Rn-1 to get:

Rn = Rn-2 - Qn(Rn-3 - Qn-1Rn-2) =

= Rn-2 - QnRn-3 + QnQn-1Rn-2 =

= -Rn-3Qn + Rn-2(1 +QnQn-1)

(3) We've now put Rn in terms of Rn-3 and Rn-2

(4) In this way, we can eliminate each Ri in terms of Ri-1 and Ri-2 up until we resolve R1 into P1, P2

(5) Eventually we get to an expression of Rn such that:

Rn = P1U1 + P2U2

QED

Proof #2:

(1) From step #4 of Theorem 1 above, we have:

P1 = Q1P2 + R1

(2) Using Matrix Theory (see here for review of 2 x 2 matrices), this gives us:



(3) From step #6 of Theorem 1 above we have:

P2 = Q2R1 + R2

which gives us:



(4) We can continue this approach until step #7d:

Rn-1 = Qn+1Rn + Rn+1

which gives us:



(5) Combining the matrix equations gives us:



(6) Now, since we know that:





(7) We see that each:



is invertible (see here for review of invertibility of matrices).

(8) We can then rearrange the equation in step #5 to be:



(9) Now, we can define U1, U2, U3, U4 such that:



(10) It now follows that:



(11) This then gives us that:

U1*P1 + U2*P2 = Rn

and

U3*P1 + U4*P2 = 0

QED

Corollary 3.1:

If P1, P2 are relatively prime polynomials in F[X], then there exists polynomials U1, U2 such that:

P1U1 + P2U2 = 1

Proof:

Since for relatively prime polynomials GCD = 1, this result follows directly from Theorem 3 above.

QED

References

Tuesday, December 04, 2007

Polynomials defined

A polynomial expression is a mathematical construct that if often used and rarely defined. The most common form is a polynomial in one variable which can be represented as:
a0xn + a1xn-1 + ... + a(n-1)x + an

In today's blog, I will present a more formal definition and then show the very fundamental result that a polynomial is a ring. If you are not familiar with rings, then please start here.

The content in today's blog is taken from Jean Tignol's excellent Galois' Theory of Algebraic Equations.

Definition 1: Polynomial in one indeterminant with coefficients in ring A

P: N → A such that { n ∈ N : Pn ≠ 0 } is finite. The set of all polynomials in one indeterminant with coefficients in ring A can be denoted as A[X].

Example 1:

Let us consider the polynomial:

a0 + a1X + ... + anXn

In this case, each ai is a coefficient in ring A.

We can see that for each i, that i ∈ N and that there exists an integer n ∈ N such that:

if i ≤ n, then i ∈ N maps to ai.

if i is greater than n, then i ∈ N maps to 0.

Definition 2: Addition of Polynomials

(P + Q)n = Pn + Qn

In other words, each of the maps corresponding to the same natural number are added together to form a new map.

Definition 3: Multiplication of Polynomials

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

In other words, each of the maps corresponding to the multiplication of all maps where the index of one plus the index of the other = n.

Lemma 1: If A is a ring, then A[X] is a ring which is commutative if and only if A is commutative

Proof:

(1) A[X] is a ring since:

(a) A[X] has a commutative operation of addition

P + Q = Pi + Qi for all i.

Q + P = Qi + Pi for all i.

Since A is a ring, Pi + Qi = Qi + Pi

(b) A[X] has an associative rule for addition

(P + Q) + R = (Pi + Qi) + Ri for all i

P + (Q + R) = Pi + (Qi + Ri) for all i

(Pi + Qi) + Ri = Pi + (Qi + Ri) since A is a ring.

(c) A[X] has an additive identity

Let Q be a polynomial such that all Qi map to 0.

Then for any polynomial P, it is clear that P + Q = Pi + 0 = Pi for all i.

(d) A[X] has an additive inverse

For any polynomial P:

Let Q be a polynomial derived from P such that for all i: Qi = -Pi

Then

P + Q = Pi + -Pi = 0 for all i.

(e) A[X] has an associative rule for multiplication

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

(PQ)R = ∑ (i+j+k=n) (Pi*Qj)Rk for all n =

= ∑ (i+j+k=n) Pi*(QjRk) for all n

QR = (j+k=n) Qj*Rk for all n

P(QR) = ∑ (i+j+k=n) Pi*(QjRk) for all n

(f) A[X] has a distributive rule

Q + R = Qj + Rj for all j

P(Q+R) = ∑ (i+j=n) Pi*(Qj + Rj) =

= ∑ (i+j=n) PiQj + PiRj

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

PR = ∑ (i+j=n) Pi*Rj for all n.

PQ + PR = ∑ (i+j=n) PiQj + ∑(i + j=n) PiRj for all n =

= ∑(i+j=n) PiQj + PiRj

(Q+R)P = ∑ (i+j=n) (Qj + Rj)*Pi =

= ∑ (i+j=n) PiQj + PiRj

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

(a) Assume that A is a commutative ring

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

= ∑ (i+j=n) Qj*Pi for all n = QP

(3) If A[X] is a commutative ring, then A is a commutative ring

(a) Assume that A[X] is a commutative ring

(b) QP = PQ = ∑ (i+j=n) Pi*Qj for all n

(c) QP = ∑ (i+j=n) Qj*Pi for all n

(d) So, therefore for all n, ∑ (i+j=n) Pi*Qj = ∑ (i+j=n) Qj*Pi

QED

References

Breakdown of rational fractions as sums of partial fractions

Lemma 1: Rational fraction as sum of relatively prime polynomials

If P,Q,S1,S2 are polynomials such that:

Q = S1S2

S1,S2 are relatively prime polynomials

Then, there exists polynomials P0, P1, P2 such that:

P/Q = P0 + P1/S1 + P2/S2

deg Pi is less than deg Si for both i=1 and i=2

Proof:

(1) Since GCD(S1,S2) = 1, there exists polynomials T1, T2 such that [See Corollary 3.1, here]:

1 = S1T1 + S2T2

(2) Multiply each side by P/Q to get:

P/Q = (PS1T1)/Q + (PS2T2)/Q

(3) Since Q=S1S2, we now have:

P/Q = (PS1T1)/(S1S2) + (PS2T2)/(S1S2) = (PT1)/S2 + (PT2)/S1

(4) By the Euclidean Division Algorithm for Polynomials (see Theorem, here), there exists U1, U2, R1, R2 such that:

PT1 = S2U2 + R2

where deg R2 is less than deg S2

PT2 = S1U1 + R1

where deg R1 is less than deg S1

(5) Replacing PT1 and PT2 in step #3 gives us:

P/Q = (S2U2 + R2)/S2 + (S1U1 + R1)/S1 =

= (S2U2)/S2 + R2/S2 + (S1U1)/S1 + R1/S1 =

= (U2 + U1) + R1/S1 + R2/S2

QED

Lemma 2:

For polynomials Q,P:

If Q is irreducible and deg P is less than deg Qm, then:

P/Qm = P1/Q + P2/Q2 + ... + Pm/Qm

where deg Pi is less than deg Q for i = 1, ..., m

Proof:

(1) Using Euclidean Division for Polynomials (see Theorem, here), there exists P1,R1 such that:

P = P1Qm-1 + R1 where deg R1 is less than deg Qm-1

(2) deg P1 is less than deg Q since:

(a) Assume deg P1 ≥ deg Q

(b) Then P1Qm-1 is greater than deg Qm

(c) But this is impossible since deg P is less than deg Qm and since P1Qm-1 is less than P.

(d) So we reject our assumption at step #2a.

(3) We can now repeat this same step with P2 as a quotient for Qm-2 and so on.

(4) Eventually, we get to:

P = P1Qm-1 + P2Qm-2 + ... + Pm-1Q + Pm

(5) If we now divide both sides by Qm, we get:

P/Qm = P1/Q + P2/Q2 + ... + Pm-1/Qm-1 + Pm/Qm

QED

References