Cyclotomic polynomials

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

Write

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

the $n$th roots of unity. For $n>1$, there is an element $\zeta$ of $U_n$ with $\zeta \ne 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 \ne 1$, which means that

$$\sum _{k=0}^{n-1}{e}^{2\pi ik/n}=\sum _{\xi \in U_n}\xi =0,n>1.$$

Write

$${\mathrm{\Delta }}_n=\{e^{2\pi ik/n}:1\le k\le n,\gcd (k,n)=1\},$$

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

$$\varphi (n)=|\{k:1\le k\le n,\gcd (k,n)=1\}|=|{\mathrm{\Delta }}_n|.$$

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

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

$$\mu (n)=\sum _{1\le k\le n,\gcd (k,n)=1}{e}^{2\pi ik/n}=\sum _{\xi \in {\mathrm{\Delta }}_n}\xi .$$

For $p$ prime, as ${\mathrm{\Delta }}_p=U_p\setminus \{1\}$,

$$\mu (p)=-1+\sum _{\xi \in U_p}\xi =0-1=-1.$$

For $r\ge 2$, as ${\mathrm{\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

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

$$g(n)=\sum _{d\mid n}f(d),n\ge 1,$$

then

$$f(n)=\sum _{d\mid n}\mu (n/d)g(d),n\ge 1.$$

We can write

$$U_n=\bigcup _{d\mid n}{\mathrm{\Delta }}_d,$$

and ${\mathrm{\Delta }}_d\cap {\mathrm{\Delta }}_e=\mathrm{\varnothing }$ for $d\ne e$. So

$$n=\sum _{d\mid n}\varphi (d).$$

Therefore by the Möbius inversion formula,

$$\varphi (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 {\mathrm{\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}\mathrm{\cdots }{p}_r^{{\alpha }_r}$, ${\alpha }_1,\mathrm{\dots },{\alpha }_r\ge 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\ge 1$, let

$${\mathrm{\Phi }}_n(x)=\prod _{1\le k\le n,\gcd (k,n)=1}(x-e^{2\pi ik/n})=\prod _{\xi \in {\mathrm{\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\ge 1$,

$$x^n-1=\prod _{d\mid n}{\mathrm{\Phi }}_d(x),$$

and for $x\notin U_n$,

$${\mathrm{\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\le k\le n$, is a distinct root of $F_n(x)$, so

$x^n-1$ $={\displaystyle \prod _{1\le k\le n}}(x-e^{2\pi ik/n})$

$={\displaystyle \prod _{d\mid n}}{\displaystyle \prod _{1\le k\le n,\gcd (k,n)=d}}(x-e^{2\pi ik/n})$

$={\displaystyle \prod _{d\mid n}}{\displaystyle \prod _{1\le j\le n/d,\gcd (j,n/d)=1}}(x-e^{2\pi ijd/n})$

$={\displaystyle \prod _{d\mid n}}{\mathrm{\Phi }}_{n/d}(x)$

$={\displaystyle \prod _{d\mid n}}{\mathrm{\Phi }}_d(x).$

That is, $\log F_n={\sum }_{d\mid n}\log {\mathrm{\Phi }}_d$. Therefore applying the Möbius inversion formula yields $\log {\mathrm{\Phi }}_n={\sum }_{d\mid n}\mu (n/d)\log F_d$ and so ${\mathrm{\Phi }}_n={\prod }_{d\mid n}{F}_d^{\mu (n/d)}$. ∎

Lemma 2.

When $p$ is a prime,

$${\mathrm{\Phi }}_p(x)=x^{p-1}+\mathrm{\cdots }+x+1.$$

When $p$ is an odd prime,

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

Proof.

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

$${\mathrm{\Phi }}_p(x)=\frac{x^p-1}{{\mathrm{\Phi }}_1(x)}=\frac{x^p-1}{x-1}=x^{p-1}+\mathrm{\cdots }+x+1.$$

When $p$ is an odd prime,

$${\mathrm{\Phi }}_{2p}(x)=\frac{x^{2p}-1}{{\mathrm{\Phi }}_1(x){\mathrm{\Phi }}_2(x){\mathrm{\Phi }}_p(x)}=\frac{x^{2p}-1}{(x^p-1){\mathrm{\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}-\mathrm{\cdots }+x^2-x+1)=x^p+1$,

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

∎

Lemma 3.

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

For $k\ge 1$,

Proof.

Using Lemma 1,

${\mathrm{\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 {\displaystyle \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 {\displaystyle \prod _{d\mid (pm),p\nmid d}}{(x^d-1)}^{\mu (pm/d)}$

$={\mathrm{\Phi }}_m(x^p)\cdot {\displaystyle \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 (a{p}^2/d)=0$ and

$${\mathrm{\Phi }}_{pm}(x)={\mathrm{\Phi }}_m(x^p)\cdot \prod _{d\mid a}{(x^d-1)}^{\mu (a{p}^2/d)}={\mathrm{\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

$${\mathrm{\Phi }}_{pm}(x)={\mathrm{\Phi }}_m(x^p)\cdot \prod _{d\mid (pm),p\nmid d}{(x^d-1)}^{\mu (pm/d)}={\mathrm{\Phi }}_m(x^p)\cdot \prod _{d\mid m}{(x^d-1)}^{-\mu (m/d)}.$$

For $k\ge 2$,

$${\mathrm{\Phi }}_{p^{k}m}(x)={\mathrm{\Phi }}_{p\cdot p^{k-1}m}(x)={\mathrm{\Phi }}_{p^{k-1}m}(x^p)=\mathrm{\cdots }={\mathrm{\Phi }}_{pm}(x^{p^{k-1}}),$$

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

Lemma 4.

For $n=p_1^{{\alpha }_1}\mathrm{\cdots }{p}_r^{{\alpha }_r}$, where $p_i$ are prime and ${\alpha }_i\ge 1$, and $N=p_1\mathrm{\cdots }{p}_r$,

$${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_N(x^{n/N}).$$

Proof.

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

${\mathrm{\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)}$

$={\mathrm{\Phi }}_N(x^{n/N}).$

∎

Lemma 5.

If $n>1$ then

$${\mathrm{\Phi }}_n(x^{-1})=x^{-\varphi (n)}{\mathrm{\Phi }}_n(x).$$

Proof.

$${\mathrm{\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

$${\mathrm{\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)=\varphi (n)$ yields

$${\mathrm{\Phi }}_n(x^{-1})=x^{-\varphi (n)}{\mathrm{\Phi }}_n(x).$$

∎

Lemma 6.

If $r>1$ is odd then

$${\mathrm{\Phi }}_{2r}(x)={\mathrm{\Phi }}_r(-x).$$

Proof.

Because $r$ is odd, if $d_1,\mathrm{\dots },d_l$ are the divisors of $r$ then

$$d_1,\mathrm{\dots },d_l,2d_1,\mathrm{\dots },2d_l$$

are the divisors of $2r$, so

${\mathrm{\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 {\displaystyle \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

$${\mathrm{\Phi }}_{2r}(x)=\prod _{d\mid r}{(-1)}^{\mu (r/d)}{({(-x)}^d-1)}^{\mu (r/d)}={(-1)}^{\varphi (r)}\cdot \prod _{d\mid r}{({(-x)}^d-1)}^{\mu (r/d)}.$$

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

Theorem 7.

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

First, ${\mathrm{\Phi }}_1(x)=x-1\in \mathbb{Z}[x]$. For $n>1$, assume that ${\mathrm{\Phi }}_d(x)\in \mathbb{Z}[x]$ for . Then let

which by hypothesis belongs to $\mathbb{Z}[x]$. Since each ${\mathrm{\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 . On the other hand, by Lemma 1 we have $g={\mathrm{\Phi }}_{n}f\in ℂ[x]$. Thus ${\mathrm{\Phi }}_{n}f=qf+r\in ℂ[x]$, so $r=f\cdot ({\mathrm{\Phi }}_n-q)\in ℂ[x]$. If ${\mathrm{\Phi }}_n\ne q$ then $\mathrm{deg}r=\mathrm{deg}f+\mathrm{deg}({\mathrm{\Phi }}_n-q)\ge \mathrm{deg}f$, contradicting that $r=0$ or . Therefore ${\mathrm{\Phi }}_n=q\in ℂ[x]$, and because $q\in \mathbb{Z}[x]$ this means that ${\mathrm{\Phi }}_n\in \mathbb{Z}[x]$. ∎

In fact, it can be proved that ${\mathrm{\Phi }}_n$ is irreducible in $\mathbb{Q}[x]$. Gauss states in entry 40 of his mathematical diary, dated October 9, 1796, that ${\mathrm{\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$, ${\mathrm{\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\mathrm{-}\mathrm{1}$. Gauss’s work on cyclotomic polynomials is surveyed by Neumann [40]. For any $\xi \in {\mathrm{\Delta }}_n$, ${\mathrm{\Phi }}_n(\xi )=0$, and since ${\mathrm{\Phi }}_n$ is irreducible in $\mathbb{Q}[x]$ and is monic, $\mathrm{\Phi }$ is the minimal polynomial of $\xi$ over $\mathbb{Q}$, which implies that $[\mathbb{Q}(\xi ):\mathbb{Q}]=\mathrm{deg}{\mathrm{\Phi }}_n=\varphi (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)}^{\varphi (n)/2}{n}^{\varphi (n)}}{{\prod }_{p\mid n}{p}^{\varphi (n)/(p-1)}}.$$

It can be proved that ${𝒪}_{\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\ge 1$, let ${𝔽}_q$ be a finite field with $q$ elements, and for $n\ge 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(modn)$. It can be proved that there are monic, degree $\nu$, irreducible polynomials $P_1,\mathrm{\dots },P_{\varphi (n)/\nu }\in {𝔽}_q[x]$ such that ${\mathrm{\Phi }}_n=P_1\mathrm{\cdots }{P}_{\varphi (n)/\nu }\in {𝔽}_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 =\varphi (n)$ if and only if ${\mathrm{\Phi }}_n$ is irreducible in ${𝔽}_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 \mathrm{\cdots }\times {(\mathbb{Z}/p_r^{{\alpha }_r})}^{*}$ for $n=p_1^{{\alpha }_1}\mathrm{\cdots }{p}_r^{{\alpha }_r}$, (ii) ${(\mathbb{Z}/2^{\alpha })}^{*}$ is isomorphic with $\mathbb{Z}/2\times \mathbb{Z}/2^{\alpha -2}$, $\alpha \ge 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 \ge 1$ [16, p. 314, Corollary 20].

3 Special values

Lemma 8.

${\mathrm{\Phi }}_1(0)=-1$, and for $n\ge 2$, ${\mathrm{\Phi }}_n(0)=1$.

Proof.

${\mathrm{\Phi }}_1(x)=x-1$, so ${\mathrm{\Phi }}_1(0)=-1$. For $n\ge 2$, using (1),

$${\mathrm{\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 $\mathrm{\Lambda }$ be the von Mangoldt function: $\mathrm{\Lambda }(n)=\log p$ if $n=p^{\alpha }$ for some prime $p$ and some integer $\alpha \ge 1$, and is $\mathrm{\Lambda }(n)=0$ otherwise. Thus $\mathrm{\Lambda }(2)=\log 2$, $\mathrm{\Lambda }(8)=\log 2$, $\mathrm{\Lambda }(3)=\log 3$, and $\mathrm{\Lambda }(6)=0$. One sees that

$$\log n=\sum _{d\mid n}\mathrm{\Lambda }(d).$$

Therefore by the Möbius inversion formula,

$$\mathrm{\Lambda }(n)=\sum _{d\mid n}\mu (n/d)\log d.$$

Theorem 9.

For $n>1$,

$${\mathrm{\Phi }}_n(1)=e^{\mathrm{\Lambda }(n)}$$

and

$${\mathrm{\Phi }}_n^{\prime }(1)=\frac{1}{2}{e}^{\mathrm{\Lambda }(n)}\varphi (n).$$

Proof.

For $n>1$,

$$x^{n-1}+\mathrm{\cdots }+x+1=\prod _{d\mid n,d>1}{\mathrm{\Phi }}_d(x),$$

hence

$$\log n=\sum _{d\mid n,d>1}\log {\mathrm{\Phi }}_d(1).$$

Therefore by the Möbius inversion formula,

$$\log {\mathrm{\Phi }}_n(1)=\sum _{d\mid n,d>1}\mu (n/d)\log d=\sum _{d\mid n}\mu (n/d)\log d=\mathrm{\Lambda }(n).$$

Because $x^n-1={\prod }_{d\mid n}{\mathrm{\Phi }}_d(x)$, taking the logarithm and then taking the derivative yields

$$\frac{n{x}^{n-1}}{x^n-1}=\sum _{d\mid n}\frac{{\mathrm{\Phi }}_d^{\prime }(x)}{{\mathrm{\Phi }}_d(x)}.$$

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

$$\frac{n{x}^{n-1}}{x^n-1}-\frac{1}{x-1}=\sum _{d\mid n,d>1}\frac{{\mathrm{\Phi }}_d^{\prime }(x)}{{\mathrm{\Phi }}_d(x)},$$

i.e.

$$\frac{n{x}^{n-1}-(x^{n-1}+x^{n-2}+\mathrm{\cdots }+x+1)}{x^n-1}=\sum _{d\mid n,d>1}\frac{{\mathrm{\Phi }}_d^{\prime }(x)}{{\mathrm{\Phi }}_d(x)}.$$

Doing polynomial long division we find

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

Hence

$$\frac{(n-1)x^{n-2}+(n-2)x^{n-3}+\mathrm{\cdots }+2x+1}{x^{n-1}+x^{n-2}+\mathrm{\cdots }+x+1}=\sum _{d\mid n,d>1}\frac{{\mathrm{\Phi }}_d^{\prime }(x)}{{\mathrm{\Phi }}_d(x)},$$

and for $x=1$ this is

$$\frac{n-1}{2}=\sum _{d\mid n,d>1}\frac{{\mathrm{\Phi }}_d^{\prime }(1)}{{\mathrm{\Phi }}_d(1)}.$$

By the Möbius inversion formula,

$$\frac{{\mathrm{\Phi }}_n^{\prime }(1)}{{\mathrm{\Phi }}_n(1)}=\sum _{d\mid n,d>1}\mu (n/d)\cdot \frac{d-1}{2},$$

and using (i) ${\mathrm{\Phi }}_n(1)=e^{\mathrm{\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)=\varphi (n)$, we have

$${\mathrm{\Phi }}_n^{\prime }(1)=e^{\mathrm{\Lambda }(n)}\frac{1}{2}\sum _{d\mid n}\mu (n/d)\cdot d-e^{\mathrm{\Lambda }(n)}\frac{1}{2}\sum _{d\mid n}\mu (n/d)=\frac{1}{2}{e}^{\mathrm{\Lambda }(n)}\varphi (n).$$

∎

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

Theorem 10.

${\mathrm{\Phi }}_1(i)=i-1$, ${\mathrm{\Phi }}_2(i)=i+1$, ${\mathrm{\Phi }}_4(i)=0$, and otherwise we have the following.

• If $n$ is odd and has a prime factor $p\equiv 1(mod4)$, then ${\mathrm{\Phi }}_n(i)=1$.

• If $p\equiv 3(mod4)$ is prime and $k\ge 1$ is odd, then ${\mathrm{\Phi }}_{p^k}(i)=i$.

• If $p\equiv 3(mod4)$ is prime and $k\ge 1$ is even, then ${\mathrm{\Phi }}_{p^k}(i)=-i$.

• If $p\equiv 3(mod4)$ is prime and $k\ge 1$ is odd, then ${\mathrm{\Phi }}_{2p^k}(i)=-i$.

• If $p\equiv 3(mod4)$ is prime and $k\ge 1$ is even, then ${\mathrm{\Phi }}_{2p^k}(i)=i$.

• If $p,q\equiv 3(mod4)$ are distinct primes and $k,l\ge 1$, then ${\mathrm{\Phi }}_{p^k{q}^l}(i)=-1$.

• If $p,q\equiv 3(mod4)$ are distinct primes and $k,l\ge 1$, then ${\mathrm{\Phi }}_{2p^k{q}^l}(i)=-1$.

• If $p$ is an odd prime and $k\ge 1$, then ${\mathrm{\Phi }}_{4p^k}(i)=p$.

• If $\omega (n)\ge 3$ then ${\mathrm{\Phi }}_n(i)=1$.

Proof.

${\mathrm{\Phi }}_1(x)=x-1$, ${\mathrm{\Phi }}_2(x)=x+1$, so ${\mathrm{\Phi }}_1(i)=i-1$ and ${\mathrm{\Phi }}_2(i)=i+1$. As $i\in {\mathrm{\Delta }}_4$, ${\mathrm{\Phi }}_4(i)=0$.

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

$${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_{p^{k}m}(x)=\frac{{\mathrm{\Phi }}_m(x^{p^k})}{{\mathrm{\Phi }}_m(x^{p^{k-1}})},$$

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

$${\mathrm{\Phi }}_n(i)=\frac{{\mathrm{\Phi }}_m(i)}{{\mathrm{\Phi }}_m(i)}=1.$$

Suppose that $n$ is odd, that $p\equiv 3(mod4)$ 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(mod4)$, so

$${\mathrm{\Phi }}_n(i)=\frac{{\mathrm{\Phi }}_m(i^{p^k})}{{\mathrm{\Phi }}_m(i^{p^{k-1}})}=\frac{{\mathrm{\Phi }}_m(i^3)}{{\mathrm{\Phi }}_m(i)}=\frac{{\mathrm{\Phi }}_m(-i)}{{\mathrm{\Phi }}_m(i)},$$

and if $m=1$ then

$${\mathrm{\Phi }}_n(i)=\frac{{\mathrm{\Phi }}_1(-i)}{{\mathrm{\Phi }}_1(i)}=\frac{-i-1}{i-1}=i.$$

If $k$ is even then $p^k\equiv 1(mod4)$, so

$${\mathrm{\Phi }}_n(i)=\frac{{\mathrm{\Phi }}_m(i)}{{\mathrm{\Phi }}_m(-i)},$$

and if $m=1$ then ${\mathrm{\Phi }}_n(i)=-i$.

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

$${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_2(x^{n/2})={\mathrm{\Phi }}_2(x^{2^{k-1}})=x^{2^{k-1}}+1,$$

thus

$${\mathrm{\Phi }}_n(i)=i^{2^{k-1}}+1=1+1=2.$$

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

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

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

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

$${\mathrm{\Phi }}_{4m}(i)={\mathrm{\Phi }}_m(1),$$

and for $k>2$,

$${\mathrm{\Phi }}_n(i)={\mathrm{\Phi }}_m(-i^{2^{k-1}})={\mathrm{\Phi }}_m(-1).$$

∎

Kurshan and Odlyzko [25]

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

Theorem 11.

If $n={\prod }_{p\le y,p\equiv 2,3(mod5)}p$ with $\omega (n)$ odd, then

$$|{\mathrm{\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\mathrm{\cdots }{p}_k\cdot q_1\mathrm{\cdots }{q}_l$ where $p_1,\mathrm{\dots },p_k\equiv 2(mod5)$ and $q_1,\mathrm{\dots },q_l\equiv 3(mod5)$ are prime. Then $\omega (d)=k+l$ and, as $2^3\equiv 3(mod5)$,

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

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

If $\omega (d)\equiv 1(mod4)$ then $2^{k+l}\equiv 2(mod5)$ and if $\omega (d)\equiv 3(mod4)$ then $2^{k+l}\equiv -2(mod5)$, and therefore if $\omega (d)$ is odd then $d\equiv 2(mod5)$ or $d\equiv -2(mod5)$. 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|$,

$|{\mathrm{\Phi }}_n(e(1/5))|$ $={\displaystyle \prod _{d\mid n}}{|e(d/5)-1|}^{\mu (n/d)}$

$={\displaystyle \prod _{d\mid n,\omega (d)\text{ even}}}{|e(1/5)-1|}^{-1}\cdot {\displaystyle \prod _{d\mid n,\omega (d)\text{ 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|$,

$\log |{\mathrm{\Phi }}_n(e(1/5))|$ $={\displaystyle \sum _{r=0}^{\nu }}\left({\displaystyle \genfrac{}{}{0pt}{}{2\nu +1}{2r}}\right)\log A+{\displaystyle \sum _{r=0}^{\nu }}\left({\displaystyle \genfrac{}{}{0pt}{}{2\nu +1}{2r+1}}\right)\log B$

$=2^{2\nu }\log A+2^{2\nu }\log B$

$=\log ({(AB)}^{2^{\omega (n)}/2}),$

and using $d(n)={\sum }_{r=0}^{\omega (n)}\left(\genfrac{}{}{0pt}{}{\omega (n)}{r}\right)=2^{\omega (n)}$ this is $|{\mathrm{\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 ${\mathrm{\Phi }}_n$ [44, p. 13, Lemma 2.9]. We remind ourselves that ${\mathrm{\Phi }}_n\in \mathbb{Z}[x]$ (Theorem 7), and so ${\mathrm{\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 {\mathrm{\Phi }}_n(a)$ if and only if $n$ is the multiplicative order of $a$ modulo $p$.

Proof.

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

$$b^n-1={\mathrm{\Phi }}_n(b){\mathrm{\Phi }}_{d_0}(b)\cdot \prod _{d\mid n,d\ne d_0,n}{\mathrm{\Phi }}_d(b).$$

Applying the above with $b=a$ yields $a^n-1\equiv 0(mod{p}^2)$. Moreover, by the binomial theorem, ${\mathrm{\Phi }}_n(a+p)\equiv {\mathrm{\Phi }}_n(a)\equiv 0(modp)$ and ${\mathrm{\Phi }}_{d_0}(a+p)\equiv {\mathrm{\Phi }}_{d_0}(a)\equiv 0(modp)$, so applying the above with $b=a+p$ yields ${(a+p)}^n-1\equiv 0(mod{p}^2)$. But by the binomial theorem, ${(a+p)}^n-1={\sum }_{j=0}^n\left(\genfrac{}{}{0pt}{}{n}{j}\right)a^{n-j}{p}^j-1$, whence ${(a+p)}^n-1\equiv a^n+n{a}^{n-1}p-1(mod{p}^2)$, hence $a^n+n{a}^{n-1}p-1\equiv 0(mod{p}^2)$. Together with $a^n-1\equiv 0(mod{p}^2)$ this yields $n{a}^{n-1}p\equiv 0(mod{p}^2)$, i.e. $n{a}^{n-1}\equiv 0(modp)$, contradicting that $p\nmid n,a$. Therefore $\nu =n$.

Suppose that $a^n\equiv 1(modp)$ and that $a^{\nu }\not\equiv 1(modp)$ for . As ${\prod }_{d\mid n}{\mathrm{\Phi }}_d(a)=a^n-1\equiv 0(modp)$, there is some $d_0\mid n$ for which ${\mathrm{\Phi }}_{d_0}(a)\equiv 0(modp)$. Suppose by contradiction that . As $d_0\mid n$,

contradicting that $a^{\nu }\not\equiv 1(modp)$ for . Therefore ${\mathrm{\Phi }}_n(a)\equiv 0(modp)$, i.e. $p\mid {\mathrm{\Phi }}_n(a)$. ∎

Lemma 13.

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

Proof.

Suppose that $a\in \mathbb{Z}$ and $p\mid {\mathrm{\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(modn)$.

Suppose that $p\equiv 1(modn)$, 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 {\mathrm{\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\ge 1$, there are infinitely many primes $p$ with $p\equiv 1(modn)$.

Proof.

The claim for $n=1$ follows from the claim for $n=2$. For $n\ge 2$, by Lemma 8, ${\mathrm{\Phi }}_n(0)=1$, namely the constant coefficient of ${\mathrm{\Phi }}_n(x)$ is $1$. Suppose by contradiction that there are at most finitely many such primes $p_1,\mathrm{\dots },p_t$ and let $M=n{p}_1\mathrm{\cdots }{p}_t$. For $N\in \mathbb{Z}$, ${\mathrm{\Phi }}_n(NM)\equiv 1(modM)$ and from $M\mid ({\mathrm{\Phi }}_n(NM)-1)$ it follows that $p_i\mid ({\mathrm{\Phi }}_n(NM)-1)$, $1\le i\le t$, and $n\mid ({\mathrm{\Phi }}_n(NM)-1)$. Hence if $p$ is a prime factor of ${\mathrm{\Phi }}_n(NM)$ then $p\ne p_i$, $1\le i\le t$, and $p\nmid n$. As ${\mathrm{\Phi }}_n$ is a monic polynomial that is not a constant, for all sufficiently large $N$, ${\mathrm{\Phi }}_n(NM)$ is an integer $\ge 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(modn)$. But we have also established that $p\ne p_i$, $1\le i\le r$, a contradiction. Therefore there are infinitely many primes $p$ with $p\equiv 1(modn)$. ∎

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

$$\frac{1}{2}\cdot b^{\varphi (n)}\le {\mathrm{\Phi }}_n(b)\le 2\cdot b^{\varphi (n)}.$$

Using this, Thangadurai and Vatwani [42] prove that for $n\ge 2$, the least prime $p\equiv 1(modn)$ satisfies

$$p\le 2^{\varphi (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\le j\le n,\gcd (n,j)=1}{e}^{2\pi ijk/n}=\sum _{\xi \in {\mathrm{\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

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 ,

$${\mathrm{\Phi }}_n(x)=\exp \left(-\sum _{m=1}^{\mathrm{\infty }}\frac{c_n(m)}{m}{x}^m\right).$$

Proof.

Using that $\xi \mapsto {\xi }^{-1}$ is a bijection ${\mathrm{\Delta }}_n\to {\mathrm{\Delta }}_n$,

${\displaystyle \frac{d}{dx}}\log {\mathrm{\Phi }}_n(x)$ $={\displaystyle \frac{d}{dx}}{\displaystyle \sum _{\xi \in {\mathrm{\Delta }}_n}}\log (x-\xi )$

$={\displaystyle \sum _{\xi \in {\mathrm{\Delta }}_n}}{\displaystyle \frac{1}{x-\xi }}$

$={\displaystyle \sum _{\xi \in {\mathrm{\Delta }}_n}}-{\displaystyle \frac{1}{\xi }}\cdot {\displaystyle \frac{1}{1-\frac{x}{\xi }}}$

$=-{\displaystyle \sum _{\xi \in {\mathrm{\Delta }}_n}}{\displaystyle \frac{1}{\xi }}{\displaystyle \sum _{m=0}^{\mathrm{\infty }}}{\left({\displaystyle \frac{x}{\xi }}\right)}^m$

$=-{\displaystyle \sum _{m=0}^{\mathrm{\infty }}}{x}^m{\displaystyle \sum _{\xi \in {\mathrm{\Delta }}_n}}{\xi }^{m+1}.$

Because $n>1$, ${\mathrm{\Phi }}_n(0)=1$, and integrating,

$${\mathrm{\Phi }}_n(x)=\exp \left(-\sum _{m=0}^{\mathrm{\infty }}\frac{x^{m+1}}{m+1}\sum _{\xi \in {\mathrm{\Delta }}_n}{\xi }^{m+1}\right)=\exp \left(-\sum _{m=1}^{\mathrm{\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 \varphi (n)}{\varphi (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\ge 1$ and $\mathrm{Re}s>1$,

$$\sum _{k=1}^{\mathrm{\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}^{\mathrm{\infty }}}{c}_n(k)k^{-s}$ $={\displaystyle \sum _{k=1}^{\mathrm{\infty }}}{k}^{-s}{\displaystyle \sum _{d\mid n,d\mid k}}\mu (n/d)d$

$={\displaystyle \sum _{d\mid n}}{\displaystyle \sum _{m=1}^{\mathrm{\infty }}}{(md)}^{-s}\mu (n/d)d$

$={\displaystyle \sum _{d\mid n}}{\displaystyle \sum _{m=1}^{\mathrm{\infty }}}{m}^{-s}{d}^{-s}\mu (n/d)d$

$={\displaystyle \sum _{m=1}^{\mathrm{\infty }}}{m}^{-s}{\displaystyle \sum _{d\mid n}}{d}^{-s}\mu (n/d)d$

$=\zeta (s)\cdot {\displaystyle \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\ge 1$,

$$p_k=\sum _{j=1}^n{\alpha }_j^k.$$

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

$$p_k=\sum _{j=1}^{k-1}{(-1)}^{j-1}{s}_j{p}_{k-j}+{(-1)}^{k-1}k{s}_k.$$ (3)

Write

$${\mathrm{\Phi }}_n(x)=\sum _{k=0}^{\varphi (n)}{a}_n(k)x^k.$$

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

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

$${\mathrm{\Phi }}_n(x)=\prod _{1\le k\le n,\gcd (n,k)=1}(x-e^{2\pi ik/n})=x^{-n+\varphi (n)}\prod _{j=1}^n(x-{\alpha }_j)$$

for ${\alpha }_j={\chi }_1(j)e^{2\pi ij/n}$, and thus

$$x^{n-\varphi (n)}{\mathrm{\Phi }}_n(x)=\prod _{j=1}^n(x-{\alpha }_j).$$

Because ${\chi }_1{(j)}^k={\chi }_1(j)$ for $k\ge 1$,

$$p_k=\sum _{j=1}^n{\alpha }_j^k=\sum _{j=1}^n{\chi }_1(j)e^{2\pi ijk/n}=\sum _{1\le j\le n,\gcd (n,j)=1}{e}^{2\pi ijk/n}=c_n(k).$$

Now, from

$$x^{n-\varphi (n)}\sum _{k=1}^{\varphi (n)}{a}_n(k)x^k=\sum _{k=0}^n{(-1)}^k{s}_k{x}^{n-k}$$

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

$${(-1)}^k{s}_k=a_n(\varphi (n)-k).$$

In fact by Lemma 20, $a_n(\varphi (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\ge 1$ and $k\ge 1$,

$$k{a}_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\le j\le 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\le j\le 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\le a\le n,\chi (a)=1}(x-e^{2\pi ia/n})=\sum _j{\alpha }_n(j)x^j$$

and

$$B_n(x)=\prod _{1\le b\le n,\chi (b)=-1}(x-e^{2\pi ib/n})=\sum _j{\beta }_n(j)x^j,$$

and write

$$S_n(k)=\sum _{1\le a\le n,\chi (a)=1}{e}^{2\pi ika/n},T_n(k)=\sum _{1\le b\le n,\chi (b)=-1}{e}^{2\pi ikb/n}.$$

Then

$${\mathrm{\Phi }}_n(x)=A_n(x)B_n(x),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\le j\le n}\chi (j)e^{2\pi ikj/n}=\chi (k)\sqrt{n^{*}},$$

hence

$$2S_n(k)=c_n(k)+\chi (k)\sqrt{n^{*}},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\ge 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 {𝒪}_{\mathbb{Q}(\sqrt{n^{*}})}$. If $D$ is a square-free, it is a fact [16, p. 698, §15.3] that ${𝒪}_{\mathbb{Q}(\sqrt{D})}=\mathbb{Z}[\omega ]$ for

and $n^{*}={(-1)}^{(n-1)/2}n\equiv 1(mod4)$, we have ${𝒪}_{\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\ge 1$, we write

$${\mathrm{\Phi }}_n(x)=\sum _{k=0}^{\varphi (n)}{a}_n(k)x^k.$$

Let

$$A(n)=\underset{0\le k\le \varphi (n)}{\max }|a_n(k)|$$

and

$$S(n)=\sum _{k=0}^{\varphi (n)}|a_n(k)|.$$

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

Lemma 20.

For $n>1$ and for $0\le k\le \varphi (n)$,

$$a_n(\varphi (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\le j\le n$ is equivalent to $x^{n}P(x^{-1})=P(x)$. But because $n>1$, by Lemma 5 we have ${\mathrm{\Phi }}_n(x^{-1})=x^{-\varphi (n)}{\mathrm{\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 ,

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

Proof.

By Lemma 1,

${\mathrm{\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}}$

$=(1-x){\displaystyle \sum _{0\le \alpha \le p-1}}{x}^{\alpha q}\cdot {\displaystyle \sum _{\beta \ge 0}}{x}^{\beta p}$

$={\displaystyle \sum _{0\le \alpha \le p-1,\beta \ge 0}}{x}^{\alpha q+\beta p}-{\displaystyle \sum _{0\le \alpha \le p-1,\beta \ge 0}}{x}^{\alpha q+\beta p+1}$

$={\displaystyle \sum _{0\le \alpha \le p-1,\beta \ge 0,0\le \delta \le 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\le {\alpha }_1,{\alpha }_2\le p-1$ means $0\le |{\alpha }_1-{\alpha }_2|\le 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\le k\le \varphi (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 are primes. Then there are nonnegative integers $r,s$ such $(p-1)(q-1)=rp+sq$, and for $0\le k\le \varphi (pq)=(p-1)(q-1)$,

Furthermore,

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

and

$$|\{k:0\le k\le \varphi (pq),a_{pq}(k)=-1\}|=(p-s-1)(q-r-1).$$

Proof.

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

$$rp\equiv -p+1(modq).$$

If $r=q-1$ then we get from the above that $1\equiv 0(modq)$, which is false because $q\ne 1$, so in fact $0\le r\le 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}\ge \frac{-q+1}{q}>-1,$$

hence $s\ge 0$. Also, , so $s\le p-2$. We then have

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

For $\xi \in {\mathrm{\Delta }}_{pq}$, because ${\mathrm{\Phi }}_q({\xi }^p)=0$ and ${\mathrm{\Phi }}_p({\xi }^q)=0$,

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

(Because $0\le r\le q-2$ and $0\le s\le 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 {\mathrm{\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=\varphi (pq)$. The second product is a polynomial of degree

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

Therefore $f(x)$ is a monic polynomial of degree $\varphi (pq)$. Because each $\xi \in {\mathrm{\Delta }}_{pq}$ is a zero of $f(x)$ and $f(x)$ is monic, $f(x)={\mathrm{\Phi }}_{pq}(x)$. ∎

Carlitz [10] proves the following.

Theorem 23.

Let be primes, let

let $\theta (pq)$ be the number of terms of ${\mathrm{\Phi }}_{pq}$ with nonzero coefficients, and let ${\theta }_0(pq)$ be the number of terms of ${\mathrm{\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 are primes, $p$ is fixed, and $q,r$ are free.

Bang [2] proves the following.

Theorem 24 (Bang).

For odd primes ,

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

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

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

Bloom [6] proves the following.

Theorem 25 (Bloom).

For odd primes ,

$$A(pqrs)\le 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\ge 3$ there are primes , with $p_1+p_2>p_m$. For such primes,

$$a_{p_1{p}_2\mathrm{\cdots }{p}_m}(p_m)=-m+1.$$

Proof.

Write

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

For $m\ge 3$, suppose by contradiction that if are primes then $p_1+p_2\le p_m$, and thus . For $k\ge 1$, as there are infinitely many primes, let $p_1$ be the least prime $>k$, and let . Then

$$\pi (2k)-\pi (k)=\pi (2k)-\pi (p_1)+1\le \pi (2p_1)-\pi (p_1)+1\le (m-1)+1=m.$$

This yields, for $j\ge 1$,

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

But the prime number theorem tells us

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

with which we get a contradiction.

Let $m\ge 3$ be odd and let be primes satisfying $p_1+p_2>p_m$, and let $n=p_1{p}_2\mathrm{\cdots }{p}_m$. Since $p_1+p_2>p_m$, for $1\le j,k\le m$ we have $p_j+p_k\ge p_m+1$. It follows that if $d$ is a divisor of $n$ aside from $1$ and $p_1,\mathrm{\dots },p_m$, and $\mu (n/d)\ne 0$, then

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

Therefore

${\mathrm{\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)\ne 0}}{(x^d-1)}^{\mu (n/d)}+x^{p_m+1}\mathbb{Z}[x]$

$={(x-1)}^{-1}\cdot {\displaystyle \prod _{j=1}^m}{(x^{p_j}-1)}^{\mu (n/p_j)}+x^{p_m+1}\mathbb{Z}[x]$

$={(x-1)}^{-1}\cdot {\displaystyle \prod _{j=1}^m}(x^{p_j}-1)+x^{p_m+1}\mathbb{Z}[x]$

$={(x-1)}^{-1}\cdot (-1+x^{p_1}+\mathrm{\cdots }+x^{p_m})+x^{p_m+1}\mathbb{Z}[x].$

Now,

For $1\le i\le m$, there is one and only one $0\le j\le 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 such that $A(pqr)\ge M$. Lehmer proves this without the hypothesis that there are infinitely many twin primes.

For power series $A(x)={\sum }_{k=0}^{\mathrm{\infty }}{a}_k{x}^k$ and $B(x)={\sum }_{k=0}^{\mathrm{\infty }}{b}_k{x}^k$, write

$$A⪯B$$

if $|a_k|\le b_k$ for all $k$. For power series $A,B,P,Q$ with $A⪯P$ and $B⪯Q$,

$$|a_k+b_k|\le |a_k|+|b_k|\le p_k+q_k,$$

so $A+B⪯P+Q$, and

$$\left|\sum _{i+j=k}{a}_i{b}_j\right|\le \sum _{i+j=k}|a_i{b}_j|\le \sum _{i+j=k}{p}_i{q}_j,$$

so $AB⪯PQ$.

Now,

$$x^d-1⪯\sum _{k=0}^{\mathrm{\infty }}{x}^{kd},1⪯\sum _{k=0}^{\mathrm{\infty }}{x}^{kd},{(x^d-1)}^{-1}⪯\sum _{k=0}^{\mathrm{\infty }}{x}^{kd},$$

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

$${\mathrm{\Phi }}_n(x)=\prod _{d\mid n}{(x^d-1)}^{\mu (n/d)}⪯\prod _{d\mid n}\left(\sum _{k=0}^{\mathrm{\infty }}{x}^{kd}\right)=\prod _{d\mid n}\frac{1}{1-x^d}.$$ (5)

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

$${\mathrm{\Phi }}_n(x)⪯\prod _{j=1}^{\mathrm{\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 , 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 ,

$$\prod _{j=1}^{\mathrm{\infty }}\frac{1}{1-x^j}=\sum _{k=0}^{\mathrm{\infty }}p(k)x^k,$$

found by Euler.

Theorem 27.

$$|a_n(k)|\le p(k),$$

and so

$$A(n)=\underset{0\le k\le \varphi (n)}{\max }|a_n(k)|\le \underset{0\le k\le \varphi (n)}{\max }p(k)\le p(\varphi (n))\le 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),n\to \mathrm{\infty }.$$

This implies

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

Therefore,

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

Now let

$$Q_n(x)=\prod _{d|n}(1+x^d+x^{2d}+\mathrm{\cdots }+x^{n-d}).$$

It is straightforward that for , 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 ${\mathrm{\Phi }}_n(x)$ is , using (5) we get

$${\mathrm{\Phi }}_n(x)⪯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 ${\mathrm{\Phi }}_n(x)⪯Q_n(x)$ we have that $S(n)$ is $\le$ the sum of the coefficients of the polynomial $Q_n(x)$, i.e.

$$S(n)\le Q_n(1)=n^{d(n)/2}.$$

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

Theorem 28 (Bateman).

$$S(n)\le \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

$$\underset{n\to \mathrm{\infty }}{lim\; sup}\log d(n)\cdot \frac{\log \log n}{\log n}=\log 2.$$

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

$$\log d(n)\cdot \frac{\log \log n}{\log n}\le \log 2+ϵ,$$

so

$$\log d(n)\le \frac{\log n}{\log \log n}(ϵ+\log 2).$$

Then

$$\log S(n)\le \frac{d(n)}{2}\cdot \log n\le \frac{\log n}{2}\exp \left(\frac{\log n}{\log \log n}(ϵ+\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 ${\mathrm{\Psi }}_n(x)=\frac{x^n-1}{{\mathrm{\Phi }}_n(x)}$, i.e. , 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\le y,p\equiv 2,3(mod5)}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}^{\mathrm{\infty }}{c}_m{m}^{-s}=\prod _p\sum _{k=0}^{\mathrm{\infty }}{c}_{p^k}{p}^{-ks},\mathrm{Re}s>0$$

and

$$\sum _{m=1}^{\mathrm{\infty }}\chi (m)c_m{m}^{-s}=\prod _p\sum _{k=0}^{\mathrm{\infty }}\chi (p^k)c_{p^k}{p}^{-ks},\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}^{\mathrm{\infty }}{c}_{p^k}{p}^{-ks}=\frac{1-p^{-s}}{1-p^{-(s+1)}}$$

and for $p\nmid n$,

$$\sum _{k=0}^{\mathrm{\infty }}{c}_{p^k}{p}^{-ks}=\frac{1}{1-p^{-(s+1)}},$$

thus

$$\sum _{m=1}^{\mathrm{\infty }}{c}_m{m}^{-s}=\zeta (1+s)\prod _{p\mid n}(1-p^{-s}),\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}^{\mathrm{\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}^{\mathrm{\infty }}\chi (p^k)c_{p^k}{p}^{-ks}=\frac{1}{1-\chi (p)p^{-(s+1)}},$$

thus

$$\sum _{m=1}^{\mathrm{\infty }}\chi (m)c_m{m}^{-s}=L(1+s,\chi )\prod _{p\mid n}(1+p^{-s}),\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}^{\mathrm{\infty }}{c}_m{e}^{2\pi im/5}{e}^{-m/x}=\sum _{m=1}^{\mathrm{\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$,

For $x>0$, writing $f(x)=\mathrm{Re}{\sum }_{m=1}^{\mathrm{\infty }}{c}_m{e}^{2\pi im/5}{e}^{-m/x}$, one has for ,

$${\int }_0^{\mathrm{\infty }}f(x)x^{-\sigma -1}𝑑x\le \frac{1}{1-\sigma }+\frac{1}{\sigma }\underset{x\ge 1}{sup}f(x),$$

so

As $\sigma \to 0$ we have $\sigma \mathrm{\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

$$\underset{x\ge 1}{sup}f(x)\ge \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 ,

$$|{\mathrm{\Phi }}_n(z)|=\exp \left(\mathrm{Re}\sum _{m=1}^{\mathrm{\infty }}{c}_m{z}^m\right),$$

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

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

Theorem 29 (Vaughan).

If $n={\prod }_{p\le y,p\equiv 2,3(mod5)}p$ with $\omega (n)$ odd, then

$$|{\mathrm{\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 \underset{n\ge 1}{\max }|a_n(k)|\ge C{k}^{1/2}{(\log k)}^{-1/4}.$$

9 Fourier analysis

Let $𝕋=ℝ/\mathbb{Z}$. For $p\ge 1$, define

$${\parallel f\parallel }_{L^p}={\left({\int }_0^1{|f(x)|}^p𝑑x\right)}^{1/p}$$

and ${\parallel f\parallel }_{L^{\mathrm{\infty }}}={sup}_{x\in [0,1]}|f(x)|$. By Jensen’s inequality, if $1\le p\le q\le \mathrm{\infty }$ then

$${\parallel f\parallel }_{L^p}\le {\parallel f\parallel }_{L^q}.$$

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

$$\widehat{f}(k)={\int }_0^1{e}^{-2\pi ikx}f(x)𝑑x.$$

Define

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

and ${\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^{\mathrm{\infty }}}={sup}_{k\in \mathbb{Z}}|\widehat{f}(k)|$. For $1\le p\le q\le \mathrm{\infty }$,

$${\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^q}\le {\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^p}.$$

Plancherel’s theorem tells us that

$${\parallel f\parallel }_{L^2}={\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^2}.$$

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

$${\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^q}\le {\parallel f\parallel }_{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 and for $r\ge \frac{p}{2}$ an integer,

$${\parallel f\parallel }_{L^q}\le {(2nr+1)}^{\frac{1}{p}-\frac{1}{q}}{\parallel f\parallel }_{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\le p\le q\le \mathrm{\infty }$,

$${\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^p}\le {(2n+1)}^{\frac{1}{p}-\frac{1}{q}}{\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^q}.$$

For $f:𝕋\to ℂ$, define

$${\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^0}=|\mathrm{supp}\widehat{f}|=\left|\{n\in \mathbb{Z}:\widehat{f}(n)\ne 0\}\right|.$$

McGehee, Pigno and Smith [33] prove that there is some $K$ such that for all $N$, if $n_1,\mathrm{\dots },n_N$ are distinct integers and $c_1,\mathrm{\dots },c_N\in ℂ$ satisfy $|c_k|\ge 1$, then

$${\parallel \sum _{k=1}^N{c}_k{e}^{2\pi i{n}_{k}t}\parallel }_{L^1}\ge K\log N.$$

That is, if $f:𝕋\to ℂ$ is a trigonometric polynomial with $|\widehat{f}(n)|\ge 1$ when $\widehat{f}(n)\ne 0$, then

$${\parallel f\parallel }_{L^1}\ge K\log {\parallel \widehat{f}\parallel }_{{\mathrm{\ell }}^0}.$$

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

$$\widehat{F}(k)=\frac{1}{N}\sum _{j=0}^{N-1}F(j)e^{-2\pi ijk/N},0\le k\le 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},0\le j\le 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,\mathrm{\dots },a_{N-1}\in ℂ$, define $f:𝕋\to ℂ$ by

$$f(x)=\sum _{k=0}^{N-1}{a}_k{e}^{2\pi ikx}$$

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

$$F(j)=f(j/N)=\sum _{k=0}^{N-1}{a}_k{e}^{2\pi ikj/N},0\le j\le N-1,$$

for which we calculate $\widehat{F}(k)=a_k$, for $0\le k\le 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]