Cyclotomic polynomials

circular polynomials

The polynomials $ \Phi _ {1} , \Phi _ {2}, \dots $ that satisfy the relation

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

where the product is taken over all positive divisors $ d $ of the number $ n $, including $ n $ itself. Over the field of complex numbers one has

$$ \Phi _ {n} ( x) = \ \prod _ \zeta ( x - \zeta ), $$

where $ \zeta $ ranges over the primitive $ n $-th roots of unity (cf. Primitive root). The degree of $ \Phi _ {n} ( x) $ is the number of integers $ k $ among $ 1, \dots, n $ that are relatively prime with $ n $. The polynomials $ \Phi _ {n} ( x) $ can be computed recursively by dividing the polynomial $ x ^ {n} - 1 $ by the product of all $ \Phi _ {d} ( x) $, $ d < n $, $ d \mid n $. The coefficients lie in the prime field $ \mathbf Q $; in case of characteristic zero, they are integers. Thus,

$$ \Phi _ {1} ( x) = x - 1 ,\ \Phi _ {2} ( x) = x + 1 ,\ \ \Phi _ {3} ( x) = x ^ {2} + x + 1 . $$

If, moreover, $ n= p $ is prime, then

$$ \Phi _ {p} ( x) = \frac{x ^ {p} - 1 }{x - 1 } = x ^ {p - 1 } + \dots + x + 1 . $$

The polynomial $ \Phi _ {n} ( x) $ can be explicitly expressed using the Möbius function $ \mu $:

$$ \Phi _ {n} ( x) = \prod _ {d \mid n } ( x ^ {d} - 1 ) ^ {\mu ( n / d ) } . $$

For example,

$$ \Phi _ {12} ( x) = $$

$$ = \ ( x ^ {12} - 1) ( x ^ {6} - 1) ^ {-1} ( x ^ {4} - 1) ^ {-1} ( x ^ {3} - 1) ^ {0} ( x ^ {2} - 1) ( x - 1) ^ {0 } = $$

$$ = \ \frac{x ^ {6} + 1 }{x ^ {2} + 1 } = x ^ {4} - x ^ {2} + 1 . $$

All the polynomials $ \Phi _ {n} ( x) $ are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation

$$ \Phi _ {12} ( x) = x ^ {4} - x ^ {2} + 1 = ( x ^ {2} + 5x + 1 ) ( x ^ {2} - 5x + 1 ) $$

is valid over the field of residues modulo 11.

The equation $ \Phi _ {n} ( x) = 0 $, which gives all primitive $ n $-th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is

$$ r _ {k} = \cos \frac{2 k \pi }{n} + i \sin \frac{2 k \pi }{n} = \ e ^ {2 k \pi i /n } , $$

where the fraction $ k / n $ is irreducible, i.e. $ k $ and $ n $ are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular $ n $-gon, or with the equivalent problem of subdividing the circle into $ n $ equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation $ \Phi _ {n} ( x) = 0 $ is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if

$$ n = 2 ^ {m} p _ {1} \cdots p _ {s} , $$

where $ m $ is a non-negative integer and $ p _ {1}, \dots, p _ {s} $ are pairwise different prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $, where $ k $ is a non-negative integer.

References

[1]	B.L. van der Waerden, "Algebra" , 1–2 , Springer (1967–1971) (Translated from German)
[2]	A.K. Sushkevich, "Foundations of higher algebra" , Moscow-Leningrad (1941) (In Russian)

Comments

The degree of $ \Phi _ {n} ( x) $ is equal to $ \phi ( n) $, the value (at $ n $) of the Euler $ \phi $-function (cf. Euler function).

Prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $ with $ k $ a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number $ F _ {k} = 2 ^ {2 ^ {k} } + 1 $, with $ k $ as before, prime? The only small Fermat primes are $ F _ {0} $, $ F _ {1} $, $ F _ {2} $, $ F _ {3} $, $ F _ {4} $ (cf. [a1], pp. 183-185).

References

[a1]	I. Stewart, "Galois theory" , Chapman & Hall (1973)
[a2]	H. Davenport, "Multiplicative number theory" , Springer (1980)