*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 = [1] * (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()
```

## Comments

Comments are pre-moderated. Please be patient and your comment will appear soon.

There are currently no comments

## New Comment