Posts Tagged ‘Mobius function’

The Möbius function is a rather useful one, especially when dealing with multiplicative functions. But first of all, a few definitions are in order.

Definition 1: Let $\omega(n)$ be the number of distinct prime divisors of $n$.

Definition 2: The Möbius function, $\mu(n)$ is defined as $(-1)^{\omega(n)}$ if $n$ is square-free and $0$ otherwise. (A number $n$ is square-free if there is no prime $p$ such that $p^2$ divides $n$.)

It may be a good idea to compute the following: $\omega(n)$ and $\mu(n)$ for $n=64, 12, 17, 1$ to get an idea of what’s going on.

A Möbius function is an arithmetic function, i.e. a function from $\mathbb{N}$ to $\mathbb{C}$. Can you think of some other arithmetic functions?

Definition 3:  If $f(n)$ is an arithmetic function not identically zero such that $f(m)f(n)=f(mn)$ for every pair of positive integers $m, n$ satisfying $(m,n)=1$, then $f(n)$ is multiplicative.

Theorem 0: $\mu(n)$ is a multiplicative function.

Proof: The proof is left to the reader.

Theorem 1: If $f(n)$ is a multiplicative function, so is $\displaystyle \sum_{d|n} f(d)$.

Before we jump to the proof, let us be clear on the notation. For $n=12$, $\displaystyle \sum_{d|n} f(d)=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)$ i.e. the sum taken over the divisors of $n$.

Proof: Consider the sets $A= \{d :  0<d, d|n \}$ and $B= \{d_1d_2 : d_1|m_1, d_2|m_2, (m_1,m_2)=1,m_1m_2=n\}$.

(Note that such $m_1, m_2$ exist. Take $m_1=1,m_2=n$).

Now take $d \in A$. Then $1\cdot d$ divides $1\cdot n$ which means that $d \in B$ and so $A \subset B$.

Now take $s \in B$. So $s$ is of the form $d_1d_2$ where $d_1|m_1$ and $d_2 |m_2$ such that $(m_1,m_2)=1$ with their product $n$. So, $s$ divides $m$ and hence $B \subset A$. From these, we infer that $A=B$.

Now, suppose that $(m,n)=1$. Then $\displaystyle F(mn)=\sum_{d|mn} f(d)=\sum_{d_1|m,d_2|n,d_1d_2=mn}f(d_1d_2)=\sum_{d_1|m}\sum_{d_2|n} f(d_1d_2)$

So, $$F(mn)=\sum_{d_1|m}\sum_{d_2|n}f(d_1)f(d_2)(\text{since f is multiplicative})=\sum_{d_1|m}f(d_1)\sum_{d_2|n}f(d_2).$$

Now with this theorem in hand, let us a prove a few more theorems.

 Theorem 2: $\displaystyle \sum_{d|n} \mu(d)$ is $0$ if $n>1$ and $1$ if $n=1$.

Proof: The case $n=1$ is trivial.

Suppose that $n>1$.

Since $\mu(n)$ is multiplicative, so is $\displaystyle F(n)= \sum_{d|n} \mu(d)$. Now let us recall that $n>1$ can be written as a product of primes, say $\displaystyle n=p_i^{a_i}\dots p_k^{a_k}$. So, we can write $F(n)=F(p_1^{a^1})\dots F(p_k^{a_k})$.

As $a_i\ge 1$, $F(p_i^{a_i})= 0$ (using the definition of $\mu$.)That means $F(n)=0$. The desired conclusion now follows from this discussion.

Before we now move on to a theorem which shows a connection between the Euler’s $\varphi-$function and the Möbius function, let us state a really important theorem, also known as the Möbius Inversion formula.

Theorem 3: If $\displaystyle F(n)=\sum_{d|n}f(d)$ for every positive integer $n$, then $\displaystyle  f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$.

Proof:  We will flesh this proof in somewhat lesser detail because we have developed most of the techniques related to his proof.

Note that $\displaystyle \sum_{d|n}\mu(d)F(\frac{n}{d})$

$\displaystyle =\sum_{d|n}\mu(d)\sum_{k|(n/d)} f(k)= \sum_{dk|n}\mu(d)f(k)=\sum_{dk|n}\mu(k)f(d)$.

Can the reader now complete the proof? (Hint: Use Theorem 2).

Theorem 4: $\displaystyle \varphi(n)= n\sum_{d|n} \frac{\mu(d)}{d}.$

Proof:  To write the proof, we use a lemma.

Lemma: $\displaystyle \sum_{d|n} \varphi(d)=n$.

Proof of the lemma: Note that for $n=1$, this is true. Suppose that $n>1$. Then $\displaystyle n=p_1^{a_1}\dots p_k^{a_k}$ for some primes $p_1,\dots, p_k$. As $\varphi(n)$ is multiplicative, so is $\displaystyle  F(n)= \sum_{d|n} \varphi(d)$

That means $\displaystyle F(n)=\prod_{i=1}^k F(p_i^{a_i})$. A quick calculation reveals that $F(p_i^{a_i})=p_i^{a_i}$ which gives $F(n)=n$.

We can now use this lemma and  the Möbius Inversion formula to finish off the proof.

Here as some other problems on multiplicative functions.

Problem 1:  $\displaystyle \frac{1}{\varphi(n)}=\frac{1}{n}\sum_{d|n}\frac{\mu(d)^2}{\varphi(d)}$.

Problem 2:  For each positive integer $n$, $\displaystyle \mu(n)\mu(n+1)\mu(n+2)\mu(n+3) = 0$.

Problem 3: $\displaystyle \sum_{d|n}|\mu(d)| = 2^{\omega(n)}$.