Cyclotomic polynomial explained

In mathematics, the nth 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 Its roots are all nth primitive roots of unity e ^{2 i\pi (k)/(n)} , where k runs over the positive integers not greater than n and coprime to n (and i is the imaginary unit). In other words, the nth cyclotomic polynomial is equal to\Phi _{n(x)} = \prod _{\stackrel{1\le} k\le n}{\gcd(k,n) =1 } \left(x - e ^{2 i\pi (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 (

e ^{2i\pi/n} is an example of such a root).

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

\prod _{d\mid} \Phi _{d(x)} = x ^{n} - 1 , showing that is a root of x ^{n} - 1 if and only if it is a dth primitive root of unity for some d that divides n.

Examples

If n is a prime number, then

\Phi _{n(x)} = 1+ x + x ^{2+ … +x} ^{n-1} = \sum ^{n -1} _{k =0} x ^{k.} If n = 2p where p is a prime number other than 2, then\Phi _{2p} (x) = 1- x + x ^{2- … +x} ^{p-1} = \sum ^{p -1} _{k =0} ( - x) ^{k.}

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

\begin{align} \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 . \end{align}

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:

\begin{align} \Phi _{105} (x) = {}&x ^{48} + x ^{47} + x ^{46} - x ^{43} - x ^{42} - 2 x ^{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} - 2 x ^{7} - x ^{6} - x ^{5} + x ^{2} + x + 1 . \end{align}

Properties

Fundamental tools

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

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

The fact that

\Phi _{n} is an irreducible polynomial of degree \varphi (n) in the ring \Z[x] is a nontrivial result due to Gauss. 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

\begin{align} x ^{n} - 1 & = \prod _{1\leqslant} \left(x - e ^{2 i\pi (k)/(n)} \right) \\ & = \prod _{d} \prod _{1} \left(x - e ^{2 i\pi (k)/(n)} \right) \\ & = \prod _{d} \Phi _{(n)/(d)} (x) = \prod _{d\mid} \Phi _{d(x).\end{align}}

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

\Phi _{n(x)} to be expressed as an explicit rational fraction:\Phi _{n(x)=\prod} _{d\mid} (x ^{d-1)} ^{\mu \left ( (n)/(d) \right )} ,

where

\mu is the Möbius function.

The cyclotomic polynomial

\Phi _{n} (x) may be computed by (exactly) dividing x ^{n-1} by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:\Phi _{n(x) = (x ^{n} -1)/(\prod _{\stackrel{d|n} {{)} _{d<n} }}\Phi_(x)}

(Recall that

\Phi _{1} (x) = x -1 .)

This formula defines an algorithm for computing

\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

As noted above, if is a prime number, then

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

If n is an odd integer greater than one, then

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

In particular, if is twice an odd prime, then (as noted above)

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

If is a prime power (where p is prime), then

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

More generally, if with relatively prime to, then

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

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial

\Phi _{n(x)} in term of a cyclotomic polynomial of square free index: If is the product of the prime divisors of (its radical), then^[2] \Phi _{n(x)} = \Phi ^{n/q} _{q(x} ) .

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

\Phi _{2 ^{h}} (x) = x ^{2 ^{h-1}} +1 , \Phi _{p ^{k}} (x) = \sum ^{p -1} _{j =0} x ^{jp ^{k-1}} , \Phi _{2 ^{hp} ^{k}} (x) = \sum ^{p -1} _{j =0} ( -1 ) ^{jx} ^{j 2 ^{h-1} p ^{k-1}} .

For the other values of, the computation of the th cyclotomic polynomial is similarly reduced to that of

\Phi _{q(x),} where is the product of the distinct odd prime divisors of . To deal with this case, one has that, for prime and not dividing,\Phi _{np} (x) = \Phi _{n} (x ^{p)/\Phi} _{n(x) .}

Integers appearing as coefficients

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.^[3] If n has at most two distinct odd prime factors, then Migotti showed that the coefficients of

\Phi _{n} are all in the set .

The first cyclotomic polynomial for a product of three different odd prime factors is

\Phi _{105} (x); it has a coefficient −2 (see its expression above). The converse is not true: \Phi _{231} (x) = \Phi _{3 x} (x) only has coefficients in .

If n is a product of more different odd prime factors, the coefficients may increase to very high values. E.g.,

\Phi _{15015} (x) = \Phi _{3 x} (x) has coefficients running from −22 to 23, \Phi _{255255} (x) = \Phi _{3 x} (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.

A combination of theorems of Bateman resp. Vaughan states that on the one hand, for every

\varepsilon> 0 , we haveA(n) < e ^{\left(n ^{(log} \right)} for all sufficiently large positive integers n , and on the other hand, we haveA(n) > e ^{\left(n ^{(log} \right)} for infinitely many positive integers n . This implies in particular that univariate polynomials (concretely x ^{n-1} for infinitely many positive integers n ) can have factors (like \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

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

4 \Phi _{n(z)} = A ^{2 (z)} _{n} - ( -1 ) ^{(n -1)/(2)} nz ^{2 (z)} _{n}

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

\begin{align} 4 \Phi _{5(z)} & =4 (z ^{4+z} ^{3+z} ^{2+z+1)\ &=} ( 2 z ^{2+z+2)} ^{2} - 5 z ^{2} \\[ 6 pt] 4 \Phi _{7(z)} & =4 (z ^{6+z} ^{5+z} ^{4+z} ^{3+z} ^{2+z+1)\ &=} ( 2 z ^{3+z} ^{2-z-2)} ^{2+7z} ^{2(z+1)} ^{2} \ [ 6 pt] 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)\ &=} ( 2 z ^{5+z} ^{4-2z} ^{3+2z} ^{2-z-2)} ^{2+11z} ^{2(z} ^{3+1)} ^{2 \end{align}}

Lucas's formula

Let n be odd, square-free and greater than 3. Then

\Phi _{n(z)} = U ^{2 (z)} _{n} - ( -1 ) ^{(n -1)/(2)} nzV ^{2 (z)} _{n}

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

\Phi _{n} \left (( -1 ) ^{(n -1)/(2)} z \right ) = C ^{2 (z)} _{n} - nzD ^{2 (z).} _{n}

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

\Phi _{(n)/(2)} \left ( - z ^{2} \right ) = \Phi _{2n} (z) = C ^{2 (z)} _{n} - nzD ^{2 (z)} _{n}

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:

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

Sister Beiter conjecture

The Sister Beiter conjecture is concerned with the maximal size (in absolute value)

A(pqr) of coefficients of ternary cyclotomic polynomials \Phi _{pqr} (x) where 3 \leq p\leq q\leq r are three prime numbers.

Cyclotomic polynomials over a finite field and over the -adic integers

Over a finite field with a prime number of elements, for any integer that is not a multiple of, the cyclotomic polynomial

\Phi _{n} factorizes into (\varphi (n))/(d) irreducible polynomials of degree, where \varphi (n) is Euler's totient function and is the multiplicative order of modulo . In particular, \Phi _{n} is irreducible if and only if is a primitive root modulo , that is, does not divide, and its multiplicative order modulo is \varphi(n) , the degree of \Phi _{n} .^[5]

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

Polynomial values

If takes any real value, then

\Phi _{n(x)>0} for every (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for).

For studying the values that a cyclotomic polynomial may take when is given an integer value, it suffices to consider only the case, as the cases and are trivial (one has

\Phi _{1(x)=x-1} and \Phi _{2(x)=x+1} ).

For, one has

\Phi _{n(0)} =1 , \Phi _{n(1)} =1 if is not a prime power,\Phi _{n(1)} = p if n = p ^{k} is a prime power with .

The values that a cyclotomic polynomial

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

More precisely, given a prime number and an integer coprime with, the multiplicative order of modulo, is the smallest positive integer such that is a divisor of

b ^{n-1.} For, the multiplicative order of modulo is also the shortest period of the representation of in the numeral base (see Unique prime; this explains the notation choice).

The definition of the multiplicative order implies that, if is the multiplicative order of modulo, then is a divisor of

\Phi _{n(b).} The converse is not true, but one has the following.

If is a positive integer and is an integer, then (see below for a proof)

\Phi ^{kgh,} _{n(b) =2} where

• is a non-negative integer, always equal to 0 when is even. (In fact, if is neither 1 nor 2, then is either 0 or 1. Besides, if is not a power of 2, then is always equal to 0)
• is 1 or the largest odd prime factor of .
• is odd, coprime with, and its prime factors are exactly the odd primes such that is the multiplicative order of modulo .

This implies that, if is an odd prime divisor of

\Phi _{n(b),} then either is a divisor of or is a divisor of . In the latter case, p ^{2} does not divide \Phi _{n(b).}

Zsigmondy's theorem implies that the only cases where and are

\begin{align} \Phi _{1(2)} & =1 \\ \Phi _{2} \left ( 2 ^{k-1} \right ) & =2 ^{k} && k > 0 \\ \Phi _{6(2)} & =3 \end{align}

It follows from above factorization that the odd prime factors of

(\Phi _{n(b)})/(\gcd(n,\Phi _{n(b))})

are exactly the odd primes such that is the multiplicative order of modulo . This fraction may be even only when is odd. In this case, the multiplicative order of modulo is always .

There are many pairs with such that

\Phi _{n(b)} is prime. In fact, Bunyakovsky conjecture implies that, for every, there are infinitely many such that \Phi _{n(b)} is prime. See for the list of the smallest such that \Phi _{n(b)} is prime (the smallest such that \Phi _{n(b)} is prime is about λ ⋅ \varphi(n) , where λ is Euler–Mascheroni constant, and \varphi is Euler's totient function). See also for the list of the smallest primes of the form \Phi _{n(b)} with and, and, more generally,, for the smallest positive integers of this form.

• Values of

\Phi _{n(1).} If n = p ^{k+1} is a prime power, then \Phi ^{p ^{k}} _{n(x) =1+ x} + x ^{2 p ^{k}} + … + x ^{(p -1 )p ^{k}} and \Phi _{n(1)=p.}

If is not a prime power, let

P(x) =1+ x + … + x ^{n-1} , we have P( 1 ) = n, and is the product of the \Phi _{k(x)} for dividing and different of . If is a prime divisor of multiplicity in, then \Phi _{p(x),} \Phi _{p ^{2}} (x), … , \Phi _{p ^{m}} (x) divide, and their values at are factors equal to of n = P( 1 ). As is the multiplicity of in, cannot divide the value at of the other factors of P(x). Thus there is no prime that divides \Phi _{n(1).}

• If is the multiplicative order of modulo, then

p \mid \Phi _{n(b).} By definition, p \mid b ^{n-1.} If p \nmid \Phi _{n(b),} then would divide another factor \Phi _{k(b)} of b ^{n-1,} and would thus divide b ^{k-1,} showing that, if there would be the case, would not be the multiplicative order of modulo .

• The other prime divisors of

\Phi _{n(b)} are divisors of . Let be a prime divisor of \Phi _{n(b)} such that is not be the multiplicative order of modulo . If is the multiplicative order of modulo, then divides both \Phi _{n(b)} and \Phi _{k(b).} The resultant of \Phi _{n(x)} and \Phi _{k(x)} may be written P\Phi _{k+Q\Phi} _{n,} where and are polynomials. Thus divides this resultant. As divides, and the resultant of two polynomials divides the discriminant of any common multiple of these polynomials, divides also the discriminant n ^{n} of x ^{n-1.} Thus divides .

• and are coprime. In other words, if is a prime common divisor of and

\Phi _{n(b),} then is not the multiplicative order of modulo . By Fermat's little theorem, the multiplicative order of is a divisor of, and thus smaller than .

• is square-free. In other words, if is a prime common divisor of and

\Phi _{n(b),} then p ^{2} does not divide \Phi _{n(b).} Let . It suffices to prove that p ^{2} does not divide for some polynomial, which is a multiple of \Phi _{n(x).} We take S(x) = (x ^{n-1})/(x ^{m-1}) = 1 + x ^{m} + x ^{2m} + … + x ^{(p-1)m} .

The multiplicative order of modulo divides, which is a divisor of . Thus is a multiple of . Now,

S(b) = (( 1+ c) ^{p-1})/(c) = p + \binom{p}{ 2 }c + … + \binom{p}{p}c ^{p-1} .

As is prime and greater than 2, all the terms but the first one are multiples of

p ^{2.} This proves that p ^{2} \nmid \Phi _{n(b).}

Applications

Using

\Phi _{n} , one can give an elementary proof for the infinitude of primes congruent to 1 modulo n,^[6] which is a special case of Dirichlet's theorem on arithmetic progressions.Suppose p _{1,} p _{2,} \ldots, p _{k} is a finite list of primes congruent to 1 modulo n. Let N = np _{1p} _{2 …} p _{k} and consider \Phi _{n(N)} . Let q be a prime factor of \Phi _{n(N)} (to see that \Phi _{n(N)} ≠ \pm 1 decompose it into linear factors and note that 1 is the closest root of unity to N ). Since \Phi _{n(x)} \equiv \pm 1 \pmod x, we know that q is a new prime not in the list. We will show that q \equiv 1 \pmod n.

Let

m be the order of N modulo q. Since \Phi _{n(N)} \mid N ^{n} - 1 we have N ^{n} -1 \equiv 0 \pmod{q} . Thus m \mid n . We will show that m = n .

Assume for contradiction that

m < n . Since \prod _{d} \Phi _{d(N)} = N ^{m} - 1 \equiv 0 \pmod q

we have

\Phi _{d(N)} \equiv 0 \pmod q,

for some

d < n . Then N is a double root of \prod _{d} \Phi _{d(x)} \equiv x ^{n} -1 \pmod q.

Thus

N must be a root of the derivative so \left. (d(x ^{n} -1 ))/(dx) \right| _{N} \equiv nN ^{n-1} \equiv 0 \pmod q.

But

q \nmid N and therefore q \nmid n. This is a contradiction so m = n . The order of N \pmod q, which is n , must divide q -1 . Thus q \equiv 1 \pmod n.

See also

• Cyclotomic field
• Aurifeuillean factorization
• Root of unity

Further reading

Gauss's book Disquisitiones Arithmeticae [''Arithmetical Investigations''] has been translated from Latin into French, German, and English. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

Reprinted 1965, New York: Chelsea,

Corrected ed. 1986, New York: Springer,,

Notes and References

1. cs2.
2. .
3. 2111.04034 . Sanna . Carlo . A Survey on Coefficients of Cyclotomic Polynomials . 2021 . math.NT. cs2 .
4. Gauss, DA, Articles 356-357
5. .
6. S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67.