More fun with Dirichlet convolution

I’m back after a bit of a hiatus for the holidays! Last time we saw how the principle of Möbius inversion arises from considering the $\mu$ function from the point of view of Dirichlet convolution. Put simply, the Möbius function $\mu$ is the inverse of $\mathbf{1}$ with respect to Dirichlet convolution. As an example, we noted that $\mathbf{1} \ast \varphi = \mathit{id}$ (that is, the sum of $\varphi(d)$ over all divisors $d$ of $n$ is equal to $n$ ), and hence by Möbius inversion $\varphi = \mu \ast \mathit{id}$ .

This is far from earth-shattering, but it’s fun to see how a number-theoretic function like $\varphi$ arises in a simple formula involving Dirichlet convolution, and how Möbius inversion allows us to quickly derive a related but non-obvious fact. Let’s do a few more!

First, let’s consider $\mathbf{1} \ast \mathbf{1}$ . We have

$\displaystyle (\mathbf{1} \ast \mathbf{1})(n) = \sum_{d \mid n} \mathbf{1}(d) \mathbf{1}(n/d) = \sum_{d \mid n} 1,$

which is just counting the number of divisors of $n$ . This function is often denoted $\tau$ . For example, $12$ has six divisors (namely, 1, 2, 3, 4, 6, and 12), so $\tau(12) = 6$ . Likewise $\tau(7) = 2$ (1 and 7), $\tau(4) = 3$ (1, 2, and 4), and so on.

The above equation can be restated as $\mathbf{1} \ast \mathbf{1} = \tau$ , so by Möbius inversion, we immediately conclude that $\mathbf{1} = \mu \ast \tau$ , that is,

$\displaystyle 1 = \sum_{ab = n} \mu(a) \tau(b).$

For example, we can check this for $n = 12$ :

$\displaystyle \begin{array}{l} \mu(1) \tau(12) + \mu(2) \tau(6) + \mu(3) \tau(4)\\[1em] + \mu(4) \tau(3) + \mu(6) \tau(2) + \mu(12) \tau(1) \\[1em] = 6 - 4 - 3 + 0 + 2 + 0 \\[1em] = 1 \end{array}$

indeed.

As another example, $\mathbf{1} \ast \mathit{id}$ gives us $\sum_{d \mid n} d$ , the sum of the divisors of $n$ . This is usually denoted $\sigma$ . For example, $\sigma(12) = 1+2+3+4+6+12 = 28$ , $\sigma(6) = 1+2+3+6 = 12$ , $\sigma(7) = 1+7 = 8$ , and so on. Often we also define $s(n) = \sigma(n) - n$ to be the sum of all the divisors of $n$ other than $n$ itself, i.e. the proper divisors. Perfect numbers like 6 and 28 are those for which $n = s(n)$ .

Again, since $\mathbf{1} \ast \mathit{id} = \sigma$ , by Möbius inversion we immediately conclude $\mathit{id} = \mu \ast \sigma$ ; for example, again when $n = 12$ , we have

$\displaystyle \begin{array}{l} \mu(1) \sigma(12) + \mu(2) \sigma(6) + \mu(3) \sigma(4)\\[1em] + \mu(4) \sigma(3) + \mu(6) \sigma(2) + \mu(12) \sigma(1) \\[1em] = 28 - 12 - 7 + 0 + 3 + 0 \\[1em] = 12. \end{array}$

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →