I read the claim that the prime number theorem is equivalent to the assertion that

$$\sum_{n \geq 1} \frac{\mu(n)}{n} := \frac{1}{1} - \frac{1}{2} - \frac{1}{3} - \frac{1}{5} + \frac{1}{6} - \frac{1}{7} + \frac{1}{10} - \ldots - \frac{1}{30} - \ldots = 0$$

This surprised me, because I find the prime number theorem highly non-obvious, to the point of not being able to remember its statement, while the above statement is intuitively completely clear. I will quickly explain my intuition below, but my question is: How is it equivalent to PNT, what do the two implications look like? I was not able to find it on the internet.

Intuition behind above equality: we start with all numbers (if you want, you may think of it als all numbers in some large interval). They are $1/1$ of the total. Next we kick out all even numbers, which are $1/2$ of the total, all numbers divisible by 3, which are $1/3$ of the total etc until nothing is left. But we have been a bit over zealous here: numbers divisible by 6 (these are $1/6$'th of the total) have been thrown out twice, so we put them back once (our goal is to kick out every number exactly one time so that we end up with $0$) and the same for numbers divisible by $10, 15$ etc. But now numbers divisible by $30$ have been put back in three times (after being thrown out three times) and so they are still there. Hence we kick them out in order to, in the end, after a lot of moves like this, end up with nothing, which is what the right hand side of the equation signifies.

I understand that talking about even numbers being 'half' of all numbers is not exactly rigorous but still this sounds way too easy to be equivalent to something as complicated as the PNT. What is going on here?

EDIT: as for the source of the claim: this article https://www.jstor.org/stable/2321853?seq=3#metadata_info_tab_contents, claims (without proof) that the PNT is equivalent to the even weaker statement that the left hand side converges at all. I added the 0 myself for above reasons. Wikipedia (PNT) claims a closely related equivalence namely that PNT is equivalent to $\lim_{N \to \infty} \sum_{n \leq N} \frac{\mu(n)}{N} = 0$, whereas the claim at the beginning of this post can be written as $\lim_{N \to \infty} \sum_{n \leq N} \frac{\mu(n)}{n} = 0$

  • 1
    $\begingroup$ here is a relevant reference. $\endgroup$ – lulu Nov 2 '18 at 13:52
  • 1
    $\begingroup$ Apostol (Analytic Number Theory, thm. 4.16) shows that $\sum \mu(x)/x \sim 0 \rightarrow$ PNT. He gives a reference for the other side ($\leftarrow $). $\endgroup$ – daniel Nov 7 '18 at 15:35
  • 1
    $\begingroup$ Also, regarding your edit, Apostol proves in Thm 4.14 ff. that the PNT is equivalent ($\leftrightarrow$) to your first expression which, as you say, is closely related. $\endgroup$ – daniel Nov 8 '18 at 6:06
  • 1
    $\begingroup$ The citation for the converse of thm. 4.16 is to R. Ayoub, Intro. to the Analytic Thy. of Numbers, Math. Surveys, No. 10 (AMS 1963). $\endgroup$ – daniel Nov 8 '18 at 6:14
  • 1
    $\begingroup$ BTW, Ayoub's proof that $\sum \mu(x)/x\sim 0 \leftrightarrow PNT$ depends heavily on the proof that $\sum \mu (x) = o(x)\leftrightarrow PNT$. Then in his thm. 7.13 he shows that $\sum \mu(x)=o(x)$ iff $\sum \mu(x)/x = o(1) $ (in other words that it's equivalent to the PNT) but it's only half a page. The version of the PNT used is that $\psi(x)\sim x,$ so if you get used to this statement it may give some intuition. $\endgroup$ – daniel Nov 19 '18 at 16:44

The prime number theorem in its usual form is somewhat obvious and maybe intuitive from tables of data that prompted Gauss in 1792 or 1793 to speculate that the density of primes was $1/\log x.$ Unfortunately very little is obvious beyond this. Proofs of the PNT often use the version $\psi(x)\sim x$ and so intuition about proofs of the PNT require some familiarity with that version, which can be shown to be equivalent to the usual $\pi(x)\sim x/\log x.$ See Apostol [1], p. 79.

Your question (in bold) is, what does the implication $\sum \mu(x)/x=0\leftrightarrow PNT$ look like? I mentioned in a comment that it depends on the result that $\sum \mu(x)=o(x) \leftrightarrow PNT.$ Because this latter result is easy to find (see, for example, Apostol), below is only a sketch of the last step from Ayoub [1], showing that $\sum \mu(x)/x= o(1) \leftrightarrow \sum \mu(x)=o(x)$ (and hence $\sum \mu(x)/x=o(1)\leftrightarrow PNT$).

The general theorem below is a prerequisite for the proof and I think Apostol and others more or less also prove it so the proof is omitted.

Theorem. If $a(x)$ is defined for integral $x$, if B(x) is of bounded variation in every finite interval, if $\sum_{n \leq x}a(n)=o(x), if B(x) =O(1)$ and $\sum_{n\leq x}|a(n)|=O(x)$ then

$$\sum_{n\leq x}a(n)B\left(\frac{x}{n}\right)=o(x) $$ [proof omitted].

Main result. Let $M(x) = \sum_{n\leq x}\mu(n), L(x) =\sum_{n\leq x}\frac{\mu(n)}{n}.$ Then $M(x) =o(x)$ if and only if $L(x)=o(1).$

First assume $M(x)=o(x).$ In the theorem above put $a(n)=\mu(x)$ and $B(x)=x-[x].$ Then

$$\sum_{n\leq x }\mu(n)\left( \frac{x}{n}-\left[\frac{x}{n}\right]\right)=o(x). $$

But $\sum_{n\leq x}\mu(n)\left[ \frac{x}{n}\right]=1$ (see Apostol, etc.) and so

$$\sum_{n\leq x}\mu(n)\frac{x}{n}=o(x)$$ and dividing by $x,~L(x)=o(1).$

Now assume $L(x) = o(1).$ Then $M(x)=\sum_{n\leq x}\mu(n)=\sum \frac{\mu(n)\cdot n}{n}$

$$= xL(x)-\int_1^x L(t)~ dt = o(x) + o(x) =o(x). $$

The last line is a consequence of the following lemma.

Lemma. Let $x\geq 1$ and $\phi(x)$ have continuous derivatives for $x\geq 1.$ Let $S(x)=\sum_{n\leq x}C(n)$ with $C(n)$ real or complex numbers. Then

$$\sum_{n\leq x}C(n)\phi(n)=S(x)\phi(x)-\int_1^x S(t)\phi'(t)dt. $$

If we put $C(n)=\mu(n)/n$ and $\phi(x)=x$ then the last line next above follows. This is the direction of the proof that is included in Apostol's text [2], so you can get the non-trivial details there on page 97.

[1] Ayoub, An Introduction to the Theory of Numbers, AMS 1963.

[2] Apostol, Introduction to Analytic Number Theory, Springer 2000.

  • 1
    $\begingroup$ Thank you, this is really interesting! Could it be that there are two typos in the beginning of the second paragraph? In the first line of that paragraph I am pretty sure that '$\mu(x)/x$' should read '$\sum \mu(x)/x$'. Is that correct? In the second line I think that '$\sum\mu(x) = 0$' should read '$\sum \mu(x) = o(x)$' (given the rest of your post) but here I am less sure. Could you clarify? $\endgroup$ – Vincent Nov 21 '18 at 11:26
  • $\begingroup$ Also I really like the lemma. it is easy reading right to left, but magic reading left to right as in the proof of the main result. $\endgroup$ – Vincent Nov 21 '18 at 11:28
  • $\begingroup$ @Vincent: thank you, will correct that in a bit. $\endgroup$ – daniel Nov 21 '18 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.