Sum of Möbius function over Complementary Divisors of Square-Divisors

While considering the summatory function of the Liouville Function, we found that

which takes the value of 1 when n is a perfect square and 0 otherwise.  The following question was given as a challenge and we present its solution in this article.

Question
Find

Solution:-
From
     ` \sum_{d|n}\lambda(d)=\bb{1}_\text{PerfectSquare}(n) `
using the Möbius Inversion formula, we have
     ` \sum_{d|n}\mu(\frac{n}{d})\bb{1}_\text{PerfectSquare}(d)=\lambda(n) `
The summands will be zero except when ` d=D^2 `.  Hence we get
     ` \sum_{D^2|n}\mu(\frac{n}{D^2}) =\lambda(n) `
[End]

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]

Liouville Function, Summatory of

We introduced the Liouville function here.  The summatory function of ` f(n) ` is defined as

In this post, we examine the summatory function of the Liouville function.


Question
Prove that

Solution:-
   Note that for ` n=p^a ` where p is a prime number,
   ` \sum_{d|n}\lambda(d) `  =   ` \sum_{j=0}^a \lambda(p^j) `  =   ` \sum_{j=0}^a (-1)^j `
=   ` \frac{1\cdot(1-(-1)^{a+1})}{1-(-1)}`  =   ` \frac{1-(-1)^{a+1}}{2} `
=   ` \bb{1}_\text{even}(a) `  =   ` {(1,\text{if }a\text{ is even}),(0,\text{if }a\text{ is odd}):} `       ("Even indicator function")

Hence for ` n=p_1^{a_1}p_2^{a_2}...p_k^{a_k} `
   ` \sum_{d|n}\lambda(d) `  =   ` \sum_{i_1,i_2,...,i_k}\lambda(p_1^{i_1}p_2^{i_2}...p_k^{i_k}) ` =   ` \sum_{i_1,i_2,...,i_k}\lambda(p_1^{i_1})\lambda(p_2^{i_2})...\lambda(p_k^{i_k}) `
=   ` \sum_{i_1=0}^{a_1}\lambda(p_1^{i_1})\sum_{i_2=0}^{a_2}\lambda(p_2^{i_2})...\sum_{i_1=0}^{a_k}\lambda(p_k^{i_k}) `
=   ` \bb{1}_\text{even}(a_1)\bb{1}_\text{even}(a_2)...\bb{1}_\text{even}(a_k) ` 
=   ` {(1,\text{if }\forall i\text{ }a_i\in2ZZ),(0,\text{otherwise}):} `      =   ` {(1,\text{if }n\text{ is a perfect square}),(0,\text{otherwise}):} `

Challenge: Find ` \sum_{D^2|n}\mu(\frac{n}{D^2}) `, where ` \mu() ` is the Möbius function.  Solution here.

Liouville Function - Introduction

The Liouville function, after Joseph Liouville, is defined for ` n=p_1^{a_1}p_2^{a_2}...p_k^{a_k} ` as

interpreted so that ` \lambda(1)=1 `.  It is quite obvious that

This, coupled with the fact that the Liouville function is completely multiplicative (see below), we have

 

Question
Prove that the Liouville function is completely multiplicative i.e.

for all integers m and n (not necessarily coprime).
Solution:-
   Let ` p_1,p_2,...,p_k ` be the list of primes appearing in m and/or n. Write ` m=p_1^{a_1}p_2^{a_2}...p_k^{a_k} ` and ` n=p_1^{b_1}p_2^{b_2}...p_k^{b_k} `, in which any of the non-negative integers ` a_1,a_2, ..., a_k  ` and ` b_1,b_2, ..., b_k  ` can be zero.  Then
                     ` mn=p_1^{a_1+b_1}p_2^{a_2+b_2}...p_k^{a_k+b_k} `
Consequently
   ` \lambda(mn)=(-1)^{(a_1+b_1)+(a_2+b_2)+...+(a_k+b_k)} `
            ` =(-1)^{(a_1+a_2+...+a_k)+(b_1+b_2+...+b_k)} `
            ` =(-1)^{a_1+a_2+...+a_k}(-1)^{b_1+b_2+...+b_k} `
            ` =\lambda(m)\lambda(n) `
[End]


More about the Liouville function here, and a result involving Möbius Inversion function here.

An ascending, then descending sum (2)

In my inaugural blog post I talked about an epiphany that I had regarding the relation

and a pictorial "proof without words".  The mathematical lesson to learn here is to be mentally flexible and look at things from a variety of ways: vertically, horizontally and diagonally.  After all, that was how Georg Cantor took the bull by the horns by tackling uncountable infinite numbers with his diagonal argument.

Seeing that there is someone with high standards who had done Java applet and even gave an exposition of "proof without words", I decided to step up my game and post an Adobe Flash interactive animation of what I had in mind.  You can even click on the "rotate" button to change your "point of view".



I had some fun learning and doing it in Adobe Flash ActionScript 3. AS3 does things differently but is more consistent that the older versions. However, there are some issues with Flash's timing and updating, which I have not found a work-around. Meanwhile, please be gentle with the applet.

Dirichlet convolution is commutative

The Dirichlet convolutions was introduced here.  The following illustrates a proof technique that avoids writing ` \frac{n}{d} ` over and over again.
Theorem

Proof:-
For any ` n ` we have
   ` (f \mbox{*} g)(n)  `
= ` \sum_{n=cd}f (c) \cdot g(d) `
= ` \sum_{n=cd}f (d) \cdot g(c) `  [ as ` d ` runs through all divisors of  ` n `, so does ` c = \frac{n}{d} ` ]
= ` \sum_{n=cd}g(c) \cdot f(d) `
= ` (g \mbox{*} f)(n)  `
(proven) 

The proof technique can be extended to prove the associativity law.

Dirchlet Convolution is Distributive over Addition

The Dirichlet Convolution has the following property:-

The proof is a straightforward exercise.


Proof:-

For any ` n ` we have
   ` [f \mbox{*} (g + h)](n)  `
= ` \sum_{d|n}f(d) \cdot (g+h)(n/d) `
= ` \sum_{d|n}\{ f(d) \cdot g(n/d) + f(d) \cdot h(n/d) \}`
= ` \sum_{d|n}f(d) \cdot g(n/d) + \sum_{d|n}f(d) \cdot h(n/d) `
= ` (f \mbox{*}g)(n) + (f \mbox{*}h)(n)  `
= ` (f \mbox{*}g + f \mbox{*}h)(n)  `

(proven)

Dirchlet Convolution is Associative

The following is one of the properties of Dirichlet convolutions. The commutative law was proven by writing  ` n ` as a product of two factors i.e. ` n = cd `, and writing ` c ` instead of the more cumbersome `\frac{n}{d}`.  We extend this technique to three factors here.  By a summation over ` n = uvw `, I mean: take all possible combinations of ` u `, ` v ` and ` w ` as long as ` n = uvw `.


Theorem

Proof:-
For any ` n ` we have
   ` [(f \mbox{*} g) \mbox{*} h](n)  `
= ` \sum_{d|n}(f \mbox{*} g)(d) \ h(n/d) `
= ` \sum_{n=dw}(f \mbox{*} g)(d) \  h(w) `
= ` \sum_{n=dw} { \sum_{d=uv} f(u) \  g(v) } \  h(w) `
= ` \sum_{n=uvw} f(u) \  g(v) \  h(w) `
= ` \sum_{n=uc} f(u)  \  { \sum_{c=vw} g(v) \  h(w) } `
= ` \sum_{n=uc} f(u)  \  (g \mbox{*} h)(c) `
= ` [f \mbox{*} (g \mbox{*} h)](n)  `
(proven)

Arithmetic Functions

An arithmetic function is a function ` ZZ^+ \rightarrow S ` where `S \subseteq RR \subseteq CC `.  They try to capture the essence of various properties of positive whole numbers.

Examples
The constant ` 1 ` function maps every  n  to the number 1.

The identity function ` I ` maps every  n  to itself.

Möbius function ` \mu `

The unit function ` \delta_1 ` (or ` \epsilon ` function)

Euler's totient function ` \phi `

Number of divisors ` \tau `

Sum of divisors ` \tau `

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.

Euler Totient Function (Example 2)

... answers to question posed here.

Example 2

For `n=12`, each of the numbers in `\{1,2,...,12\}` belongs to exactly one of the subsets
     `S_1  = \{1, 5, 7, 11\}`
     `S_2  = \{2, 10\}`
     `S_3  = \{3, 9\}`
     `S_4  = \{4, 8\}`
     `S_6  = \{6\}`
     `S_12 = \{12\}`
 Each subset is in fact an equivalence class of the relation ~ (where `a~b \Leftrightarrow`
`\gcd(a,12)=\gcd(b,12)`).  `S_h` means the equivalence class (or subset) of all the numbers whose highest common factor with `12` is  `h`.  Now observe
     `S_1  = \{1, 5, 7, 11\}`,   `\divide  1`, get `\{1, 5, 7, 11\}  \subseteq \{1,...,12\}`  `\#=\phi(12)`
     `S_2  = \{2, 10\}`,   `\divide  2`, get `\{1, 5\}                       \subseteq \{1,...,6\}`   `\#=\phi(6)`
     `S_3  = \{3, 9\}`,   `\divide  3`, get `\{1, 3\}                     \subseteq \{1,...,4\}`    `\#=\phi(4)`
     `S_4  = \{4, 8\}`,   `\divide  4`, get `\{1, 2\}                         \subseteq \{1,...,3\}`   `\#=\phi(3)`
     `S_6  = \{6\}`,               `\divide  6`, get `\{1}                   \subseteq \{1,...,2\}`   `\#=\phi(2)`
     `S_12 = \{12\}`,            `\divide 12`, get `\{1\}                      \subseteq \{1\}`          `\#=\phi(1)`
Hence
     `\#S_1 + \#S_2 + \#S_3 + \#S_4 + \#S_6 + \#S_12`
=   `\phi(12) + \phi(6) + \phi(4) + \phi(3) + \phi(2) + \phi(1)`
=   `4 + 2 + 2 + 2 + 1 + 1`
=   12

Euler Totient Function

The Euler Totient Function is an arithmetic function defined as

i.e. the number of elements `k \in \{1,...,n \}`  that are coprime with `n`.

Theorem

    

Proof:- Note that each  `k \in S=\{1,...,n \}`  has a highest common factor `h=\gcd(k,n)` with `n` and of course this is a factor of n.  So each `k` belongs to a unique subset `S_h`, and these subsets have no overlapping elements.  In other words `S=\{1,...,n \}` can be partitioned into a disjoint union
     `S = uuu_h  S_h `
Counting the elements, we have
`#S`    =  `\sum_{h|n}# S_h`
`n`    =  `\sum_{h|n}# \{k:\gcd(k,n)=h\}`
        =  `\sum_{h|n}# \{k:\gcd(k,\frac{n}{h})=1\} `
        =  `\sum_{h|n}\phi(\frac{n}{h})`
        =  `\sum_{d|n}\phi(d)`
[as `h` runs through all the divisors of `n`, `d=\frac{n}{h}` will also run through all the divisors of `n`]
(proven)
Here is another way to express the formula.

Example 1
For `n=10`, each of the numbers in `\{1,2,...,10\}` belongs to exactly one of the subsets
     `S_1  = \{1, 3, 7, 9\}`
     `S_2  = \{2, 4, 6, 8\}`
     `S_5  = \{5\}`
     `S_10 = \{10\}`
 Each subset `S_h`  is an equivalence class of the relation ~ (where `a~b \Leftrightarrow``a` and `b` share the same the highest common factor `h` with 10).  Now observe
     `S_1  = \{1, 3, 7, 9\}`,   `\divide  1`, get `\{1, 3, 7, 9\}  \subseteq \{1,...,10\}`  `\#=\phi(10)`
     `S_2  = \{2, 4, 6, 8\}`,   `\divide  2`, get `\{1, 2, 3, 4\}   \subseteq \{1,...,5\}`   `\#=\phi(5)`
     `S_5  = \{5\}`            ,   `\divide  5`, get `\{1}               \subseteq \{1,...,2\}`    `\#=\phi(2)`
     `S_10 = \{10\}`        ,    `\divide 10`, get `\{1\}                   \subseteq \{1\}`              `\#=\phi(1)`
Hence
     `\#S_1 + \#S_2 + \#S_5 + \#S_10`
=   `\phi(10) + \phi(5) + \phi(2) + \phi(1)`
=   `4 + 4 + 1 + 1`
=   10

Example 2
Try to work out the example for `n=12`, and check your work here.

An ascending, then descending sum

While tutoring lower secondary olympiad maths, my student and I encountered an interesting sum

The numbers start from 1 and go up to a maximum value $k$, and then go down back to 1. If one knows summation formulas, there is no problem with evaluating this sum.  The answer is $k^2$.

Using $1 + 2 + ... + k = \frac{k(k+1)}{2}$ (provable using Gauss' trick), we can proceed as follows:-
   $1 + 2 + ... + (k-1) + k + (k-1) + ... + 2 + 1 $
= $[1 + 2 + ... + k] + [(k-1) +  ... + 2 + 1] $
= $ \frac{(k - 1) k}{2} + \frac{k(k+1)}{2} $  = $ \frac{(k - 1 + k + 1) k}{2} $
= $ \frac{(2 k ) k}{2} $  = $ k^2 $

Straightforward exercise for the left-brain, especially for older kids in Junior College.  But ... where is the insight?  Thanks to Descartes, Mathematics is as much a right-brained activity as a left-brained one.


Then my right brain had an epiphany ("ting!" with flashing lightbulbs).  I realised that there is a way to visualise this fact and got the "Hey!  I never looked at it this way" kind of feeling.


Challenge to the reader: Is there a way to visualise this sum?  Can you do a "Proof without words"?

Think.  Then refer to here.