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 {\mu(n)} is defined to equal {(-1)^k} when {n} is the product of {k} 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

\displaystyle \sum_{p \leq x} 1 = (1+o(1)) \frac{x}{\log x} \ \ \ \ \ (1)

(where {o(1)} denotes a quantity that goes to zero as {x \rightarrow \infty}) was logically equivalent to the partial sum estimates

\displaystyle \sum_{n \leq x} \mu(n) = o(x) \ \ \ \ \ (2)

and

\displaystyle \sum_{n \leq x} \frac{\mu(n)}{n} = o(1); \ \ \ \ \ (3)

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 {o()} terms are replaced by their {O()} counterparts. For instance, by observing that the binomial coefficient {\binom{2n}{n}} is bounded by {4^n} on the one hand (by Pascal’s triangle or the binomial theorem), and is divisible by every prime between {n} and {2n} on the other hand, we conclude that

\displaystyle \sum_{n < p \leq 2n} \log p \leq n \log 4

from which it is not difficult to show that

\displaystyle \sum_{p \leq x} 1 = O( \frac{x}{\log x} ). \ \ \ \ \ (4)

Also, since {|\mu(n)| \leq 1}, we clearly have

\displaystyle |\sum_{n \leq x} \mu(n)| \leq x.

Finally, one can also show that

\displaystyle |\sum_{n \leq x} \frac{\mu(n)}{n}| \leq 1. \ \ \ \ \ (5)

Indeed, assuming without loss of generality that {x} is a positive integer, and summing the inversion formula {1_{n=1} = \sum_{d|n} \mu(d)} over all {n \leq x} one sees that

\displaystyle 1 = \sum_{d \leq x} \mu(d) \left\lfloor \frac{x}{d}\right \rfloor = \sum_{d \leq x} \mu(d) \frac{x}{d} - \sum_{d<x} \mu(d) \left \{ \frac{x}{d} \right\} \ \ \ \ \ (6)

and the claim follows by bounding {|\mu(d) \left \{ \frac{x}{d} \right\}|} by {1}.

In this paper I extend these observations to more general multiplicative subsemigroups of the natural numbers. More precisely, if {P} is any set of primes (finite or infinite), I show that

\displaystyle |\sum_{n \in \langle P \rangle: n \leq x} \frac{\mu(n)}{n}| \leq 1 \ \ \ \ \ (7)

and that

\displaystyle \sum_{n \in \langle P \rangle: n \leq x} \frac{\mu(n)}{n} = \prod_{p \in P} (1-\frac{1}{p}) + o(1), \ \ \ \ \ (8)

where {\langle P \rangle} is the multiplicative semigroup generated by {P}, i.e. the set of natural numbers whose prime factors lie in {P}.

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 {x} to be a positive integer. Clearly we may assume that

\displaystyle \sum_{n \in \langle P \rangle: n \leq x} \frac{1}{n} > 1, \ \ \ \ \ (9)

as the claim is trivial otherwise.

If {P'} denotes the primes that are not in {P}, then Möbius inversion gives us

\displaystyle 1_{n \in \langle P' \rangle} = \sum_{d|n; d \in \langle P \rangle} \mu(d).

Summing this for {1 \leq n \leq x} gives

\displaystyle \sum_{n \in \langle P' \rangle: n \leq x} 1 = \sum_{d \in \langle P \rangle: d \leq x} \mu(d) \frac{x}{d} - \sum_{d \in \langle P \rangle: d \leq x} \mu(d) \left \{ \frac{x}{d} \right \}.

We can bound {|\mu(d) \left \{ \frac{x}{d} \right \}| \leq 1 - \frac{1}{d}} and so

\displaystyle |\sum_{d \in \langle P \rangle: d \leq x} \mu(d) \frac{x}{d}| \leq \sum_{n \in \langle P' \rangle: n \leq x} 1 + \sum_{n \in \langle P \rangle: n \leq x} 1 - \sum_{n \in \langle P \rangle: n \leq x} \frac{1}{n}.

The claim now follows from (9), since {\langle P \rangle} and {\langle P' \rangle} overlap only at {1}.

As special cases of (7) we see that

\displaystyle |\sum_{d \leq x: d|m} \frac{\mu(d)}{d}| \leq 1

and

\displaystyle |\sum_{n \leq x: (m,n)=1} \frac{\mu(n)}{n}| \leq 1

for all {m,x}. Since {\mu(mn) = \mu(m) \mu(n) 1_{(m,n)=1}}, we also have

\displaystyle |\sum_{n \leq x} \frac{\mu(mn)}{n}| \leq 1.

One might hope that these inequalities (which gain a factor of {\log x} 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 {\zeta_P(s) = \sum_{n \in \langle P \rangle} \frac{1}{n^s} = \prod_{p \in P} (1-\frac{1}{p^s})^{-1}} associated to this problem, but it need not have a meromorphic continuation beyond the region {\{ \hbox{Re}(s) > 1 \}}, 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 —

We now show the equivalences between (1), (2), and (3). The arguments here are drawn from this article of Diamond; I will skip some of the details in order to focus on the main ideas.

It is convenient to introduce the von Mangoldt function {\Lambda(n)}, defined as {\log p} when {n} is a prime {p} (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

\displaystyle \sum_{n \leq x} \Lambda(n) = (1+o(1)) x. \ \ \ \ \ (10)

Now we show that (10) implies (2). The starting point is the identity

\displaystyle -\mu(n) \log n = \sum_{d|n} \mu(d) \Lambda(\frac{n}{d})

connecting {\mu} and {\Lambda}, which is the coefficient form of the identity

\displaystyle (\frac{1}{\zeta(s)})' = \frac{1}{\zeta(s)} \frac{-\zeta'(s)}{\zeta(s)}

involving the Riemann zeta function {\zeta(s)}. Summing this identity for {1 \leq n \leq x}, one obtains the formula

\displaystyle - \sum_{n \leq x} \mu(n) \log n = \sum_{d \leq x} \mu(d) \sum_{m \leq x/d} \Lambda(m). \ \ \ \ \ (11)

Using the Chebyshev bound (4), one can bound {\sum_{m \leq x/d} \Lambda(m)} by {O(x/d)}; using (10), one can refine this to {(1 + O(\varepsilon)) x/d} for any {\varepsilon > 0} when {x/d} is large enough. Using these bounds together with (5), one can show that the right-hand side of (11) is {o( x \log x )}. It is not too difficult to get to (2) from here (e.g. by summation by parts).

To get from (2) to (3), we use (6). A summation by parts argument using (2) shows that

\displaystyle \sum_{x/A<d<x} \mu(d) \left \{ \frac{x}{d} \right\} = o(x)

for any fixed {A>1} (basically because the function {d \mapsto \left \{ \frac{x}{d} \right\} } has bounded variation). Letting {A} go to infinity and using (6) we obtain (3). Conversely, a summation by parts argument easily deduces (2) from (3).

Finally, to get back from (2) and (3) to (10), we use the identities

\displaystyle \Lambda(n) = \sum_{d|n} \mu(d) \log \frac{n}{d}, \ \ \ \ \ (12)

and

\displaystyle 1 = \sum_{d|n} \mu(d) \tau(\frac{n}{d}), \ \ \ \ \ (13)

where {\tau(n) := \sum_{d|n} 1} is the divisor function; these identities are the coefficient forms of the identities

\displaystyle (\frac{1}{\zeta(s)})' = \frac{1}{\zeta(s)} \frac{-\zeta'(s)}{\zeta(s)}

and

\displaystyle \zeta(s) = \frac{1}{\zeta(s)}\zeta^2(s).

Expanding out {\sum_{n \leq x} \Lambda(n)-1} using these formulae, we see that to prove (10) it suffices to show that

\displaystyle \sum_{d, m: dm \leq x} \mu(d) [ \tau(m) - \log m ] = o(x). \ \ \ \ \ (14)

From the Dirichlet hyperbola method one can show that

\displaystyle \sum_{m \leq N} \tau(m) = N \log N + c N + O( N^{1/2} )

for some absolute constant {c} (in fact {c = 2 \gamma-1}, where {\gamma = 0.577\ldots} is Euler’s constant), and from Stirling’s formula one has

\displaystyle \sum_{m \leq N} \log m = N \log N - N + O(N^{1/2} )

and so

\displaystyle \sum_{m \leq x/d} \tau(m) - \log m = (c+1) \frac{x}{d} + O( \sqrt{\frac{x}{d}} ).

From this, (2), (3), and summation by parts one soon obtains (14).

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 {s=1} and no other poles or zeroes on the line {\{ \hbox{Re}(s) = 1 \}}. This approach can of course be found in any introductory analytic number theory text.