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 💡

Möbius Inversion

Contents