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

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?

-
some history: math.columbia.edu/~goldfeld/ErdosSelbergDispute.pdf – roy smith Jan 2 '11 at 18:02

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$.1 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$.

1 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.

-
An earlier version of this post contained the claim that $\sum_{p \in P} (\log p)^k/p$ diverged at the same rate for $P$ the primes or my funny set. This was wrong. – David Speyer Jan 3 '11 at 3:28

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).

-

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.

-
Or worthwhile for that matter. It was famously noted that the elementary proof of the PNT was a huge disappointment in terms of how much it advanced mathematical techniques (although Selberg's sieve techniques are still extremely useful, these were developed before the elementary proof of the PNT). The questioner asked whether or not it was possible (to give a non-complex-analytic proof), though, and it certainly is! – deeeez Jan 2 '11 at 17:57
@deeeez: Actually, he asked "why", not "if". – simplequestions Jan 2 '11 at 18:37
@simplequestions: Then his question contained a false premise. – deeeez Jan 2 '11 at 18:40

nice and elegant approach... !!!