The Möbius function proof, part 1

In my last post, I introduced the Möbius function \mu(n), which is defined in terms of the prime factorization of n:

  • \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.

Previously, we also considered the sum S(n) of all the primitive nth roots of unity. Today, we will begin proving they are the same: S(n) = \mu(n) for all n \geq 1! This is surprising since it is not immediately obvious what the two functions have to do with each other: one is about sums of complex numbers, and the other is about prime factorization. On the other hand, perhaps it is not all that surprising after all: we’ve already seen that primitive roots of unity have a lot to do with divisibility and prime factorization. In any case, this connection is the key that cracks open a lot of really cool mathematics.

So, how will we do it? Recall that we proved S(n) satisfies this equation:

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

In the case of S(n) this was fairly “obvious”: we proved it essentially by staring at some pictures. But we will show that \mu(n) also satisfies this equation, that is,

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

(In contrast to S(n), this is not so obvious! But it’s true, and we will prove it.) Given a starting value for n = 1, we have seen that this equation uniquely determines all values of a function for n > 1: for example, given S(1), we can use the equation to uniquely determine S(2); given S(1) and S(2), we can then uniquely determine S(3); and so on. So, if S(n) and \mu(n) both satisfy this equation, they must be the same for all n as long as they have the same starting value—and they do, since S(1) = \mu(1) = 1.

I have to say that this is one of my favorite proofs—it rests on a beautiful little combinatorial argument, and, as we’ll see, it gives some insight into the Principle of Inclusion-Exclusion as well. We’ll start the proof today and then see the really beautiful part in my next post. So, without further ado:

Theorem. \displaystyle \sum_{d \mid n} \mu(d) = \begin{cases}1 \qquad n=1 \\ 0 \qquad n>1.\end{cases}

Corollary. \mu(n) = S(n) for all n \geq 1.

Proof. Since \mu(1) = 1, we can already see that \sum_{d \mid 1} \mu(d) = \mu(1) = 1 as desired. So now consider \sum_{d \mid n} \mu(d) for some n > 1; we wish to show this sum is zero.

Since \mu(d) = 0 for values of d which are divisble by a perfect square, those values of d contribute nothing to the sum. We can therefore concentrate on only those d which are not divisible by a perfect square (we call such numbers squarefree). Each squarefree d must be a product of distinct prime factors, since if any prime factor was repeated, then d would be divisible by a perfect square. Since d \mid n, the prime factorization of each squarefree d is therefore a subset of the set of distinct prime factors of n, and conversely, each subset of the distinct prime factors of n yields a distinct squarefree divisor d.

For example, consider n = 360 = 2^3 \cdot 3^2 \cdot 5. Each squarefree divisor of n can have at most one copy of each of 2, 3, and 5. There are therefore 2^3 = 8 squarefree divisors of n, one corresponding to each subset of \{2, 3, 5\}:

\displaystyle \begin{array}{rcr} d & \text{factorization} & \mu(d) \\ 1 & & 1 \\ 2 & 2 & -1 \\ 3 & 3 & -1 \\ 5 & 5 & -1 \\ 6 & 2 \cdot 3 & 1 \\ 10 & 2 \cdot 5 & 1 \\ 15 & 3 \cdot 5 & 1 \\ 30 & 2 \cdot 3 \cdot 5 & -1 \end{array}

Adding up all the values of \mu(d) listed in the right column, we can see that there are four 1’s and four -1’s, which cancel to yield 0 as claimed.

As another example, for n = 21 = 3 \cdot 7, all of the divisors of n are squarefree: we have

\displaystyle \mu(1) + \mu(3) + \mu(7) + \mu(3 \cdot 7) = 1 - 1 - 1 + 1 = 0.

Our goal is to show that this sum is always zero, and the only way for it to be zero is if there are always an equal number of 1’s and -1’s. Given the definition of \mu, we know that the 1’s come from even-sized subsets of the distinct prime factors of n, and the -1’s come from odd-sized subsets. So in other words, we need to show that there are the same number of even-sized subsets as there are odd-sized subsets.

The fact that these are sets of distinct prime factors really makes no difference, since we are just counting them. What we really need, in essence, is the following lemma:

Subset parity lemma: any nonempty finite set has an equal number of even-sized and odd-sized subsets.

Can you see how to prove this? (And as an aside, do you see why it is false if we exclude the word “nonempty”? Do you see what this has to do with the n=1 versus n > 1 cases?) My next post will explain a nice proof of the lemma and then conclude the proof that \mu(n) = S(n)!

Advertisements

About Brent

Assistant 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.

9 Responses to The Möbius function proof, part 1

  1. decourse says:

    I do believe I see how to prove that. Hint: (1-1)^n

    • Brent says:

      Good! An extra challenge for you: can you prove it *without* using the Binomial Theorem?

      • decourse says:

        I couldn’t do it in the 10 minutes I had available to think about it! Having said that, I do like Andrey’s proof (and presumably yours) below.

  2. Andrey Mokhov says:

    Here is my proof:

    1. If n is odd then there is a simple bijection between even-sized e and odd-sized o subsets, achieved via set complement: e S\o.

    2. If n > 0 is even then subsets that do not contain element n have the same bijection as in (1) above, while subsets that do contain n have a slightly different bijection: e S\o U {n}.

    • Brent says:

      Nice, this is essentially the proof I had in mind, though I think your description for even sets not containing n may be slightly off: we don’t want to just take their set complement, but rather take the set complement and then remove n. Or did you have something different in mind?

  3. Pingback: The Möbius function proof, part 2 (the subset parity lemma) | The Math Less Traveled

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

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

Comments are closed.