Cyclotomic polynomial


In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of and is not a divisor of for any Its roots are all nth primitive roots of unity
, where k runs over the positive integers not greater than n and coprime to n. In other words, the nth cyclotomic polynomial is equal to
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.
An important relation linking cyclotomic polynomials and primitive roots of unity is
showing that is a root of 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
If n = 2p where p is an odd prime number, then
For n up to 30, the cyclotomic polynomials are:
The case of the 105th cyclotomic polynomial is interesting because 105 is the lowest integer that is the product of three distinct odd prime numbers and this polynomial is the first one that has a coefficient other than 1, 0, or −1:

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 palindromics of even degree.
The degree of, or in other words the number of nth primitive roots of unity, is, where is Euler's totient function.
The fact that is an irreducible polynomial of degree in the ring 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
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 the expression of as an explicit rational fraction:
where is the Möbius function.
The Fourier transform of functions of the greatest common divisor together with the Möbius inversion formula gives:
The cyclotomic polynomial may be computed by dividing by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:
This formula allows computation of on a computer for any n, as soon as integer factorization and division of polynomials are available. Many computer algebra systems have a built in function to compute the cyclotomic polynomials. For example, this function is called by typing cyclotomic_polynomial in SageMath, numtheory; in Maple, and Cyclotomic in Mathematica.

Easy cases for computation

As noted [|above], if is a prime number, then
If n is an odd integer greater than one, then
In particular, if is twice an odd prime, then
If is a prime power, then
More generally, if with relatively prime to, then
These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial in term of a cyclotomic polynomial of square free index: If is the product of the prime divisors of , then
This allows to give formulas 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:
For the other values of, the computation of the th cyclotomic polynomial is similarly reduced to that of where is the product of the distinct odd prime divisors of. To deal with this case, one has that, for prime and not dividing,

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.
If n has at most two distinct odd prime factors, then Migotti showed that the coefficients of are all in the set.
The first cyclotomic polynomial for a product of three different odd prime factors is it has a coefficient −2. The converse is not true: 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., has coefficients running from −22 to 23,, the smallest n with 6 different odd primes, has coefficients of magnitude up to 532.
Let A 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 > nk is at least c⋅x for a positive c depending on k and x sufficiently large. In the opposite direction, for any function ψ tending to infinity with n we have A bounded above by nψ for almost all n.

Gauss">Carl Friedrich Gauss">Gauss's formula

Let n be odd, square-free, and greater than 3. Then:
where both An and Bn have integer coefficients, An has degree φ/2, and Bn has degree φ/2 − 2. Furthermore, An is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, Bn is palindromic unless n is composite and ≡ 3, in which case it is antipalindromic.
The first few cases are

Lucas">Édouard Lucas">Lucas's formula

Let n be odd, square-free and greater than 3. Then
where both Un and Vn have integer coefficients, Un has degree φ/2, and Vn has degree φ/2 − 1. This can also be written
If n is even, square-free and greater than 2,
where both Cn and Dn have integer coefficients, Cn has degree φ, and Dn has degree φ − 1. Cn and Dn are both palindromic.
The first few cases are:

Cyclotomic polynomials over a finite field and over -adic integers

Over a finite field with a prime number of elements, for any integer that is not a multiple of, the cyclotomic polynomial factorizes into irreducible polynomials of degree, where is Euler's totient function, and is the multiplicative order of modulo. In particular, is irreducible if and only if is a primitive root modulo, that is, does not divide, and its multiplicative order modulo is the degree of.
These results are also true over the -adic integers, since Hensel's lemma allows lifting a factorization over the field with of elements to a factorization over the -adic integers.

Polynomial values

If takes any real value, then for every .
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.
For, one has
The values that a cyclotomic polynomial 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 For, the multiplicative order of modulo is also the shortest period of the representation of in the numeral base .
The definition of the multiplicative order implies that, if is the multiplicative order of modulo, then is a divisor of The converse is not true, but one has the following.
If is a positive integer and is an integer, then
where
This implies that, if is an odd prime divisor of then either is a divisor of or is a divisor of. In the latter case, does not divide
Zsigmondy's theorem implies that the only cases where and are
It follows from above factorization that the odd prime factors of
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 is prime. In fact, Bunyakovsky conjecture implies that, for every, there are infinitely many such that is prime. See for the list of the smallest such that is prime. See also for the list of the smallest primes of the form with and, and, more generally,, for the smallest positive integers of this form.
Using, one can give an elementary proof for the infinitude of primes congruent to 1 modulo n, which is a special case of Dirichlet's theorem on arithmetic progressions.
Suppose are a finite list of primes congruent to modulo Let and consider. Let be a prime factor of . Since we know that is a new prime not in the list. We will show that
Let be the order of modulo Since we have. Thus. We will show that.
Assume for contradiction that. Since
we have
for some. Then is a double root of
Thus must be a root of the derivative so
But and therefore This is a contradiction so. The order of which is, must divide. Thus