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