Sunday, February 24, 2008

Dedekind: irreducibility of Φp over Q(μk)

Carl Friedrich Gauss made an assumption about the irreducibility of Φp over Q(μk). This assumption is correct but the proof of this assumption was first given by Leopold Kronecker in 1854.

The proof presented in today's blog is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations and is based on "some ideas of [Richard] Dedekind".

For review if needed, see here for review of a monic polynomials. See Definition 1, here for definition of an irreducible factor of a polynomial.

Lemma 1:

Let f be a monic irreducible factor of Φn in Q[X]

Let p be a prime number which does not divide n.

If ω ∈ C is a root of f

Then:

ωp is also a root of f and:

f(ω) = 0 → f(ωp) = 0

Proof:

(1) Assume that f(ω) = 0

(2) Assume that f(ωp) ≠ 0

(3) Since f divides Φn and Φn divides xn - 1 [See Definition 1, here for definition of Φn], then, there exists a polynomial g such that:

xn - 1 = fg

(4) We know that g is monic. [See Lemma 1, here]

(5) Since f(ω) = 0, it follows that ωn = 1 since:

(a) (ω)n - 1 = f(ω)g(ω) = 0*g(ω) = 0

(b) Adding 1 to both sides of the equation gives us ωn = 1

(6) We also know that p)n = 1 since:

p)n = ωpn = (ωn)p = (1)p = 1
(7) So, we have: p)n - 1 = f(ωp)g(ωp) = 0

(8) But f(ωp) ≠ 0 from step #2 above so we can conclude that g(ωp) = 0

(9) This shows that ω is a root of g(xp)

(10) Since f is irreducible, we can use a previous result (see Lemma 2, here) to conclude that f(x) divides g(xp)

(11) Thus, there exists a polynomial h(x) such that:

g(xp) = f(x)h(x)

(12) Further, we can conclude that f,g, and h all have integer coefficients since:

(a) Step #3 above shows that f,g have integer coefficients. [See Corollary 2.1, here] since:

f,g are monic [f is monic from the given; g is monic from step #4 above] and they both divide a monic polynomial with integral coefficients: xn - 1.

(b) Step #11 above shows that h has integer coefficients since: g is a monic polynomial with integral coefficients [step #12a above] and h is monic since f,g are monic [see Lemma 1, here]

(13) So, we can consider the polynomials: f, g, and h whose coefficients are the congruence classes modulo p of the coefficients of f,g, and h. [See here for review of congruence classes modulo p]

(14) From step #3 above, we can conclude:

xn - 1 = f(x)g(x) in Fp[x]

where Fp[x] is a polynomial whose coefficients are the set of congruence classes modulo p Z/pZ.

(15) From step #11 above, we can conclude:

g(xp) = f(x)h(x) in Fp[x]

(16) Using Fermat's Little Theorem (see Theorem, here), we know that:

ap-1 ≡ 1 (mod p)

which further implies that:

ap ≡ a (mod p)

(17) Assume that:

g(x) = a0 + a1x + ... + ar-1xr-1 + xr

(18) Then using step #16 we also have:

g(x) = a0p + a1px + ... + ar-1pxr-1 + xr

(19) But from step #17, we also have:

g(xp) = a0p + a1pxp + ... + ar-1pxp(r-1) + xpr

(20) Using the result (see Lemma, here) that (a + b)p ≡ ap + bp (mod p), we further have:

g(xp) = (a0 + a1x + ... + ar-1xr-1 + xr)p = g(x)p in Fp[x]

(21) From step #20 and step #15, we can conclude that:

gp = fh

(22) But then if f divides gp, it is clear that f and g must have a common factor.

(23) Let φ(x) be the the nonconstant common factor of f and g .

(24) Then, there exists polynomials f ' and g ' such that:

f = f ' φ g = g' φ

(25) Using step #14, we have:

xn - 1 = f(x)g(x) = (f' φ)(g'φ ) in Fp[x]

(26) Let ψ = f '*g'

(27) Then we have:

xn - 1 = φ2ψ in Fp[x]

(28) Taking the derivatives from both sides (see here for linear combination rule and product rule):

nxn-1 = φ*(2dφ*ψ + φ*dψ)

(29) But this now gives us a contradiction since by step #27:

φ divides xn - 1

and by step #28:

φ divides nxn-1

which is impossible

(30) So, we reject our assumption in step #2.

QED

Theorem 2:

For every integer n ≥ 1, the cyclotomic polynomial Φn is irreducible over Q

Proof:

(1) Let f be a monic irreducible factor of Φn in Q[x]

(2) To establish this result, I will show that every root of Φn in C is a root of f and finally that f = Φn.

(3) Let ζ be a root of f.

(4) Then ζ is a root of Φn since:

(a) Since f is a factor of Φn, there exists a polynomial g such that:

Φn = fg

(b) Φn(ζ) = f(ζ)g(ζ) = 0*g(ζ) = 0

(5) From step #4, we can conclude that ζ is a primitive n-th root of unity since:
Φn only includes primitive n-th roots of unity as roots [See Definition 1, here]

(6) Since ζ is a primitive n-th root of unity, all other primitive n-th roots of unity (if they exist) have the form ζk where k is an integer relatively prime to n between 1 and n-1. [See Theorem 3, here]

(7) Factoring k in prime factors we get (see Theorem 3, here):

k = p1*...*ps

(8) We can now use Lemma 1 above to show that any root of Φn is a root of f since if f(ζ) = 0, then also:

f(ζp1) = 0 f(ζp1p2) = 0 ... f(ζk) = 0

(9) Thus, f has as its root every primitive n-th root of unity and every root of Φn

(10) Using a previous result (see Corollary 2.2, here), we can further conclude that Φn divides f.

(11) So if Φn divides f and f divides Φn, it follows that Φn = f

QED

Theorem 3:

If m and n are relatively prime integers, then Φn is irreducible over Q(μm)

Proof:

(1) Let f be a monic irreducible factor of Φn in Q(μm)[x], that is, the coefficients of f are in Q(ηm)

(2) Let ζ ∈ C be a root of f so that ζ is a primitive n-th root of unity [see step #5 in Theorem 2 above].

(3) Let η be a primitive m-th root of unity.

(4) Since all roots of unity are powers of the primitive m-th root of unity (see Theorem 3, here), we have:

Q(μm) = Q(η)

(5) From an earlier result (see Lemma 3, here), we can conclude that every coefficient of f is a polynomial expression in η with rational coefficients since:

(a) ζ ∈ C is a root of f ∈ Q[x] which is irreducible and is of degree less than n.

(b) Let Q(α) be the set of elements in C which are rational expressions of α with coefficients in Q where α ∈ C.

(c) Q(α) = u(α)/v(α) ∈ C such that u,v ∈ Q[x] and v(α) ≠ 0.

(d) So using Lemma 3, here, we can conclude that every element in Q(α) can be uniquely written in the form a0 + a1α + a2α2 + ... + an-1αn-1 with ai ∈ Q.

(e) From 5d, it is clear that we can define a polynomial

(6) Therefore f(x) = φ(η,x) for some polynomial φ(y,x) ∈ Q[y,x]

(a) f(x) ∈ Q(μn)[x] [See step #1 above]

(b) Q(μn) = Q(η) [See step #4 above]

(c) Using step #5d, it is clear that all elements of Q(η) can be expressed as:

a0 + a1η + a2η2 + ... + an-1ηn-1 with ai ∈ Q

(d) From step #6c, it is clear that we can define a polynomial φ(η,x) such that:

f(x) = (a0,0 + a0,1η + ... + a0,n-1ηn-1) + (a1,0 + a1,1η + ... + a1,n-1ηn-1)x + ... + (an-1,0 + an-1,1η + ... + an-1,n-1ηn-1)xn-1

where φ(y,x) = (a0,0 + a0,1y + ... + a0,n-1yn-1) + (a1,0 + a1,1y + ... + a1,n-1yn-1)x + ... + (an-1,0 + an-1,1y + ... + an-1,n-1yn-1)xn-1 and φ(y,x) ∈ Q[y,x]

(7) Let ρ = ζη.

(8) Since m,n are relatively prime, it follows from a previous result (see Theorem 2, here) that:

ρ is a primitive mn-th root of unity.

(9) Since m,n are relatively prime, there exists integers r,s such that (see Lemma 1, here):

mr + ns = 1.

(10) Since ζn = 1 and ηm = 1, we have:

ζ = ζmr = ζmr*(1)rmr*(ηm)rmr

and

η = ηns = (1)sns= (ζn)snsns

(11) Since f(ζ) = 0, we have [see step #6 above]:

φ(η,ζ) = 0

and therefore [from step #10 above],

φ(ρnsmr) = 0

(12) From an earlier result (see Lemma 2, here), we can conclude that Φmn(x) divides φ(xns,xmr) since:

(a) Φmn(x) and φ(xns,xmr) are polynomials with coefficients in Q(μm).

(b) Since φ(xns,xmr) = f(x) [see step #6 above] and f(x) is irreducible in Q(μm), it follows that:

φ(xns,xmr) is irreducible in Q(μm)

(c) Finally, Φmn(x) and φ(xns,xmr) have a common root ρ in field C which contains the field Q(μm) [See step #8 above and step #11 above]

(d) Therefore, we can use Lemma 2, here to conclude that Φmn(x) divides φ(xns,xmr)

(13) It follows then that: φ(ωnsmr) = 0 for every mn-th root of unity ω since:

if Φmn(x) divides φ(xns,xmr), then there exists a polynomial g such that:

φ(xns,xmr) = Φmn(x)g(x)

so that if Φmn(a)=0, it follows that φ(ans,amr) =0.

(14) Let k be an integer relatively prime to n such that 1 ≤ k ≤ n-1.

(15) Let l = kmr + ns [Derived from the equation in step #9 above]

(16) Since mr + ns=1, we have mr ≡ 1 (mod n) and ns ≡ 1 ( mod m)

(17) We further have:

l ≡ k (mod n)

and

l ≡ 1 (mod m)

(18) It follows that ζl = ζk and ηl = η [See Lemma 1, here]

(19) Since we already have observed (see step #10 above) that ζ = ρmr and η = ρns, we have:

ρlmr = ρkmr = (ρmr)k= ζk [Since ζ is an primitive n-th root of unity]

and

ρlnsns = η [Since η is a primitive m-th root of unity]

(20) On the other hand, the congruences in step #17 also show that l is relatively prime to mn.

(21) Therefore, ρl is a primitive mn-th root of unity [See Definition 2, here].

(22) step #11 combined with Lemma 1 above gives us:

φ(ρlnslmr) = 0

since:

φ(ρns, ρmr) = 0 and Lemma 1 above implies that:

φ([ρl]ns,[ρl]mr) = 0.

(23) So since φ([ρl]ns,[ρl]mr) = φ(η,ζk) [see step #19 above], we have:

φ(η,ζk) = 0

(24) Since we have φ(η,ζk) = f(ζk) [see step #6 above], we can conclude:

f(ζk) = 0.

(25) To complete the proof, we use the same reasoning as in Theorem 2 above since:

(a) We have shown that every root of Φn in C is a root of f [see step #14 since for every root r, there exists k such that r = ζk]

(b) Using a previous result (see Corollary 2.2, here), we can further conclude that Φn divides f.

(c) So if Φn divides f and f divides Φn, it follows that Φn = f

QED

Corollary 3.1:

Let p be a prime number and let k be an integer which divides p-1.

Let ζ ∈ C be a primitive p-th root of unity

Then:

Every element in Q(μk)(μp) can be uniquely written in the form:

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

for some a1, ..., ap-1 in Q(μk)

Proof:

(1) The hypothesis on k ensures that k is relatively prime to p since k ≡ 1 (mod p).

(2) Hence, Φp is irreducible over Q(μk) by Theorem 3 above.

(3) Let ζ be a primitive p-th root of unity.

(4) Then, Q(μk)(μp) = Q(μk)(ζ) since:

Using Theorem 3, here, we can conclude for all x ∈ μp, there exists an integer i such that x = ζi.

(5) We make the following observations:

(a) ζ ∈ C is a root of Φp [See step #3 above]

(b) Φp is irreducible over Q(μk) [see step #2 above]

(c) Φp has degree p-1. [See Lemma 1, here]

(6) Using Lemma 3, here, we can conclude that every element in Q(μk)(ζ) can be uniquely written in the form:

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

with ai ∈ Q(μk)

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

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

which means that:

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

(8) This gives us that:

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

(9) Combining step #6 with step #8 gives us:

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

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

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

(11) From step #7, we also have:

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

(12) Putting this into step #10 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

(13) From Lemma 3 here, 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