Möbius Function & Inversion

The Möbius function and recovering f from its divisor sums.

The idea

Möbius inversion recovers an arithmetic function from its divisor sums: given $F(n) = \sum_{d \mid n} f(d)$ for every $n$, it returns $f$ itself. The tool is the Möbius function. Call an integer squarefree when no prime divides it twice.

Definition (Möbius function).

$\mu(n) = \begin{cases} 1 & n = 1 \\ (-1)^{k} & n \text{ is a product of } k \text{ distinct primes} \\ 0 & n \text{ is not squarefree.} \end{cases}$

The signs are chosen to make the divisor sums of $\mu$ collapse.

Lemma.

For every positive integer $n$, $\sum_{d \mid n} \mu(d)$ equals $1$ when $n = 1$ and $0$ when $n > 1$.

This collapse is what drives the inversion.

Theorem (Möbius inversion formula).

If $F(n) = \sum_{d \mid n} f(d)$ for every positive integer $n$, then for every $n$ $f(n) = \sum_{d \mid n} \mu(d)\, F(n/d).$

Summing over divisors and inverting with $\mu$ undo each other.

Ways to work on it

• Walkthrough. Define the Möbius function and use it to invert sums over divisors.
• Practice. Evaluate the Möbius function at a given integer.
• Hardest. Invert a divisor sum to recover a hidden arithmetic function.

Not sure where to start? Take the ten-question placement test.