The Möbius function

Time to pull back the curtain a bit! My recent series of posts on complex roots of unity may seem somewhat random and unmotivated so far, but the fact is that I definitely have a destination in mind—we are slowly and inexorably heading towards some really deep and beautiful mathematics. It has just taken a while to build up all the requisite concepts!

Last time, we defined $S(n)$ as the sum of all the primitive $n$ th roots of unity. We noted that

$\displaystyle \sum_{d \mid n} S(d) = \begin{cases}1 \qquad n=1 \\ 0 \qquad n>1\end{cases}$

and used this to deduce values of $S(n)$ . In principle we could carry this as far as we want to compute $S(n)$ for any $n$ , but this doesn’t necessarily give us any insight into the nature of $S$ . For example, is $S(n)$ always either $-1$ , $0$ , or $1$ ? Is there a nicer way to characterize $S(n)$ , and/or a quicker way to compute it?

It turns out that $S(n)$ is more than just an idle curiosity. In fact, it is famous enough that it has a name: it is known as the Möbius function, and it is usually written $\mu(n)$ . There are indeed nicer ways to characterize and compute $\mu(n)$ . Here’s how it is most commonly defined:

$\mu(n) = 0$ if $n$ has any repeated prime factors, that is, if $n$ is divisible by a perfect square.
Otherwise, if $n$ has $k$ distinct prime factors, $\mu(n) = (-1)^k$ . In other words, $\mu(n) = 1$ if $n$ has an even number of distinct prime factors, and $-1$ if the number of prime factors is odd.

For example:

$\mu(8) = 0$ since $8$ is divisible by a perfect square (namely, $4$ ).
$\mu(5) = -1$ since $5$ has an odd number of prime factors (namely, one).
$\mu(10) = 1$ since $10$ has two distinct prime factors.
$\mu(30) = -1$ since $30$ has three distinct prime factors.
$\mu(1) = 1$ since $1$ has zero prime factors, and zero is even.

So far, this seems to match up with what we had already deduced about $S(n)$ , but it is not at all obvious whether $S(n)$ and $\mu(n)$ are the same. Why should adding up a particular set of complex numbers have anything to do with the number of prime factors of $n$ ? In my next post, we’ll prove that they are in fact the same. The proof is a nice exercise in combinatorics and relates to Pascal’s Triangle. (Michael Paul Goldenberg hinted at such a proof in a comment on my previous post.)

As you might guess, $\mu$ is deeply related to prime numbers and the Riemann zeta function. It turns out it is also related to the Principle of Inclusion-Exclusion. All this and more to come!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →