Dirichlet convolution
I was skimming a book on number theory [1] recently and came across the following theorem that makes no sense out of context:
An arithmetical function f has an inverse if and only if f(1) 0.
Wait, what?! That's obviously false unless I've missed something. Maybe arithmetical function" is far more restrictive than I thought.
No, in this book an arithmetical function is simply a function on positive integers. In general it can be complex-valued, though early in the book all the examples are integer or rational valued.
What I was missing was the meaning of inverse." My first thought was that it meant inverse with respect to composition, but it meant inverse with respect to convolution.
Dirichlet convolutionGiven to arithmetic functions f and g, their Dirichlet convolution f*g is defined by
The sum is over all divisors of n and so, for example, the value of f * g at 6 would be
It's clear that convolution is commutative, and with a little more effort you can show that it's associative.
There is an identity element for convolution, the function (n) defined to be 1 if n = 1 and 0 otherwise. For any arithmetical function f, clearly f* = f because all the terms in the sum defining (f*)(n) are zero except the term f(n).
InverseIn the context of the theorem above, the inverse of a function f is another function g whose convolution with f gives the identity , i.e. g is the inverse of f if f*g = . Inverses, if they exist, are unique.
Now that we have the right definition of inverse in mind, the theorem above isn't obviously false, but it's not clear why it should be true. And it's a remarkable statement: with just the slightest restriction, i.e. f(1) 0, every arithmetical function has an inverse with respect to convolution. Not only that, the proof is constructive, so it shows how to compute the inverse.
For an arithmetical function f with f(1) 0, define its inverse function g by
and for n > 1 define
This definition is not circular even though g appears on both sides. On the right side g is only evaluated at arguments less than n since the sum restricts d to be greater than 1. The next post implements this recursive definition of g in Python.
Mobius inversion formulaDefine the function to be the constant function 1. Since (1) is not zero, has an inverse. Call that inverse .
If f = g*, then convolution of both sides with shows that f* = g. This is the Mobius inversion formula.
When presented this way, the Mobius inversion formula looks trivial. That's because all the hard work has been moved into prerequisites. Stated from scratch, the theorem is more impressive. Without using any of the definitions above, Mobius inversion formula says that if f is defined by
then
where
We initially defined implicitly as the inverse of the constant function 1. When written out explicitly we have the definition of the Mobius function above.
Related posts[1] An Introduction of Arithmetical Functions by Paul J. McCarthy, Springer-Verlag, 1986.
The post Dirichlet convolution first appeared on John D. Cook.