## Möbius inversion

In my last post we saw that $\mu \ast \mathbf{1} = \varepsilon$, that is, the Möbius function $\mu$ is the inverse of $\mathbf{1}$ with respect to Dirichlet convolution. This directly leads to an interesting principle called Möbius inversion.

Möbius inversion. Suppose $g(n)$ is defined for $n \geq 1$ as the sum of another function $f$ over all the divisors of $n$:

$\displaystyle g(n) = \sum_{d \mid n} f(d).$

Then we can “invert” this relationship to express $f$ as a sum over $g$:

$\displaystyle f(n) = \sum_{d \mid n} \mu(d) g(n/d).$

The above is the “traditional” way of stating the principle, but I like to write it in this equivalent, more symmetric way:

$\displaystyle f(n) = \sum_{ab = n} \mu(a) g(b)$

where, as usual, the sum is over all factorizations of $n$ into a product $ab$. This is the same as the previous equation, because $ab = n$ if and only if $a \mid n$, in which case $b = n/a$. But now it becomes more clear that we are dealing with a Dirichlet convolution. Can you see how to prove this?

Proof. If we think in terms of Dirichlet convolution, the proof is almost trivial. Note first that saying $g(n) = \sum_{d \mid n} f(n)$ is the same as saying $g = \mathbf{1} \ast f$ (recall that taking the Dirichlet convolution with $\mathbf{1}$ is the same as summing over all divisors). We can then take the Dirichlet convolution of both sides with $\mu$:

$\displaystyle \begin{array}{rcl} \mu \ast g &=& \mu \ast (\mathbf{1} \ast f) \\ &=& (\mu \ast \mathbf{1}) \ast f \\ &=& \varepsilon \ast f \\ &=& f.\end{array}$

In other words, Möbius inversion is really just saying that if $f = \mathbf{1} \ast g$, then $\mu \ast f = g$, because $\mu$ is the inverse of $\mathbf{1}$.

Let’s try an example! Recall that $\varphi$ denotes the Euler totient function, which counts how many positive integers less than or equal to $n$ are relatively prime to $n$. For example, $\varphi(5) = 4$ since all the positive integers less than or equal to $5$ (other than $5$ itself) are relatively prime to it, and more generally $\varphi(p) = p-1$ for any prime $p$. As another example, $\varphi(12) = 4$ since the only positive integers between $1$ and $11$ which are relative prime to $12$ are $1$, $5$, $7$, and $11$. In a previous post we considered a visual proof that

$\displaystyle \sum_{d \mid n} \varphi(d) = n:$

For example, as seen in the picture above, $12 = \varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4$.

Now, this is in the perfect format to apply Möbius inversion: the sum over all divisors of the function $g(n) = \varphi(n)$ is equal to the function $f(n) = n$. So we conclude that

$\displaystyle \varphi(n) = \sum_{d \mid n} \mu(d) (n/d)$

or, factoring out $n$,

$\displaystyle \varphi(n) = n \sum_{d \mid n} \frac{\mu(d)}{d}$

which is interesting since it expresses $\varphi(n)$ as a fraction of $n$.

Let’s use this to compute $\varphi(360)$. We have

$\displaystyle \varphi(360) = \sum_{d \mid 360} \mu(d) (360/d).$

The prime factorization of $360$ is $2^3 \cdot 3^2 \cdot 5$. We know that $\mu(d)$ will be $0$ for any divisor with any repeated factors, so those all cancel out; we only need to consider divisors which correspond to subsets of $\{2,3,5\}$. ($n = 360$ is the same example we used in our proof of the key property of the Möbius function.) So

$\displaystyle \begin{array}{rcl} \varphi(360) &=& \mu(1) \cdot 360 \\ &+& \mu(2) \cdot 180 \\ &+& \mu(3) \cdot 120 \\ &+& \mu(5) \cdot 72 \\ &+& \mu(2\cdot 3) \cdot 60 \\ &+& \mu(2 \cdot 5) \cdot 36 \\ &+& \mu(3 \cdot 5) \cdot 24 \\ &+& \mu(2 \cdot 3 \cdot 5) \cdot 12 \end{array}$

Remembering that $\mu$ yields $1$ for an even number of prime factors and $-1$ for an odd number, we can evaluate this as

$\displaystyle \varphi(360) = 360 - 180 - 120 - 72 + 60 + 36 + 24 - 12 = 96.$

(and we can use e.g. a computer to verify that this is correct). Note how this works: we start with $360$ and then subtract out all the numbers divisible by $2$ (all $180$ of them), as well as those divisible by $3$ ($120$) and $5$ ($72$). But now we have subtracted some numbers multiple times, e.g. those which are divisible by both $2$ and $3$. So we add back in the numbers which are divisible by $2 \cdot 3$ ($60$ of them), by $2 \cdot 5$ ($36$), and by $3 \cdot 5$ ($24$). Finally, we’ve now overcounted numbers which are divisible by all three, so we subtract off the $12$ numbers which are divisible by $2 \cdot 3 \cdot 5$. Egad! This seems really similar to PIE! Indeed, this is no accident: it turns out that the Principle of Inclusion-Exclusion is really just another kind of Möbius inversion. But that’s a subject for another post!

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in combinatorics, proof and tagged , , , , . Bookmark the permalink.

### 3 Responses to Möbius inversion

1. sn0wleopard says:

Ah, Möbius inversion is so much easier to understand via Dirichlet convolution!

• Brent says:

I know, right!? I now think it is pedagogically irresponsible to teach it any other way. But I had to work really hard and read a lot of different sources to put all of this together.

• sn0wleopard says:

Agreed! Thanks for putting all bits together. The whole series is great, please keep it going 🙂