Möbius Function

The Möbius function $μ(n)$ is a multiplicative function which is important in the study of Dirichlet convolution. It is an important multiplicative function in number theory and combinatorics. While the values of the function itself are not difficult to calculate, the function is the Dirichlet inverse of the unit function ${\bf 1}(n)=1$. This fact, called Möbius inversion, gives rise to formulas involving $\mu$ for many sums and identities involving arithmetic functions.

For any positive integer $n,$ define $μ(n)$ as the sum of the primitive $n^\text{th}$ roots of unity.

It has values in $\{-1, 0, 1\}$ depending on the factorization of $n$ into prime factors:

a) $\mu(n) = 1$ if $n$ is a square-free positive integer with an even number of prime factors.
b) $\mu(n) = -1$ if $n$ is a square-free positive integer with an odd number of prime factors.
c) $\mu(n) = 0$ if $n$ has a squared prime factor.

$\mu(n) = \begin{cases} 1 & \text{ if } n=1, \\ 0 & \text{ if } a^2 \mid n \text{ for some } a > 1 \text{ (i.e., } n \text{ has a squared prime factor)}, \\ (-1)^k & \text { if } n \text{ is the product of } k \text{ distinct primes.} \end{cases}$

In particular, $\mu(p) = -1$ for all primes $p$.

From the above definition, it is straightforward to check that $\mu(n)$ is a multiplicative function.

Many arithmetic functions can be expressed as sums of other functions over the positive divisors of their argument: $f(n) = \sum_{d|n} g(d)$. In this situation, it is possible to solve for $g(n)$ in terms of values of $f$; the general solution turns out to be furnished by the Möbius function.

The following lemma explains why the Möbius function is so fundamental:

$$\sum_{d|n}\mu(d) = \begin{cases} 1 & \text{ if } n=1, \\ 0 & \text{ if } n>1. \end{cases}$$

When $n > 1,$ let $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}$ ($\alpha_i \ge 1 \text{ for all }i =1,\ldots,r).$ If $d|n$, $d = p_1^{\beta_1} p_2^{\beta_2} \cdots p_r^{\beta_r}$ with $0 \leq \beta_i \leq \alpha_i$ for $i = 1,\ldots, r.$ If $\beta_i \ge 2$ for some $i = 1, \ldots , r,$ then $\mu(d) = 0$. Therefore,

$$\begin{aligned}\large \sum_{d|n} \mu(d) &= \sum_{\overset{(\beta_1, \ldots , \beta_r)}{\beta_i = 0 \text{ or } 1}} \mu\left(p_1^{\beta_1} \cdots p_r^{\beta_r}\right) \\ &=1 - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^{r} \binom {r}{r} \\ &= (1 - 1)^{r} \\ &= 0. \end{aligned}$$

The next-to-last equality follows from the binomial theorem. $\big($The binomial coefficients $\binom{r}{k}$ in the above equation count the factors which are products of $k$ distinct primes, which have a $\mu$ value of $(-1)^k. \big)$

When $n = 1,$

$$\sum_{d|n} \mu(d) = \mu(1) = 1. \ _\square$$

Writing $e(n)$ as the function on the right side of the equality in the lemma, and defining $\mathbf{1}(n) = 1$, the lemma can be written more compactly in the language of Dirichlet convolution:

$$\mu * \mathbf{1} = e.$$

So if $f$ and $g$ are arithmetic functions such that $f(n) = \sum_{d|n} g(d)$, or $f = g * \mathbf{1}$, then

$$f * \mu = (g * \mathbf{1}) * \mu = g * (\mathbf{1} * \mu) = g * e = g.$$

This is referred to as Möbius inversion.

Let $f$ and $g$ be arithmetic functions such that $f(n) = \sum_{d|n} g(d)$ for all $n$. Then

$$g(n) = \sum_{d|n} \mu(d) f\left(\frac{n}{d}\right) = \sum_{d|n} \mu\left(\frac{n}{d}\right) f(d).$$

Here is an explicit proof that does not use the language of Dirichlet convolution; the work done in this proof is essentially a special case of the proof that Dirichlet convolution is associative. Consider

$$\begin{aligned} \sum_{d|n} f(n/d) \mu(d) &= \sum_{d|n} \sum_{r|n/d} g(r) \mu(d) \\ &= \sum_{\overset{r,d}{rd|n}} g(r) \mu(d) \\ &= \sum_{r|n} \left( \sum_{d|n/r} \mu(d) \right) g(r), \end{aligned}$$

but the sum in parentheses is $0$ if $r \ne n$ and $1$ if $r = n$, by the lemma, so this equals $g(n)$. $_\square$

There is also a multiplicative version of Möbius inversion, proved exactly the same way:

Let $f$ and $g$ be arithmetic functions such that $f(n) = \prod_{d|n} g(d)$. Then

$$g(n) = \prod_{d|n} f(n/d)^{\mu(d)} = \prod_{d|n} f(d)^{\mu(n/d)}.$$

1. Let $\phi(n)$ be Euler's totient function. It is a standard fact that $\sum_{d|n} \phi(d) = n$. Möbius inversion immediately gives $$\phi(n) = \sum_{d|n} \mu(d) \frac nd \implies \frac{\phi(n)}{n} =\sum_{d|n} \frac{\mu(d)}{d}.$$

2. Let $f(n)$ be the sum of the primitive $n^\text{th}$ roots of unity. Then $f(1) = 1$. Now suppose $n \ge 2$ and let $\zeta_n = \text{exp}\left(\frac{2\pi i}n\right).$ Since the powers of $\zeta_n$ are all the primitive $d^\text{th}$ roots of unity, where $d$ runs over the positive divisors of $n$, \[ \begin{align} \sum_{d|n} f(d) &= 1+\zeta_n+\zeta_n^2+\cdots+\zeta_n^{n-1} \\
   &= \frac{\zeta_n^n-1}{\zeta_n-1} = 0,
   \end{align} \] so $\sum_{d|n} f(d) = e(n)$. Note that $f$ and $\mu$ have the same summation, so Möbius inversion implies that they are equal to each other: $$f(n) = \sum_{d|n} \mu\left(\frac nd\right) e(d) = \mu(n).$$ So the Möbius function is the sum of the primitive $n^\text{th}$ roots of unity.

3. Let $\Phi_n(x)$ be the $n^\text{th}$ cyclotomic polynomial, the polynomial whose roots are equal to the primitive $n^\text{th}$ roots of unity. Then $$x^n-1 = \prod_{d|n} \Phi_d(x),$$ and now multiplicative Möbius inversion gives $$\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}.$$ For example, $$\Phi_{48}(x) = \frac{(x^{48}-1)(x^8-1)}{(x^{24}-1)(x^{16}-1)} = \frac{x^{24}+1}{x^8+1} = x^{16}-x^8+1.$$

A common strategy to prove facts about multiplicative functions is to first restrict attention to their values on prime powers. That is, if two multiplicative functions agree on prime powers, they must agree everywhere. The proofs of the first two identities below use this idea.

1. It is a fact that $$\sum_{d|n} \frac{\mu^2(d)}{\phi(d)} = \frac{n}{\phi(n)}.$$ To see this, note that both sides are multiplicative, so we can restrict our attention to $n = p^k$ for some prime $p$. In this case, the left side is $1 + \frac1{p-1}$ and the right side is $\frac{p}{p-1}$, so they are equal.

2. Let $\omega(n)$ denote the number of distinct prime factors of $n$. Then $$\sum_{d|n} \mu(d)^2 = 2^{\omega(n)}.$$ To see this, note that $2^{\omega(n)}$ is multiplicative $\big($since $\omega(ab) = \omega(a)+\omega(b)$ if gcd$(a,b)=1\big),$ so both sides are multiplicative. For $n = p^k$, the left side is $1+1$ and the right side is $2$, so they are equal.

3. Let $s$ be a complex number with Re$(s) > 1$. Then $$\sum_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \frac1{\zeta(s)},$$ where $\zeta$ is the Riemann zeta function. This is an example of a Dirichlet series.

4. The average value of the Möbius function is $0 .$ That is, let $a(x) = \frac1{x} \sum_{1 \le n \le x} \mu(n),$ then $$\lim_{x\to\infty} a(x) = 0.$$ This statement turns out to be equivalent to the famous prime number theorem, which gives an asymptotic estimate of the number of primes less than $x$. The point here is that answers to simple questions about the Möbius function are related to quite deep facts about prime numbers.