Cyclotomic polynomials

We now want to discuss a special class of polynomials in ℤ[x]. These polynomials occur in the factorizations of the simple polynomial xⁿ − 1. Although these polynomials are constructed easily, they have a tendency to appear in many different applications, and hence are very useful. These are thr polynomials that have as roots the primitive n-th roots of unity. Because of their relation with the division of the circle, these polynomials are called cyclotomic polynomials.

From our knowledge of cyclic groups, we know (Lemma 7.3.10) that (ζ_n^k) is a primitive nth root of 1 if and only if k is relatively prime to n. In particular, there are φ(n) primitive roots of 1, where φ is Euler's totient function. Thus,

Φ_{n} (x) := \prod_{ζ primitive root of 1} (x - ζ) = \prod_{1 \leq k \leq n, (n, k) = 1} (x - ζ_{n}^{k})

Lemma 7.5.9 For all positive integers n,

x^{n} - 1 = \prod_{d | n} Φ_{d} (x) (7.5.3)

Proof. If n = de, then every dth root ζ of 1 is an nth root of 1, because ζⁿ = ζ^de = (ζ^d)^e = 1. In particular, every primite dth root ζ of 1 is an nth root of 1. □

From the last relation we can find that

n = \sum_{d | n} ϕ (d)

which is a property of Euler's function which can be obtained wihtout resorting to cyclotomic polynomials.

Example 7.5.10. Consider x⁴ − 1. There are four roots {1,−1,i,−i}; 1 and −1 are not primitive roots of the unity, because by definition of order even if 1⁴ = 1 or −1⁴ = 1 we have 1² = 1 and −1² = 1. Only i and −i are primitive because no power smaller than 4 gives i^m = 1, or (−i)^m = 1. So that

Φ₄ (x) = (x − i) (x + i) = x² + 1

Example 7.5.11. When n = 2, the only primitive square root of unit is −1 (note that 1 has order 1, i.e. not primitive), so that Φ₂(x) = x + 1. When n = 4, the primitive fourth roots of unity are i and −i, so that

Φ₄ = (x − i) (x + i) = x² + 1

Since Φ₁ = x − 1, we get the factorization

xⁿ − 1 = Φ₁(x) Φ₂(x) Φ₄(x) = (x − 1) (x +1) (x² + 1) ■

Equation 7.5.3 can be written as well as

x^{n} - 1 = Φ_{1} (x) \prod_{\begin{matrix} d ∣ n \\ d \neq 1 \\ d \neq n \end{matrix}} Φ_{d} (x) Φ_{n} (x)

With this inductive method we can calculate the first cyclotomic polynomials, since

Φ_{n} = \frac{x^{n} - 1}{\prod_{\begin{matrix} d ∣ n \\ d \neq n \end{matrix}} Φ_{d}}

7.5.12. Evaluation of the first nine cyclotomic polynomials

Φ₁(x) = x − 1

Φ₂(x) = x² − 1/Φ₁(x) = x + 1

Φ₃(x) = x³ − 1/Φ₁(x) = x² + x + 1

Φ₄(x) = x⁴ − 1/Φ₁(x)Φ₂(x) = x⁴ − 1 /(x−1)(x+1) = x² +1

Φ₅(x) = x⁵ − 1/Φ₁(x) = x⁴ + x³ + x² + x + 1

Φ₆(x) = x⁶ − 1/Φ₁(x)Φ₂(x)Φ₃(x) = (x⁶ − 1)/(x − 1)(x + 1)(x² + x +1) = x² −x +1

Φ₇(x) = x⁷ − 1/Φ₁(x) = x⁶ + x⁵ + x⁴ + x³ + x² + x + 1

Φ₈(x) = x⁸ − 1/Φ₁(x)Φ₂(x)Φ₄(x) = x⁸ −1/(x − 1)(x + 1)(x²+1) = x⁴ + 1

Φ₉(x) = x⁹ − 1/Φ₁(x) Φ₃(x) = x⁶ + x³ + 1

In general, if p is prime

x^p−1 = Φ₁(x)Φ_p(x).

Φ_p (x) = 1 + x + x² + ... + x^p−2 + x^p−1

Moreover, for n = p^h

Φ_p^h(x) = 1 + x^{p^h−1} + (x^h−1)^p−1

Indeed

x^{p^h} − 1 = Φ₁ Φ_p Φ_p² ⋅⋅⋅ Φ_{p^{h −1}}Φ_p^h

which yields to

Φ_p^h = x^{p^h} − 1 / Φ₁ Φ_p Φ_p² ⋅⋅⋅ Φ_{p^{h −1}} = x^{p^h} − 1 / x^{p^{h − 1}} − 1 = 1 + x^{p^h−1} + ...(x^{p^{h − 1})^p−1}

Example 7.5.12. Cyclotomic polynomials have the following properties:

every Φ_n(x) is monic with integers coefficients;
the degree Φ_n(x) is Φ(n);
every Φ_n(x) is irreducile over ℚ.

Proof. a) We proceed by induction over n. for n = 1, Φ₁(x) = x − 1 which is monic and with integers coefficients. We suppose the same to hold true for Φ_m(x) with m < n and we prove it for Φ_n(x). We have

Φ_n(x) = xⁿ − 1 / ∏_{_{d|n,d ≠ n}} Φ_d(x)

Dividing xⁿ − 1 by ∏_{_{d|n,d ≠ n}} Φ_d(x), we obtain a monic polynomial with integer coefficients.

b) It follows from the construction of Φ_n(x).

c) We'll prove this property only for n = p^h, with p prime number. As we have already seen

Φ_p^h(x) = 1 + x^{p^h−1} + (x^h−1)^p−1 = x^{p^h} − 1 / x^{p^{h − 1}} − 1

To prove the irreducibility of Φ_p^h(x) we cannot apply directly Eisenstein criterion. We employ Lemma 5.7.3 and make the substitution x = y + 1 which yields to a new polynomial in y

\begin{aligned} Ψ (y) & = Φ_{p^{h}} (y + 1) = 1 + (y + 1)^{p^{h - 1}} + \dots + ((y + 1)^{p^{h - 1}})^{p - 1} \\ = \frac{(y + 1)^{p^{h}} - 1}{(y + 1)^{p^{h - 1}} - 1} = \frac{y^{p^{h}} + p f (y)}{y^{p^{h - 1}} + p g (y)} \end{aligned}

We employed Newton binomial formula and grouping the addends which are multiple of p in pf(y) and pg(y). We have then

[1 + (y + 1)^{p^h−1} + ... + ((y + 1)^{p^h−1})^p−1][y^p^h−1 + pg(y)] = y^{p^h} + pf(y)

by grouping the highest degree terms in each polynomial, we obtain

[(y + 1)^{p^{h − 1}} + ∑ α_i yⁱ] [y^p^h−1 + pg(y)] = y^{p^h} + pf(y)

doing the calculations and grouping the terms which are multiple of p yields

y^{p^h−1} ∑ α_i yⁱ + y^{p^h−1(p−1)} ⋅ y^{p^h−1} = y^{p^h} + pf̄(y)

in this form we are sure that all coefficients α_i different from the leading coefficients (which is 1) of Ψ(y) are multiples of p. To apply Eisenstein criterion we only need to prove that p² does not divide the constant term. This is true since theconstant term of Ψ(y) is obtained by putting y = 0, and hence it is equal to p times 1 i.e. p. We have proved trhat Ψ(y) is irreducible and thus Ψ_h(y) as well.

This result tells us that cyclotomic polynomials are irreducible over ℚ, and we can use them to find the factorization of xⁿ − 1. We have

xⁿ − 1 = ∏_{_d|n} Φ_d(x) (7.5.3)

From the cyclotomic polynomials we've written above it may seem that their coefficient are all either 0 ri ±1. This is not true as it can be shown that for polynomials with higher n (about 100) other coefficients start to appear.

«Polynomials: general properties Index gcd of polynomials »