# Merten’s Function

I thought that today I might write about my most favourite arithmetic function.

The Moebius function $\mu:\mathbb{N} \rightarrow \{-1,0,1\}$ is defined as follows:

$\mu(1)=1$,

$\mu(n)=0$ if $n$ is divisible by $m^2$ for $m>1$, and

$\mu(n)=(-1)^k$ if $n$ is a product of $k$ distinct prime numbers.

So the Moebius function assigns to each counting number either a $0$, $1$, or $-1$. Any number which can be divided by a square number (except 1) is given a zero. Otherwise, the number is assigned $\pm 1$ depending on whether it contains an even or odd number of primes.

For example, $\mu(10) = \mu(2 \times 5) = 1$, $\mu(20) = \mu(2^2 \times 5) = 0$, and $\mu(30) = \mu(2 \times 3 \times 5) = -1$. We can also see that all primes get mapped to $-1$.

Now this is an interesting arithmetic function, for there is some amount of symmetry that one would expect here. Surely there is no favour to an integer being a product of an even number of primes  than an odd number of primes. Although, primes must appear first before the other numbers, for we build everything up out of primes. Perhaps there is a negative bias embedded in this function?

This may seem at first like a weird function and I suppose I thought so too when I first saw it. Note that it distinguishes between numbers with an even or odd amount of prime factors. Let’s talk quickly about an interesting problem related to this.

Let $x$ be a real number and consider summing the Moebius function over all natural numbers up to and including $x$ (if $x$ is an integer, of course):

$S(x) = \sum_{n \leq x} \mu(n)$

For example,

$S(6.17) = \mu(1)+\mu(2)+\mu(3)+\mu(4)+\mu(5)+\mu(6) = -1.$

We can think of this as a walk on the real number line. We start at $0$ and we read our way through the values of the Moebius function, starting at $\mu(1) = 1$. When we meet a $1$, we take a step in the positive direction. If we meet a $-1$ we move the other way. If we meet a 0, then we don’t move at all. From this, $S(x)$ represents the final position of the walk after $[x]$ steps (where we have counted not moving as a step!), where $[x]$ is the greatest integer less than or equal to $x$.

Intuitively, most people reckon that the number of $-1$‘s should be about the same as the number of $1$‘s and so this walk is probably a random walk. A standard random walk where there is an equal 50/50 chance of walking either left or right gives that after $x$ steps, the expected translation distance should be of the order $\sqrt{x}$. Of course, our walk has lots of zeroes in it, and so after much numerical computation Stieltjes conjectured that:

$|S(x)| \leq \sqrt{x}$

The above became known as Merten’s Conjecture. Actually, in 1985 Andrew Odlyzko and Herman te Riele proved this to be false, that there is in fact a value of $x$ which gives

$|S(x)| > \sqrt{x}.$

Sadly, the proof is non-constructive in that it doesn’t tell us what this value of $x$ is! It is, however, known that the value of $x$ lies in the interval

$(10^{14}, e^{1.59 \times 10^{40}}).$

This is not a suitable range for a computer check.

Note: If Merten’s conjecture had turned out to be true, things would be different. The truth of the Merten’s conjecture would actually imply the truth of the Riemann hypothesis. It seems that fate has other plans for mathematics.