## 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}$