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!

Advertisements

About Brent

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 🙂

Comments are closed.