Gauss and Regular Polygons: Cyclotomic Polynomials

Introduction

The word "Cyclotomy" literally means "cutting a circle". So the subtitle of the post suggests that the post is going to be about some polynomials which are related to cutting a circle. Cutting a circle actually refers to dividing a given circle into a number of arcs of same length. Supposing that we are able to divide a given circle into, say $n$, arcs of equal length by means of points $P_{0}, P_{1}, \ldots, P_{n - 1}$ then joining the adjacent points we obtain a regular polygon $P_{0}P_{1}\ldots P_{n - 1}$ of $n$ sides. Therefore cyclotomic polynomials are somehow related to the construction of regular polygons.

In the previous post about complex numbers, we were able to establish that construction of a regular polygon of $n$ sides requires finding complex numbers $z$ such that $z^{n} = 1$. Thus we need to solve the equation $$z^{n} - 1 = 0\tag{1}$$ One trivial solution is $z = 1$, but we are rather interested in solutions other than $z = 1$. All the solutions of the above equation are said to be $n^{th}$ roots of unity. So how do we go about finding these $n^{th}$ roots of unity?

Obviously we need to factorize the expression $z^n - 1$ and then find any linear factors if possible. For $n = 4$ we can proceed as follows: $$\begin{align} &z^4 - 1 = 0\notag\\ &\Rightarrow (z^2 - 1)(z^2 + 1) = 0\notag\\ &\Rightarrow (z - 1)(z + 1)(z^2 + 1) = 0\notag\\ &\Rightarrow z = 1,\,\, z = -1,\,\, z^2 + 1 = 0\notag\\ &\Rightarrow z = 1,\,\,z = -1,\,\,z^2 = -1\notag\\ &\Rightarrow z = 1,\,\,z = -1,\,\,z = i,\,\,z = -i\notag \end{align}$$ Therefore we see that factorization of the polynomial $z^{n} - 1$ is the key to finding $n^{th}$ roots of unity. This is exactly where cyclotomic polynomials come into play. Cyclotomic polynomials are the irreducible factors of the polynomial $z^{n} - 1$. More precisely we have the following definition:
For any given positive integer $n$, the $n^{th}$ cyclotomic polynomial, denoted by $\Phi_{n}(z)$, is that irreducible factor (over field of rationals) of polynomial $z^{n} - 1$ which is not a factor of any polynomial $z^{m} - 1$ where $m < n$.

(Note to the not so casual reader: It will be proved later in this post that there will be one and only one such irreducible factor which is not the factor of any $z^{m} - 1$ with $m < n$.)
For $n = 1$, it is clear that $\Phi_{1}(z) = z - 1$. For $n = 2$, we have $$z^{2} - 1 = (z - 1)(z + 1)$$ and since $(z - 1)$ is already used up in factorization for case $n = 1$, $\Phi_{2}(z) = z + 1$.

For $n = 3$, $z^3 - 1 = (z - 1)(z^2 + z + 1)$ and the factor $z^2 + z + 1$ is irreducible so that $\Phi_{3}(z) = z^{2} + z + 1$. Similarly $\Phi_{4}(z) = z^2 + 1$.

Primitive $n^{th}$ Roots of Unity

The complex number $\zeta = \cos(2\pi / n) + i\sin(2\pi / n)$ is obviously an $n^{th}$ root of unity since $$\zeta^{n} = \cos\left(n \cdot \frac{2\pi}{n}\right) + i\sin\left(n \cdot\frac{2\pi}{n}\right) = \cos(2\pi) + i\sin(2\pi) = 1$$ Now consider the powers of $\zeta$. For each $k, 0 \leq k < n, \zeta^{k}$ is also an $n^{th}$ root of unity as $(\zeta^{k})^{n} = (\zeta^{n})^{k} = 1^{k} = 1$. Also each of these powers of $\zeta$ is distinct from another, i.e. $\zeta^{l} \neq \zeta^{k}, 0\leq k, l < n$ if $l \neq k$. Thus the numbers $1, \zeta, \zeta^{2}, \ldots, \zeta^{n - 1}$ are all the "n" $n^{th}$ roots of unity.

Consider any such $n^{th}$ root say $\zeta^{k}, 0 < k < n$. Obviously we have $$\zeta^{k} = \cos\left(\frac{2k\pi}{n}\right) + i\sin\left(\frac{2k\pi}{n}\right)$$ If $k$ and $n$ have a common factor we can reduce the fraction $k / n$ into another fraction, say $l / m$, where $m < n,\, l < k$. Then it follows that $$\zeta^{k} = \cos\left(\frac{2l\pi}{m}\right) + i\sin\left(\frac{2l\pi}{m}\right)$$ is also an $m^{th}$ root of unity for some $m < n$. Clearly we are not interested in such repeated roots (i.e. they occur as smaller roots of unity), but would rather like to focus on those $n^{th}$ roots of unity which are not the $m^{th}$ roots of unity for any $m < n$. These are obtained as $\zeta^{k}$ where $k$ and $n$ do not have any common factor, i.e. when $k$ is coprime to $n$. Such $n^{th}$ roots of unity are called the primitive $n^{th}$ roots of unity. What we have achieved above can be stated as follows:
The primitive $n^{th}$ roots of unity are $\zeta^{k}$ where $1 \leq k < n$, $k$ is coprime to $n$ and $$\zeta = \cos\left(\frac{2\pi}{n}\right) + i\sin\left(\frac{2\pi}{n}\right)$$ The number of positive integers $k < n$ and coprime to $n$ is denoted by $\phi(n)$ and is called the Euler's totient function. Also $\phi(1)$ is defined to be $1$. Thus the number of primitive $n^{th}$ roots of unity is $\phi(n)$. From elementary number theory the following are easily deduced:

1. $\phi(mn) = \phi(m)\phi(n)$ if $m$ is coprime to $n$.
2. $\phi(p^{k}) = p^{k} - p^{k - 1}$ where $p$ is a prime number.
3. $\displaystyle \phi(n) = n\left(1 - \frac{1}{p_{1}}\right)\left(1 - \frac{1}{p_{2}}\right)\cdots\left(1 - \frac{1}{p_{k}}\right)\,\,\,$ where $p_{1}, p_{2}, \ldots, p_{k}$ are all the distinct prime factors of $n$.

Primitive $n^{th}$ Roots and Cyclotomic Polynomials

Let us consider the polynomial $$P_{n}(z) = \prod_{1 \leq k \leq n, (k, n) = 1}(z - \zeta^{k})$$ where $(k, n)$ refers to the GCD (greatest common divisor) of $k$ and $n$. Note that in the above expression $\zeta$ can be taken as any of $\phi(n)$ primitive roots (this is easy to establish if one understands the fact that the positive integers less than $n$ and coprime to $n$ form a group under modulo $n$ multiplication). Thus the polynomial $P_{n}(z)$ has as its roots all the primitive $n^{th}$ roots of unity. We will now identify it with the cyclotomic polynomial $\Phi_{n}(z)$ by proving that $P_{n}(z)$ is an irreducible polynomial with integral coefficients.

We first establish that $P_{n}(z)$ has integer coefficients. To do so we will establish the following: $$z^{n} - 1 = \prod_{d \mid n}P_{d}(z)\tag{2}$$ Since any $n^{th}$ root of unity is of the form $$\cos\left(\frac{2k\pi}{n}\right) + i\sin\left(\frac{2k\pi}{n}\right)$$ and we can replace $k / n$ with a fraction $c / d$ in lowest terms so that $d \mid n$, it follows that any $n^{th}$ root of unity is a primitive $d^{th}$ root of unity for some divisor $d$ of $n$ and vice-versa. Also if $d_{1}$ and $d_{2}$ are two distinct divisors of $n$ then none of primitive $d_{1}^{th}$ roots of unity is a primitive $d_{2}^{th}$ root of unity. Thus the above factorization of $(z^{n} - 1)$ as a product of polynomials $P_{d}(z)$ is proved.

The above factorization (2) can be used to prove that $P_{n}(z)$ has integer coefficients. Clearly $P_{1}(z) = z - 1$ and we can apply induction by assuming that $P_{k}(z)$ has integer coefficients for $k < n$. Then we have $$P_{n}(z) = \frac{z^{n} - 1}{\prod\limits_{d \mid n,\, d < n}P_{d}(z)} = \frac{z^{n} - 1}{g(z)}$$ where $g(z)$ is a polynomial with integer coefficients and leading coefficient $1$ (by induction hypothesis). It follows by Gauss Lemma that $P_{n}(z)$ has integer coefficients.

We next establish that $P_{n}(z)$ is irreducible over the field of rationals.
The proof which follows is the one provided by Gauss and it uses modular arithmetic in very ingenious way. We will summarize the results needed as follows:

1. For a given prime $p$, the numbers $0, 1, 2, \ldots, (p - 1)$ form a finite field under the operations of modulo addition and multiplication modulo $p$.
2. Since these numbers form a field, say $F_{p}$, we can talk about polynomials $f(z)$ whose coefficients are in $F_{p}$. The set of all such polynomials, say $F_{p}[z]$, has the unique factorization property i.e. any such polynomial can be factored as a product of irreducible polynomials in $F_{p}[z]$ in a unique way apart from the order of the factors. The proof is same as that used for normal polynomials with rational coefficients.
3. If $f(z)$ is a polynomial in $F_{p}[z]$ then $\{f(z)\}^{p} = f(z^{p})$. This is true for constant polynomials by Fermat's theorem which says that $a^{p} \equiv a\,\,\text{mod} (p)$. For higher degree polynomials this is achieved by induction by writing $f(z) = az^{n} + g(z)$ and using binomial theorem to raise both sides to power $p$. In so doing we only need to note that the binomial coefficients involved are divisible by $p$.

The proof of irreducibility of $P_{n}(z)$ is done in two stages:

Stage 1:

Let $\zeta$ be a primitive $n^{th}$ root of unity and let $f(z)$ be its minimal polynomial i.e. $f(z)$ is monic (leading coefficient $1$), has rational coefficients and irreducible and $f(\zeta) = 0$. Since $\zeta$ is also a root of $z^{n} - 1 = 0$, it follows that $f(z)$ divides $(z^{n} - 1)$ and by Gauss Lemma $f(z)$ has integer coefficients as well. We now establish the following:
If $p$ is any prime which does not divide $n$ then $\zeta^{p}$ is a root of $f(z) = 0$.

Proof: Since $\zeta$ is also a root of $P_{n}(z) = 0$ it follows that $f(z)$ divides $P_{n}(z)$. Thus we have $P_{n}(z) = f(z)g(z)$ where $g(z)$ is also monic and has integer coefficients (by Gauss Lemma). Since $p$ is coprime to $n$ it follows that $\zeta^{p}$ is also a primitive $n^{th}$ root. And therefore $P_{n}(\zeta^{p}) = 0$.

Assuming that $\zeta^{p}$ is not a root of $f(z) = 0$ (otherwise there is nothing to prove), we see that it must be a root of $g(z) = 0$. Therefore $\zeta$ is a root of $g(z^{p}) = 0$. Since $f(z)$ is the minimal polynomial of $\zeta$, it follows that $f(z)$ divides $g(z^{p})$ so that $g(z^{p}) = f(z)h(z)$ where $h(z)$ is monic with integer coefficients. Also since $P_{n}(z)$ is a factor of $(z^n - 1)$ so that we have $z^{n} - 1 = P_{n}(z)d(z)$ where $d(z)$ is again monic with integer coefficients. We thus have the following equations: $$z^{n} - 1 = f(z)g(z)d(z)\tag{3}$$ $$g(z^{p}) = f(z)h(z)\tag{4}$$ We now apply the modulo $p$ operation to each of the equations above, i.e. we replace each coefficient in the polynomials involved with its remainder when it is divided by $p$. The resulting polynomials are all in $F_{p}[z]$ and we will use the same letters to denote them. So the above equations are now to be interpreted as relations between some polynomials in $F_{p}[z]$. The second equation can now be equivalently written as $$\{g(z)\}^{p} = f(z)h(z)\tag{5}$$ Let $k(z)$ in $F_{p}[z]$ be an irreducible factor of $f(z)$. Then from the above equation (5), $k(z)$ divides $\{g(z)\}^{p}$ and so divides $g(z)$. Thus from equation $(3)$ the polynomial $\{k(z)\}^{2}$ divides $(z^{n} - 1)$. Thus $(z^n - 1)$ has repeated factors and therefore $(z^{n} - 1)$ and its derivative $nz^{n - 1}$ must have a common factor. Since $n$ is coprime to $p$, therefore the derivative $nz^{n - 1}$ is non-zero polynomial and it clearly does not have any common factor with $(z^{n} - 1)$.

We have reached a contradiction and therefore the initial assumption that $\zeta^{p}$ is not the root of $f(z) = 0$ is wrong. The result is now proved.

Stage 2:

We have thus established that if $f(z)$ is the minimal polynomial for any primitive $n^{th}$ root of unity then for any prime $p$ not dividing $n$, $\zeta^{p}$ (which is again a primitive $n^{th}$ root) is also a root of $f(z) = 0$. And since $f(z)$ is irreducible and monic, it will act as minimal polynomial for the primitive root $\zeta^{p}$.

The same logic can be applied repeatedly and we will get the result that $f(z)$ is the minimal polynomial for $\zeta^{p_{1}p_{2}\ldots p_{m}}$ where $p_{1}, p_{2}, \ldots, p_{m}$ are any primes not dividing $n$. It follows that $\zeta^{k}$ where $k$ is coprime to $n$ is also a root of $f(z)$. Thus all the primitive $n^{th}$ roots of unity are roots of $f(z) = 0$. Hence $P_{n}(z)$ divides $f(z)$. Since $f(z)$ is irreducible it follows that $f(z) = P_{n}(z)$ (both $f(z)$ and $P_{n}(z)$ are monic). We thus have established that $P_{n}(z)$ is irreducible.

Moreover since the roots of $P_{n}(z) = 0$ are not the roots  of any $z^{m} - 1 = 0$ for $m < n$, it follows that $P_{n}(z)$ is the irreducible factor of $(z^{n} - 1)$ which is not the factor of any $z^{m} - 1$ for $m < n$. And thus by our definition of cyclotomic polynomials we have $P_{n}(z) = \Phi_{n}(z)$. We have also justified the note about our definition of cyclotomic polynomials.

What we have achieved here can be summarized as:
The roots of the polynomial equation $\Phi_{n}(z) = 0$ are precisely the $\phi(n)$ primitive $n^{th}$ roots of unity.

And thus the degree of $\Phi_{n}(z)$ is $\phi(n)$. Also since $\Phi_{n}(z)$ is irreducible, we get:
$\Phi_{n}(z)$ is the minimal polynomial for each of the primitive $n^{th}$ roots of unity.

The ground work in the theory of cyclotomic polynomials is now complete and we can then turn towards solving the cyclotomic equation $\Phi_{n}(z) = 0$. The solution as provided by Gauss is beautiful, but somewhat involved and will therefore be divided into multiple posts.

Print/PDF Version