Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I know about

"Simple analytic proof of the prime number theorem" Newman, 1980

However, is there a proof of the Prime Number Theorem without the use of complex analysis? (Real analysis is fine).


share|cite|improve this question
Check this out: Erdos and Selberg have an elementary proof. –  Jon Bannon Apr 4 '11 at 20:54
Yes. Do a net search. Erdos and Selberg (if memory serves) each did a mostly non-analytic version. Gerhard "Ask Me About System Design" Paseman, 2011.04.04 –  Gerhard Paseman Apr 4 '11 at 20:55
Indeed, Erdos and Selberg are cited in the second sentence of Newman's paper... –  j.c. Apr 4 '11 at 21:17
It is worthwhile to note that the Erdős-Selberg proof is nicely explained in Hardy-Wright: An introduction to the theory of numbers. See sections 22.14-22.16 there, especially Theorems 430 and 434. –  GH from MO Apr 4 '11 at 21:18

5 Answers 5

up vote 6 down vote accepted explains the classic proof in context (there is what amounts to a priority dispute).

share|cite|improve this answer
For Selberg's side of the story, see the interview with him in BAMS 2008#4. –  Harald Hanche-Olsen Apr 5 '11 at 9:39

Another exposition of an elementary proof (that is, a proof not using complex analysis) is in Gerald Tenenbaum and Michel Mendes France, The Prime Numbers and Their Distribution, which is Volume 6 of the Student Mathematical Library, published by the American Mathematical Society. The proof they give is due to Daboussi, from 1984.

share|cite|improve this answer
Somehow, I thought there is essentially just one "elementary" proof known, that due to Erdős and Selberg; do you mean, the proof you mention is substantially different? –  Seva Apr 5 '11 at 7:44
@Seva: From the MR review of Daboussi's paper (written by Diamond): "This paper gives an elementary proof of the PNT that is remarkable in that it makes no use of Selberg's now famous formula." Here is a link to the original paper of Daboussi (And then there are the other devlopments improving on the error term, Diamon-Steinig and so on.) –  quid Apr 5 '11 at 9:30

There is a terrific exposition of the elementary proof by Terry Tao, available as the file prime.dvi here. A more traditional exposition is available in Edwards's book Riemann's zeta function.

share|cite|improve this answer

If you just want $\pi(n) = \Omega \left( \frac{n}{\log n} \right)$, good enough for many applications, here is a quick proof: The highest power of a prime $p$ dividing $2n \choose n$ is at most $2n$ -- you get at most one more factor of $p$ in the numerator than denominator for each power $p^i \leq 2n$. This tells you that ${2n \choose n} \leq (2n)^{\pi(2n)}$. So $\pi(2n) \geq \frac{\log_2 {2n \choose n}}{\log_2 (2n)} \geq \frac{n}{\log_2 (2n)}$.

share|cite|improve this answer

A nice exposition of an Erdos/Selberg-type elementary proof is given by Levinson in Amer. Math. Monthly 76 (1969) 225–245.

The proof by Daboussi as written up by Tenenbaum and Mendes-France was already mentioned.

Yet another one is due to Hildebrand in Mathematika 33 (1986) 23–30.

share|cite|improve this answer

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.