# Cyclotomic polynomials

Jordan Bell
April 12, 2017

## 1 Preliminaries

By an arithmetical function we mean a function whose domain contains the positive integers. We say that an arithmetical function $f$ is multiplicative when $\gcd(n,m)=1$ implies $f(nm)=f(n)f(m)$, and that it is completely multiplicative when $f(nm)=f(n)f(m)$ for all $n,m\geq 1$.

Write

 $U_{n}=\{e^{2\pi ik/n}:1\leq k\leq n\}=\{e^{2\pi ik/n}:0\leq k\leq n-1\},$

the $n$th roots of unity. For $n>1$, there is an element $\zeta$ of $U_{n}$ with $\zeta\neq 1$. Because $\xi\mapsto\zeta\xi$ is a bijection $U_{n}\to U_{n}$ we have $\zeta\sum_{\xi\in U_{n}}\xi=\sum_{\xi\in U_{n}}\xi$, hence $(1-\zeta)\sum_{\xi\in U_{n}}\xi=0$. But $\zeta\neq 1$, which means that

 $\sum_{k=0}^{n-1}e^{2\pi ik/n}=\sum_{\xi\in U_{n}}\xi=0,\qquad n>1.$

Write

 $\Delta_{n}=\{e^{2\pi ik/n}:1\leq k\leq n,\gcd(k,n)=1\},$

the primitive $n$th roots of unity. Let $\phi$ be the Euler phi function:

 $\phi(n)=|\{k:1\leq k\leq n,\gcd(k,n)=1\}|=|\Delta_{n}|.$

$\phi$ is multiplicative, and for prime $p$ and for $r\geq 1$, $\phi(p^{r})=p^{r-1}(p-1)$.

Let $\mu$ be the Möbius function:

 $\mu(n)=\sum_{1\leq k\leq n,\gcd(k,n)=1}e^{2\pi ik/n}=\sum_{\xi\in\Delta_{n}}\xi.$

For $p$ prime, as $\Delta_{p}=U_{p}\setminus\{1\}$,

 $\mu(p)=-1+\sum_{\xi\in U_{p}}\xi=0-1=-1.$

For $r\geq 2$, as $\Delta_{p^{r}}=U_{p^{r}}\setminus U_{p^{r-1}}$,

 $\mu(p^{r})=-\sum_{\xi\in U_{p^{r-1}}}\xi+\sum_{\xi\in U_{p^{r}}}\xi=-0+0=0.$

Furthermore, one proves that $\mu$ is multiplicative. Thus

 $\mu(n)=\begin{cases}1&\textrm{n is a square-free integer with an even number% of prime factors}\\ -1&\textrm{n is a square-free integer with an odd number of prime factors}\\ 0&\textrm{otherwise}.\end{cases}$

The Möbius inversion formula states that if $f$ and $g$ are arithmetic functions satisfying

 $g(n)=\sum_{d\mid n}f(d),\qquad n\geq 1,$

then

 $f(n)=\sum_{d\mid n}\mu(n/d)g(d),\qquad n\geq 1.$

We can write

 $U_{n}=\bigcup_{d\mid n}\Delta_{d},$

and $\Delta_{d}\cap\Delta_{e}=\emptyset$ for $d\neq e$. So

 $n=\sum_{d\mid n}\phi(d).$

Therefore by the Möbius inversion formula,

 $\phi(n)=\sum_{d\mid n}d\cdot\mu(n/d).$

Also, for $n>1$,

 $\sum_{d\mid n}\mu(d)=\sum_{d\mid n}\sum_{\xi\in\Delta_{d}}\xi=\sum_{\xi\in U_{% n}}\xi=0.$ (1)

Let

 $d(n)=\sum_{d\mid n}1,$

the number of divisors of $n$, for example, $d(6)=4$. Let

 $\omega(n)=\sum_{p\mid n}1,$

the number of prime divisors of $n$: for $n=p_{1}^{\alpha_{1}}\cdots p_{r}^{\alpha_{r}}$, $\alpha_{1},\ldots,\alpha_{r}\geq 1$, we have $\omega(n)=r$, for example $\omega(12)=\omega(2^{2}\cdot 3)=2$.

## 2 Definition and basic properties of cyclotomic polynomials

For $n\geq 1$, let

 $\Phi_{n}(x)=\prod_{1\leq k\leq n,\gcd(k,n)=1}(x-e^{2\pi ik/n})=\prod_{\xi\in% \Delta_{n}}(x-\xi),$

the $n$th cyclotomic polynomial. The first of the following two identities was found by Euler [45, pp. 199–200, Chap. III, §VI].

###### Lemma 1.

For $n\geq 1$,

 $x^{n}-1=\prod_{d\mid n}\Phi_{d}(x),$

and for $x\not\in U_{n}$,

 $\Phi_{n}(x)=\prod_{d\mid n}(x^{d}-1)^{\mu(n/d)}.$
###### Proof.

For $F_{n}(x)=x^{n}-1$, each of $e^{2\pi ik/n}$, $1\leq k\leq n$, is a distinct root of $F_{n}(x)$, so

 $\displaystyle x^{n}-1$ $\displaystyle=\prod_{1\leq k\leq n}(x-e^{2\pi ik/n})$ $\displaystyle=\prod_{d\mid n}\prod_{1\leq k\leq n,\gcd(k,n)=d}(x-e^{2\pi ik/n})$ $\displaystyle=\prod_{d\mid n}\prod_{1\leq j\leq n/d,\gcd(j,n/d)=1}(x-e^{2\pi ijd% /n})$ $\displaystyle=\prod_{d\mid n}\Phi_{n/d}(x)$ $\displaystyle=\prod_{d\mid n}\Phi_{d}(x).$

That is, $\log F_{n}=\sum_{d\mid n}\log\Phi_{d}$. Therefore applying the Möbius inversion formula yields $\log\Phi_{n}=\sum_{d\mid n}\mu(n/d)\log F_{d}$ and so $\Phi_{n}=\prod_{d\mid n}F_{d}^{\mu(n/d)}$. ∎

###### Lemma 2.

When $p$ is a prime,

 $\Phi_{p}(x)=x^{p-1}+\cdots+x+1.$

When $p$ is an odd prime,

 $\Phi_{2p}(x)=x^{p-1}-x^{p-2}+x^{p-3}-\cdots+x^{2}-x+1.$
###### Proof.

When $p$ is a prime, $x^{p}-1=\Phi_{1}(x)\cdot\Phi_{p}(x)$, i.e.

 $\Phi_{p}(x)=\frac{x^{p}-1}{\Phi_{1}(x)}=\frac{x^{p}-1}{x-1}=x^{p-1}+\cdots+x+1.$

When $p$ is an odd prime,

 $\Phi_{2p}(x)=\frac{x^{2p}-1}{\Phi_{1}(x)\Phi_{2}(x)\Phi_{p}(x)}=\frac{x^{2p}-1% }{(x^{p}-1)\Phi_{2}(x)}=\frac{(x^{p}-1)(x^{p}+1)}{(x^{p}-1)(x+1)}=\frac{x^{p}+% 1}{x+1},$

and because $(x+1)(x^{p-1}-x^{p-2}+x^{p-3}-\cdots+x^{2}-x+1)=x^{p}+1$,

 $\Phi_{2p}(x)=x^{p-1}-x^{p-2}+x^{p-3}-\cdots+x^{2}-x+1.$

###### Lemma 3.

If $p$ is a prime and $m\geq 1$,

 $\Phi_{pm}(x)=\begin{cases}\Phi_{m}(x^{p})&p|m\\ \Phi_{m}(x^{p})/\Phi_{m}(x)&p\nmid m.\end{cases}$

For $k\geq 1$,

 $\Phi_{p^{k}m}(x)=\begin{cases}\Phi_{m}(x^{p^{k}})&p|m\\ \Phi_{m}(x^{p^{k}})/\Phi_{m}(x^{p^{k-1}})&p\nmid m,\end{cases}$
###### Proof.

Using Lemma 1,

 $\displaystyle\Phi_{pm}(x)$ $\displaystyle=\prod_{d\mid(pm)}(x^{d}-1)^{\mu(pm/d)}$ $\displaystyle=\prod_{d\mid(pm),p|d}(x^{d}-1)^{\mu(pm/d)}\cdot\prod_{d\mid(pm),% p\nmid d}(x^{d}-1)^{\mu(pm/d)}$ $\displaystyle=\prod_{e\mid m}(x^{pe}-1)^{\mu(m/e)}\cdot\prod_{d\mid(pm),p\nmid d% }(x^{d}-1)^{\mu(pm/d)}$ $\displaystyle=\Phi_{m}(x^{p})\cdot\prod_{d\mid(pm),p\nmid d}(x^{d}-1)^{\mu(pm/% d)}.$

If $m=ap$ and $d|(pm)$ and $p\nmid d$, then $\mu(pm/d)=\mu(ap^{2}/d)=0$ and

 $\Phi_{pm}(x)=\Phi_{m}(x^{p})\cdot\prod_{d\mid a}(x^{d}-1)^{\mu(ap^{2}/d)}=\Phi% _{m}(x^{p}).$

If $p\nmid m$ and $d\mid(pm)$ and $p\nmid d$, then $\mu(pm/d)=\mu(p)\mu(m/d)=-\mu(m/d)$ and

 $\Phi_{pm}(x)=\Phi_{m}(x^{p})\cdot\prod_{d\mid(pm),p\nmid d}(x^{d}-1)^{\mu(pm/d% )}=\Phi_{m}(x^{p})\cdot\prod_{d\mid m}(x^{d}-1)^{-\mu(m/d)}.$

For $k\geq 2$,

 $\Phi_{p^{k}m}(x)=\Phi_{p\cdot p^{k-1}m}(x)=\Phi_{p^{k-1}m}(x^{p})=\cdots=\Phi_% {pm}(x^{p^{k-1}}),$

and using the expression we obtained for $\Phi_{pm}(x)$ we get the expression stated for $\Phi_{p^{k}m}(x)$. ∎

###### Lemma 4.

For $n=p_{1}^{\alpha_{1}}\cdots p_{r}^{\alpha_{r}}$, where $p_{i}$ are prime and $\alpha_{i}\geq 1$, and $N=p_{1}\cdots p_{r}$,

 $\Phi_{n}(x)=\Phi_{N}(x^{n/N}).$
###### Proof.

If $d|n$ and $d\nmid N$ then $\mu(d)=0$, hence

 $\displaystyle\Phi_{n}(x)$ $\displaystyle=\prod_{d\mid n}(x^{n/d}-1)^{\mu(d)}$ $\displaystyle=\prod_{d\mid N}(x^{n/d}-1)^{\mu(d)}$ $\displaystyle=\prod_{d\mid N}((x^{n/N})^{N/d}-1)^{\mu(d)}$ $\displaystyle=\Phi_{N}(x^{n/N}).$

###### Lemma 5.

If $n>1$ then

 $\Phi_{n}(x^{-1})=x^{-\phi(n)}\Phi_{n}(x).$
###### Proof.
 $\Phi_{n}(x^{-1})=\prod_{d\mid n}(x^{-d}-1)^{\mu(n/d)}=\prod_{d\mid n}(1-x^{d})% ^{\mu(n/d)}(x^{-d})^{\mu(n/d)},$

hence

 $\Phi_{n}(x^{-1})=\prod_{d\mid n}(-x^{-d})^{\mu(n/d)}\cdot\prod_{d\mid n}(x^{d}% -1)^{\mu(n/d)}.$

Because $n>1$ it holds that $\sum_{d\mid n}\mu(n/d)=0$, and using this and $\sum_{d\mid n}d\cdot\mu(n/d)=\phi(n)$ yields

 $\Phi_{n}(x^{-1})=x^{-\phi(n)}\Phi_{n}(x).$

###### Lemma 6.

If $r>1$ is odd then

 $\Phi_{2r}(x)=\Phi_{r}(-x).$
###### Proof.

Because $r$ is odd, if $d_{1},\ldots,d_{l}$ are the divisors of $r$ then

 $d_{1},\ldots,d_{l},2d_{1},\ldots,2d_{l}$

are the divisors of $2r$, so

 $\displaystyle\Phi_{2r}(x)$ $\displaystyle=\prod_{d\mid(2r)}(x^{d}-1)^{\mu(2r/d)}$ $\displaystyle=\prod_{d\mid r}(x^{d}-1)^{\mu(2r/d)}\cdot\prod_{d|r}(x^{2d}-1)^{% \mu(2r/(2d))}$ $\displaystyle=\prod_{d\mid r}(x^{d}-1)^{\mu(2r/d)}(x^{2d}-1)^{\mu(r/d)}$ $\displaystyle=\prod_{d\mid r}(x^{d}-1)^{\mu(2)\mu(r/d)+\mu(r/d)}(x^{d}+1)^{\mu% (r/d)}$ $\displaystyle=\prod_{d\mid r}(x^{d}+1)^{\mu(r/d)}.$

Because $r$ is odd, any divisor $d$ of $r$ is odd and then $x^{d}+1=-((-x)^{d}-1)$, so

 $\Phi_{2r}(x)=\prod_{d\mid r}(-1)^{\mu(r/d)}((-x)^{d}-1)^{\mu(r/d)}=(-1)^{\phi(% r)}\cdot\prod_{d\mid r}((-x)^{d}-1)^{\mu(r/d)}.$

Because $r$ is odd and $>1$, $\phi(r)$ is even, so we have obtained the claim. ∎

###### Theorem 7.

$\Phi_{n}\in\mathbb{Z}[x]$.

###### Proof.

It is a fact that if $R$ is a unital commutative ring, $f\in R[x]$ is a monic polynomial and $g\in R[x]$ is a polynomial, then there are $q,r\in R[x]$ with

 $g=qf+r,$

$r=0$ or $\deg r<\deg f$.

First, $\Phi_{1}(x)=x-1\in\mathbb{Z}[x]$. For $n>1$, assume that $\Phi_{d}(x)\in\mathbb{Z}[x]$ for $1\leq d. Then let

 $f=\prod_{d\mid n,d

which by hypothesis belongs to $\mathbb{Z}[x]$. Since each $\Phi_{d}$ is monic, so is $f$. On the one hand, since $g(x)=x^{n}-1\in\mathbb{Z}[x]$, there are $q,r\in\mathbb{Z}[x]$ with $g=qf+r$ and $r=0$ or $\deg r<\deg f$. On the other hand, by Lemma 1 we have $g=\Phi_{n}f\in\mathbb{C}[x]$. Thus $\Phi_{n}f=qf+r\in\mathbb{C}[x]$, so $r=f\cdot(\Phi_{n}-q)\in\mathbb{C}[x]$. If $\Phi_{n}\neq q$ then $\deg r=\deg f+\deg(\Phi_{n}-q)\geq\deg f$, contradicting that $r=0$ or $\deg r<\deg f$. Therefore $\Phi_{n}=q\in\mathbb{C}[x]$, and because $q\in\mathbb{Z}[x]$ this means that $\Phi_{n}\in\mathbb{Z}[x]$. ∎

In fact, it can be proved that $\Phi_{n}$ is irreducible in $\mathbb{Q}[x]$. Gauss states in entry 40 of his mathematical diary, dated October 9, 1796, that $\Phi_{p}$ is irreducible in $\mathbb{Q}[x]$ when $p$ is prime, and he proves this in Disqisitiones Arithmeticae, Art. 341. Gauss further states in entry 136 of his mathematical diary, dated June 12, 1808, that for any $n$, $\Phi_{n}$ is irreducible in $\mathbb{Q}[x]$, and Kronecker proves this in his 1854 Mémoire sur les facteurs irréductibles de l’expression $x^{n}-1$. Gauss’s work on cyclotomic polynomials is surveyed by Neumann [40]. For any $\xi\in\Delta_{n}$, $\Phi_{n}(\xi)=0$, and since $\Phi_{n}$ is irreducible in $\mathbb{Q}[x]$ and is monic, $\Phi$ is the minimal polynomial of $\xi$ over $\mathbb{Q}$, which implies that $[\mathbb{Q}(\xi):\mathbb{Q}]=\deg\Phi_{n}=\phi(n)$.

There is a group isomorphism $\mathrm{Gal}(\mathbb{Q}(\xi)/\mathbb{Q})\to(\mathbb{Z}/n)^{*}$ [16, p. 596, Theorem 26].

The discriminant [44, p. 12, Proposition 2.7]:

 $d(\mathbb{Q}(e^{2\pi i/n}))=\frac{(-1)^{\phi(n)/2}n^{\phi(n)}}{\prod_{p\mid n}% p^{\phi(n)/(p-1)}}.$

It can be proved that $\mathcal{O}_{\mathbb{Q}(e^{2\pi i/n})}=\mathbb{Z}[e^{2\pi i/n}]$ [39, p. 60, Proposition 10.2].

Let $p$ be prime, let $q=p^{r}$ for $r\geq 1$, let $\mathbb{F}_{q}$ be a finite field with $q$ elements, and for $n\geq 1$ with $\gcd(n,q)=1$, let $\nu$ be the multiplicative order of $q$ modulo $n$: $\nu$ is the minimum positive integer satisfying $q^{\nu}\equiv 1\pmod{n}$. It can be proved that there are monic, degree $\nu$, irreducible polynomials $P_{1},\ldots,P_{\phi(n)/\nu}\in\mathbb{F}_{q}[x]$ such that $\Phi_{n}=P_{1}\cdots P_{\phi(n)/\nu}\in\mathbb{F}_{q}[x]$ [28, p. 65, Theorem 2.47]; cf. Bourbaki [7, p. 581] on Kummer. In particular, $q$ is a generator of the multiplicative group $(\mathbb{Z}/n)^{*}$ if and only if $\nu=\phi(n)$ if and only if $\Phi_{n}$ is irreducible in $\mathbb{F}_{q}[x]$. We remark that $(\mathbb{Z}/n)^{*}$ is cyclic if and only if $n$ is $2$, $4$, some power of an odd prime, or twice some power of an odd prime (Gauss, Disquisitiones Arithmeticae, Art. 89–92). This follows from (i) the multiplicative group $(\mathbb{Z}/n)^{*}$ is isomorphic with the direct product $(\mathbb{Z}/p_{1}^{\alpha_{1}})^{*}\times\cdots\times(\mathbb{Z}/p_{r}^{\alpha% _{r}})^{*}$ for $n=p_{1}^{\alpha_{1}}\cdots p_{r}^{\alpha_{r}}$, (ii) $(\mathbb{Z}/2^{\alpha})^{*}$ is isomorphic with $\mathbb{Z}/2\times\mathbb{Z}/2^{\alpha-2}$, $\alpha\geq 2$, and (iii) $(\mathbb{Z}/p^{\alpha})^{*}$ is a cyclic group with $p^{\alpha-1}(p-1)$ elements when $p$ is an odd prime, $\alpha\geq 1$ [16, p. 314, Corollary 20].

## 3 Special values

###### Lemma 8.

$\Phi_{1}(0)=-1$, and for $n\geq 2$, $\Phi_{n}(0)=1$.

###### Proof.

$\Phi_{1}(x)=x-1$, so $\Phi_{1}(0)=-1$. For $n\geq 2$, using (1),

 $\Phi_{n}(0)=\prod_{d\mid n}(-1)^{\mu(n/d)}=(-1)^{\sum_{d\mid n}\mu(n/d)}=(-1)^% {\sum_{d\mid n}\mu(d)}=(-1)^{0}=1.$

Let $\Lambda$ be the von Mangoldt function: $\Lambda(n)=\log p$ if $n=p^{\alpha}$ for some prime $p$ and some integer $\alpha\geq 1$, and is $\Lambda(n)=0$ otherwise. Thus $\Lambda(2)=\log 2$, $\Lambda(8)=\log 2$, $\Lambda(3)=\log 3$, and $\Lambda(6)=0$. One sees that

 $\log n=\sum_{d\mid n}\Lambda(d).$

Therefore by the Möbius inversion formula,

 $\Lambda(n)=\sum_{d\mid n}\mu(n/d)\log d.$
###### Theorem 9.

For $n>1$,

 $\Phi_{n}(1)=e^{\Lambda(n)}$

and

 $\Phi_{n}^{\prime}(1)=\frac{1}{2}e^{\Lambda(n)}\phi(n).$
###### Proof.

For $n>1$,

 $x^{n-1}+\cdots+x+1=\prod_{d\mid n,d>1}\Phi_{d}(x),$

hence

 $\log n=\sum_{d\mid n,d>1}\log\Phi_{d}(1).$

Therefore by the Möbius inversion formula,

 $\log\Phi_{n}(1)=\sum_{d\mid n,d>1}\mu(n/d)\log d=\sum_{d\mid n}\mu(n/d)\log d=% \Lambda(n).$

Because $x^{n}-1=\prod_{d\mid n}\Phi_{d}(x)$, taking the logarithm and then taking the derivative yields

 $\frac{nx^{n-1}}{x^{n}-1}=\sum_{d\mid n}\frac{\Phi_{d}^{\prime}(x)}{\Phi_{d}(x)}.$

$\Phi_{1}(x)=x-1$ and so $\frac{\Phi_{1}^{\prime}(x)}{\Phi_{1}(x)}=\frac{1}{x-1}$, hence

 $\frac{nx^{n-1}}{x^{n}-1}-\frac{1}{x-1}=\sum_{d\mid n,d>1}\frac{\Phi_{d}^{% \prime}(x)}{\Phi_{d}(x)},$

i.e.

 $\frac{nx^{n-1}-(x^{n-1}+x^{n-2}+\cdots+x+1)}{x^{n}-1}=\sum_{d\mid n,d>1}\frac{% \Phi_{d}^{\prime}(x)}{\Phi_{d}(x)}.$

Doing polynomial long division we find

 $\frac{(n-1)x^{n-1}-x^{n-2}-\cdots-x-1}{x-1}=(n-1)x^{n-2}+(n-2)x^{n-3}+\cdots+2% x+1.$

Hence

 $\frac{(n-1)x^{n-2}+(n-2)x^{n-3}+\cdots+2x+1}{x^{n-1}+x^{n-2}+\cdots+x+1}=\sum_% {d\mid n,d>1}\frac{\Phi_{d}^{\prime}(x)}{\Phi_{d}(x)},$

and for $x=1$ this is

 $\frac{n-1}{2}=\sum_{d\mid n,d>1}\frac{\Phi_{d}^{\prime}(1)}{\Phi_{d}(1)}.$

By the Möbius inversion formula,

 $\frac{\Phi_{n}^{\prime}(1)}{\Phi_{n}(1)}=\sum_{d\mid n,d>1}\mu(n/d)\cdot\frac{% d-1}{2},$

and using (i) $\Phi_{n}(1)=e^{\Lambda(n)}$ for $n>1$, (ii) $\sum_{d\mid n}\mu(n/d)=0$ for $n>1$, and (iii) $\sum_{d\mid n}d\cdot\mu(n/d)=\phi(n)$, we have

 $\Phi_{n}^{\prime}(1)=e^{\Lambda(n)}\frac{1}{2}\sum_{d\mid n}\mu(n/d)\cdot d-e^% {\Lambda(n)}\frac{1}{2}\sum_{d\mid n}\mu(n/d)=\frac{1}{2}e^{\Lambda(n)}\phi(n).$

Because $\Phi_{n}\in\mathbb{Z}[x]$, it is the case that $\Phi_{n}(-i)=\overline{\Phi_{n}(i)}$.

###### Theorem 10.

$\Phi_{1}(i)=i-1$, $\Phi_{2}(i)=i+1$, $\Phi_{4}(i)=0$, and otherwise we have the following.

• If $n$ is odd and has a prime factor $p\equiv 1\pmod{4}$, then $\Phi_{n}(i)=1$.

• If $p\equiv 3\pmod{4}$ is prime and $k\geq 1$ is odd, then $\Phi_{p^{k}}(i)=i$.

• If $p\equiv 3\pmod{4}$ is prime and $k\geq 1$ is even, then $\Phi_{p^{k}}(i)=-i$.

• If $p\equiv 3\pmod{4}$ is prime and $k\geq 1$ is odd, then $\Phi_{2p^{k}}(i)=-i$.

• If $p\equiv 3\pmod{4}$ is prime and $k\geq 1$ is even, then $\Phi_{2p^{k}}(i)=i$.

• If $p,q\equiv 3\pmod{4}$ are distinct primes and $k,l\geq 1$, then $\Phi_{p^{k}q^{l}}(i)=-1$.

• If $p,q\equiv 3\pmod{4}$ are distinct primes and $k,l\geq 1$, then $\Phi_{2p^{k}q^{l}}(i)=-1$.

• If $p$ is an odd prime and $k\geq 1$, then $\Phi_{4p^{k}}(i)=p$.

• If $\omega(n)\geq 3$ then $\Phi_{n}(i)=1$.

###### Proof.

$\Phi_{1}(x)=x-1$, $\Phi_{2}(x)=x+1$, so $\Phi_{1}(i)=i-1$ and $\Phi_{2}(i)=i+1$. As $i\in\Delta_{4}$, $\Phi_{4}(i)=0$.

Suppose that $n$ is odd, that $p\equiv 1\pmod{4}$ is a prime factor of $n$, and write $n=p^{k}m$ with $\gcd(m,p)=1$. Lemma 3 tells us

 $\Phi_{n}(x)=\Phi_{p^{k}m}(x)=\frac{\Phi_{m}(x^{p^{k}})}{\Phi_{m}(x^{p^{k-1}})},$

and as $p^{k-1}\equiv 1\pmod{4}$ and $i^{4}=1$, this yields

 $\Phi_{n}(i)=\frac{\Phi_{m}(i)}{\Phi_{m}(i)}=1.$

Suppose that $n$ is odd, that $p\equiv 3\pmod{4}$ is a prime factor of $n$, and write $n=p^{k}m$ with $\gcd(m,p)=1$. If $k$ is odd then $p^{k}\equiv 3\pmod{4}$, so

 $\Phi_{n}(i)=\frac{\Phi_{m}(i^{p^{k}})}{\Phi_{m}(i^{p^{k-1}})}=\frac{\Phi_{m}(i% ^{3})}{\Phi_{m}(i)}=\frac{\Phi_{m}(-i)}{\Phi_{m}(i)},$

and if $m=1$ then

 $\Phi_{n}(i)=\frac{\Phi_{1}(-i)}{\Phi_{1}(i)}=\frac{-i-1}{i-1}=i.$

If $k$ is even then $p^{k}\equiv 1\pmod{4}$, so

 $\Phi_{n}(i)=\frac{\Phi_{m}(i)}{\Phi_{m}(-i)},$

and if $m=1$ then $\Phi_{n}(i)=-i$.

Suppose that $n=2^{k}$, $k\geq 3$. Lemma 4 tells us that

 $\Phi_{n}(x)=\Phi_{2}(x^{n/2})=\Phi_{2}(x^{2^{k-1}})=x^{2^{k-1}}+1,$

thus

 $\Phi_{n}(i)=i^{2^{k-1}}+1=1+1=2.$

Suppose that $n=2m$ with $m>1$ odd. Lemma 6 tells us $\Phi_{n}(x)=\Phi_{2m}(x)=\Phi_{m}(-x)$, so $\Phi_{n}(i)=\Phi_{m}(-i)$.

Suppose that $n=2^{k}m$ with $k\geq 2$ and $m>1$ odd. Lemma 3 tells us

 $\Phi_{2^{k}m}(x)=\Phi_{2^{k-1}\cdot 2m}(x)=\Phi_{2m}(x^{2^{k-1}}),$

and then Lemma 6 tells us $\Phi_{2m}(x^{2^{k-1}})=\Phi_{m}(-x^{2^{k-1}})$. For $k=2$ this yields

 $\Phi_{4m}(i)=\Phi_{m}(1),$

and for $k>2$,

 $\Phi_{n}(i)=\Phi_{m}(-i^{2^{k-1}})=\Phi_{m}(-1).$

Kurshan and Odlyzko [25]

Montgomery and Vaughan [36, pp. 131–132, Exercise 9].

###### Theorem 11.

If $n=\prod_{p\leq y,p\equiv 2,3\pmod{5}}p$ with $\omega(n)$ odd, then

 $|\Phi_{n}(e^{2\pi i/5})|=\left(\frac{1+\sqrt{5}}{2}\right)^{d(n)/2}.$
###### Proof.

Write $e(x)=e^{2\pi ix}$, let $d\mid n$, $d>1$, and write $d=p_{1}\cdots p_{k}\cdot q_{1}\cdots q_{l}$ where $p_{1},\ldots,p_{k}\equiv 2\pmod{5}$ and $q_{1},\ldots,q_{l}\equiv 3\pmod{5}$ are prime. Then $\omega(d)=k+l$ and, as $2^{3}\equiv 3\pmod{5}$,

 $d\equiv 2^{k}3^{l}\equiv 2^{k}2^{3l}\equiv 2^{k+l}(-1)^{l}\pmod{5}.$

If $\omega(d)\equiv 0\pmod{4}$ then $2^{k+l}\equiv 1\pmod{5}$ and if $\omega(d)\equiv 2\pmod{4}$ then $2^{k+l}\equiv-1\pmod{5}$, and therefore if $\omega(d)$ is even then $d\equiv 1\pmod{5}$ or $d\equiv-1\pmod{5}$. Since $|e(-1/5)-1|=|e(1/5)-1|$, we have $|e(d/5)-1|=|e(1/5)-1|$.

If $\omega(d)\equiv 1\pmod{4}$ then $2^{k+l}\equiv 2\pmod{5}$ and if $\omega(d)\equiv 3\pmod{4}$ then $2^{k+l}\equiv-2\pmod{5}$, and therefore if $\omega(d)$ is odd then $d\equiv 2\pmod{5}$ or $d\equiv-2\pmod{5}$. Since $|e(-2/5)-1|=|e(2/5)-1|$, we have $|e(d/5)-1|=|e(2/5)-1|$.

Now using Lemma 1 and $|e(1/5)-1|^{-1}=|e(2/5)-1|$,

 $\displaystyle|\Phi_{n}(e(1/5))|$ $\displaystyle=\prod_{d\mid n}|e(d/5)-1|^{\mu(n/d)}$ $\displaystyle=\prod_{d\mid n,\textrm{\omega(d) even}}|e(1/5)-1|^{-1}\cdot% \prod_{d\mid n,\textrm{\omega(d) odd}}|e(2/5)-1|.$

Hence, for $\omega(n)=2\nu+1$ and for $A=|e(1/5)-1|^{-1}$ and $B=|e(2/5)-1|$,

 $\displaystyle\log|\Phi_{n}(e(1/5))|$ $\displaystyle=\sum_{r=0}^{\nu}\binom{2\nu+1}{2r}\log A+\sum_{r=0}^{\nu}\binom{% 2\nu+1}{2r+1}\log B$ $\displaystyle=2^{2\nu}\log A+2^{2\nu}\log B$ $\displaystyle=\log((AB)^{2^{\omega(n)}/2}),$

and using $d(n)=\sum_{r=0}^{\omega(n)}\binom{\omega(n)}{r}=2^{\omega(n)}$ this is $|\Phi_{n}(e(1/5))|=(AB)^{d(n)/2}$. Finally,

 $AB=\frac{|e(2/5)-1|}{|e(1/5)-1|}=|e(1/5)+1|=\frac{1+\sqrt{5}}{2}.$

## 4 Primes in arithmetic progressions

For prime $p$, $p\nmid n$, the following theorem relates the order of an element of the multiplicative group $(\mathbb{Z}/p)^{*}$ with $\Phi_{n}$ [44, p. 13, Lemma 2.9]. We remind ourselves that $\Phi_{n}\in\mathbb{Z}[x]$ (Theorem 7), and so $\Phi_{n}(a)\in\mathbb{Z}$ for $a\in\mathbb{Z}$.

###### Lemma 12.

Let $p$ be prime, $p\nmid n$, and $a\in\mathbb{Z}$. Then $p\mid\Phi_{n}(a)$ if and only if $n$ is the multiplicative order of $a$ modulo $p$.

###### Proof.

Suppose that $p\mid\Phi_{n}(a)$. Now, let $b\in\mathbb{Z}$ with $p\mid\Phi_{n}(b)$. By Lemma 1, $b^{n}-1=\prod_{d\mid n}\Phi_{d}(b)$, and because $\Phi_{n}(b)\equiv 0\pmod{p}$ this yields $b^{n}-1\equiv 0\pmod{p}$, i.e. $b^{n}\equiv 1\pmod{p}$; in particular, $p\nmid b$. Let $\nu=\min\{k>0:a^{k}\equiv 1\pmod{p}\}$, the multiplicative order of $a$ modulo $p$, so $\nu\mid n$, and suppose by contradiction that $\nu. Using $x^{\nu}-1=\prod_{d\mid\nu}\Phi_{d}(x)$ we have $b^{\nu}-1=\prod_{d\mid\nu}\Phi_{d}(b)$. Using this with $b=a$, as $a^{\nu}\equiv 1\pmod{p}$ and because $p$ is prime it follows that for some $d_{0}\leq\nu, $\Phi_{d_{0}}(a)\equiv 0\pmod{p}$. As $\nu\mid n$,

 $b^{n}-1=\Phi_{n}(b)\Phi_{d_{0}}(b)\cdot\prod_{d\mid n,d\neq d_{0},n}\Phi_{d}(b).$

Applying the above with $b=a$ yields $a^{n}-1\equiv 0\pmod{p^{2}}$. Moreover, by the binomial theorem, $\Phi_{n}(a+p)\equiv\Phi_{n}(a)\equiv 0\pmod{p}$ and $\Phi_{d_{0}}(a+p)\equiv\Phi_{d_{0}}(a)\equiv 0\pmod{p}$, so applying the above with $b=a+p$ yields $(a+p)^{n}-1\equiv 0\pmod{p^{2}}$. But by the binomial theorem, $(a+p)^{n}-1=\sum_{j=0}^{n}\binom{n}{j}a^{n-j}p^{j}-1$, whence $(a+p)^{n}-1\equiv a^{n}+na^{n-1}p-1\pmod{p^{2}}$, hence $a^{n}+na^{n-1}p-1\equiv 0\pmod{p^{2}}$. Together with $a^{n}-1\equiv 0\pmod{p^{2}}$ this yields $na^{n-1}p\equiv 0\pmod{p^{2}}$, i.e. $na^{n-1}\equiv 0\pmod{p}$, contradicting that $p\nmid n,a$. Therefore $\nu=n$.

Suppose that $a^{n}\equiv 1\pmod{p}$ and that $a^{\nu}\not\equiv 1\pmod{p}$ for $0<\nu. As $\prod_{d\mid n}\Phi_{d}(a)=a^{n}-1\equiv 0\pmod{p}$, there is some $d_{0}\mid n$ for which $\Phi_{d_{0}}(a)\equiv 0\pmod{p}$. Suppose by contradiction that $d_{0}. As $d_{0}\mid n$,

 $a^{d_{0}}-1=\prod_{d\mid d_{0}}\Phi_{d}(a)=\Phi_{d_{0}}(a)\cdot\prod_{d\mid d_% {0},d

contradicting that $a^{\nu}\not\equiv 1\pmod{p}$ for $0<\nu. Therefore $\Phi_{n}(a)\equiv 0\pmod{p}$, i.e. $p\mid\Phi_{n}(a)$. ∎

###### Lemma 13.

Let $p$ be prime, $p\nmid n$. There is some $a\in\mathbb{Z}$ such that $p\mid\Phi_{n}(a)$ if and only if $p\equiv 1\pmod{n}$.

###### Proof.

Suppose that $a\in\mathbb{Z}$ and $p\mid\Phi_{n}(a)$. Then by Lemma 12, $n$ is the multiplicative order of $a$ modulo $p$. As the multiplicative group $(\mathbb{Z}/p)^{*}$ has $p-1$ elements, this implies that $n\mid(p-1)$, i.e. $p-1\equiv 0\pmod{n}$.

Suppose that $p\equiv 1\pmod{n}$, i.e. $n\mid(p-1)$. Because $(\mathbb{Z}/p)^{*}$ is a cyclic group with $p-1$ elements, it is a fact that there is some $a\in\mathbb{Z}$, $a+p\mathbb{Z}\in(\mathbb{Z}/p)^{*}$, whose multiplicative order modulo $p$ is $n$. (Generally, if $G$ is a cyclic group with $m$ elements and $n$ divides $m$ then there is some $g\in G$ with order $n$.) Then by Lemma 12, $p\mid\Phi_{n}(a)$. ∎

We now use Lemma 13 to prove an instance of Dirichlet’s theorem on primes in arithmetic progressions [44, p. 13, Lemma 2.9].

###### Theorem 14.

For any $n\geq 1$, there are infinitely many primes $p$ with $p\equiv 1\pmod{n}$.

###### Proof.

The claim for $n=1$ follows from the claim for $n=2$. For $n\geq 2$, by Lemma 8, $\Phi_{n}(0)=1$, namely the constant coefficient of $\Phi_{n}(x)$ is $1$. Suppose by contradiction that there are at most finitely many such primes $p_{1},\ldots,p_{t}$ and let $M=np_{1}\cdots p_{t}$. For $N\in\mathbb{Z}$, $\Phi_{n}(NM)\equiv 1\pmod{M}$ and from $M\mid(\Phi_{n}(NM)-1)$ it follows that $p_{i}\mid(\Phi_{n}(NM)-1)$, $1\leq i\leq t$, and $n\mid(\Phi_{n}(NM)-1)$. Hence if $p$ is a prime factor of $\Phi_{n}(NM)$ then $p\neq p_{i}$, $1\leq i\leq t$, and $p\nmid n$. As $\Phi_{n}$ is a monic polynomial that is not a constant, for all sufficiently large $N$, $\Phi_{n}(NM)$ is an integer $\geq 2$ and thus has a prime factor $p$, amd we have established that $p\nmid n$. Therefore Lemma 13 tells us that $p\equiv 1\pmod{n}$. But we have also established that $p\neq p_{i}$, $1\leq i\leq r$, a contradiction. Therefore there are infinitely many primes $p$ with $p\equiv 1\pmod{n}$. ∎

One can prove that for any integers $n,b\geq 2$ it holds that

 $\frac{1}{2}\cdot b^{\phi(n)}\leq\Phi_{n}(b)\leq 2\cdot b^{\phi(n)}.$

Using this, Thangadurai and Vatwani [42] prove that for $n\geq 2$, the least prime $p\equiv 1\pmod{n}$ satisfies

 $p\leq 2^{\phi(n)+1}-1.$

## 5 Zsigmondy’s theorem

[20, pp. 167–169, §8.3.1]

## 6 Newton’s identities and Ramanujan sums

For positive integers $n$ and $n$, let

 $c_{n}(k)=\sum_{1\leq j\leq n,\gcd(n,j)=1}e^{2\pi ijk/n}=\sum_{\xi\in\Delta_{n}% }\xi^{k},$

called a Ramanujan sum.

###### Lemma 15.
 $c_{n}(k)=\sum_{d\mid\gcd(n,k)}d\cdot\mu(n/d).$
###### Proof.

Let

 $\eta_{n}(k)=\sum_{j=1}^{n}e^{2\pi ijk/n}=\begin{cases}0&n\nmid k\\ m&n\mid k.\end{cases}$

We can write $\eta_{n}(k)$ as

 $\eta_{n}(k)=\sum_{d\mid n}c_{d}(k),$

so by the Möbius inversion formula,

 $c_{n}(k)=\sum_{d\mid n}\mu(n/d)\eta_{d}(k).$

###### Theorem 16.

For $n>1$ and for $|x|<1$,

 $\Phi_{n}(x)=\exp\left(-\sum_{m=1}^{\infty}\frac{c_{n}(m)}{m}x^{m}\right).$
###### Proof.

Using that $\xi\mapsto\xi^{-1}$ is a bijection $\Delta_{n}\to\Delta_{n}$,

 $\displaystyle\frac{d}{dx}\log\Phi_{n}(x)$ $\displaystyle=\frac{d}{dx}\sum_{\xi\in\Delta_{n}}\log(x-\xi)$ $\displaystyle=\sum_{\xi\in\Delta_{n}}\frac{1}{x-\xi}$ $\displaystyle=\sum_{\xi\in\Delta_{n}}-\frac{1}{\xi}\cdot\frac{1}{1-\frac{x}{% \xi}}$ $\displaystyle=-\sum_{\xi\in\Delta_{n}}\frac{1}{\xi}\sum_{m=0}^{\infty}\left(% \frac{x}{\xi}\right)^{m}$ $\displaystyle=-\sum_{m=0}^{\infty}x^{m}\sum_{\xi\in\Delta_{n}}\xi^{m+1}.$

Because $n>1$, $\Phi_{n}(0)=1$, and integrating,

 $\Phi_{n}(x)=\exp\left(-\sum_{m=0}^{\infty}\frac{x^{m+1}}{m+1}\sum_{\xi\in% \Delta_{n}}\xi^{m+1}\right)=\exp\left(-\sum_{m=1}^{\infty}\frac{x^{m}}{m}c_{n}% (m)\right).$

A formula due to Hölder [36, p. 110, Theorem 4.1] is that

 $c_{n}(k)=\frac{\mu(n/\gcd(n,k))\cdot\phi(n)}{\phi(n/\gcd(n,k))}.$ (2)

This identity is used to prove the following lemma that we use later.

###### Lemma 17.

If $n$ is square-free then $k\mapsto\mu(n)c_{n}(k)$ is multiplicative.

###### Lemma 18.

For $n\geq 1$ and $\mathrm{Re}\,s>1$,

 $\sum_{k=1}^{\infty}c_{n}(k)k^{-s}=\zeta(s)\cdot\sum_{d\mid n}\mu(n/d)d^{1-s}.$
###### Proof.

By Lemma 15,

 $\displaystyle\sum_{k=1}^{\infty}c_{n}(k)k^{-s}$ $\displaystyle=\sum_{k=1}^{\infty}k^{-s}\sum_{d\mid n,d\mid k}\mu(n/d)d$ $\displaystyle=\sum_{d\mid n}\sum_{m=1}^{\infty}(md)^{-s}\mu(n/d)d$ $\displaystyle=\sum_{d\mid n}\sum_{m=1}^{\infty}m^{-s}d^{-s}\mu(n/d)d$ $\displaystyle=\sum_{m=1}^{\infty}m^{-s}\sum_{d\mid n}d^{-s}\mu(n/d)d$ $\displaystyle=\zeta(s)\cdot\sum_{d\mid n}\mu(n/d)d^{1-s}.$

Write

 $\prod_{j=1}^{n}(x-\alpha_{j})=\sum_{k=0}^{n}(-1)^{k}s_{k}x^{n-k},$

and put, for $k\geq 1$,

 $p_{k}=\sum_{j=1}^{n}\alpha_{j}^{k}.$

Newton’s identities [19, p. 32, Proposition 3.4] state that for $k\geq 1$,

 $p_{k}=\sum_{j=1}^{k-1}(-1)^{j-1}s_{j}p_{k-j}+(-1)^{k-1}ks_{k}.$ (3)

Write

 $\Phi_{n}(x)=\sum_{k=0}^{\phi(n)}a_{n}(k)x^{k}.$

Let $n>1$, and for integer $j$ define

 $\chi_{1}(j)=\begin{cases}1&\gcd(n,j)=1\\ 0&\gcd(n,j)>1,\end{cases}$

namely the principal Dirichlet character modulo $n$. We can then write

 $\Phi_{n}(x)=\prod_{1\leq k\leq n,\gcd(n,k)=1}(x-e^{2\pi ik/n})=x^{-n+\phi(n)}% \prod_{j=1}^{n}(x-\alpha_{j})$

for $\alpha_{j}=\chi_{1}(j)e^{2\pi ij/n}$, and thus

 $x^{n-\phi(n)}\Phi_{n}(x)=\prod_{j=1}^{n}(x-\alpha_{j}).$

Because $\chi_{1}(j)^{k}=\chi_{1}(j)$ for $k\geq 1$,

 $p_{k}=\sum_{j=1}^{n}\alpha_{j}^{k}=\sum_{j=1}^{n}\chi_{1}(j)e^{2\pi ijk/n}=% \sum_{1\leq j\leq n,\gcd(n,j)=1}e^{2\pi ijk/n}=c_{n}(k).$

Now, from

 $x^{n-\phi(n)}\sum_{k=1}^{\phi(n)}a_{n}(k)x^{k}=\sum_{k=0}^{n}(-1)^{k}s_{k}x^{n% -k}$

we have, for $0\leq k\leq n$,

 $(-1)^{k}s_{k}=a_{n}(\phi(n)-k).$

In fact by Lemma 20, $a_{n}(\phi(n)-k)=a_{n}(k)$, so $a_{n}(k)=(-1)^{k}s_{k}$. Thus (3) yields the following, and in particular

 $a_{n}(1)=-c_{n}(1)=-\mu(n).$
###### Theorem 19.

For $n\geq 1$ and $k\geq 1$,

 $ka_{n}(k)=-c_{n}(k)-\sum_{j=1}^{k-1}a_{n}(j)c_{n}(k-j).$

Let $n$ be a product of distinct odd primes and for $a\in\mathbb{Z}$ let $\chi(a)=\left(\frac{a}{n}\right)$ be the Jacobi symbol. Dedekind, in Supplement I to Dirichlet’s Vorlesungen über Zahlentheorie [15, pp. 208–210], §116, proves that

 $\sum_{1\leq j\leq n}\chi(j)e^{2\pi ijh/n}=\chi(h)i^{(n-1)^{2}/4}\sqrt{n};$ (4)

this is proved earlier by Gauss in his Summatio quarumdam serierum singularium [22, pp. 9–45], dated 1808. The expression $G(h,\chi)=\sum_{1\leq j\leq n}\chi(j)e^{2\pi ijh/n}$ is called a Gauss sum. Dedekind, in Supplement VII to Dirichlet’s Vorlesungen, says what amounts to the following. Define

 $A_{n}(x)=\prod_{1\leq a\leq n,\chi(a)=1}(x-e^{2\pi ia/n})=\sum_{j}\alpha_{n}(j% )x^{j}$

and

 $B_{n}(x)=\prod_{1\leq b\leq n,\chi(b)=-1}(x-e^{2\pi ib/n})=\sum_{j}\beta_{n}(j% )x^{j},$

and write

 $S_{n}(k)=\sum_{1\leq a\leq n,\chi(a)=1}e^{2\pi ika/n},\qquad T_{n}(k)=\sum_{1% \leq b\leq n,\chi(b)=-1}e^{2\pi ikb/n}.$

Then

 $\Phi_{n}(x)=A_{n}(x)B_{n}(x),\qquad c_{n}(k)=S_{n}(k)+T_{n}(k),$

and by (4), writing

 $n^{*}=(-1)^{(n-1)/2}n,$

we have

 $S_{n}(k)-T_{n}(k)=\sum_{1\leq j\leq n}\chi(j)e^{2\pi ikj/n}=\chi(k)\sqrt{n^{*}},$

hence

 $2S_{n}(k)=c_{n}(k)+\chi(k)\sqrt{n^{*}},\quad 2T_{n}(k)=c_{n}(k)-\chi(k)\sqrt{n% ^{*}}.$

We have established in Lemma 15 that $c_{n}(k)\in\mathbb{Z}$, so this shows that $S_{n}(k),T_{n}(k)\in\mathbb{Q}(\sqrt{n^{*}})$. Newton’s identities yield for $k\geq 1$,

 $S_{n}(k)=-\sum_{j=1}^{k-1}\alpha_{n}(n-j)S_{n}(k-j)-k\alpha_{n}(n-k)$

and

 $T_{n}(k)=-\sum_{j=1}^{k-1}\beta_{n}(n-j)T_{n}(k-j)-k\beta_{n}(n-k),$

and it follows that $\alpha_{n}(k),\beta_{n}(k)\in\mathbb{Q}(\sqrt{n^{*}})$. Furthermore, $\alpha_{n}(k),\beta_{n}(k)$ are algebraic integers, so $\alpha_{n}(k),\beta_{n}(k)\in\mathcal{O}_{\mathbb{Q}(\sqrt{n^{*}})}$. If $D$ is a square-free, it is a fact [16, p. 698, §15.3] that $\mathcal{O}_{\mathbb{Q}(\sqrt{D})}=\mathbb{Z}[\omega]$ for

 $\omega=\begin{cases}\sqrt{D}&D\equiv 2,3\pmod{4}\\ \frac{1+\sqrt{D}}{2}&D\equiv 1\pmod{4},\end{cases}$

and $n^{*}=(-1)^{(n-1)/2}n\equiv 1\pmod{4}$, we have $\mathcal{O}_{\mathbb{Q}(\sqrt{n^{*}})}=\mathbb{Z}[(1+\sqrt{n^{*}})/2]$. Thus $\alpha_{n}(k),\beta_{n}(k)\in\mathbb{Z}[(1+\sqrt{n^{*}})/2]$.

It is a fact that $\mathbb{Q}(\sqrt{n^{*}})\subset\mathbb{Q}(e^{2\pi i/n})$ [23, p. 19, Proposition 5.13]

Gauss, Disquisitiones Arithmeticae, Art. 357

## 7 Algebraic theorems about coefficients of cyclotomic polynomials

For $n\geq 1$, we write

 $\Phi_{n}(x)=\sum_{k=0}^{\phi(n)}a_{n}(k)x^{k}.$

Let

 $A(n)=\max_{0\leq k\leq\phi(n)}|a_{n}(k)|$

and

 $S(n)=\sum_{k=0}^{\phi(n)}|a_{n}(k)|.$

It is immediate that $A(n)\leq S(n)$.

###### Lemma 20.

For $n>1$ and for $0\leq k\leq\phi(n)$,

 $a_{n}(\phi(n)-k)=a_{n}(k).$
###### Proof.

For $P(x)=\sum_{j=0}^{n}a(j)x^{j}$, check that $a(j)=a(n-j)$ for each $0\leq j\leq n$ is equivalent to $x^{n}P(x^{-1})=P(x)$. But because $n>1$, by Lemma 5 we have $\Phi_{n}(x^{-1})=x^{-\phi(n)}\Phi_{n}(x)$, so we obtain the claim. ∎

Migotti [35] proves the following, and also calculates $a_{105}(7)=-2$. The following is also proved by Bang [2]; cf. Beiter [4].

###### Theorem 21 (Bang).

For odd primes $p,

 $a_{pq}(k)\in\{0,-1,1\}.$
###### Proof.

By Lemma 1,

 $\displaystyle\Phi_{pq}(x)$ $\displaystyle=\frac{(x^{pq}-1)(x-1)}{(x^{p}-1)(x^{q}-1)}$ $\displaystyle=\frac{(1-x)\sum_{\alpha=0}^{p-1}x^{\alpha q}}{1-x^{p}}$ $\displaystyle=(1-x)\sum_{0\leq\alpha\leq p-1}x^{\alpha q}\cdot\sum_{\beta\geq 0% }x^{\beta p}$ $\displaystyle=\sum_{0\leq\alpha\leq p-1,\beta\geq 0}x^{\alpha q+\beta p}-\sum_% {0\leq\alpha\leq p-1,\beta\geq 0}x^{\alpha q+\beta p+1}$ $\displaystyle=\sum_{0\leq\alpha\leq p-1,\beta\geq 0,0\leq\delta\leq 1}(-1)^{% \delta}x^{\alpha q+\beta p+\delta}.$

Suppose by contradiction that $\alpha_{1}q+\beta_{1}p+\delta_{1}=\alpha_{2}q+\beta_{2}p+\delta_{2}$ with $\delta_{1}=\delta_{2}$. Then $q(\alpha_{1}-\alpha_{2})=p(\beta_{2}-\beta_{1})$, which implies that $p$ divides $\alpha_{1}-\alpha_{2}$. But $0\leq\alpha_{1},\alpha_{2}\leq p-1$ means $0\leq|\alpha_{1}-\alpha_{2}|\leq p-1$, so $\alpha_{1}-\alpha_{2}=0$ and thence $\beta_{2}-\beta_{1}=0$, which means that $(\alpha_{1},\beta_{1},\delta_{1})=(\alpha_{2},\beta_{2},\delta_{2})$. Therefore, for $0\leq k\leq\phi(pq)$ there are zero, one, or two triples $(\alpha,\beta,\delta)$ such that $k=\alpha q+\beta p+\delta$; if there are two such triples, then one has $\delta=0$ and one has $\delta=1$. If there are no such triples, then $a_{n}(k)=0$. If there is one such triple $(\alpha,\beta,\delta)$, then $a_{n}(k)=(-1)^{\delta}$. If there are two such triples, then $a_{n}(k)=(-1)^{0}+(-1)^{1}=0$. ∎

Lam and Leung [26] determine the following explicit formula.

###### Theorem 22 (Lam and Leung).

Suppose that $p are primes. Then there are nonnegative integers $r,s$ such $(p-1)(q-1)=rp+sq$, and for $0\leq k\leq\phi(pq)=(p-1)(q-1)$,

 $a_{pq}(k)=\begin{cases}1&\textrm{0\leq i\leq r, 0\leq j\leq s with k=ip+% jq}\\ -1&\textrm{r+1\leq i\leq q-1, s+1\leq j\leq p-1 with k+pq=ip+jq}\\ 0&\textrm{otherwise}\end{cases}$

Furthermore,

 $|\{k:0\leq k\leq\phi(pq),a_{pq}(k)=1\}|=(r+1)(s+1)$

and

 $|\{k:0\leq k\leq\phi(pq),a_{pq}(k)=-1\}|=(p-s-1)(q-r-1).$
###### Proof.

Because $\gcd(p,q)=1$, there is some $0\leq r\leq q-1$ such that

 $rp\equiv-p+1\pmod{q}.$

If $r=q-1$ then we get from the above that $1\equiv 0\pmod{q}$, which is false because $q\neq 1$, so in fact $0\leq r\leq q-2$. Now,

 $s=\frac{(p-1)(q-1)-rp}{q}=\frac{pq-p-q+1-rp}{q}$

is an integer and

 $s=\frac{p(q-r-1)-q+1}{q}\geq\frac{-q+1}{q}>-1,$

hence $s\geq 0$. Also, $s\leq\frac{(p-1)(q-1)}{q}, so $s\leq p-2$. We then have

 $rp+sq=rp+(p-1)(q-1)-rp=(p-1)(q-1).$

For $\xi\in\Delta_{pq}$, because $\Phi_{q}(\xi^{p})=0$ and $\Phi_{p}(\xi^{q})=0$,

 $\sum_{i=0}^{r}(\xi^{p})^{i}=-\sum_{i=r+1}^{q-1}(\xi^{p})^{i},\qquad\sum_{j=0}^% {s}(\xi^{q})^{j}=-\sum_{j=s+1}^{p-1}(\xi^{q})^{j}.$

(Because $0\leq r\leq q-2$ and $0\leq s\leq p-2$, each of the above four sums has a nonempty index set.) From this we have

 $\left(\sum_{i=0}^{r}(\xi^{p})^{i}\right)\left(\sum_{j=0}^{s}(\xi^{q})^{j}% \right)-\left(\sum_{i=r+1}^{q-1}(\xi^{p})^{i}\right)\left(\sum_{j=s+1}^{p-1}(% \xi^{q})^{j}\right)=0.$

Because $\xi^{-pq}=1$, this implies that each $\xi\in\Delta_{pq}$ is a zero of the polynomial

 $f(x)=\left(\sum_{i=0}^{r}x^{ip}\right)\left(\sum_{j=0}^{s}x^{jq}\right)-\left(% \sum_{i=r+1}^{q-1}x^{ip}\right)\left(\sum_{j=s+1}^{p-1}x^{jq}\right)x^{-pq};$

that this is indeed a polynomial follows from

 $(r+1)p+(s+1)q-pq=rp+sq+p+q-pq=1.$

The first product is a monic polynomial of degree $rp+sq=\phi(pq)$. The second product is a polynomial of degree

 $(q-1)p+(p-1)q-pq=-p-q+pq=\phi(pq)-1.$

Therefore $f(x)$ is a monic polynomial of degree $\phi(pq)$. Because each $\xi\in\Delta_{pq}$ is a zero of $f(x)$ and $f(x)$ is monic, $f(x)=\Phi_{pq}(x)$. ∎

Carlitz [10] proves the following.

###### Theorem 23.

Let $p be primes, let

 $qu\equiv-1\pmod{p},\qquad 0

let $\theta(pq)$ be the number of terms of $\Phi_{pq}$ with nonzero coefficients, and let $\theta_{0}(pq)$ be the number of terms of $\Phi_{pq}$ with positive coefficients. Then

 $\theta(pq)=2\theta_{0}(pq)-1$

and

 $\theta_{0}(pq)=(p-u)(uq+1)/p.$

Cobeli, Gallot, Moree and Zaharescu [13] give an exposition of $a_{pqr}(k)$ where $p are primes, $p$ is fixed, and $q,r$ are free.

Bang [2] proves the following.

###### Theorem 24 (Bang).

For odd primes $p,

 $A(pqr)\leq p-1.$

Beiter [5] proves the following improvement for a case of the above theorem. If $p,q,r$, $3, are odd primes for which either $q\equiv\pm 1\pmod{p}$ or $r\equiv\pm 1\pmod{p}$, then

 $A(pqr)\leq\frac{1}{2}(p+1).$

Bloom [6] proves the following.

###### Theorem 25 (Bloom).

For odd primes $p,

 $A(pqrs)\leq p(p-1)(pq-1).$

Gallot and Moree [21]

The following is from Lehmer [27], who says that it appears in an unpublished letter of Schur to Landau; cf. Bourbaki [8, V. 165, §11, Exercise 19].

###### Theorem 26 (Schur).

For any odd $m\geq 3$ there are primes $p_{1}, with $p_{1}+p_{2}>p_{m}$. For such primes,

 $a_{p_{1}p_{2}\cdots p_{m}}(p_{m})=-m+1.$
###### Proof.

Write

 $\pi(x)=|\{p:\textrm{p is prime and p\leq x}\}|.$

For $m\geq 3$, suppose by contradiction that if $p_{1} are primes then $p_{1}+p_{2}\leq p_{m}$, and thus $2p_{1}. For $k\geq 1$, as there are infinitely many primes, let $p_{1}$ be the least prime $>k$, and let $k\leq p_{1}. Then

 $\pi(2k)-\pi(k)=\pi(2k)-\pi(p_{1})+1\leq\pi(2p_{1})-\pi(p_{1})+1\leq(m-1)+1=m.$

This yields, for $j\geq 1$,

 $\pi(2^{j})\leq m+\pi(2^{j-1})\leq m+m+\pi(2^{j-2})\leq\cdots\leq jm.$

But the prime number theorem tells us

 $\pi(2^{j})\sim\frac{2^{j}}{j\log 2},\qquad j\to\infty,$

with which we get a contradiction.

Let $m\geq 3$ be odd and let $p_{1} be primes satisfying $p_{1}+p_{2}>p_{m}$, and let $n=p_{1}p_{2}\cdots p_{m}$. Since $p_{1}+p_{2}>p_{m}$, for $1\leq j,k\leq m$ we have $p_{j}+p_{k}\geq p_{m}+1$. It follows that if $d$ is a divisor of $n$ aside from $1$ and $p_{1},\ldots,p_{m}$, and $\mu(n/d)\neq 0$, then

 $(x^{d}-1)^{\mu(n/d)}\in x^{p_{m}+1}\mathbb{Z}[x].$

Therefore

 $\displaystyle\Phi_{n}(x)+x^{p_{m}+1}\mathbb{Z}[x]$ $\displaystyle=\prod_{d|n}(x^{d}-1)^{\mu(n/d)}+x^{p_{m}+1}\mathbb{Z}[x]$ $\displaystyle=\prod_{d|n,\mu(d/n)\neq 0}(x^{d}-1)^{\mu(n/d)}+x^{p_{m}+1}% \mathbb{Z}[x]$ $\displaystyle=(x-1)^{-1}\cdot\prod_{j=1}^{m}(x^{p_{j}}-1)^{\mu(n/p_{j})}+x^{p_% {m}+1}\mathbb{Z}[x]$ $\displaystyle=(x-1)^{-1}\cdot\prod_{j=1}^{m}(x^{p_{j}}-1)+x^{p_{m}+1}\mathbb{Z% }[x]$ $\displaystyle=(x-1)^{-1}\cdot(-1+x^{p_{1}}+\cdots+x^{p_{m}})+x^{p_{m}+1}% \mathbb{Z}[x].$

Now,

 $\begin{split}&\displaystyle(x-1)^{-1}\cdot(-1+x^{p_{1}}+\cdots-x^{p_{m}})+x^{p% _{m}+1}\mathbb{Z}[x]\\ \displaystyle=&\displaystyle(1+x+x^{2}+\cdots+x^{p_{m}})\cdot(1-x^{p_{1}}-% \cdots-x^{p_{m}})+x^{p_{m}+1}\mathbb{Z}[x].\end{split}$

For $1\leq i\leq m$, there is one and only one $0\leq j\leq p_{m}$ such that $p_{i}+j=p_{m}$. This implies that the coefficient of $x^{p_{m}}$ in the above expression is $-m+1$. ∎

Lehmer also states that in Rolf Bungers’ 1934 dissertation, Über die Koeffizienten von Kreisteilungspolynomen (University of Göttingen), it is proved that if there exist infinitely many twin primes then for any $M$ there are primes $p such that $A(pqr)\geq M$. Lehmer proves this without the hypothesis that there are infinitely many twin primes.

For power series $A(x)=\sum_{k=0}^{\infty}a_{k}x^{k}$ and $B(x)=\sum_{k=0}^{\infty}b_{k}x^{k}$, write

 $A\preceq B$

if $|a_{k}|\leq b_{k}$ for all $k$. For power series $A,B,P,Q$ with $A\preceq P$ and $B\preceq Q$,

 $|a_{k}+b_{k}|\leq|a_{k}|+|b_{k}|\leq p_{k}+q_{k},$

so $A+B\preceq P+Q$, and

 $\left|\sum_{i+j=k}a_{i}b_{j}\right|\leq\sum_{i+j=k}|a_{i}b_{j}|\leq\sum_{i+j=k% }p_{i}q_{j},$

so $AB\preceq PQ$.

Now,

 $x^{d}-1\preceq\sum_{k=0}^{\infty}x^{kd},\quad 1\preceq\sum_{k=0}^{\infty}x^{kd% },\quad(x^{d}-1)^{-1}\preceq\sum_{k=0}^{\infty}x^{kd},$

and since $\mu(n/d)\in\{0,1,-1\}$,

 $\Phi_{n}(x)=\prod_{d\mid n}(x^{d}-1)^{\mu(n/d)}\preceq\prod_{d\mid n}\left(% \sum_{k=0}^{\infty}x^{kd}\right)=\prod_{d\mid n}\frac{1}{1-x^{d}}.$ (5)

Hence, because $1\preceq\frac{1}{1-x^{j}}$,

 $\Phi_{n}(x)\preceq\prod_{j=1}^{\infty}\frac{1}{1-x^{j}}.$

Let $n\mapsto p(n)$ be the partition function, the number of ways of writing $n$ as a sum of positive integers, where the order does not matter. $p(0)=1$ and $p(n)=0$ for $n<0$, and for example, $p(4)=5$ because $4=4,3+1,2+2,2+1+1,1+1+1+1$. It is a fact that for $|x|<1$,

 $\prod_{j=1}^{\infty}\frac{1}{1-x^{j}}=\sum_{k=0}^{\infty}p(k)x^{k},$

found by Euler.

###### Theorem 27.
 $|a_{n}(k)|\leq p(k),$

and so

 $A(n)=\max_{0\leq k\leq\phi(n)}|a_{n}(k)|\leq\max_{0\leq k\leq\phi(n)}p(k)\leq p% (\phi(n))\leq p(n).$

It is proved by Hardy and Ramanujan [12, p. 166, Chapter VII] that for $K=\pi\sqrt{\frac{2}{3}}$ and $\lambda_{n}=\sqrt{n-\frac{1}{24}}$,

 $p(n)=\frac{e^{K\lambda_{n}}}{4\sqrt{3}\cdot\lambda_{n}^{2}}+O\left(\frac{e^{K% \lambda_{n}}}{\lambda_{n}^{3}}\right),\qquad n\to\infty.$

This implies

 $p(n)\sim\frac{e^{K\sqrt{n}}}{4\sqrt{3}\cdot n},\qquad n\to\infty.$

Therefore,

 $A(n)=O\left(\frac{e^{K\sqrt{n}}}{n}\right),\qquad S(n)=O(e^{K\sqrt{n}}),\qquad n\to\infty$

Now let

 $Q_{n}(x)=\prod_{d|n}(1+x^{d}+x^{2d}+\cdots+x^{n-d}).$

It is straightforward that for $0\leq k, the coefficient of $x^{k}$ in $Q_{n}(x)$ is equal to the coefficient of $x^{k}$ in $\prod_{d\mid n}\frac{1}{1-x^{d}}$. For $n>1$, because the degree of $\Phi_{n}(x)$ is $\phi(n), using (5) we get

 $\Phi_{n}(x)\preceq Q_{n}(x).$

Let

 $d(n)=\sum_{d\mid n}1,$

the number of positive integer divisors of $n$. It is straightforward that

 $\prod_{d\mid n}d=n^{d(n)/2},$

so

 $Q_{n}(1)=\prod_{d\mid n}\frac{n}{d}=\prod_{d\mid n}d=n^{d(n)/2}.$

But from $\Phi_{n}(x)\preceq Q_{n}(x)$ we have that $S(n)$ is $\leq$ the sum of the coefficients of the polynomial $Q_{n}(x)$, i.e.

 $S(n)\leq Q_{n}(1)=n^{d(n)/2}.$

This is found by Bateman [3]; cf. [36, p. 64, Exercise 7].

###### Theorem 28 (Bateman).
 $S(n)\leq\exp\left(\frac{1}{2}d(n)\log n\right).$

A result due to Wigert [12, p. 19, Theorem 6], proved using the prime number theorem, is that

 $\limsup_{n\to\infty}\log d(n)\cdot\frac{\log\log n}{\log n}=\log 2.$

Thus, for each $\epsilon>0$, there is some $n_{\epsilon}$ such that when $n\geq n_{\epsilon}$,

 $\log d(n)\cdot\frac{\log\log n}{\log n}\leq\log 2+\epsilon,$

so

 $\log d(n)\leq\frac{\log n}{\log\log n}(\epsilon+\log 2).$

Then

 $\log S(n)\leq\frac{d(n)}{2}\cdot\log n\leq\frac{\log n}{2}\exp\left(\frac{\log n% }{\log\log n}(\epsilon+\log 2)\right).$

Wirsing [46]

Konyagin, Maier and Wirsing [24]

Maier [29], [30], [31], [32]

Bachman [1]

Bzdęga [9]

Nicolas and Terjanian [41]

Let $\Psi_{n}(x)=\frac{x^{n}-1}{\Phi_{n}(x)}$, i.e. $\Psi_{n}(x)=\prod_{d\mid n,d, which belongs to $\mathbb{Z}[x]$ and is monic. Moree [37] proves the following.

## 8 Analytic theorems about coefficients of cyclotomic polynomials

Erdős [18]

Erdős and Vaughan [17] prove the following.

Vaughan [43] proves the next theorem. Vaughan’s original proof is complicated and delightful, and we first outline it and then give a radically simplified proof using Theorem 11, attributed to Saffari by Montgomery and Vaughan [36, pp. 131–132, Exercise 9].

For $n=\prod_{p\leq y,p\equiv 2,3\pmod{5}}p$ with $\omega(n)$ odd, let $c_{m}=-\frac{c_{n}(m)}{m}$. Because $n$ is square-free and $\mu(n)=-1$, it follows from Lemma 17 that $m\mapsto c_{m}$ is multiplicative. Because $c_{m}=O(m^{-1})$, the following Euler product expansions hold [36, p. 20, Theorem 1.9]:

 $\sum_{m=1}^{\infty}c_{m}m^{-s}=\prod_{p}\sum_{k=0}^{\infty}c_{p^{k}}p^{-ks},% \qquad\mathrm{Re}\,s>0$

and

 $\sum_{m=1}^{\infty}\chi(m)c_{m}m^{-s}=\prod_{p}\sum_{k=0}^{\infty}\chi(p^{k})c% _{p^{k}}p^{-ks},\qquad\mathrm{Re}\,s>0,$

where $\chi$ is the quadratic Dirichlet character modulo $5$. Using Hölder’s formula (2) one works out that for $p\mid n$,

 $\sum_{k=0}^{\infty}c_{p^{k}}p^{-ks}=\frac{1-p^{-s}}{1-p^{-(s+1)}}$

and for $p\nmid n$,

 $\sum_{k=0}^{\infty}c_{p^{k}}p^{-ks}=\frac{1}{1-p^{-(s+1)}},$

thus

 $\sum_{m=1}^{\infty}c_{m}m^{-s}=\zeta(1+s)\prod_{p\mid n}(1-p^{-s}),\qquad% \mathrm{Re}\,s>0.$

Using Hölder’s formula and that $\chi$ is completely multiplicative, one works out that for $p\mid n$,

 $\sum_{k=0}^{\infty}\chi(p^{k})c_{p^{k}}p^{-ks}=\frac{1+p^{-s}}{1-\chi(p)p^{-(s% +1)}}$

and for $p\nmid n$,

 $\sum_{k=0}^{\infty}\chi(p^{k})c_{p^{k}}p^{-ks}=\frac{1}{1-\chi(p)p^{-(s+1)}},$

thus

 $\sum_{m=1}^{\infty}\chi(m)c_{m}m^{-s}=L(1+s,\chi)\prod_{p\mid n}(1+p^{-s}),% \qquad\mathrm{Re}\,s>0.$

Using (i) the fact that the Gauss sum $\sum_{r=1}^{4}\chi(r)e^{2\pi ira/5}$ is equal to $\chi(a)\sqrt{5}$, (ii) the fact that $c_{5m}=\frac{c_{m}}{5}$, and (iii) $e^{2\pi im/5}+e^{2\pi i\cdot 4m/5}=2\cdot\mathrm{Re}\,e^{2\pi im/5}$, one works out that for $x>0$,

 $4\cdot\mathrm{Re}\,\sum_{m=1}^{\infty}c_{m}e^{2\pi im/5}e^{-m/x}=\sum_{m=1}^{% \infty}c_{m}\left(\sqrt{5}\cdot\chi(m)e^{-m/x}+e^{-5m/x}-e^{-m/x}\right).$

Using this and the above Euler product expansions we get for $s>0$,

 $\begin{split}&\displaystyle\int_{0}^{\infty}\left(\mathrm{Re}\,\sum_{m=1}^{% \infty}c_{m}e(m/5)e^{-m/x}\right)x^{-s-1}dx\\ \displaystyle=&\displaystyle\frac{\Gamma(s)}{4}\left(\sqrt{5}\cdot L(1+s,\chi)% \prod_{p\mid n}(1+p^{-s})-(1-5^{-s})\zeta(1+s)\prod_{p\mid n}(1-p^{-s})\right)% .\end{split}$

For $x>0$, writing $f(x)=\mathrm{Re}\,\sum_{m=1}^{\infty}c_{m}e^{2\pi im/5}e^{-m/x}$, one has for $0<\sigma<1$,

 $\int_{0}^{\infty}f(x)x^{-\sigma-1}dx\leq\frac{1}{1-\sigma}+\frac{1}{\sigma}% \sup_{x\geq 1}f(x),$

so

 $\begin{split}&\displaystyle\sup_{x\geq 1}f(x)\\ \displaystyle\geq&\displaystyle\sigma\int_{0}^{\infty}f(x)x^{-\sigma-1}dx-% \frac{\sigma}{1-\sigma}\\ \displaystyle=&\displaystyle\frac{\sigma\Gamma(\sigma)}{4}\left(\sqrt{5}\cdot L% (1+\sigma,\chi)\prod_{p\mid n}(1+p^{-\sigma})-(1-5^{-\sigma})\zeta(1+\sigma)% \prod_{p\mid n}(1-p^{-\sigma})\right)\\ &\displaystyle-\frac{\sigma}{1-\sigma}.\end{split}$

As $\sigma\to 0$ we have $\sigma\Gamma(\sigma)=1+O(\sigma)$, $(1-5^{-\sigma})\zeta(1+\sigma)=\log 5+O(\sigma)$, and $1-p^{-\sigma}=\sigma\log p+O(\sigma^{2})$, thus

 $\sup_{x\geq 1}f(x)\geq\frac{1}{4}\cdot\sqrt{5}\cdot L(1,\chi)\cdot 2^{\omega(n% )}=\frac{1}{4}\cdot\sqrt{5}\cdot L(1,\chi)\cdot d(n).$

But Theorem 16 tells us that for $|z|<1$,

 $|\Phi_{n}(z)|=\exp\left(\mathrm{Re}\,\sum_{m=1}^{\infty}c_{m}z^{m}\right),$

so $|\Phi_{n}(e^{2\pi i/5}e^{-1/x})|=e^{f(x)}$ and thus

 $\sup_{|z|<1}|\Phi_{n}(z)|\geq\exp\left(\frac{1}{4}\cdot\sqrt{5}\cdot L(1,\chi)% \cdot d(n)\right).$

As $\chi$ is the quadratic Dirichlet character modulo $5$, it is a fact that $L(1,\chi)$ can be explicitly evaluated (this is an instance of Dirichlet’s class number formula), and using this one checks that $\exp\left(\frac{1}{2}\cdot\sqrt{5}\cdot L(1,\chi)\right)=\frac{1+\sqrt{5}}{2}$. Therefore

 $\sup_{|z|<1}|\Phi_{n}(z)|\geq\left(\frac{1+\sqrt{5}}{2}\right)^{d(n)/2}.$
###### Theorem 29 (Vaughan).

If $n=\prod_{p\leq y,p\equiv 2,3\pmod{5}}p$ with $\omega(n)$ odd, then

 $|\Phi_{n}(e^{2\pi i/5})|=\left(\frac{1+\sqrt{5}}{2}\right)^{d(n)/2}.$

There are infinitely many $n$ such that

 $\log A(n)>\exp\left(\frac{(\log 2)(\log n)}{\log\log n}\right).$
###### Proof.

Vaughan further proves the following.

###### Theorem 30 (Vaughan).

There is some $C$ such that for infinitely many $k$,

 $\log\max_{n\geq 1}|a_{n}(k)|\geq Ck^{1/2}(\log k)^{-1/4}.$

## 9 Fourier analysis

Let $\mathbb{T}=\mathbb{R}/\mathbb{Z}$. For $p\geq 1$, define

 $\left\|f\right\|_{L^{p}}=\left(\int_{0}^{1}|f(x)|^{p}dx\right)^{1/p}$

and $\left\|f\right\|_{L^{\infty}}=\sup_{x\in[0,1]}|f(x)|$. By Jensen’s inequality, if $1\leq p\leq q\leq\infty$ then

 $\left\|f\right\|_{L^{p}}\leq\left\|f\right\|_{L^{q}}.$

For $f\in L^{1}(\mathbb{T})$, define $\widehat{f}:\mathbb{Z}\to\mathbb{C}$ by

 $\widehat{f}(k)=\int_{0}^{1}e^{-2\pi ikx}f(x)dx.$

Define

 $\left\|\widehat{f}\right\|_{\ell^{p}}=\left(\sum_{k\in\mathbb{Z}}|\widehat{f}(% k)|^{p}\right)^{1/p}$

and $\left\|\widehat{f}\right\|_{\ell^{\infty}}=\sup_{k\in\mathbb{Z}}|\widehat{f}(k)|$. For $1\leq p\leq q\leq\infty$,

 $\left\|\widehat{f}\right\|_{\ell^{q}}\leq\left\|\widehat{f}\right\|_{\ell^{p}}.$

Plancherel’s theorem tells us that

 $\left\|f\right\|_{L^{2}}=\left\|\widehat{f}\right\|_{\ell^{2}}.$

The Hausorff-Young inequality states that for $1\leq p\leq 2$ and $\frac{1}{p}+\frac{1}{q}=1$,

 $\left\|\widehat{f}\right\|_{\ell^{q}}\leq\left\|f\right\|_{L^{p}}.$

Nikolsky’s inequality [14, p. 102, Theorem 2.6] says that if $\widehat{f}(k)=0$ for $|k|>n$, namely $f$ is a trigonometric polynomial of degree $n$, then for $0 and for $r\geq\frac{p}{2}$ an integer,

 $\left\|f\right\|_{L^{q}}\leq(2nr+1)^{\frac{1}{p}-\frac{1}{q}}\left\|f\right\|_% {L^{p}}.$

On the other hand, using Jensen’s inequality for sums one proves that if $f$ is a trigonometric polynomial of degree $n$, then for $1\leq p\leq q\leq\infty$,

 $\left\|\widehat{f}\right\|_{\ell^{p}}\leq(2n+1)^{\frac{1}{p}-\frac{1}{q}}\left% \|\widehat{f}\right\|_{\ell^{q}}.$

For $f:\mathbb{T}\to\mathbb{C}$, define

 $\left\|\hat{f}\right\|_{\ell^{0}}=|\mathrm{supp}\,\hat{f}|=\left|\{n\in\mathbb% {Z}:\hat{f}(n)\neq 0\}\right|.$

McGehee, Pigno and Smith [33] prove that there is some $K$ such that for all $N$, if $n_{1},\ldots,n_{N}$ are distinct integers and $c_{1},\ldots,c_{N}\in\mathbb{C}$ satisfy $|c_{k}|\geq 1$, then

 $\left\|\sum_{k=1}^{N}c_{k}e^{2\pi in_{k}t}\right\|_{L^{1}}\geq K\log N.$

That is, if $f:\mathbb{T}\to\mathbb{C}$ is a trigonometric polynomial with $|\hat{f}(n)|\geq 1$ when $\hat{f}(n)\neq 0$, then

 $\left\|f\right\|_{L^{1}}\geq K\log\left\|\hat{f}\right\|_{\ell^{0}}.$

For $F:\mathbb{Z}/N\to\mathbb{C}$, define $\widehat{F}:\mathbb{Z}/N\to\mathbb{C}$ by

 $\widehat{F}(k)=\frac{1}{N}\sum_{j=0}^{N-1}F(j)e^{-2\pi ijk/N},\qquad 0\leq k% \leq N-1.$

One checks that [36, pp. 109–110, §4.1]

 $F(j)=\sum_{k=0}^{N-1}\widehat{F}(k)e^{2\pi ijk/N},\qquad 0\leq j\leq N-1$

and

 $\sum_{k=0}^{N-1}|\widehat{F}(k)|^{2}=\frac{1}{N}\sum_{j=0}^{N-1}|F(j)|^{2}.$

For $a_{0},\ldots,a_{N-1}\in\mathbb{C}$, define $f:\mathbb{T}\to\mathbb{C}$ by

 $f(x)=\sum_{k=0}^{N-1}a_{k}e^{2\pi ikx}$

and define $F:\mathbb{Z}/N\to\mathbb{C}$ by

 $F(j)=f(j/N)=\sum_{k=0}^{N-1}a_{k}e^{2\pi ikj/N},\qquad 0\leq j\leq N-1,$

for which we calculate $\widehat{F}(k)=a_{k}$, for $0\leq k\leq N-1$. Then

 $\sum_{k=0}^{N-1}|a_{k}|^{2}=\sum_{k=0}^{N-1}|\widehat{F}(k)|^{2}=\frac{1}{N}% \sum_{j=0}^{N-1}|F(j)|^{2}=\frac{1}{N}\sum_{j=0}^{N-1}|f(j/N)|^{2}.$

Carlitz [11]

## 10 Algebraic topology

Musiker and Reiner [38]

Meshulam [34]

## References

• [1] G. Bachman (1993) On the coefficients of cyclotomic polynomials. Memoirs of the American Mathematical Society 106 (510), pp. 1–80. Cited by: §7.
• [2] A. S. Bang (1895) Om Ligningen $\Phi_{m}(X)=0$. Nyt Tidsskrift for Mathematik, Afdeling B 6, pp. 6–12. Cited by: §7, §7.
• [3] P. T. Bateman (1949) Note on the coefficient of the cyclotomic polynomial. Bull. Amer. Math. Soc. 55 (12), pp. 1180–1181. Cited by: §7.
• [4] M. Beiter (1964) The midterm coefficient of the cyclotomic polynomial $F_{pq}(x)$. Amer. Math. Monthly 71 (7), pp. 769–770. Cited by: §7.
• [5] M. Beiter (1968) Magnitude of the coefficients of the cyclotomic polynomial $F_{pqr}(x)$. Amer. Math. Monthly 75 (4), pp. 370–372. Cited by: §7.
• [6] D. M. Bloom (1968) On the coefficients of the cyclotomic polynomials. Amer. Math. Monthly 75, pp. 372–377. Cited by: §7.
• [7] N. Bourbaki (1972) Elements of mathematics. Commutative algebra. Addison-Wesley. Cited by: §2.
• [8] N. Bourbaki (1990) Elements of mathematics. Algebra II, chapters 4–7. Springer. Note: Translated by P. M. Cohn and J. Howie Cited by: §7.
• [9] B. Bzd\kega (2012) On the height of cyclotomic polynomials. Acta Arith. 152 (4), pp. 349–359. Cited by: §7.
• [10] L. Carlitz (1966) The number of terms in the cyclotomic polynomial $F_{pq}(x)$. Amer. Math. Monthly 73 (9), pp. 979–981. Cited by: §7.
• [11] L. Carlitz (1967) The sum of the squares of the coefficients of the cyclotomic polynomial. Acta Math. Acad. Sci. Hungar. 18, pp. 295–302. Cited by: §9.
• [12] K. Chandrasekharan (1970) Arithmetical functions. Die Grundlehren der mathematischen Wissenschaften, Vol. 167, Springer. Cited by: §7, §7.
• [13] C. Cobeli, Y. Gallot, P. Moree, and A. Zaharescu (2013) Sister Beiter and Kloosterman: a tale of cyclotomic coefficients and modular inverses. Indagationes Mathematicae 24, pp. 915–929. Cited by: §7.
• [14] R. A. DeVore and G. G. Lorentz (1993) Constructive approximation. Die Grundlehren der mathematischen Wissenschaften, Vol. 303, Springer. Cited by: §9.
• [15] P. G. L. Dirichlet (1999) Lectures on number theory. History of Mathematics, Vol. 16, American Mathematical Society, Providence, RI. Note: Supplements by R. Dedekind, translated from the German by John Stillwell Cited by: §6.
• [16] D. S. Dummit and R. M. Foote (2004) Abstract algebra. third edition, John Wiley & Sons. Cited by: §2, §2, §6.
• [17] P. Erdős and R. C. Vaughan (1974) Bounds for the $r$-th coefficients of cyclotomic polynomials. J. London Math. Soc. (2) 8 (3), pp. 393–400. Cited by: §8.
• [18] P. Erdős (1957) On the growth of the cyclotomic polynomial in the interval $(0,1)$. Proceedings of the Glasgow Mathematical Association 3 (2), pp. 102–104. Cited by: §8.
• [19] J. Escofier (2001) Galois theory. Graduate Texts in Mathematics, Vol. 204, Springer. Note: Translated by Leila Schneps Cited by: §6.
• [20] G. Everest and T. Ward (2005) An introduction to number theory. Graduate Texts in Mathematics, Vol. 232, Springer. Cited by: §5.
• [21] Y. Gallot and P. Moree (2009) Ternary cyclotomic polynomials having a large coefficient. J. reine angew. Math. 632, pp. 105–125. Cited by: §7.
• [22] C. F. Gauss (1876) Carl Friedrich Gauss. Werke. Zweiter Band. Königlichen Gesellschaft der Wissenschaften zu Göttingen. Cited by: §6.
• [23] K. Kato, N. Kurokawa, and T. Saito (2011) Number theory 2: introduction to class field theory. Translations of Mathematical Monographs, Vol. 240, American Mathematical Society, Providence, RI. Note: Translated by Masato Kuwata and Katsumi Nomizu Cited by: §6.
• [24] S. Konyagin, H. Maier, and E. Wirsing (2004) Cyclotomic polynomials with many primes dividing their orders. Period. Math. Hungar. 49 (2), pp. 99–106. Cited by: §7.
• [25] R. P. Kurshan and A. M. Odlyzko (1981) Values of cyclotomic polynomials at roots of unity. Math. Scand. 49, pp. 15–35. Cited by: §3.
• [26] T. Y. Lam and K. H. Leung (1996) On the cyclotomic polynomial $\Phi_{pq}(X)$. Amer. Math. Monthly 103 (7), pp. 562–564. Cited by: §7.
• [27] E. Lehmer (1936) On the magnitude of the coefficients of the cyclotomic polynomial. Bull. Amer. Math. Soc. 42 (6), pp. 389–392. Cited by: §7.
• [28] R. Lidl and H. Niederreiter (1997) Finite fields. Encyclopedia of Mathematics and Its Applications, Vol. 20, Cambridge University Press. Cited by: §2.
• [29] H. Maier (1990) The coefficients of cyclotomic polynomials. In Analytic Number Theory. Proceedings of a Conference in Honor of Paul T. Bateman, B. C. Berndt, H. G. Diamond, H. Halberstam, and A. Hildebrand (Eds.), Progress in Mathematics, Vol. 85, pp. 349–366. Cited by: §7.
• [30] H. Maier (1996) The size of the coefficients of cyclotomic polynomials. In Analytic Number Theory. Proceedings of a Conference in Honor of Heini Halberstam, Volume 2, B. C. Berndt, H. G. Diamond, and A. J. Hildebrand (Eds.), Progress in Mathematics, Vol. 139, pp. 633–639. Cited by: §7.
• [31] H. Maier (2006) The distribution of the $L^{2}$-norm of cyclotomic polynomials on the unit circle. In Elementare und analytische Zahlentheorie, W. Schwarz and J. Steuding (Eds.), Schriften der Wissenschaftlichen Gesellschaft an der Johann Wolfgang Goethe-Universität Frankfurt am Main, Vol. 20, pp. 164–179. Cited by: §7.
• [32] H. Maier (2008) Anatomy of integers and cyclotomic polynomials. In Anatomy of Integers, J. De Koninck, A. Granville, and F. Luca (Eds.), CRM Proceedings & Lecture Notes, Vol. 46, pp. 89–95. Cited by: §7.
• [33] O. C. McGehee, L. Pigno, and B. Smith (1981) Hardy’s inequality and the $L^{1}$ norm of exponential sums. Ann. of Math. (2) 113 (3), pp. 613–618. Cited by: §9.
• [34] R. Meshulam (2012) Homology of balanaced complexes via the Fourier transform. J. Algebraic Combin. 35, pp. 565–571. Cited by: §10.
• [35] A. Migotti (1883) Zur Theorie der Kreistheilungsgleichung. Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften 87, pp. 7–14. Note: Heft I, Abt. II Cited by: §7.
• [36] H. L. Montgomery and R. C. Vaughan (2006) Multiplicative number theory I: classical theory. Cambridge Studies in Advanced Mathematics, Vol. 97, Cambridge University Press. Cited by: §3, §6, §7, §8, §8, §9.
• [37] P. Moree (2009) Inverse cyclotomic polynomials. J. Number Theory 129, pp. 667–680. Cited by: §7.
• [38] G. Musiker and V. Reiner (2014) The cyclotomic polynomial topologically. J. reine angew. Math. 687, pp. 113–132. Cited by: §10.
• [39] J. Neukirch (1999) Algebraic number theory. Grundlehren der mathematischen Wissenschaften, Vol. 322, Springer. Note: Translated from the German by Norbert Schappacher Cited by: §2.
• [40] O. Neumann (2007) The Disquisitiones Arithmeticae and the theory of equations. In The Shaping of Arithmetic after C. F. Gauss’s Disquisitiones Arithmeticae, C. Goldstein, N. Schappacher, and J. Schwermer (Eds.), pp. 107–127. Cited by: §2.
• [41] J. Nicolas and G. Terjanian (1999) Une majoration de la longueur des polynômes cyclotomiques. Enseign. Math. (2) 45 (3-4), pp. 301–309. Cited by: §7.
• [42] R. Thangadurai and A. Vatwani (2011) The least prime congruent to one modulo $n$. Amer. Math. Monthly 118 (8), pp. 737–742. Cited by: §4.
• [43] R. C. Vaughan (1974) Bounds for the coefficients of cyclotomic polynomials. Michigan Math. J. 21, pp. 289–295 (1975). Cited by: §8.
• [44] L. C. Washington (1997) Introduction to cyclotomic fields. second edition, Graduate Texts in Mathematics, Vol. 83, Springer. Cited by: §2, §4, §4.
• [45] A. Weil (1984) Number theory: an approach through history from Hammurapi to Legendre. Birkhäuser. Cited by: §2.
• [46] E. Wirsing (2006) The third logarithmic momentum of the cyclotomic polynomial on the unit circle and factorizations with a linear side condition. In Elementare und analytische Zahlentheorie, W. Schwarz and J. Steuding (Eds.), Schriften der Wissenschaftlichen Gesellschaft an der Johann Wolfgang Goethe-Universität Frankfurt am Main, Vol. 20, pp. 297–312. Cited by: §7.