FOURIER-ANALYTIC PROOFS OF THE PRIME NUMBER THEOREM

TERENCE TAO

Abstract. We take the two classical proofs of the prime number theorem - the contour integration based one and the elementary proof of Erdos and Selberg - and rephrase them in the language of Fourier analysis and convolutions on measures on the real line. This is not intended to be a serious alternative to the standard proofs, but highlights the well-known link between complex analysis and Fourier analysis. We do not presuppose any knowledge of analytic number theory.

1. The prime number theorem

The famous prime number theorem, conjectured by Legendre and Gauss around 1800, and finally proven by Hadamard and de la Valleé Poussin in 1896 (with fundamental contributions made by Riemann a few decades earlier) asserts that

|\{2 ≤ p ≤ N : p is prime\}| = \frac{N}{log N} (1 + o_{N→∞}(1))  (1)

for N large, where we use o_{N→∞}(1) to denote a quantity that goes to zero as N → ∞; note that it does not matter whether N is integer or not. The purpose of this note is to present the two standard proofs of this theorem (one using contour integration and the Riemann zeta function, and the elementary proof of Erdös and Selberg [3], [6]) using the language of Fourier analysis^{1} and convolution of measures on the real line. The contour integration proof will in fact end up proving the slightly more precise estimate

|\{2 ≤ p ≤ N : p is prime\}| = ∫_{2}^{N} \frac{dn}{log n} + O_{M}(\frac{N}{log^{M+1} N})  (2)

for all M ≥ 0, where O_{M}(X) denotes a quantity bounded by C_{M}X for some constant C depending only on M (and similarly if there are other subscripts than M in the O() notation); we have deliberately used n to denote a continuous variable as we shall later wish to invoke the analogy between an integral ∫_{a}^{b} f(n) dn and the corresponding Riemann sum ∑_{n=a}^{b} f(n) (also, we are reserving the letter x for the variable x = log n). It is easy to verify that ∫_{2}^{N} \frac{dn}{log n} = \frac{N}{log N} (1 + o(1)) (for instance, split the interval [2, N] into [2, \sqrt{N}], [\sqrt{N}, εN] and [εN, N] for some 0 < ε < 1, estimate each portion of the integral separately, and let ε → 0), so the latter statement implies the former.

1Our presentation of the elementary proof is similar to that in [2]; we thank Peter Sarnak for this observation.

To prove (1), or the stronger version (2), we obviously need to use some fact about the prime numbers. The basic fact we need is

Theorem 1.1 (Unique factorization theorem). Every positive integer n has a unique representation of the form

n = ∏_{p prime} p^{c_{p}},  (3)

where the c_{p} are non-negative integers and all but finitely many of the c_{p} are equal to zero (so the product converges).

Remark 1.2. One can in fact view (3) as a definition of the prime numbers, or more precisely the set of prime numbers is the only subset of the positive integers Z^{+} for which the above theorem holds. Thus it should be possible, at least in principle, to deduce (1) and (2) purely from (3) (and the trivial fact that the primes are a subset of Z^{+}), and this is in fact what we do^{2}.

Note that c_{p} is equal to the number of powers of p which divide n. Thus we can take logarithms of (3) to obtain

log n = ∑_{p prime} ∑_{j≥1:p^{j}|n} log p  (4)

where d|n means that d divides n. This motivates the introduction of the Von Mangoldt function Λ(n) : Z^{+} → R^{+}, defined as setting Λ(n) := log p if n = p^{j} is a power of p for some j ≥ 1, and Λ(n) = 0 otherwise. We thus get the the crude bound

0 ≤ Λ(n) ≤ log n.  (5)

and from (4) the fundamental identity

log n = ∑_{d|n} Λ(d)  (6)

and all sums are over the non-negative integers unless otherwise stated.

The function Λ(n) is almost supported on the primes, and Λ(p) = log p on the primes. Indeed, we have the crude bound

|{n ≤ N : Λ(n) ≠ 0, n not prime}| = |{n ≤ N : n = p^{j} for some j > 1}|

= ∑_{p≤\sqrt{N}, prime} |\{j > 1 : p^{j} ≤ N\}|

= O(\sqrt{N} log N) and thus (by (5)) we have

2Indeed, this point of view was pushed further by Beurling [1], who showed that any multiplicative submonoid of the positive reals which is distributed approximately like the integers will obey a prime number theorem (though one does not necessarily have a Riemann hypothesis or a functional equation in this level of generality).

|\{2 ≤ p ≤ N : p is prime\}| = ∑_{2}^{N} \frac{Λ(n)}{log n} + O(\sqrt{N} log^{2} N).

The prime number theorem, in its strong form (2), is now equivalent to the statement that

∑_{n=2}^{N} \frac{Λ(n)}{log n} = ∫_{2}^{N} \frac{dn}{log n} + O_{M}(N log^{−M−1} N) for all M ≥ 0.  (7)

Thus the theorem is some sort of assertion that Λ(n) has an average value of 1. The following lemma makes this more precise:

Lemma 1.3 (Tauberian theorem). The strong prime number theorem (2) (or (7)) is equivalent to the estimate

∑_{n=2}^{N} Λ(n) = N + O_{M}(N log^{−M} N) for all M ≥ 0.  (8)

The prime number theorem in the weaker form (1) is equivalent to the estimate

∑_{n=2}^{N} Λ(n) = N(1 + o_{N→∞}(1)).  (9)

Proof Let us first show that (8) implies (7). From the fundamental theorem of calculus we have

\frac{1}{log n} = \frac{1}{log N} + ∫_{n}^{N} \frac{dm}{m log^{2} m}

and hence (by two applications of (8) and then integration by parts)

∑_{n=2}^{N} \frac{Λ(n)}{log n} = ∑_{n=2}^{N} \frac{Λ(n)}{log N} + ∑_{n=2}^{N} Λ(n) ∫_{n}^{N} \frac{dm}{m log^{2} m}

= \frac{N + O_{M}(N log^{−M} N)}{log N} + ∫_{n}^{N} \frac{∑_{2≤n≤m} Λ(n) dm}{m log^{2} m}

= \frac{N}{log N} + O_{M}(N log^{−M−1} N) + ∫_{2}^{N} \frac{[m + O_{M}(m log^{−M})]dm}{m log^{2} m}

= \frac{N}{log N} + ∫_{2}^{N} \frac{dm}{log^{2} m} dm + O_{M}(N log^{−M−1} N)

= ∫_{2}^{N} \frac{dn}{log n} + O_{M}(N log^{−M−1} N)

which is (7). Conversely, if (7) holds, then we use the identity

1 = \frac{log N}{log n} − \frac{1}{log n} ∫_{n}^{N} \frac{dm}{m}

to obtain

∑_{n=2}^{N} Λ(n) = log N ∑_{n=2}^{N} \frac{Λ(n)}{log n} − ∑_{n=2}^{N} \frac{Λ(n)}{log n} ∫_{n}^{N} \frac{dm}{m}

= log N(∫_{2}^{N} \frac{dn}{log n} + O_{M}(N log^{−M−1} N)) − ∫_{2}^{N} \frac{dm}{m} ∑_{2≤n≤m} \frac{Λ(n)}{log n}

= log N ∫_{2}^{N} \frac{dn}{log n} + O_{M}(N log^{−M} N) − ∫_{2}^{N} \frac{dm}{m} ∫_{2}^{m} \frac{dn}{log n} + ∫_{2}^{N} \frac{dm}{m}O_{M}(m log^{−M−1})

= ∫_{2}^{N} \frac{dn}{log n}(log N − ∫_{n}^{N} \frac{dm}{m}) + O_{M}(N log^{−M} N)

= ∫_{2}^{N} dn + O_{M}(N log^{−M} N)

which is (8). The equivalence of (1) with (9) is proven similarly and is left to the reader.

In this note we shall present one proof of (9), which is essentially the Erdös-Selberg elementary proof in disguise, and another proof of (8), which is the classical contour integration proof in disguise. However we phrase them both in a common language, namely that of convolution of discrete measures on the half-line. To study these convolutions, we need to work simultaneously in physical space (using such basic facts as that the convolution of two non-negative measures is non-negative) and in frequency space (using the fact that the Fourier transform converts convolution to multiplication). In the contour integration proof, one works primarily in frequency space (the Riemann zeta function ζ(σ + it) and its relatives, in our language, are essentially the Fourier or Fourier-Laplace transforms of the measures we consider, with the t parameter playing the role of frequency variable), but one still needs to descend to physical space occasionally in order to ensure some non-vanishing properties of this zeta function. In the elementary proof one works primarily in physical space (which in our context is parameterized by the variable x = log n), but to obtain the genuine prime number theorem (as opposed to the weaker Selberg symmetry formula (46), which requires only physical space considerations) one still needs a little bit of Fourier analysis (or an equivalent). But in other respects the two proofs have much in common, and thus can be viewed as two extremes of a common spectrum of proofs. (Two other proofs, which at present seem to be quite different from these two, should be mentioned. The first is by Hildebrand [4] and proceeds via controlling the oscillation of the Möbius function via the large sieve. The second is by Sarnak [5] and proceeds by converting the problem of disproving zeroes of the zeta function on the line ℜ(s) = 1 to that of controlling the poles of the Eisenstein series on SL_{2}(Z).)

2. Elementary estimates

We now present the elementary theory of the primes, which corresponds roughly speaking to what one can say by analyzing the Riemann zeta function ζ(s) in the neighbourhood of the pole s = 1. However we will not explicitly introduce the Riemann zeta function in what follows (although it is lurking in the background, as the Fourier transform of certain measures which we shall encounter), and work entirely in physical space. The culmination of this elementary theory is the Selberg symmetry formula (44) (or (46)), which gives the prime number theorem (9) up to a factor of two, the error being caused by the “almost primes”. The problem, of removing the almost primes from the formula and ending up with just the primes themselves is an instance of the parity problem, and to resolve it requires a slightly nontrivial additional ingredient, in this case some Fourier analysis.

The first thing we need to do is to establish the Möbius inversion formula, which expands the Kronecker delta function δ_{n,1} as a sum over the divisors of n. Recall that δ_{n,1} is equal to 1 if n = 1 and equal to 0 otherwise. Thus if n has a factorization of the form (3) with c_{p} non-zero for exactly k primes p_{1}, …, p_{k}, then we have (by the binomial formula)

δ_{n,1} = 0^{k}

= (1 − 1)^{k}

= ∑_{A⊂{p_{1},... ,p_{k}}}(−1)^{|A|}

= ∑_{p_{i_{1}} ...p_{ir} |p_{1}...p_{k}}(−1)^{r}

= ∑_{p_{i_{1}} ...p_{ir} |n;p_{i_{1}} ...p_{ir} squarefree}(−1)^{r}.

This motivates introducing the Möbius function μ : Z^{+} → R, defined by setting μ(n) := (−1)^{r} if n is the product of k distinct primes n = p_{1} … p_{r} (with the convention that μ(1) = 1), and μ(n) = 0 otherwise (i.e. if n is not square-free). From the above considerations we have thus proven the Möbius inversion formula

δ_{n,1} = ∑_{d|n} μ(d).  (10)

We also observe the trivial bound

|μ(n)| ≤ 1  (11)

on the Möbius function.

To manipulate the Möbius and von Mangoldt functions it is convenient to work with the convolution algebra of measures on the half-line.

Definition 2.1. Define a half-line measure to be a complex-valued, locally finite Borel measure on the half-line R^{+}. If ν_{1} and ν_{2} are half-line measures, we define their convolution ν_{1} ∗ ν_{2} in the usual manner by the formula

∫ f(x)(ν_{1} ∗ ν_{2})(x) = ∫ ∫ f(x + y)ν_{1}(x)ν_{2}(y)

for all continuous functions f, thus ν_{1} ∗ ν_{2} is also a half-line measure. If ν is a half-line measure and g(x) is a continuous function on [0, +∞), we can define their product g(x)ν in the usual manner by the formula

∫ f(x)(g(x)ν)(x) = ∫ (f(x)g(x))ν(x),

and observe that g(x)ν is also a half-line measure

We observe that the operation of convolution (f, g) ↦ f ∗g is bilinear, commutative, associative, and has δ as the identity. We also have the Leibnitz rule^{3}

x(ν_{1} ∗ ν_{2}) = (xν_{1}) ∗ ν_{2} + ν_{1} ∗ (xν_{2})  (12)

and the modulation invariance

e^{sx}(ν_{1} ∗ ν_{2}) = (e^{sx}ν_{1}) ∗ (e^{sx}ν_{2})  (13)

for any complex s. We also make the trivial but important observations that the convolution of two non-negative measures is also non-negative, and if ν_{1} = O(μ_{1}) and ν_{2} = O(μ_{2}) for some non-negative μ_{1}, μ_{2} then ν_{1} ∗ ν_{2} = O(μ_{1} ∗ μ_{2}).

We shall analyze the following half-line measures:

• Heaviside measure H(x) dx, defined as Lebesgue measure dx multiplied by the Heaviside function H(x) := 1_{[0,+∞)}.

• Dirac measure δ(x) = H′(x), defined as the point mass at the origin; note that this is the identity for the convolution operator.

• Log-integer measure M_{1}(x), defined by the formula

M_{1}(x) := ∑_{n} e^{−x}δ(x − log n) = ∑_{n} \frac{1}{n}δ(x − log n).  (14)

• Von Mangoldt measure M_{Λ}(x), defined by the formula

M_{Λ}(x) := ∑_{n} e^{−x}Λ(n)δ(x − log n) = ∑_{n} \frac{Λ(n)}{n}δ(x − log n).  (15)

• Möbius measure M_{μ}(x), defined by the formula

M_{μ}(x) := ∑_{n} e^{−x}μ(n)δ(x − log n) = ∑_{n} \frac{μ(n)}{n}δ(x − log n).  (16)

The Heaviside measure H(x) dx can also be written in the suggestive form

H(x) dx = ∫_{1}^{∞} e^{−x}H′(x − log n) dn = ∫_{1}^{∞} \frac{1}{n}δ(x − log n) dn,  (17)

where we are now making n a continuous variable rather than a discrete one. Thus one should think of H(x) dx as a continuous analogue of the discrete measure M_{1}(x), and we have the heuristic

H(x) dx ≈ M_{1}(x) in some “weak” sense.  (18)

3This is equivalent to the more familiar Leibnitz rule \frac{d}{dξ} (f(ξ)g(ξ)) = ( \frac{d}{dξ} f(ξ))g(ξ) + (f(ξ) \frac{d}{dξ} g(ξ)) after using the Fourier transform to convert the convolution to a multiplication.

Similarly, under the Fourier transform, (13) reflects the invariance of multiplication of two meromorphic functions under complex translations.

Now we connect the above measures to each other, as well as to the measure e^{−x}H(x) dx (which is a convenient “bump function” or “approximate identity” for us to convolve against).

Lemma 2.2 (Convolution identities). We have the identities

H(x) dx ∗ H(x) dx = xH(x) dx  (19)
H(x) dx ∗ xH(x) dx = \frac{1}{2}x^{2}H(x) dx  (20)
e^{−x}H(x) dx ∗ e^{−x}H(x) dx = xe^{−x}H(x) dx  (21)
H(x) dx ∗ e^{−x}H(x) dx = (1 − e^{−x})H(x) dx  (22)
H(x) dx ∗ xe^{−x}H(x) dx = (1 − e^{−x} − xe^{−x})H(x) dx  (23)
xH(x) dx ∗ e^{−x}H(x) dx = (x − 1 + e^{−x})H(x) dx  (24)
M_{Λ} ∗ M_{1} = xM_{1}  (25)
M_{μ} ∗ M_{1} = δ.  (26)

Proof The estimates (19), (20), (22), (23) can be verified directly, using the observation that H(x) dx ∗ f(x)H(x) dx = F (x)H(x) dx where F is the primitive of f with F (0) = 0. The claim (21) then follows from (19) and (13), and (24) follows from (22), (23), (12). To prove (25), we see from (14), (15) and the substitution r := nm that

M_{Λ}∗M_{1} = ∑_{n} ∑_{m} \frac{Λ(n)}{n} \frac{1}{m}δ(x−log n)∗δ(x−log m) = ∑_{n,m} \frac{Λ(n)}{nm}δ(x−log nm) = ∑_{r} \frac{1}{r} ∑_{n|r} Λ(n)

and the claim follows from (14), (6). The proof of (26) is similar^{4} but uses (10) instead of (6).

Remark 2.3. From (18), (19), (25) one is tentatively led to the heuristic

M_{Λ} ≈ H(x) dx in some “weak” sense.  (27)

while the prime number theorem (8) can be rephrased (using the change of variables N := e^{x})

M_{Λ} ∗ e^{−x}H(x) dx = (1 + O_{M}((1 + x)^{−M}))H(x) dx.  (28)

Actually we will not obtain this strong form of the prime number theorem by this elementary method, instead we shall shoot for the weaker estimate

M_{Λ} ∗ e^{−x}H(x) dx = (1 + o_{x→∞}(1))H(x) dx,  (29)

which is equivalent to (9). The estimate (29) is already plausible from (27) and (22). But to make the heuristic (27) precise requires a certain amount of effort; the basic problem is that convolution with M_{1} is inverted by convolution with M_{μ}, which is an infinite measure. (though one with plenty of cancellation, as we shall see below). Incidentally, there is an analogue of (27) for M_{μ}, namely

4What is happening here is that we have embedded the algebra of Dirichlet convolution inside the algebra of convolution of half-line measures; however the latter algebra has the advantage that it also contains some other useful objects such as Heaviside measure, which do not directly exist in the Dirichlet convolution setting.

M_{μ} ≈ δ′(x) in some “weak” sense  (30)

(this is consistent with (26), (18) since δ′(x) ∗ H(x) dx = δ). this heuristic is rather difficult to pin down precisely, though it does suggest that M_{μ} does indeed have a substantial amount of cancellation.

The discrete measures M_{1}, M_{Λ}, M_{μ} are of course very rough measures, and difficult to estimate pointwise, although from (5), (11) we have the crude bounds

0 ≤ M_{Λ}(x) ≤ xM_{1}(x); −M_{1}(x) ≤ M_{μ}(x) ≤ M_{1}(x).  (31)

However, we can do a lot better if we convolve these discrete measures with a smoother measure such as H(x) dx or with a bump function. We begin with some estimates for averages of M_{1} and xM_{1}, for which we have very good estimates.

Proposition 2.4 (Averaged estimates for the log-integers). We have the estimates

M_{1} ∗ H(x) dx = (x + γ + O(e^{−x})H(x) dx  (32)
M_{1} ∗ e^{−x}H(x) dx = (1 + O(e^{−x}))H(x) dx  (33)
M_{1} ∗ xe^{−x}H(x) dx = (1 + O(e^{−x}))H(x) dx  (34)
(xM_{1}) ∗ H(x) dx = (\frac{1}{2}x^{2} + γ_{2} + O(xe^{−x}))H(x) dx  (35)
(xM_{1}) ∗ e^{−x}H(x) dx = (x + O(1))H(x) dx  (36)

where γ is Euler’s constant

γ := lim_{N→∞} ∑_{n=1}^{N} \frac{1}{n} − ∫_{1}^{N} \frac{dn}{n} = 0.577 …

and γ_{2} is an additional absolute constant (the exact value of which is not important for us).

Remark 2.5. These estimates for M_{1} should be compared with the corresponding estimates (19), (22), (24) for H(x) dx, and with the heuristic (18). One can obtain more complete asymptotic series for the above expressions by means of Euler’s integration identities, but we will not need such series here (there are other error terms in our analysis which swamp the precision one obtains from further terms in these expansions).

Proof The estimate (33) can be rewritten (using the substitution x = log N) as

∑_{n≤N} 1 = N + O(1)

for N ≥ 1, which is clearly true; the estimate (34) then follows by convolving both sides with e^{−x}H(x) dx and using (21), (22), and (36) then follows from^{5} the Leibnitz rule (12) . The estimate (32), on the other hand, becomes

5One can be much more precise here using Stirling’s formula N! = \sqrt{2πN}N^{N} e^{−N} (1+O(1/N)), but we will not need to do so here.

∑_{n≤N} \frac{1}{n} = log N + γ + O(1/N).

It suffices to prove this for integer N. We can split

log N = ∫_{2}^{N} \frac{dm}{m} = ∑_{n=2}^{N−1} ∫_{n}^{n+1} \frac{dm}{m}.

From the trapezoid rule we have ∫_{n}^{n+1} \frac{dm}{m} = \frac{1}{2}(\frac{1}{n} + \frac{1}{n+1}) + O(\frac{1}{n^{2}} ), and the claim follows from the definition of γ and the absolute convergence of ∑_{n} \frac{1}{n^{2}} . Finally, we convolve both sides of (32) with H(x) dx and using (19), (20) we have

M_{1} ∗ xH(x) dx = (\frac{1}{2}x^{2} + γx − γ_{2} + O(xe^{−x})H(x) dx

for some constant γ_{2}, and (35) follows from the Leibniz rule (12).

Using these estimates, (2.2), and the crude estimates (31) we can now quickly conclude a number of basic estimates on averages of M_{μ} and M_{Λ}, although the estimates here will not be nearly as precise as those in the above Proposition.

Corollary 2.6 (Averaged estimates for the Möbius and von Mangoldt measures). We have

M_{μ} ∗ H(x) dx = O(1)H(x) dx  (37)
M_{μ} ∗ xH(x) dx = O(1)H(x) dx  (38)
M_{μ} ∗ x^{2}H(x) dx = (2x + O(1))H(x) dx  (39)
M_{Λ} ∗ e^{−x}H(x) dx = O(1)H(x) dx  (40)
M_{Λ} ∗ H(x) dx = (x + O(1))H(x) dx  (41)

The reader is invited to verify that these heuristics are consistent with (though weaker than) the heuristics (27), (30), at least in the asymptotic region x ≫ 1.

Proof If we convolve both sides of (33) with M_{μ} and use (26) we obtain

e^{−x}H(x) dx = M_{μ} ∗ H(x) dx + M_{μ} ∗ O(e^{−x})H(x) dx

while from (31) and (33), (34) we have

M_{μ} ∗ O(e^{−x})H(x) dx = O(1)H(x) dx; M_{μ} ∗ O(xe^{−x})H(x) dx = O(1)H(x) dx; . (42)

Combining these two estimates we obtain (37). The claim (38) follows similarly, by convolving both sides of (32) with M_{μ} and then applying (26), (38), (??).

We delay the proof of (39) for now, and turn to (40). From (25), (26) we have

M_{Λ} = M_{μ} ∗ xM_{1}.  (43)

The claim (40) now follows by convolving both sides of (36) with M_{μ} and then using (37), (42).

Now we prove (41). If we convolve both sides of (33) with M_{Λ} and use (25) we obtain

(xM_{1}) ∗ e^{−x}H(x) dx = M_{Λ} ∗ H(x) dx + M_{Λ} ∗ O(e^{−x})H(x) dx.

The claim now follows from (33) and (40).

Finally, if we convolve both sides of (35) with M_{μ} and use (43), (38), (37), (42) we obtain

(x + O(1))H(x) dx = \frac{1}{2}M_{μ} ∗ x^{2}H(x) dx + O(1)H(x) dx

which is (39).

Remark 2.7. In more traditional notation, the estimates in the above Corollary become

∑_{n<N} \frac{μ(n)}{n} = O(1)

∑_{n<N} \frac{μ(n) log n}{n} = O(1)

∑_{n<N} \frac{μ(n) log^{2} n}{n} = 2 log N + O(1)
∑_{n<N} Λ(n) = O(N)

∑_{n<N} \frac{Λ(n)}{n} = log N + O(1).

The reader may wish to compare the proofs above with their counterparts in traditional notation; the role of convolution on R is of course taken over by Dirichlet convolution, but the convolution on R has the advantage of also allowing one to use the continuous measure H(x) dx, which allows for some simplifications. It should be clear that one can continue obtaining further estimates in this vein involving higher powers of x, but we will not need them here, and in any case a more systematic way to obtain such estimates is to study the Laurent expansions of the zeta function ζ(s) and the companion functions \frac{1}{ζ(s)} and \frac{−ζ′(s)}{ζ(s)} around the pole s = 1 (and to use all available knowledge about the zeroes of the zeta function in order to get the best possible control on the error terms).

3. The Selberg symmetry formula

Note that (40) is too weak to imply the prime number theorem (29), as it gives a bound O(1) on the right-hand side rather than an asymptotic 1 + o(1). The estimate (41) does give an asymptotic, but unfortunately it is weighted in such a way that it also does not imply the prime number theorem (29) (the best it can do is show that ∑_{n≤N} Λ(n) is comparable to N, or equivalently that the number of primes less than N is comparable to N/ log N up to a constant; this was first proven by Chebyshev). Indeed one cannot obtain the prime number theorem purely from these types of manipulations, for a reason related to the “parity problem” in sieve theory - there is a difficulty in trying to separate the primes from the almost primes

- the numbers which are products of two primes. (This problem also manifests itself in Fourier space, where the difficulty is now to prevent vanishing of the Riemann zeta function on the line ℜ(s) = 1. We shall compare these two perspectives on the same difficulty later). However if one combines the primes and almost primes together then it is much easier to obtain an asymptotic for the number of primes and almost primes. The key estimate is

Lemma 3.1 (Selberg symmetry formula). We have

(xM_{Λ} + M_{Λ} ∗ M_{Λ}) ∗ e^{−x}H(x) dx = (2x + O(1))H(x) dx.  (44)

Proof From the Leibnitz identity (12) and two applications of (25), we obtain

(xM_{Λ} + M_{Λ} ∗ M_{Λ}) ∗ M_{1} = (xM_{Λ}) ∗ M_{1} + M_{Λ} ∗ (xM_{1}) = x(M_{Λ} ∗ M_{1}) = x^{2}M_{1}. (45)

Convolving both sides with M_{μ} ∗ e^{−x}H(x) dx, the claim now follows from (26) and (39).

Remark 3.2. In more conventional notation, this formula becomes

∑_{n≤N} Λ_{2}(n) = 2N log N + O(N)

where Λ_{2} is the second order von Mangoldt function

Λ_{2}(n) = log(n)Λ(n) + ∑_{d|n} Λ(d)Λ(\frac{n}{d}) = ∑_{d|n} μ(d) log^{2} \frac{n}{d}

(the latter identity is essentially (45). This estimate can easily be shown to be equivalent to

∑_{p≤N:p prime} log^{2} p + 2 ∑_{pq≤N:pq almost prime,p<q} log p log q = 2N log N + O(N). (46)

Thus the Selberg symmetry formula (44) can be viewed as an “almost prime number theorem”, which counts both the primes and almost primes simultaneously (with some suitable logarithmic weights).

From (44) and the trivial observation that M_{Λ} ∗ M_{Λ} ∗ e^{−x}H(x) dx is non-negative we obtain the inequality

(xM_{Λ}) ∗ e^{−x}H(x) dx ≤ (2x + O(1))H(x) dx.

From (12), (21) we have

(xM_{Λ})∗e^{−x}H(x) dx = x(Λ∗e^{−x}H(x))+O(1)H(x) dx = (x+1)(Λ∗e^{−x}H(x))+O(1)H(x) dx

and so we obtain the bounds

0 ≤ M_{Λ} ∗ e^{−x}H(x) dx ≤ 2 + O(\frac{1}{1 + x})H(x) dx  (47)

(the lower bound simply reflecting the non-negativity of M_{Λ}); note that this comes within a factor of 2 of giving the prime number theorem (28). This loss of 2 is a manifestation of the parity problem, and requires a non-trivial amount of effort to remove.

Remark 3.3. There are higher-order generalizations of the Selberg symmetry formula (44) involving the higher order von Mangoldt functions Λ_{k}(n) := ∑_{d|n} μ(d) log^{k} \frac{n}{d}, and these asymptotics can in fact be vastly generalized further by means of the Bombieri sieve, which also tends to give upper bounds on problems such as the twin prime conjecture or Goldbach’s conjecture which also miss out by a factor of two over the expected asymptotic. We will not discuss these topics here.

It is generally accepted that the Selberg symmetry formula (44) more or less represents the limit of what can be said about the distribution of primes using just the above types of methods^{6}. Observe (from (19), (24)) that the formula (44) is still consistent with the heuristic (27); indeed, (44) can be shown to be implied by the strong prime number theorem (28). Unfortunately, (44) is also consistent with other heuristics such as

M_{Λ} ≈ (1 − ∑_{j=1}^{k} e^{it_{j}x})H(x) dx  (48)

for any finite collection t_{1}, …, t_{k} ∈ R of distinct non-zero frequencies (this is best seen by working in the Fourier domain, where this heuristic corresponds to the vanishing of ζ(1 + it_{1}), …, ζ(1 + it_{k}); see also the periodic model below). What’s worse, these exotic heuristics (48) are compatible with all the other estimates already established but are inconsistent with (28) for k ≥ 1. However, the heuristic (27) is the only heuristic which is consistent with (44) and also the non-negativity constraint M_{Λ} ≥ 0 in (31). This is basically how Erdös and Selberg obtain the elementary proof of the prime number theorem (29); we shall present this proof shortly.

4. Elementary proof of the prime number theorem

We can now begin the proof of the prime number theorem (29) in earnest. We begin rewriting the Selberg symmetry formula (44) in a more convenient form. Subtracting two copies of (24) from (44) we obtain

(xM_{Λ} + M_{Λ} ∗ M_{Λ} − 2xH(x) dx) ∗ e^{−x}H(x) dx = O(1)H(x) dx.

Now let ϕ ∈ C_{c}^{∞}(R^{+}) be any test function supported on the half-line R^{+}. From integration by parts we observe the formula

ϕ(x) dx = e^{−x} H(x)dx ∗ ((ϕ′(x) − ϕ(x)) dx),

6In other words, it is the limit of what can be achieved by algebraic manipulation of convolutions, and approximating integrals by their Riemann sums; or equivalently, this is the limit of what can be achieved purely by analyzing the Riemann zeta function ζ(s) near the pole s = 1 (and not incorporating any significant new information on ζ(s), in particular whether there are any zeroes on the line ℜ(s) = 1). Another way to see this is to observe that the Dirichlet series for Λ_{2} is \frac{ζ′′(s)}{ζ(s)} , and the Selberg symmetry formula is basically equivalent to the assertion that this function has no double poles on the half-plane ℜ(s) ≥ 1 other than at s = 1. Note that this assertion does not preclude the possibility of simple zeroes of ζ(s) on the line ℜ(s) = 1, it only excludes zeroes of order 2 or higher. But those can be excluded by the bound (11), which allows one to dominate 1/ζ(1 + ε + it) by ζ(1 + ε) and thus conclude that any zeroes of ζ on ℜ(s) = 1 are necessarily simple. Indeed the proof of (44) given in the text is essentially equivalent to the above argument up to Fourier transforms.

and thus see from Young’s inequality that

(xM_{Λ} + M_{Λ} ∗ M_{Λ} − 2xH(x) dx) ∗ ϕ = O_{ϕ}(1)H(x) dx.  (49)

We exploit this formula as follows. Let ν_{ϕ} denote the measure

ν_{ϕ} := (M_{Λ} − H(x) dx) ∗ ϕ(x) dx;  (50)

This measure ν_{ϕ} quantifies the extent to which the heuristic (27) is true; we would like it to be as small as possible. We say that ϕ is a normalized bump function if it is non-negative and has total mass ∫_{R^{+}} ϕ = 1.

Lemma 4.1 (Preliminary bounds on ν_{ϕ}). If ϕ is a test function, we have the pointwise bound

ν_{ϕ} = O(∥ϕ′∥_{L^{1}})H(x) dx  (51)

and the averaged decay estimate

ν_{ϕ} ∗ H(x) dx = O(∥ϕ∥_{L^{1}})H(x) dx.  (52)

If ϕ is in fact a normalized bump function, we can sharpen (51) to

|ν_{ϕ}| ≤ (1 + O_{ϕ}(\frac{1}{1 + x}))H(x) dx.  (53)

Finally, if ϕ_{1}, ϕ_{2} are any two test functions on R^{+}, we have

ν_{ϕ_{1}∗ϕ_{2}} = −\frac{1}{1 + x}(ν_{ϕ_{1}} ∗ ν_{ϕ_{2}}) + O_{ϕ_{1},ϕ_{2}}(\frac{1}{1 + x})H(x) dx.  (54)

Proof The estimate (52) follows from (??), (41), and Young’s inequality, and then the estimate (51) follows from (52) and the identity ϕ(x) dx = H(x) dx ∗ ϕ′(x) dx. Now we turn to (53), which is a variant of (47). To see the lower bound on ν_{ϕ}, simply discard the non-negative measure M_{Λ} ∗ ϕ and use the easy estimate H(x) dx ∗ ϕ(x) dx = (1 + O_{ϕ}(\frac{1}{1+x}))H(x) dx. To obtain the upper bound, we discard the non-negative term M_{Λ} ∗ M_{Λ} ∗ ϕ from (49) to obtain the inequality

(xM_{Λ} − 2xH(x) dx) ∗ ϕ ≤ O(∥ϕ∥_{W^{1,1}})H(x) dx.

By the Leibnitz rule (12), the left-hand side is equal to

x[(M_{Λ} − 2H(x) dx) ∗ ϕ] − (M_{Λ} − 2H(x) dx) ∗ xϕ.

The second term is O_{ϕ}(1)H(x) dx thanks to (51) and Young’s inequality, and so

xν_{ϕ} − x(H(x) dx ∗ ϕ) ≤ O_{ϕ}(1)H(x) dx.

Since H(x) dx ∗ ϕ = (1 + O_{ϕ}(\frac{1}{1+x}))H(x) dx, we thus see (using (51)) that

(1 + x)ν_{ϕ} ≤ O_{ϕ}(1)H(x) dx

which gives the upper bound in (53).

Finally, we prove (54). Applying (49) with ϕ replaced by ϕ_{1} ∗ ϕ_{2} and using (19), we obtain

(xM_{Λ} − xH(x)) ∗ ϕ_{1}(x) dx ∗ ϕ_{2}(x) dx
+ (M_{Λ} ∗ ϕ_{1}(x) dx) ∗ (M_{Λ}(x) ∗ ϕ_{2}(x) dx)
− (H(x) dx ∗ ϕ_{1}(x) dx) ∗ (H(x) dx ∗ ϕ_{2}(x) dx) = O_{ϕ_{1},ϕ_{2}}(1)H(x) dx.

From (12), (50), and (51) (or (53)) we have

(xM_{Λ}−xH(x))∗ϕ_{1}(x) dx∗ϕ_{2}(x) dx = xν_{ϕ_{1}∗ϕ_{2}}−ν_{x(ϕ_{1}∗ϕ_{2})} = xν_{ϕ_{1}∗ϕ_{2}}+O_{ϕ_{1},ϕ_{2}}(1)H(x) dx

and from (50), (52) we have

(M_{Λ} ∗ ϕ_{1}(x) dx) ∗ (M_{Λ}(x) ∗ ϕ_{2}(x) dx)
−(H(x) dx ∗ ϕ_{1}(x) dx) ∗ (H(x) dx ∗ ϕ_{2}(x) dx) = ν_{ϕ_{1}} ∗ ν_{ϕ_{2}} + ν_{ϕ_{1}} ∗ H(x) dx ∗ ϕ_{2}(x) dx
+ H(x) dx ∗ ϕ_{1}(x) dx ∗ ν_{ϕ_{1}}
= ν_{ϕ_{1}} ∗ ν_{ϕ_{2}} + O_{ϕ_{1},ϕ_{2}}(1)H(x) dx

and hence

xν_{ϕ_{1}∗ϕ_{2}} + ν_{ϕ_{1}} ∗ ν_{ϕ_{2}} = O_{ϕ_{1},ϕ_{2}}(1)H(x) dx.

Adding ν_{ϕ_{1}∗ϕ_{2}} to both sides using (51) (or (53)), the claim (54) follows.

The formula (54) is crucial; it allows us to essentially write ν_{ϕ_{1}∗ϕ_{2}} as a weighted convolution of ν_{ϕ_{1}} and ν_{ϕ_{2}}. As we shall see, there is a certain “smoothing effect” in this convolution which allows us to start with estimates such as (51), (52), (53) and bootstrap them to better estimates via (54). Iterating this procedure we will in fact eventually be able to show that ν_{ϕ} = o_{x→∞;ϕ}(1)H(x) dx for all test functions ϕ, from which it shall be easy to deduce the prime number theorem (9).

We turn to the details. We shall need some Fourier analysis in order to analyze the convolution; it is easiest to do this by modulating the test functions ϕ(x) by various complex phases e^{itx}, where t is a frequency parameter which we shall later perform some averaging over. Somewhat remarkably, it is possible to still obtain bounds such as (53) when one does so; furthermore one can even gain by an epsilon, by exploiting the apparently innocuous fact that M_{Λ} and H(x) are real rather than complex. More precisely:

Lemma 4.2. There exists a real-valued normalized bump function ϕ_{1} and an ε > 0 such that

|ν_{e^{itx}ϕ_{1}}| ≤ ((1 − ε) + O_{t,ϕ_{1},ε}(\frac{1}{1 + x}))H(x) dx  (55)

for all t ∈ R. Furthermore the dependence of the constants in the error term O_{t,ϕ_{1},ε}(\frac{1}{1+x}) on t is uniform if t is restricted to a compact set.

Remark 4.3. This ε gain over (53) may seem innocuous, but it is one of the two keys to the whole proof (the other being the Selberg symmetry formula); it corresponds in Fourier space to eliminating the possibility of zeroes of the zeta function on the axis ℜ(s) = 1 (basically by showing that the residues of −\frac{ζ′(s)}{ζ(s)} have to be at least −1 + ε). To put it another way, this estimate is what eliminates the scenario (48) from consideration. It already implies, for instance, that given any ε > 0 and sufficiently large N, that there is always a prime between N and (1 + ε)N (in fact, there are at least c(ε)N/ log N of them for some c(ε) > 0); as we shall see, this fact (which seems to be one of Erdös’s primary contributions to the elementary proof) can be bootstrapped up via the Selberg symetry formula to give the full prime number theorem.

Proof Note that by choosing the normalized bump function ϕ_{1} to have sufficiently broad support, we can make ∥ϕ′_{1}∥_{L^{1}} as small as one wishes. Thus by (51) we can ensure that we have the bound

|ν_{ϕ_{1}}| ≤ \frac{1}{2}H(x) dx

(for instance), and then by continuity of the quantity ∥(e^{itx}ϕ_{1})′∥_{L^{1}} we thus have

|ν_{e^{itx}ϕ_{1}}| ≤ \frac{3}{4}H(x) dx

for all |t| < δ, for some δ > 0. This resolves the “low frequency case” when |t| is small; it remains to deal with the high frequencies.

The point is that the modulation e^{itx} creates some non-trivial cancellation in ϕ_{1}. To quantify this, observe that ϕ_{1} is non-negative and has total mass 1. This means that for any non-zero frequency t and any phase θ, the modulated function cos(tx+θ)ϕ_{1} will have L^{1} norm strictly less than 1, since ϕ_{1} cannot possibly be supported just on the discrete set {x : | cos(tx + θ)| = 1}. Furthermore, as t → ±∞, we have

∥ cos(tx + θ)ϕ_{1}∥_{L^{1}} → \frac{2}{π} ∥ϕ_{1}∥_{L^{1}} = \frac{2}{π} < 1

uniformly in θ, simply because ϕ is smooth, and | cos(x)| is periodic and has an average value of \frac{2}{π}. Thus by continuity and compactness sees that

∥ cos(tx + θ)ϕ_{1}∥_{L^{1}} < 1 − 2ε for all |t| ≥ δ and 0 ≤ θ ≤ 2π  (56)

if we choose ε > 0 sufficiently small depending on ϕ_{1} and δ.

Now fix |t| ≥ δ. By the usual theory of approximations to the identity, we can find a normalized bump function ψ_{t,ε} (of quite narrow support, depending on t) such that (e^{itx}ϕ_{1}) ∗ ψ_{t,ε} is as close to e^{itx}ϕ_{1} as one wishes in (say) the Sobolev norm W^{1,1}. In particular, by (51) we may ensure that (for instance)

ν_{(e^{itx}ϕ_{1}∗ψ_{t,ε})−e^{itx}ϕ_{1}} = O(ε^{2})H(x) dx

or in other words

ν_{e^{itx}ϕ_{1}} = ν_{ψ_{t,ε}} ∗ e^{itx}ϕ_{1}(x) dx + O(ε^{2})H(x) dx.

We multiply this by an arbitrary phase e^{iθ} and take real part (exploiting the fact that ν_{ψ_{t,ε}} and ϕ_{1} are real-valued) to obtain

ℜ(e^{iθ}ν_{e^{itx}ϕ_{1}}) = ν_{ψ_{t,ε}} ∗ cos(tx + θ)ϕ_{1}(x) dx + O(ε^{2})H(x) dx.

We then take absolute values on both sides and apply (53) to obtain

|ℜ(e^{iθ}ν_{e^{itx}ϕ_{1}})| ≤ (1 + O_{t,ε}(\frac{1}{1 + x}))H(x) dx) ∗ cos(tx + θ)ϕ_{1}(x) dx + O(ε^{2})H(x) dx.

We can crudely bound

O_{t,ε}(\frac{1}{1 + x}))H(x) dx)∗cos(tx+θ)ϕ_{1}(x) dx = O_{t,ε}(\frac{1}{1 + x}H(x) dx∗ϕ_{1}(x) dx) = O_{t,ε,ϕ}(\frac{1}{1 + x})H(x) dx

to obtain

|ℜ(e^{iθ}ν_{e^{itx}ϕ_{1}})| ≤ ∥ cos(tx+θ)ϕ_{1}(x)∥_{L^{1}}H(x) dx+O_{t,ε,ϕ}(\frac{1}{1 + x})H(x) dx+O(ε^{2})H(x) dx.

Using (56), we thus have (if ε is small enough

|ℜ(e^{iθ}ν_{e^{itx}ϕ_{1}})| ≤ (1 − ε)H(x) dx + O_{t,ε,ϕ}(\frac{1}{1 + x})H(x) dx.

Taking supremum in θ, the claim follows. (The uniformity of the estimates when t is restricted to a compact set follows by the usual compactness arguments, noting we only need to choose finitely many approximations to the identity ψ_{t,ε}).

Let us fix ϕ_{1} and ε as in the above lemma, and suppress all further dependence of the O() and o() error terms on these parameters. The bound (55) only seems to have gained an ε or so over (53) (though admittedly we have also gained the freedom to modulate by an arbitrary frequency parameter e^{itx}). However we can use the Selberg symmetry formula, in the guise (54), to bootstrap (55) substantially:

Corollary 4.4. Define the convolution iterates ϕ_{2}, ϕ_{3}, … of ϕ_{1} by the formula ϕ_{k+1} := ϕ_{k} ∗ ϕ_{1}, thus the ϕ_{k} are a sequence of increasingly broad normalized bump functions. Then we have

|ν_{e^{itx}ϕ_{k}}| ≤ ((1 − ε)^{k} + O_{t,k}(\frac{log^{k−1}(1 + x)}{1 + x}))H(x) dx

for all t ∈ R and k ≥ 1. Again, the bounds in the error term are uniform in t when t is restricted to a compact set.

Proof From (13) we observe that e^{itx}ϕ_{k+1} dx = (e^{itx}ϕ_{k} dx) ∗ (e^{itx}ϕ_{1} dx). The claim now follows by (54), (19), and induction, observing that the convolution of O(1)H(x) dx with O_{t,k}(\frac{log^{k−1}(1+x)}{1+x}))H(x) dx is equal to O_{t,k}(\frac{log^{k}(1+x)}{1+x}))H(x) dx.

Remark 4.5. This is substantially stronger than what can be obtained using (51), especially given the presence of the oscillation e^{itx}, as the quantity (1 − ε)^{k} decays exponentially in k.

The shape of the convolution iterates ϕ_{k} can be controlled quite precisely by means of the central limit theorem; their profile approaches that of a Gaussian with total mass 1 and standard deviation ∼ k^{1/2}. In particular we have the bounds

∥ϕ_{k}∥_{L^{∞}} ∼ 1/k^{1/2}; ∥ϕ′_{k}∥_{L^{∞}} = O(1/k)  (57)

From these facts and the Fourier inversion formula, we can now obtain the desired decay estimates on ν_{ϕ}:

Proposition 4.6. For any test function ϕ, we have

ν_{ϕ} = o_{x→∞;ϕ}(1)H(x) dx.

Proof Let k ≥ 1 be a large integer, and let x_{k} be a point in R where ϕ_{k} attains its maximum, thus from (57) we have

ϕ_{k}(x_{k}) ∼ c/k^{1/2}.  (58)

From (57) again, we observe that

∥\frac{d}{dx}((ϕ_{k}(x) − ϕ_{k}(x_{k}))ϕ(x − x_{k}))∥_{L^{1}} = O_{ϕ}(1/k)

and hence by (51)

ν_{ϕ_{k}(x)ϕ(x−x_{k})} − ϕ_{k}(x_{k})ν_{ϕ(x−x_{k})} = O_{ϕ}(1/k)H(x) dx.  (59)

Since ϕ is a test function, it has a rapidly convergent Fourier expansion, and in particular it can be approximated by its Fejer integrals \frac{1}{2π} ∫_{−T}^{T} (1 − \frac{t}{T})ϕ̂(t)e^{itx} dt, where ϕ̂(t) := ∫_{R} ϕ(x)e^{−ixt} dx and T is a parameter to be chosen later. Since Fejer kernels are approximations to the identity we know that these Fejer integrals converge in W^{1,1} (for instance):

∥ϕ(x) − \frac{1}{2π} ∫_{−T}^{T} (1 − \frac{|t|}{T})ϕ̂(t)e^{itx} dt∥_{W^{1,1}} = o_{T →∞}(1)

In particular we have

∥ϕ_{k}(x)ϕ(x − x_{k}) − \frac{1}{2π} ∫_{−T}^{T} (1 − \frac{|t|}{T})ϕ̂(t)e^{−itx_{k}}e^{itx}ϕ_{k}(x) dt∥_{W^{1,1}} = o_{T →∞}(1).

Applying (51) we obtain

ν_{ϕ_{k}(x)ϕ(x−x_{k})} − \frac{1}{2π} ∫_{−T}^{T} (1 − \frac{|t|}{T})ϕ̂(t)e^{−itx_{k}}ν_{e^{itx}ϕ_{k}(x)} dt = o_{T →∞}(1)H(x) dx;

applying Corollary 4.4 (with t restricted to [−T, T]) we thus have

ν_{ϕ_{k}(x)ϕ(x−x_{k})} + O_{T,ϕ}((1 − ε)^{k})H(x) dx + O_{T,ϕ,k}(\frac{log^{k−1}(1 + x)}{1 + x}))H(x) dx.

Combining this with (59), (57) we obtain

ν_{ϕ(x−x_{k})} = [O_{ϕ}(1/k)+O_{T,ϕ}((1−ε)^{k})+O_{T,ϕ,k}(\frac{log^{k−1}(1 + x)}{1 + x}))+o_{T →∞}(1)]H(x) dx,

which upon shifting by x_{k} becomes

ν_{ϕ} = [O_{ϕ}(1/k) + O_{T,ϕ}((1 − ε)^{k}) + O_{T,ϕ,k}(\frac{log^{k−1}(1 + x)}{1 + x})) + o_{T →∞}(1)]H(x) dx.

For any σ > 0, the right-hand side can be made O(σ)H(x) dx by choosing T sufficiently large depending on σ, then k sufficiently large depending on T, ϕ, ε, σ, and then x sufficiently large depending on T, ϕ, k, σ. The claim follows.

Finally, we can now prove the prime number theorem in the weak form (9). The function e^{−x}H(x) is non-negative, bounded, has total mass 1, and is supported on the half-line. Thus for any σ > 0 one can find a normalized bump function ϕ_{σ} such that

e^{−x}H(x) ≥ (1 − σ)ϕ_{σ};

convolving this with the non-negative measure M_{Λ} we obtain

M_{Λ} ∗ e^{−x}H(x) dx ≥ (1 − σ)M_{Λ} ∗ ϕ_{σ}(x) dx.

But from Proposition 4.6 we have

M_{Λ}∗ϕ_{σ}(x) dx = H(x) dx∗ϕ_{σ}(x) dx+o_{x→∞;σ}(1)H(x) dx = H(x) dx+o_{x→∞;σ}(1)H(x) dx and hence

M_{Λ} ∗ e^{−x}H(x) dx ≥ (1 − σ)H(x) dx + o_{x→∞;σ}(1)H(x) dx.

Since σ > 0 is arbitrary, we thus have

M_{Λ} ∗ e^{−x}H(x) dx ≥ H(x) dx + o_{x→∞}(1)H(x) dx

which is one half of (9). To obtain the other half, we convolve the above inequality with M_{Λ} using (41) to obtain

M_{Λ} ∗ M_{Λ} ∗ e^{−x}H(x) dx ≥ xH(x) dx + o_{x→∞}(x)H(x) dx

and apply the Selberg symmetry formula (44) to obtain

(xM_{Λ}) ∗ e^{−x}H(x) dx ≤ xH(x) dx + o_{x→∞}(x)H(x) dx.

Applying the Leibnitz rule (12) and (47) (or (40)) we obtain

M_{Λ} ∗ e^{−x}H(x) dx ≤ H(x) dx + o_{x→∞}(1)H(x) dx

which gives the other half of (9). This proves the prime number theorem.

Remark 4.7. The above argument is based on the Selberg symmetry formula, where the error term is only O(1/x) smaller than the main term. Thus one cannot hope to obtain an estimate as strong as (8) by this method (unless one works out higher order terms in the symmetry formula). In the next section we present an alternate proof, based much more strongly in Fourier space than this argument, of the prime number theorem which does not use the Selberg symmetry formula and can give the bound (28).

Remark 4.8. From (9) and further manipulations of the type used in Lemma 2.6 one can now revisit that Lemma and improve some of the estimates, for instance we now have

M_{μ} ∗ H(x) dx = o_{x→∞}(1)H(x) dx

and

M_{μ} ∗ e^{−x}H(x) dx = o_{x→∞}(1)H(x) dx;

the equivalence of these estimates with the prime number theorem was first observed by Landau in his thesis. We leave the deduction of such estimates as exercises to the reader.

5. The Riemann zeta proof

We now give the Fourier analytic proof of the strong prime number theorem (28). It is convenient to smooth the weight function e^{−x}H(x) a little bit. Let 0 < r ≪ 1 be a small parameter, and let ψ_{r} be a normalized bump function supported on the interval [0, r]. We will prove the estimate

M_{Λ} ∗ e^{−x}H(x) dx ∗ ψ_{r}(x) dx = (1 + O_{M}(log^{M+7}(1/r)(1 + x)^{−M}))H(x) dx.(60)

At first glance this seems weaker than (28), since there is a logarithmic divergence when taking r → 0. However, we can remove this divergence by exploiting the non-negativity of M_{Λ}. Observe the pointwise inequalities

(1 − O(r))e^{−x+r}H(x − r) dx ≤ e^{−x}H(x) dx ∗ ψ_{r}(x) ≤ (1 + O(r))e^{−x}H(x) dx and hence (60) implies that

M_{Λ} ∗ e^{−x+r}H(x − r) dx ≤ (1 + O(r))(1 + O_{M}(log^{M+7}(1/r)(1 + x)^{−M}))H(x) dx

and

M_{Λ} ∗ e^{−x}H(x) dx ≥ (1 − O(r))(1 + O_{M}(log^{M+7}(1/r)(1 + x)^{−M}))H(x) dx.

If one shifts the first inequality by r and then combines it with the second, we obtain

M_{Λ} ∗ e^{−x}H(x) dx = (1 + O(r))(1 + O_{M}(log^{M+7}(1/r)(1 + x)^{−M}))H(x) dx

and the claim (28) then follows by setting r equal to a large negative power of (1 + x), and M to be large.

It remains to prove (60). We observe (cf. (22)) that

H(x) dx ∗ e^{−x}H(x) dx ∗ ψ_{r}(x) dx = (1 + O_{M}((1 + x)^{−M}))H(x) dx

and so it will suffice to show that

(M_{Λ} − H(x) dx) ∗ e^{−x}H(x) dx ∗ ψ_{r}(x) dx = O_{M}(log^{M+7}(1/r)(1 + x)^{−M})H(x) dx

We would like to prove this using the Fourier transform. However, there is a slight difficulty in that neither M_{Λ} or H(x) dx are finite measures. But by dominated convergence it will suffice to prove the estimate

(e^{(1−σ)x}M_{Λ} − e^{(1−σ)x}H(x) dx) ∗ e^{−x}H(x) dx ∗ ψ_{r}(x) dx = O_{M}(log^{M+7}(1/r)(1 + x)^{−M})H(x) dx (61)

for all 1 < σ < 1 + ε for some small ε, as long as the right-hand side bounds are uniform in σ. Observe that the measures e^{(1−σ)x}M_{Λ} and e^{(1−σ)x}H(x) dx are finite when σ > 1:

∫ e^{(1−σ)x}M_{Λ} = ∑_{n} \frac{Λ(n)}{n^{σ}} ≤ ∑_{n} \frac{log n}{n^{σ}} < ∞

and

∫ e^{(1−σ)x}H(x) dx = \frac{1}{σ − 1}.

The measure e^{(1−σ)x}M_{1} is similarly finite. In particular these measures have Fourier transforms. The Fourier transform of e^{(1−σ)x}H(x) dx is explicit:

{ \atop e^{(1−σ)x}H(x) dx}(t) = ∫_{1}^{∞} \frac{dn}{n^{σ+it}} = \frac{1}{σ + it − 1}.  (62)

The Fourier transform of e^{(1−σ)x}M_{1} is just the Riemann zeta function:

{ \atop e^{(1−σ)x}M_{1}}(t) = ∫ e^{−ixt}e^{(1−σ)x}M_{1}(x) = ∑_{n=1}^{∞} \frac{1}{n^{σ+it}} =: ζ(σ + it).  (63)

In analogy with this, we define ζ_{Λ}(σ+it) to be the Fourier transform of e^{(1−σ)x}M_{Λ}:

ζ_{Λ}(σ + it) := { \atop e^{(1−σ)x}M_{Λ}}(t) = ∫ e^{−ixt}e^{(1−σ)x}M_{Λ}(x) = ∑_{n=1}^{∞} \frac{Λ(n)}{n^{σ+it}} . (64)

By the Fourier inversion formula and (64), (62), the left-hand of (61) is

\frac{1}{2π} ∫_{R}(ζ_{Λ}(σ + it) − \frac{1}{σ + it − 1})\frac{1}{1 + it}ψ̂_{r}(t)e^{itx} dt.

To prove (61), it thus suffices by repeated integration by parts to prove the derivative estimates

\frac{d^{k}}{dt^{k}} ((ζ_{Λ}(σ+it)−\frac{1}{σ + it − 1})\frac{1}{1 + it}ψ̂_{r}(t)) = O_{k}(log^{k+6}(2+|t|)(1+|t|)^{−1}(1+r|t|)^{−100}),

since the right-hand side has an L^{1} norm of O(log^{k+7}(1/r)) in t. Since ψ_{r} is an approximation to the identity at scale r, we have ψ̂_{r}(t) = (1+r|t|)^{−100}, and similarly for all its derivatives (in fact each derivative gains an additional factor of r). Thus by the Leibnitz rule it will suffice to prove the estimate

\frac{d^{k}}{dt^{k}} (ζ_{Λ}(σ + it) − \frac{1}{σ + it − 1}) = O_{k}(log^{k+6}(2 + |t|)).  (65)

To prove (65) we must get some control on the von Mangoldt function Λ. As in the elementary proof of the prime number theorem, the key is (25). By combining this identity with (13) we obtain an ODE linking ζ with ζ_{Λ}:

ζ_{Λ}(σ + it)ζ(σ + it) = { \atop e^{(1−σ)x}xM_{1}}(t) = −\frac{d}{dσ} { \atop e^{(1−σ)x}M_{1}}(t) = −\frac{d}{dσ} ζ(σ + it).(66)

The analogue of this corresponding to (19) is the identity

\frac{1}{σ + it − 1} \frac{1}{σ + it − 1} = −\frac{d}{dσ} \frac{1}{σ + it − 1}.  (67)

This suggests the following strategy of proof for (65): first we quantify the heuristic (18), which in Fourier space means that we give estimates demonstrating that ζ(σ + it) is close to \frac{1}{σ+it−1}, and then use (66) and (67) to obtain (65). There is an obstruction however, which is that in order to use (66) effectively we need to prevent ζ(σ + it) from vanishing, and thus need lower bounds on |ζ(σ + it)| which are uniform in σ. Fortunately this can be done by once again exploiting the non-negativity of the von Mangoldt function Λ(n).

We turn to the details. We begin by showing that ζ(σ + it) is close to \frac{1}{σ+it−1}.

Lemma 5.1. For 1 < σ < 2, t ∈ R and k ≥ 0 we have the estimates

\frac{d^{k}}{dt^{k}} (ζ(σ + it) − \frac{1}{σ + it}) = O_{k}(log^{k+1}(2 + |t|)).  (68)

Proof From (14), (17) we have

e^{(1−σ)x}H(x) dx − e^{(1−σ)x}M_{1}(x) = ∑_{n=1}^{∞} ∫_{n}^{n+1} e^{−sx}(δ(x − log n′) − δ(x − log n) dn′,

and hence after taking Fourier transforms

ζ(σ + it) − \frac{1}{σ + it} = ∑_{n=1}^{∞} ∫_{n}^{n+1} e^{−(s+it) log n′} − e^{−(s+it) log n} dn′.

Differentiating this k times in t, we obtain

|\frac{d^{k}}{dt^{k}} (ζ(σ +it)− \frac{1}{σ + it})| ≤ ∑_{n=1}^{∞} ∫_{n}^{n+1} |e^{−(σ+it) log n′} log^{k} n′ −e^{−(σ+it) log n} log^{k} n| dn′.

We have two bounds on the integrand. On the one hand, from the triangle inequality we have

|e^{−(s+it) log n′} log^{k} n′−e^{−(σ+it) log n} log^{k} n| ≤ |e^{−(σ+it) log n′} log^{k} n′|+|e^{−(σ+it) log n} log^{k} n| = O_{k}(n^{−σ} log^{k} n).

On the other hand, from the fundamental theorem of calculus, we obtain

| log^{k} ne^{−(σ+it) log n′} − (log^{k} n)e^{−(σ+it) log n}| ≤ ∫_{n}^{n′} |\frac{d}{dm}(e^{−(σ+it) log m} log^{k} m)| dm

= O_{k}(∫_{n}^{n′} |σ + it|m^{−σ−1} log^{k} m dm)
= O_{k}((1 + |t|) log^{k} nn^{−σ−1}).

We thus have

|\frac{d^{k}}{dt^{k}} (ζ(σ + it) − \frac{1}{σ + it}) = O_{k}(∑_{n=1}^{∞} min(n^{−σ} log^{k} n, (1 + |t|) log^{k} nn^{−σ−1})).

Splitting into the regions n ≤ t and n ≥ t (and estimating n^{−σ} crudely by n^{−1}) we obtain the result.

Remark 5.2. The above argument shows in fact that ζ(σ + it) − \frac{1}{σ+it−1}) could be continued analytically to the region σ > 0 (this can also be seen by modulating (32)). A refinement of the above arguments in fact allow this function to be continued to the entire complex plane.

Next, we need to prevent ζ(σ + it) from vanishing in the limit σ → 1. As in the elementary proof, the fact that Λ is non-negative and real is essential. We shall exploit this by the following lemma (which plays a role here roughly analogous to the role of (56) in the elementary argument):

Lemma 5.3. For any σ > 1 and t ∈ R we have

ℜ(3ζ_{Λ}(σ) + 4ζ_{Λ}(σ + it) + ζ_{Λ}(σ + 2it)) ≥ 0.

Proof The left-hand side can be expanded using (64) as

∑_{n=2}^{∞} \frac{Λ(n)}{n^{s}}(3 + 4 cos(t log n) + cos(2t log n)) = ∑_{n=2}^{∞} \frac{Λ(n)}{n^{s}}2(1 + cos(t log n))^{2}

and the claim follows.

Corollary 5.4 (Monotonicity formula). For any fixed t ∈ R, the quantity

|ζ(σ)|^{3}|ζ(σ + it)|^{4}|ζ(σ + 2it)|

is decreasing in σ for σ > 1.

Proof From (67) and the product rule we have

\frac{d}{dσ} (ζ(σ)^{3}ζ(σ+it)^{4}ζ(σ+2it)) = −(ζ(σ)^{3}ζ(σ+it)^{4}ζ(σ+2it))(3ζ_{Λ}(σ)+4ζ_{Λ}(σ+it)+ζ_{Λ}(σ+2it))

and the claim then follows from the previous lemma.

We can use this monotonicity formula to obtain a crucial lower bound for ζ(σ + it):

Lemma 5.5. There exists absolute constants 0 < ε < 1 and c > 0 such that

|ζ(σ + it)| ≥ \frac{c}{|t| log^{4}(2 + |t|)}  (69)

for all t ∈ R and 1 < σ < 1 + ε. In particular, ζ(σ + it) is non-zero.

Proof When |t| < ε the claim will follow directly from Lemma 5.1 if ε and c are chosen small enough, so let us suppose |t| ≥ ε instead. From (63) and dominated convergence we have the limit

lim_{σ′→+∞} ζ(σ′ + it) = 1 for all t ∈ R

so from the above monotonicity formula we have the lower bound

|ζ(σ′)|^{3}|ζ(σ′ + it)|^{4}|ζ(σ′ + 2it)| ≥ 1 for all σ′ > 1.

Now let us specialize to the case 1 < σ′ < 1 + ε. From Lemma 5.1 we have

ζ(σ′) = O_{ε}(\frac{1}{σ′ − 1}); ζ(σ + 2it) = O_{ε}(log(2 + |t|)),

and hence

|ζ(σ′ + it)| ≥ c_{ε}(σ′ − 1)^{3/4} log^{−1/4}(2 + |t|).  (70)

Set σ_{0} := 1 + \frac{c}{log^{5}(2+|t|)} for some small constant c > 0. If σ > σ_{0} then the above estimate yields (69) simply by setting σ′ equal to σ, so we may assume 1 < σ < σ_{0}. By Lemma 5.1 (and the complex analyticity of ζ) we have

|\frac{d}{dσ̃} ζ(σ̃ + it)| = |\frac{d}{dt}ζ(σ̃ + it)| = O_{ε}(log(2 + |t|)) for all σ ≤ σ̃ ≤ σ_{0}

and so by the fundamental theorem of calculus we have

ζ(σ + it) = ζ(σ_{0} + it) + O(σ_{0} − 1)O_{ε}(log(2 + |t|)).

The claim now follows by applying (70) with σ′ := σ_{0} and ensuring the constant c used to define σ_{0} is suitably small.

Remark 5.6. It is of course of tremendous interest to see to what extend lower bounds on ζ can be pushed beyond the line σ = 1; this would for instance allow for much stronger control on the error estimate in (28). The Lemma above, combined with a modification of Lemma 5.1 beyond the σ = 1 line, does allow for a small “zero-free region” for ζ to the left of σ = 1, but of course we are nowhere near such conjectures as the Riemann hypothesis, which asserts that ζ remains zero-free for all σ > 1/2.

We are now ready to prove (65). From (69), Lemma 5.1, and the quotient rule we have

\frac{d^{k}}{dt^{k}} \frac{1}{ζ(σ + it)} = O_{k}(log^{4+k}(2 + |t|))

while from (66), (67) and some algebra we have

ζ_{Λ}(σ + it) − \frac{1}{σ + it − 1} = − (ζ(σ + it) − \frac{1}{σ + it − 1}) + \frac{1}{ζ(σ + it)}[(ζ(σ + it) − \frac{1}{σ + it − 1})^{2}

− \frac{d}{dσ} (ζ(σ + it) − \frac{1}{σ + it − 1})].

The claim (65) then follows from Lemma 5.1 and the Leibnitz rule.

6. Dirichlet’s theorem

Now we investigate the primes modulo q for some fixed integer q > 1. Consider the set Z_{q}^{∗}, which are the multiplicatively invertible elements of Z/qZ. This is a finite abelian multiplicative group with |Z_{q}^{∗}| = ϕ(q) elements, (where ϕ(q) is the number of integers in {1, …, q} which are coprime to q), and so (by Pontryagin duality) there exist ϕ(q) distinct (and pairwise orthogonal) characters χ : Z_{q}^{∗} → C on this group; recall that a character is a non-trivial multiplicative function, i.e. a function which is not identically zero and such that χ(nm) = χ(n)χ(m) for all n, m ∈ Z_{q}^{∗}. Note that we have |χ(n)| = 1 for all n ∈ Z_{q}^{∗}. Among all the ϕ(q) characters there is the principal character χ_{0} : Z_{q}^{∗} → C defined by χ_{0}(n) := 1 for all n ∈ Z_{q}^{∗}; all other characters shall be called non-principal.

Every character χ : Z_{q}^{∗} → C can be extended canonically to a function on Z, which we shall also denote (by abuse of notation) as χ, defined by setting χ(n) := χ(n mod q) if n is coprime to q and χ(n) := 0 otherwise. Note that χ is still multiplicative (χ(nm) = χ(n)χ(m) for all n, m ∈ Z) and is now also periodic modulo q. Also note that |χ(n)| = 1 when n is coprime to q aand |χ(n)| = 0 otherwise (or in other words |χ(n)| = χ_{0}(n) for all n).

Given any character χ, we define the associated Dirichlet measure M_{χ} by

M_{χ}(x) := ∑_{n} \frac{χ(n)}{n}δ(x − log n).

Since χ is bounded in magnitude by χ_{0}, we have

|M_{χ}| ≤ M_{χ_{0}} ≤ M_{1}.

We can also define the associated Dirichlet-von Mangoldt measure M_{χΛ} by

M_{χΛ}(x) := ∑_{n} \frac{χ(n)Λ(n)}{n}δ(x − log n).

By repeating the proof of (25) we have

M_{χ} ∗ M_{χΛ} = xM_{χ}  (71)

Now we see what happens when we convolve these measures with the Heaviside function.

Lemma 6.1. Let χ be a non-principal character. Then there exist complex numbers L(1, χ) and L′(1, χ) such that

M_{χ} ∗ H(x) dx = (L(1, χ) + O_{χ}(e^{−x}))H(x) dx  (72)

and

(xM_{χ}) ∗ H(x) dx = (−L′(1, χ) + O_{χ}(xe^{−x}))H(x) dx.

Also, for any 0 < α ≤ 1, we have

M_{χ} ∗ e^{−αx}H(x) dx = O_{χ,α}(e^{−αx})H(x) dx  (73)

and

(M_{χ_{0}} − \frac{ϕ(q)}{q}H(x) dx) ∗ e^{−αx}H(x) dx = O_{q,α}(e^{−αx})H(x) dx.  (74)

Proof The first statement is equivalent to the assertion that

∑_{n≤N} \frac{χ(n)}{n} = L(1, χ) + O_{χ}(1/N)

as N → ∞. Without loss of generality we may take N to be a multiple of q, N = qM, since the error incurred in doing so is O_{χ}(1/N). But then we can use the periodicity of χ modulo q (and the fact that χ is orthogonal to χ_{0} and hence ∑_{j=1}^{q} χ(j) = 0) to write

∑_{n≤N} \frac{χ(n)}{n} = ∑_{m≤M} ∑_{j=1}^{q} \frac{χ(j)}{mq − q + j}

= ∑_{m<M} ∑_{j=1}^{q} χ(j)(1mq − q + j − \frac{1}{mq}).

The expression ∑_{j=1}^{q} χ(j)(\frac{1}{mq−q+j} − \frac{1}{mq}) has magnitude O_{q}(1/m^{2}), and so the summation is of the form L(1, χ)+O_{χ}(1/M) = L(1, χ)+O_{χ}(1/N) for some L(1, χ), as desired.

The second assertion is similarly equivalent to

∑_{n≤N} \frac{χ(n) log n}{n} = −L′(1, χ) + O_{χ}(log N/N)

and is proven in the same way, noting that \frac{log(mq−q+j)}{mq−q+j} − \frac{log(mq)}{mq} = O_{q}(log m/m^{2}) for m ≥ 2. The third assertion is equivalent to

∑_{n≤N} \frac{χ(n)}{n^{1−α}} = O_{χ,α}(1)

and is again proven similarly, now noting that \frac{1}{(mq−q+j)^{1−α}} −\frac{1}{(mq)^{1−α}} = O_{q}(1/m^{2−α}). Finally, for the last assertion, we are trying to show that

∑_{n≤N} \frac{χ_{0}(n)}{n^{1−α}} − \frac{ϕ(q)}{q} ∫_{1}^{N} \frac{dx}{x^{1−α}} = O_{χ,α}(1).

Again we let N = qM, and discard the low values of n to avoid technicalities, and end up trying to show that

∑_{2≤m≤M}(∑_{j=1}^{q} \frac{χ_{0}(j)}{(mq − q + j)^{1−α}} − \frac{ϕ(q)}{q} ∫_{mq−q}^{q} \frac{dx}{x^{1−α}} = O_{χ,α}(1).

the new feature is that ∑_{j=1}^{q} χ_{0}(q) is equal to ϕ(q) rather than equal to zero, but the term of ϕ(q)/m^{1−α} generated by this is essentially cancelled by the integral term, and we argue as before.

Corollary 6.2. If χ is a non-principal character and L(1, χ) is non-zero, then

M_{χΛ} ∗ H(x) dx = O_{χ}(1)H(x) dx  (75)

Proof If we convolve both sides of (71) with H(x) dx and use the previous lemma, we obtain

L(1, χ)(M_{χΛ} ∗ H(x) dx) + M_{χΛ} ∗ O_{χ}(e^{−x})H(x) dx = O_{χ}(1)H(x) dx.

But by (40) we have M_{χΛ} ∗ O_{χ}(e^{−x})H(x) dx. Since L(1, χ) is assumed to be non-zero, the claim (75) follows.

To use this corollary, it is thus of interest to know when L(1, χ) is non-zero; it turns out that this is indeed the case for all non-principal characters χ. To prove this, let us convolve all the Dirichlet measures together^{7}:

M_{(q)} := ⋆_{χ}M_{χ},

where ⋆_{χ} represents convolution as χ ranges over all characters modulo q (including the principal character χ_{0}. We observe two basic facts about this measure; firstly, that it is positive, and secondly, that one can recover ∏_{χ:χ≠χ_{0}} L(1, χ) from the asymptotic averages of M_{(q)}.

Lemma 6.3 (Positivity of M^{(q)}). . M_{(q)} is a non-negative measure, and in fact we have

M_{(q)} ≥ ∑_{n≥1:n coprime to q;n=m^{ϕ(q)} for some m∈Z} \frac{1}{n}δ(x − log n).  (76)

Remark 6.4. The mere fact that M_{(q)} is positive and not identically zero is already enough to show that at most one of the L(1, χ) can be zero (as otherwise one can show that the total measure of M_{(q)} must vanish); this combined with conjugation symmetry can show that L(1, χ) does not vanish for any complex character. However, to show that the real characters also do not vanish seems to require exploiting further positivity properties of M_{(q)}.

7The Fourier transform of this function is essentially the Riemann zeta function associated to the cyclotomic number field generated by the q^{th} roots of unity; indeed there is an extremely rich theory of zeta-functions and L-functions associated to any number field, which we will not discuss here.

Proof It is now convenient to employ the Euler product (actually, an Euler convolution for us, since we are working in physical space rather than frequency space) formulation of Dirichlet measures. Observe from the unique factorization theorem (Theorem 1.1) and the multiplicativity of χ(n) (and hence χ(n)/n) that

χ(n)/n = ∏_{p prime} χ^{c_{p}(n)}(p)/p^{c_{p}(n)}

where c_{p}(n) is the number of times p divides into n. In particular we have

χ(n)/nδ(x − log n) = ⋆_{p prime}χ^{c_{p}(n)}(p)/p^{c_{p}(n)}δ(x − c_{p}(n) log p).

Summing this over all n (which essentially means letting c_{p} range freely over all positive integers, we obtain the formula

M_{χ} = ⋆_{p prime} ∑_{j=0}^{∞} χ^{j}(p)/p^{j}δ(x − j log p).

Note that this convolution is well-defined on any compact interval, as only finitely many of the j log p are involved in that case. Note that when p divides q, we have χ(p) = 0 and so the summation is trivial in that case, so we can restrict to those p coprime to q. Convolving all the χ together we obtain

M_{(q)} = ⋆_{p prime:p|̸q}⋆_{χ} ∑_{j=0}^{∞} χ^{j}(p)/p^{j}δ(x − j log p).

It will then suffice to show that

⋆_{χ} ∑_{j=0}^{∞} \frac{χ^{j}(p)}{p^{j}}δ(x − j log p) ≥ ∑_{j≥0:ϕ(q)|j} \frac{1}{p^{j}} δ(x − j log p)

for all primes p not dividing q, as another application of the unique factorization theorem shows that

⋆_{p prime:p|̸q} ∑_{j≥0:ϕ(q)|j} \frac{1}{p^{j}} δ(x−j log p) = ∑_{n≥1:n coprime to q;n=m^{ϕ(q)} for some m∈Z} \frac{1}{n}δ(x−log n).

Fix p. We will in fact prove the identity

⋆_{χ}(∑_{j=0}^{∞} \frac{χ^{j}(p)}{p^{j}}δ(x − j log p)) = ( ∑_{j≥0:ord_{Z^{∗}_{q}} (p)|j} \frac{1}{p^{j}} δ(x − j log p))^{⋆ϕ(q)/ord_{Z^{∗}_{q}} (p)},

where f^{⋆n} denotes the n-fold convolution of f with itself, and ord_{G}(g) is the order of an element g in a group G (i.e the least positive integer n such that g^{n} is the identity). To prove this, we take Fourier transforms, to rewrite the identity as

∏_{χ}(∑_{j=0}^{∞} \frac{χ^{j}(p)}{p^{j}}e^{2πiξj log p}) = ( ∑_{j≥0:ord_{Z^{∗}_{q}} (p)|j} \frac{1}{p^{j}} e^{2πiξj log p}))^{ϕ(q)/ord_{Z^{∗}_{q}} (p)};

writing z := e^{2πij log p}/p, this becomes

∏_{χ}(∑_{j=0}^{∞} χ^{j}(p)z^{j}) = ( ∑_{j≥0:ord_{Z^{∗}_{q}} (p)|j} z^{j})^{ϕ(q)/ord_{Z^{∗}_{q}} (p)},

which on evaluating the geometric series and then inverting becomes

∏_{χ}(1 − χ(p)z) = (1 − z^{ord_{Z^{∗}_{q}} (p)})^{ϕ(q)/ord_{Z^{∗}_{q}} (p)}.

But observe that both sides are polynomials in z, which equal 1 at the origin. The right-hand side has a zero of order ϕ(q)/ord_{Z_{q}^{∗}}(p) at every ord_{Z_{q}^{∗}}(p)^{th} root of unity; meanwhile, the left-hand side has a zero at each value of χ(p)^{−1}. But a little group theory (or Fourier analoysis on Z_{q}^{∗}, or Galois theory) shows that the ϕ(q) numbers χ(p)^{−1} are ord_{Z_{q}^{∗}}(p)^{th} roots of unity and must be evenly distributed among such roots, and the claim follows.

Lemma 6.5 (Asymptotics of M^{(q)}). . For any 0 < α < 1 we have

M_{(q)} ∗ \frac{x^{ϕ(q)}}{ϕ(q)!}e^{−αx}H(x) dx = (α^{ϕ(q)} \frac{ϕ(q)}{q} ∏_{χ:χ≠χ_{0}} L(1, χ) + O_{q}(x^{ϕ(q)}e^{−αx}))H(x) dx

Proof Observe that

\frac{x^{n}}{n!} H(x) dx ∗ H(x) dx = \frac{x^{n+1}}{n!} H(x) dx

and hence by induction and (13)

\frac{x^{ϕ(q)}}{ϕ(q)!}e^{−αx}H(x) dx = (e^{−αx}H(x) dx)^{⋆ϕ(q)}  (77)

and hence (by associativity of convolution)

M_{(q)} ∗ \frac{x^{ϕ(q)−1}}{ϕ(q)!} e^{−αx}H(x) dx = ⋆_{χ}(M_{χ} ∗ e^{−αx}H(x) dx).

We extract out the χ_{0} component of this, and use (74), to rewrite this as

⋆_{χ≠χ_{0}}(M_{χ} ∗ e^{−αx}H(x) dx) ∗ (α\frac{ϕ(q)}{q}H(x) dx + O_{q,α}(e^{−αx})H(x) dx).

The error term can be treated using (73) and (77), so it suffices to show that

(⋆_{χ≠χ_{0}}M_{χ}∗e^{−αx}H(x) dx)∗H(x) dx = α^{ϕ(q)−1} ∏_{χ:χ≠χ_{0}} L(1, χ)+O_{q}(x^{ϕ(q)}e^{−αx}))H(x) dx

We then look at each of the χ in turn and use (72) to replace each M_{χ} ∗ H(x) dx with L(1, χ)H(x) dx plus a remainder (which can be absorbed using (73) and (77)). Eventually the left-hand side is rewritten as

(⋆_{χ≠χ_{0}}L(1, χ)e^{−αx}H(x) dx) ∗ H(x) dx + O_{q}(x^{ϕ(q)}e^{−αx}))H(x) dx

and we are reduced to showing that

(e^{−αx}H(x) dx)^{⋆ϕ(q)−1} ∗ H(x) dx = α^{ϕ(q)−1}H(x) dx + O_{q}(x^{ϕ(q)}e^{−αx}))H(x) dx.

But this follows from the estimate

e^{−αx}H(x) dx ∗ H(x) dx = αH(x) dx + O_{q}(e^{−αx})H(x) dx

and an induction argument (using (77)).

Corollary 6.6. L(1, χ) ≠ 0 for any non-principal character χ.

Proof Suppose for contradiction that least one of the L(1, χ) vanished. Then by the previous lemma we have

M_{(q)} ∗ \frac{x^{ϕ(q)}}{ϕ(q)!}e^{−αx}H(x) dx = O_{q}(x^{ϕ(q)}e^{−αx}))H(x) dx

for all 0 < α < 1. In particular, from (76) we have

( ∑_{n≥1:n coprime to q;n=m^{ϕ(q)} for some m∈Z} \frac{1}{n}δ(x−log n))∗\frac{x^{ϕ(q)}}{ϕ(q)!}e^{−αx}H(x) dx = O_{q}(x^{ϕ(q)}e^{−αx}))H(x) dx.

We rewrite this as

∑_{n≤N:n coprime to q;n=m^{ϕ(q)} for some m∈Z} \frac{log^{ϕ(q)}(N/n)}{n^{1−α}} = O_{q}(log^{ϕ(q)}(N)).

Changing variables n = m^{ϕ(q)} and N = M^{ϕ(q)}, this becomes

∑_{n≤M:m coprime to q} \frac{log^{ϕ(q)}(M/m)}{m^{ϕ(q)(1−α)}} = O_{q}(log^{ϕ(q)}(M)).

But this clearly fails for α > 1 − 1/ϕ(q) (in fact it also fails at the endpoint^{8} α = 1 − 1/ϕ(q)), as the left-hand side then grows like M^{1−ϕ(q)(1−α)}.

Corollary 6.7 (Dirichlet’s theorem). For any k ∈ Z we have

∑_{n=k mod q:n≤N} \frac{Λ(n)}{n} = \frac{χ_{0}(k)}{ϕ(q)} log N + O_{q}(1).

Proof We may assume that k is coprime to q (i.e. χ_{0}(k) = 1) since the claim is trivial otherwise. From the Fourier inversion formula on Z_{q}^{∗} we have

∑_{n=k mod q:n≤N} \frac{Λ(n)}{n} = \frac{1}{ϕ(q)} ∑_{χ} ∑_{n≤N} \frac{χ(n)\overline{χ(q)}Λ(n)}{n}.

The contributions of the non-principal characters χ ≠ χ_{0} are acceptable from (75), and so

∑_{n=k mod q:n≤N} \frac{Λ(n)}{n} = \frac{1}{ϕ(q)} ∑_{n≤N} \frac{χ_{0}(n)Λ(n)}{n} + O(1).

But the right-hand side is acceptable from (74).

Remark 6.8. By exploiting the positivity of M_{(q)} (as one did with M_{1} in the previous section) one can in fact show that the Fourier transform M_{(q)} has no zeroes whatsoever, and hence neither do any of its convolution factors M_{χ}. This can be used to obtain a prime number theorem version of Dirichlet’s theorem, for instance

|\{p prime : p = k mod q, p ≤ N\}| = \frac{χ_{0}(k)}{ϕ(q)} \frac{N}{log N} + O_{q}(1).

The error term can be sharpened up somewhat (and the dependence on q made more precise), yielding the Siegel-Walfisz theorem. However, there is a serious issue in that the zero-free region for L-functions is not as good as that for the Riemann zeta function; instead, there is a Siegel region which is similar to region similar to the zero-free region for the zeta function, but instead of being zero-free, all that is known is that this region contains at most one zero (known as a Siegel zero). While such a result is already very useful, it is a major open problem to determine whether Siegel zeroes actually exist (the generalized Riemann Hypothesis asserts that they do not).

8By convolving fewer of the Dirichlet measures together, one can obtain failure sooner, for instance at α = 1/2 by considering a single real character convolved with the principal character.

7. Functional equation

The log-integer measure M_{1} obeys some interesting convolution identities:

Lemma 7.1. For any α > 0 we have

M_{1} ∗ e^{−x}e^{−αe^{−x}} dx = e^{−x} \frac{e^{−αe^{−x}}}{1 − e^{−αe^{−x}}} dx

and

M_{1} ∗ e^{−x}e^{−αe^{−2x}} dx = \frac{1}{2}e^{−x}(θ(\frac{α}{π}e^{−2x}) − 1) dx

where θ is the θ-function

θ(x) := ∑_{n∈Z} e^{−πn^{2}x}.

Remark 7.2. Admittedly, the functions e^{−x}e^{−αe^{−x}} dx and e^{−x}e^{−αe^{−2x}} dx are not half-line measures, but they decay so rapidly on the left half-line that there is no issue with convergence. The freedom to vary α is actually not all that exciting, as it basically corresponds to translating these measures by an amount depending on α.

Proof The first identity can be rewritten as

∑_{n≥1} \frac{1}{n}e^{−(x−log n)}e^{−αe^{−(x−log n)}} = e^{−x} \frac{e^{−αe^{−x}}}{1 − e^{−αe^{−x}}}

which we can simplify to

∑_{n≥1} e^{−nαe^{−x}} = \frac{e^{−αe^{−x}}}{1 − e^{−αe^{−x}}} .

But this is just the geometric series formula. Simliarly, the second identity can be rewritten as

∑_{n≥1} \frac{1}{n}e^{−(x−log n)}e^{−αe^{−2(x−log n)}} = \frac{1}{2}e^{−x}(θ(\frac{α}{π}e^{−2x}) − 1)

which simplifies to

∑_{n≥1} e^{−n^{2}αe^{−x}} = \frac{1}{2}(θ(\frac{α}{π}e^{−2x}) − 1).

But this is clear from the definition of the theta function.

Recall from Poisson summation that

θ(x) = \frac{1}{\sqrt{x}}θ(1/x).

Thus if we define the function

F (x) dx := M_{1} ∗ e^{−x}e^{−πe^{−2x}} dx = \frac{1}{2}e^{−x}(θ(e^{−2x}) − 1) dx  (78)

then we obtain the symmetry

F (−x) = \frac{1}{2}e^{x}(θ(e^{2x}) − 1)

= \frac{1}{2}e^{x}(\frac{1}{e^{x}} θ(e^{−2x}) − 1)

= e^{x}F (x) + \frac{1}{2}e^{x} − \frac{1}{2}.

Formally, this means that for any complex number s, the measures F (x)e^{−(s−1)x} dx and F (−x)e^{−sx} dx differ by pure exponential factors (which correspond in Fourier-Laplace space to poles (delta functions) at s = 0 and s = 1 respectively). Ignoring these factors, we formally obtain the identity

∫_{R} F (x)e^{−(s−1)x} dx = ∫_{R} F (−x)e^{−sx} dx = ∫_{R} F (x)e^{sx} dx

so if we set Ξ(s) := ∫_{R} F (x)e^{−(s−1)x} dx then we have the symmetry

Ξ(s) = Ξ(1 − s).  (79)

On the other hand, from (78) and (13) we formally have

F (x)e^{−(s−1)x} dx = e^{−(s−1)x}M_{1} ∗ e^{−sx}e^{−πe^{−2x}} dx

and so (formally) on integrating in x we obtain

Ξ(s) = (∫ e^{−(s−1)x}M_{1})(∫_{R} e^{−sx}e^{−πe^{−2x}} dx).

The first integral is just the Riemann zeta function ζ(s). The second one, after a change of variables t = πe^{−2x}, becomes

\frac{1}{π^{s/2}} ∫_{0}^{∞} t^{s/2−1}e^{−t} dt = \frac{1}{π^{s/2}} Γ(s/2)

and hence

Ξ(s) = \frac{1}{π^{s/2}} Γ(s/2)ζ(s).

Combining this with (79) gives the well-known functional equation for the zeta function. The formality in the above derivations can be removed by developing a theory of Fourier-Laplace transforms of measures which are rapidly decreasing in both directions modulo a finite number of pure exponentials (their Fourier-Laplace transform then becomes a meromorphic function with a finite number of simple poles); we omit the details.

Acknowledgements I thank Peter Sarnak for helpful comments.

References

[1] A. Beurling, Analyse de la loi asymptotique de la distribution des nombres premiers généralisés, Acta Math., 68 (1937), 255-291.

[2] H.G. Diamond, J. Stening, An elementary proof of the prime number theorem with a remainder term, Invent. Math. 11 (1970), 199–258.

[3] P. Erdös, On a new method in elementary number theory which leads to an elementary proof of the prime number theorem, Proc. Nat. Acad. Sci. 35 (1948), 374–384.

[4] A. Hildebrand, The prime number theorem via the large sieve, Mathematika 33 (1986), 23–30.

[5] P. Sarnak, Nonvanishing of L-functions on ℜ(s) = 1, In honour of P. Shalika on his 60th birthday, preprint.

[6] A. Selberg, An elementary proof of the Prime Number Theorem, Ann. Math. 50 (1948), 305–313.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu