Archive for January, 2009

A playful approach to the Moebius Function

January 25, 2009

The Moebius Function \mu of number theory seems to be defined in a rather artificial way:

\mu (n) = 1 if n is the product of an even number of distinct primes,
\mu (n) = -1 if n is the product of an odd number of distinct primes and
\mu (n) = 0   otherwise, i.e. if n is  not squarefree.

James Tanton gives a playful approach to \mu in his article “An Illuminating Introduction to the Moebius Function”, MAA Focus, March 2007, P. 16-17. It starts with the following game: Imagine a row of 100 coins — all equal and all with heads up. Also imagine 100 players. The first player flips every coin. The second player flips every other coin, the third player every third coin, …, the nth player flips every nth coin. Now, the question arises: Which coins show tails up after 100 rounds? Amazingly, it is all those whose position is a perfect square.

This game is then generalized to a row of light bulbs where every light bulb can cycle through k different states: 0, 1, ..., k-1 and returns to state 0 after state k-1. Imagine an infinite row of such light bulbs and face the following task: Which of the players (characterized above) do you have to send down the row (several ones certainly repeatedly) to set the first bulb into state 1 and all others into state 0? Tanton then proves the following claim:

If the nth player works the row \mu(n) times (where we read -1  as k-1), then bulb 1 will be in state 1 and all others will be in state 0.

This approach also gives access to the multiplicity of the Moebius function and the Moebius inversion formula.