info prev up next book cdrom email home

Cyclotomic Polynomial

A polynomial given by

\Phi_d(x)=\prod_{k=1}^d (x-\zeta_k),
\end{displaymath} (1)

where $\zeta_i$ are the primitive $d$th Roots of Unity in $\Bbb{C}$ given by $\zeta_k=e^{2\pi i
k/d}$. The numbers $\zeta_k$ are sometimes called de Moivre Numbers. $\Phi_d(x)$ is an irreducible Polynomial in $\Bbb{Z}[x]$ with degree $\phi(d)$, where $\phi$ is the Totient Function. For $d$ Prime,
\Phi_p=\sum_{k=0}^{p-1} x^k,
\end{displaymath} (2)

i.e., the coefficients are all 1. $\Phi_{105}$ has coefficients of $-2$ for $x^7$ and $x^{41}$, making it the first cyclotomic polynomial to have a coefficient other than $\pm 1$ and 0. This is true because 105 is the first number to have three distinct Odd Prime factors, i.e., $105=3\cdot 5\cdot 7$ (McClellan and Rader 1979, Schroeder 1997). Migotti (1883) showed that Coefficients of $\Phi_{pq}$ for $p$ and $q$ distinct Primes can be only 0, $\pm 1$. Lam and Leung (1996) considered
\Phi_{pq}\equiv \sum_{k=0}^{pq-1} a_k x^k
\end{displaymath} (3)

for $p,q$ Prime. Write the Totient Function as
\end{displaymath} (4)

and let
0\leq k\leq (p-1)(q-1),
\end{displaymath} (5)

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

2. $a_k=-1$ Iff $k+pq=ip+jq$ for $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$.

The Logarithm of the cyclotomic polynomial

\Phi_n(x)=\prod_{d\vert n}(1-x^{n/d})^{\mu(d)}
\end{displaymath} (6)

is the Möbius Inversion Formula (Vardi 1991, p. 225).

The first few cyclotomic Polynomials are

$\displaystyle \Phi_1(x)$ $\textstyle =$ $\displaystyle x-1$  
$\displaystyle \Phi_2(x)$ $\textstyle =$ $\displaystyle x+1$  
$\displaystyle \Phi_3(x)$ $\textstyle =$ $\displaystyle x^2+x+1$  
$\displaystyle \Phi_4(x)$ $\textstyle =$ $\displaystyle x^2+1$  
$\displaystyle \Phi_5(x)$ $\textstyle =$ $\displaystyle x^4+x^3+x^2+x+1$  
$\displaystyle \Phi_6(x)$ $\textstyle =$ $\displaystyle x^2-x+1$  
$\displaystyle \Phi_7(x)$ $\textstyle =$ $\displaystyle x^6+x^5+x^4+x^3+x^2+x+1$  
$\displaystyle \Phi_8(x)$ $\textstyle =$ $\displaystyle x^4+1$  
$\displaystyle \Phi_9(x)$ $\textstyle =$ $\displaystyle x^6+x^3+1$  
$\displaystyle \Phi_{10}(x)$ $\textstyle =$ $\displaystyle x^4-x^3+x^2-x+1.$  

The smallest values of $n$ for which $\Phi_n$ has one or more coefficients $\pm 1$, $\pm 2$, $\pm 3$, ... are 0, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465, 10465, 10465, 10465, 11305, ... (Sloane's A013594).

The Polynomial $x^n-1$ can be factored as

x^n-1=\prod_{d\vert n} \Phi_d(x),
\end{displaymath} (7)

where $\Phi_d(x)$ is a Cyclotomic Polynomial. Furthermore,
x^n+1={x^{2n}-1\over x^n-1} ={\prod_{d\vert 2n} \Phi_d(x)\over \prod_{d\vert n}\Phi_d(x)}.
\end{displaymath} (8)

The Coefficients of the inverse of the cyclotomic Polynomial
$\displaystyle {1\over 1+x+x^2}$ $\textstyle =$ $\displaystyle 1-x+x^3-x^4+x^6-x^7+x^9-x^{10}+\ldots$  
  $\textstyle \equiv$ $\displaystyle \sum_{n=0}^\infty c_n x^n$ (9)

can also be computed from
c_n=1-2\left\lfloor{{\textstyle{1\over 3}}(n+2)}\right\rfloo...
...t\rfloor +\left\lfloor{{\textstyle{1\over 3}}n}\right\rfloor ,
\end{displaymath} (10)

where $\left\lfloor{x}\right\rfloor $ is the Floor Function.

See also Aurifeuillean Factorization, Möbius Inversion Formula


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.

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.

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 Coefficients of the Cyclotomic Polynomials.'' 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.

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.

Sloane, N. J. A. Sequence A013594 in ``The On-Line Version of the Encyclopedia of Integer Sequences.''

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 8 and 224-225, 1991.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein