Why are complex numbers necessary to prove the Prime Number Theorem?

Question

The standard proof of the Prime Number Theorem requires taking into consideration that there are no zeroes of the Riemann Zeta function in which the real part equals one. But consider the following argument:

The probability that a number less than X is prime $\pi(X)/X$ is approximately $\Pi_{p<X} (1-1/p)$ (this is for the same reason that the Sieve of Eratosthenes works), which is approximately $1/\Sigma_{n=1}^X 1/n$, which is approximately $1/\log X$. Hence, $\pi(X)$ is approximately $X/\log X$.

This doesn't use complex numbers, but it gives a good reason to believe the Prime Number Theorem. Why do complex numbers (which seem to come from nowhere) make this argument rigorous?

Answer 1

Here is a heuristic which I find useful for ruling out easy proofs of the PNT. Consider a set of positive integers $P$ with the following properties: Between $2^{2k-1}$ and $2^{2k}$, there are roughly $a \frac{2^{2k-1}}{(2k-1) \log 2}$ elements of $P$ and, between $2^{2k}$ and $2^{2k+1}$, there are roughly $b \frac{2^{2k}}{(2k) \log 2}$ elements of $P$.

Now, if $P$ is the primes, then $a=b=1$. Suppose instead that $a=1 + c$ and $b=1 - c$, for some small constant $c$.

Then $\prod_{p \in P} (1-p^{-s})^{-1}$ has a simple pole at $s=1$, with residue $1$. The sum $\sum_{p \in P,\ p \leq N} 1/p$ grows like $\log \log N$. And, regarding your specific question, $\prod_{p \in P,\ p \leq N} (1-1/p) \approx 1/\log N$.¹ So these properties can't distinguish $P$ from the set of primes.

However, the PNT does not hold for $P$. Let $\pi_P(N)$ be the number of elements of $P$ which are $\leq N$. Then, if $N=2^{2k}$, then $$\frac{\pi_P(N)}{N/\log N} = (2k) \left( a \frac{2^{2k-1}}{2k-1} + b \frac{2^{2k-2}}{2k-2} + a \frac{2^{2k-3}}{2k-3} + \cdots \right)$$ $$\approx a \left( \frac{1}{2} + \frac{1}{8} + \cdots \right) + b \left( \frac{1}{4} + \frac{1}{16} + \cdots \right) = (2/3) a + (1/3) b. $$ Similarly, if $N=2^{2k+1}$, then $$\frac{\pi_P(N)}{N/\log N} \approx (2/3) b + (1/3) a.$$

So the ratio of $\pi_P(N)/(N/\log N)$ does not approach a well defined ratio. Any proof of the PNT must use facts about the primes which distinguish them from $P$.

¹ There is also a second issue here. It turns out that $$\prod_{p\ \mbox{Prime},\ p \leq N} \left(1-\frac{1}{p} \right) \sim \frac{e^{- \gamma}}{\sum_{n \leq N} 1/n},\ \mbox{not}\ \sim \frac{1}{\sum_{n \leq N} 1/n}.$$ So you would have to explain why that $e^{- \gamma}$ disappears.

Answer 2

They're not! This is the theorem of Selberg and Erdős! Look up the "elementary proof of the Prime Number Theorem". This link is clicky and wonderful. (It is also majestic, so please do click it).

Answer 3

If you try to make the argument you describe rigorous in a naive way, then the error terms rapidly become too big for it to actually work, and this is why nobody uses the Legendre sieve to count primes. This is a well-known problem in sieve theory; see, for example, this blog post by Terence Tao. There are elementary proofs, like the one found by Selberg and Erdős, but they are much harder than the complex analytic proof; don't be fooled into thinking that "elementary" means "easier."

As far as the "come from nowhereness" of it all, perhaps you would like to read a blog post I wrote (and its companion) about how to motivate the definition of the zeta function and, in particular, how to motivate studying its asymptotic behavior near $s = 1$. It is a nontrivial fact that one can use complex analysis to study this behavior, and complex analysis is always extremely powerful when it applies.

Answer 4

nice and elegant approach... !!!

Answering this question:

Why do complex numbers (which seem to come from nowhere) make this argument rigorous?

What makes an argument rigorous or not, is still very much debatable. I think, making the PNT rigorous meant to have a formulation that will be widely accepted as a "true-proof", and complex numbers did a very nice job at that.

I only wonder what would have happened if the elementary proofs of PNT came earlier, and the complex-analytic proof came later. Would that have created the same awe for the complex-analytic proof?