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}

Advertisements

About Brent

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

One Response to More fun with Dirichlet convolution

  1. Pingback: The Riemann zeta function | The Math Less Traveled

Comments are closed.