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/π², 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/π²) 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/π², 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: