Contents

Cyclotomic polynomial

${\displaystyle \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 (${\displaystyle e^{2i\pi /n}}$ is an example of such a root).

An important relation linking cyclotomic polynomials and primitive roots of unity is

${\displaystyle \prod _{d\mid n}\Phi _{d}($x)=x^{n}-1,}

showing that x is a root of ${\displaystyle x^{n}-1}$ if and only if it is a d th primitive root of unity for some d that divides n.^[1]

Examples[edit]

Ifn is a prime number, then

${\displaystyle \Phi _{n}($x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.}

Ifn = 2p where p is a prime number other than 2, then

${\displaystyle \Phi _{2p}($x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.}

For n up to 30, the cyclotomic polynomials are:^[2]

${\displaystyle {\begin{aligned}\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}\\&\qquad \quad +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}\\&\qquad \quad +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.\end{aligned}}}

The case of the 105th cyclotomic polynomial is interesting because 105 is the least positive integer that is the product of three distinct odd prime numbers (3*5*7) and this polynomial is the first one that has a coefficient other than 1, 0, or −1:^[3]

${\displaystyle {\begin{aligned}\Phi _{105}($x)={}&x^{48}+x^{47}+x^{46}-x^{43}-x^{42}-2x^{41}-x^{40}-x^{39}+x^{36}+x^{35}+x^{34}\\&{}+x^{33}+x^{32}+x^{31}-x^{28}-x^{26}-x^{24}-x^{22}-x^{20}+x^{17}+x^{16}+x^{15}\\&{}+x^{14}+x^{13}+x^{12}-x^{9}-x^{8}-2x^{7}-x^{6}-x^{5}+x^{2}+x+1.\end{aligned}}}

Properties[edit]

Fundamental tools[edit]

The cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers. Except for n equal to 1 or 2, they are palindromes of even degree.

The degree of ${\displaystyle \Phi _{n}}$, or in other words the number of nth primitive roots of unity, is ${\displaystyle \varphi ($n)} , where ${\displaystyle \varphi }$isEuler's totient function.

The fact that ${\displaystyle \Phi _{n}}$ is an irreducible polynomial of degree ${\displaystyle \varphi ($n)} in the ring ${\displaystyle \mathbb {Z} [$x]} is a nontrivial result due to Gauss.^[4] Depending on the chosen definition, it is either the value of the degree or the irreducibility which is a nontrivial result. The case of prime n is easier to prove than the general case, thanks to Eisenstein's criterion.

A fundamental relation involving cyclotomic polynomials is

${\displaystyle {\begin{aligned}x^{n}-1&=\prod _{1\leqslant k\leqslant n}\left(x-e^{2i\pi {\frac {k}{n}}}\right)\\&=\prod _{d\mid n}\prod _{1\leqslant k\leqslant n \atop \gcd(k,n)=d}\left(x-e^{2i\pi {\frac {k}{n}}}\right)\\&=\prod _{d\mid n}\Phi _{\frac {n}{d}}($x)=\prod _{d\mid n}\Phi _{d}(x).\end{aligned}}}

which means that each n-th root of unity is a primitive d-th root of unity for a unique d dividing n.

The Möbius inversion formula allows ${\displaystyle \Phi _{n}($x)} to be expressed as an explicit rational fraction:

${\displaystyle \Phi _{n}($x)=\prod _{d\mid n}(x^{d}-1)^{\mu \left({\frac {n}{d}}\right)},}

where ${\displaystyle \mu }$ is the Möbius function.

The cyclotomic polynomial ${\displaystyle \Phi _{n}($x)} may be computed by (exactly) dividing ${\displaystyle x^{n}-1}$ by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:

${\displaystyle \Phi _{n}($x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d<n}}}\Phi _{d}(x)}}}

(Recall that ${\displaystyle \Phi _{1}($x)=x-1} .)

This formula defines an algorithm for computing ${\displaystyle \Phi _{n}($x)} for any n, provided integer factorization and division of polynomials are available. Many computer algebra systems, such as SageMath, Maple, Mathematica, and PARI/GP, have a built-in function to compute the cyclotomic polynomials.

Easy cases for computation[edit]

As noted above, if n is a prime number, then

${\displaystyle \Phi _{n}($x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}\;.}

Ifn is an odd integer greater than one, then

${\displaystyle \Phi _{2n}($x)=\Phi _{n}(-x)\;.}

In particular, if n = 2p is twice an odd prime, then (as noted above)

${\displaystyle \Phi _{n}($x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}\;.}

Ifn = p^m is a prime power (where p is prime), then

${\displaystyle \Phi _{n}($x)=\Phi _{p}(x^{p^{m-1}})=\sum _{k=0}^{p-1}x^{kp^{m-1}}\;.}

More generally, if n = p^mr with r relatively primetop, then

${\displaystyle \Phi _{n}($x)=\Phi _{pr}(x^{p^{m-1}})\;.}

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial ${\displaystyle \Phi _{n}($x)} in term of a cyclotomic polynomial of square free index: If q is the product of the prime divisors of n (its radical), then^[5]

${\displaystyle \Phi _{n}($x)=\Phi _{q}(x^{n/q})\;.}

This allows formulas to be given for the nth cyclotomic polynomial when n has at most one odd prime factor: If p is an odd prime number, and h and k are positive integers, then

${\displaystyle \Phi _{2^{h}}($x)=x^{2^{h-1}}+1\;,}

${\displaystyle \Phi _{p^{k}}($x)=\sum _{j=0}^{p-1}x^{jp^{k-1}}\;,}

${\displaystyle \Phi _{2^{h}p^{k}}($x)=\sum _{j=0}^{p-1}(-1)^{j}x^{j2^{h-1}p^{k-1}}\;.}

For the other values of n, the computation of the nth cyclotomic polynomial is similarly reduced to that of ${\displaystyle \Phi _{q}($x),} where q is the product of the distinct odd prime divisors of n. To deal with this case, one has that, for p prime and not dividing n,^[6]

${\displaystyle \Phi _{np}($x)=\Phi _{n}(x^{p})/\Phi _{n}(x)\;.}

Integers appearing as coefficients[edit]

The problem of bounding the magnitude of the coefficients of the cyclotomic polynomials has been the object of a number of research papers. Several survey papers give an overview.^[7]

Ifn has at most two distinct odd prime factors, then Migotti showed that the coefficients of ${\displaystyle \Phi _{n}}$ are all in the set {1, −1, 0}.^[8]

The first cyclotomic polynomial for a product of three different odd prime factors is ${\displaystyle \Phi _{105}($x);} it has a coefficient −2 (see its expression above). The converse is not true: ${\displaystyle \Phi _{231}($x)=\Phi _{3\times 7\times 11}(x)} only has coefficients in {1, −1, 0}.

Ifn is a product of more different odd prime factors, the coefficients may increase to very high values. E.g., ${\displaystyle \Phi _{15015}($x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)} has coefficients running from −22 to 23, ${\displaystyle \Phi _{255255}($x)=\Phi _{3\times 5\times 7\times 11\times 13\times 17}(x)} , the smallest n with 6 different odd primes, has coefficients of magnitude up to 532.

Let A(n) denote the maximum absolute value of the coefficients of Φ_n. It is known that for any positive k, the number of n up to x with A(n) > n^k is at least c(k)⋅x for a positive c(k) depending on k and x sufficiently large. In the opposite direction, for any function ψ(n) tending to infinity with n we have A(n) bounded above by n^ψ(n) for almost all n.^[9]

A combination of theorems of Bateman resp. Vaughan states^[7]: 10 that on the one hand, for every ${\displaystyle \varepsilon >0}$, we have

${\displaystyle A($n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}}

for all sufficiently large positive integers ${\displaystyle n}$, and on the other hand, we have

${\displaystyle A($n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)}}

for infinitely many positive integers ${\displaystyle n}$. This implies in particular that univariate polynomials (concretely ${\displaystyle x^{n}-1}$ for infinitely many positive integers ${\displaystyle n}$) can have factors (like ${\displaystyle \Phi _{n}}$) whose coefficients are superpolynomially larger than the original coefficients. This is not too far from the general Landau-Mignotte bound.

Gauss's formula[edit]

Let n be odd, square-free, and greater than 3. Then:^[10][11]

${\displaystyle 4\Phi _{n}($z)=A_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nz^{2}B_{n}^{2}(z)}

where both A_n(z) and B_n(z) have integer coefficients, A_n(z) has degree φ(n)/2, and B_n(z) has degree φ(n)/2 − 2. Furthermore, A_n(z) is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, B_n(z) is palindromic unless n is composite and ≡ 3 (mod 4), in which case it is antipalindromic.

The first few cases are

${\displaystyle {\begin{aligned}4\Phi _{5}($z)&=4(z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{2}+z+2)^{2}-5z^{2}\\[6pt]4\Phi _{7}(z)&=4(z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{3}+z^{2}-z-2)^{2}+7z^{2}(z+1)^{2}\\[6pt]4\Phi _{11}(z)&=4(z^{10}+z^{9}+z^{8}+z^{7}+z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{5}+z^{4}-2z^{3}+2z^{2}-z-2)^{2}+11z^{2}(z^{3}+1)^{2}\end{aligned}}}

Lucas's formula[edit]

Let n be odd, square-free and greater than 3. Then^[11]

${\displaystyle \Phi _{n}($z)=U_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nzV_{n}^{2}(z)}

where both U_n(z) and V_n(z) have integer coefficients, U_n(z) has degree φ(n)/2, and V_n(z) has degree φ(n)/2 − 1. This can also be written

${\displaystyle \Phi _{n}\left((-1)^{\frac {n-1}{2}}z\right)=C_{n}^{2}($z)-nzD_{n}^{2}(z).}

Ifn is even, square-free and greater than 2 (this forces n/2 to be odd),

${\displaystyle \Phi _{\frac {n}{2}}\left(-z^{2}\right)=\Phi _{2n}($z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)}

where both C_n(z) and D_n(z) have integer coefficients, C_n(z) has degree φ(n), and D_n(z) has degree φ(n) − 1. C_n(z) and D_n(z) are both palindromic.

The first few cases are:

${\displaystyle {\begin{aligned}\Phi _{3}(-z)&=\Phi _{6}($z)=z^{2}-z+1\\&=(z+1)^{2}-3z\\[6pt]\Phi _{5}(z)&=z^{4}+z^{3}+z^{2}+z+1\\&=(z^{2}+3z+1)^{2}-5z(z+1)^{2}\\[6pt]\Phi _{6/2}(-z^{2})&=\Phi _{12}(z)=z^{4}-z^{2}+1\\&=(z^{2}+3z+1)^{2}-6z(z+1)^{2}\end{aligned}}}

Sister Beiter conjecture[edit]

The Sister Beiter conjecture is concerned with the maximal size (in absolute value) ${\displaystyle A(pqr)}$ of coefficients of ternary cyclotomic polynomials ${\displaystyle \Phi _{pqr}($x)} where ${\displaystyle 3\leq p\leq q\leq r}$ are three prime numbers.^[12]

Cyclotomic polynomials over a finite field and over the p-adic integers[edit]

Over a finite field with a prime number p of elements, for any integer n that is not a multiple of p, the cyclotomic polynomial ${\displaystyle \Phi _{n}}$ factorizes into ${\displaystyle {\frac {\varphi ($n)}{d}}} irreducible polynomials of degree d, where ${\displaystyle \varphi ($n)} isEuler's totient function and d is the multiplicative orderofp modulo n. In particular, ${\displaystyle \Phi _{n}}$ is irreducible if and only if p is a primitive root modulo n, that is, p does not divide n, and its multiplicative order modulo nis${\displaystyle \varphi ($n)} , the degree of ${\displaystyle \Phi _{n}}$.^[13]

These results are also true over the p-adic integers, since Hensel's lemma allows lifting a factorization over the field with p elements to a factorization over the p-adic integers.

Polynomial values[edit]

This section does not cite any sources. Please help improve this sectionbyadding citations to reliable sources. Unsourced material may be challenged and removed. (April 2014) (Learn how and when to remove this message)

Ifx takes any real value, then ${\displaystyle \Phi _{n}($x)>0} for every n ≥ 3 (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for n ≥ 3).

For studying the values that a cyclotomic polynomial may take when x is given an integer value, it suffices to consider only the case n ≥ 3, as the cases n = 1 and n = 2 are trivial (one has ${\displaystyle \Phi _{1}($x)=x-1} and ${\displaystyle \Phi _{2}($x)=x+1} ).

For n ≥ 2, one has

${\displaystyle \Phi _{n}(0)=1,}$

${\displaystyle \Phi _{n}($1)=1} ifn is not a prime power,

${\displaystyle \Phi _{n}($1)=p} if${\displaystyle n=p^{k}}$ is a prime power with k ≥ 1.

The values that a cyclotomic polynomial ${\displaystyle \Phi _{n}($x)} may take for other integer values of x is strongly related with the multiplicative order modulo a prime number.

More precisely, given a prime number p and an integer b coprime with p, the multiplicative order of b modulo p, is the smallest positive integer n such that p is a divisor of ${\displaystyle b^{n}-1.}$ For b >1, the multiplicative order of b modulo p is also the shortest period of the representation of 1/p in the numeral base b (see Unique prime; this explains the notation choice).

The definition of the multiplicative order implies that, if n is the multiplicative order of b modulo p, then p is a divisor of ${\displaystyle \Phi _{n}($b).} The converse is not true, but one has the following.

Ifn > 0 is a positive integer and b >1 is an integer, then (see below for a proof)

${\displaystyle \Phi _{n}($b)=2^{k}gh,}