1. Dirichlet's Theorem: Preliminary Results
The main theorem of this unit will be the following:
Theorem
If \(d\) and \(r\) are relatively prime positive integers, then there are infinitely many primes \(p\) with \(p = q d + r\) for some integer \(q\) (i.e., infinitely many primes congruent to \(r\) modulo \(d\)).
The proof of the theorem will use quite a substantial portion of the tools that we have developed over the course of the year. It will be assumed that you are familiar with a number of basic facts about prime numbers. Perhaps the most sophisticated result we will take for grated is that every natural number \(N\) has a unique prime factorization \(N = p_1^{\ell_1} \cdots p_{n}^{\ell_n}\) where each exponent \(\ell_j\) is a nonnegative integer and the \(p_1,\ldots,p_n\) are distinct primes.
1.1. Factorization of the Riemann Zeta Function
Definition
The Riemann Zeta Function \(\zeta(s)\) is defined to equal
\[ \zeta(s) := \sum_{n=1}^\infty \frac{1}{n^s}\]
for each real \(s > 1\).
We know that the series does indeed converge when \(s > 1\) because it's simply a \(p\)-series. The Zeta function is intimately connected to the prime numbers. One particularly important way that this can be seen is through the following factorization theorem:
Theorem (Zeta Function Factorization)
For each \(s > 1\),
\[ \zeta(s) = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}. \]
By the product over primes, we mean
\[ \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}} := \lim_{N \rightarrow \infty} \prod_{\substack{p \text{ prime} \\ p \leq N}} \frac{1}{1 - p^{-s}}. \]
The proof of the Zeta function factorization is a consequence of the following lemma:
Lemma
For any positive integers \(K\) and \(N\), let \(p_1,\ldots,p_n\) be the prime numbers less than or equal to \(N\). Then for any \(s > 1\),
\[{}\prod_{\substack{p \text{ prime} \\ p \leq N}} \sum_{\ell=0}^K \frac{1}{(p^{\ell})^s}{}\]
\[{}= \sum_{\ell_1=0}^K \cdots \sum_{\ell_n=0}^K \frac{1}{(p_1^{\ell_1} \cdots p_n^{\ell_n})^s}{}\]
\[{}\leq \sum_{n=1}^\infty \frac{1}{n^s}.{}\]
Proof
The equality is simply a consequence of the distributive property; more precisely, it is easily proved by induction on the number of primes by summing the innermost sum, i.e.,
\[{}\sum_{\ell_1=0}^K \cdots \sum_{\ell_n=0}^K \frac{1}{(p_1^{\ell_1} \cdots p_n^{\ell_n})^s}{}\]
\[{}= \sum_{\ell_1=0}^K \cdots \sum_{\ell_{n-1}=0}^K \frac{1}{(p_1^{\ell_1} \cdots p_{n-1}^{\ell_{n-1}})^s}{}\]
\[{}\cdot \left( \sum_{\ell_n=0}^K \frac{1}{p_n^{\ell_ns}} \right){}\]
\[{}= \left( \sum_{\ell_1=0}^K \cdots \sum_{\ell_{n-1}=0}^K \frac{1}{(p_1^{\ell_1} \cdots p_{n-1}^{\ell_{n-1}})^s} \right){}\]
\[{}\cdot \left( \sum_{\ell_n=0}^K \frac{1}{p_n^{\ell_ns}} \right){}\]
\[{}= \left(\prod_{\substack{p \text{ prime} \\ p \leq p_{n}-1}} \sum_{\ell=0}^K \frac{1}{(p^{\ell})^s} \right){}\]
\[{}\cdot \left( \sum_{\ell_n=0}^K \frac{1}{p_n^{\ell_ns}} \right){}\]
\[{}= \prod_{\substack{p \text{ prime} \\ p \leq p_{n}}} \sum_{\ell=0}^K \frac{1}{(p^{\ell})^s}{}\]
\[{}= \prod_{\substack{p \text{ prime} \\ p \leq N}} \sum_{\ell=0}^K \frac{1}{(p^{\ell})^s},{}\]
where the last equality follows simply because there can be no more primes between \(p_n\) and \(N\).
To get the inequality, we use unique factorization: the map \((\ell_1,\ldots,\ell_n) \mapsto p_1^{\ell_1} \cdots p_n^{\ell_n}\) is injective because the prime factorization is unique. Thus if we let \(S_{N,K}\) be the set of natural numbers whose prime factorization involves only primes less than or equal to \(N\) with exponents \(\leq K\), it must be the case that
\[ \sum_{\ell_1=0}^K \cdots \sum_{\ell_n=0}^K \frac{1}{(p_1^{\ell_1} \cdots p_n^{\ell_n})^s} = \sum_{n \in S_{N,K}} \frac{1}{n^s}. \]
Because the terms are all nonnegative, if \(M\) is the largest element of \(S_{N,K}\), then
\[ \sum_{n \in S_{N,K}} \frac{1}{n^s} \leq \sum_{n=1}^M \frac{1}{n^s}, \]
and then the proof of the lemma follows by observing that the partial sums of a nonnegative series are dominated by the sum of the series.
Corollary 1
For any natural number \(N\) and any \(s > 1\),
\[ \prod_{\substack{p \text{ prime} \\ p \leq N}} \frac{1}{1-p^{-s}} \leq \sum_{n=1}^\infty \frac{1}{n^s}. \]
Proof
For each prime \(p\), since \(p > 1\), for any \(s > 0\) it must be the case that
\[ \frac{1}{1-p^{-s}} = \sum_{\ell=0}^\infty \frac{1}{(p^\ell)^s}, \]
and, in particular, the infinite series on the right-hand side must converge. Thus the corollary follows by fixing \(N\) and letting \(K \rightarrow \infty\) in the lemma above.
Corollary 2
For any natural number \(N\) and any \(s > 1\),
\[ \prod_{\substack{p \text{ prime} \\ p \leq N}} \frac{1}{1-p^{-s}} \geq \sum_{n=1}^N \frac{1}{n^s}. \]
Proof
We certainly must have
\[ \prod_{\substack{p \text{ prime} \\ p \leq N}} \sum_{\ell=0}^K \frac{1}{(p^{\ell})^s} \leq \prod_{\substack{p \text{ prime} \\ p \leq N}} \frac{1}{1-p^{-s}}\]
for each \(N\) and \(S\). By the Lemma, the product on the left-hand side is equal to the sum of \(n^{-s}\) as \(n\) ranges over natural numbers whose prime factorization involves primes less than \(N\) with powers less than \(K\). Fixing \(K = N\), because \(p^{\ell} \geq 2^{\ell} \geq \ell\) for any prime \(p\), every number \(n \leq N\) must itself have a prime factorization involving only primes less than or equal to \(N\) with powers less than or equal to \(N\), so \(\{1,\ldots,N\} \subset S_{N,N}\).
Proof (Proof of Zeta Function Factorization)
\[ \sum_{n=1}^N \frac{1}{n^s} \leq \prod_{\substack{p \text{ prime} \\ p \leq N}} \frac{1}{1-p^{-s}} \leq \sum_{n=1}^{\infty} \frac{1}{n^s}\]
and the left-hand side tends to the right-hand side as \(N \rightarrow \infty\), the product in the middle converges as \(N \rightarrow \infty\) and in the limit, all three “sides” must be equal.
2. A Theorem About the Primes
A sample of the kind of arguments we will use to prove Dirichlet's Theorem is the following result.
Theorem
\[ \sum_{p \text{ prime}} \frac{1}{p} = \infty. \]
Step 1 (Compare the Product to an Exponentiated Sum)
We have seen before that \(1 + x \leq e^x\) for all \(x \in {\mathbb R}\) by convexity of the exponential function. Fixing \(x = 1/(1-p^{-s}) - 1 = p^{-s}/(1-p^{-s})\) gives that
\[ \frac{1}{1-p^{-s}} \leq e^{\frac{p^{-s}}{1-p^{-s}}}\]
and so
\[ \prod_{\substack{p \text{ prime} \\ p \leq N}}\frac{1}{1-p^{-s}} \leq \exp \left( \sum_{\substack{p \text{ prime} \\ p \leq N}}\frac{p^{-s}}{1-p^{-s}} \right). \]
Letting \(N \rightarrow \infty\) gives that
\[ \zeta(s) \leq \exp \left( \sum_{\substack{p \text{ prime}}}\frac{p^{-s}}{1-p^{-s}} \right)\]
for each \(s > 1\).
Step 2 (Estimate the Zeta Function)
By the Integral Test,
\[ \zeta(s) \geq \int_1^\infty \frac{dx}{x^s} = \frac{1}{s-1}. \]
This means
\[ \ln \frac{1}{s-1} \leq \sum_{\substack{p \text{ prime}}}\frac{p^{-s}}{1-p^{-s}}\]
for each \(s > 1\).
Step 3 (Finishing the Proof)
When \(p\) is prime and \(s > 1\), \(p^{-s} \leq p^{-1} \leq 1/2\), so \(1-p^{-s} \geq 1/2\) and so
\[{}\ln \frac{1}{s-1}{}\]
\[{}\leq \sum_{\substack{p \text{ prime}}}\frac{p^{-s}}{1-p^{-s}}{}\]
\[{}\leq 2 \sum_{\substack{p \text{ prime}}} \frac{1}{p^s}{}\]
\[{}\leq 2 \sum_{p \text{ prime}} \frac{1}{p}.{}\]
Since \(\ln (s-1)^{-1} \rightarrow \infty\) as \(s \rightarrow 1^+\), the sum of \(1/p\) over all primes \(p\) cannot possibly be finite.