I’ve just uploaded to the arXiv the paper A remark on partial sums involving the Möbius function, submitted to Bull. Aust. Math. Soc..
The Möbius function is defined to equal when is the product of distinct primes, and equal to zero otherwise; it is closely connected to the distribution of the primes. In 1906, Landau observed that one could show using purely elementary means that the prime number theorem
we give a sketch of the proof of these equivalences below the fold.
On the other hand, these three inequalities are all easy to prove if the terms are replaced by their counterparts. For instance, by observing that the binomial coefficient is bounded by on the one hand (by Pascal’s triangle or the binomial theorem), and is divisible by every prime between and on the other hand, we conclude that
Also, since , we clearly have
and the claim follows by bounding by .
where is the multiplicative semigroup generated by , i.e. the set of natural numbers whose prime factors lie in .
Actually the methods are completely elementary (the paper is just six pages long), and I can give the proof of (7) in full here. Again we may take to be a positive integer. Clearly we may assume that
as the claim is trivial otherwise.
If denotes the primes that are not in , then Möbius inversion gives us
Summing this for gives
We can bound and so
The claim now follows from (9), since and overlap only at .
As special cases of (7) we see that
for all . Since , we also have
One might hope that these inequalities (which gain a factor of over the trivial bound) might be useful when performing effective sieve theory, or effective estimates on various sums involving the primes or arithmetic functions.
This inequality (7) is so simple to state and prove that I must think that it was known to, say, Landau or Chebyshev, but I can’t find any reference to it in the literature. [Update, Sep 4: I have learned that similar results have been obtained in a paper by Granville and Soundararajan, and have updated the paper appropriately.] The proof of (8) is a simple variant of that used to prove (7) but I will not detail it here.
Curiously, this is one place in number theory where the elementary methods seem superior to the analytic ones; there is a zeta function associated to this problem, but it need not have a meromorphic continuation beyond the region , and it turns out to be remarkably difficult to use this function to establish the above results. (I do have a proof of this form, which I in fact found before I stumbled on the elementary proof, but it is far longer and messier.)
— 1. Equivalences —
It is convenient to introduce the von Mangoldt function , defined as when is a prime (or a power of that prime), and zero otherwise. It is not difficult to see that the prime number theorem (1) is equivalent to the asymptotic
connecting and , which is the coefficient form of the identity
Using the Chebyshev bound (4), one can bound by ; using (10), one can refine this to for any when is large enough. Using these bounds together with (5), one can show that the right-hand side of (11) is . It is not too difficult to get to (2) from here (e.g. by summation by parts).
where is the divisor function; these identities are the coefficient forms of the identities
Expanding out using these formulae, we see that to prove (10) it suffices to show that
From the Dirichlet hyperbola method one can show that
Remark 1 These equivalences are elementary, but somewhat ad hoc in nature. A less elementary, but more “natural”, approach would be to rewrite everything in terms of the Riemann zeta function, and in particular to show that (10), (2), (3) are all equivalent to the assertion that the zeta function has a simple pole at and no other poles or zeroes on the line . This approach can of course be found in any introductory analytic number theory text.