# Prime Number Theorem w/o Complex Analysis

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

Thanks!

-
Check this out: jstor.org/pss/1969455 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... jstor.org/stable/2321853 –  j.c. Apr 4 '11 at 21:17
While none of the downvotes is from me, I still would ask you to make precise why you want to know this. In particular for this question this is crucial to know to give an answer that is relevant to you. –  quid Apr 4 '11 at 21:32
@Cam: I downvoted because a minimum of effort on the part of the OP would have unearthed Erdos-Selberg. –  Felipe Voloch Apr 7 '11 at 0:13

http://www.math.columbia.edu/~goldfeld/ErdosSelbergDispute.pdf explains the classic proof in context (there is what amounts to a priority dispute).

-
For Selberg's side of the story, see the interview with him in BAMS 2008#4. dx.doi.org/10.1090/S0273-0979-08-01223-8 –  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.

-
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 math.jussieu.fr/~allouche/20060929144515189.pdf (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.

-

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

-

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.

-