18.785: Analytic Number Theory, MIT, spring 2007 (K.S. Kedlaya)
Primes in arithmetic progressions
In this unit, we first prove Dirichlet’s theorem on primes in arithmetic progressions. We
then prove the prime number theorem in arithmetic progressions, modulo some exercises.

1

Dirichlet’s theorem

For short, I will say an arithmetic progression is eligible if it has the form m, m + N, m +2N, . . . where gcd(m, N ) = 1; it is equivalent to ask that any two consecutive terms arerelatively prime.
Theorem 1 (Dirichlet). Any eligible arithmetic progression of positive integers contains
infinitely many primes.
There are a few special cases where one can prove this directly, but otherwise algebraic
methods cannot touch this problem. Dirichlet’s idea was to prove, in some appropriate quantitative sense, that the primes distribute themselves equally among the eligible arithmetic
progressions with a particular difference; this goes back to Euler’s proof of the infinitude ofprimes using the Riemann zeta function.

2Asymptotic density and Dirichlet density

In order to speak quantitatively about the distribution of certain types of primes, or integers
in general, we need some sort of measure theory on the set of primes or the set of integers.
Note that Lebesgue-type measure theory is not an option for countable sets: we can only
hope to make finitely additive measures.
For S ⊆ T two sets of positive integers, with T infinite, the upper natural density andlower natural density of S in T are defined as
lim supN →∞#{n ∈ S : n ≤ N },#{n ∈ T : n ≤ N }lim infN →∞#{n ∈ S : n ≤ N }.
#{n ∈ T : n ≤ N }Of course the upper density is never less than the lower density. If they coincide, we call thecommon value the natural density (or asymptotic density) of S in T .
Many interesting sets fail to have a natural density (e.g., see exercises). We get a lessrestrictive notion of density by using Dirichlet series.
PFor S ⊆ T two sets of positive integers, with n∈T n−1 divergent, the upper Dirichlet
density and lower Dirichlet density of S in T are defined asPP−s−sn∈S nn∈S nPlim sup P,liminf.
−s−ss→1+s→1+n∈T nn∈T n

If they coincide, we call the common value the Dirichlet density of S in T .
1Let us make this explicit in two cases of interest. Recall that ζ(s) has a simple pole ofresidue 1 at s = 1, so as s → 1+ ,(s − 1)∞X

n−s = 1 + o(1).

n=1Hence if T = N, then the Dirichlet density of S is given byX
lim+ (s − 1)
n−ss→1n∈S

if the limit exists.
Taking logarithms, we see that as s → 1+ ,log ζ(s) + log(s − 1) = log(s − 1) +∞XXpMoreover,P P∞
pn=2 p−ns

p−ns = O(1).

n=1= O(1), soX
p−s = − log(s − 1) + O(1).
pHence if T is the set of primes, then the Dirichlet density of S is given by
P−sp∈S plims→1+ − log(s − 1)
if the limit exists.
Here are some easy facts about density. (If I don’t specify natural vs. Dirichlet, I meanthat the statement holds if you make a choice and use it consistently throughout the statement.)• Any finite set has density 0 in any infinite set.
• Density is a finitely additive measure: if S1 , . . . , Sm are disjoint subsets of T withdensities δ1 , . . . , δm in T , then their union has density δ1 + · · · + δm in T . Corollary:
two subsets of T whose combined density exceeds 1 must have infinite intersection.
• If S has density δ in N, then for any positive integer n, nS = {ns : s ∈ S} has density
δ/n.
I can’t help mentioning a fun example of the additivity of densities. Let α, β be positive
irrational numbers with 1/α + 1/β = 1. Put
Sα = {bnαc : n ∈ N}
Sβ = {bnβc : n ∈ N}.
Then Sα , Sβ have natural densities 1/α, 1/β. The fact that these add up to 1 is explainedby the beautiful result (Beatty’s theorem) that Sα , Sβ are disjoint and their union is N! (Ifyou’ve never seen this before, I recommend this as an amusing exercise.)2

Lemma 2. Let S ⊆ T be subsets of N such that S has natural density δ in T . Then S also
has Dirichlet density δ in T .
Proof. See exercises. (The converse is false; also see exercises.)
To prove Theorem 1, we will prove the following.
Theorem 3. For any positive integers m, N with gcd(m, N ) = 1, the set of primes congruent
to m modulo N has Dirichlet density 1/φ(N ) in the set of all primes (hence is infinite).

3

L-functions and discrete Fourier analysis

For χ a Dirichlet character of level N , we can writelog L(s, χ) =∞XXpχ(pn )p−nsn=1

for Re(s) > 1; as s → 1+ , we havelog L(s, χ) =X

χ(p)p−s + O(1).

pFor χ nonprincipal, we know that L(s, χ) is holomorphic and nonvanishing at s = 1, soX
χ(p)p−s = O(1),pwhereas for χ0 the principal conductor of level N , we saw above thatX
χ0 (p)p−s = − log(s − 1) + O(1).
p

At this point it mayPbe clear how to proceed: form a certain linear combination of thelog L(s, χ) to isolate p≡m (N ) p−s , and compare the asymptotic contributions of − log(s−1).
The fact that we can do this amounts to what is sometimes called discrete Fourier
analysis; if you prefer, it is the representation theory of the finite abelian group (Z/N Z) ∗ .
Theorem 4 (Discrete abelian Fourier analysis). Let G be a finite abelian group, and let Ĝ
be the character group (or dual group) of G, i.e., the group of homomorphisms G → C ∗ .
(a) The order of Ĝ is equal to the order of G.
(b) (Orthogonality of characters) If χ1 , χ2 ∈ Ĝ, then(X|G| χ1 = χ2
χ1 (g)χ2 (g) =0χ1 =6 χ2 .
g∈G
3

(c) If g1 , g2 ∈ G, thenXχ∈Ĝ

(|G| g1 = g2
χ(g1 )χ(g2 ) =0
g1 =6 g2 .

Proof. (a) If G = G1 × G2 , then clearly Ĝ = Ĝ1 × Ĝ2 . Since every finite abelian group G
is a product of cyclic groups, we may reduce to the case where G is cyclic, and thenthe result is clear. (For G = (Z/N Z)∗ , we can make this more explicit: we can use
the Chinese remainder theorem to split N into distinct prime-power factors, then usethe fact that (Z/pn Z)∗ is cyclic unless p = 2, in which case it is {±1} times a cyclicgroup.)(b) We saw this argument once before, but here it goes again: the left side is invariant
under multiplication by χ1 (h)χ2 (h) for any h ∈ G, because there is no difference
between summing over g or over gh. If χ1 6= χ2 , then we can make that multiplierdifferent from 1 by choosing suitable h. So the sum vanishes if χ1 6= χ2 . If χ1 = χ2 ,each summand is equal to 1 because characters of finite groups takes values which areroots of unity.
(c) See exercises.
So now it is clear what to do: given a choice of m coprime to N , taking sums of χ overall Dirichlet characters of level N , we obtain
1 X
1 XX
χ(m) log L(s, χ) =χ(p)χ(m)p−s + O(1)φ(N ) χφ(N ) χ pX=
p−s + O(1)p≡m (N )as s → 1+ . On the other hand,1 X
11 X
χ(m) log L(s, χ) =χ(m) log L(s, χ)log L(s, χ0 ) +φ(N ) χφ(N )φ(N ) χ6=χ0=−1log(s − 1) + O(1).
φ(N )This yields Theorem 3.

4

The prime number theorem in arithmetic progressions

The proof of Dirichlet’s theorem only uses information about the behavior of the L(s, χ)near s = 1. Using the fact that L(s, χ) 6= 0 on the entire line Re(s) = 1, we can prove amuch stronger result.
4

Theorem 5 (Prime number theorem in arithmetic progressions). For m, N positive integers
with gcd(m, N ), the set of primes congruent to m modulo N has natural density 1/φ(N ).
1xIn other words, the number of primes p ≤ x with p ≡ m (mod N ) is asymptotic to φ(N) log x
as x → ∞.
Proof. Given what we now know, this is a straightforward adaptation of our proof of theprime number theorem. For χ a Dirichlet character of level N , defineXϑχ (x) =χ(p) log p.
p≤xGiven a choice of m coprime to N , put
1 X
χ(m)ϑχ (x)φ(N ) χX=log p.

ϑm (x) =p≤x:p≡m (N )As in the proof of the prime number theorem, if we prove that the improper integral
Z ∞φ(N )ϑm (x) − xdxx2
11x as desired.
converges, we may then deduce that ϑm (x) ∼ φ(N)It suffices in turn to check that for χ principal,
Z ∞ϑχ (x) − xdxx2
1converges, and for χ nonprincipal,

Z ∞1ϑχ (x)
dxx2

converges. The former is an immediate consequence of the corresponding fact for ϑ (whichwe proved in the unit on the prime number theorem), since ϑ and ϑχ differ in only finitely
many terms. For the latter, see exercises.
As with the proof of the prime number theorem, we get very little information about
the error term, i.e., the difference between the actual number of primes p ≤ x with p ≡ mx
1(mod N ) and the asympotic count φ(N. That becomes a problem if, for instance, we) log x
want to know how long it takes to find one prime in an arithmetic progression. To address
this, we must first get better results on zero-free regions for the L(s, χ), then make a better
analytic argument to take advantage of the improved analytic information. We turn to thisin the next few lectures.

5Exercises
1. Prove Lemma 2. (Hint: use partial summation.)
2. Let S be the set of positive integers which have first digit 1 when written in base 10.
(a) Compute the upper and lower natural density of S, and verify that S does nothave a natural density.
(b) Prove that S has a natural Dirichlet density, and compute it.
Optional (not to be turned in): generalize to an arbitrary base b ≥ 3. Even more
optional: prove the analogous result for the set of primes with first digit 1 in base b.
3. Prove that there exists a constant c such that
X1= log log x + c + o(1).
pp≤x(Hint: you established asymptotics forpartial summation.)Pp≤xlog pp

on a previous homework. Apply

4. (a result of Mertens; tricky, optional) In the previous exercise, prove thatX
log(1 − p−1 ) + p−1 ,c=γ+pwhere γ is Euler’s constant. Then deduce thatY

(1 − p−1 ) ∼p≤xe−γ.
log x5. Deduce point (c) of Theorem 4 from points (a) and (b). (Hint: form the matrix A withrows indexed by g ∈ G, columns indexed by χ ∈ Ĝ, and entries χ(g). Then compareAA∗ with A∗ A, where ∗ denotes conjugate transpose. Or if you prefer, prove that thedual of Ĝ is canonically isomorphic to G.)
R∞
6. Prove that 1 ϑχt2(t) dt converges for χ nonprincipal, by applying the Tauberian theorem
from the unit on the prime number theorem. (Hint: use the fact that L(s, χ) 6= 0for Re(s) ≥ 1 to argue that −L0 (s, χ)/L(s, χ) is holomorphic in a neighborhood ofRe(s) ≥ 1. There will be an extra term to deal with, just as there was a term I
neglected in the original notes from the prime number theorem unit; see the corrected
notes online.)6