How to Count (with Symmetry)
The 13th group theory lecture
In our last lecture, we proved the ping-pong lemma and showed how it can be used to compute presentations of various groups.
At least for now, this wraps up what I want to do with regard to the geometric side of group actions. But we went through all of this trouble defining quotient groups as part of our quest to describe groups in some sense. And we showed that they could be used to convert homomorphisms into isomorphisms (a very useful process sometimes!). But is that all that they are good for?
No—the uses of quotient groups are legion. Today, we’ll look at some counting problems. For this, it will be useful to understand the size of the quotient group and what that tells us.
Definition: Let H be a subgroup of G. The index [G:H] of H in G is the number of elements in the set of cosets G/H.1
Observe that if H is a normal subgroup, the index is simply the number of elements in the quotient group G/H.
Theorem: Let K be a subgroup of H, which is a subgroup of G. Then [G:K]=[G:H][H:K].
Proof: Let R be a minimal set of elements in H such that every coset in H/K is of the form rK for some r in R. Clearly, the number of elements in R is precisely [H:K].
Now, take any coset aH in G/H. Since we know that H decomposes as a disjoint union of sets rK, where r ranges through the elements of R, it immediately follows that aH decomposes as a disjoint union of sets arK. These are cosets in G/K, and we have demonstrated that G splits into [G:H][H:K] of them (since there are [H:K] elements r and [G:H] distinct cosets aH). □
This result is already good, but I am more interested in its myriad corollaries. For instance, write |G| to denote the order of the group G—that is, its number of elements.
Corollary: (Lagrange’s Theorem) Let H be a subgroup of G. Then |G|=[G:H]|H|.
Remark: Lagrange died in 1813, a couple of decades before the term “group” was even coined—thus, he certainly didn’t prove this theorem in the form that we have stated it. In a bit, we will state and then prove what he actually showed.
Proof: Take K={1} and observe that [G:{1}]=|G| for any group. □
Corollary: Let H be a normal subgroup of G. Then |G|=|G/H||H|.
Proof: This is just a special case of the above corollary. □
Corollary: Let g be an element of a group G. The order of g divides the order of G.
Proof: In Lagrange’s theorem, take H=⟨g⟩. □
Corollary: Let p be a prime. Up to isomorphism, there is exactly one group with p elements (ℤ/pℤ).
Proof: By the above corollary, for any element g of a group with p elements, its order is either 1 or p. Only the identity has order 1, so every other element has order p. Each of them is a generator of the group, so it is cyclic of order p. □
Corollary: Up to isomorphism, there are exactly two groups with 4 elements (ℤ/4ℤ and ℤ/2ℤ×ℤ/2ℤ).
Proof: Similarly to the previous corollary, every non-identity element of the group must have order either 2 or 4. If there is even one with order 4, this is the cyclic group of order 4. Otherwise, every non-identity element has order 2. Choose any such element g and any h such that h is not in the subgroup generated by g.
Their product gh cannot be 1, g, or h, so it must be the remaining element of the group. The same is true of hg. Therefore, gh=hg, from which we see that
is an isomorphism. □
These are all nice group-theoretic results. But Lagrange’s theorem can be applied to many areas outside of pure algebra.
Corollary: (Euler’s Theorem) Let N be a positive integer, and let ϕ(N) be the number of integers 0≤a<N that are coprime to N. For any integer a coprime with N, aϕ(N)=1 mod N.
Proof: In our discussion about the Diffie-Hellman key exchange, we proved that (ℤ/Nℤ)×, the collection of elements in ℤ/Nℤ that are coprime with N, is a group under multiplication. Observe that ϕ(N) is exactly the number of elements in this group.
On the other hand, if a is coprime with N, then it is an element in (ℤ/Nℤ)×, so by Lagrange’s theorem, its order divides ϕ(N). □
Corollary: (Fermat’s Little Theorem) Let p be a prime. For any integer a, ap=a mod p.
Proof: If a is divisible by p, this is obvious. If a is not divisible by p, this is just Euler’s theorem. □
Of course, both of these results were known long before group theory existed as a discipline.2 Fermat seldom wrote down any proofs, but Leibniz had an unpublished manuscript (written some time before 1683) in which he proved Fermat’s little theorem; Euler gave the first proof of Euler’s theorem in 1763.3 The power of the group-theoretic approach is its versatility.
Toward that end, we would really like to connect Lagrange’s theorem with group actions—this will immediately broaden its applicability. We can accomplish that using the orbit-stabilizer theorem. We already know what an orbit is—what is a stabilizer?
Definition: Let G act on X. For any x in X, the stabilizer subgroup StabG(x) of G is the subgroup of elements g such that g.x=x.
Theorem (Orbit-Stabilizer Theorem): Let G act on X. For any x in X, the map
is a well-defined bijection.
Proof: First of all, why is this well-defined? Choose any g,h in the same coset—we need to prove that g.x=h.x. But this is the same as proving that h-1g.x=x, which is the exact same thing as saying that h-1g is in StabG(x), which is the same as saying that g and h are in the same coset.
The map is obviously surjective. Is it injective? Yes, precisely by the argument that we just gave: if g.x=h.x, then g and h are in the same coset. □
Why is this useful in the context of Lagrange’s theorem? Well, suppose that G is finite. Then the number of elements in the orbit G.x is the same as the number of elements in G/StabG(x), which Lagrange’s theorem tells us is the same thing as |G|/|StabG(x)|. So, we may conclude that the size of an orbit always divides the size of the group, and we even have a handy way to determine the factor!
For example, let’s now state and prove what Lagrange actually proved.
Theorem: Let P be a polynomial in n variables. The number of polynomials that can be obtained by shuffling the variables of P divides n!.
Proof: Observe that Sn acts on the space of all polynomials in X1, X2,… Xn, as follows: given a polynomial P(X1,X2,…,Xn), we can send it to P(Xσ(1),Xσ(2),…,Xσ(n)), which σ is in Sn—that is, we reorder the variables.
Thus, the size of the orbit Sn.P must divide |Sn|=n!. □
Let’s see this with a concrete example. Take the polynomial P=x2-xy-xz. We can exchange x, y, and z to produce three different polynomials: x2-xy-xz, y2-xy-yz, and z2-xz-yz. This divides 3!=6.
We could have seen that it had to be three specifically by working out the stabilizer of P. If you look at it, you can see that exchanging y and z does not change the polynomial—the stabilizer has order 2, so there must be 6/2=3 distinct polynomials.
A second example: take P=xy2+yz2+zx2. If we shift x↦y↦z↦x, then it will be the same polynomial. Thus, the stabilizer has at least three elements (since this one transformation generates a subgroup of order 3). Thus, there are at most 6/3=2 distinct polynomials, and indeed there are exactly two: xy2+yz2+zx2 and zy2+yx2+xz2.
We can also apply the orbit-stabilizer theorem directly to group theory.
Theorem: (Cauchy’s Theorem) Let G be a finite group, and p a prime such that p divides |G|. Then there exists an element g in G of order p.
Proof: Consider the set X of tuples (g0, g1,… gp-1) of elements in G such that g0g1…gp-1=1. The cyclic group of order p acts on X as follows: n.(g0, g1,… gp-1)=(gn, gn+1,… gn+p-1)—in other words, we just cyclically permute the elements in the tuple.
We want to prove that there exists a non-identity element g such that (g, g,… g) is an element of X—that would mean that gp=1, and since g is not the identity, that has to mean that its order is exactly p (since p is prime). We’ll do this by a counting argument.
Note that, by the orbit-stabilizer theorem, any orbit of the above action has to have either 1 or p elements in it. It has precisely one element if and only if that element is of the form (g, g,… g) for some g in G. We know that there is at least one such orbit: take g=1.
Now, observe that there are |G|p-1 elements in X. Why? Because we can freely choose g0, g1,… gp-2—it’s just that then our choice of gp-1 is completely determined. Since |G| is divisible by p, that proved that the number of elements in X is divisible by p.
However, by what we said above, the number of elements in X is mp+n, where m is the number of orbits with p elements in it, and n is the number of orbits with 1 element in it. This is divisible by p if and only if n is, and we know that n>0, so in fact there are at least p orbits with a single element. □
Corollary: For any prime p>2, there are exactly two groups with 2p elements, up to isomorphism (ℤ/2pℤ and D2p, the isometry group of the regular p-gon).
Proof: This will be included as an exercise on the next problem set. □
Upgrade to a paid subscription to see additional content. (E.g., extra examples, problem sets, etc.)
Although in general, G/H is not the same as H/G, there is always a bijection between them. I invite the reader to think about how to construct it!
On the other hand, they are still very relevant: both of these results are crucial components of various cryptographic protocols, for example.
While it feels strange to have to specify that X mathematician proved X’s theorem, the sheer number of historical counterexamples makes this necessary.
Euler’s Theorem has 1<a<N in the definition of \varphi(N). It should be 1\leq a \leq N. The first inequality allows 1, which is necessary, the second has no effect (unless N=1 when it is also necessary).