Möbius Inversion with Liouville Function

This article concerns Möbius Inversion with the Liouville Function.  For ` n=p_1^{a_1}p_2^{a_2}...p_k^{a_k} `, the number of distinct prime factors of n is

Question
(i)  Prove that

(ii) Hence show that

Solution:-
(i) Note that ` \mu(d)=0 ` for divisors d containing any prime power of index 2 or higher.  We only need to consider divisors of the form ` d=p_{i_1}p_{i_2}...p_{i_h} `, where ` h = 0` is interpreted as ` d=1 `.
    ` \sum_{d|n}\mu(d)\lambda(d) `
= ` \sum_{h=0}^{k}\sum_{p_{i_1},p_{i_2},...,p_{i_h}} \mu(p_{i_1}p_{i_2}...p_{i_h})\lambda(p_{i_1}p_{i_2}...p_{i_h}) `
= ` \sum_{h=0}^{k}\sum_{p_{i_1},p_{i_2},...,p_{i_h}} (-1)^h(-1)^{1+1+...+1} `   (where 1+1+...+1 has h copies of 1)
= ` \sum_{h=0}^{k}\sum_{p_{i_1},p_{i_2},...,p_{i_h}} (-1)^{2h} ` = ` \sum_{h=0}^{k}\sum_{p_{i_1},p_{i_2},...,p_{i_h}} 1 ` = ` \sum_{h=0}^{k}((k),(h)) `
= ` 2^k `  = ` 2^{\omega(n)} `
(ii)  Recall that ` \lambda(\frac{n}{d})=\frac{\lambda(n)}{\lambda(d)}=\lambda(n)\lambda(d) `
     From the result in part (i) we multiply both sides by ` \lambda(n) ` to get
                  ` \sum_{d|n}\mu(d)\lambda(n)\lambda(d)= \lambda(n)2^{\omega(n)} `
                  ` \sum_{d|n}\mu(d)\lambda(\frac{n}{d})= \lambda(n)2^{\omega(n)} `
    Treating this as the "Möbius Inversed" formula, the "original" formula is
                  ` \sum_{d|n}\lambda(d)2^{\omega(d)}= \lambda(n) `
Hence
     ` \sum_{d|n}\lambda(\frac{n}{d})2^{\omega(d)} ` =   ` \sum_{d|n}\lambda(n)\lambda(d)2^{\omega(d)} ` =   ` \lambda(n)\cdot\sum_{d|n}\lambda(d)2^{\omega(d)} `
=   ` \lambda(n)\cdot\lambda(n) ` =   ` \lambda(n)^2 ` =   ` 1 `

[End]

Möbius Inversion Formula

Möbius Inversion Formula (by August Ferdinand Möbius) states that if ` Df ` the summatory function of f

then

 

where ` f ` is an arithmetic function.  This is more like a "formula machine", which, when given an input ` f `, gives you a version of formula as an output (Well, as long as you know what ` Df ` is).  ` \mu ` is the Möbius function.  [ By the way, Möbius was also famous for his Möbius strip. ]  Using Dirichlet Convolutions (* operation), the formula just says that

and since the *-inverse of the ` 1(n) ` function is the Möbius function ` \mu(n) `

the formula can be proven succinctly as follows.
Proof:     ` \mu \mbox{*} Df` `
` =  \mu \mbox{*} (1 \mbox{*} f) =  (\mu \mbox{*} 1) \mbox{*} f   =  delta_1 \mbox{*} f    =    f  `
(proven)

Example
For `f(n) = \phi(n)` the Euler totient function, we know that

Hence applying Möbius Inversion we have

i.e.                                     

since ` \phi(n) = (\mu * D\phi)(n)  = \sum_{d|n}\mu(d) \cdot D\phi(\frac{n}{d})  = \sum_{d|n}\mu(d) \cdot I(\frac{n}{d}) = \sum_{d|n}\mu(d) \cdot \frac{n}{d} `

Dirchlet Convolution

The Dirichlet convolution of arithmetic functions ƒ and g, is the arithmetic function ƒ * g  defined by

where d runs over all positive divisors of n.  This allows us to express certain sums over divisors more concisely and let us see their more elegant structure.

Properties
The Dirichlet convolution has some nice properties.  It is commutative

and associative

 and distributive over addition

 In fact, arithmetic functions together with * and + operations form a ring.


Dirichlet convolution's Identity Function
The unit function (or ` \epsilon ` function)

works like the Kronecker delta or the Dirac delta.  Think of it as a light bulb that switches on (gives a '1') when given ` n = 1 ` as an input and turns off when n is given any other value as input.  Under the operation of Dirichlet convolution (* operation), this function plays the role of the *-identity.  In other words, for all arithmetic functions ` f `,

The constant 1 function and the function identity ` I ` do not play the same role, unlike what we would expect for ordinary multiplication and function composition.  However, they are related by the formula

which is described here and proven here.

Divisor Sums and the inverse of the '1' function
The divisor sum ` Df ` of  ` f ` is

Thus we can think of the ` D ... ` operator as formally the same as ` 1 \mbox{*} ... `  The Inverse of ` 1 ` function under Dirichlet convolution turns out to be the Möbius function ` \mu ` as

This leads to the celebrated Möbius Inversion Formula.

Euler Totient Function Sum (Dirchlet Convolution Form)

Using Dirchlet Convolution, the totient sum formula

 

can be re-written more concisely as

in which ` \phi `, ` 1 `  and  ` I `  are arithmetic functions.  This theorem was proven here.

You see, mathematicians like to disguise complicated formulas with simpler-looking ones and they do that by inventing more arcane short-cuts.  Once the formulas have been simplified, they get bored and push the game further by deriving deeper results from these.  So the game seems to be: explore/gather ` \rightarrow ` compress/simplify ` \rightarrow ` explore/gather ` \rightarrow ` compress/simplify, ... and so on and on and on.