On the Möbius function

April 11, 2015 by . 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)}\).


Subscribe to comments with RSS.

  • Anon Till says:

    This article looks hasty and poorly written. There is no motivation to a majority of the text and no exposition is given. There are some places where words are misspelled, letters are missing, or mathematics is off. It reads more like it has been copied from a textbook than actually written for a blog.

  • For Theorem 0, it might be useful to briefly define what a multiplicative function is. Especially since there are two different definitions, and the number-theoretical definition meant here is not quite obvious from the name.

    (Of course, if you’ve taken a few courses on number theory, you’ll likely know the definition already. But in that case, you’re probably already familiar with the Möbius function, too. In fact, at least for me, I’m pretty sure I first learned the definition of a multiplicative function in the context of learning about the Möbius function.)

  • Yes, you might want to define multiplicative function.

  • vzn says:

    in regard to the negative comments, nobody has actually pointed out any errors. those who dont like the blog can write their own or go **** themselves.

    • mixedmath says:

      Although I might not use the same terminology as vzn, I’m also surprised at the response. Some prefer terse exposition, some prefer wordy exposition.

      Seems like a reasonable post to me!

    • Anon Till says:

      There were errors and they were pointed out but they were removed by someone once the post was edited (a process which I find rather rude). “Go ****” yourself.