Root of Unity - Cyclotomic Polynomials

Cyclotomic Polynomials

The zeroes of the polynomial

are precisely the nth roots of unity, each with multiplicity 1. The nth cyclotomic polynomial is defined by the fact that its zeros are precisely the primitive nth roots of unity, each with multiplicity 1.

where z₁,z₂,z₃,...,z_φ(n) are the primitive nth roots of unity, and φ(n) is Euler's totient function. The polynomial Φ_n(z) has integer coefficients and is an irreducible polynomial over the rational numbers (i.e., it cannot be written as the product of two positive-degree polynomials with rational coefficients). The case of prime n, which is easier than the general assertion, follows by applying Eisenstein's criterion to the polynomial ((z + 1)n−1) / ((z + 1) − 1), and expanding via the binomial theorem.

Every nth root of unity is a primitive dth root of unity for exactly one positive divisor d of n. This implies that

This formula represents the factorization of the polynomial zn − 1 into irreducible factors.

z1−1 = z−1

z2−1 = (z−1)·(z+1)

z3−1 = (z−1)·(z2+z+1)

z4−1 = (z−1)·(z+1)·(z2+1)

z5−1 = (z−1)·(z4+z3+z2+z+1)

z6−1 = (z−1)·(z+1)·(z2+z+1)·(z2−z+1)

z7−1 = (z−1)·(z6+z5+z4+z3+z2+z+1)

Applying Möbius inversion to the formula gives

where μ is the Möbius function.

So the first few cyclotomic polynomials are

Φ₁(z) = z−1

Φ₂(z) = (z2−1)·(z−1)−1 = z+1

Φ₃(z) = (z3−1)·(z−1)−1 = z2+z+1

Φ₄(z) = (z4−1)·(z2−1)−1 = z2+1

Φ₅(z) = (z5−1)·(z−1)−1 = z4+z3+z2+z+1

Φ₆(z) = (z6−1)·(z3−1)−1·(z2−1)−1·(z−1) = z2−z+1

Φ₇(z) = (z7−1)·(z−1)−1 = z6+z5+z4+z3+z2+z+1

If p is a prime number, then all the pth roots of unity except 1 are primitive pth roots, and we have

Substituting any positive integer ≥ 2 for z, this sum becomes a base z repunit. Thus a necessary (but not sufficient) condition for a repunit to be prime is that its length be prime.

Note that, contrary to first appearances, not all coefficients of all cyclotomic polynomials are 0, 1, or −1. The first exception is Φ₁₀₅. It is not a surprise it takes this long to get an example, because the behavior of the coefficients depends not so much on n as on how many odd prime factors appear in n. More precisely, it can be shown that if n has 1 or 2 odd prime factors (e.g., n = 150) then the nth cyclotomic polynomial only has coefficients 0, 1 or −1. Thus the first conceivable n for which there could be a coefficient besides 0, 1, or −1 is a product of the three smallest odd primes, and that is 3·5·7 = 105. This by itself doesn't prove the 105th polynomial has another coefficient, but does show it is the first one which even has a chance of working (and then a computation of the coefficients shows it does). A theorem of Schur says that there are cyclotomic polynomials with coefficients arbitrarily large in absolute value. In particular, if n = p₁·p₂· ... ·p_t, where p₁ < p₂ < ... < p_t are odd primes, p₁ + p₂ > p_t, and t is odd, then 1 − t occurs as a coefficient in the nth cyclotomic polynomial.

Many restrictions are known about the values that cyclotomic polynomials can assume at integer values. For example, if p is prime and d | Φ_p(d), then either d ≡ 1 mod (p), or d ≡ 0 mod (p).

Cyclotomic polynomials are solvable in radicals, as roots of unity are themselves radicals. Moreover, there exist more informative radical expressions for nth roots of unity with the additional property that every value of the expression obtained by choosing values of the radicals (for example, signs of square roots) is a primitive nth root of unity. This was already shown by Gauss in 1797. Efficient algorithms exist for calculating such expressions.