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 xⁿ - 1 [See Definition 1, here for definition of Φ_n], then, there exists a polynomial g such that:

xⁿ - 1 = fg

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

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

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

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

(6) We also know that (ω^p)ⁿ = 1 since:

(ω^p)ⁿ = ω^pn = (ωⁿ)^p = (1)^p = 1
(7) So, we have: (ω^p)ⁿ - 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(x^p)

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

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

g(x^p) = 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: xⁿ - 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:

xⁿ - 1 = f(x)g(x) in F_p[x]

where F_p[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(x^p) = f(x)h(x) in F_p[x]

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

a^p-1 ≡ 1 (mod p)

which further implies that:

a^p ≡ a (mod p)

(17) Assume that:

g(x) = a₀ + a₁x + ... + a_r-1x^r-1 + x^r

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

g(x) = a₀^p + a₁^px + ... + a_r-1^px^r-1 + x^r

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

g(x^p) = a₀^p + a₁^px^p + ... + a_r-1^px^p(r-1) + x^pr

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

g(x^p) = (a₀ + a₁x + ... + a_r-1x^r-1 + x^r)^p = g(x)^p in F_p[x]

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

g^p = fh

(22) But then if f divides g^p, 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:

xⁿ - 1 = f(x)g(x) = (f' φ)(g'φ ) in F_p[x]

(26) Let ψ = f '*g'

(27) Then we have:

xⁿ - 1 = φ²ψ in F_p[x]

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

nx^n-1 = φ*(2dφ*ψ + φ*dψ)

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

φ divides xⁿ - 1

and by step #28:

φ divides nx^n-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 = p₁*...*p_s

(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(ζ^p₁) = 0 f(ζ^p₁p₂) = 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 a₀ + a₁α + a₂α² + ... + a_n-1α^n-1 with a_i ∈ 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:

a₀ + a₁η + a₂η² + ... + a_n-1η^n-1 with a_i ∈ Q

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

f(x) = (a_0,0 + a_0,1η + ... + a_0,n-1η^n-1) + (a_1,0 + a_1,1η + ... + a_1,n-1η^n-1)x + ... + (a_n-1,0 + a_n-1,1η + ... + a_n-1,n-1η^n-1)x^n-1

where φ(y,x) = (a_0,0 + a_0,1y + ... + a_0,n-1y^n-1) + (a_1,0 + a_1,1y + ... + a_1,n-1y^n-1)x + ... + (a_n-1,0 + a_n-1,1y + ... + a_n-1,n-1y^n-1)x^n-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 ζⁿ = 1 and η^m = 1, we have:

ζ = ζ^mr = ζ^mr*(1)^r =ζ^mr*(η^m)^r =ρ^mr

and

η = η^ns = (1)^s*η^ns= (ζⁿ)^s*η^ns =ρ^ns

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

φ(η,ζ) = 0

and therefore [from step #10 above],

φ(ρ^ns,ρ^mr) = 0

(12) From an earlier result (see Lemma 2, here), we can conclude that Φ_mn(x) divides φ(x^ns,x^mr) since:

(a) Φ_mn(x) and φ(x^ns,x^mr) are polynomials with coefficients in Q(μ_m).

(b) Since φ(x^ns,x^mr) = f(x) [see step #6 above] and f(x) is irreducible in Q(μ_m), it follows that:

φ(x^ns,x^mr) is irreducible in Q(μ_m)

(c) Finally, Φ_mn(x) and φ(x^ns,x^mr) 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 φ(x^ns,x^mr)

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

if Φ_mn(x) divides φ(x^ns,x^mr), then there exists a polynomial g such that:

φ(x^ns,x^mr) = Φ_mn(x)g(x)

so that if Φ_mn(a)=0, it follows that φ(a^ns,a^mr) =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

ρ^lns =ρ^ns = η [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:

φ(ρ^lns,ρ^lmr) = 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:

a₁ζ + a₂ζ² + ... + a_p-1ζ^p-1

for some a₁, ..., a_p-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 = ζⁱ.

(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 = a₀ + a₁ζ + a₂ζ² + ... + a_p-2ζ^p-2

with a_i ∈ Q(μ_k)

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

Φ_p(ζ) = 1 + ζ + ζ² + ... + ζ^p-1 = 0

which means that:

ζ + ζ² + ... + ζ^p-1 = -1

(8) This gives us that:

a₀ = -a₀(ζ + ζ² + ... + ζ^p-1)

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

a = (a₁ - a₀)ζ + (a₂ - a₀)ζ² + ... + (a_p-2 - a₀)ζ^p-2 + (-a₀)ζ^p-1

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

a₁ζ + ... + a_p-1ζ^p-1 = b₁ζ + ... + b_p-1ζ^p-1

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

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

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

a₁ζ + ... + a_p-1(-1 - ζ - ζ² + ... -ζ^p-2) = b₁ζ + ... + b_p-1(-1 - ζ - ζ² + ... -ζ^p-2)

which reduces to:

-a_p-1 + (a₁ - a_p-1)ζ + (a₂ - a_p-1)ζ² + ... + (a_p-2 - a_p-1)ζ^p-2 = -b_p-1 + (b₁ - b_p-1)ζ + (b₂ - b_p-1)ζ² + ... + (b_p-2 - b_p-1)ζ^p-2

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

a_p-1 = b_p-1

which then gives us:

a₁ = b₁
...
a_p-2 = b_p-2

QED

References

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

Starting a new blog on algorithms

For the past two years, I have been working exclusively on a math blog. It has really been great for me. It has been an opportunity to delve into the history of mathematics in the effort of reviewing great works of genius and try to put these achievements in the context of a very tough math problem: Fermat's Last Theorem.

In light of the great enjoyment I've had in running this blog, I've decided to start another blog. This one will be closer to my day job, software engineering.

The purpose of the new blog is to analyze computer algorithms in the same way that I have up to now been analyzing mathematical proofs. It will cover the classic works of algorithms and some contemporary algorithms.

For example, my first series of blogs will be on the $50,000 algorithm. This is the algorithm that has won the 2007 Progress Prize as part of the $1 million Netflix Prize contest. Details on this content can be found here.

I hope to keep up the same standards of rigorous logic as well as clarity and precision. If you have an interest in computer programming, I hope that you find my new blog as interesting complement to this math blog.

I plan to continue the Fermat's Last Theorem blog up until Andrew Wiles' second proof so if math is your thing, please continue coming here. :-)

Regards,

-Larry

Gauss: Periods of Cyclotomic Equations

In today's blog, I show some major results from Carl Friedrich Gauss in his analysis of periods of cyclotomic equations. These results represent a very small subset of Gauss's work in his classic Disquisitiones Arithmeticae which he wrote when he was 21. These properties of periods of cyclotomic equations are later used to demonstrate Gauss's proof that all cyclotomic polynomials are solvable by radicals.

Today's content is taken straight from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations which covers the history of Galois Theory from a mathematical perspective.

Definition 1: μ_p

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

Examples:

μ₁ = {1}
μ₂ = {1, -1}
μ₃ = {1, (1/2)[-1 + √-3], 1/2)[-1 - √-3])
μ₄ = {1, -1, i, -i}

I will use μ_p in the following context:

Definition 2: Q(μ_p)

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

So that:



Definition 3: period of f terms of a p-th root of unity

For any two positive integers: e,f where ef = p-1, the periods of f terms are:

η₀ = ζ₀ + ζ_e + ζ_2e + ... + ζ_e(f-1)

η₁ = ζ₁ + ζ_e+1 + ζ_2e+1 + ... + ζ_e(f-1)+1

η₂ = ζ₂ + ζ_e+2 + ζ_2e+2 + ... + ζ_e(f-1)+2

...

η_e-1 = ζ_e-1 + ζ_2e-1 + ζ_3e-1 + ... + ζ_e(f-1)+(e-1)

If you review Alexander-Theophile Vandermonde's solution of the eleventh root of unity, it is clear that Carl Friedrich Gauss's theory of periods is a generalization of his solution. Interestingly, it is not clear if Gauss derived his solution from the work of Vandermonde or if he came upon it independently as part of his solution of the seventeenth root of unity.

Definition 4: σⁱ(f)

If we number each time that we apply σ such that σ(σ(f)) = σ₁(σ₂(f)), then:
σⁱ(f) = σ₁(σ₂(...(σ_i(f))...))

We will now use the equation ef=p-1 (see Definition 3 above) to define a set whose elements are invariant under σ^e.

Definition 5: K_f

By K_f, let us denote the set of all Q(μ_p) which are invariant under σ^e where ef = p-1.

Examples of K_f:

(1) All rational numbers

u ∈ Q → u ∈ K_f [This is clear from Lemma 6, here]

(2) All periods of cyclotomic equations

This is clear from definition 3 above.

Now, we can use these definitions to identify some properties which we will use later.

Theorem 1: K_f is a vector space

Proof:

The proof follows from Definition 2, here since:

(1) K_f is nonempty [See Lemma 6, here since Q is nonempty]

(2) K_f is closed on addition. [See Lemma 5, here]

(3) K_f is closed on scalar multiplication. [See Lemma 7, here]

(4) K_f addition is associative. [See Lemma 5, here]

(5) 0 ∈ K_f [See Lemma 6, here since 0 ∈ Q]

(6) K_f has negative elements [See Lemma 7, here since (-1)*σ(x) = σ(-x)]

(7) K_f addition is commutative. [See Lemma 5, here]

(8) All elements of K_f are distributive since:

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

(9) Scalar multiplication is associative [See Lemma 7, here]

(10) Existence of 1 [See Lemma 6, here since 1 ∈ Q]

QED

Theorem 2: Every element in K_f can be written in a unique way as a linear combination with rational coefficients of the e periods of f terms.

(1) Let a be an arbitrary element in K_f [See Definition 5 above]

(2) We can write a as follows: [See Definition 2 above and See Definition 1, here, for ζ_i]

a = a₀ζ₀ + a₁ζ₁ + ... + a_e-1ζ_e-1 +
+ a_eζ_e + a_e+1ζ_e+1 + ... + a_2e-1ζ_2e-1 +
+ ... +
+ a_e(f-1)ζ_e(f-1) + a_e(f-1)+1ζ_e(f-1)+1 + ... + a_p-2ζ_p-2

(3) By the definition of σⁱ [See Definition 4 above], we have:

σ^e(a) = a₀ζ_e + a₁ζ_e+1 + ... + a_e-1ζ_2e-1 +
+ a_eζ2e + a_e+1ζ_2e+1 + ... + a_2e-1ζ_3e-1 +
+ ... +
+ a_e(f-1)ζ₀ + a_e(f-1)+1ζ₁ + ... + a_p-2ζ_e-1.

(4) Since a ∈ K_f, we know that:

σ^e(a) = a

(5) Thus:

a₀ = a_e = a_2e = ... = a_e(f-1)

a₁ = a_e+1 = a_2e+1 = ... = a_e(f-1)+1

...

a_e-1 = a_2e-1 = a_3e-1 = ... = a_p-2

(6) Therefore:

a = a₀(ζ₀ + ζ_e + ... + ζ_e(f-1)) +
+ a₁(ζ₁ + ζ_e+1 + ... + ζ_e(f-1)+1) +
+ ... +
+ a_e-1(ζ_e-1 + ζ_2e-1 + ... + ζ_p-2).

(7) This proves that a is a linear combination of the periods, since the expressions between the brackets are the periods of f terms. [See Definition 3 above]

(8) Further, this expression is unique. [See Theorem 4, here]

QED

Corollary 2.1: 1, η, η₂, ..., η_e-1 is a basis for K_f

Proof:

This follows directly from Theorem 1 above, Theorem 2 above and Lemma 1, here.

QED

Theorem 3:

1, η, η², ..., η^e-1 is a basis for the vector space K_f

Proof:

(1) 1, η, η², ..., η^e-1 are linearly independent [see Definition 1, here for definition of linearly independent if needed] since:

(a) Assume that a₀ + a₁η + ... + a_e-1η^e-1 = 0 for some rational numbers a₀, ..., a_e-1

(b) Then η is the root of the polynomial p(x) where:

p(x) = a₀ + a₁x + ... + a_e-1x^e-1 (from step #1a)

(c) Now if a₀ + a₁η + ... + a_e-1η^e-1 = 0, it follows that:

σ(a₀ + a₁η + ... + a_e-1η^e-1 ) = σ(0) = 0

σ²(a₀ + a₁η + ... + a_e-1η^e-1 ) = σ²(0) = 0

σ³(a₀ + a₁η + ... + a_e-1η^e-1 ) = σ³(0) = 0

...

σ^e-1(a₀ + a₁η + ... + a_e-1η^e-1 ) = σ^e-1(0) = 0

(d) So, σ(η), σ²(η), ..., σ^e-1(η) are all roots of p(x) in step #1b

(e) Now, each of η, σ(η), etc. are the e periods of f terms which are pairwise distinct [See Definition 3 above]

(f) Since by the Fundamental Theorem of Algebra (see Theorem, here), the polynomial p(x) has degree at most e -1, it cannot have as roots the e periods of the f terms unless it is the zero polynomial.

(g) Therefore, a₀ = ... = a_e-1 = 0

(h) This then proves 1, η, η², ..., η^e-1 are linearly independent. [See Definition 1, here]

(2) From Corollary 2.1 above, we know that dim K_f = e. [See Theorem 1, here and Definition 2, here]

(3) But then using the fact 1, η, η², ..., η^e-1 are linearly independent and Lemma 2, here, we can conclude that:

1, η, η², ..., η^e-1 is a basis for K_f.

QED

Corollary 3.1:

If η, η' are periods of f terms, then:

η' = a₀ + a₁η + ... + a_e-1η^e-1

for some rational numbers a₀, ..., a_e-1

Proof:

This follows from Theorem 3 above since η' ∈ K_f and 1, η, η², ..., η^e-1 is a basis for the vector space K_f.

QED

Lemma 4:

if gh=ef=p-1 and f divides g, then it follows that:

K_g ⊂ K_f

Proof:

(1) Since gh=ef and f divides g, there exists an integer k such that:

k = g/f = e/h

(2) Therefore e = hk which gives us that:

σ^e = (σ^h)^k

(3) This means that every element that is invariant under σ^h is also invariant under σ^e since:

(a) Assume that an element a is invariant under σ^h such that:

σ^h(a) = a

(b) Further:

σ^h₁(σ^h₂(...(σ^h_k(a)...))) = a

(4) Since h*k = e, it follows from definition 4 above that:

σ^h₁(σ^h₂(...(σ^h_k(a)...))) = σ^e(a)

(5) And it follows that:

σ^e(a) = a

(6) Since σ^h(a) = a → a ∈ K_g and σ^e(a) = a → a ∈ K_f, it follows that:

K_g ⊂ K_f

QED

Lemma 5:

Let f,g be divisors of p-1.

If f divides g, then every element in K_f is a root of a polynomial of degree g/f with coefficients in K_g

Proof:

(1) Let a be an element of K_f

(2) Let us define k such that:

k = g/f

Since ef = gh, it follows that:

k = g/f = e/h

(3) Let use define P(x) such that:

P(x) = (x - a)(x - σ^h(a))(x - σ^2h(a))*...*(x - σ^h(k-1)(a))

(4) P(x) has degree hk/h = k = g/f

(5) It is also clear that a is a root of P(x). [Since if x=a, then P(x)=0]

(6) We note that:

σ^h(σ^h(k-1)(a)) = σ^hk(a) = (σ^h(a))^k

(7) Since k = e/h, it follows that e=hk and:

(σ^h(a))^k = σ^e(a) = a

(8) Step #3 and step #6 and step #7 give us that:

σ^h(P(x)) = P(x)

(9) Therefore, we conclude that P(x) has coefficients in K_g.

QED

Corollary 5.1:

Let f,g be divisors of p-1 and let η, ξ be periods of f and g terms respectively.

If f divides g, then η is a root of a polynomial of degree g/f whose coefficients are rational expressions of ξ

Proof:

(1) ξ ∈ K_g, and η ∈ K_f

(2) Using Lemma 5 above, we know that η is a root of a polynomial P(x) of degree g/f with coefficients in K_g

(3) Using Theorem 3 above, it follows that:

P(x) has coefficients which are rational expressions of ξ.

QED

References

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

Gauss: σ notation

In today's blog, I present a mapping notation σ(f) that I will use in proofs about periods of cyclotomic equations. I will talk in more detail in my next blog about Gauss's concept of periods which generalize the same method that Alexander-Theophile Vandermonde used to solve the eleventh root of unity.

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

Lemma 1:

for any prime p, if m ≡ n (mod p), and ζ is a p-th root of unity

then:

ζ^m = ζⁿ

Proof:

(1) Assume m ≡ n (mod p) [See here for a review of modular arithmetic if needed]

(2) Then, there exists an integer d such that:

0 ≤ d ≤ p-1

and

m ≡ d (mod p)
n ≡ d (mod p)

(3) So there exists m' and n' such that:

m = m'*p + d
n = n'*p + d

(4) Since ζ^p = 1 (see here for review of roots of unity if needed), this gives us that:

ζ^m = ζ^{m'*p + d} = (ζ^p)^m'*ζ^d = 1^m'*ζ^d = ζ^d

ζⁿ = ζ^{n'*p + d} = (ζ^p)^n'*ζ^d = 1^n'*ζ^d = ζ^d

QED

Definition 1: ζ_i

Let ζ_i = ζ^gi where g is a primitive root of a prime p.

Lemma 2:

ζ_p-1 = ζ₀

ζ_p = ζ₁

Proof:

(1) Since g is a primitive root, g^p-1 ≡ 1 (mod p) [By Fermat's Little Theorem, see here].

(2) So using Lemma 1 above, it follows that:

ζ_p-1 = ζ^gp-1 = ζ¹ = ζ^g0 = ζ₀

and

ζ_p = ζ^g(p-1)+1 = ζ^gp-1*g1 = (ζ^gp-1)^g = (ζ¹)^g = ζ^g1 = ζ₁

QED

Definition 2: μ_p

Let μ_p denote the set of p-th roots of unity so that:

μ_p = { 1, ζ₀, ζ₁, ..., ζ_p-2 }

Example:

μ₁ = {1}
μ₂ = {1, -1}
μ₃ = {1, (1/2)[-1 + √-3], 1/2)[-1 - √-3])
μ₄ = {1, -1, i, -i}

Definition 3: σ(ζ) where ζ ∈ μ_p

Let σ be a map that changes f(ζ) to f(ζ^g)

Lemma 3: σ(ζ_i) = ζ_i+1

Proof:

(1) From the definition of ζ_i [See Definition 1 above]

σ(ζ_i) = σ(ζ^gi)

(2) From the definition of σ [See Definition 2 above]

σ(ζ^gi) = ζ^gi+1 = ζ_i+1

QED

Lemma 4:

if ρ, ω ∈ μ_p

then:

σ(ρω) = σ(ρ)σ(ω)

Proof:

(1) Since ρ, ω ∈ μ_p, there exists i,j such that:

ρ = ζ_i

ω = ζ_j

(2) σ(ρ)σ(ω) = (ζ^gi+1)*(ζ^gj+1) = (ζ^gi)^g*(ζ^gj)^g = (ζ^gi*ζ^gj)^g

(3) There also exists a,b such that:

gⁱ ≡ a (mod p)
g^j ≡ b (mod p)

(4) So that ρ*ω = ζ^a*ζ^b = ζ^a+b

(5) There exists d such that a+b ≡ d (mod p) and 0 ≤ d ≤ p-1 so it follows that ζ^d ∈ μ_p

(6) There exists k such that g^k ≡ d (mod p) so we have:

σ(ρ*ω) = σ(ζ^gk) = ζ^gk+1 = (ζ^gk)^g = (ζ^{a + b})^g = (ζ^{gi + gj})^g = (ζ^gi*ζ^gj)^g

QED

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



Definition 5: σ(f) where f ∈ Q(μ_p)

σ(a₀ζ₀ + ... + a_p-2ζ_p-2) = a₀σ(ζ₀) + ... + a_p-2σ(ζ_p-2)

where a_i ∈ Q and ζ_i ∈ μ_p

Lemma 5: σ is well-defined on the whole of Q(μ_p)

Proof:

This follows from Definition 5 above and Theorem 4, here.

QED

Lemma 6:

The map σ is a field automorphism of Q(μ_p) which leaves every element of Q invariant.

Proof:

(1) σ is bijective . [See Definition 1, here for definition of bijective; see Definition 5 above]

(2) σ(ua + vb) = uσ(a) + vσ(b) for a,b ∈ Q(μ_p) and u,v ∈ Q. [see Definition 5 above]

(3) If a ∈ Q, then using Corollary 1.1, here, we have:

a = (-a)ζ + (-a)ζ² + ... + (-a)ζ^p-1

where ζ is a primitive p-th root of unity

(4) Since each of these ζⁱ corresponds to a different p-th root of unity (see Theorem 3, here), this implies that:

a = (-a)ζ₀ + (-a)ζ₁ + ... + (-a)ζ_p-2

(5) This shows that every rational number is invariant under σ.

(6) Finally: σ(ab) = σ(a)σ(b) where a,b ∈ Q(μ_p) since:

(a) We can define a,b, and ab as summations:

a = ∑ (i=0, p-2) a_iζ_i

b = ∑ (j=0, p-2) b_jζ_j

ab = ∑ (i,j =0, p-2) a_ib_jζ_iζ_j

(b) From Definition 5 above, we have:

σ(ab) = ∑ (i,j=0, p-2) σ(a_ib_jζ_iζ_j)

(c) Since a_i, b_j ∈ Q, we have:

σ(ab) = ∑ (i,j=0, p-2) a_ib_jσ(ζ_iζ_j)

(d) Since ζ_i, ζ_j ∈ μ_p, using Lemma 4 above, we have:

σ(ab) = ∑ (i,j=0, p-2) a_ib_jσ(ζ_i)σ(ζ_j)

(e) Also, using Definition 5 above, we have:

σ(a)σ(b) = [∑ (i=0, p-2) σ(a_iζ_i)][∑ (j=0, p-2) σ(b_jζ_j)]

(f) Since a_i, b_j ∈ Q, we have:

σ(a)σ(b) = [∑ (i=0, p-2) a_iσ(ζ_i)][∑ (j=0, p-2) b_jσ(ζ_j)] =

= ∑ (i,j=0, p-2) a_ib_jσ(ζ_i)σ(ζ_j)

(7) This shows that σ is a field automorphism of Q(μ_p) [See Definition 6, here, for definition of field automorphism]

QED

Definition 6: σ(f) where f ∈ Q(μ_k)(μ_p) where k divides p-1.

σ(a₀ζ₀ + ... + a_p-2ζ_p-2) = a₀σ(ζ₀) + ... + a_p-2σ(ζ_p-2)

where a_i ∈ Q(μ_k) and ζ_i ∈ μ_p

Lemma 7: σ is well-defined on the whole of Q(μ_k)(μ_p)

Proof:

This follows from Definition 6 above and Corollary 3.1, here.

QED

Lemma 8:

The map σ is a field automorphism of Q(μ_k)(μ_p) which leaves every element of Q(μ_k) invariant.

Proof:

(1) σ is bijective . [See Definition 1, here for definition of bijective; see Definition 6 above]

(2) σ(ua + vb) = uσ(a) + vσ(b) for a,b ∈ Q(μ_k)(μ_p) and u,v ∈ Q(μ_k). [see Definition 6 above]

(3) If a ∈ Q(μ_k), then using Corollary 1.1, here, we have:

a = (-a)ζ + (-a)ζ² + ... + (-a)ζ^p-1

where ζ is a primitive p-th root of unity

(4) Since each of these ζⁱ corresponds to a different p-th root of unity (see Theorem 3, here), this implies that:

a = (-a)ζ₀ + (-a)ζ₁ + ... + (-a)ζ_p-2

(5) This shows that every number a ∈ Q(μ_k) is invariant under σ.

(6) Finally: σ(ab) = σ(a)σ(b) where a,b ∈ Q(μ_k)(μ_p) since:

(a) We can define a,b, and ab as summations:

a = ∑ (i=0, p-2) a_iζ_i

b = ∑ (j=0, p-2) b_jζ_j

ab = ∑ (i,j =0, p-2) a_ib_jζ_iζ_j

(b) From Definition 6 above, we have:

σ(ab) = ∑ (i,j=0, p-2) σ(a_ib_jζ_iζ_j)

(c) Since a_i, b_j ∈ Q, we have:

σ(ab) = ∑ (i,j=0, p-2) a_ib_jσ(ζ_iζ_j)

(d) Since ζ_i, ζ_j ∈ μ_p, using Lemma 4 above, we have:

σ(ab) = ∑ (i,j=0, p-2) a_ib_jσ(ζ_i)σ(ζ_j)

(e) Also, using Definition 6 above, we have:

σ(a)σ(b) = [∑ (i=0, p-2) σ(a_iζ_i)][∑ (j=0, p-2) σ(b_jζ_j)]

(f) Since a_i, b_j ∈ Q(μ_k), we have:

σ(a)σ(b) = [∑ (i=0, p-2) a_iσ(ζ_i)][∑ (j=0, p-2) b_jσ(ζ_j)] =

= ∑ (i,j=0, p-2) a_ib_jσ(ζ_i)σ(ζ_j)

(7) This shows that σ is a field automorphism of Q(μ_k)(μ_p) [See Definition 6, here, for definition of field automorphism]

QED

References

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