Arithmetic Functions-Mobius Functions, Dirichlet Product

Number theory, like many other branches of mathematics, is often concerned with sequences of real or complex numbers. In number theory such sequences are called arithmetical functions.

Definition A real- or complex-valued function defined on the positive integers is called an arithmetical function or a number-theoretic function.

In many cases $f(n)$ is an integer , describing some number-theoretic property of $n$. Examples include

$\phi(n)=|U(n)|$- The number of units mod $n$.

$\tau(n)=\sum_{d|n} 1 $- The number of divisors of $n$.

$\sigma(n)=\sum_{d|n} d $- Sum of divisors of $n$.

For example consider $n=12$

$\phi(12)=4\quad U_{12}=\{1,5,7,11\}$

$\tau(12)=6 \quad \{1,2,3,4,6,12\}$

$\sigma(12)=28$

The functions $\tau$ and $\sigma$ are called divisor functions.

Note:If $n$ is prime , then it has exactly two positive factors, 1 and $n$.So $\sigma(n)=n+1$.On the other hand if $\sigma(n)=n+1$, then $n$ must be prime.

Definition: An arithmetic function is called multiplicative if

$$f(mn)=f(m)f(n)$$ whenever $gcd(m,n)=1$

$f$ multipluicative $n_1,n_2,\ldots,n_k$ are mutually coprime ,then

$$f(n_1,n_2,\ldots,n_k)=f(n_1).f(n_2).\ldots.f(n_k)$$

if $n$ has a prime power factorization $p_1^{e1},\ldots,p_k^{ek}$, then

$$f(n)=f(p_1^{e1}),\ldots,f(p_k^{ek})$$

Note:$\phi(n), \tau(n),\sigma(n)$ are all multiplicative.If $g$ is a multiplicative function then $f(n)=\sum_{d|n}g(d)$ is also multiplicative.

Consider the functions $u(n)=1$ and $N(n)=n$ are both multiplicative.

The divisor functions $\tau(n)=\sum_{d|n}1=\sum_{d|n} u(d)$ and $\sigma(n)=\sum_{d|n}d=\sum_{d|n}N(d)$.Since $u$ and $N$ are multiplicative so are $\tau$ and $\sigma$

Lets evaluate the divisor function at prime powers $p^e$.Since the divisors of $p^e$ are $1,p,p^2,\ldots,p^e$, we have

$$\tau(p^e)=e+1 \quad \text{and} \quad  \sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1}$$

We know that $\tau$ and $\sigma$ are multiplicative.So we can immediately deduce the following theorem

Theorem:

If $n$ has prime-power  factorization $n=p_1^{e_1}\cdots p_k^{e_k}$, then

$$\tau(n)=\prod_{i=1}^k (e_i+1)\quad \text{and} \quad  \sigma(n)=\prod_{i=1}^k \frac{p^{e+1}-1}{p-1}$$

Example:

compute $\tau(36)$ and $\sigma(36)$

Note: The positive divisors of 36 are $\{1,2,3,4,6,9,12,18,36\}$

$\tau(36)=\tau(9).\tau(4)=\tau(3^2).\tau(2^2)=(2+1).(2+1)=9$

$\sigma(36)=\sigma(9).\sigma(4)=(3^3-1)/(3-1).(2^3-1)/(2-1)=13.7=91$

Compute $\tau(6120)$ and $\sigma(6120)$

$6120=2^3.3^2.5.17$

$\tau(6120)=(3+1).(2+1).(1+1).(1+1)=48$

$\sigma(6120)=\frac{2^4-1}{2-1}.\frac{3^3-1}{3-1}.\frac{5^2-1}{5-1}.\frac{17^2-1}{17-1}$

$\sigma(6120)=15.13.6.18=21060$

Perfect Numbers

A positive integer $n$ is perfect if $n$ is the sum of its proper divisors ( the positive divisors $d \ne n$).Since $\sigma(n)$ is the sum of all positive divisors of $n$,this condition can be written as $n=\sigma(n)-n$, or equivalently

$$\sigma(n)=2n$$

The term perfect numbers was coined by the Pythagoreans.The perfect numbers were believed by the Ancient Greeks to have particular aesthetic and religious significance. The first two examples are

$6=1+2+3$ and $28=1+2+4+7+14$

and the next is 496.

Theorem

1.If $n$ is $2^{p-1}(2^p-1)$, where $p$ and $2^p-1$ are both primes.($2^p-1$ is the Mersenne Prime $M_p$), then $n$ is perfect.

2.If $n$ is even and perfect , then $n$ has the form given in (1)

Proof:

if $n=2^{p-1}(2^p-1)$ So $\sigma(n)=\sigma(2^{p-1})\sigma(2^p-1)$

$\sigma(2^{p-1})=(2^p-1)/(2-1)=2^p-1$

$\sigma(2^p-1)=(2^p-1)+1=2^p$

Thus $\sigma(n)=(2^p-1)(2^p)=2n$, so $n$ is perfect.

This theorem shows that there is one-to-one correspondence between even perfect numbers and Mersenne primes $M_p$.For example the perfect numbers 6,28,496 corresponds to the Mersenne primes $M_2=3,M_3=7$ and $M_5=31$

$6=2(2^2-1)$ and $28=2^2(2^3-1)$

Note:No example of odd perfect number is known.

Mobius Function and Mobius Inversion Formulae

Mobius Function

The Möbius function, denoted as $\mu(n)$, is a multiplicative arithmetic function used in number theory. It is defined on the positive integers and takes on the values -1, 0, or 1 depending on the factorization of the input number $n$. The Möbius function is defined as follows:

• If $n$ has any squared prime factors, then$\mu(n)=0$.
• If $n$ is a product of an even number of distinct prime factors, then $\mu(n)=1$.
• If $n$ is a product of an odd number of distinct prime factors, then $\mu(n)=−1$.

In other words $\mu$ assigns -1,0,1 to each positive integer.

Here are some examples:

$μ(1)=1$ because 1 has no prime factors.
$μ(2)=−1$ because 2 is a prime number.
$μ(4)=0$ because 4 has a squared prime factor (2).

$μ(6)=1$ because 6 has two distinct prime factors (2 and 3), and the number of prime factors is even.

$μ(35)=1$ because $35=7.5$ ,two distinct even prime factors.

The Möbius function is useful in various number theoretic applications, including number theory proofs, the study of arithmetic functions, and in algorithms related to number theory such as the Möbius inversion formula.

The mobius function $\mu$ is defined mathematically as follows

$\mu(1)=1$ if $n>1$, write $n=p_1^{e_1},\cdots p_k^{e_k}$. Then

$\mu(n)=(-1)^k$ if $e_1=e_2=\cdots=e_k=1$

$\mu(n)=0$ otherwise

Note that $\mu(n)=0$ if and only if $n$ has a square factor >1

Example:

$15=3.5$.So $\mu(15)=(-1)^2=-1$

$30=2.3.5$.So $\mu(30)=(-1)^3=-1$

$60=2^2.3.5$.So $\mu(60)=0$

Recursive Definition

Lets define an Identity Function $I$ given by ( This function is multiplicative)

$\begin{equation}
I(n)=
\begin{cases}
1 & \text{if } n=1\\
0 & \text{if } n >1
\end{cases}
\end{equation}$

A useful alternate formula for $I$ is

$$I(n)=\left \lfloor \frac{1}{n} \right \rfloor$$, the integer part of $1/n$.

Mobius Function $\mu$ is defined by the formula$\begin{equation}\sum_{d|n} \mu(d) =I(n)=
\begin{cases}
1 & \text{if } n=1\\
0 & \text{if } n >1
\end{cases}
\end{equation}$

If $n=1$ with a unique divisor $d=1$ then $\mu(1)=1$, and if $n>1$ then $\sum_{d|n} \mu(d)=0$, so

$$\mu(n)=-\sum_{d|n,d<n}\mu(d)$$

which defines $\mu(n)$ in terms of the values of $\mu$ at smaller integers $d$.If $n$ is prime, then its only divisors are $d=1$ and $d=n$, so $\mu(n)=-\mu(1)=-1$ ;ie; for primes $\mu(p)=-1$

The following are the values of $\mu(n)$ for $n=1,\ldots , 12$

$\mu(n)=1,-1,-1,0,-1,1,-1,0,0,1,-1,0$

Theorem:

The mobius function $\mu$ is multiplicative

To prove that the Möbius function $μ(n)$ is multiplicative, we need to show that for any two coprime positive integers $a$ and $b$, we have:

$μ(ab)=μ(a)⋅μ(b)$

Case 1: $a=1$ or $b=1$

If either $a$ or $b$ is equal to 1, then $ab=1$, and $μ(ab)=μ(1)=1$ since 1 has no prime factors. $μ(a)=μ(1)=1$ and $μ(b)=μ(1)=1$. So $\mu(ab)=\mu(a) .\mu(b)$

Case 2:$gcd(a,b)=1$

Since $a$ and $b$ are coprime they have distinct prime factors and the product is having $k+1$ prime factors, where $k$ and $l$ are the number of prime factors of $a$ and $b$ respectively.

So $\mu(ab)=(-1)^{k+1}=(-1)^k.(-1)^l=\mu(a).\mu(b)$

Note that when $gcd(a,b) \ne 1$, the theorem $\mu(ab)=\mu(a).\mu(b)$ does not apply.

Example:$\mu(2)=-1$ and $\mu(6)=1$ But $\mu(12)=0$ which is not equal to $\mu(2).\mu(6)$

Example:

Let $m=15$ and $n=28$

$\mu(15)=1$ and $\mu(28)=0$

$\mu(420)=0$

Thus $\mu(mn)=\mu(m).\mu(n)$

$\mu(420)=\mu(15 .28)=\mu(15).\mu(28)$

Now we develop a formula for $\sum_{d|n} \mu(d)$. When $n=1,\sum_{d|1} \mu(d)=\mu(1)=1$.

When $n$ is prime power $p^e$. the following lemma holds.

lemma:Let $F(n)=\sum_{d|n} \mu(d)$.Then $F(p^e)=0$,, where $e>1$

proof:

$F(p^e)=\sum_{d|p^e} \mu(d)$

$\quad =\sum_{i=0}^e \mu(p^i)$

$\quad =\mu(1)+\mu(p)+\mu(p^2)+\cdots+\mu(p^e)$

$\quad=1+-1+0+\cdots+0=0$

Example:$n=81$

$81=3^4$

$\sum_{d|3^4} \mu(d)=\mu(1)+\mu(3)+\mu(3^2)+\mu(3^3)+\mu(3^4)=1+(-1)=0$

Theorem: let $n$ be a positive integer .Then

$\sum_{d|n} \mu(d)=1$ if $n=1$ and 0 otherwise

Example:$n=15$

The divisors are $1,3,5,15$ So

$\sum_{d|n}\mu(n)= \mu(1)+\mu(3)+\mu(5)+\mu(15)$

$\quad =1+(-1)+(-1)+1=0$

Mobius Inversion Formula

We have seen several instances where pairs of arithmetic functions $f$ and $g$ are related by the identity $f(n)=\sum_{d|n} g(d)$.It is often useful  to be able to invert the roles of $f$ and $g$, that is, to find a similar formula expressing $g$ in terms of $f$.

• This formula relates two arithmetic functions (f(n) and g(n)) defined through sums over divisors.
• It allows you to express one function in terms of the other under certain conditions.
• The Möbius function (μ(n)) plays a crucial role in "balancing" the sum based on the primality of divisors.

Theorem:

Let  $f$ and $g$ be arithmetic functions.If

$$f(n)=\sum_{d|n} g(d)$$

for all $n$, then 

$$g(n)=\sum_{d|n} f(d)\mu(n/d)=\sum_{d|n}\mu(d) f(n/d)$$

for all $n$

this shows that if $f$ is expressed in terms of $g$ as a sum over divisors, then one can invert their roles and define $g$ in terms of $f$ by similar expression.The relationship between $f$ and $g$ is nearly symmetric, except that the function $\mu$ appears in the expression for $g$.

Corollary:

Let $\tau(n)=\sum_{d|n}1$ and $\sigma(n)=\sum_{d|n} d$

Then

$$1=\sum_{d|n}\mu(d)\tau(n/d)=\sum_{d|n}\mu(n/d)\tau(d)$$

and

$$n=\sum_{d|n}\mu(d)\sigma(n/d)=\sum_{d|n}\mu(n/d)\sigma(d)$$

Example: Let $n=15,\tau(15)=4,\sigma(15)=24$ .The factors are $\{1,3,5,15\}$

we will prove this $1=\sum_{d|n}\mu(d)\tau(n/d)=\sum_{d|n}\mu(n/d)\tau(d)$

$\sum_{d|n} \mu(d)\tau(n/d)$

$\mu(1).\tau(15)+\mu(3).\tau(5)+\mu(5).\tau(3)+\mu(15).\tau(1)$

$1.4+(-1).2+(-1).2+1.1=1$

Now consider $n=\sum_{d|n}\mu(d)\sigma(n/d)=\sum_{d|n}\mu(n/d)\sigma(d)$

$\sum_{d|n} \mu(n/d)\sigma(d)$

$\mu(15).\sigma(1)+\mu(5).\sigma(3)+\mu(3).\sigma(5)+\mu(1).\sigma(15)$

$1.1+(-1).4+(-1).6+1.24$

$25-10=15=n$

Corollary

Let $n=\sum_{d|n} \phi(d)$

if $n \ge 1$ then 

$$\phi(n)=\sum_{d|n}d \mu(n/d)=\sum_{d|n}\mu(d)(n/d)$$

Example:

$12=2^2.3$

$\phi(12)=12(1-1/2)(1-1/3)=12/1-12/2-12/3+12/6=\sum_{d|12}\mu(d)12/d$

Let $n=12$,so $\phi(12)=4$.The divisors of 12 are 1,2,3,4,6 and 12.We can find that

$$\sum_{d|12} d. \mu(12/d)=1.0+2.1+3.0+4.-1+6.-1+12.1=4$$

and also 

$$\sum_{d|12} \mu(d) .12/d=1.12+-1.6+-1.4+0.3+1.2+0.1=4$$

Dirichlet Product

The Dirichlet product is an operation that combines two arithmetic functions to form a new arithmetic function. It is named after the German mathematician Johann Peter Gustav Lejeune Dirichlet, who introduced it in his study of number theory.

Definition:If $f$ and $g$ are arithmetic functions, then their Dirichlet product, or convolution is arithmetic function $f * g$ given by

$$(f*g)(n)=\sum_{d|n} f(d)g(\frac{n}{d})$$

Remark:Since $d$ divides $n$ if and only if $n/d$ divides $n$ so 

$$(f*g)(n)=\sum_{d|n} f(\frac{n}{d})g(d)$$

or equivalently by putting $e=n/d$

$(f*g)(n)=\sum_{de=n} f(d)g(e)$

where $\sum_{de=n}$ denotes summation over all pairs $d,e$ such that $de=n$.

Example:

$(f*g)(10)=f(10)g(1)+f(2)g(2)+f(5)g(5)+f(1)g(10)$ or

$(f*g)(10)=f(1)g(10)+f(2)g(5)+f(5)g(2)+f(10)g(1)$

Example:

$\sum_{d|n} \phi(d)=n$ fo all $n$; using the functions $u(n)=1$ and $N(n)=n$, we can rewrite this as

$$\sum_{d|n} \phi(d)u(n/d)=N(n)=n$$

for all $n$, which becomes in our new notation $\phi * u=N$.Similarly our definition of $\mu$ can be written as $\mu * u=I$ .The corollary $\phi(n)=\sum_{d|n}d \mu(n/d)$ can be written as $\phi=N*\mu=\mu * N$.If $g$ is multiplicative,then so is the function $f=g * u$.Mobius inversion formula states that if $f=g*u$  then $g=f* \mu=\mu * f$ 

$n=7$

$\phi(1)u(7)+phi(7)u(1)=1.1+6.1=7$

Properties

For all the arithmetic functions $f$,$g$ and $h$ we have

$(a)\quad f*g=g*f$

$(b)\quad (f*g)*h=f*(g*h)$

$(c)\quad f*(g+h)=f*g+f*h$

$(d)\quad f*I=I*f=f$

Thus * is commutative and associative , and has $I$ as an Identity.

Applications:

The Dirichlet product finds applications in various areas of number theory, including:

• Divisor functions: Dirichlet products are commonly used to define and study divisor functions such as the sum of divisors function $σ_k​(n)$.
• Möbius inversion: The Möbius inversion formula, which relates the Möbius function $μ(n)$ to other arithmetic functions, involves Dirichlet products.
• Prime number theory: Dirichlet products are used in various proofs and theorems related to prime numbers, including Dirichlet's theorem on primes in arithmetic progressions.

Overall, the Dirichlet product is a fundamental operation in number theory that allows for the combination and manipulation of arithmetic functions to explore the properties of positive integers.