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*}

Leave a Reply

Your email address will not be published. Required fields are marked *