Notes on Cyclotomic Polynomial

(This is a work in progess...)

Nth roots of Unity

n^{th} roots of unity is given by the equation:
\large (1)^{1\over n}=e^{i\frac{2k\pi}{n}}, \large k=0,1,\dots,n-1

Applet for visualizing nth roots of unity

Nth Cyclotomic Polynomial

n^{th} cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of x^{n}-1 and is not a divisor of x^{k}-1 for any k < n.

Its roots are all n^{th} primitive roots of unity e^{2i\pi {\frac{k}{n}}}, where 1\le k\le n and k & n are coprime. 

\large \Phi_{n}(x)=\prod_{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(x-e^{2i\pi {\frac {k}{n}}}\right)

It may also be defined as the monic polynomial with integer coefficients that is the minimal polynomial  over the field of the rational numbers of any primitive nth-root of unity.

In short, \Phi_{n}(x)|x^n-1, but \Phi_{n}(x)\not|x^k-1, for k=0,\dots,n-1.

Relation linking cyclotomic polynomials & primitive roots of unity

\prod_{d\mid n}\Phi_{d}(x)=x^{n}-1

That is,  x is a root of x^n - 1 if and only if it is  a dth primitive roots of unity for some d that divides n.

GAP experiment to understand this relationship:

gap> x:=Indeterminate(Rationals,"x");
x
gap> C1:=CyclotomicPolynomial(Rationals,1);
x-1
gap> C2:=CyclotomicPolynomial(Rationals,2);
x+1
gap> C3:=CyclotomicPolynomial(Rationals,3);
x^2+x+1
gap> C4:=CyclotomicPolynomial(Rationals,4);
x^2+1
gap> C6:=CyclotomicPolynomial(Rationals,6);
x^2-x+1
gap> C12:=CyclotomicPolynomial(Rationals,12);
x^4-x^2+1
gap> (x^12-1)/C12;
x^8+x^6-x^2-1
gap> C1*C2*C3*C4*C6*C12;
x^12-1
gap> C1*C2*C3*C4*C6;
x^8+x^6-x^2-1

Interesting fact:

While \Phi_{n}(x) uses complex number in its definition, it produces irreducible polynomial over integer coefficients.
That is while \Phi:\mathbb{Z}\to\mathbb{Z}, it is defined using a c\in\mathbb{C} in its definition.

Closer inspection reveals this is because of symmetry (look at the applet for nth root). One of the root will always be 1, and when n is even there is another root which is -1. The other roots will be conjugate of each other in pairs.
And when n is odd one of the nth root will be 1, while other roots occurring as conjugates in pairs.

When you multiply or add two complex conjugates, it always produces real numbers.  (Incomplete...).

When n is prime:

If n is a prime number, then
\Phi_{n}(x)=1+x+x^{2}+\cdots +x^{n-1}
=\sum_{k=0}^{n-1}x^{k}.

If n = 2p where p is an odd prime number, then
\Phi_{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}
=\sum_{k=0}^{p-1}(-x)^{k}.

Cyclotomic Polynomials upto n=41

\Phi_{1}(x)=x-1

\Phi_{2}(x)=x+1

\Phi_{3}(x)=x^{2}+x+1

\Phi_{4}(x)=x^{2}+1

\Phi_{5}(x)=x^{4}+x^{3}+x^{2}+x+1

\Phi_{6}(x)=x^{2}-x+1

\Phi_{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi_{8}(x)=x^{4}+1

\Phi_{9}(x)=x^{6}+x^{3}+1

\Phi_{10}(x)=x^{4}-x^{3}+x^{2}-x+1

\Phi_{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi_{12}(x)=x^{4}-x^{2}+1

\Phi_{13}(x)=x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi_{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi_{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1

\Phi_{16}(x)=x^{8}+1

\Phi_{17}(x)=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{18}(x)=x^{6}-x^{3}+1

\Phi_{19}(x)=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi_{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1

\Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1

\Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi _{23}(x)=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi_{24}(x)=x^{8}-x^{4}+1

\Phi_{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1

\Phi_{26}(x)=x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi_{27}(x)=x^{18}+x^{9}+1

\Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1

\Phi _{29}(x)=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1

\Phi _{31}(x)=x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{32}(x)=x^{16}+1

\Phi _{33}(x)=x^{20}-x^{19}+x^{17}-x^{16}+x^{14}-x^{13}+x^{11}-x^{10}+x^9-x^7+x^6-x^4+x^3-x+1

\Phi _{34}(x)=x^{16}-x^{15}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi _{35}(x)=x^{24}-x^{23}+x^{19}-x^{18}+x^{17}-x^{16}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^{8}+x^{7}-x^{6}+x^{5}-x+1

\Phi_{36}(x)=x^{12}-x^{6}+1

\Phi_{37}(x)=x^{36}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi_{38}(x)=x^{18}-x^{17}+x^{16}-x^{15}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi_{39}(x)=x^{24}-x^{23}+x^{21}-x^{20}+x^{18}-x^{17}+x^{15}-x^{14}+x^{12}-x^{10}+x^{9}-x^{7}+x^{6}-x^{4}+x^{3}-x+1

\Phi_{40}(x)=x^{16}-x^{12}+x^{8}-x^{4}+1

\Phi_{41}(x)=x^{40}+x^{39}+x^{38}+x^{37}+x^{36}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}+x^{30}+x^{29}+x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

Share This:

Leave a Reply