# The Möbius function and the Mertens conjecture

This blog post was inspired by Holly Krieger's video for Numberphile.

The Möbius function, $\mu(n)$, is related to the factorization of the positive integer $n$ through $$\mu(n) = \delta_{\Omega(n), \omega(n)} (-1)^{\Omega(n)},$$ where $\Omega(n)$ is the number of prime factors of $n$, $\omega(n)$ is the number of distinct prime factors of $n$, and $\delta_{i,j}$ is the Kronecker delta function (equal to 1 or 0 according to whether $i=j$ or not).

That is, $\mu(n) = 1$ if $n$ is a square-free and has an even number of factors, $\mu(n) = -1$ if $n$ is a square-free and has an odd number of factors, and $\mu(n) = 0$ if $n$ has a repeated prime factor. For example,

$n$Factorization$\mu(n)$
1$1$
2 = $2$$-1 3 = 3$$-1$
4 = $2^2$$0 5 = 5$$-1$
6 = $2\cdot 3$$1 7 = 7$$-1$
8 = $2^3$$0 9 = 3^2$$0$
10 = $2\cdot 5$$1 11 = 11$$-1$
12 = $2^2\cdot 3$$0 The Mertens function is the cumulative sum of the Möbius function:$$ M(n) = \sum_{k=1}^n \mu(k). $$This function is the subject of a famous disproven conjecture: that the magnitude of M(n) is always less than the square root of n:$$ |M(n)| < \sqrt{n} \quad\quad(not\;true)$$It was disproved by Andrew Odlyzko and Herman te Riele in 1985; the current upper-bound to a counter-example was shown by Kotnik and Te Riele (2006) to be below$10^{6.91\times 10^{39}}$, but the precise value is not known. The code below plots the Mertens function and$\pm \sqrt{n}$for$n \le 10^6$. import numpy as np import matplotlib.pyplot as plt NMAX = 1000000 def get_mu_seq(nmax): """Return the values of the Möbius function up to nmax in a list.""" sqrt_nmax = int(np.sqrt(nmax)) mu =  * (nmax+1) # Comopose the numbers from their factors, keeping track of the # parity of the number of factors in the sign. If a number is the # product of two prime factors set its value of mu to 0. for k in range(2, sqrt_nmax+1): if mu[k] == 1: for j in range(k, nmax+1, k): mu[j] *= -k for j in range(k*k, nmax+1, k*k): mu[j] = 0 # Set the value of the Möbius function according to the value in mu. for k in range(2, nmax+1): if mu[k] == k: mu[k] = 1 elif mu[k] == -k: mu[k] = -1 elif mu[k] < 0: mu[k] = 1 elif mu[k] > 0: mu[k] = -1 return mu mu = get_mu_seq(NMAX) n = range(1,NMAX+1) # Plot the Mertens function and its (wrongly) conjectured bounds, ±sqrt(n). plt.plot(n, np.cumsum(mu[1:]), lw=1) plt.plot(n, np.sqrt(n), '0.5', lw=1) plt.plot(n, -np.sqrt(n), '0.5', lw=1) plt.xlim(0,NMAX+1) plt.axhline(0, 0, NMAX+1, c='0.5', lw=1) plt.xlabel('$n$') plt.ylabel('$M(n)\$')
plt.show()

Current rating: 3.8