Cyclotomic Polynomial

A polynomial given by

$$\Phi_d(x)=\prod_{k=1}^d (x-\zeta_k),$$ (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,$$ (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$$ (3)

for $p,q$ Prime. Write the Totient Function as

$$\phi(pq)=(p-1)(q-1)=rp+sq$$ (4)

and let

$$0\leq k\leq (p-1)(q-1),$$ (5)

then

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)}$$ (6)

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

The first few cyclotomic Polynomials are

$$\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.$$

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),$$ (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)}.$$ (8)

The Coefficients of the inverse of the cyclotomic Polynomial

$${1\over 1+x+x^2} = 1-x+x^3-x^4+x^6-x^7+x^9-x^{10}+\ldots$$

$$\equiv \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 ,$$ (10)

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

See also Aurifeuillean Factorization, Möbius Inversion Formula

References

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.'' http://www.research.att.com/~njas/sequences/eisonline.html.

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