What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

Question

There is an easy proof of the PNT, just in a few lines, in the book by Julian Havil, "Gamma", pages 201-202. Specifically, Von Mangoldt's formula, which is very easy to derive: $$ \psi(x) = x - \ln(2\pi) - \frac{1}{2}\ln(1 - x^{-2}) - \sum_{\zeta(\rho) = 0} \frac{x^{\rho}}{\rho}, $$ implies the PNT, since from this equation it follows that $\psi(x)/x \to 1$.

I am a Physicist and my Mathematician colleagues regard this proof as non-elementary. I've never seen easier proof of the PNT than this one. Any other proofs of the PNT without complex analysis are very lengthy, tedious and difficult to understand (and actually non-elementary, therefore). But why this a very simple proof is regarded as non-elementary? Unfortunately, I could not get a clear answer. Could you please clarify?

EDIT: Von Mangoldt's formula itself is not sufficient to immediately claim that $\psi(x)/x \to 1$. However, we can consider Newman's proof of the PNT. This proof is much easier and shorter than any existing non-elementary proofs of the PNT. Although this proof involves very basics of the complex analysis, it is, nevertheless, regarded as a non-elementary proof. Therefore, the difference between elementary and non-elementary proofs of the PNT is the presence of the complex analysis. I hope, I am not mistaken.

Answer 1

To complement Will Sawin's answer, in the specific context of the prime number theorem, there are historically well-established notions of "elementary" and "non-elementary" proofs, stemming from Hardy's 1921 lecture:

No elementary proof of the prime number theorem is known, and one may ask whether it is reasonable to expect one. Now we know that the theorem is roughly equivalent to a theorem about an analytic function, the theorem that Riemann’s zeta function has no roots on a certain line. A proof of such a theorem, not fundamentally dependent on the theory of functions, seems to me extraordinarily unlikely. It is rash to assert that a mathematical theorem cannot be proved in a particular way; but one thing seems quite clear. We have certain views about the logic of the theory; we think that some theorems, as we say ‘lie deep’ and others nearer to the surface. If anyone produces an elementary proof of the prime number theorem, he will show that these views are wrong, that the subject does not hang together in the way we have supposed, and that it is time for the books to be cast aside and for the theory to be rewritten.

The history behind is that while up-to-multiplicative constant bounds for the prime counting function were obtained, by Chebyshev, by an ingenious but elementary counting arguments, all the proofs of PNT known in 1921 were a lot more involved and went via Riemann's zeta function and it analytic properties.

An elementary proof was found in 1948 by Selberg and Erdős:

In this paper will be given a new proof of the prime-number theorem, which is elementary in the sense that it uses practically no analysis, except the simplest properties of the logarithm.

This became a big deal, in a large part, because it answered the above-quoted challenge of Hardy. The shortest proof nowadays is Newman's proof, although using complex analysis, it is much more "elementary" than the proofs known to Hardy; it is an interesting question how would Hardy judge it.

Answer 2

The PNT is indeed equivalent to $\lim_{x\to\infty} \frac{\psi(x) -x}{x}=0$ which Von Mangoldt's formula and some trivial estimates reduce to proving $$ \lim_{x\to\infty} \sum_{ \zeta(\rho)=0} \frac{x^{\rho-1}}{\rho}=0.$$

However, this is not easy. It's easy to show that $\zeta(\rho)=0$ implies $\operatorname{Re}(\rho)\leq 1$. To get the PNT, you at least need to show that each term in the sum converges to $0$, which requires improving the inequality to $\operatorname{Re}(\rho)<1$. This requires its own argument.

However, that is by no means sufficient. Since the sum over zeroes is an infinite sum, one can't simply exchange the sum with the limit. Instead one needs a bound for the individual terms, showing they decay reasonably rapidly, and a bound for the number of terms. The first one is done by a zero-free region, i.e. by an even stronger bound on $\operatorname{Re}(\rho)$, while the second is done by zero-counting estimates. Each requires its own argument.

It's helpful to give a version of the von Mangoldt formula which involves a truncated sum over zeroes with an explicit error term, but I don't think this is necessary as there are other approaches.

Furthermore, to even make von Mangoldt's formula make sense, you need analytic continuation of $\zeta$, which is its own argument. There are some cheap proofs of that but you'll need one that also gives the functional equation since you have that $\ln(1-x^{-2})$ term. I don't know if that is contained in your reference.

The proof also depends on the whole machinery of complex analysis - certainly the Cauchy integral formula but probably also a bunch of other stuff.

If you included all this background material, I'm pretty sure it would be longer than the elementary proofs.

But what is meant by "elementary" doesn't have much to do with the total length, but more to do with the amount of background material, and specifically material that a priori seems to have nothing to do with the original problem - i.e. why to prove a result about counting whole numbers of a certain type should we have to introduce real numbers, complex numbers, functions on the complex numbers, analytic functions, zeroes and poles of meromorphic functions, and numerous other things?

Still the non-elementary proofs are, in fact, generally preferred, since they give better conceptual understanding of why the result is true and how it can be generalized and strengthened.

---

Having looked at the book, some additional comments: The book indeed skips many steps, even just in the proof of von Mangoldt's formula. In the first displayed equation on p. 201, the function on the left side is not actually integrable, since it decays only as $1/z$ in the imaginary direction and $\int 1/z =\infty$. The integral can be interpreted precisely as a limit of integrals over symmetric intervals. In a few lines this integral (or limit of integrals) is exchanged with an infinite sum. One can't actually always do that, and more justification is needed.

Most crucially, the residue theorem applies to closed curves, while the contour integral here is over an infinite line. To apply the residue theorem in this context one needs some estimates on the growth rate of the function (in this case, the logarithmic derivative of zeta) at infinity. To see why this is problematic, note that nothing obvious explains why we should sum over the zeroes to the left of the line $c+it$, instead of to the right (where there are no zeroes, suggesting the sum should be zero). To figure out why the left side works and the right side doesn't one needs to draw more complicated contours and estimate the integrals over those.

The necessity of proving non vanishing of $\zeta$ on the line $1+it$ is mentioned on p. 202. It's not mentioned that this on its own isn't enough to prove the PNT and more work is needed.

Some of the needed material for the proof on the analytic continuation and functional equation is contained in Appendix E. It also doesn't make sense to describe the simplicity of the proof without including this!

Answer 3

The fundamental problem with using formulas of the kind you described for $\psi(x)$ is that the series $\sum_\rho x^\rho/\rho$ is hard to estimate on its own.

The crux of the problem here is that there is no easy way to bound $|\sum_\rho x^\rho/\rho|$ directly, starting from just knowing the series converges (and I'm ignoring the proof of von Mangoldt's formula, which itself is a lot of work in order to justify the steps!). The only way you could easily bound a general convergent series $\sum_{n \geq 1} z_n$ is the triangle inequality: $|\sum_{n \geq 1} z_n| \leq \sum_{n \geq 1} |z_n|$. But that doesn't help if $\sum_{n \geq 1} |z_n| = \infty$. For example, the alternating harmonic series $\sum_{n \geq 1} (-1)^{n-1}/n$ converges (alternating series test), but using the triangle inequality on this series to bound it leads to $$ \left|\sum_{n \geq 1} \frac{(-1)^{n-1}}{n}\right| \leq \sum_{n \geq 1} \frac{1}{n} = \infty, $$ which is true but utterly useless.

And that is exactly what happens with the series over zeros in von Mangoldt's formula: $$ \left|\sum_{\rho} \frac{x^\rho}{\rho}\right| \leq \sum_{\rho} \frac{|x^\rho|}{|\rho|} = \sum_{\rho} \frac{x^{{\rm Re}(\rho)}}{|\rho|} \leq ??? $$ We have ${\rm Re}(\rho) < 1$, but there is no known uniform (= same for all $\rho$) upper bound on the zeros better than $1$. If you replace $x^{{\rm Re}(\rho)}$ with the larger value $x$, then the upper bound on $\sum_\rho x^\rho/\rho$ is no longer smaller than the first term $x$ in von Mangoldt's formula, so we lose the ability to deduce PNT.

In fact, it's even worse than that because it's known that $\sum_{\rho} 1/|\rho| = \infty$. So the sum over zeros is not absolutely convergent. Therefore to have clear agreement about what $\sum_\rho x^\rho/\rho$ means, we need an agreement on how we sum the terms. And that agreement is: sum over zeros according to increasing value of $|{\rm Im}(\rho)|$: $$ \sum_{\rho} \frac{x^\rho}{\rho} = \lim_{T \to \infty} \sum_{|{\rm Im}(\rho)| \leq T} \frac{x^{\rho}}{\rho}. $$ Since the non-real zeros of $\zeta(s)$ come in complex-conjugate pairs and ${\rm Im}(\rho) = {\rm Im}(\overline{\rho})$, we can sum over $\rho$ with positive imaginary part and combine terms at $\rho$ and $\overline{\rho}$ together: $$ \sum_{\rho} \frac{x^\rho}{\rho} = \lim_{T \to \infty} \sum_{0 < {\rm Im}(\rho) \leq T} \left(\frac{x^{\rho}}{\rho} + \frac{x^{\overline{\rho}}}{\overline{\rho}}\right) = \lim_{T \to \infty} \sum_{0 < {\rm Im}(\rho) \leq T} \left(\frac{\overline{\rho}x^{\rho} + \rho{x^\overline{\rho}}}{|\rho|^2}\right). $$ Writing $\rho = \beta + i\gamma$ (standard notation), we have (since $x^\rho := e^{\rho\log x} = e^{\beta\log x}e^{i\gamma\log x}$ and $e^{\beta\log x} = x^\beta$) $$ \overline{\rho}x^{\rho} + \rho{x^\overline{\rho}} = 2{\rm Re}(\overline{\rho}x^{\rho}) = 2x^\beta{\rm Re}((\beta - i\gamma)(\cos(\gamma\log x) + i\sin(\gamma\log x))), $$ so $$ \overline{\rho}x^{\rho} + \rho{x^\overline{\rho}} = 2x^\beta(\beta\cos(\gamma\log x) + \gamma\sin(\gamma\log x)). $$ Then $$ |\overline{\rho}x^{\rho} + \rho{x^\overline{\rho}}| \leq 2x^\beta(1 + \gamma), $$ so $$ \left|\sum_{\rho} \frac{x^\rho}{\rho}\right| = \lim_{T \to \infty} \sum_{0 < {\rm Im}(\rho) \leq T} \left(\frac{|\overline{\rho}x^{\rho} + \rho{x^\overline{\rho}}|}{|\rho|^2}\right) \leq \lim_{T \to \infty} \sum_{0 < {\rm Im}(\rho) \leq T} \frac{2x^\beta(1 + \gamma)}{\beta^2 + \gamma^2}. $$ This doesn't look any better: $0 < \beta < 1$, but using that leads to $$ \left|\sum_{\rho} \frac{x^\rho}{\rho}\right| \leq \lim_{T \to \infty} \sum_{0 < \gamma \leq T} \frac{2x(1 + \gamma)}{\gamma^2}, $$ and $(1+\gamma)/\gamma^2 \sim 1/\gamma$, so we're back at the same problem as before: $\sum_{\gamma > 0} 1/\gamma$ is essentially like summing $\sum_{\rho} 1/|\rho|$ from before and that's $\infty$.

In fact, the problem is worse than that: baked into the sum over zeros is a convention that is not explicitly written in the sum but can't be ignored, namely the role of multiplicities of zeros. Each term $x^\rho/\rho$ in the sum over zeros of $\zeta(s)$ actually is repeated in the sum as often as the multiplicity $m_\rho$ of $\rho$ as a zero of $\zeta(s)$: that detail comes from the proof of von Mangoldt's formula, because the starting point of the proof is the Hadamard factorization of $\zeta(s)$, in which the factor associated to each zero of $\zeta(s)$ appears as often as the multiplicity of that zero. So each $x^\rho/\rho$ has an implicit coefficient $m_\rho$ that I have ignored so far (and to collect terms at $\rho$ and $\overline{\rho}$ together as above actually depends on knowing $\rho$ and $\overline{\rho}$ have equal multiplicities, which is true but I hadn't mentioned it earlier). I don't have Havil's book in front of me: does he mention the need to repeat terms in the sum with multiplicity?

To be fair, we expect all zeros of $\zeta(s)$ are simple, meaning we expect each $m_\rho$ to be $1$, but that remains unproved and there isn't even a proved uniform upper bound on the multiplicities of all zeros (e.g., it's not yet proved that every zero of $\zeta(s)$ has multiplicity at most $2$ or $3$).

The bottom line is that it is hard to directly bound the series $\sum_\rho x^\rho/\rho$ and it is even hard to prove that series converges. This is analogous to the difficulty with proving convergence of Fourier series, which need not be absolutely convergent. (A power series, by contrast, is absolutely convergent on the interior of its disc of convergence.) In fact, the only known method of showing the series converges and bounding it is to work from the start with a truncated sum over the zeros $\rho$ with $|{\rm Im}(\rho)| \leq T$ and only pass to the limit in $T$ at the very end: von Mangoldt's formula is not easy to derive, no matter how straightforward it appears in Havil's book. Truncated versions of von Mangoldt's formula (with an error term) is what people use, never the full von Mangoldt formula without error term. The von Mangoldt formula in Havil's book is basically useless except in popular expositions about the zeta function to impress people about the link between prime numbers and zeros of the zeta function.

Answer 4

Some historical context may be helpful here. Back in the first half of the twentieth century, mathematics was widely regarded as being stratified into three "tiers": arithmetic, analysis, and set theory. Roughly speaking, arithmetic was the realm of the finitary or "potentially infinite" but not "actually infinite," analysis was the realm of $\mathbb{R}$, $\mathbb{C}$, and separable function spaces, while set theory dealt with higher infinities. We can see this distinction in, for example, Gentzen's work; after proving the consistency of arithmetic, he spent much of the rest of his life trying to prove the consistency of analysis.

With this backdrop, the notion of an elementary proof had a very specific meaning. Contrary to what you might think, it did not mean a simple proof, an easy proof, a short proof, or even a proof using very little "conceptual machinery." It meant a proof using only the tools of arithmetic. Therefore a proof using the tools of complex analysis was automatically "not elementary" no matter how easy or conceptual it was.

Nowadays, we have mostly moved away from this narrow, technical definition of the word "elementary." One can, if one likes, identify "arithmetic" with first-order Peano arithmetic (PA for short), and "analysis" with second-order arithmetic, and set theory with ZFC. While these axiomatic systems are still of great interest, people have come to realize that it is not very helpful to use the word elementary as being synonymous with provable in PA. After all, analysis or no analysis, the word elementary still retains a strong connotation of "simple, easy, and using very little conceptual machinery." We understand now much better than in the past how it is possible to encode in PA highly sophisticated and complicated proofs—proofs that are in no sense "elementary" unless you insist that they are elementary by definition. There is such a large disconnect between the intuitive concept of "elementary" and the technical concept of "provable in PA" that identifying them causes more confusion than anything else.

As an example, people often ask whether Fermat's Last Theorem is provable in PA. While this question is of some proof-theoretic interest, what people who ask this question usually want to know is whether there exists an elementary proof of FLT, in the sense of a simple, easy proof that avoids all the high-powered machinery of the current proof. The catch is, most likely, all that high-powered machinery can be encoded in PA, or rather, encoded with enough fidelity that the current proof can be pushed through in more or less its current form. There are many technical details that one would need to check before we could declare with 100% confidence that this program can indeed be carried out, but the point is, even if it were carried out, it wouldn't really answer the intended question of whether there is a simple, easy proof that avoids high-powered machinery.

The Selberg-Erdős elementary proof of the PNT probably also contributed to the decline in the use of defining "elementary" to mean "provable in PA." Hardy expected that an elementary proof of PNT would lead to a huge conceptual breakthrough in number theory. This didn't happen. The elementary proof was ingenious, but did not revolutionize number theory the way some people were hoping. This disillusionment helped people realize that their intuition about "elementary" proofs, as they defined them at the time, was flawed. So nowadays, people pretty much use "elementary" in the way you would expect (simple, easy, and using very little machinery), except in vestigial phrases such as "elementary proof of the prime number theorem" which have managed to survive from a bygone era.

As a final comment, there is still some contemporary interest in seeing how much (multiplicative) number theory can be developed without recourse to zeros of zeta functions and $L$-functions. However, Granville and Soundararajan, perhaps the leading champions of this area of study, have chosen to call it pretentious number theory instead of elementary number theory.