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
     ${\displaystyle \sum _{d|n}\lambda \left(d\right)=1_{\text{PerfectSquare}}\left(n\right)}$
using the Möbius Inversion formula, we have
     ${\displaystyle \sum _{d|n}\mu \left(\frac{n}{d}\right)1_{\text{PerfectSquare}}\left(d\right)=\lambda \left(n\right)}$
The summands will be zero except when ${\displaystyle d=D^2}$.  Hence we get
     ${\displaystyle \sum _{D^2|n}\mu \left(\frac{n}{D^2}\right)=\lambda \left(n\right)}$
[End]

Möbius Inversion with Liouville Function

This article concerns Möbius Inversion with the Liouville Function.  For ${\displaystyle 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 ${\displaystyle \mu \left(d\right)=0}$ for divisors d containing any prime power of index 2 or higher.  We only need to consider divisors of the form ${\displaystyle d=p_{i_1}{p}_{i_2}...p_{i_h}}$, where ${\displaystyle h=0}$ is interpreted as ${\displaystyle d=1}$.
    ${\displaystyle \sum _{d|n}\mu \left(d\right)\lambda \left(d\right)}$
= ${\displaystyle \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})}$
= ${\displaystyle \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)
= ${\displaystyle \sum _{h=0}^k\sum _{p_{i_1},p_{i_2},...,p_{i_h}}{(-1)}^{2h}}$ = ${\displaystyle \sum _{h=0}^k\sum _{p_{i_1},p_{i_2},...,p_{i_h}}1}$ = ${\displaystyle \sum _{h=0}^k\left(\begin{array}{c}k\\ h\end{array}\right)}$
= ${\displaystyle 2^k}$  = ${\displaystyle 2^{\omega \left(n\right)}}$
(ii)  Recall that ${\displaystyle \lambda \left(\frac{n}{d}\right)=\frac{\lambda \left(n\right)}{\lambda \left(d\right)}=\lambda \left(n\right)\lambda \left(d\right)}$
     From the result in part (i) we multiply both sides by ${\displaystyle \lambda \left(n\right)}$ to get
                  ${\displaystyle \sum _{d|n}\mu \left(d\right)\lambda \left(n\right)\lambda \left(d\right)=\lambda \left(n\right)2^{\omega \left(n\right)}}$
                  ${\displaystyle \sum _{d|n}\mu \left(d\right)\lambda \left(\frac{n}{d}\right)=\lambda \left(n\right)2^{\omega \left(n\right)}}$
    Treating this as the "Möbius Inversed" formula, the "original" formula is
                  ${\displaystyle \sum _{d|n}\lambda \left(d\right)2^{\omega \left(d\right)}=\lambda \left(n\right)}$
Hence
     ${\displaystyle \sum _{d|n}\lambda \left(\frac{n}{d}\right)2^{\omega \left(d\right)}}$ =   ${\displaystyle \sum _{d|n}\lambda \left(n\right)\lambda \left(d\right)2^{\omega \left(d\right)}}$ =   ${\displaystyle \lambda \left(n\right)\cdot \sum _{d|n}\lambda \left(d\right)2^{\omega \left(d\right)}}$
=   ${\displaystyle \lambda \left(n\right)\cdot \lambda \left(n\right)}$ =   ${\displaystyle \lambda {\left(n\right)}^2}$ =   ${\displaystyle 1}$

[End]

Liouville Function, Summatory of

We introduced the Liouville function here.  The summatory function of ${\displaystyle f\left(n\right)}$ is defined as

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


Question
Prove that

Solution:-
   Note that for ${\displaystyle n=p^a}$ where p is a prime number,
   ${\displaystyle \sum _{d|n}\lambda \left(d\right)}$  =   ${\displaystyle \sum _{j=0}^a\lambda \left(p^j\right)}$  =   ${\displaystyle \sum _{j=0}^a{(-1)}^j}$
=   ${\displaystyle \frac{1\cdot (1-{(-1)}^{a+1})}{1-(-1)}}$  =   ${\displaystyle \frac{1-{(-1)}^{a+1}}{2}}$
=   ${\displaystyle 1_{\text{even}}\left(a\right)}$  =   ${\displaystyle \{\begin{array}{ll}1& \text{if}a\text{is even}\\ 0& \text{if}a\text{is odd}\end{array}}$       ("Even indicator function")

Hence for ${\displaystyle n=p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}}$
   ${\displaystyle \sum _{d|n}\lambda \left(d\right)}$  =   ${\displaystyle \sum _{i_1,i_2,...,i_k}\lambda (p_1^{i_1}{p}_2^{i_2}...p_k^{i_k})}$ =   ${\displaystyle \sum _{i_1,i_2,...,i_k}\lambda \left(p_1^{i_1}\right)\lambda \left(p_2^{i_2}\right)...\lambda \left(p_k^{i_k}\right)}$
=   ${\displaystyle \sum _{i_1=0}^{a_1}\lambda \left(p_1^{i_1}\right)\sum _{i_2=0}^{a_2}\lambda \left(p_2^{i_2}\right)...\sum _{i_1=0}^{a_k}\lambda \left(p_k^{i_k}\right)}$
=   ${\displaystyle 1_{\text{even}}\left(a_1\right)1_{\text{even}}\left(a_2\right)...1_{\text{even}}\left(a_k\right)}$ 
=   ${\displaystyle \{\begin{array}{ll}1& \text{if}\forall i{a}_i\in 2\mathbb{Z}\\ 0& \text{otherwise}\end{array}}$      =   ${\displaystyle \{\begin{array}{ll}1& \text{if}n\text{is a perfect square}\\ 0& \text{otherwise}\end{array}}$

Challenge: Find ${\displaystyle \sum _{D^2|n}\mu \left(\frac{n}{D^2}\right)}$, where ${\displaystyle \mu \left(\right)}$ is the Möbius function.  Solution here.

Liouville Function - Introduction

The Liouville function, after Joseph Liouville, is defined for ${\displaystyle n=p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}}$ as

interpreted so that ${\displaystyle \lambda \left(1\right)=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 ${\displaystyle p_1,p_2,...,p_k}$ be the list of primes appearing in m and/or n. Write ${\displaystyle m=p_1^{a_1}{p}_2^{a_2}...p_k^{a_k}}$ and ${\displaystyle n=p_1^{b_1}{p}_2^{b_2}...p_k^{b_k}}$, in which any of the non-negative integers ${\displaystyle a_1,a_2,...,a_k }$ and ${\displaystyle b_1,b_2,...,b_k }$ can be zero.  Then
                     ${\displaystyle mn=p_1^{a_1+b_1}{p}_2^{a_2+b_2}...p_k^{a_k+b_k}}$
Consequently
   ${\displaystyle \lambda \left(mn\right)={(-1)}^{(a_1+b_1)+(a_2+b_2)+...+(a_k+b_k)}}$
            ${\displaystyle ={(-1)}^{(a_1+a_2+...+a_k)+(b_1+b_2+...+b_k)}}$
            ${\displaystyle ={(-1)}^{a_1+a_2+...+a_k}{(-1)}^{b_1+b_2+...+b_k}}$
            ${\displaystyle =\lambda \left(m\right)\lambda \left(n\right)}$
[End]


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

A Polar Double Integral

  ${\displaystyle {\int }_0^{\frac{\pi }{2}}{\int }_0^{1+sin\theta }\theta r\text{d}r\text{d}\theta }$
= ${\displaystyle {\int }_0^{\frac{\pi }{2}}\theta {\left[\frac{1}{2}{r}^2\right]}_0^{1+sin\theta }\text{d}\theta }$
= ${\displaystyle {\int }_0^{\frac{\pi }{2}}\frac{1}{2}\theta {(1+sin\theta )}^2\text{d}\theta }$
= ${\displaystyle \frac{1}{2}{\int }_0^{\frac{\pi }{2}}\theta (1+2sin\theta +{sin}^2\theta )\text{d}\theta }$
= ${\displaystyle \frac{1}{2}{\int }_0^{\frac{\pi }{2}}\theta (1+2sin\theta +\frac{1-cos2\theta }{2})\text{d}\theta }$
= ${\displaystyle \frac{1}{2}{\int }_0^{\frac{\pi }{2}}\theta (\frac{3}{2}+2sin\theta -\frac{1}{2}cos2\theta )\text{d}\theta }$

= ${\displaystyle \frac{3}{4}{\int }_0^{\frac{\pi }{2}}\theta \text{d}\theta +{\int }_0^{\frac{\pi }{2}}\theta (sin\theta -\frac{1}{4}cos2\theta )\text{d}\theta }$
= ${\displaystyle \frac{3}{4}{\left[\frac{{\theta }^2}{2}\right]}_0^{\frac{\pi }{2}}-{\int }_0^{\frac{\pi }{2}}\theta \frac{\text{d}}{\text{d}\theta }(cos\theta +\frac{1}{8}sin2\theta )\text{d}\theta }$
= ${\displaystyle \frac{3}{8}\cdot \frac{{\pi }^2}{4}-{\left[\theta (cos\theta +\frac{1}{8}sin2\theta )\right]}_0^{\frac{\pi }{2}}+{\int }_0^{\frac{\pi }{2}}cos\theta +\frac{1}{8}sin2\theta \text{d}\theta }$
= ${\displaystyle \frac{3{\pi }^2}{32}-0+{[sin\theta -\frac{1}{16}cos2\theta ]}_0^{\frac{\pi }{2}}}$
= ${\displaystyle \frac{3{\pi }^2}{32}+[(1+\frac{1}{16})-(0-\frac{1}{16})]}$
= ${\displaystyle \frac{3{\pi }^2}{32}+\frac{9}{8}}$

Line Parallel to Two Planes [modified from FM N2005/I/9 part]

The planes  $\Pi_1$ and $\Pi_2$  have vector equation
           $\mathbf{r} = \lambda_1(\mathbf{i + j - k}) + \mu_1 (2\mathbf{i - j + k})$
 and     $\mathbf{r} = \lambda_2(\mathbf{i + }2\mathbf{j + k}) + \mu_2 (3\mathbf{i + j - k})$
respectively.  The line  l  passes through the point with position vector $4\mathbf{i + }5\mathbf{j + }6\mathbf{k}$  and is parallel to both   $\Pi_1$ and $\Pi_2$.  Find a vector equation for  l.

Method 1
First, we find the normal vectors to the planes  $\Pi_1$ and $\Pi_2$ respectively.

Taking cross-products yields the direction parallel to both planes

Hence the required line parallel to both planes is

Method 2
Putting the two equations together

Transferring terms to the left side, one obtains the simultaneous system

Solving by Graphing Calculator, one obtains $\lambda_1 = \frac{5}{3}t$, $\mu_1 = \frac{2}{3}t$, $\lambda_2 = 0$, $\mu_1 = t$.  Upon substitution, we find The line of intersection is given by

Hence the required line parallel to both planes is

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 ${\displaystyle \frac{n}{d}}$ over and over again.
Theorem

Proof:-
For any ${\displaystyle n}$ we have
   ${\displaystyle \left(f\text{*}g\right)\left(n\right) }$
= ${\displaystyle \sum _{n=cd}f\left(c\right)\cdot g\left(d\right)}$
= ${\displaystyle \sum _{n=cd}f\left(d\right)\cdot g\left(c\right)}$  [ as ${\displaystyle d}$ runs through all divisors of  ${\displaystyle n}$, so does ${\displaystyle c=\frac{n}{d}}$ ]
= ${\displaystyle \sum _{n=cd}g\left(c\right)\cdot f\left(d\right)}$
= ${\displaystyle \left(g\text{*}f\right)\left(n\right) }$
(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 ${\displaystyle n}$ we have
   ${\displaystyle \left[f\text{*}\left(g+h\right)\right]\left(n\right) }$
= ${\displaystyle \sum _{d|n}f\left(d\right)\cdot \left(g+h\right)\left(\frac{n}{d}\right)}$
= ${\displaystyle \sum _{d|n}\{f\left(d\right)\cdot g\left(\frac{n}{d}\right)+f\left(d\right)\cdot h\left(\frac{n}{d}\right)\}}$
= ${\displaystyle \sum _{d|n}f\left(d\right)\cdot g\left(\frac{n}{d}\right)+\sum _{d|n}f\left(d\right)\cdot h\left(\frac{n}{d}\right)}$
= ${\displaystyle \left(f\text{*}g\right)\left(n\right)+\left(f\text{*}h\right)\left(n\right) }$
= ${\displaystyle \left(f\text{*}g+f\text{*}h\right)\left(n\right) }$

(proven)

Möbius Inversion Formula

Möbius Inversion Formula (by August Ferdinand Möbius) states that if ${\displaystyle Df}$ the summatory function of f

then

 

where ${\displaystyle f}$ is an arithmetic function.  This is more like a "formula machine", which, when given an input ${\displaystyle f}$, gives you a version of formula as an output (Well, as long as you know what ${\displaystyle Df}$ is).  ${\displaystyle \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 ${\displaystyle 1\left(n\right)}$ function is the Möbius function ${\displaystyle \mu \left(n\right)}$

the formula can be proven succinctly as follows.
Proof:     ${\displaystyle \mu \text{*}Df}$
${\displaystyle = \mu \text{*}\left(1\text{*}f\right)= \left(\mu \text{*}1\right)\text{*}f = {\delta }_1\text{*}f = f }$
(proven)

Example
For ${\displaystyle f\left(n\right)=\phi \left(n\right)}$ the Euler totient function, we know that

Hence applying Möbius Inversion we have

i.e.                                     

since ${\displaystyle \phi \left(n\right)=(\mu \cdot D\phi )\left(n\right) =\sum _{d|n}\mu \left(d\right)\cdot D\phi \left(\frac{n}{d}\right) =\sum _{d|n}\mu \left(d\right)\cdot I\left(\frac{n}{d}\right)=\sum _{d|n}\mu \left(d\right)\cdot \frac{n}{d}}$

Dirchlet Convolution is Associative

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


Theorem

Proof:-
For any ${\displaystyle n}$ we have
   ${\displaystyle \left[\left(f\text{*}g\right)\text{*}h\right]\left(n\right) }$
= ${\displaystyle \sum _{d|n}\left(f\text{*}g\right)\left(d\right) h\left(\frac{n}{d}\right)}$
= ${\displaystyle \sum _{n=dw}\left(f\text{*}g\right)\left(d\right) h\left(w\right)}$
= ${\displaystyle \sum _{n=dw}\{\sum _{d=uv}f\left(u\right) g\left(v\right)\} h\left(w\right)}$
= ${\displaystyle \sum _{n=uvw}f\left(u\right) g\left(v\right) h\left(w\right)}$
= ${\displaystyle \sum _{n=uc}f\left(u\right) \{\sum _{c=vw}g\left(v\right) h\left(w\right)\}}$
= ${\displaystyle \sum _{n=uc}f\left(u\right) \left(g\text{*}h\right)\left(c\right)}$
= ${\displaystyle \left[f\text{*}\left(g\text{*}h\right)\right]\left(n\right) }$
(proven)

Arithmetic Functions

An arithmetic function is a function ${\displaystyle {\mathbb{Z}}^{+}\to S}$ where ${\displaystyle S\subseteq ℝ\subseteq ℂ}$.  They try to capture the essence of various properties of positive whole numbers.

Examples
The constant ${\displaystyle 1}$ function maps every  n  to the number 1.

The identity function ${\displaystyle I}$ maps every  n  to itself.

Möbius function ${\displaystyle \mu }$

The unit function ${\displaystyle {\delta }_1}$ (or ${\displaystyle \epsilon }$ function)

Euler's totient function ${\displaystyle \phi }$

Number of divisors ${\displaystyle \tau }$

Sum of divisors ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle f}$,

The constant 1 function and the function identity ${\displaystyle 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 ${\displaystyle Df}$ of  ${\displaystyle f}$ is

Thus we can think of the ${\displaystyle D...}$ operator as formally the same as ${\displaystyle 1\text{*}...}$  The Inverse of ${\displaystyle 1}$ function under Dirichlet convolution turns out to be the Möbius function ${\displaystyle \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 ${\displaystyle \phi }$, ${\displaystyle 1}$  and  ${\displaystyle 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 ${\displaystyle \to }$ compress/simplify ${\displaystyle \to }$ explore/gather ${\displaystyle \to }$ compress/simplify, ... and so on and on and on.