Dirichlet’s Theorem for arithmetic progressions with difference 4

From antiquity, Euclid’s Theorem asserts that the number of primes is infinite. Since all primes except $2$ are odd, a re-phrasement of Euclid’s theorem is that the set of odd integers $\{2k+1\}_{k\in\mathbb{Z}}$ contains an infinite number of primes. A natural generalization, proved by Dirichlet, is that every arithmetic progression of the form $\{qk+\ell\}_{k\in\mathbb{Z}}$ contains an infinite number of primes, provided that $q$ and $k$ are relatively prime.

(Dirichlet’s Theorem) If $(q,\ell)=1$ , then the arithmetic progression $\{qk+\ell\}_{k\in\mathbb{Z}}$ contains infinitely many primes, where $(q, \ell)$ denotes the greatest common divisor of $q$ and $\ell$ .

The proof is one of the first application of Fourier analysis on finite abelian groups. Here in this post, we prove Dirichlet’s theorem when $q=4$ , i.e., both the arithmetic progressions $\{4k+1\}_{k\in\mathbb{Z}}$ and $\{4k+3\}_{k\in\mathbb{Z}}$ contain an infinite number of primes. The restriction to $q=4$ highlights the main structure of Dirichlet’s proof without needing as much background from number theory.

Before jumping directly into the proof, let us first discuss some number-theoretic background and the high-level strategy. First recall Euclid’s argument. For the sake of contradiction, there are exactly $N$ primes $p_{1},\ldots,p_{N}$ of the $2k+1$ . Then the number $M:=2\prod_{i=1}^{N}p_{i}+1$ is larger than every $p_{i}$ and cannot be a prime of the form $2k+1$ . On the other hand, from the Fundamental Theorem of Arithmetic, $M$ is the product of primes, and one of them must be congruent to $1 \Mod 2$ since $M$ itself is. So some $p_{i}$ must divide both $M$ and and $2\prod_{i=1}^{N}p_{i}$ , implying that $p$ divides $1=M-2\prod_{i=1}^{N}p_{i}$ , a contradiction. One can easily verify that this argument can be adapted to $\{4k+3\}_{k\in\mathbb{Z}}$ by taking $M=4\prod_{i=1}^{N}p_{i}+3$ . However, the argument breaks down when applied to the arithmetic progression $\{4k+1\}_{k\in\mathbb{Z}}$ . The reason is that the number $4\prod_{i=1}^{N}p_{i}+1$ is no longer guaranteed to have a prime divisor of the form $4k+1$ .

Instead, Euler’s analytic proof of Euclid’s Theorem provides the proper framework to extend the infinitude of primes to arithmetic progressions, where the zeta function $\zeta(s)=\sum_{n=1}^{\infty}\frac{1}{n^{s}}$ can be written as the product of geometric series of primes:

(Euler-Dirichlet Product Formula) For every $s>1$ ,

$\sum_{n=1}^{\infty}\frac{1}{n^{s}}=\prod_{p}\frac{1}{1-\frac{1}{p^{s}}}.$

Furthermore, if $f:\mathbb{Z}\rightarrow \mathbb{R}$ is multiplicative, i.e., $f(xy)=f(x)f(y)$ , then

$\sum_{n=1}^{\infty}\frac{f(n)}{n^{s}}=\prod_{p}\frac{1}{1-\frac{f(p)}{p^{s}}}.$

(A note on notation: $p$ always denotes a prime, and $\sum_{p}$ and $\prod_{p}$ range over all primes.) The identity can be viewed as an analytic version of the Fundamental Theorem of Arithmetic: every positive integer is the product of some prime powers, and the expression $1/(1-p^{-s})$ is a geometric series. Since $\zeta(1)$ diverges, The Product Formula also implies that the number of primes is infinite. With additional calculation, Euler proved the stronger form of Euclid’s Theorem:

$\sum_{p}\frac{1}{p^{s}}\rightarrow\infty \text{ as } s\rightarrow1^{+}.$

Now to prove Dirichlet’s Theorem, we will show that the sum $\sum_{p}\frac{D(p)}{p^{s}}\rightarrow\infty$ as $s\rightarrow1^{+}$ , where $D_{\ell}$ is the indicator function on $\mathbb{Z}$ for being congruent to $\ell \Mod q$ . By Fourier analysis, $\sum_{p}\frac{D_{\ell}(p)}{p^{s}}$ can be decomposed into two sums. Roughly, the first corresponds to the zeroth Fourier coefficient of $D_{\ell}$ and evaluates to $\sum_{p}\frac{1}{p^{s}}$ , which diverges as $s\rightarrow1^{+}$ , and the second sum corresponds to the non-zero Fourier coefficients and is always bounded. In our writeup, the advantage of restricting to $q=4$ is that the estimate of the second sum becomes significantly simpler, without further tools from number theory.

(Proof of Dirichlet’s Theorem restricted to $q=4$ .) Let $G:=\mathbb{Z}_{4}^{*}$ be the multiplicative group of integers modulo $4$ , and $\delta_{\ell}:G\rightarrow\{0,1\}$ be the indicator function such that $\delta_{\ell}(x)=1$ if $x\equiv\ell\Mod 4$ and $0$ otherwise. Then by Fourier expansion,
for every $n\in G$ ,

$\begin{eqnarray*} \delta_{\ell}(n) & = & \sum_{e\in\hat{G}}\hat{\delta_{\ell}}(e)e(n),\\ & = & \frac{1}{|\hat{G}|}\sum_{e\in\hat{G}}\overline{e(\ell)}e(n), \end{eqnarray*}$

where $e$ ranges over all characters of the dual group of $G$ . Since $G$ is a finite abelian group, it is is also isomorphic to its dual, and with $|G|=2$ , we can conclude that the only characters of $\hat{G}$ are: the trivial character $e_{0}$ that is identically $1$ , and the character $e_{1}$ where $e_{1}(x)=1$ if
$x\equiv1\Mod 4$ and $-1$ if $x\equiv3\Mod 4$ . Thus, we can simplify and rewrite $\delta_{\ell}$ as

$\begin{eqnarray*} \delta_{\ell}(n) & = & \frac{1}{2}\left(\overline{e_{0}(\ell)}e_{0}(n)+\overline{e_{1}(\ell)}e_{1}(n)\right)\\ & = & \frac{1}{2}\left(e_{0}(n)+e_{1}(\ell)e_{1}(n)\right). \end{eqnarray*}$

(For sanity check, one can easily verify via direct computation, without Fourier analysis, that the identities $\delta_{1}(n)=\frac{1+e_{1}(n)}{2}$ and $\delta_{3}(n)=\frac{1-e_{1}(n)}{2}$ hold.) For the rest of this proof, we will rely on the the fact that the characters $e_{0}$ and $e_{1}$ are real-valued.

To prove the theorem, we have to sum over all integers instead of just the multiplicative subgroup of $\mathbb{Z}_{4}^{*}$ . To this end, for every character $e\in\hat{G}$ , we define its Dirichlet character $\chi$ to be the extension to all of $\mathbb{Z}$ as follows: $\chi(n)=e(n)$ if $(n,4)=1$ and $0$ otherwise. Let $D_{\ell}:\mathbb{Z}\rightarrow\{0,1\}$ be the indicator function of being congruent to $\ell \Mod 4$ . Then it is easy to see that

$D_{\ell}(n)=\frac{1}{2}\left(\chi_{0}(n)+\chi_{1}(\ell)\chi_{1}(n)\right),$

where $\chi_{0},\chi_{1}$ are the Dirichlet characters of $e_{0},e_{1}$ , respectively. Since we can express the indicator function $D_{\ell}$ in terms of Dirichlet characters, we have

$\begin{eqnarray*} \sum_{p\equiv\ell\Mod 4}\frac{1}{p^{s}} & = & \sum_{p}\frac{D_{\ell}(p)}{p^{s}}\\ & = & \frac{1}{2}\sum_{p}\frac{\chi_{0}(p)}{p^{s}}+\frac{\chi_{1}(\ell)}{2}\sum_{p}\frac{\chi_{1}(p)}{p^{s}}. \end{eqnarray*}$

It suffices to prove that $\sum_{p\equiv\ell\Mod 4}\frac{1}{p^{s}} \rightarrow \infty$ as $s\rightarrow1^{+}$ . In particular, we will show that

$\sum_{p}\frac{\chi_{0}(p)}{p^{s}} \rightarrow \infty$ as $s\rightarrow1^{+}$ , which coincides with Euler’s argument since $\chi_{0}(p)=1$ for all $p > 2$ , and
$\sum_{p}\frac{\chi_{1}(p)}{p^{s}}=O(1)$ .

To estimate these sums, we prove the following:

Let $\chi$ be a Dirichlet character for $G$ . Then $\sum_{p}\frac{\chi(p)}{p^{s}}=\log(L(s,\chi))+O(1)$ , where $L(s,\chi)=\sum_{n=1}^{\infty}\frac{\chi(n)}{n^{s}}$ .

(of Proposition) Since $\chi$ is multiplicative, from the Euler-Dirichlet Product Formula,

$L(s,\chi)=\prod_{p}\frac{1}{1-\frac{\chi(p)}{p^{s}}}.$

Since $\chi$ is real-valued, taking log of both sides, we have

$\begin{eqnarray*} \log(L(s,\chi)) & = & \sum_{p}-\log\left(1-\frac{\chi(p)}{p^{s}}\right)\\ & = & \sum_{p}\frac{\chi(p)}{p^{s}}+O\left(\frac{\chi(p)^{2}}{2p^{2s}}\right)\\ & = & \sum_{p}\frac{\chi(p)}{p^{s}}+O(1), \end{eqnarray*}$

where the second line follows from the estimate of the power series $\log(1-x)=\sum_{n=1}^{\infty}x^{n}/n=x+O(x^{2})$ when $|x|<1$ , and the third from the fact that $\sum_{n}\frac{1}{n^{2}}$ converges.

Now we estimate the two sums using the above proposition. For the trivial Dirichlet character $\chi_{0}$ , we have

$\begin{eqnarray*} \sum_{p}\frac{\chi_{0}(p)}{p^{s}} & = & \log\left(\sum_{n=1}^{\infty}\frac{\chi_{0}(n)}{n^{s}}\right)+O(1)\\ & = & \log\left((1-\frac{1}{2^{s}})\sum_{n=1}^{\infty}\frac{1}{n^{s}}\right)+O(1)\\ & = & \log\left(\sum_{n=1}^{\infty}\frac{1}{n^{s}}\right)+O(1), \end{eqnarray*}$

which diverges as $s\rightarrow1^{+}$ since $\sum_{n}\frac{1}{n^{s}}$ diverges as $s\rightarrow1^{+}$ .

For the non-trivial character $\chi_{1}$ , $\sum_{n}\frac{\chi_{1}(n)}{n}$ is simply the alternating series $1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\dots$ , which converges to a positive number. Thus,

$\begin{eqnarray*} \sum_{p}\frac{\chi_{1}(p)}{p^{s}} & = & \log\left(\sum_{n=1}^{\infty}\frac{\chi_{1}(n)}{n^{s}}\right)+O(1)\\ & \leq & \log\left(\sum_{n=1}^{\infty}\frac{\chi_{1}(n)}{n}\right)+O(1)\\ & = & O(1), \end{eqnarray*}$

completing the proof.

Most steps in the preceding proof can be easily extended to an arbitrary $q$ . The Euler-Dirichlet Product Formula works for a multiplicative function taking values in $\mathbb{C}$ . The Fourier expansion of $D_{\ell}$ works as before. The Proposition $\sum_{p}\frac{\chi(p)}{p^{s}}=\log(L(s,\chi))+O(1)$ still holds, but extra care has to be taken since the $L$ -function is now complex-valued. The sum $\sum_{p}\frac{\chi_{0}(p)}{p^{s}}$ diverges, but for a non-trivial Dirichlet character $\chi$ , the fact that the sum $\sum_{p}\frac{\chi(p)}{p^{s}}$ is bounded is significantly more involved. See for instance Apostol or Stein-Shakarchi for further details.

We finish by observing that the proof above has a quantitative form.

(Quantitative version of Dirichlet’s Theorem) For every $s > 1$ ,

$\sum_{p\equiv\ell\Mod 4}\frac{1}{p^{s}}=\frac{1}{2}\log\frac{1}{s-1}+O(1).$

In general, for an arbitrary $q$ , the expression $\frac{1}{2}\log\frac{1}{s-1}$ is replaced by $\frac{1}{|\mathbb{Z}_q^*|}\log\frac{1}{s-1}$ , with $|\mathbb{Z}_q^*|=\phi(q)$ , where $\phi$ is the Euler totient function.

Proof proceeds the same as before, where we showed that

$\sum_{p\equiv\ell\Mod 4}\frac{1}{p^{s}}=\frac{1}{2}\sum_{p}\frac{\chi_{0}(p)}{p^{s}}+\frac{\chi_{1}(\ell)}{2}\sum_{p}\frac{\chi_{1}(p)}{p^{s}},$

with $\sum_{p}\frac{\chi_{0}(p)}{p^{s}}=\log\left(\sum_{n=1}^{\infty}\frac{1}{n^{s}}\right)+O(1)$ and $\sum_{p}\frac{\chi_{1}(p)}{p^{s}}=O(1)$ . Previously, we simply noted that $\sum_{n=1}^{\infty}\frac{1}{n^{s}}$ diverges as $s\rightarrow1^{+}$ . To finish the proof, it suffices to note that

$\begin{eqnarray*} \sum_{n=1}^{\infty}\frac{1}{n^{s}} & \leq & \sum_{n=1}^{\infty}\frac{1}{(n+1)^{s}}+O(1)\\ & \leq & \int_{1}^{\infty}\frac{1}{x^{s}}+O(1)\\ & = & \frac{1}{s-1}+O(1). \end{eqnarray*}$

Victor Chen

mathematics blog

Dirichlet’s Theorem for arithmetic progressions with difference 4

Leave a Reply Cancel reply