Posted by: christian on 25 Jan 2020
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