The Möbius Function (or, on Squarefree Numbers)

**Ed Pegg Jr**

In 1831, August
Ferdinand Möbius
put numbers into 3 bins. We now call it the Möbius
function,
and represented by the greek letter Mu (µ).

In
the "zero" bin, he placed multiples of square numbers
(other than 1). {4 8 9 12 16 18 20 24 25 27 28 32 36 40 44 45 48 49
50 52 54 56 60 63 64 68}. So, µ(48)
= 0, µ(49)
= 0, and µ(50)
= 0, since each is divisible by a square number.

These are
sometimes called the squareful numbers. Already, we have
something amazing. The probabilty that a number is not in the
"zero" bin just happens to be 6/π^{2},
so about .39207 of numbers are in here. If we look at the first
100000 numbers, 39206 of them are divisible by a square number.
In that range, the n * (1- 6/π^{2})
guess can be 14 too low, at 80157, or 15 too high, at 47524. A
proof of this density can be found at planetmath.org.

ListPlot[FoldList[Plus,
0, Table[If[MoebiusMu[n] == 0, 1, 0], {n, 1, 100000 - 1}]] - Table[n
(1 - 6/Pi^2), {n, 1, 100000}], PlotJoined -> True, AspectRatio ->
1/7];

Figure 1. Differences between the real and
predicted density of squarefree numbers.

You might notice
three numbers in a row in the above list, {48, 49, 50}. It's a nice
problem
to find the first occurrence of 4 in a row. 22020 is the start
of 6 in a row. In the Online
Encyclopedia of Integer Sequences,
you can find a number that starts 16 square-divisible numbers in a
row.

In the "negative one" bin, Möbius placed
any number that factored into an odd number of distinct primes.
2 3 5 7 11 13 17 19 23 29 30 31 37 41 42 43 47 53 59 61 66 67 70 71
73 78 79 83 89 97. So, µ(29) = -1,
µ(30) = -1, and µ(31)
= -1. Every fourth number is divisible by 4, so there won't be more
than three in a row in this bin.

The primes are in this bin,
along with numbers like 66 (2×3×11), 665 (5×7×19),
6654 (2×3×1109), ..., 66549954999999999
(3×11×61×2238013×14772071) and
665499549999999999 (3×2063×107529415091291). This
series of numbers can be extended, but not by 9 (6654995499999999999
is divisible by a square number, so it goes in the "zero"
bin). The probability that a number falls in this bin, P(µ(n)
= -1) = 3/π^{2}, but
the prediction isn't nearly as accurate, as seen in the plot of
differences between the real and expected values.

ListPlot[FoldList[Plus,
0, Table[If[MoebiusMu[n] == -1, 1, 0], {n, 1, 100000 - 1}]] - Table[n
(3/Pi^2), {n, 1, 100000}], PlotJoined -> True, AspectRatio ->
1/7];

Figure 2. Differences between the real and
predicted density of µ(n) = -1.

In the "positive
one" bin, Möbius put all the numbers that factor into an
even number of distinct primes. For completeness, he put 1 into
this bin. 1 6 10 14 15 21 22 26 33 34 35 38 39 46 51 55 57 58 62 65
69 74 77 82 85 86 87 91 93.

Numbers like 6 (2x3), 69 (2x23),
699 (2x233), 6999, ..., and 69999069090909090990909090 are all in
this bin. As a puzzle, there are three distinct digits that can
be arranged to make product of two distinct primes. In fact,
all six arrangements give the product of two primes. Can you find the
smallest of these numbers?

The Möbius function, µ(*n*),
is strongly related to the Zeta (ζ) function.

Figure
3. Identities of the Riemann
Zeta function.

The
Möbius function has many
amazing identities.
Is it possible to figure out m(googolplex +1)? We know a lot of
factors of this number, 316912650057057350374175801344000001,
for example. A list of all the factors googolplex +1 would have more
digits than atoms in the universe, so it's a hard number to factor.
Is there some way of identifying whether a number has an odd or even
number of distinct prime factors without factoring?

Perhaps.
For ζ(*s*), consider *s*
= 14.1347251417347 I + 1/2? This is (approximately)
the first nontrivial zero of the Riemann
Zeta function.
ζ(*s*) = 0, for that
value. 1/z(*s*) = infinity. For these special zeroes on
the critical
line
(the first half
trillion
nontrivial zeroes have been computed), the sign of *ζ*(*s*)*
*and µ(*n*)
are strongly connected, via sgn[Re[*n*^{(14.1347251417347 i
+ 1/2)}]].

ListPlot[FoldList[Plus,
0, Table[Sign[Re[1/n^(14.1347251417347 I + 1/2)]] MoebiusMu[n], {n,
1, 100000}]], PlotJoined -> True, AspectRatio -> 1/7]

Figure
4. Cumulative accuracy of the Zeta Zero guessing method

In the first 100000
tries, the zetazero idea is correct a thousand times more than it is
wrong. Pretty lousy, really, but better than nothing. Through
this method, a wild guess at the Möbius value of googolplex+1 is
possible, without a complete factorization.

With a bit of
number sleuthing, Table[Sign[Re[1/n^(14.1347251417347 I + 1/2)]] ,
{n, 1, 2000}] changes signs at points Table[Round[2.17698
1.248896^k], {k, 1, 30}]. We want 2.17698 1.248896^k ==
10^(10^100) + 1. At this too-low level of accuracy, k is
closest to an even number, so I can guess that googolplex+1 has an
even number of factors. It would be nice to redo this
calculation with hundreds of digits of accuracy on all levels.

For
*n* = 1 to 20, m(*n*) = 1, -1, -1, 0, -1, 1, -1, 0, 0, 1,
-1, 0, -1, 1, 1, 0, -1, 0, -1, 0. The Cumulative sum is thus 1,
0, -1, -1, -2, -1, -2, -2, -2, -1, -2, -2, -3, -2, -1, -1, -2, -2,
-3, -3. This is known as Mertens Function, or *M*(*x*).
In 1885, Stieltjes
claimed to have a proof that |*M*(*x*)/*x*^{½}|
< 1 for all *x*. In 1897, Mertens said the same thing,
and now gets all the credit. In 1979, Cohen found that at x =
7725030629, *M*(*x*) = 43947, so |*M*(*x*)/*x*^{½}|
= 0.500011 ... the first time it gets over ½.

ListPlot[Drop[FoldList[Plus,
0, Table[MoebiusMu[n], {n, 1, 100000}]], 1]/Sqrt[Range[100000]],
PlotJoined -> True, AspectRatio -> 1/7, PlotRange -> {-.5,
.5}]

Figure 6. The bounded Mertens function, |*M*(*x*)/*x*^{½}|
.

It
would seem that the only way to calculate *M*(*x*) is to
sum up the m(*n*) values for all *n*<*x*, and the
only way to find m(*n*) is to factor *n*. However,
there is another
method

13939561178686765875648114721807011720559027347842649442846632872

Things
to work in

References

Gaussian Integer equivalents

Notebook
of all things used here.

Mertens function

Unsolved
problems.

*References:*

Finch,
Steven. Mathematical Constants.

Weisstein, Eric.
Moebius

*Mathematica
Code:*