TOPICS
Search

Cyclotomic Polynomial

The cyclotomic polynomial Phi_n(x), for a positive integer n, is the polynomial given by

Phi_n(x)=product_(k=1)^n^'(x-zeta_k),
(1)

where zeta_k are the roots of unity in C given by

zeta_k=e^(2piik/n)
(2)

and k runs over integers relatively prime to n. The prime may be dropped if the product is instead taken over primitive roots of unity, so that

Phi_n(x)=product_(k=1; primitive zeta_k)^n(x-zeta_k).
(3)

The notation F_n(x) is also frequently encountered. Dickson et al. (1923) and Apostol (1975) give extensive bibliographies for cyclotomic polynomials.

The cyclotomic polynomial for n>1 can also be defined as

Phi_n(x)=product_(d|n)(1-x^(n/d))^(mu(d)),
(4)

where mu(d) is the Möbius function and the product is taken over the divisors d of n (Vardi 1991, p. 225).

Cyclotomic polynomial roots

Phi_n(x) is an integer polynomial and an irreducible polynomial over Q with polynomial degree phi(n), where phi(n) is the totient function. Cyclotomic polynomials are returned by the Wolfram Language command Cyclotomic[n, x]. The roots of cyclotomic polynomials lie on the unit circle in the complex plane, as illustrated above for the first few cyclotomic polynomials.

Cyclotomic

The first few cyclotomic polynomials are

Phi_1(x)=x-1
(5)
Phi_2(x)=x+1
(6)
Phi_3(x)=x^2+x+1
(7)
Phi_4(x)=x^2+1
(8)
Phi_5(x)=x^4+x^3+x^2+x+1
(9)
Phi_6(x)=x^2-x+1
(10)
Phi_7(x)=x^6+x^5+x^4+x^3+x^2+x+1
(11)
Phi_8(x)=x^4+1
(12)
Phi_9(x)=x^6+x^3+1
(13)
Phi_(10)(x)=x^4-x^3+x^2-x+1.
(14)
CyclotomicPhiReIm
CyclotomicPhiContours

The cyclotomic polynomial Phi_7(z) is illustrated above in the complex plane.

For any fixed real theta and positive integer n, the absolute value |Phi_n(re^(itheta))| is strictly increasing as r>1 increases along the corresponding ray outside the unit disk.

If p is an odd prime, then

Phi_p(x)=(x^p-1)/(x-1)
(15)
=x^(p-1)+x^(p-2)+...+x+1
(16)
Phi_(2p)(x)=(x^(2p)-1)/(x^p-1)(x-1)/(x^2-1)
(17)
=x^(p-1)-x^(p-2)+...-x+1
(18)
Phi_(4p)(x)=(x^(4p)-1)/(x^(2p)-1)(x^2-1)/(x^4-1)
(19)
=x^(2p-2)-x^(2p-4)+...-x^2+1
(20)

(Riesel 1994, p. 306). Similarly, for p again an odd prime,

x^p-1=Phi_1(x)Phi_p(x)
(21)
x^(2p)-1=Phi_1(x)Phi_2(x)Phi_p(x)Phi_(2p)(x)
(22)
x^(4p)-1=Phi_1(x)Phi_2(x)Phi_4(x)Phi_p(x)Phi_(2p)(x)Phi_(4p)(x).
(23)

For the first few remaining values of n,

x-1=Phi_1(x)
(24)
x^2-1=Phi_1(x)Phi_2(x)
(25)
x^4-1=Phi_1(x)Phi_2(x)Phi_4(x)
(26)
x^8-1=Phi_1(x)Phi_2(x)Phi_4(x)Phi_8(x)
(27)
x^9-1=Phi_1(x)Phi_3(x)Phi_9(x)
(28)
x^(15)-1=Phi_1(x)Phi_3(x)Phi_5(x)Phi_(15)(x)
(29)
x^(16)-1=Phi_1(x)Phi_2(x)Phi_4(x)Phi_8(x)Phi_(16)(x)
(30)
x^(18)-1=Phi_1(x)Phi_2(x)Phi_3(x)Phi_6(x)Phi_9(x)Phi_(18)(x)
(31)

(Riesel 1994, p. 307).

For p a prime relatively prime to n,

Phi_(np)(x)=(Phi_n(x^p))/(Phi_n(x)),
(32)

but if p|n,

Phi_(np)(x)=Phi_n(x^p)
(33)

(Nagell 1951, p. 160).

An explicit equation for Phi_n(x) for squarefree positive integers n is given by

Phi_n(x)=sum_(j=0)^(phi(n))a_(nj)x^(phi(n)-j),
(34)

where phi(n) is the totient function and a_(nj) is calculated using the recurrence relation

a_(nj)=-(mu(n))/jsum_(m=0)^(j-1)a_(nm)mu(GCD(n,j-m))phi(GCD(n,j-m))
(35)

for 1<=j<=phi(n), with a_(n0)=1, where mu(n) is the Möbius function and GCD(m,n) is the greatest common divisor of m and n.

The polynomial x^n-1 can be factored as

x^n-1=product_(d|n)Phi_d(x).
(36)

Furthermore,

x^n+1=(x^(2n)-1)/(x^n-1)
(37)
=(product_(d|2n)Phi_d(x))/(product_(d|n)Phi_d(x)).
(38)

For |x|<1, the coefficients of the inverse of the cyclotomic polynomial

1/(1+x+x^2)=1-x+x^3-x^4+x^6-x^7+x^9-...
(39)
=sum_(n=0)^(infty)c_nx^n
(40)

can also be computed from

c_n=1-2|_1/3(n+2)_|+|_1/3(n+1)_|+|_1/3n_|
(41)
=1-3|_1/3(n+2)_|+|_n_|
(42)
=2/(sqrt(3))sin[2/3pi(n+1)],
(43)

where n is a nonnegative integer and |_x_| is the floor function.

For p prime,

Phi_p(x)=sum_(k=0)^(p-1)x^k,
(44)

i.e., the coefficients are all 1. The first cyclotomic polynomial to have a coefficient other than +/-1 and 0 is Phi_(105)(x), which has coefficients of -2 for x^7 and x^(41). This is true because 105 is the first number to have three distinct odd prime factors, i.e., 105=3·5·7 (McClellan and Rader 1979, Schroeder 1997). The smallest values of n for which Phi_n(x) has one or more coefficients +/-1, +/-2, +/-3, ... are 1, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465, 10465, 10465, 10465, 11305, ... (OEIS A013594, which uses an initial term of 0 instead of 1).

It appears to be true that, for m,n>1, if Phi_m(x)+Phi_n(x) factors, then the factors contain a cyclotomic polynomial. For example,

Phi_7(x)+Phi_(22)(x)=(x^2+1)(x^8-x^7+2x^4+2)
(45)
=Phi_4(x)(x^8-x^7+2x^4+2).
(46)

This observation has been checked up to m,n=150 (Nicol 2000). If m and n are prime, then Phi_m(x)+Phi_n(x) is irreducible over Q.

Migotti (1883) showed that coefficients of Phi_(pq)(x) for p and q distinct primes can be only 0, +/-1. Lam and Leung (1996) considered

Phi_(pq)(x)=sum_(k=0)^(pq-1)a_kx^k
(47)

for distinct primes p and q. Write the totient function as

phi(pq)=(p-1)(q-1)=rp+sq,
(48)

where r and s are the unique integers with 0<=r<q and 0<=s<p. For an integer k with 0<=k<=(p-1)(q-1),

1. a_k=1 iff k=ip+jq for some integers i in [0,r] and j in [0,s],

2. a_k=-1 iff k+pq=ip+jq for some integers i in [r+1,q-1] and j in [s+1,p-1],

3. otherwise a_k=0.

The number of terms having a_k=1 is (r+1)(s+1), and the number of terms having a_k=-1 is (p-s-1)(q-r-1). Furthermore, assume q>p, then the middle coefficient of Phi_(pq) is (-1)^r.

Resultants of cyclotomic polynomials have been computed by Lehmer (1936), Diederichsen (1940), and Apostol (1970). It is known that rho(Phi_m(x),Phi_n(x))=1 if m,n>1 and (m,n)=1, i.e., m and n are relatively prime (Apostol 1975). Apostol (1975) showed that for positive integers m,n>1 and arbitrary nonzero complex numbers a and b,

rho(Phi_m(ax),Phi_n(bx))=b^(phi(m)phi(n))product_(d|n)[Phi_(m/delta)((a^d)/(b^d))]^(mu(n/d)phi(m)/phi(m/delta)),
(49)

where delta=GCD(m,d) is the greatest common divisor of m and d, phi(n) is the totient function, mu(n) is the Möbius function, and the product is over the divisors of n. If m and n are distinct primes p and q, then (49) simplifies to

rho(Phi_q(ax),Phi_p(bx))={(a^(pq)-b^(pq))/(a^p-b^p)(a-b)/(a^q-b^q) for a!=b; a^((p-1)(q-1)) for a=b.
(50)

Quotients in these formulas are interpreted by continuity when a denominator vanishes. The following table gives the resultants rho(Phi_n(x),Phi_k(x)) for 1<=n<=k (OEIS A054372).

k\n1234567
10
220
3310
42210
551110
6134110
77111110

The numbers of 1s in successive rows of this table are given by 0, 0, 1, 1, 3, 3, 5, 4, 6, 7, 9, ... (OEIS A075795).

The cyclotomic polynomial Phi_6(x) has the particularly nice Maclaurin series

1/(Phi_6(x))=1+x-x^3-x^4+x^6+x^7-x^9-x^(10)+...
(51)

for |x|<1. Its coefficients, starting with the constant term, are 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, ... (OEIS A010892). They are given by solving the recurrence equation

a(n)=a(n-1)-a(n-2)
(52)

for n>=2, with a(0)=a(1)=1 (Wolfram 2002, p. 128), giving the explicit form

a(n)=2/3sqrt(3)sin[1/3(n+1)pi].
(53)

Interestingly, any sequence b(n) satisfying the linear recurrence equation

b(n)=b(n-1)-b(n-2)
(54)

for n>=2 can be written for n>=1 as

b(n)=b(0)a(n)+[b(1)-b(0)]a(n-1).
(55)

See also

Aurifeuillean Factorization, Gauss's Cyclotomic Formula, Lucas's Theorem, Möbius Inversion Formula, Primitive Root of Unity, Root of Unity

Related Wolfram sites

https://functions.wolfram.com/Polynomials/Cyclotomic/

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Apostol, T. M. "Resultants of Cyclotomic Polynomials." Proc. Amer. Math. Soc. 24, 457-462, 1970.Apostol, T. M. "The Resultant of the Cyclotomic Polynomials F_m(ax) and F_n(bx)." Math. Comput. 29, 1-6, 1975.Beiter, M. "The Midterm Coefficient of the Cyclotomic Polynomial F_(pq)(x)." Amer. Math. Monthly 71, 769-770, 1964.Beiter, M. "Magnitude of the Coefficients of the Cyclotomic Polynomial F_(pq)." Amer. Math. Monthly 75, 370-372, 1968.Bloom, D. M. "On the Coefficients of the Cyclotomic Polynomials." Amer. Math. Monthly 75, 372-377, 1968.Brent, R. P. "On Computing Factors of Cyclotomic Polynomials." Math. Comput. 61, 131-149, 1993.Carlitz, L. "The Number of Terms in the Cyclotomic Polynomial F_(pq)(x)." Amer. Math. Monthly 73, 979-981, 1966.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, 1996.de Bruijn, N. G. "On the Factorization of Cyclic Groups." Indag. Math. 15, 370-377, 1953.Dickson, L. E.; Mitchell, H. H.; Vandiver, H. S.; and Wahlin, G. E. Algebraic Numbers. Bull Nat. Res. Council, Vol. 5, Part 3, No. 28. Washington, DC: National Acad. Sci., 1923.Diederichsen, F.-E. "Über die Ausreduktion ganzzahliger Gruppendarstellungen bei arithmetischer Äquivalenz." Abh. Math. Sem. Hanisches Univ. 13, 357-412, 1940.Lam, T. Y. and Leung, K. H. "On the Cyclotomic Polynomial Phi_(pq)(X)." Amer. Math. Monthly 103, 562-564, 1996.Lehmer, E. "On the Magnitude of the Coefficients of the Cyclotomic Polynomial." Bull. Amer. Math. Soc. 42, 389-392, 1936.McClellan, J. H. and Rader, C. Number Theory in Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1979.Migotti, A. "Zur Theorie der Kreisteilungsgleichung." Sitzber. Math.-Naturwiss. Classe der Kaiser. Akad. der Wiss., Wien 87, 7-14, 1883.Nagell, T. "The Cyclotomic Polynomials" and "The Prime Divisors of the Cyclotomic Polynomial." §46 and 48 in Introduction to Number Theory. New York: Wiley, pp. 158-160 and 164-168, 1951.Nicol, C. "Sums of Cyclotomic Polynomials." Apr. 26, 2000. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0004&L=nmbrthry&T=0&F=&S=&P=2317.Riesel, H. "The Cyclotomic Polynomials" in Appendix 6. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 305-308, 1994.Schroeder, M. R. Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity, 3rd ed. New York: Springer-Verlag, p. 245, 1997.Séroul, R. "Cyclotomic Polynomials." §10.8 in Programming for Mathematicians. Berlin, Germany: Springer-Verlag, pp. 265-269, 2000.Sloane, N. J. A. Sequences A010892, A013594, A054372, and A075795 in "The On-Line Encyclopedia of Integer Sequences."Trott, M. "The Mathematica Guidebooks Additional Material: Graphics of the Argument of Cyclotomic Polynomials." https://www.mathematicaguidebooks.org/additions.shtml#N_2_03.Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 8 and 224-225, 1991.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002.

Referenced on Wolfram|Alpha

Cyclotomic Polynomial

Cite this as:

Weisstein, Eric W. "Cyclotomic Polynomial." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CyclotomicPolynomial.html

Subject classifications