Dirichlet convolution
From AoPSWiki
For two functions 
, the Dirichlet convolution (or simply convolution, when the context is clear) 
of 
and 
is defined as
.
We usually only consider positive divisors of 
. We are often interested in convolutions of weak multiplicative functions; the set of weak multiplicative functions is closed under convolution. In general, convolution is commutative and associative; it also has an identity, the function 
defined to be 1 if 
, and 0 otherwise. Not all functions have inverses (e.g., the function 
has no inverse, as 
, for all functions 
), although all functions such that 
have inverses.
Closure of Weak Multiplicative Functions Under Convolution
Theorem. If 
are weak multiplicative functions, then so is 
.
Proof. Let 
be relatively prime. We wish to prove that 
.
For 
, let 
be the set of divisors of 
. For relatively prime , we claim that the function 
is a bijection from 
to 
. Indeed, for any 
and 
, so 
. Furthermore, for each 
, there exist unique 
such that , , 
. Thus 
is bijective. As a result of our claim, we have the identity
,
for any functions 
mapping subsets of 
into 
. In particular, we may let the domains of and 
be 
, and define 
and 
. We then have
.
But since each divisor of 
is relatively prime to every divisor of , we have
,
as desired.
Resources
This article is a stub. Help us out by expanding it.
