Let be a finite group, and let be a positive integer dividing . Then the number of solutions to in is divisible by .
This is a 1907 theorem of Frobenius. Along with the Sylow theorems, it is one of the few nontrivial elementary results about a completely general finite group. And it has some nice applications, which you can read about on Mathoverflow. But it has never made it into the standard basic group theory syllabus the way the Sylow theorems have. I wanted to give it as a challenging problem last time I taught group theory, but I didn’t find a proof that I liked enough.
The last few days, I’ve been thinking about the problem again, and I found what I think is a decent counting proof. I have the feeling there is a really slick proof in here waiting to get out. Let me know if you can find it!
As with almost all counting proofs in group theory, we’ll be using Burnside’s Lemma (due to Cauchy): If a finite group acts on a finite set , then . Actually, we only need the following corollary:
Corollary of Burnside’s theorem If a finite group acts on a finite set , then .
Notation Fix a finite group and a positive integer dividing . For any dividing , let denote the number of -torsion elements in , and let denote the number of elements of order precisely . So
Let act on the set of element subsets of . We will apply the Corollary to this action. So, we each , we must determine how many element sets are taken to themselves under multiplication by .
A set is fixed by if and only if is a union of cosets for . If the order of does not divide , this is impossible. If the order of is , a divisor of , then there are cosets of , and we must choose of them to make up a set of size . So there are sets fixed by , if is the order of . We obtain
Our desired result is that . If all of the binomial coefficients were equal to , we’d be done. Our strategy is to show that the binomial coefficients act enough like that we win.
Let’s start with a special case. Suppose that is a prime. Equation says . We have (exercise!). We deduce that , so as desired. The argument that follows is just this argument for a more general .
Substituting the Mobius inversion formula from into , we get
Interchanging summation and putting , we get
We now need a lemma to evaluate the inner sum.
Lemma: Let . Then .
Proof: We give a combinatorial interpretation. Consider necklaces with beads, of which are black and the rest are white. Then is the number of necklaces which are taken to themselves under a rotation of period . So the Mobius sum is the number of such necklaces with no nontrivial periodicity. Rotating such a necklace will produce distinct necklaces, so the number of such aperiodic necklaces is divisible by . (Here are some similar examples.)
We remark that, if we had in place of , the sum would be zero and the result obvious. So this Lemma is an example of our strategy of showing that binomial coefficients are -adically close to fractions.
Putting and , the inner sum of is divisible by . Also, inductively, for every , we know that . So every summand in except for possibly the term is divisible by . We deduce that the term is also divisible by .
In other words, . So . QED
The reason I am unsatisfied is that we started with direct counting to get to . We then messed around with a bit of Mobius inversion (which, sadly, is not considered standard material) and get to another sum which we evaluated combinatorially (modulo ) in order to win. Let denote the number of aperiodic necklaces on beads, of which are black. I feel like, if I were really clever, I could give a counting argument to jump directly to the equation . Then I’d never have to mention Mobius inversion. At that point I’d be completely happy giving this proof in class, or as a exercise with a series of hints.
Can you be that clever?