Cyclotomic polynomial
In mathematics, particularly in algebra and number theory, the nth cyclotomic polynomial, denoted \Phi_n(x), is the monic polynomial of degree \phi(n) (where \phi is Euler's totient function) whose roots are precisely the primitive nth roots of unity in the complex numbers, that is, the complex numbers \zeta satisfying \zeta^n = 1 and whose order is exactly n.[1][2] It has integer coefficients and is irreducible over the rational numbers \mathbb{Q}.[1][3] The cyclotomic polynomials satisfy the fundamental identity x^n - 1 = \prod_{d \mid n} \Phi_d(x), which allows them to be computed recursively or via the explicit formula \Phi_n(x) = \prod_{d \mid n} (x^{n/d} - 1)^{\mu(d)}, where \mu is the Möbius function.[2][3] For example, \Phi_1(x) = x - 1, \Phi_2(x) = x + 1, \Phi_3(x) = x^2 + x + 1, and \Phi_4(x) = x^2 + 1; in general, for a prime p, \Phi_p(x) = (x^p - 1)/(x - 1) = x^{p-1} + \cdots + x + 1.[1][2] These polynomials are reciprocal for n > 1, meaning their coefficients read the same forwards and backwards, and they play a key role in the factorization of cyclotomic extensions.[4] Cyclotomic polynomials are foundational in algebraic number theory, as adjoining a primitive nth root of unity to \mathbb{Q} generates the nth cyclotomic field \mathbb{Q}(\zeta_n), a Galois extension of degree \phi(n) whose ring of integers is \mathbb{Z}[\zeta_n].[2] They underpin proofs of significant results, such as the infinitude of primes congruent to 1 modulo n (a case of Dirichlet's theorem on arithmetic progressions) and the constructibility of regular n-gons using ruler and compass, which holds precisely when \Phi_n(x) has degree a power of 2.[4] Beyond pure mathematics, they appear in applications to cryptography (e.g., in factoring algorithms) and finite fields, where primitive elements are roots of \Phi_d(x) for appropriate d.[2]Basic Concepts
Definition
The nth cyclotomic polynomial, denoted \Phi_n(x), is defined as the monic polynomial in \mathbb{Z} whose roots are precisely the primitive nth roots of unity, for each positive integer n \geq 1.[5] A primitive nth root of unity is a complex number \zeta satisfying \zeta^n = 1 and such that the order of \zeta is exactly n, meaning \zeta^k \neq 1 for any positive integer k < n; explicitly, these are the elements e^{2\pi i k / n} where $1 \leq k \leq n and \gcd(k, n) = 1.[5] There are exactly \varphi(n) such roots, where \varphi is Euler's totient function, so \Phi_n(x) has degree \varphi(n).[5] The cyclotomic polynomials satisfy the fundamental relation x^n - 1 = \prod_{d \mid n} \Phi_d(x), where the product runs over all positive divisors d of n; this factorization uniquely determines the \Phi_n(x) recursively, starting from \Phi_1(x) = x - 1.[3] Applying Möbius inversion to this product formula yields the explicit expression \Phi_n(x) = \prod_{d \mid n} (x^{n/d} - 1)^{\mu(d)}, where \mu is the Möbius function, defined on positive integers by \mu(m) = (-1)^r if m is square-free with r prime factors, \mu(m) = 0 if m has a squared prime factor, and \mu(1) = 1.[3] The concept of cyclotomic polynomials was introduced by Carl Friedrich Gauss in 1801, in the context of solving equations related to the constructibility of regular polygons with straightedge and compass.[6]Examples
The cyclotomic polynomials for small positive integers n illustrate their explicit forms and reveal initial patterns in their coefficients and degrees. These polynomials are monic with integer coefficients, and their degrees are given by Euler's totient function \phi(n), which counts the number of integers up to n that are coprime to n.[1] As n increases, \phi(n) generally grows, though not always monotonically, providing a sense of how the polynomials become more complex. The following table lists \Phi_n(x) and \deg(\Phi_n) = \phi(n) for n \leq 12:| n | \phi(n) | \Phi_n(x) |
|---|---|---|
| 1 | 1 | x - 1 |
| 2 | 1 | x + 1 |
| 3 | 2 | x^2 + x + 1 |
| 4 | 2 | x^2 + 1 |
| 5 | 4 | x^4 + x^3 + x^2 + x + 1 |
| 6 | 2 | x^2 - x + 1 |
| 7 | 6 | x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 |
| 8 | 4 | x^4 + 1 |
| 9 | 6 | x^6 + x^3 + 1 |
| 10 | 4 | x^4 - x^3 + x^2 - x + 1 |
| 11 | 10 | x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 |
| 12 | 4 | x^4 - x^2 + 1 |
Properties
Irreducibility and Degree
The nth cyclotomic polynomial \Phi_n(x) is monic of degree \phi(n), where \phi denotes Euler's totient function. This degree arises because \Phi_n(x) is the monic polynomial whose roots are precisely the primitive nth roots of unity in the complex numbers, and there are exactly \phi(n) such roots. To see this, note that the primitive nth roots of unity are the complex numbers \zeta = e^{2\pi i k / n} for integers k with $1 \leq k \leq n and \gcd(k, n) = 1; the count of such k is \phi(n). Thus, \Phi_n(x) = \prod (x - \zeta), where the product runs over these \phi(n) roots, confirming the degree. As the minimal polynomial over \mathbb{Q} for any primitive nth root of unity, \Phi_n(x) is monic with integer coefficients. The field extension \mathbb{Q}(\zeta)/\mathbb{Q}, where \zeta is a primitive nth root of unity, has degree \phi(n) over \mathbb{Q}, and since \Phi_n(x) is the monic polynomial of least degree vanishing at \zeta, it generates this extension and has the required properties. The irreducibility of \Phi_n(x) over \mathbb{Q} follows from its role as a minimal polynomial, but direct proofs exist for both prime and general n. When n = p is prime, \Phi_p(x) = \frac{x^p - 1}{x - 1} = x^{p-1} + x^{p-2} + \cdots + x + 1. To apply Eisenstein's criterion, consider the substitution \Phi_p(x+1) = \sum_{k=0}^{p-1} \binom{p}{k} x^k. Here, p divides the coefficients \binom{p}{k} for $1 \leq k \leq p-1 but not the leading coefficient 1 or the constant term 1, and p^2 does not divide the constant term; thus, \Phi_p(x+1) (and hence \Phi_p(x)) is irreducible over \mathbb{Q}.[7] For general n, one proof uses properties of cyclotomic extensions and Galois theory, as developed by Dedekind. Suppose \Phi_n(x) = f(x) g(x) for monic polynomials f, g \in \mathbb{Z} with \deg f < \phi(n). Let \zeta be a root of f(x), so \zeta is a primitive nth root of unity. For any prime q \nmid n, the Frobenius automorphism \sigma_q: \zeta \mapsto \zeta^q fixes \mathbb{Q} and maps roots of \Phi_n(x) to other roots. Since f(\zeta) = 0 and \deg f < \phi(n), iterating \sigma_q generates more roots than f can accommodate unless f(x) = \Phi_n(x), a contradiction. Thus, \Phi_n(x) is irreducible over \mathbb{Q}.[7] A fundamental divisibility property is that \Phi_n(x) divides x^m - 1 in \mathbb{Q} if and only if n divides m. To prove this, first recall that x^m - 1 = \prod_{d \mid m} \Phi_d(x), so if n \mid m then \Phi_n(x) appears as a factor. Conversely, if \Phi_n(x) divides x^m - 1, every root \zeta of \Phi_n(x) (of multiplicative order exactly n) satisfies \zeta^m = 1, so the order n divides m.[8]Coefficients
The coefficients of the nth cyclotomic polynomial \Phi_n(x) are integers for all n \geq 1.[9] These polynomials are monic with integer coefficients, and the constant term is \pm 1.[9] Moreover, for n \geq 2, the coefficients satisfy the palindromic relation \Phi_n(x) = x^{\phi(n)} \Phi_n(1/x), meaning the coefficient of x^k equals the coefficient of x^{\phi(n)-k} for $0 \leq k \leq \phi(n).[9] The sum of the coefficients of \Phi_n(x) equals \Phi_n(1). For n=1, \Phi_1(1)=0; for n \geq 2, \Phi_n(1) = p if n = p^r for some prime p and integer r \geq 1, and \Phi_n(1) = 1 otherwise.[9] This follows from the factorization x^n - 1 = \prod_{d \mid n} \Phi_d(x) and Möbius inversion, with the value at x=1 determined by the prime power structure of n.[9] The coefficients of \Phi_n(x) exhibit sparsity, with many zeros and non-zero terms predominantly \pm 1, particularly for small n. Specifically, all coefficients lie in \{-1, 0, 1\} if n has at most two distinct odd prime factors, a result due to Migotti (1883).[9] This holds for all n < 105, as $105 = 3 \times 5 \times 7 is the smallest positive integer with three distinct odd prime factors. For n=105, \Phi_{105}(x) is the first cyclotomic polynomial with a coefficient outside \{-1, 0, 1\}, specifically including a -2.[9]Beiter Conjecture
In 1968, Marion Beiter conjectured that the coefficients of every cyclotomic polynomial \Phi_n(x) lie in the set \{-1, 0, 1\}.[10] This conjecture suggested that the height A(n), defined as the maximum absolute value of the coefficients of \Phi_n(x), satisfies A(n) \leq 1 for all positive integers n. However, the conjecture was disproved in 1981 when Kenneth S. Williams computed \Phi_{105}(x) and found coefficients of -2 at x^7 and x^{41}, establishing A(105) = 2.[11] The failure of Beiter's conjecture highlighted the more general "cyclotomic polynomial coefficient conjecture" concerning the smallness of these coefficients, which had been a longstanding belief prior to the counterexample. It is now known that the coefficients are unbounded in absolute value, a result first proved by Issai Schur in 1929 by showing that A(n) can exceed any fixed bound for sufficiently composite n. The maximal order of A(n) grows subexponentially; specifically, there exist infinitely many n such that A(n) > \exp(c n / \log \log n) for some constant c > 0, while an upper bound of A(n) < \exp(n (\log 2 + \epsilon) / \log \log n) holds for any \epsilon > 0 and all sufficiently large n.[12][13] Improved explicit bounds for specific forms of n have been obtained, such as the explicit formulas for binary cyclotomic polynomials \Phi_{pq}(x) provided by T. Y. Lam and K. H. Leung in their 1996 analysis, confirming that their coefficients lie in \{-1, 0, 1\}. As of 2025, the subexponential bounds described above remain the state-of-the-art asymptotic bounds, with no tighter general estimates known.[14] Related computational results confirm that \Phi_n(x) has all coefficients in \{0, \pm 1\} for n < 105, and larger coefficients appear only for highly composite n with at least three distinct odd prime factors. The following table lists the smallest such n along with their heights A(n):| n | A(n) |
|---|---|
| 105 | 2 |
| 385 | 3 |
| 1365 | 4 |
| 1785 | 5 |
| 2805 | 6 |