$\lim_\limits{x \to \infty} \frac1x \sum_\limits{n\leq x}\mu(n)=0 \iff$ Prime Number Theorem

There is an interesting history regarding the development of this equivalence. Tom M. Apostol addresses in the beginning of ch. 4 so-called elementary proofs of the prime number theorem which use methods from real analysis and number theory only in contrast to analytic proofs which are mainly based upon methods from complex analysis.

Up to the twenties of last century mathematicians were not sure, if an elementary proof can be found. The following quote is from

• G. H. Hardy (1921):

  No elementary proof of the prime number theorem is known, and one may ask whether it is reasonable to expect one. Now we know that the theorem is roughly equivalent to a theorem about an analytic function, the theorem that Riemann’s zeta function has no roots on a certain line.

  A proof of such a theorem, not fundamentally dependent on the theory of functions, seems to me extraordinarily unlikely. It is rash to assert that a mathematical theorem cannot be proved in a particular way; but one thing seems quite clear. We have certain views about the logic of the theory; we think that some theorems, as we say ‘lie deep’ and others nearer to the surface.

  If anyone produces an elementary proof of the prime number theorem, he will show that these views are wrong, that the subject does not hang together in the way we have supposed, and that it is time for the books to be cast aside and for the theory to be rewritten.

It was 1949 when A. Selberg and P. Erdős discovered an elementary proof. As indicated above elementary is far from being simple. It just addresses the type of used techniques.

Some words how the Möbius function comes into play. Recall an arithmetic function $a: \mathbb{N}\to\mathbb{C}$ is called completely multiplicative if
\begin{align*} a(n)a(m)=a(nm)\qquad\qquad\text{ for all }m,n\in\mathbb{N} \end{align*} Let $\mathbb{P}$ denote the set of primes. The following theorem holds:

Theorem: If a completely multiplicative function $a: \mathbb{N}\to\mathbb{C}$ is not identically zero and such that $\sum_{n=1}^\infty|a(n)|$ is convergent, then \begin{align*} \sum_{n=1}^\infty a(n)=\prod_{p\in\mathbb{P}}\frac{1}{1-a(p)}\tag{1} \end{align*} This important representation of a series as Euler product, i.e. as product over primes only is the key where the Möbius function comes into play. Note the Riemann Zeta function $\zeta(s)$ also has a representation as Euler product for $\Re(s)>1$: \begin{align*} \zeta(s)=\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}} \end{align*}

We consider the reciprocal of (1): \begin{align*} \frac{1}{\sum_{n=1}^\infty a(n)}=\prod_{p\in\mathbb{P}}(1-a(p))\tag{2} \end{align*} and are looking for a series representation of (2). Denoting with $\mathbb{P}[N]$ the set of primes less or equal a real number $N$ we look at first at the finite product and try to derive a series representation for \begin{align*} \prod_{p\in\mathbb{P}[N]}(1-a(p))\tag{3} \end{align*} We see from (3) that $a(1)=1$ is a term of the series. All other non-zero terms of the series come from products $(-1)^ka(p_1)a(p_2)\cdots a(p_k)$ with $k$ pairwise different primes $p_j, 1\leq j\leq k$. Since $a$ is completely multplicative, the non-zero terms besides $a(1)$ have a representation \begin{align*} (-1)^ka(p_1)a(p_2)\cdots a(p_k)=(-1)^ka(p_1p_2\cdots p_k) \end{align*}

and we obtain a definition of the Möbius function $\mu: \mathbb{N}\to\mathbb{C}$ as \begin{align*} \mu(1)&=1\\ \mu(n)&=(-1)^k\qquad\qquad\text{$n$ is a product of $k$ pairwise different primes}\\ \mu(n)&=0\qquad\qquad\qquad\text{otherwise; i.e. a square of a prime, $p^2$ divides $n$} \end{align*} We get the series representation: \begin{align*} \color{blue}{\prod_{p\in\mathbb{P}[N]}(1-a(p))=\sum_{n\in E_N}\mu(n)a(n)} \end{align*} where $E_N$ denotes the set of positive integers less or equal $\mathbb{P}[N]$.

Note:

• The answer given here is mainly taken from the thesis The prime number theorem: Analytic and elementary proofs by Ciarán O’Rourke which is worth reading.

• The history of the elementary proof by A. Selberg and P. Erdős is presented in the elementary proof of the prime number theorem: An historical perspective by D. Goldfeld from which G. H. Hardy's quote was taken.