# Posts Tagged ‘Mobius function’

## On the Möbius function

April 11, 2015 by Sabyasachi Mukherjee. 7 comments

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)}$$.