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

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.

• Elementary is not the same as easy; it refers to the amount of background necessary to understand the proof. For PNT, 'elementary' proofs are those which don't use complex analysis, regardless of the level of difficulty. Apr 12, 2023 at 17:37
• Can you give a more precise reference for the book? Apr 12, 2023 at 17:40
• @PeterS. It is mathematical terminology, not everyday English. For another example, 'normal' subgroups may be rare and not the typical example of a subgroup. It is not productive to argue that normal subgroups are not normal. Apr 12, 2023 at 19:05
• @Peter S. No, $\xi$ is the xi function, a variant of the zeta function, whose complex roots are exactly the non-trivial roots of the zeta function. Btw, it is Riemann and not Reimann. Apr 13, 2023 at 7:13
• Whenever I hear the word "elementary" I am reminded of Feynman's definition: "Elementary does not mean easy to understand. Elementary means that very little is required to know ahead of time in order to understand it, except to have an infinite amount of intelligence." Apr 13, 2023 at 21:21

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.

• I feel confident that Hardy would not have judged Newman's proof to be elementary, for the simple reason that it still uses complex analysis. Apr 13, 2023 at 12:16
• Newman's proof is not difficult to understand. Moreover, this proof is much easier and shorter than any existing elementary proof of the PNT. But again, it is regarded as a non-elementary proof just only due to Cauchy's theorem. Apr 13, 2023 at 16:30
• @PeterS. it is a matter of taste, but I don't find Newman's proof easy to understand, as compared to some of the more usual zeta-function proofs. It may be easy to check it line by line, but that is different from understanding. Apr 14, 2023 at 11:09

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!

• Many thanks for clarifications! Rigorous proof of the PNT is not as easy as it looks. Apr 12, 2023 at 19:11

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.

• The multiplicity of the zeroes is unmentioned in Havil's writeup. Apr 13, 2023 at 17:02
• @WillSawin thanks. I'm not surprised, of course. Does he attempt to derive the formula in any sense or is it presented using a line like "it can be shown..."? Apr 13, 2023 at 17:58
• He first relates $\psi(x)$ to a contour integral of the logarithmic derivative of zeta using a derivation that ignores certain analytic difficulties (which might in a formal textbook be presented as a heuristic derivation) and then says "The remaining contour integral is evaluated using the theory of residues, all of which have to be added together to arrive at the answer." which I guess is a version of "it can be shown". Apr 13, 2023 at 19:56
• @WillSawin yes, it looks that way. And he surely glosses over the issue you point in your answer about why the sum of residues is good from one side of the contour (nontrivial residues) but not from the other side (identically 0). Apr 13, 2023 at 20:00

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.

• This answer is very enlightening and clarifying but I have questions about some parts: (1) Why do you think that most people who ask about whether Fermat is provable in PA are worried about the machinery rather than the axioms? I don't think that was my understanding of the point of interest when I first saw the question. Haven't lots of people heard the claim that the proof of FLT depends on universe axioms and are interested from that perspective? Apr 13, 2023 at 14:09
• (2) Do people really nowadays use "elementary" to mean "simple, easy, and using very little machinery" instead of just "using very little machinery"? Whenever I try to remember a mathematician using that word it's always in the context of avoiding certain high-powered machinery and not necessarily using a simple argument (except maybe in the sense that even long and difficult low-machinery arguments are almost always shorter than even simple high-machinery arguments if you count all the necessary background material in the length). Apr 13, 2023 at 14:14
• @WillSawin People asking about universes are typically asking if FLT is provable in ZF, not whether FLT is provable in PA. I admit that my evidence for my claim is anecdotal, based on personal conversations with several people who have asked about the provability of FLT in PA. It's entirely possible that my anecdotal sample is biased. As for "elementary," if I think harder about it, I guess I mostly agree with you, but for example, the OP of the current question seems to think of "elementary" as connoting easy ("I've never seen an easier proof...") and I don't think this is uncommon. Apr 13, 2023 at 14:37
• For example, in a sketch of a complicated, multi-part proof, I think people will sometimes say, "This part is elementary" to mean that it's short and straightforward, rather than that it avoids machinery. Apr 13, 2023 at 14:38
• (On googling, I found a more recent version (2.5 instead of 1.2) for "Multiplicative number theory: The pretentious approach", with about 50 more pages. I could not tell from looking at Andrew's website (an interesting collection of hyperlinked pdf files) if this was the most recent version) Apr 14, 2023 at 1:55