Friday, February 01, 2008

Gauss: Q(μp)

In today's blog, I will review some basic properties of Q(μp) which is the set of complex numbers which are rational expressions in the p-th roots of unity.

The content in today's blog is taken straight from Jean-Pierre Tignol's Galois Theory of Algebraic Equations. I will later use the results in today's blog in the proof by Carl Friedrich Gauss that all roots of unity are expressible as radicals.

Definition 1: μp

Let μp denote the set of p-th roots of unity.

Example:

μ1 = {1}
μ2 = {1, -1}
μ3 = {1, (1/2)[-1 + √-3], 1/2)[-1 - √-3])
μ4 = {1, -1, i, -i}

Now, let's use this to define a field (see Definition 3, here for definition of a field if needed)

Definition 2: Q(μp)

Let Q(μp) denote the set of complex numbers that are rational expressions in these p-th roots of unity.

This gives us that:



Now, we can show that Q(μp) = Q(ζ).

Lemma 1:

Q(μp) = Q(ζ)

Proof:

(1) From Defintion 1 above:

μp = { ρ1, ..., ρp}

(2) Let ζ = a primitive p-th root of unity (see Definition 2, here for definition of a primitive p-th root of unity if needed)

(3) Using Theorem 3, here, we have:

μp = { 1, ζ, ζ2, ..., ζp-1 }

(4) Then we have:



QED

Lemma 2:

Let P,Q be polynomials with coefficients in field F.

If:

P is irreducible in F[X]. (See Definition 1, here, for definition of irreducible polynomials)

P,Q have a common root u in field K which contains F

Then:

P divides Q.

Proof:

(1) Assume that P does not divide Q.

(2) Then P,Q are relatively prime polynomials since P is irreducible. [See Definition 1, here for definition of irreducible polynomials]

(3) Then (see Corollary 3.1, here), there exists polynomials U,V in F[X] such that:

P(X)U(X) + Q(X)V(X) = 1

(4) Substituting the common root u into the polynomials, we get:

P(u)U(u) + Q(u)V(u) = 1 in K

(5) Since u is the root for P(X) and Q(X), this gives us that:

P(u) = 0, Q(u) = 0 in K

(6) But then:

o*U(u) + 0*V(u) = 1 in K which is impossible.

(7) Therefore we reject our assumption in step #1.

QED

Lemma 3:

If u ∈ field K is a root of an irreducible polynomial P ∈ F[X] of degree d

and



Then:

every element in F(u) can be uniquely written in the form:

a0 + a1u + a2u2 + ... + ad-1ud-1 with ai field F.

Proof:

(1) Let f(u)/g(u) be an arbitrary element in F(u)

(2) Since g(u) ≠ 0, it follows that g(u) is not divisible by P since:

(a) Assume that g(u) is divisible by P.

(b) Since P(u) = 0, if follows that (X - u) divides P. [See Theorem, here]

(c) But if P divides g(u), then (X -u) divides g(u).

(d) But this is impossible since this implies g(u) = 0 [See Theorem, here] but g(u) ≠ 0.

(e) So we reject the assumption in step #2a.

(3) Then, g(u) is relatively prime to P since P is irreducible. [See Definition 1, here for definition of irreducible polynomials]

(4) Then (see Corollary 3.1, here), there exists polynomials h,U in F such that:

g(X)h(X) + P(X)U(X) = 1 in F[X]

(5) Since P(u) = 0, substituting u for X gives us:

g(u)h(u) + P(u)U(u) = g(u)h(u) + 0*U(u) = g(u)h(u) = 1 in K.

(6) Since g(u) ≠ 0, we have:

h(u) = 1/g(u) in K

which gives us that:

f(u)/g(u) = f(u)h(u) in K

(7) Using the Division Algorithm for Polynomials (see Theorem, here), there exists Q, R such that:

fh = PQ + R in F[X] with deg R ≤ d - 1.

(8) Since P(u) = 0, it follows that:

f(u)h(u) = P(u)Q(u) + R(u) = 0*Q(u) + R(u) = R(u) in K

(9) Since R(u) is a polynomial of degree at most d-1, we have converted an arbitrary expression f(u)/g(u) ∈ F(u) into a polynomial expression of the type:

a0 + a1u + ... + ad-1ud-1

with ai ∈ F

(10) Now, I will prove uniqueness.

(11) Assume that:

a0 + a1u + ... + ad-1ud-1 = b0 + b1u + ... + bd-1ud-1

(12) Let us define V(X) such that:

V(X) = (a0 - b0) + (a1 - b1)X + ... + (ad-1 - bd-1)Xd-1 ∈ F[X]

(13) It is clear that V(u) = 0 from step #11.

(14) Using Lemma 2 above, it is clear that P divides V.

(15) But since deg V ≤ d-1 and since P is of degree d, this is impossible unless V=0.

(16) Therefore, it follows that:

a0 - b0 = a1 - b1 = ... = ad-1 - bd-1 = 0

QED

Theorem 4: Every element in Q(μp) can be expressed in one and only one way as a linear combination with rational coefficients of the p-th roots of unity other than 1:

a1ζ + a2ζ2 + ... + ap-1ζp-1

with ai ∈ Q.

Proof:

(1) Let ζ be a root of Φp [See Definition 1, here]

(2) Q(μp) = Q(ζ) [From Lemma 1 above]

(3) Since p is a prime, Φp is irreducible over Q . [See Corollary 1.1., here]

(4) Using Lemma 3 above, since the degree of ζ is p-1, it follows that every element a ∈ Q(μp) can be uniquely expressed in the form:

a = a0 + a1ζ + a2ζ2 + ... + ap-2ζp-2

for some ai ∈ Q.

(5) Using the cyclotomic equation (see Lemma 1, here), we have:

Φp(ζ) = 1 + ζ + ζ2 + ... + ζp-1 = 0

which means that:

ζ + ζ2 + ... + ζp-1 = -1

(6) This gives us that:

a0 = -a0(ζ + ζ2 + ... + ζp-1)

(7) Combining step #6 with step #4 gives us:

a = (a1 - a0)ζ + (a2 - a02 + ... + (ap-2 - a0p-2 + (-a0p-1

(8) To prove uniqueness, let's assume that:

a1ζ + ... + ap-1ζp-1 = b1ζ + ... + bp-1ζp-1

(9) From step #5, we also have:

ζp-1 = -1 - ζ - ζ2 + ... -ζp-2

(10) Putting this into step #8 gives us:

a1ζ + ... + ap-1(-1 - ζ - ζ2 + ... -ζp-2) = b1ζ + ... + bp-1(-1 - ζ - ζ2 + ... -ζp-2)

which reduces to:

-ap-1 + (a1 - ap-1)ζ + (a2 - ap-12 + ... + (ap-2 - ap-1p-2 = -bp-1 + (b1 - bp-1)ζ + (b2 - bp-12 + ... + (bp-2 - bp-1p-2

(11) From Lemma 3 above, we can conclude that the coefficients on both sides are equal which gives us:

ap-1 = bp-1

which then gives us:

a1 = b1
...
ap-2 = bp-2

QED

References

Thursday, January 31, 2008

Eisenstein: Criteria for Irreducibility of Polynomials

In today's blog, I will go over a classical result from Ferdinand Eisenstein. The content in today's proof is taken directly from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

I will later use this result in Carl Friedrich Gauss's proof that all roots of unity are expressible as radicals.

For those who are not familiar, a monic polynomial is a polynomial whose leading coefficient is 1.

Theorem 1: Eisenstein's Criteria for Irreducibility of Polynomials

Let P be a monic polynomial with integral coefficients such that:

P = Xt + ct-1Xt-1 + ... + c1X + c0 ∈ Z[X]

If there is a prime number p which divides ci for i = 0, ..., t-1 but p2 does not divide c0

then:

P is irreducible over Q

Proof

(1) Assume that P is not irreducible over Q.

(2) Then there exist two non-constant polynomials f,g ∈ Q[X] such that:

P = fg

(3) Assume that f has degree n with n ≥ 1 and g has degree m with m ≥ 1 so that:

f = Xn + an-1Xn-1 + ... + a1X + a0 ∈ Z[X]

g = Xm + bm-1Xm-1 + ... + b1X + b0 ∈ Z[X]

(4) Since P is monic, we can assume that f,g are monic [if f,g are not monic, then (f/an is monic and an*g is monic since P = (f/an)*(g*an)]

(5) From step #2, it is also clear that c0 = a0*b0

(6) Using Euclid's Lemma (see Lemma 2, here), it is clear that for the prime p, p divides a0 or b0.

(7) It is also clear that since p2 does not divide c0 that p cannot divide both a0 and b0.

(8) We can assume that p divides a0 but not b0 (if it did not, we could switch f,g since they are interchangeable with respect to p and make the same assumption)

(9) Let i be the largest index of a such that p divides ai. It is clear that 0 ≤ i ≤ n-1. So, we can conclude that for any i, p divides a0, a1, ..., ai.

(10) Let k = i+1, it is clear that 1 ≤ k ≤ n and p does not divide ak.

(11) So:

ci+1 = ai+1b0 + aib1 + ai-1b2 + ... + a0bi+1.

where bj = 0 if j is greater than m.

(12) Now i+1 ≤ n which is less than t since n+1 ≤ m+n = t [since m ≥ 1 and n ≥ 1]

(13) So it follows that i+1 ≤ t-1 and p divides ci+1. [From the given in the theorem that p divides c0, ..., ct-1]

(14) So, from step #13, it follows that since p divides ci+1 and p divides a0, a1, ..., ai [step #9] that p must also divide ai+1b0.

(15) But this is impossible since p doesn't divide b0 (step #8) and p doesn't divide ai+1 [step #10]

(16) So we have a contradiction and we must reject our assumption in step #1.

QED

Corollary 1.1: For every prime p, the cyclotomic polynomial

Φp(x) = xp-1 + xp-2 + ... + x + 1

is irreducible over the field of rational numbers

Proof:

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

Φp(x) = (xp - 1)/(x - 1)

(2) Setting x = y + 1, we get:

Φp(y+1) = ([y + 1]p - 1)/([y + 1] - 1) =

= ([y + 1]p - 1)/y

(3) Using the Binomial Theorem (see Theorem, here):



(4) So, combining this with step #2 gives us:












(5) Now, it is clear that for (y+1)p all the resulting coefficients are integral (since integers are closed on additional and multiplication, see Lemma 1 and Lemma 2, here).

(6) Further, we know that for p!/[(m!)(p-m)!] where 1 ≤ m ≤ p-2, p is not divisible by (m!) or by (p-1)! [Since p is a prime and only divisible by p and m! and (p-m)! does not include p]

(7) So, we can conclude that for m=1, ..., p-2, we have p divides p!/[(m!)(p-m)!]

(8) Now, we can use Eisenstein's Criterion above to conclude that the cyclotomic polynomial is irreducible in the field Q since:

the cyclotomic polynomial is monic, p divides all coefficients except for the leading coefficient, and p2 does not divide the last coefficient (p2 does not divide p.)

QED

References

Tuesday, January 29, 2008

Gauss: Gauss's Lemma for Polynomials

Today's proof is taken from Carl Friedrich Gauss' Disquisitiones Arithmeticae (Article 42). This is Gauss' classic work on number theory which he wrote when he was 21. It is a masterpiece that includes the first use of modular arithmetic, the first complete proof of the fundamental theorem of algebra, a proof for quadratic reciprocity, Gauss' analysis of cyclotomic equations, as well as the first systematic presentation of number theory.

Lemma 1:

if a prime p doesn't divide an integer a, then (a +bp)/cp is not an integer

Proof:

(1) There exists an integer d such that a ≡ d (mod p) where 1 ≤ d ≤ p-1.

(2) So, p divides a - d. (see here for review of modular arithmetic)

(3) And p divides (a - d) so p divides (a -d) + bp = (a + bp) -d

(4) So therefore a + bp ≡ d (mod p)

(5) So it follows that since p doesn't divide a+bp, then (a +bp)/cp is not an integer.

QED

A monic polynomial is a polynomial whose leading coefficient is 1 (see Definition 5, here)

Theorem 2: Gauss's Lemma for Polynomials

Let P,Q be two monic polynomials such that:

P = xm + a1xm-1 + a2xm-2 + a3xm-3 + ... + am

Q = xn + b1xn-1 + b2xn-2 + b3xn-3 + ... + bn

If the coefficients of P are rational but not all integers and if the product is also monic such that:

PQ = xm+n + c1xm+n-1 + c2xm+n-2 + c3xm+n-3 + ... + cm+n

Then, the coefficients c1, c2, ..., cm+n cannot all be integers.

Proof:

(1) Let us assume that all rational cofficients in a1, ..., am and b1, ..., bn are expressed in their lowest form.

(2) Let p be a prime number that divides one of the denominators of P [we can assume this since not all the coefficients of P are integers]

(3) Since Q is monic, it is clear that the at least one of the coefficients of (Q)/p will have p as a factor of its denominator (for example, bn will have (1/p) as its coefficient).

(4) In P, there will always be one term, a fraction, whose denominator involves high powers of p than all the fractional coefficients that precede it and no lower powers than the denominators of all succeeding fractional coefficients.

For example, if there is only one fraction with the rest integers, than this fraction is the coefficient. One can start with the first coefficient divisible by p and then check if there are any coefficients after it that are divisible by a greater power of p.

(5) We can identify the term in step #4 as Gxg with G divisible by 1/(pt) with t ≥ 1.

(6) Since p divides at least one of the denominators in (Q)/p, the same term in step #4 exists in (Q)/p.

(7) We can identify the term in step #6 as Hxh with H divisible by 1/(pu) with u ≥ 1.

(8) Now, it follows that t + u ≥ 2.

(9) Next, I will show that the term xg+h in the product of (P) and (Q) will have a fractional coefficient who denominator is divisible by 1/(pt+u-1). This then will complete the proof since a coefficient that is divisible by 1/(pt+u-1) where p is a prime is not an integer.

(10) Let the terms in P which precede Gxg be 'Gxg+1, ''Gxg+2 and those which follow Gxg be G'xg-1, G''xg-2

(11) Let the terms in (Q)/p which precede Hxh be 'Hxh+1, ''Hxh+2 and those which follow Hxh be H'xh-1, H''xh-2

(12) If we multiply P and (Q)/p, the coefficient of the term Gxg*Hxh is GH + 'GH' + ''GH'' + ... + 'HG' + ''HG'' + ...

(13) Because G,H have the highest power of p, there exists e0,f0 such that:

p does not divide e0
p does not divide f0

and

GH = e0/(f0pt+u)

(14) Since any of the ('G, ''G, etc.) or ('H, ''H, etc.) have a power of p less than t or u and because any of the (G', G'', etc.) or (H', H'', etc) have a power of p no greater than t or u, it follows that any product of the form ('GH', ''GH'', etc.) will have the following form:

'GH' = ei/(fipt+u-di)

where

p does not divide ei
p does not divide fi
di ≥ 1.

(15) Now if we sum all the factors in step #14 and reduce the denominator to the lowest term, then we get:

∑ ei/(fipt+u-di) =

= e'/(f'pt+u-d'i)

where

p does not divide e'
p does not divide f'
d' ≥ 1.

(16) If we add up the result of step #14 with step #15, we get:

(e0f' + e'f0pd)/(f0f'pt+u)

where:

p does not divide e0
p does not divide e'
p does not divide f0
p does not divide f'
d ≥ 1
(t + u) ≥ 2

(17) Since Q = p*(Q)/p, for this same coefficient for P*Q, we have:

(e0f' + e'f0pd)/(f0f'pt+u-1)

where:

p does not divide e0
p does not divide e'
p does not divide f0
p does not divide f'
d ≥ 1
(t + u - 1) ≥ 1

(18) Since p does not divide e0 or f', it follows that p does not divide e0f.

(19) If:

a = e0f'
b = ef0pd-1
c = f0f'pt+u-2

Then we can use Lemma 1 above to conclude that:

(e0f' + e'f0pd)/(f0f'pt+u-1)

is not an integer.

QED

Corollary 2.1:

If a monic polynomial in Q[X] divides a monic polynomial with integral coefficients, then its coefficients are all integral.

Proof:

(1) Let f be a monic polynomial with integral coefficients.

(2) Let P be a monic polynomial that divides f.

(3) Since P divides f, there exists a polynomial Q such that:

f = PQ

(4) Since P,f are monic, it follows that Q must also be monic. [See Lemma 1, here]

(5) Assume that the coefficient in P are not all integers.

(6) Then, using Theorem 2 above, it follows that the coefficients of f are not all integers.

(7) But this is not correct since by assumption, all the coefficients of f are integers.

(8) So we reject our assumption in step #5.

QED

References