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 nth 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.
This entry was posted in Uncategorized and tagged , , , , , , , , . Bookmark the permalink.

5 Responses to The Möbius function

  1. Thanks for the mention, Brent. This is really interesting. Tomorrow will be a good opportunity to explore this. ;^)

  2. Pingback: The Möbius function proof, part 1 | The Math Less Traveled

  3. Pingback: Dirichlet convolution and the Möbius function | The Math Less Traveled

  4. Pingback: Möbius inversion | The Math Less Traveled

  5. Pingback: More fun with Dirichlet convolution | The Math Less Traveled

Comments are closed.