In my last post we saw that , that is, the Möbius function is the inverse of with respect to Dirichlet convolution. This directly leads to an interesting principle called Möbius inversion.

Möbius inversion. Suppose is defined for as the sum of another function over all the divisors of :

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

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

where, as usual, the sum is over all factorizations of into a product . This is the same as the previous equation, because if and only if , in which case . 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 is the same as saying (recall that taking the Dirichlet convolution with is the same as summing over all divisors). We can then take the Dirichlet convolution of both sides with :

In other words, Möbius inversion is really just saying that if , then , because is the inverse of .

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

For example, as seen in the picture above, .

Now, this is in the perfect format to apply Möbius inversion: the sum over all divisors of the function is equal to the function . So we conclude that

or, factoring out ,

which is interesting since it expresses as a fraction of .

Let’s use this to compute . We have

The prime factorization of is . We know that will be for any divisor with any repeated factors, so those all cancel out; we only need to consider divisors which correspond to subsets of . ( is the same example we used in our proof of the key property of the Möbius function.) So

Remembering that yields for an even number of prime factors and for an odd number, we can evaluate this as

(and we can use e.g. a computer to verify that this is correct). Note how this works: we start with and then subtract out all the numbers divisible by (all of them), as well as those divisible by () and (). But now we have subtracted some numbers multiple times, e.g. those which are divisible by both and . So we add back in the numbers which are divisible by ( of them), by (), and by (). Finally, we’ve now overcounted numbers which are divisible by all three, so we subtract off the numbers which are divisible by . 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!