The Cyclotomic polynomial

After we’ve met the terms of roots of unity, primitive roots, and deduced a great identity, we are now finally ready to define the Cyclotomic polynomial of order . It is the polynomial where it’s roots are the primitive roots of unity of order :

\Phi_n(x)=\prod_{\overset{1\leq k < n}{\text{gcd}(k,n)=1}} (x-\rho_n^k)

Let’s find out what’s so special about it:

First, note that it divides the polynomial , since we can write it as:

x^n-1=\prod_{k=0}^{n-1}(x-\rho_n^k)=(x-1)(x-\rho_n)(x-\rho_n^2)\cdots (x-\rho_n^{n-1})

But we can conclude something stronger, there is a reason for why I have shown the disjoint decomposition in the last post:

\Omega_n=\bigcup_{d|n}\Omega_d^*

(Recall that is the group of roots of unity of order and is the set of the primitive roots of order ) This fact allows us to write the product a bit different:

\overbrace{\prod_{k=0}^{n-1}(x-\rho_n^k)}^{\Omega_n}=\prod_{d|n}\overbrace{\prod_{\overset{1\leq k< d}{(k,d)=1}}(x-\rho_d^k)}^{\Omega_d^{*}}

Pause and ponder on it for a second – make sure that’s clear, since that’s the major key here.

Now, note that the product:

\prod_{\overset{1\leq k< d}{(k,d)=1}}(x-\rho_d^k)

is exactly the definition of the cyclotomic polynomial of order . Therefore:

\prod_{d|n}\prod_{\overset{1\leq k< d}{(k,d)=1}}(x-\rho_d^k)=\prod_{d|n}\Phi_d(x)

And in total we get that:

x^n-1=\prod_{d|n}\Phi_d(x)

Now it’s pretty clear that the cyclotomic polynomial divides , Moreover, we got a recursive definition for it:

x^n-1=\prod_{d|n}\Phi_d(x)=\Phi_n(x)\prod_{\overset{d< n}{d|n}}\Phi_d(x) \\
\\ \Downarrow \\
\Phi_n(x)=\frac{x^n-1}{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}

That’s just great fact:

Note that , and by this fact we can easily calculate the rest of them using with recursion that can be easily implemented in code (it may not be so efficient, but it works)

In addition, since we can easily prove by induction that for every :

The case is trivial. Now suppose that and for every , . Therefore, the quotient:

\frac{\overbrace{x^n-1}^{\in\mathbb{Q}[x]}}{\underbrace{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}_{\in\mathbb{Q}[x]}}

is a raitonal function in , however, this quotient is exactly , which is polynomial, therefore, the quotient is a polynomial with rational coefficents, so as well.

Surprising fact

Let’s calculate the first 5 cyclotomic polynomials:

\Phi_1(x)= x-1\\
\text{}\\ 
\Phi_2(x)= \frac{x^2-1}{x-1}=x+1\\
\text{}\\ 
\Phi_3(x)= \frac{x^3-1}{x-1}=x^2+x+1\\
\text{}\\ 
\Phi_4(x)= \frac{x^4-1}{(x-1)(x+1)}=\frac{x^4-1}{x^2-1}=x^2+1\\
\text{}\\ 
\Phi_5(x)= \frac{x^5-1}{x-1}=x^4+x^3+x^2+x+1\\

That’s pretty interesting… Not only that the coefficients are rationals, but they are integers, maybe it’s not a coincidence, maybe for every :

\Phi_n\in\mathbb{Z}[x]

So as it turns out, it’s true! The cyclotomic polynomials have integer coefficients! That’s incredible! Think about it, that’s not a trivial fact at all! In order to prove it, I want to present Gauss’s lemma:

Gauss’s lemma

So Gauss’s lemma is actually not just one lemma, but two. The first lemma deals with the term of a primitive polynomial – which is a polynomial where the greatest common divisor of it’s coefficients is one. For example the polynomial:

3x^2+6x+9

Is not primitive, since the GCD of it’s coefficients is 3 (=). However, the polynomial

x^2+10x+15

is primitive. It is a monic polymonial – it’s leading coefficient is one, so the GCD of the coefficients has to be one.

Ok, so the first part of the lemma states:

If are primitive polynomials, then their product is also primitive

And the second part states:

If is reducible over the rationals, then it is also reducible over the integers

I am not going to prove the lemmas here, since they are realted to ring theory, and I’ll prove them in a separate post related to ring theory, though the proofs are pretty short.

Now I am going to use the first part of the lemma to prove a statement which from it, it will follow immideatly that the cyclotomic polynomials have integer coefficients.

The statement

Suppose that is a monic polynomial, and there exist two polynomials such that:

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

Then .

The proof

The key here is to note that for every polynomial with rational coefficients, there exists some rational number , such that has integer coefficients and it is primitive.

Why? We can actually construct one in two steps:

First, multiply the polynomial by the common denominator of it’s coefficients. For example:

r(x)=\frac{1}{3}x^2+\frac{1}{6}x+\frac{1}{4} \ \ \ \ /\cdot 24 \\ \Downarrow \\
24\cdot r(x)=8x^2+4x+6

Now, we can divide the new polynomial by the GCD of it’s coefficients – this yields a primitive polynomial. In our example, the GCD is 2, hence:

\frac{24}{2}\cdot r(x)=4x^2+2x+3

And is the number we were looking for.

So after we understand that, let be the rational numbers such that are polynomials with integer coefficients and are also primitive. Therefore, by Gauss’s lemma, their product:

a_g g(x)\cdot a_hh(x)=a_ga_h\cdot g(x)h(x) \in\mathbb{Z}[x]

Is a primitive polynomial as well.

Recall that and is monic, hence the leading coefficient of is . But we know that this is a polynomial with integer coefficients, so is an integer.

Therefore, is a common divisor of the coefficients of the product! Hence, it must be (since it divides the GCD, which is one):

a_ga_h=\pm 1 \\ \Downarrow \\
a_g=\pm1, a_h=\pm 1

Therefore:

\pm g(x), \pm h(x)\in\mathbb{Z}[x] \\ \Downarrow \\
g(x),h(x)\in\mathbb{Z}[x]

As we wanted!

Back to the cyclotomic polynomial

We know that:

\Phi_n(x)=\frac{x^n-1}{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}

Which is the same as:

\overbrace{x^n-1}^{\in\mathbb{Z}[x]\text{ and monic}}=\overbrace{\Phi_n(x)}^{\in\mathbb{Q}[x]}\cdot \overbrace{\prod_{\overset{d< n}{d|n}}\Phi_d(x)}^{\mathbb{Q}[x]}

And this fits perfrectly to what we just proved, hence as we thought!

Is it irreducible?

Our only goal left now is to find out if is irreducible or not. If it is, then it is the minimal polynomial of over , and this fact allows us to finally start talking about Galois theory related things (like what?)

Let’s find out

I am going to prove that it is indeed irreducible, but before I’ll do so, I want to mention few things that we’ll use in the proof:

Primitive root to the power of a prime number

First, note that if is a primitive root of unity of order ,so for any prime that doesn’t divide , is also a primitive root of unity:

Suppose not, then there exists some such that:

(\rho^p)^r=\rho^{pr}=1=(\rho^{n})^m=\rho^{nm}\ \text{  for every }m\in\mathbb{N}

So there exists some such that

Recall that is a divisor of (lagrange’s theorem…) so there exists some such that:

n=kr \\ \Downarrow \\
pr=nm=kr\cdot m  \ /:r \\
\\ \Downarrow \\
p=km

But is prime, so or . If , then , and that’s a contradiction to being smaller than . If , then , and we get that and that’s a contradiction since doesn’t divide .

Therefore, no such exists, and is indeed a primitive polynomial.

Polynomial over

Recall that over the field , the identity is true. Moreover, by fermat’s little theorem, for every : over . Therefore, if is a polynomial, then, over :

\overline{h}(x^p)=(x^k)^p+a_{n-1}(x^{k-1})^p+\cdots +a_0\overset{\text{Fermat}}{=}(x^k)^p+a_{n-1}^p(x^{k-1})^p+\cdots +a_0^p

= (x^k)^p+(a_{n-1}x^{k-1})^p+\cdots +a_0^p\overset{(a+b)^p}{=}(x^k+a_{n-1}x^{k-1}+\cdots a_0)^p=(\overline{h}(x))^p

And that’s a useful property we will use in the proof.

Separablility of over

Recall that we’ve proved in this post that if the derivative of is not 0 over a field , then it is separable over .

So let’s see if is separable over , where doesn’t divide :

(x^n-1)^\prime=\underbrace{n}_{(n,p)=1}\cdot x^{n-1}\neq 0\in\mathbb{F}_p

So it is indeed separable over .

The proof

Aimining for contradiction. suppose that is reducible over , so by the second part of Gauss’s lemma, it is also reducible over .

Now, let be polynomials such that:

\Phi_n(x)=g(x)h(x)

And we can pick them both to be monic, and we can also also assume that is irreducible (why?)

Note that Some primitve roots of unity of order are roots of , and the others are roots of .

Let be a root of , and let be any prime that doesn’t divide . Note that is also a primitive root by what we’ve proved above. Now there are two cases:

For every such , is a root of

Then we can conclude that every such that , must be a root of as well:

Indeed, we can write where the -s are primes that doesn’t divide (if some of them divide , then have a common factor). So, is a primitive root, and by the assumption of this case, it is a root of .

Similarly, is a root of , and so on… Until we get that is a root of .

Therefore, every primitive root of unity of order must be a root of ! so (they have the same roots, and one divides the other) Moreover, by our assumption, is irreducible, then so as as we wanted.

There exists some where is a root of

That is, , which is equivalent to being a root of the polynomial . However, is irreducible, thus, it is the minimal polynomial of . So must divide . In other words, there exists some such that:

h(x^p)=g(x)r(x)

However, is monic, hence primitive with integer coefficients. So by the statement we proved, we know that , and now we can reduce the equation modulo :

\overline{h}(x^p)=\overline{g}(x)\overline{r}(x) \ \ \ \text{ in }\mathbb{F}_{p}

However, we’ve seen that , thus:

(\overline{h}(x))^p=\overline{g}(x)\overline{r}(x) \ \ \ \text{ in }\mathbb{F}_{p}

Therefore, and have a common factor over (you can decompose into irrdeucible factors over since it is a UFD, so one factor must be a factor of , but it is a factor of as well)

Now, note that

\overline{\Phi}_n(x)=\overline{g}(x)\overline{h}(x) \ \ \ \text{in }\mathbb{F}_p

But since and have a common factor, has a mutiple root over . However, it divides over so has a mutiple root, but that’s a contradiction of it being separable.

Therefore, such case is impossible, hence, is irreducible, as we wanted!

The splitting field

Yes! Finally we’ve proved everything we wanted to prove about the cyclotomic polynomial. Now it’s time for some Galois theory:

It’s not hard to see that is the splitting field of the cyclotomic polynomial, which is separable. Thus, the extension is Galois. Moreover, it is a simple extension, and it’s degree is exactly the degree of the cyclotomic polynomial – . Therefore, the order of the galois group is as well (Recall that is Euler totient function).

Since the roots of are exactly the primitive roots of order , and the automorphisms in the galois group does a permutation on the roots of , we can conclude that the automorphisms map a primitive root of unity to another primitive root of unity.

However, since the extension is simple, every automorphism is defined entirely by the image of . Therefore, the automorphisms are exactly those of the form:

\sigma_k:\rho_n\mapsto \rho_n^k

Where is a primitive root of unity of order (in other words, ).

The Galois group

Those facts allow us to fully identify the Galois group of the extension. We can define an isomorphism from Euler group of order – which is denoted as or , and defined as the set:

U_n=\{1\leq k< n:(k,n)=1\}

equipped with the action of multiplication modulo to

The isomorphism now is pretty clear:

f:U_n\to \text{Gal}(\mathbb{Q}(\rho_n)/\mathbb{Q})\\
k\mapsto \sigma_k

I won’t even bother proving that it is indeed an isomorphism…

Let’s see an exmaple:

The extension

We’ve already seen what the roots of unity of are:

\color{purple}\rho_{12}^0=\rho_1=1\ (\text{order 1})
\\
\text{}\\
\color{blue} \rho_{12}^6=\rho_2=-1 \ (\text{order 2})
\\
\text{}\\
\color{green} \rho_{12}^{4}=\rho_3, \rho_{12}^{8}=\rho_3^2 \ (\text{order 3})
\\
\text{}\\
\color{orange} \rho_{12}^{3}=\rho_4, \rho_{12}^{9}=\rho_4^3 \ (\text{order 4})
\\
\text{}\\
\color{red} \rho_{12}^2=\rho_6, \rho_{12}^{10}=\rho_6^5 \ (\text{order 6})
\\
\text{}\\
\color{black}\rho_{12},\rho_{12}^5,\rho_{12}^7,\rho_{12}^{11} \ (\text{order 12})
\\

So , and there are exactly automorphisms, and the group is of order 4. Well, there aren’t that much options for the group – it can one of the following:

\mathbb{Z}_4, V_4=\mathbb{Z}_2\times\mathbb{Z}_2

So all we have to do in order to deteremine which group it is exaclty, is to check whether or not is cyclic. We’ll the group is:

U_{12}=\{1,5,7,11\}

Let’s see if is a genarator:

5^1\equiv 5 \ (\text{mod }12)\\
5^2\equiv 25\equiv 1 \ (\text{mod }12)\\

So 5 is of order 2, similarly, 7 and 11 are both of order 2. Hence, the group is not cyclic, thus:

\text{Gal}(\mathbb{Q}(\rho_{12})/\mathbb{Q})\cong V_4

Let’s identify the roots as:

1\leftrightarrow \rho_{12} \\
\text{} \\ 
2\leftrightarrow \rho_{12}^{5} \\
\text{} \\ 
3\leftrightarrow \rho_{12}^{7}\\ 
\text{} \\ 
4\leftrightarrow \rho_{12}^{11}

We need to match each automorphism to a premutation – however, we can do it in clever way – note that each automorphism maps to one of the other roots. Since the automorphisms are all of order 2 (as elements of ), we have to map the image of back to . The other two roots are being mapped to each other as well (why?). So the automorphisms are:

(1\ 2 )(3\ 4) \\
(1\ 3)(2\ 4) \\
(1\ 4)(2\ 3)

And the subgroup lattice is:

The sub-fields

Now we would like to calculate the sub-fields, and since the extension is galois – the subfields are all fixed fields.

Let’s start with : Note that:

\sigma(\rho_{12}+\rho_{12}^5)=\sigma(\rho_{12})+\sigma(\rho_{12}^5)=\rho_{12}^5+\rho_{12} \\ \Downarrow \\
\rho_{12}+\rho_{12}^5\in\mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}

Moreover:

\rho_{12}+\rho_{12}^5=(\cos {\frac{2\pi}{12}}+i\sin\frac{2\pi}{12})+(\cos {\frac{2\pi\cdot 5}{12}}+i\sin\frac{2\pi\cdot 5}{12})

=(\cos {\frac{\pi}{6}}+i\sin\frac{\pi}{6})+(\cos {\frac{5\pi}{6}}+i\sin\frac{5\pi}{6})

=(\cos {\frac{\pi}{6}}+\cos {\frac{5\pi}{6}})+i(\sin\frac{\pi}{6}+\sin\frac{5\pi}{6})

Recall that and . So:

=0+i(2\sin\frac{\pi}{6})=2\sin\frac{\pi}{6}\cdot i

And is :

Therefore, we conclude that:

\rho_{12}+\rho_{12}^5=i

So, in total we get that:

\mathbb{Q}(i)=\mathbb{Q}(\rho_{12}+\rho_{12}^{5})\sube \mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}

However, by the fundamental theorem:

[\mathbb{Q}(i):\mathbb{Q}]{=}2=[V_4:\langle (1\ 2)(3\ 4)\rangle]\overset{\text{fund.thm.}}{=}[\mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}:\mathbb{Q}]

Therefore, the fields (degrees) are the same and we conclude that:

\mathbb{Q}(i)= \mathbb{Q}^{\langle (1\ 2)(3\ 4)\rangle}

In a similar way we get that:

\mathbb{Q}(\sqrt{3})\overset{(\text{why?})}{=}\mathbb{Q}(\cos \frac{\pi}{6})=\mathbb{Q}^{\langle (1\ 4)(2\ 3)\rangle}

(Try it! Hint: check if the element is being fixed under the automorphism ). For the fixed field we need to be a bit more creative – we’ll pick the element:

\rho_{12}^{}\cdot\rho_{12}^{7}=\rho_{12}^8

This one is indeed being fixed under the automorphism , moreover:

\rho_{12}^8=\cos\frac{2\pi\cdot 8}{12}+i\sin\frac{2\pi\cdot 8}{12}=\cos\frac{4\pi}{3}+i\sin\frac{4\pi}{3}

=-\cos\frac{\pi}{3}+i\sin\frac{\pi}{3}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}

So:

\mathbb{Q}(\sqrt{3}i)=\mathbb{Q}(-\frac{1}{2}+i\frac{\sqrt{3}}{2})\sube\mathbb{Q}^{\langle (1\ 3)(2\ 4)\rangle}

And in a similar way to before, we can compare the degrees of the extensions and conclude that:

\mathbb{Q}(\sqrt{3}i)=\mathbb{Q}^{\langle (1\ 3)(2\ 4)\rangle}

That’s it!

Note that in fact, ,

Summary

Ok, so we’ve met the cyclotomic polynimial and the cyclotomic extensions. As we’ve seen, they have beautiful properties – they have integer coefficients, they are irreducible, and we can compute them recursively.

However, that’s not going to be the last time we’ll see them. As I said, those polynomials, and those extension are so useful – and that’s great, since I am huge fan of them!