Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
some history: – roy smith Jan 2 '11 at 18:02
Please accept an answer. – Jun 8 '11 at 19:16
up vote 7 down vote accepted

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.

share|cite|improve this answer
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).

share|cite|improve this answer

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.

share|cite|improve this answer
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... !!!

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?

share|cite|improve this answer
I think it would've increased the awe for the complex-analytic proof: it would've looked even better by comparison, since it is not only easier but suggests avenues for further inquiry leading immediately to the Riemann hypothesis, which the elementary proof doesn't. – Qiaochu Yuan Jan 3 '11 at 18:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.