In 1737, Euler presented a novel proof of the infinitude of the primes, in showing that the harmonic sum of the primes diverges. Explicitly, Euler’s work furnishes the estimate
in which the sum exhausts the rational primes at most . At this point, it becomes quite elementary to derive the two inequalities
Results of this flavor remained essentially unimproved for over a century, until Chebyshev presented the following landmark theorem in 1852:
Theorem (Chebyshev): There exist positive constants such that
Thus Chebyshev’s Theorem shows that represents the growth rate (up to constants) of ; stated equivalently in Bachmann-Landau notation, we have . Yet more is true: the constants in Chebyshev’s proof are therein made effective, and can be taken as
As a corollary to Chebyshev’s Theorem, we have for. By making this implicit bound on precise, Chebyshev was able to prove Bertrand’s Postulate (thereafter known as the Bertrand-Chebyshev Theorem).
In this post, we’ll prove a variant of Chebyshev’s Theorem in great generality, and discuss some historically competitive bounds on the constants and given above. Lastly, we’ll discuss how Chebyshev’s Theorem relates to proposed “elementary” proofs of the PNT.
— PART I (LEMMAS) —
We recall that (by elementary methods), whereby it suffices in the context of Chebyshev’s Theorem to study the asymptotic growth of . This (given the complexity of the PNT) is understandably difficult, and so our first step towards Chebyshev’s result is to approximate by “simpler” functions.
For what follows, let be a multi-set of non-zero integers. We define the two functions
If , we’ll say that is balanced. In this case, the following Lemma provides the asymptotic growth of :
Lemma 1: If is balanced, then
Proof: To begin, consider the identity
which expresses Legendre’s formula (1808) in terms of the von Mangoldt function. Extending by linearity, we obtain
i.e. an expression of as the logarithm of a ratio of factorials. To continue, we now recall Stirling’s approximation (in its weak form), that. Accordingly, we obtain
As is balanced, the first and third sums vanish and our result follows.
(Note: In the proof of Lemma 1 we remarked that arises as the logarithm of a ratio of factorials. On the other hand, , and we may view our general technique as an estimation of as a ratio of factorials.)
For future use, we define .
With Lemma 1 in hand, we seek to relate the growth of and . To do so, we first note that is periodic (with period dividing ), provided that is balanced. In particular, is bounded; let (resp. ) denote the maximum (resp. minimum) of . Define , if such an exists (i.e. for ). Lemma 2 gives an upper bound for :
Lemma 2: Let be balanced, and suppose that . Then
Proof: By definition of , we have for . As , it follows that
This last expression telescopes, and we obtain (after iterated substitution)
in which denotes the cube and represents the multinomial coefficient. With Lemma 1, this implies
Now, it follows from the multinomial theorem that
and this proves Lemma 2.
In our final lemma, we derive a lower bound for . Recall that is bounded (with maximum dependent on ) provided that is balanced. For , we define , and then set . We then have:
Lemma 3: Let be balanced, and suppose that . Then
Proof: By definition of (and our hypothesis on ), we have
as the previous expression telescopes. Let be a lower bound for as (these lower bounds exist by positivity of ). Then for large , and thus
In particular, this forces for all lower bounds ; Lemma 3 follows in passing to the liminf.
— PART II —
Now, we present some applications of the lemmas in Part I. Our first example concerns the simplest of all balanced multi-sets:
Example 1: In this example, we take . Then satisfies
in particular, (with ), and (with ). Noting that , we conclude (via Lemmas 2-3) that
The relationship between and the central binomial coefficients (cf. Lemma 1) is far from coincidental: a more-precise study of these coefficients yields a proof of Bertrand’s Postulate (an observation due to Erdős). Yet this is likely the extent to which the central binomial coefficients encapsulate the density of primes, as the upper and lower bounds on differ here by a factor of two (cf. for all ).
Example 2: Our second example comes from Chebyshev (1852), and is generated by the (balanced) multi-set . We readily find (with ) and (with ), which yields the bounds
(exact values for are given in the introduction). As remarked above, these bounds suffice to give an elementary proof of Bertrand’s Postulate, which may explain why Chebyshev makes no attempt to further improve them (at least, not in his original manuscript, Mémoire sur les nombres premiers).
On the other hand, it’s quite possible that Chebyshev could not find other multi-sets that improved upon these bounds. Indeed, insofar as required to prove Bertrand’s Postulate (for all , not just asymptotically), the multi-set affords a similar — yet far shorter — proof.
The torch that Chebyshev lit was carried in subsequent decades by Sylvester, who in 1892 published the bounds
In a sense, these bounds were penultimate: within four years two proofs of the PNT were published (due to Hadamard and de la Vallée-Poussin).
Example 3: Now, to find for ourselves some competitive bounds on , we embrace that which Chebyshev could not: brute force search over short multi-sets . In a few hundred hours of CPU time (in Mathematica), I’ve found the following:
which induce the lower (resp. upper) bounds and on the infimum and supremum of , respectively. Unfortunately, I have yet to find multi-sets that improve upon the elementary bounds of Sylvester (which — credit to him — require far more delicate approximations). Nevertheless, the lower bound which stems from lies within spitting distance () of Sylvester’s bound, a non-trivial feat in itself.
— PART III —
After 1896, the Chebyshev Theorem (and extensions thereof) became little more than a historical/pedagogical note. But the nagging question remains: could Chebyshev (in theory) have proven the PNT with this approach?
In short, maybe. Under the assumption of the PNT, three proofs emerged (circa 1937; due independently to Erdős, Kalmár, and Rosser) that showed that the constants in Chebyshev’s proof could be forced arbitrarily close to one. (Due to a miscommunication none saw publication until 1980, when Erdős and Diamond reconstructed a proof in the memory of Kalmár.)
I confess that the techniques presented hitherto in this article are too ad hoc to reach this result. That is, in building upon the weak foundation of Egyptian fractions to create multi-sets with desirable properties, we find ourselves limited by the unpredictability of Egyptian fraction representations.
Morally, then, our multi-sets form great examples but remain too unwieldy for use in a theoretic capacity. All the same, it takes only a small tweak of our previous methods to reach the result above, which we prove now as a fitting end to this article:
Proof: Consider the multi-set
Then is not necessarily balanced. (In fact, Bertrand’s Postulate implies that is never balanced; see the Exercises.) Nevertheless, if we set , the modified function
is periodic — with period dividing — and is consequently bounded. Next, we introduce the “indicator function”
Our proof now commences in earnest. With the convolution identity (the so-called Chebyshev Identity), we derive
The right-hand side of may be rewritten as
Using Stirling’s Approximation (just as in Lemma 1), we obtain the asymptotic
in which denotes the constant
Now turning to the left-hand side of , an application of the Dirichlet Hyperbola method gives
By construction, on the interval . In particular, the rightmost term above is nothing more than , which is by our estimates in Part II. Moreover, since represents the summary function of, it follows that on . And so, the second sum in the line above simplifies to , and we obtain at last:
wherein the final simplification comes from direct analogy with Lemma 1. Coupled with lines and , this implies
(provided that for simplicity). For fixed , we obtain
for all sufficiently large (e.g. ).
At this point in our proof, we need only show that as . For this, it suffices to establish the following two claims:
a. tends to as , i.e.
b. tends to as .
For (a), define the functions
The two estimates and — both equivalent to the PNT (e.g. Apostol, Thm 4.16) — yield
whereby . Then, because the classical error bound on the PNT (due to Hadamard and de la Vallée-Poussin) provides
for some , we obtain . Thus (after some calculus), which proves our claim from (a).
To establish (b), we begin with the identity
which follows from the Abel summation formula (using the smooth weight function ). As — by the classical PNT error bound — each term on the right-hand side of converges as . If denotes this limit, then as and
in the context of line . Our early estimates in Part II give , whereby. It is an old result of Chebyshev that this forces (see the Exercises), and this concludes our proof.
— EXERCISES —
Exercise: Suppose that for some constant . Show that this implies . Then, use Euler’s estimate on the harmonic sum of primes (given in the introduction) to prove that . (While this was first noticed by Chebyshev in 1852, our work here shows that his result was well within the grasp of Euler, over a century beforehand.)
Exercise: Let , and use the closed form for to show that
Use this estimate to give a second proof that implies . Hint: use the Taylor Series for .
Exercise: Use Bertrand’s Postulate to show that is never balanced, i.e.
for all . Similarly, show that the th harmonic number is never an integer. How does Möbius inversion connect these two results? Hint: For the first part, multiply by and reduce modulo a large prime.
— REFERENCES —
 T. Apostol, Introduction to Analytic Number Theory, Springer (1976).
 P. L. Chebyshev, Mémoire sur les Nombres Premiers, J. Math. Pures Appl., 17, (1852).
 H. Diamond and P. Erdős, On Sharp Elementary Prime Number Estimates, L’Enseignement Mathématique, 26, (1980).