Dirichlet’s Theorem and Sieves

Dirichlet’s Theorem on the infinitude of primes in arithmetic progressions from 1837 is often viewed as the first result in analytic theory. To prove this result, Dirichlet shows that it suffices to prove the non-vanishing of (non-trivial) Dirichlet $L$ -functions

$\displaystyle L(s,\chi) := \sum_{n \geq 1} \frac{\chi(n)}{n^s}$

at the special point $s=1$ . Dirichlet’s theorem is without a doubt a beautiful result, but the reduction to $L(1,\chi) \neq 0$ is often introduced in a clumsy way. For example, the proof given in Apostol’s Introduction to Analytic Number Theory exposes the significance of $L(1,\chi)\neq 0$ while trying to prove the implication

$\displaystyle L(1,\chi) \sum_{n \leq X} \frac{\mu(n)\chi(n)}{n} = O(1) \quad \Longrightarrow \quad \sum_{n \leq X} \frac{\mu(n)\chi(n)}{n} = O(1).$

(By this point in the proof, the first result has been proven and the second is known to imply Dirichlet’s theorem.)

In this post I’d like to give a different (and possibly new) proof of the reduction of Dirichlet’s theorem to the non-vanishing of $L(1,\chi)$ which borrows some ideas from sieve theory. After this, I’ll show how the stronger hypothesis $L(1+it,\chi) \neq 0$ for $t \in \mathbb{R}$ can be used to prove an asymptotic for the size of the sieved set

$\displaystyle S:=\{ n : p \mid n, \, p \text{ prime} \Rightarrow p \equiv b \!\!\!\mod k\}.$

— REDUCTION OF DIRICHLET’S THEOREM —

The method of sieving with Dirichlet series is an effective method of estimating sieved sets that exhibit some sort of multiplicative structure. Roughly, to estimate the size of a set $S$ , let $a(n)$ denote the indicator function of $S$ and consider the Dirichlet series

$\displaystyle F(s) = \sum_{n \geq 1} \frac{a(n)}{n^s}.$

Note that $F(s)$ has an Euler product if and only if the indicator function $a(n)$ is multiplicative.

In the case of the set $S$ from the introduction, we consider

$\displaystyle F(s;b) = \prod_{p\equiv b(k)} \left(1 - \frac{1}{p^s}\right)^{-1}.$

This series is analytic in the right half-plane $\Re s > 1$ by comparison to the Riemann zeta function. To understand its analytic properties, we need a way to detect the condition $p \equiv b(k)$ . There’s really just one way to do this, which uses orthogonality of characters:

Lemma 1: We have

$\displaystyle \sum_{\chi} \chi(p)\overline{\chi(b)} = \begin{cases} \phi(k), & \quad p \equiv b(k) \\ 0, & \quad \text{else},\end{cases}$

in which the sum runs over all characters $\chi$ mod $k$ .

In particular,

$\displaystyle \prod_\chi \prod_p \Bigg( 1 - \frac{\chi(p)\overline{\chi(b)}}{p^s} \Bigg)^{\!-1} = \prod_p \Bigg( 1-\sum_\chi \chi(p)\overline{\chi(b)} p^{-s} + O(p^{-2s})\Bigg)^{\!-1}$

$\displaystyle = \prod_{p \equiv b(k)} \left(1-\frac{\phi(k)}{p^s}+O(p^{-2s})\right)^{-1} \prod_{p \not\equiv b(k)} \left( 1- O(p^{-2s})\right)^{-1}$

$\displaystyle = \prod_{p \equiv b(k)} \left( 1- \frac{1}{p^s}\right)^{-\phi(k)} H(s) = F(s)^{\phi(k)} H(s)$

in which $H(s)$ is analytic and non-zero in $\Re s > \frac{1}{2}$ . Of course, this implies that the analytic properties of $F(s;b)$ in $\Re s > \frac{1}{2}$ may be obtained from those of the Euler products

$\displaystyle D(s,\chi; b):=\prod_p \Bigg( 1 - \frac{\chi(p)\overline{\chi(b)}}{p^s} \Bigg)^{\!-1}.$

When $\chi$ is the trivial character mod $k$ , $D(s,\chi;b)$ reduces to $\zeta(s)$ (up to some Euler factors which divide $k$ ). Thus $F(s;b)$ has a pole at $s=1$ unless one of the terms $D(s,\chi;b)$ corresponding to $\chi \neq 1$ vanishes at $s=1$ .

Some remarks are in order:

1. If Dirichlet’s theorem is false, then $F(s;b)$ is a finite product which extends analytically into the half-plane $\Re s > 0$ . Thus we prove Dirichlet’s theorem if we can show that $F(s)^{\phi(k)}$ has a pole at $s=1$ .

2. Except for the ugly addition of $\overline{\chi(b)}$ , the Euler products of the functions $D(s,\chi;b)$ are exactly the Euler products of the Dirichlet $L$ -functions $L(s,\chi)$ . Wouldn’t it be nice if we could relate the analytic properties of $D(s,\chi;b)$ and $L(s,\chi)$ ?

It turns out that relating $L(s,\chi)$ and $D(s,\chi;b)$ to each other isn’t actually that hard. The idea is simple (except for one technical result), so I’ll sketch the proof before filling in the last detail.

Lemma 2: The infinite product $\prod(1+a_n)$ converges to a non-zero value if and only the series $\sum a_n$ converges.

Assuming the lemma, note that $D(s,\chi;b)$ converges to a non-zero value if and only if

$\displaystyle \sum_p \frac{\chi(p) \overline{\chi(b)}}{p^s}$

converges. Of course, $\chi(b)$ doesn’t affect convergence here, so we can factor it out, apply the Lemma in the reverse direction, and relate convergence of $D(s,\chi;b)$ to $L(s,\chi)$ !

There’s only one issue; namely, that the form of Lemma 2 you probably remember from calculus actually only holds when convergence is replaced with absolute convergence. And, alas, this is not satisfied at $s=1$ . This isn’t a fatal flaw, though — we just need a stronger form of Lemma 2:

Lemma 2.5: If $\sum \vert a_n \vert^2 < \infty$ , then $\prod (1+a_n)$ converges to a non-zero value if and only if the series $\sum a_n$ converges.

I first found this result in the AMM article Conditional Convergence of Infinite Products, by William Trench, but Trench notes that it appears in Knopp’s Theory and Applications of Infinite Series. In any case, we can use it to prove the following result:

Proposition: Suppose that $\Re s > \frac{1}{2}$ . Then $L(s,\chi)$ converges and is non-zero if and only the same holds for $D(s,\chi;b)$ .

Corollary: If $L(1,\chi) \neq 0$ for all non-trivial $\chi$ , then $F(s;b)^{\phi(k)}$ has a pole of order 1 at $s=1$ . (This proves Dirichlet’s theorem by Remark 1.)

— ESTIMATING A CERTAIN SIEVED SET —

We can actually extract a fair bit more from these analytic preliminaries. In general, we expect to be able to study the asymptotic growth of

$\displaystyle \#\{ n \leq X : p \mid n, \, p \text{ prime} \Rightarrow p \equiv b \!\!\!\mod k\}$

by studying the growth of the generating function $F(s;b)$ about its dominant singularity. Our task is complicated by the fact that $F(s;b)$ has a pole of fractional order at $s=1$ , but these concerns melt away with the right theorem. In this case, we apply a theorem due to Raikov (1954):

Theorem: Let $F(s) = \sum_{n \geq 1} a(n)/n^s$ be a Dirichlet series with non-negative coefficients. Suppose that $F(s)$ converges in $\Re s >1$ and that $F(s)$ extends analytically to $\Re s \geq 1$ except at $s=1$ . Suppose further that

$\displaystyle F(s) = \frac{H(s)}{(s-1)^{1-\alpha}},$

in which $\alpha \in \mathbb{R}$ and $H(s)$ is analytic and non-zero in $\Re s \geq 1$ . Then

$\displaystyle \sum_{n \leq X} a(n) \sim \frac{H(1) X}{\Gamma(1-\alpha) (\log X)^\alpha}.$

The function $F(s;b)$ satisfies the hypotheses of Raikov’s theorem provided that the Dirichlet series $D(s,\chi;b)$ do not vanish in the region $\Re s \geq 1$ . But this follows from the previous Proposition and the well-known fact that $L(s,\chi) \neq 0$ on the line $\Re s =1$ . We conclude that

$\displaystyle \#\{ n \leq X : p \mid n, \, p \text{ prime} \Rightarrow p \equiv b \!\!\!\mod k\} \sim \frac{cX}{(\log X)^{1-1/\phi(k)}}$

for some $c > 0$ which depends on $b$ and $k$ .

More generally, we can consider sets of the form

$\displaystyle S_B := \{n \geq 1 : p \mid n, \, p \text{ prime} \Rightarrow (p \!\!\!\mod k) \in B\}$

where $B$ is any subset of invertible residues mod $k$ . Since the Dirichlet series associated to $S_B$ factors as

$\displaystyle F(s;B):=\prod_{b \in B} F(s;b),$

we see at once that $F(s;B)$ has a pole of order $\# B/\phi(k)$ at $s=1$ . Raikov’s Tauberian theorem then implies that $S_B$ has

$\displaystyle \sim \frac{c_B X}{(\log X)^{1-\# B/\phi(k)}}$

elements $n \leq X$ .

— EXERCISES —

Exercise 1: Let $S$ denote the set of integers which may be written as a sum of two squares. Prove that $S$ has $\sim c X/ \sqrt{\log X}$ elements $n \leq X$ .

Exercise 2: Use Euler’s classification of odd perfect numbers to show that the set of odd perfect numbers has density 0. (It’s actually known that the number of odd perfect numbers at most $X$ is $O(x^\epsilon)$ for all $\epsilon > 0$ .)

Exercise 3: Let $P$ be a finite set of primes and let $S$ denote the set of integers composed only of powers of elements of $P$ . Find the asymptotic size of $S$ .

Exercise 4: Let $A$ be any set of positive integers and let $S$ denote the set of integers which can be written as a product of $a$ th powers, as $a$ varies through $A$ . Find the asymptotic size of $S$ .

Exercise 5: We call an integer $n$ square-full if $p^2 \mid n$ for every prime $p$ which divides $n$ . Find the asymptotic size of the set of square-full numbers. Along the way, show that the number of representations of $n$ as a product of a square-full number and a 6th power equals the number of representations of $n$ as a product of a square and a cube.

a. w. walker

mathematics and miscellany

Dirichlet’s Theorem and Sieves

Leave a Reply Cancel reply

Share this:

Like this:

Leave a Reply Cancel reply