# Möbius Inversion

Suppose for some (not necessarily multiplicative) number-theoretic function $$f$$

$F(n) = \sum_{d|n} f(d) .$

Can we make $$f(n)$$ the subject of this equation?

We’ll see that we can find a function $$\mu$$ such that

$f(n) = \sum_{d|n} \mu(n/d) F(d) = \sum_{d|n} \mu(d) F(n/d) .$

and we call this process Möbius inversion.

We have

\begin{aligned} \sum_{d|n} \mu(d) F(n/d) &=& \sum_{d|n}\mu(d) \sum_{r|\frac{n}{d}} f(r) \\ &=& \sum_{d r |n} \mu(d)f(r) \\ &=& \sum_{r |n} f(r) \sum_{d|(n/r)} \mu(d) \end{aligned}

If we want this equal to $$f(n)$$ we need $$\mu$$ to satisfy

$\sum_{d|m}\mu(d) = \begin{cases} 0, & m > 1 \\ 1, & m = 1 \end{cases}$

A little thought leads to this unique solution, known as the Möbius function:

$\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & p^2 | n \textrm{ for some prime }p \\ (-1)^r & n = p_1...p_r \textrm{ for distinct primes }p_i \end{cases}$

Notice $$\mu$$ is multiplicative, which implies $$f(n)$$ is multiplicative if $$F(n)$$ is. In summary,

Theorem:

$F(n) = \sum_{d|n} f(d)$

if and only if

$f(n) = \sum_{d|n} \mu(n/d) F(d)$

and $$f(n)$$ is multiplicative if and only if $$F(n)$$ is multiplicative.

Example: From before $$n = \sum_{d|n} \phi(n)$$. Write $$n = p_1^{k_1}...p_m^{k_m}$$. Then

\begin{aligned} \phi(n) &=& \sum_{d|n} \mu(d) \frac{n}{d} \\ &=& n \sum_{d|n} \mu(d) \frac{1}{d} \\ &=& n \left(1 - \sum_i \frac{1}{p_i} + \sum_{i\ne j} \frac{1}{p_i p_j} - ...\right) \\ &=& n \left(1 - \frac{1}{p_1}\right)...\left(1 - \frac{1}{p_m}\right) \end{aligned}

which is another way to derive the formula for $$\phi$$.

Gauss encountered the Möbius function over 30 years before Möbius when he showed that the sum of the generators of $$\mathbb{Z}_p^*$$ is $$\mu(p-1)$$. More generally, if $$\mathbb{Z}_n^*$$ has a generator, then the sum of all the generators of $$\mathbb{Z}_n^*$$ is $$\mu(\phi(n))$$. This can be seen by considering the sums of the roots of polynomials of the form $$x^d - 1$$ where $$d | \phi(n)$$.

Ben Lynn blynn@cs.stanford.edu 💡