# 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 are odd, a re-phrasement of Euclid’s theorem is that the set of odd integers contains an infinite number of primes. A natural generalization, proved by Dirichlet, is that every arithmetic progression of the form contains an infinite number of primes, provided that and are relatively prime.

(Dirichlet’s Theorem) If , then the arithmetic progression contains infinitely many primes, where denotes the greatest common divisor of and .

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 , i.e., both the arithmetic progressions and contain an infinite number of primes. The restriction to 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 primes of the . Then the number is larger than every and cannot be a prime of the form . On the other hand, from the Fundamental Theorem of Arithmetic, is the product of primes, and one of them must be congruent to since itself is. So some must divide both and and , implying that divides , a contradiction. One can easily verify that this argument can be adapted to by taking . However, the argument breaks down when applied to the arithmetic progression . The reason is that the number is no longer guaranteed to have a prime divisor of the form .

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 can be written as the product of geometric series of primes:

(Euler-Dirichlet Product Formula) For every ,

Furthermore, if is multiplicative, i.e., , then

(A note on notation: always denotes a prime, and and 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 is a geometric series. Since 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:

Now to prove Dirichlet’s Theorem, we will show that the sum as , where is the indicator function on for being congruent to . By Fourier analysis, can be decomposed into two sums. Roughly, the first corresponds to the zeroth Fourier coefficient of and evaluates to , which diverges as , and the second sum corresponds to the non-zero Fourier coefficients and is always bounded. In our writeup, the advantage of restricting to is that the estimate of the second sum becomes significantly simpler, without further tools from number theory.

(Proof of Dirichlet’s Theorem restricted to .) Let be the multiplicative group of integers modulo , and be the indicator function such that if and otherwise. Then by Fourier expansion,
for every ,

where ranges over all characters of the dual group of . Since is a finite abelian group, it is is also isomorphic to its dual, and with , we can conclude that the only characters of are: the trivial character that is identically , and the character where if
and if . Thus, we can simplify and rewrite as

(For sanity check, one can easily verify via direct computation, without Fourier analysis, that the identities and hold.) For the rest of this proof, we will rely on the the fact that the characters and are real-valued.

To prove the theorem, we have to sum over all integers instead of just the multiplicative subgroup of . To this end, for every character , we define its Dirichlet character to be the extension to all of as follows: if and otherwise. Let be the indicator function of being congruent to . Then it is easy to see that

where are the Dirichlet characters of , respectively. Since we can express the indicator function in terms of Dirichlet characters, we have

It suffices to prove that as . In particular, we will show that

• as , which coincides with Euler’s argument since for all , and
• .

To estimate these sums, we prove the following:

Let be a Dirichlet character for . Then , where .
(of Proposition) Since is multiplicative, from the Euler-Dirichlet Product Formula,

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

where the second line follows from the estimate of the power series when , and the third from the fact that converges.

Now we estimate the two sums using the above proposition. For the trivial Dirichlet character , we have

which diverges as since diverges as .

For the non-trivial character , is simply the alternating series , which converges to a positive number. Thus,

completing the proof.

Most steps in the preceding proof can be easily extended to an arbitrary . The Euler-Dirichlet Product Formula works for a multiplicative function taking values in . The Fourier expansion of works as before. The Proposition still holds, but extra care has to be taken since the -function is now complex-valued. The sum diverges, but for a non-trivial Dirichlet character , the fact that the sum 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 ,

In general, for an arbitrary , the expression is replaced by , with , where is the Euler totient function.
Proof proceeds the same as before, where we showed that

with and . Previously, we simply noted that diverges as . To finish the proof, it suffices to note that