The Möbius function proof, part 2 (the subset parity lemma)

Continuing from my previous post, we are in the middle of proving that $\mu$ satisfies the same equation as $S$ , that is,

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

and that therefore $\mu(n) = S(n)$ for all $n \geq 1$ , that is, $\mu(n)$ is the sum of all the $n$ th primitive roots of unity.

We had gotten as far as the following lemma:

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

In fact, this lemma is the only remaining piece of the proof: if we can prove this then we will have a complete proof that $S(n) = \mu(n)$ . Just for fun, we’re actually going to consider two different proofs of this lemma today.

The first proof

The first proof will be by a combinatorial or counting argument, and was suggested in a comment by Andrey Mokhov. The idea is to match up the subsets in such a way that:

Each subset is matched with exactly one other subset, that is, the matching is 1-1.
Each even subset is matched with an odd subset, and vice versa.

Since the subsets are in pairs and each pair has one even and one odd subset, the inescapable conclusion will be that there are the same number of even and odd subsets. For example, suppose there are a bunch of people in a room and you tell them to get into pairs where each pair has one person with a hat and one person without a hat. If they are able to do this exactly, with no unpaired people left over, then you know (without actually having to count people or hats!) that there must be an equal number of hatted and hatless people.

Call the entire set $T$ . Let’s first consider the case where $T$ has an odd number of elements. How will we match up its subsets? That is, given some subset $U \subseteq T$ , which other subset should $U$ be matched with? A natural idea—which turns out to be the right one in this case—is to match $U$ with its complement $T - U$ , that is, the subset of elements from $T$ which are not in $U$ . Since the complement of $U$ ’s complement is $U$ again (and also because $U$ cannot be its own complement), this does indeed put the subsets of $T$ into pairs. Also, if $|U|$ is even, then $|T - U| = |T| - |U| = \text{odd} - \text{even} = \text{odd}$ (and vice versa if $|U|$ is odd). So each pair has one even and one odd subset.

A picture will probably help. Here’s an example where $|T| = 5$ . As you can check, each row in the picture is a pair of subsets which are each other’s complement, with one even subset and one odd subset:

Now, what about if $|T|$ is even? Matching $U$ with $T - U$ doesn’t work anymore, since they have the same parity—both are even or both are odd. But we can use a cute trick to fix things. Pick some particular element $t \in T$ (note, this is the place in the proof where we depend on the assumption that $T$ is nonempty!)—for example, we might pick the smallest element if they can be ordered, but it really doesn’t matter which one we pick. Previously, when complementing a subset $U$ , we “flipped” the membership of each element of $T$ : if $x$ is element of $U$ , then $x$ is not an element of $T - U$ , and vice versa. Now we do the same, except that we don’t flip $t$ : if $t \in U$ we keep it; if $t \not\in U$ we leave it out. But we still flip all the other elements. Here’s an example when $|T| = 4$ :

Note how we match all the sets that don’t have the smallest (blue) element with each other, and likewise all the sets that do have the smallest element are matched with each other. But within each pair, all the elements other than the smallest one are flipped.

You can convince yourself that this does indeed match up all the subsets into pairs. Moreover, each pair has one even and one odd subset, because the sizes of the paired sets add up to an odd number: $n-1$ if they don’t contain $t$ , or $n + 1$ if they do. QED.

And that’s it for the first proof! We’ve shown that any nonempty finite set has the same number of even and odd subsets, because we can always match them up perfectly.

Binomial coefficient sums

And now for a small tangent. Remember that a set of size $n$ has $\binom{n}{k}$ subsets of size $k$ , where $\binom n k$ is a binomial coefficient, or an entry in Pascal’s Triangle. Since we now know there are the same number of even and odd subsets, if we add $\binom{n}{k}$ when $k$ is even and subtract when $k$ is odd, we must get zero:

$\displaystyle \sum_{0 \leq k \leq n} (-1)^k \binom n k = 0$

That is, the alternating sum of each row of Pascal’s Triangle (besides the zeroth row) is 0:

$\displaystyle \begin{array}{ccccccccccc} &&&1&-&1&&&&=&0 \\ &&1&-&2&+&1&&&=&0 \\ &1&-&3&+&3&-&1&&=&0 \\ 1&-&4&+&6&-&4&+&1&=&0 \end{array}$

and so on. As you can see, this is already really obvious for odd rows, for example, $1-3+3-1$ , since equal numbers cancel out. This is why in some sense the proof was so easy for odd $n$ : we just took the complement of each $U$ . However, for even rows, such as $1-4+6-4+1$ , it is not as obvious: why should we have $1+6+1 = 4+4$ ? So the proof for even $n$ required a bit more cleverness.

In any case, this discussion of binomial coefficiencts brings us to:

The second proof

The second proof was hinted at in a comment by decourse. Recall the Binomial Theorem:

$\displaystyle (x+y)^n = \sum_{0 \leq k \leq n} \binom n k x^{n-k} y^k$

Set $x = 1$ and $y = -1$ . Then the Binomial Theorem says that

$\displaystyle 0 = 0^n = (1-1)^n = \sum_{0 \leq k \leq n} \binom n k (-1)^k.$

And voila! The fact that this sum is zero is the same as saying that there are the same number of even and odd subsets. So we can see that the subset parity lemma is really just a special case of the Binomial Theorem. QED.

Onward

Which proof is better? I like them both. The second proof is really short, and would be your best bet to quickly communicate the idea of the proof to someone who already knows the Binomial Theorem. On the other hand, although it’s longer, the first proof is really cute and feels simpler somehow—it doesn’t depend on the Binomial Theorem and doesn’t even use any actual numbers or equations.

So, where are we? We’ve proved the subset parity lemma. But this means that

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

since we saw that this amounts to looking at subsets of the set of unique prime factors of $n$ , and adding $1$ for even subsets and $-1$ for odd subsets.

This proves that $\mu(n) = S(n)$ (the sum of primitive $n$ th roots of unity) since $S(n)$ satisfies the same equation. But it’s also a useful fact in its own right, will play an important role in our continuing exploration of the Möbius function $\mu$ .

3 Responses to The Möbius function proof, part 2 (the subset parity lemma)

Fergal Daly says:

December 4, 2016 at 5:34 am

You can move between the binomial coefficient proof and the combinatorial proof by applying Pascal’s identity. Take an even row of Pascal’s triangle and replace each element by the two elements above that it’s the sum of (first and last element excepted, they only the sum of 1). Now it’s easy to see that if you sum that row, alternating plus and minus, it’s like a telescoping series

1 – 4 + 6 – 4 +1

becomes

1 – 1 – 3 + 3 + 3 – 3 – 1 + 1
- Brent says:
  
  December 4, 2016 at 4:04 pm
  
  Oh, thanks, that’s a nice way to think about it!
Pingback: Signed sets and ballots and naturality | blog :: Brent -> [String]

Comments are closed.