Prime numbers theorem via Mertens’ function I have read in many places that $M(x)=o(x)$ (where $M(x):= \sum_{n\leq x}\mu(n)$ and $\mu$ is the Mobius function) implies the prime numbers theorem. However, I am yet to find one readable proof of this statement. Can anyone please explain how these two properties are related? (Supposedly elementarily).
Thanks in advance to all the helpers
 A: There are a few elementary proofs of the prime number theorem out there, most notably Selberg's elementary proof [1]. While these are "elementary" in the sense that they avoid the use of complex analysis or other more advanced mathematics, they are typically much more difficult to reason about. This answer to a very closely related question notes this as well: elementary does not mean simple.
This is my justification for giving you a non-elementary response, but the one which I find easiest to actually reason about. A key idea in the prime number theorem --- and indeed, in Riemann's Memoir, which is perhaps most accessible now through Edwards's book [2] --- is that complex analysis, $\zeta(s)$, and prime numbers are related.
Complex Analytic Ingredients
There are two major complex analysis ingredients.
The first complex analytic ingredient is Cauchy's Residue Theorem, which states essentially that an integral of a nice complex function around a closed, nice curve $\Gamma$ is equal to a sum of particular values (called residues) associated to $f$,
$$
\frac{1}{2\pi i} \int_\Gamma f(z) dz = \sum_{\textrm{Residues } z_i} \mathrm{Res}f(z_i). \tag{1}
$$
For a nice function, each place where $f(z)$ tends to $\infty$ is called a pole, and each of these poles has an associated residue. I don't define what nice means, but $\zeta(s)$ is nice and the curves of interest are nice for this application.
The second is essentially Perron's Formula, which in this application states essentially that
$$
\frac{1}{2\pi i} \int_{2 - iT}^{2 + iT} \frac{\zeta'(s)}{\zeta(s)} \frac{X^s}{s} ds = \sum_{n \leq X} \Lambda(n) + \mathrm{Error}(X, T), \tag{2}
$$
where $\Lambda(n)$ is the von Mangoldt function and the error term depends on $X$ and $T$, but is small enough to not be a major hurdle.
Idea of the proof of Prime Number Theorem
A very short summary of the idea of the Prime Number Theorem is to study the integral on the left side of $(2)$ by studying the analytic properties of $\zeta'(s)/\zeta(s)$ as a complex function $f(s)$ and applying Cauchy's Residue Theorem $(1)$. There are a few technical hurdles that arise, but this is the idea.
The analytic properties of $\zeta'(s)/\zeta(s)$ that we care about are where it has poles (places where $\zeta'(s)/\zeta(s) \to \infty$). There are two sources of poles for $\zeta'(s)/\zeta(s)$: poles of $\zeta(s)$ and zeros of $\zeta(s)$.
Morally, after applying the residue theorem $(1)$ to $(2)$ on the rectangular contour with vertices $2 - iT, 2 + iT, 1 - \epsilon + iT, 1 - \epsilon - iT$ for some $\epsilon$ shows that
$$\begin{align}
\frac{1}{2 \pi i} \int_{2 - iT}^{2 + iT} \frac{\zeta'(s)}{\zeta(s)} \frac{X^s}{s} ds 
&=\frac{1}{2 \pi i} \int_{1 - \epsilon - iT}^{1 - \epsilon + iT} \frac{\zeta'(s)}{\zeta(s)} \frac{X^s}{s} ds \\
&\quad + \sum_{\textrm{Residues} s_i} \mathrm{Res} \frac{\zeta'(s_i)}{\zeta(s_i)} \frac{X^{s_i}}{s_i} + \mathrm{Error}(T), \tag{3}
\end{align}$$
where the error comes from the two small horizontal components of the box and is small for classically understood reasons.
The only pole of $\zeta(s)$ is at $s = 1$ (and it has residue $1$). In the sum over residues, this pole gives a term $1 \cdot X^1/1 = X$. The Prime Number Theorem is equivalent to this being the dominant term on the right hand side of $(3)$, as after rearranging $(2)$ this would give the well known equivalent result
$$ \sum_{n \leq X} \Lambda(n) = X + o(X). \tag{4}$$
Thus to show the prime number theorem, it's necessary to understand the location of the other residues and to study the shifted integral in $(3)$.
Zeros of $\zeta(s)$ and the error term
The other residues come from zeros, and the zeros of $\zeta(s)$ are mysterious. It is straightforward to show that $\zeta(s)$ has no zeros with $\mathrm{Re} s > 1$ using the Euler product representation
$$ \zeta(s) = \prod_p \Big( 1 - \frac{1}{p^s} \Big)^{-1}.$$
But other than that, their location is mysterious. The Riemann Hypothesis states that there are no zeros with $\mathrm{Re} s > \frac{1}{2}$. The region $(1/2, 1]$ is an important region.
Morally, a zero at $s = 1 + it_0$ would add a term of size $X^{1 + it_0}$ to the right hand side of $(4)$. This is as large as the main term! This would be bad. But zeros to the left would only contribute smaller terms.
"$\zeta(s) \neq 1$ for $\mathrm{Re} s = 1$ is equivalent to the PNT"
It is in this context that people say that "$\zeta(s)$ having no zeros on the line $\mathrm{Re} s = 1$ is equivalent to the Prime Number Theorem." If there are no zeros on the line $\mathrm{Re} s = 1$, then subtle but well-known arguments can show that the remaining residues and shifted integral in $(3)$ are all smaller than the main term. (One such argument is the Wiener Ikehara Theorem, which is very subtle. An easier-to-understand form of this theorem is the "Analytic Theorem" in [3], perhaps the most understandable proof of the prime number theorem I've ever seen. Another possible argument is to prove a bit more, a zero-free region. This is used in more precise versions of the prime number theorem with explicit error terms, as in most textbooks on analytic number theory).
Relation to the Merten's function
We finally arrive at the Merten's function. The locations of the zeros of $\zeta(s)$ are deeply connected with the Merten's function. This is because
$$ \frac{1}{\zeta(s)} = \sum_{n \geq 1} \frac{\mu(n)}{n^s},$$
and Perron's Formula applied to $\zeta(s)^{-1}$ gives that
$$ \frac{1}{2 \pi i} \int_{2 - iT}^{2 + iT} \frac{1}{\zeta(s)} \frac{X^s}{s} ds = \sum_{n \leq X} \mu(n) + \mathrm{Error}(X, T),$$
where again the error is manageable.
Exactly as in $(3)$ above, morally we have
$$ \begin{align}
\frac{1}{2 \pi i} \int_{2 - iT}^{2 + iT} \frac{1}{\zeta(s)} \frac{X^s}{s} ds 
&= \frac{1}{2 \pi i} \int_{1 - \epsilon - iT}^{1 - \epsilon + iT} \frac{1}{\zeta(s)} \frac{X^s}{s} ds \\
&\quad + \sum_{\textrm{Residues} s_i} \mathrm{Res} \frac{1}{\zeta(s_i)} \frac{X^{s_i}}{s_i} + \mathrm{Error}(T). \tag{5}\end{align}$$
And just as in the previous integral, a zero of $\zeta(s)$ at $s = 1 + it_0$ would show that
$$ \sum_{n \leq X} \mu(n) = c X^{1 + it_0} + \text{other terms} + \mathrm{Error},$$
which is bigger than $o(X)$. (There is a subtle argument here too, showing that even if there are lots of zeros with $\mathrm{Re} s = 1$, they can't all cancel out pathologically to contribute $o(X)$ overall).
Thus the locations of the zeros of $\zeta(s)$ on the line $\mathrm{Re} s = 1$ and the existence of primary residue terms of size $X$ in $(3)$, and the existence of primary residue terms of size $X$ in $(5)$ are all essentially the same question if we accept a variety of other arguments as background information and tooling.
I would also posit that the reason why the relationship isn't stated explicitly very often is because there actually is a lot of subtle analysis in the background, and it's difficult to explain.
Historical context
Much of the subtle analytic methodology in the background existed before a satisfactory proof that $\zeta(s) \neq 0$ for $\mathrm{Re} s = 1$ came into existence. For example, in Hadamard's proof of the Prime Number Theorem [4], the first major part of the paper was proving that $\zeta(s) \neq 0$ for $\mathrm{Re} s = 1$. The second half of the paper deduced the PNT (with some further subtle analysis, to be fair).
Further, the proofs of this given by Hadamard and de la Vallée Poussin (who each gave the first complete proofs of the PNT) were both complicated and annoying. de la Vallée Poussin's proof took over 20 pages!
Now there is a relatively short and straightforward proof later due to de la Vallée Poussin and Mertens. Yet another proof appears in [3] and takes about a paragraph.
Later, different proofs of the Prime Number Theorem were given that need fewer subtle analytic arguments, but which still need $\zeta(s) \neq 0$ for $\mathrm{Re} s = 1$. One such proof is described in [3].
Much more can be read in [6] about this. This is a survey article written in 1996, 100 years after the PNT was first proved.
Final remark
A few times in this answer, I wrote "morally". This is particularly true in my handling of equations $(3)$ and $(5)$. In an actual proof of the Prime Number Theorem (or of bounds for the Mertens function), you wouldn't actually move the contour to $1 - \epsilon$ since we don't understand the zeros well enough to actually do this. Instead, one would typically shape the contour in a way to deliberately avoid extra zeros. This requires either a slightly different analytic argument or a zero-free region.
Hadamard's proof was very similar to the outline above, except that he actually considered the closely related integral
$$\frac{1}{2\pi i} \int{2 - iT}^{2 + iT} \frac{\zeta'(s)}{\zeta(s)} \frac{X^s}{s^2} ds$$
(note the $s^2$ instead of $s$ in the denominator).
de la Vallée Poussin's proof also used a slightly different integral, with something like $(s-u)(s-v)$ in place of $s$ in the denominator, and he used the additional parameters for a bit of flexibility.

References

*

*Selberg, Atle. “An Elementary Proof of the Prime-Number Theorem.” Annals of Mathematics, vol. 50, no. 2, 1949, pp. 305–313.


*Edwards, Harold M. Rieman's zeta function. Academic Press, 1974.


*Zagier, Don. "Newman's short proof of the prime number theorem." The American Mathematical Monthly 104.8 (1997): 705-708.


*Hadamard, Jacques. "Sur la distribution des zéros de la fonction $\zeta (s) $ et ses conséquences arithmétiques." Bulletin de la Societé mathematique de France 24 (1896): 199-220.


*De la Vallée Poussin, Charles-Jean. Recherches analytiques sur la théorie des nombres premiers. Hayez, Imprimeur de l'Académie royale de Belgique, 1897.


*Bateman, Paul T., and Harold G. Diamond. "A hundred years of prime numbers." The American mathematical monthly 103.9 (1996): 729-741.
