Monday Math 92

Last Monday, I discussed the Dirichlet convolution. We noted that it is commutative, associative, and has an identity element (the “unit function” ). We also noted that the Dirichlet convolution of two multiplicative functions is also multiplicative.

Now, suppose we have an arithmetic function f(n). Is it possible to find another arithmetic function, g(n), such that f*g=ε? First, note that ε(1)=1. Thus, we have 1=(f*g)(1)=f(1)g(1), and thus, we see that we can find , so long as f(1)≠0. Assuming that this is true, we now can examine higher n; using the fact that ε(n)=0 for n>0, we note that
.
Similarly,
,
,
and so on; more specifically, for n>0,
.
Thus, we can find the value of g(n) for each positive integer n recursively, in terms of the values of g for the proper divisors of n, so long as f(1)≠0, and we see that for a given f(n), g(n) is unique. This function, which we shall denote f-1(n), is called the Dirichlet inverse of f(n). Note that the Dirichlet inverse of the Dirichlet inverse of a function is that function, as we expect from inverse elements.
Writing the above recursive procedure succinctly:
,
and for n>0,
.

An important property of the Dirichlet inverse is that the Dirichlet inverse of a multiplicative function is also multiplicative. Thus, since the set of multiplicative functions is closed under the Dirichlet convolution, the Dirichlet convolution is commutative and associative, has an identity, and every multiplicative function has a multiplicative function as an inverse, we see that the multiplicative functions form an Abelian group under Dirichlet convolution.

Now, since the Dirichlet inverse of a multiplicative function is also multiplicative, we can limit the recursive procedure to the powers of primes; that is, we use

and then use , p prime and k>0, to get
,

For example, let’s consider the Möbius function μ(n). We have μ-1(1)=1, and, using
along with
,
we see

,
and, since for k>1, we see that all terms in the sum are zero except the i=k-1 term,

and thus, via this recursion, for any prime p and non-negative integer k; and thus
μ-1(n)=1(n), the constant function that returns 1 for all arguements.

This fact allows us to prove a relation known as the Möbius inversion formula, which states that for arithmetic functions f(n) and g(n), with
for every positive integer n, then
.
Note that in the notation of Dirichlet convolutions, the first relation is just g=f*1, and the second is f=μ*g. Now, if g=f*1, then
,
and we have proven the formula.

To show it in use, suppose that g(n) is the identity function id(n)=n, and we want to find f; that is, we want to find the function f(n) such that for every positive integer n. The Möbius inversion formula tells us that f(n)=(id*μ)(n). Using the fact that both id and μ are multiplicative, we see f is multiplicative, so for p prime and k>0,
,
and we should thus recognize that f(n)=(id*μ)(n)=φ(n), the totient function, and so .

We can also see that, since we showed last time that , the Möbius inversion formula then tells us that
.

Advertisements

Tags: , , , , , , , ,

3 Responses to “Monday Math 92”

  1. Monday Math 93 « Twisted One 151’s Weblog Says:

    […] Math 93 By twistedone151 Last Monday, I discussed the Dirichlet inverse. I showed that the Dirichlet inverse can be found by the […]

  2. Monday Math 95 « Twisted One 151’s Weblog Says:

    […] convolution, (Λ*1)(n)=ln(n). Note that since Λ(1)=0, the von Mangoldt function has no Dirichlet inverse. Now, let us consider a completely multiplicative function f(n), with Dirichlet inverse f-1(n), […]

  3. Monday Math 94 « Twisted One 151's Weblog Says:

    […] is their product, . Similarly, we can use the Möbius inversion formula relationship that , found here, to confirm that φ(n) has Dirichlet series generating function , as we found via Euler product […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: