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?
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.
Thanks! Yup, I agree. Also, in the context of actual class presentation, doing a bunch of examples for small
. I filled up a lot of paper rewriting the sums for
and
in different ways before I saw what was going on.
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.
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.
Perhaps amplifying on Russ’ remarks, the relation
can be encoded as a(n infinite) triangular matrix
(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
only depends on the ratio
; but this isn’t needed for the present argument.
@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
be the coefficients such that
is equivalent to
. So we get
. This gives
. Switching summation
. It seems to me that, for the necklace argument, I want to know that the inner sum is the same as
. So I want
, which is the surprising fact.
Or did I do this wrong/miss a trick?
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.
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.
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
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
by a certain more general system of inequalities in an analogous way that “a group of order p” is replaced by ” a solution to
.”)
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.