A counting argument for Frobenius’ theorem

Let G be a finite group, and let n be a positive integer dividing |G|. Then the number of solutions to g^n=1 in G is divisible by n.

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 G acts on a finite set X, then \sum_{g \in G} \# \{ x \in X : gx = x \} = |G| \times |X/G|. Actually, we only need the following corollary:

Corollary of Burnside’s theorem If a finite group G acts on a finite set X, then \sum_{g \in G} \# \{ x \in X : gx = x \} \equiv 0 \bmod |G|.

Notation Fix a finite group G and a positive integer n dividing |G|. For any d dividing |G|, let N_d denote the number of d-torsion elements in G, and let M_d denote the number of elements of order precisely d. So

\displaystyle{N_d = \sum_{e|d} M_e \ \mbox{and}\ M_d = \sum_{e|d} \mu(d/e) N_e} \qquad (1)

Let G act on the set of n element subsets of G. We will apply the Corollary to this action. So, we each g \in G, we must determine how many n element sets are taken to themselves under multiplication by g.

A set X is fixed by g if and only if X is a union of cosets for \langle g \rangle. If the order of g does not divide n, this is impossible. If the order of g is d, a divisor of n, then there are |G|/d cosets of \langle g \rangle, and we must choose n/d of them to make up a set of size n. So there are \binom{|G|/d}{n/d} sets fixed by g, if d is the order of g. We obtain

\displaystyle{ \sum_{d|n} \binom{|G|/d}{n/d} M_d \equiv 0 \bmod |G|}. \qquad (2)

Our desired result is that \sum_{d|n} M_d \equiv 0 \bmod n. If all of the binomial coefficients were equal to |G|/n, we’d be done. Our strategy is to show that the binomial coefficients act enough like |G|/n that we win.

Let’s start with a special case. Suppose that n = p is a prime. Equation (\ast) says \tfrac{|G|}{p} M_p + \binom{|G|}{p} M_1 \equiv 0 \bmod |G|. We have \binom{|G|}{p} \equiv \tfrac{|G|}{p} \bmod |G| (exercise!). We deduce that \tfrac{|G|}{p} M_p+ \tfrac{|G|}{p} M_1 \equiv 0 \bmod |G|, so M_p + M_1 \equiv 0 \bmod p as desired. The argument that follows is just this argument for a more general n.

Substituting the Mobius inversion formula from (1) into (2), we get

\displaystyle{ \sum_{d|n} \binom{|G|/d}{n/d} \sum_{e|d} \mu(d/e) N_e \equiv 0 \bmod |G|}.

Interchanging summation and putting f = d/e, we get

\displaystyle{ \sum_{e|n} N_e \left(\sum_{f|n/e} \mu(f) \binom{|G|/(ef)}{n/(ef)} \right) \equiv 0 \bmod |G|}. \qquad (3)

We now need a lemma to evaluate the inner sum.
Lemma: Let a|b. Then \sum_{f|a} \mu(f) \binom{b/f}{a/f} \equiv 0 \bmod b.

Proof: We give a combinatorial interpretation. Consider necklaces with b beads, of which a are black and the rest are white. Then \binom{b/f}{a/f} is the number of necklaces which are taken to themselves under a rotation of period f. So the Mobius sum is the number of such necklaces with no nontrivial periodicity. Rotating such a necklace will produce b distinct necklaces, so the number of such aperiodic necklaces is divisible by b. \square (Here are some similar examples.)

We remark that, if we had \frac{b/f}{a/f} = \tfrac{b}{a} in place of \binom{b/f}{a/f}, the sum would be zero and the result obvious. So this Lemma is an example of our strategy of showing that binomial coefficients are p-adically close to fractions.

Putting a=n/e and b = |G|/e, the inner sum of (3) is divisible by |G|/e. Also, inductively, for every e<n, we know that e | N_e. So every summand in (3) except for possibly the e=n term is divisible by e \cdot |G|/e = |G|. We deduce that the e=n term is also divisible by |G|.

In other words, N_n \binom{|G|/n}{1} \equiv 0 \bmod |G|. So N_n \equiv 0 \bmod n. QED

The reason I am unsatisfied is that we started with direct counting to get to (2). 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 b) in order to win. Let \mathcal{N}(b,a) denote the number of aperiodic necklaces on b beads, a of which are black. I feel like, if I were really clever, I could give a counting argument to jump directly to the equation \sum_{e|n} N_e \ \mathcal{N}(|G|/e, n/e) \equiv 0 \bmod |G|. 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?

9 thoughts on “A counting argument for Frobenius’ theorem”

  1. This is the first time I see a nice proof for this theorem! (Typo: “we each”.)

    I would somewhat disarm its difficulty by factoring it into a group-theoretical part and a combinatorial part. The group-theoretical part is the way to (2). The combinatorial part is the statement that if $n$ and $g$ are two positive integers with $n | g$, and if $\left(M_e\right)_{e | n}$ is a family of integers such that every $e | n$ satisfies $\sum_{d | e} \binom{g/d}{e/d} M_d \equiv 0 \mod g$, then $\sum_{e | n} M_e \equiv 0 \mod n$. Your proof (using necklaces) is the best one I see for this latter part.

  2. Thanks! Yup, I agree. Also, in the context of actual class presentation, doing a bunch of examples for small n. I filled up a lot of paper rewriting the sums for n=4 and n=6 in different ways before I saw what was going on.

  3. This isn’t a solution to the mathematical problem, but possibly a solution to the pedagogical problem: restrict to the case where n is square-free. Then Möbius inversion becomes normal inclusion-exclusion, which is a much more reasonable thing to assume.

    Probably you could also first show it for prime-powers, then stitch these together using inclusion-exclusion. (At that point however, you have something equivalent to, though possibly even more complicated than, Möbius inversion.)

    I can definitely see why inclusion-exclusion might come up. If you’re counting the solutions to g^6 = 1, then g^2 = 1 and g^3 = 1 seem very likely to come up as subproblems.

  4. Of course, if you do it with Mobius inversion, then your students will get the benefit of seeing Mobius inversion, which as you say they might not otherwise do.

  5. Perhaps amplifying on Russ’ remarks, the relation d|n can be encoded as a(n infinite) triangular matrix I + LocallyNilpotent (division refines natural order), so that even not knowing finer features like multiplicativity, it’s straight-forward that something like Möbius inversion exists over the integers; what’s most surprising about inversion is that the coefficient at (a,b) only depends on the ratio a:b; but this isn’t needed for the present argument.

  6. @jessemckeown I was thinking the another night about whether or not I need the “surprising” fact, and I thought I did. Let’s work it out!

    Let \mu(n,d) be the coefficients such that N_n = \sum_{d|n} M_d is equivalent to M_n = \sum_{d|n} \mu(n,d) N_d. So we get \sum_{d|n} M_d \binom{G/d}{n/d} \equiv 0 \bmod G. This gives
    \sum_{d|n} \binom{G/d}{n/d} \sum_{e|d} \mu(d,e) N_e \equiv \bmod n. Switching summation \sum_{e|n} N_e \sum_{f|n/e} \mu(fe,e) \binom{(G/e)/f}{(n/e)/f}. It seems to me that, for the necklace argument, I want to know that the inner sum is the same as \sum_{f|n/e} \mu(n/e,(n/e)/f) \binom{(G/e)/f}{(n/e)/f}. So I want \mu(fe,e) = \mu(n/e, (n/e)/f), which is the surprising fact.

    Or did I do this wrong/miss a trick?

  7. The use of the Moebius function can be eliminated; the two uses formally cancel. In terms of convolution on the divisor semigroup, you have A=a*1, B=b*1 and argued b*A=B*μ*A=B*a. But you could simply argue b*A=b*1*a=B*a. In other words, expand A() in terms of a(), regroup, and combine b() into B(). The only reason you didn’t is that you only came to a() at the very end, when it was forced on you as μ*A. But once you know about it, it’s easy to start over and exploit it.

    Specifically, b(d)=M_d, B(d)=N_d,
    a(d)=aperiodic(|G|/(n/d), d)
    A(d)=|G|/(n/d) choose d

    Then Burnside’s lemma gives you the congruence on (b*A)(n), but this is equal to (B*a)(n), which is what you want.

    Pedagogically, I don’t recommend this amount of abstraction. As I said above, this is just expanding the binomial coefficient in terms of the aperiodic terms, regrouping, and combining M into N. And that’s how I first found it (actually, going the other direction). But I wrote it out in the formalism to convince myself that it really is that simple, that I haven’t made any convenient errors. Also, I was worried about comments #5-6, but the convolution formalism takes care of that coincidence, so they aren’t relevant.

    PS – necklaces are a somewhat natural fit with cyclic group actions. Just interlace all the orbits. It’s probably a sign of a more direct argument.

  8. Hmm… Seemingly I overstretched, but Ben seems to… well, I don’t know.

    Anyways, The Unrelated odd thing is: this theorem is called Frobenius, presumably because Frobenius wrote something about it, but what I most think of when I hear “Frobenius” are A) the finite field automorphisms and B) character theory. So I’m wondering if either or both tools together don’t produce something helpful.

  9. I had an early dream of a theorem that unifies Sylvester theorem and part of Sylow’s theorems asserting that the number of subgroup of order p^k is 1 modulo p. (As David remarked in the post this was also proved by Frobenius) https://gilkalai.wordpress.com/2008/08/20/two-very-early-problems-a-simple-solution-and-a-new-problem/

    The connection I was hoping for is a more general theorem which replace “a group of order p^k by a certain more general system of inequalities in an analogous way that “a group of order p” is replaced by ” a solution to x^n=1.”)

    Actually Frobenious theorem can be seen as a statement about a combinatorial relation between the number of subgroups of order r where r divides n. And I hoped for a more gineral relation on the number of certain subgroups which extend this part of Sylow’s theorem.

Comments are closed.