{'fraction_non_alphanumeric': 0.0734514212982605, 'fraction_numerical': 0.02317564700890963, 'mean_word_length': 3.7308078273958856, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Prime Number Theorem via Karamata's proof of the Landau-Ingham Tauberian theorem

This is an exposition, in 12 pages including all prerequisites and a generalization, of Karamata's little known elementary proof of the Landau-Ingham Tauberian theorem, a result in real analysis from which the Prime Number Theorem follows in a few lines. We believe this to be the most transparent of the elementary proofs of the PNT.


Introduction
The aim of this paper is to give a self-contained, accessible and 'elementary' proof of of the following theorem, which we call the Landau-Ingham Tauberian theorem: The interest of this theorem derives from the fact that that, while ostensibly it is a result firmly located in classical real analysis, the prime number theorem (PNT) π(x) ∼ x log x can be deduced from it by a few lines of Chebychev-style reasoning.
Versions of Theorem 1.1 were proven by Landau [18, §160] as early as 1909, Ingham [13, Theorem 1], Gordon [10] and Ellison [4,Theorem 3.1], but none of these proofs was from scratch. Landau used as input the identity n µ(n) log n n = −1. But the latter easily implies M (x) = n≤x µ(n) = o(x) which (as also shown by Landau) is equivalent to the PNT. Actually, n µ(n) log n n = −1 is 'stronger' than the PNT in the sense that it cannot be deduced from the latter (other than by elementarily reproving the PNT with a sufficiently strong remainder estimate). In this sense, Gordon's version of Theorem 1.1 is an improvement, in that he uses as input exactly the PNT (in the form ψ(x) ∼ x) and thereby shows that Theorem 1.1 is not 'stronger' than the PNT. Ellison's version assumes M (x) = o(x) (and an O(x β ) remainder with β < 1 in (1.1)). It is thus clear that none of these approaches provides a proof of the PNT. Ingham's proof, on the other hand, departs from the information that ζ(1 + it) = 0 (which can be deduced from the PNT, but also be proven ab initio). Thus his proof is not 'elementary', but arguably it is one of the nicer and more conceptual deductions of the PNT from ζ(1 + it) = 0 -though certainly not the simplest (which is [29]) given that the proof requires Wiener's L 1 -Tauberian theorem.
Our proof will essentially follow the elementary Selberg-style proof given by Karamata [15] under the assumption that f is the summatory function of an arithmetic function, i.e. constant between successive integers. We will remove this assumption. For the proof of the PNT, this generality is not needed, but from an analysis perspective it seems desirable, and it brings us fairly close to Ingham's version of the theorem, which differed only in having o(x) instead of C x log x + o( x log x ) in the hypothesis.
Unfortunately, Karamata's paper [15] seems to be essentially forgotten: There are so few references to it that we can discuss them all. It is mentioned in [7] by Erdös and Ingham and in the book [4] of Ellison and Mendès-France. (Considering that the latter authors know Karamata's work, one may find it surprising that for their elementary proof of the PNT they chose the somewhat roundabout route of giving a Selberg-style proof of M (x) = o(x), using this to prove a weak version of Theorem 1.1, from which then ψ(x) ∼ x is deduced.) Even the two books [2,17] on Tauberian theory only briefly mention Karamata's [15] (or just the survey paper [16]) but then discuss in detail only Ingham's proof. Finally, [15,16] are cited in the recent historical article [22], but its emphasis is on other matters. We close by noting that Karamata is not even mentioned in the only other paper pursuing an elementary proof of a Landau-Ingham theorem, namely Balog's [1], where a version of Theorem 1.1 with a (fairly weak) error term in the conclusion is proven.
Our reason for advertising Karamata's approach is that, in our view, it is the conceptually cleanest and simplest of the Selberg-Erdös style proofs of the PNT, cf. [26,5] and followers, e.g. [24,21,14,19,25,23]. For f = ψ and f (x) = M (x) + ⌊x⌋, Theorem 1.1 readily implies ψ(x) = x + o(x) and M (x) = o(x). Making these substitutions in advance, the proof simplifies only marginally, but it becomes less transparent (in particular for f = ψ) due to an abundance of nonlinear expressions. By contrast, Theorem 1.1 is linear w.r.t. f and F . To be sure, also the proof given below has a non-linear core, cf. (3.2) and Proposition 3.15, but by putting the latter into evidence, the logic of the proof becomes clearer. One is actually led to believe that the non-linear component of the proof is inevitable, as is also suggested by Theorem 2 in Erdös' [6], to wit from which the PNT can be deduced with little effort.
Another respect in which [15] is superior to most of the later papers, including V. Nevanlinna's [21] (whose approach is adopted by several books [25,23]), concerns the Tauberian deduction of the final result from a Selberg-style integral inequality. In [15], this is achieved by a theorem (Theorem 2.4 below, attributed to Erdös) with clearly identified, obviously minimal hypotheses and an elegant proof. This advantage over other approaches like [21], which tend to use further information about the discontinuities of the function under consideration, is essential for our generalization to arbitrary non-decreasing functions. However, we will have to adapt the proof (not least in order to work around an obscure issue).
In our exposition we make a point of avoiding the explicit summations over (pairs of) primes littering many elementary proofs, almost obtaining a proof of the PNT free of primes! This is achieved by defining the Möbius and von Mangoldt functions µ and Λ in terms of the functional identities they satisfy and using their explicit computation only to show that they are bounded and non-negative, respectively. Some of the proofs are formulated in terms of parametric Stieltjes integrals, typically of the form f (x/t)dg(t) and integration by parts. We also do this in situations where f and g may both be discontinuous. Since our functions will always have bounded variation, thus at most countably many discontinuities, this can be justified by observing that the resulting identities hold for all x outside a countable set. Alternatively, we can replace f (x) at every point of discontinuity by (f (x + 0) + f (x − 0))/2 without changing the asymptotics. For such functions, integration by parts always holds in the theory of Lebesgue-Stieltjes integration, cf. [11,12].
The proof of Theorem 1.1 exhibited below is, including all preliminaries, just 12 pages long, and the author hopes that this helps dispelling the prejudice that the elementary proofs of the PNT are difficult. Indeed he thinks that this is the most satisfactory of the elementary (and in fact of all) proofs of the PNT in that, besides not invoking complex analysis or Riemann's ζ-function, it minimizes number theoretic reasoning to a very well circumscribed minimum. One may certainly dispute that this is desirable, but we will argue elsewhere that it is.
The author is of course aware of the fact that the more direct elementary proofs, cf. the review [3], of the PNT give better control of the remainder term. (The most recent one [20] finally obtains the error estimate of de la Vallée-Poussin.) It is not clear whether this is necessarily so.
Proof. (i) Following Ingham [13], we define f to be 0 on [0, 1) and compute With positivity and monotonicity of f , this gives f (x) − 2f (x/2) ≤ Kx for some K > 0. Adding these inequalities for x, x 2 , x 4 , . . ., we find f (x) ≤ 2Kx. Together with f ≥ 0, this gives (i). (ii) We compute In view of 0 ≤ t − ⌊t⌋ < 1 and the weak monotonicity of f , the last integral is bounded by Using the hypothesis about F , we have and division by x proves the claim. (iii) Integrating by parts, we have where we used (i) and (ii).
2.2 Remark 1. The proposition can be proven under the weaker assumption F (x) = Ax log x + O(x), but we don't bother since later we will need the stronger hypothesis anyway. 2. Theorem 1.1, which we ultimately want to prove, implies a strong form of (iii): [13]. Conversely, existence of the improper integral already implies f (x) ∼ Ax, cf. [29].
3. Putting f = ψ and using (5.1), the above proofs of (i) and (ii) reduce to those of Chebychev and Mertens, respectively. ✷ The following two theorems will be proven in Sections 3 and 4, respectively:

4)
and when S > 0 we have 2.5 Remark 1. Note that (2.2) implies that g is Riemann integrable over finite intervals. 2. In our application, (2.4) already follows from Proposition 2.1 so that we do not need the corresponding part of the proof of Theorem 2.4. It will be given nevertheless in order to give Theorem 2.4 an independent existence.
3. With minimal additional effort, Theorem 2.4 can be proven under the weaker assumption cf. [15]. We don't need this generality since our g will satisfy (2.2) by construction.
Thus S = 0 holds, which is equivalent to g(x) = f (x)−Ax x → 0, as was to be proven.
The next two sections are dedicated to the proofs of Theorems 2.3 and 2.4. The statements of both results are free of number theory, and this is also the case for the proof of the second. The proof of Theorem 2.3, however, uses a very modest amount of number theory, but nothing beyond Möbius inversion and the divisibility theory of N up to the fundamental theorem of arithmetic.

Proof of Theorem 2.3.1 Arithmetic
The aim of this subsection is to collect the basic arithmetic results that will be needed. We note that this is very little.
We begin by noting that (N, ·, 1) is an abelian monoid. Given n, m ∈ N, we call m a divisor of n if there is an r ∈ N such that mr = n, in which case we write m|n. In view of the additive structure of the semiring N, it is clear that the monoid N has cancellation (ab = ac ⇒ b = c), so the the quotient r above is unique, and that the set of divisors of any n is finite.
Calling a function f : N → R an arithmetic function, the facts just stated allow us to define: It is easy to see that Dirichlet convolution is commutative and associative. It has a unit given by the function δ defined by δ(1) = 1 and δ(n) = 0 if n = 1.

Lemma
There is a unique arithmetic function µ, called the Möbius function, such that µ⋆1 = δ.

Remark
The only properties of µ and Λ that will be used in the proof of Theorem 1.1 are the defining ones (µ ⋆ 1 = δ, Λ ⋆ 1 = log), the trivial consequence (ii) in the above proposition, and the boundedness of µ and the non-negativity of Λ.
In particular, the explicit computations of µ(n) and Λ(n) in terms of the prime factorization of n were only needed to prove the latter two properties. (Of course, these properties of µ and Λ would be obvious if one defined them by the explicit formulae proven above, but this would be ad hoc and ugly, and one would still need to use the fundamental theorem of arithmetic for proving that µ ⋆ 1 = δ and Λ ⋆ 1 = log.) Note that prime numbers will play no rôle whatsoever before we turn to the actual proof of the prime number theorem in Section 5, where the computation of Λ(n) will be used again.

Lemma
The Möbius transform f → F is invertible, the inverse Möbius transform being given by where we used the defining property d|n µ(d) = δ(n) of µ.

Remark
Since the point of Theorem 1.1 is to deduce information about f from information concerning its Möbius transform F , it is tempting to appeal to Lemma 3.7 directly. However, in order for this to succeed, we would need control over M (x) = n≤x µ(n), at least as good as M (x) = o(x). But then one is back in Ellison's approach mentioned in the introduction. The essential idea of the Selberg-Erdös approach to the PNT, not entirely transparent in the early papers but clarified soon after [27], is to consider weighted Möbius inversion formulae as follows. ✷

Lemma
By Lemma 3.7, the first term equals f (x) log x, whereas for the second we have 3.10 Remark 1. Eq. (3.1) is known as the 'Tatuzawa-Iseki formula', cf. [27, (8)] (and [15, p. 24]). 2. Without the factor log(x/n) on the right hand side, (3.1) reduces to Möbius inversion. Thus (3.1) is a sort of weighted Möbius inversion formula. The presence of the sum involving f (x/n) is very much wanted, since it will allow us to obtain the integral inequality (2.1) involving all f (t), t ∈ [1, x]. In order to do so, we must get rid of the explicit appearance of the function Λ(n), which is very irregular and about which we know little. This requires some preparations. ✷

Lemma For any arithmetic function
In particular, we have Selberg's identity: Proof. If f is an arithmetic function, i.e. defined only on N, we extend it to R as being 0 on R\N.
With this extension, so that (3.1) becomes the claimed identity. Taking f (n) = Λ(n) and using d|n Λ(d) = log n, Selberg's formula follows.

Lemma
The following elementary estimates hold: Here, γ is Euler's constant and c > 0.

Conclusion
3.14 Proposition If g : [1, ∞) → R is such that (3.14) Proof. In view of Lemma 3.9, all we have to do is estimate The three terms are where we used (3.9), (3.10), and µ(n) = O(1), respectively.

Proposition (Selberg, Erdös-Karamata [8])
Writing Proof. We estimate Here we used ( In view of the estimate we are done.

Remark
In view of (3.2), the above estimate where we used (3.16). On the other hand, where we used g(x) = f (x)− Ax to obtain |dg| = |df − Adt| ≤ |df |+ Adt = df + Adt and Proposition 2.1(ii). Plugging this into (3.18), we have n≤x (Λ(n) + K(n)) g x n = 2x After these preparations, we can conclude quickly: Subtracting (3.17) from (3.14) we obtain Taking absolute values of this and of (3.14) while observing that Λ and K are non-negative, we have the inequalities Adding these inequalities and comparing with (3.19) we have so that (2.1), and with it Theorem 2.3, is obtained dividing by 2x log x.
3.17 Remark 1. We did not use the full strength of Proposition 3.15, but only an o(x) remainder. 2. Inequality (2.1) is the special case k = 1 of the more general integral inequality proven in [1], assuming a O whereas the conclusions (2.4) and (2.5) assume the form The proof of (4.3) is easy: Dividing (4.1) by e t ′ and integrating over Similarly, dividing (4.1) by e t and integrating over t ∈ [t ′ − h, t ′ ], one obtains the lower bound
Before we give the proof of the proposition, we show that it implies (4.4) and thus Theorem 2.4. For every S > S there is  x Since S 1 < S and since S > S can be chosen arbitrarily close to S, (4.4) holds and thus Theorem 2.4.

Lemma
Let s : [0, ∞) → R be integrable over bounded intervals, satisfying (4.2). Let e > 0 and 0 < S 2 < S 1 be arbitrary, and assume Then every interval [x, x + h] satisfies at least one of the following conditions: where E x,h,S1 is as in (4.5), Proof. It is enough to show that falsity of (i) implies (ii). Define and therefore We observe that (4.7) with T = x would contradict (4.6). Thus x < T ≤ x + h, so we can indeed find a t 2 ∈ [x, x + h] with s(t 2 ) ≤ S 2 . Since we do not assume continuity of s, we cannot claim that we may take t 2 = T , but by definition a t 2 can be found in (T − ε, T ] for every ε > 0. Now we claim that there is a point t 1 ∈ [x, t 2 ] such that s(t 1 ) ≥ S 1 . Otherwise, we would have s(t) < S 1 for all t ∈ [x, t 2 ]. By definition, |s(t)| ≤ S 1 for t ∈ E x,h,S1 , thus |s| > S 1 on the complement of E x,h,S1 . Combined with s(t) < S 1 for t ∈ [x, t 2 ], this means s(t) < −S 1 whenever t ∈ [x, t 2 ]\E x,h,S1 . Thus In view of (4.7) and t 2 > T − ε (with ε > 0 arbitrary), we have By our the assumption that (i) is false, we have µ([x, t 2 ] ∩ E x,h,S1 ) ≤ µ(E x,h,S1 ) < e. Thus choosing ε such that 0 < ε < 2(e − µ([x, t 2 ] ∩ E x,h,S1 )), we have Combining this with (4.6), we finally obtain t2 x s(t)dt < −2M ′ , which contradicts the assumption (4.2). Thus there is a point t 1 ∈ [x, t 2 ] such that s(t 1 ) ≥ S 1 . In view of s(t 1 ) ≥ S 1 > S 2 ≥ s(t 2 ), we have t 1 = t 2 , thus t 1 < t 2 .
Proof of Proposition 4.1. Assuming that S = lim sup |s(x)| > 0, choose S 1 , S 2 such that 0 < S 2 < S 1 < S. We claim that the assertion of the proposition holds for e := log To prove this, assume that there is an x ≥ 0 such that µ(E x,h,S1 ) < e. Then Lemma 4.2 implies the existence of t 1 , t 2 satisfying x ≤ t 1 < t 2 ≤ x + h such that s(t 1 ) ≥ S 1 and s(t 2 ) ≤ S 2 . Now we note that (4.1) is equivalent to the statement that the function k : t → e t (s(t) + M ) is non-decreasing. Since s is given by s(t) = e −t k(t)− M , it follows that it can only have jump discontinuities 'upwards' (in the sense of s(x + 0) > s(x − 0)) but not downwards. Thus if t 1 < t 2 are such that (This is topologically quite obvious, but see the remark below for a proof sketch.) Furthermore, since s(t) + M cannot decrease faster than t → e −t , we have µ(s −1 ([S 2 , S 1 ])) ≥ log S1+M S2+M . (See the remark below.) Since s −1 ([S 2 , S 1 ]) ⊂ E x,h,S1 , we have µ(E x,h,S1 ) ≥ log S1+M S2+M = e, contradicting our assumption. Thus µ(E x,h,S1 ) ≥ e for all x ≥ 0. 2. The author did not succeed in making full sense of the proof in [15] corresponding to that of Proposition 4.1 above. It seems that there is a logical mistake in the reasoning, which is why we resorted to the more topological approach via a generalized intermediate value theorem. Proof. Since Λ(x) ≥ 0, we have that ψ is non-negative and non-decreasing. Furthermore, Note that we still used only (i) of Proposition 3.4, but now we will need (iii):

Theorem
Let π(x) be the number of primes ≤ x and p n the n-th prime. Then π(x) ∼ x log x , p n ∼ n log n.
Proof. Using Proposition 3.4(iii), we compute ψ(x) = n≤x Λ(n) = p k ≤x log p = p≤x log p log x log p ≤ π(x) log x.
Thus π(x) ≤ y + ψ(x)/ log y. Taking y = x/ log 2 x this gives thus ψ(x) ∼ π(x) log x. Together with Proposition 5.1, this gives π(x) ∼ x/ log x. Taking logarithms of π(x) ∼ x/ log x, we have log π(x) ∼ log x − log log x ∼ log x and thus π(x) log π(x) ∼ x. Taking x = p n and using π(p n ) = n gives n log n ∼ p n .

Remark
Karamata's proof of the Landau-Ingham theorem is obviously modeled on Selberg's original elementary proof [26] of the prime number theorem. However, Selberg worked with f = ψ from the beginning. Most later proofs follow Selberg's approach, but there are some that work with M instead of ψ. Cf. the papers [24,14] and the textbooks [9,4]. As mentioned in the introduction, the result for M also follows easily from Theorem 1.1: Proof. We define f (x) = M (x) + ⌊x⌋, which is non-negative and non-decreasing. Now

Remark
Note that we had to define f (x) = M (x)+ ⌊x⌋ and use (5. 2) since f (x) = M (x)+ x is non-negative, but not non-decreasing. One can generalize Theorem 1.1 somewhat so that it applies to functions like f (x) = M (x) + x weakly violating monotonicity. (As to Theorem 2.4, this was noted in Remark 2.5.3.) But the additional effort would exceed that for the easy proof of (5.2). ✷