Cyclotomic polynomial
In mathematics, the n -th cyclotomic polynomial, for any positive integer n , is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any k .
≈ 22 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, the n -th cyclotomic polynomial, for any positive integer n , is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any k . Its roots are all n -th primitive roots of unity e^{2i\pi\frac{k}{n}} , where k runs over the positive integers up to n and coprime to n (where i is the imaginary unit). In other words, the n -th cyclotomic polynomial is equal to : \Phi_n(x) = \prod_\stackrel{1\le k\le n}{\gcd(k,n)=1} \left(x-e^{2i\pi\frac{k}{n}}\right).
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 ( e^{2i\pi/n} is an example of such a root). An important relation linking cyclotomic polynomials and primitive roots of unity is : \prod_{d\mid n}\Phi_d(x) = x^n - 1, showing that \alpha is a root of x^n - 1 if and only if it is a d -th primitive root of unity for some d that divides n .
In mathematics, the n -th cyclotomic polynomial, for any positive integer n , is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any k . Its roots are all n -th primitive roots of unity e^{2i\pi\frac{k}{n}} , where k runs over the positive integers up to n and coprime to n (where i is the imaginary unit). In other words, the n -th cyclotomic polynomial is equal to \Phi_n(x) = \prod_\stackrel{1\le k\le n}{\gcd(k,n)=1} \left(x-e^{2i\pi\frac{k}{n}}\right).
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 ( e^{2i\pi/n} is an example of such a root). An important relation linking cyclotomic polynomials and primitive roots of unity is \prod_{d\mid n}\Phi_d(x) = x^n - 1, showing that \alpha is a root of x^n - 1 if and only if it is a d -th primitive root of unity for some d that divides n .
Examples
If n is a prime number, then \Phi_n(x) = 1+x+x^2+\cdots+x^{n-1}=\sum_{k=0}^{n-1} x^k. If n = 2p where p is a prime number other than 2, then \Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{k=0}^{p-1} (-x)^k. For n up to 30, the cyclotomic polynomials are: \begin{align} \Phi_1(x) &= x - 1 \\ \Phi_2(x) &= x + 1 \\ \Phi_3(x) &= x^2 + x + 1 \\ \Phi_4(x) &= x^2 + 1 \\ \Phi_5(x) &= x^4 + x^3 + x^2 + x +1 \\ \Phi_6(x) &= x^2 - x + 1 \\ \Phi_7(x) &= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_8(x) &= x^4 + 1 \\ \Phi_9(x) &= x^6 + x^3 + 1 \\ \Phi_{10}(x) &= x^4 - x^3 + x^2 - x + 1 \\ \Phi_{11}(x) &= x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{12}(x) &= x^4 - x^2 + 1 \\ \Phi_{13}(x) &= x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{14}(x) &= x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\ \Phi_{15}(x) &= x^8 - x^7 + x^5 - x^4 + x^3 - x + 1 \\ \Phi_{16}(x) &= x^8 + 1 \\ \Phi_{17}(x) &= x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\ \Phi_{18}(x) &= x^6 - x^3 + 1 \\ \Phi_{19}(x) &= x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\ \Phi_{20}(x) &= x^8 - x^6 + x^4 - x^2 + 1 \\ \Phi_{21}(x) &= x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1 \\ \Phi_{22}(x) &= x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\ \Phi_{23}(x) &= x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} \\ & \qquad\quad + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{24}(x) &= x^8 - x^4 + 1 \\ \Phi_{25}(x) &= x^{20} + x^{15} + x^{10} + x^5 + 1 \\ \Phi_{26}(x) &= x^{12} - x^{11} + x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\ \Phi_{27}(x) &= x^{18} + x^9 + 1 \\ \Phi_{28}(x) &= x^{12} - x^{10} + x^8 - x^6 + x^4 - x^2 + 1 \\ \Phi_{29}(x) &= x^{28} + x^{27} + x^{26} + x^{25} + x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} \\ & \qquad\quad + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\ \Phi_{30}(x) &= x^8 + x^7 - x^5 - x^4 - x^3 + x + 1. \end{align} The case of the 105th cyclotomic polynomial is interesting because 105 is the least positive integer that is the product of three distinct odd prime numbers (3×5×7) and this polynomial is the first one that has a coefficient other than 1, 0, or −1: \begin{align} \Phi_{105}(x) ={}&x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2 x^{41} - x^{40} - x^{39} + x^{36} + x^{35} + x^{34} \\ &{}+ x^{33} + x^{32} + x^{31} - x^{28} - x^{26} - x^{24} - x^{22} - x^{20} + x^{17} + x^{16} + x^{15} \\ &{}+ x^{14} + x^{13} + x^{12} - x^9 - x^8 - 2 x^7 - x^6 - x^5 + x^2 + x + 1. \end{align}
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 palindromes of even degree. The degree of \Phi_n , or in other words the number of nth primitive roots of unity, is \varphi (n) , where \varphi is Euler's totient function.
The fact that \Phi_n is an irreducible polynomial of degree \varphi (n) in the ring \Z[x] 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 \begin{align} x^n - 1 &=\prod_{1\leqslant k\leqslant n} \left(x- e^{2i\pi\frac{k}{n}} \right) \\ &= \prod_{d \mid n} \prod_{1 \leqslant k \leqslant n \atop \gcd(k, n) = d} \left(x- e^{2i\pi\frac{k}{n}} \right) \\ &=\prod_{d \mid n} \Phi_{\frac{n}{d}}(x) = \prod_{d\mid n} \Phi_d(x).\end{align} 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 \Phi_n(x) to be expressed as an explicit rational fraction: \Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu \left (\frac{n}{d} \right )}, where \mu is the Möbius function. This provides a recursive formula for the cyclotomic polynomial \Phi_{n}(x) , which may be computed by dividing x^n-1 by the cyclotomic polynomials \Phi_d(x) for the proper divisors d dividing n, starting from \Phi_{1}(x)=x-1 : \Phi_n(x)=\frac{x^{n}-1}{\prod_{\stackrel{d|n}{{}_{d This gives an algorithm for computing any \Phi_n(x) , provided integer factorization and division of polynomials are available.
Many computer algebra systems, such as SageMath, Maple, Mathematica, and PARI/GP, have a built-in function to compute the cyclotomic polynomials.
Easy cases for computation
As noted above, if is a prime number, then \Phi_p(x) = 1+x+x^2+\cdots+x^{p-1}=\sum_{k=0}^{p-1}x^k\;. If n is an odd integer greater than one, then \Phi_{2n}(x) = \Phi_n(-x)\;. In particular, if is twice an odd prime, then (as noted above) \Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{k=0}^{p-1}(-x)^k\;.
If is a prime power (where p is prime), then \Phi_{p^m}(x) = \Phi_p(x^{p^{m-1}}) =\sum_{k=0}^{p-1}x^{kp^{m-1}}\;. More generally, if with relatively prime to , then \Phi_{p^mr}(x) = \Phi_{pr}(x^{p^{m-1}})\;.
These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial \Phi_n(x) in terms of a cyclotomic polynomial of square free index: If is the product of the prime divisors of (its radical), then \Phi_n(x) = \Phi_q(x^{n/q})\;. This allows formulas to be given 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 \Phi_{2^m}(x) = x^{2^{m-1}}+1\;, \Phi_{p^m}(x) = \sum_{j=0}^{p-1}x^{jp^{m-1}}\;, \Phi_{2^\ell p^m}(x) = \sum_{j=0}^{p-1}(-1)^jx^{j2^{\ell-1}p^{m-1}}\;.
For other values of , the computation of the th cyclotomic polynomial is similarly reduced to that of \Phi_q(x), where is the product of the distinct odd prime divisors of . To deal with this case, one has that, for prime and not dividing , \Phi_{np}(x)=\Phi_{n}(x^p)/\Phi_n(x)\;.
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 \Phi_n are all in the set {1, −1, 0}.
The first cyclotomic polynomial for a product of three different odd prime factors is \Phi_{105}(x); it has a coefficient −2 (see above). The converse is not true: \Phi_{231}(x)=\Phi_{3\times 7\times 11}(x) only has coefficients in {1, −1, 0}. If n is a product of more different odd prime factors, the coefficients may increase to very high values.
E.g., \Phi_{15015}(x) =\Phi_{3\times 5\times 7\times 11\times 13}(x) has coefficients running from −22 to 23; also \Phi_{255255}(x)=\Phi_{3\times 5\times 7\times 11\times 13\times 17}(x) , the smallest n with 6 different odd primes, has coefficients of magnitude up to 532. Let A(n) denote the maximum absolute value of the coefficients of \Phi_{n}(x) . It is known that for any positive k, the number of n up to x with A(n) > n k is at least c(k)⋅x for a positive c(k) depending on k and x sufficiently large.
In the opposite direction, for any function ψ(n) tending to infinity with n we have A(n) bounded above by n ψ(n) for almost all n. A combination of theorems of Bateman and Vaughan states that on the one hand, for every \varepsilon>0 , we have A(n) for all sufficiently large positive integers n , and on the other hand, we have A(n) > e^{\left(n^{(\log 2)/(\log\log n)}\right)} for infinitely many positive integers n . This implies in particular that univariate polynomials (concretely x^n-1 for infinitely many positive integers n ) can have factors (like \Phi_n ) whose coefficients are superpolynomially larger than the original coefficients. This is not too far from the general Landau-Mignotte bound.
Gauss's formula
Let n be odd, square-free, and greater than 3. Then: 4\Phi_n(z) = A_n^2(z) - (-1)^{\frac{n-1}{2}}nz^2B_n^2(z) for certain polynomials A n (z) and B n (z) with integer coefficients, A n (z) of degree φ(n)/2, and B n (z) of degree φ(n)/2 − 2. Furthermore, A n (z) is palindromic when its degree is even; if its degree is odd it is antipalindromic.
Similarly, B n (z) is palindromic unless n is composite and n ≡ 3 (mod 4), in which case it is antipalindromic. The first few cases are \begin{align} 4\Phi_5(z) &=4(z^4+z^3+z^2+z+1)\\ &= (2z^2+z+2)^2 - 5z^2 \\[6pt] 4\Phi_7(z) &=4(z^6+z^5+z^4+z^3+z^2+z+1)\\ &= (2z^3+z^2-z-2)^2+7z^2(z+1)^2 \\ [6pt] 4\Phi_{11}(z) &=4(z^{10}+z^9+z^8+z^7+z^6+z^5+z^4+z^3+z^2+z+1)\\ &= (2z^5+z^4-2z^3+2z^2-z-2)^2+11z^2(z^3+1)^2 \end{align}
Lucas's formula
Let n be odd, square-free and greater than 3. Then \Phi_n(z) = U_n^2(z) - (-1)^{\frac{n-1}{2}}nzV_n^2(z) for certain polynomials U n (z) and V n (z) with integer coefficients, U n (z) of degree φ(n)/2, and V n (z) of degree φ(n)/2 − 1.
This can also be written \Phi_n \left ((-1)^{\frac{n-1}{2}}z \right ) = C_n^2(z) - nzD_n^2(z). If n is even, square-free and greater than 2 (this forces n/2 to be odd), \Phi_{\frac{n}{2}} (-z^2) = \Phi_{2n}(z)= C_n^2(z) - nzD_n^2(z) for C n (z) and D n (z) with integer coefficients, C n (z) of degree φ(n), and D n (z) of degree φ(n) − 1. C n (z) and D n (z) are both palindromic.
The first few cases are: \begin{align} \Phi_3(-z) &=\Phi_6(z) =z^2-z+1 \\ &= (z+1)^2 - 3z \\[6pt] \Phi_5(z) &=z^4+z^3+z^2+z+1 \\ &= (z^2+3z+1)^2 - 5z(z+1)^2 \\[6pt] \Phi_{6/2}(-z^2) &=\Phi_{12}(z)=z^4-z^2+1 \\ &= (z^2+3z+1)^2 - 6z(z+1)^2 \end{align}
Sister Beiter conjecture
The Sister Beiter conjecture is concerned with the maximal size (in absolute value) A(pqr) of coefficients of ternary cyclotomic polynomials \Phi_{pqr}(x) where p\leq q\leq r are three odd primes.
Polynomial values
If takes any real value, then \Phi_n(x)>0 for every (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for ). 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 (one has \Phi_1(x)=x-1 and \Phi_2(x)=x+1 ).
For , one has \Phi_n(0) =1, \Phi_n(1) =1 if is not a prime power, \Phi_n(1) =p if n=p^k is a prime power with . The values that a cyclotomic polynomial \Phi_n(x) 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 b^n-1. For , the multiplicative order of modulo is also the shortest period of the representation of in the numeral base (see Unique prime; this explains the notation choice).
The definition of the multiplicative order implies that, if is the multiplicative order of modulo , then is a divisor of \Phi_n(b). The converse is not true, but one has the following. If is a positive integer and is an integer, then (see below for a proof) \Phi_n(b)=2^kgh, where is a non-negative integer, always equal to 0 when is even.
(In fact, if is neither 1 nor 2, then is either 0 or 1. Besides, if is not a power of 2, then is always equal to 0) is 1 or the largest odd prime factor of . is odd, coprime with , and its prime factors are exactly the odd primes such that is the multiplicative order of modulo . This implies that, if is an odd prime divisor of \Phi_n(b), then either is a divisor of or is a divisor of .
In the latter case, p^2 does not divide \Phi_n(b). Zsigmondy's theorem implies that the only cases where and are \begin{align} \Phi_1(2) &=1 \\ \Phi_2 \left (2^k-1 \right ) & =2^k && k >0 \\ \Phi_6(2) &=3 \end{align} It follows from above factorization that the odd prime factors of \frac{\Phi_n(b)}{\gcd(n,\Phi_n(b))} 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 \Phi_n(b) is prime. In fact, Bunyakovsky conjecture implies that, for every , there are infinitely many such that \Phi_n(b) is prime.
See for the list of the smallest such that \Phi_n(b) is prime (the smallest such that \Phi_n(b) is prime is about \gamma \cdot \varphi(n) , where \gamma is Euler–Mascheroni constant, and \varphi is Euler's totient function). See also for the list of the smallest primes of the form \Phi_n(b) with and , and, more generally, , for the smallest positive integers of this form.
Values of \Phi_n(1). If n=p^{k+1} is a prime power, then \Phi_n(x)=1+x^{p^k}+x^{2p^{k}}+\cdots+x^{(p-1)p^k} \qquad \text{and} \qquad \Phi_n(1)=p. If is not a prime power, let P(x)=1+x+\cdots+x^{n-1}, we have P(1)=n, and is the product of the \Phi_k(x) for dividing and different of .
If is a prime divisor of multiplicity in , then \Phi_p(x), \Phi_{p^2}(x), \cdots, \Phi_{p^m}(x) divide , and their values at are factors equal to of n=P(1). As is the multiplicity of in , cannot divide the value at of the other factors of P(x). Thus there is no prime that divides \Phi_n(1). If is the multiplicative order of modulo , then p \mid \Phi_n(b). By definition, p \mid b^n-1.
If p \nmid \Phi_n(b), then would divide another factor \Phi_k(b) of b^n-1, and would thus divide b^k-1, showing that, if there would be the case, would not be the multiplicative order of modulo . The other prime divisors of \Phi_n(b) are divisors of . Let be a prime divisor of \Phi_n(b) such that is not be the multiplicative order of modulo .
If is the multiplicative order of modulo , then divides both \Phi_n(b) and \Phi_k(b). The resultant of \Phi_n(x) and \Phi_k(x) may be written P\Phi_k+Q\Phi_n, where and are polynomials. Thus divides this resultant. As divides , and the resultant of two polynomials divides the discriminant of any common multiple of these polynomials, divides also the discriminant n^n of x^n-1.
Thus divides . and are coprime. In other words, if is a prime common divisor of and \Phi_n(b), then is not the multiplicative order of modulo . By Fermat's little theorem, the multiplicative order of is a divisor of , and thus smaller than . is square-free.
In other words, if is a prime common divisor of and \Phi_n(b), then p^2 does not divide \Phi_n(b). Let . It suffices to prove that p^2 does not divide for some polynomial , which is a multiple of \Phi_n(x). We take S(x)=\frac{x^n-1}{x^m-1} = 1 + x^m + x^{2m} + \cdots + x^{(p-1)m}. The multiplicative order of modulo divides , which is a divisor of .
Thus is a multiple of . Now, S(b) = \frac{(1+c)^p-1}{c} = p+ \binom{p}{2}c + \cdots + \binom{p}{p}c^{p-1}. As is prime and greater than 2, all the terms but the first one are multiples of p^2.
This proves that p^2 \nmid \Phi_n(b).
Applications
Using \Phi_n , 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 p_1, p_2, \ldots, p_k is a finite list of primes congruent to 1 modulo n. Let N = np_1p_2\cdots p_k and consider \Phi_n(N) . Let q be a prime factor of \Phi_n(N) (to see that \Phi_n(N) \neq \pm 1 decompose it into linear factors and note that 1 is the closest root of unity to N ). Since \Phi_n(x) \equiv \pm 1 \pmod x, we know that q is a new prime not in the list.
We will show that q \equiv 1 \pmod n. Let m be the order of N modulo q. Since \Phi_n(N) \mid N^n - 1 we have N^n -1 \equiv 0 \pmod{q} . Thus m \mid n . We will show that m = n . Assume for contradiction that m . Since \prod_{d \mid m} \Phi_d(N) = N^m - 1 \equiv 0 \pmod q we have \Phi_d(N) \equiv 0 \pmod q, for some d . Then N is a double root of \prod_{d \mid n} \Phi_d(x) \equiv x^n -1 \pmod q. Thus N must be a root of the derivative so \left.\frac{d(x^n -1)}{dx}\right|_N \equiv nN^{n-1} \equiv 0 \pmod q. But q \nmid N and therefore q \nmid n. This is a contradiction so m = n . The order of N \pmod q, which is n , must divide q-1 .
Thus q \equiv 1 \pmod n. In the theory of combinatorial generating functions, the denominator of a rational function determines a linear recurrence for its power series coefficients. For example, the Fibonacci sequence has generating function F(x) = F_1x + F_2x^2 + F_3x^3 + \cdots = \frac{x}{1-x-x^2} , and equating coefficients on both sides of F(x)(1-x-x^2) = x gives F_n - F_{n-1} - F_{n-2} = 0 for n\geq 2 .
Any rational function whose denominator is a divisor of x^n - 1 has a recursive sequence of coefficients which is periodic with period at most n. For example, P(x) = -\frac{1+2x}{\Phi_6(x)} = \frac{1+2x}{1-x+x^2} = \sum_{n\geq 0} P_n x^n = 1 + 3 x + 2 x^2 - x^3 - 3 x^4 - 2 x^5 + x^6 + 3 x^7 + 2 x^8 + \cdots has coefficients defined by the recurrence P_n - P_{n-1} + P_{n-2} = 0 for n\geq 2 , starting from P_0=1, P_1=3 . But 1-x^6 = \Phi_6(x)\Phi_3(x)\Phi_2(x)\Phi_1(x) , so we may write P(x) = \frac{(1+2x)\Phi_3(x)\Phi_2(x)\Phi_1(x)}{1 - x^6}
See also
Cyclotomic field Aurifeuillean factorization Zsigmondy number Root of unity
Further reading
Gauss's book Disquisitiones Arithmeticae [Arithmetical Investigations] has been translated from Latin into French, German, and English. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes. - ; Reprinted 1965, New York: Chelsea, ; Corrected ed. 1986, New York: Springer, ,
Text derived from https://en.wikipedia.org/w/index.php?oldid=1376799198 under CC BY-SA 4.0; modifications have been made.