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

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, -1}
μ₃ = {1, (1/2)[-1 + √-3], 1/2)[-1 - √-3])
μ₄ = {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 = { ρ₁, ..., ρ_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, ζ, ζ², ..., ζ^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:

a₀ + a₁u + a₂u² + ... + a_d-1u^d-1 with a_i ∈ 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:

a₀ + a₁u + ... + a_d-1u^d-1

with a_i ∈ F

(10) Now, I will prove uniqueness.

(11) Assume that:

a₀ + a₁u + ... + a_d-1u^d-1 = b₀ + b₁u + ... + b_d-1u^d-1

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

V(X) = (a₀ - b₀) + (a₁ - b₁)X + ... + (a_d-1 - b_d-1)X^d-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:

a₀ - b₀ = a₁ - b₁ = ... = a_d-1 - b_d-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:

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

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

for some a_i ∈ Q.

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

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

which means that:

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

(6) This gives us that:

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

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

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

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

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

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

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

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

(11) From Lemma 3 above, 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

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 = X^t + c_t-1X^t-1 + ... + c₁X + c₀ ∈ Z[X]

If there is a prime number p which divides c_i for i = 0, ..., t-1 but p² does not divide c₀

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 = Xⁿ + a_n-1X^n-1 + ... + a₁X + a₀ ∈ Z[X]

g = X_m + b_m-1X^m-1 + ... + b₁X + b₀ ∈ Z[X]

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

(5) From step #2, it is also clear that c₀ = a₀*b₀

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

(7) It is also clear that since p² does not divide c₀ that p cannot divide both a₀ and b₀.

(8) We can assume that p divides a₀ but not b₀ (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 a_i. It is clear that 0 ≤ i ≤ n-1. So, we can conclude that for any i, p divides a₀, a₁, ..., a_i.

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

(11) So:

c_i+1 = a_i+1b₀ + a_ib₁ + a_i-1b₂ + ... + a₀b_i+1.

where b_j = 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 c_i+1. [From the given in the theorem that p divides c₀, ..., c_t-1]

(14) So, from step #13, it follows that since p divides c_i+1 and p divides a₀, a₁, ..., a_i [step #9] that p must also divide a_i+1b₀.

(15) But this is impossible since p doesn't divide b₀ (step #8) and p doesn't divide a_i+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) = x^p-1 + x^p-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) = (x^p - 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 p² does not divide the last coefficient (p² does not divide p.)

QED

References

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