Classifying Groups
The 14th group theory lecture
Last time, we discussed Lagrange’s theorem, the orbit-stabilizer theorem, and their myriad consequences.
As part of these corollaries, we successfully classified all groups with no more than 8 elements, up to isomorphism. (If you read carefully, you’ll see that they are ℤ/2ℤ, ℤ/3ℤ, ℤ/4ℤ, ℤ/2ℤ×ℤ/2ℤ, ℤ/5ℤ, ℤ/6ℤ, D6, and ℤ/7ℤ.) They are almost all abelian, and there are either 1 or 2 groups of any particular size.
This falls apart for groups of 8 elements, of which there are five: ℤ/8ℤ, ℤ/4ℤ×ℤ/2ℤ, (ℤ/2ℤ)3, D8, and Q8. As the order of the group increases (or, more accurately, as the number of prime powers that it is divisible by increases), the number of possible group structures grows rapidly. Although, an accurate asymptotic was only proved in 1993—the number of isomorphism classes of groups of order n is roughly
This was proved by László Pyber, and he needed the classification of finite simple groups to do it—we’ll talk about what that is in a later post.
The idea of classifying all finite groups is alluring. If we could sort all finite groups into some simple categories, then we could use that as a proof technique: try to prove that a given property is true of all groups by showing that it is true for each of these nice types in the classification. (Many theorems are proved like this. To give a simple example, the classification of isometries in Euclidean geometry can help determine if an isometry with given properties exists.)
Unfortunately, we really don’t even have the beginnings of a classification. I doubt that we will have anything like it in my lifetime, and it is not impossible that humanity will never produce such a thing ever.
But we can try to get classifications of groups of some particular type. Today, we’re going to look at probably the simplest case: we will classify all finite abelian groups.
Observe that all of the abelian groups we have seen are just products of cyclic groups. This is true, but we can be more specific.
Theorem: Let N>1 be an integer, and N=p1k1p2k2…pnkn be its prime factorization. Then
Proof: In the last problem set, I had you prove that if m, n are positive, coprime integers, then
The theorem follows from this by induction on the number of distinct prime factors. □
Thus, we shouldn’t be looking to show that abelian groups are products of cyclic groups—we should be showing that they are products of cyclic groups whose order is a prime power.
The proof comes in two stages: first, we will prove that any finite group can be decomposed as a product of groups whose elements all have orders that are powers of some particular prime p; second, we will prove that any finite group with this special property must be a product of cyclic groups.
Let’s begin with a definition to sum up what we just said.
Definition: Let p be a prime. A p-group is a group G such that the order of every element in G is a power of p.
Lemma: Any finite group G is a p-group if and only if |G|=pk for some integer k>0.
Proof: By Cauchy’s theorem (which we proved last time), if |G| is divisible by a prime q, then there exists an element in G of order q. Therefore, |G|=pk if G is a p-group. On the other hand, if |G|=pk, then by Lagrange’s theorem the order of every element in G divides it, so it must also be a power of p. □
Lemma: Let G be a finite abelian group. For every prime p that divides |G|, define
Then Gp is a subgroup, and moreover
is a group isomorphism, where p1,…pn are the primes that divide |G|.
Proof: Suppose that g,h are in Gp, of orders pm and pn, where m≥n. Then
so the order of gh must divide pm—in particular, gh is in Gp. Similarly, the order of g-1 is always the same as the order of g, so if one is in Gp, so is the other. Thus, Gp is a subgroup of G.
It is easy to see that ϕ is a group homomorphism, as a consequence of G being abelian. Is it injective? Well, suppose that |G|=p1k1p2k2…pnkn. Let N=|G|/prkr—that is, the same prime factorization, but with one prime factor dropped. Now, suppose that ϕ(g1,…,gn)=g1…gn=1. Then it follows that
The last line follows from the fact that for every i other than r, the order of gi divides N. On the other hand, pr does not divide N, so the only way that grN=1 is if gr=1. This is true for each of the prime factors, so ϕ is indeed injective.
Is ϕ surjective? Choose any g in G. The subgroup generated by g is cyclic, so we already know that it breaks apart as a product of cyclic groups whose orders are all prime powers. In other words, g is a product of elements of order pk, which is just to say that g is a product of elements in the p-subgroups. □
Thus, we see that we only need to consider finite, abelian p-groups. The idea of the next step is to find a way to flake off as large a cyclic subgroup as we can, and then apply induction.
Lemma: Let G be a finite abelian p-group. Let g be an element of the largest order in G. Then there exists a subgroup H such that
is a group isomorphism.
Proof: We use induction on the number of elements in G. The base case is |G|=p, in which case G is cyclic and so we can just take H={1}.
In the induction step, observe that if G is cyclic, then we can again just take H={1}, so the only interesting case is where the order of g is less than |G|—thus, there exists some element h of G that isn’t in the cyclic subgroup generated by g. Choose such an element whose order is as small as possible—we claim that its order must be p.
Suppose not. Then hp is a non-identity element whose order is less than h. By the definition of h, it must be that hp=gk for some k. It must be that k=pr for some r—if not, hp would generate ⟨g⟩, which contradicts the definition of h.
So, we can consider h’=g-rh. Observe that (h’)p=g-khp=1. Since h’ isn’t in the cyclic subgroup generated by g (that would imply that h is), we see we have produced the desired element with order p.
Great: now, consider G’=G/⟨h⟩. Certainly, it is a finite abelian group and smaller than G, so we can apply our inductive hypothesis to it to get a subgroup H’. On the last problem set, I had a set of exercises that proved that any subgroup of a quotient group G/K must be of the form H/K for some subgroup H of G that contains K. Thus, in particular, H’ is the image of some subgroup H of G that contains h.
The only question is whether H has the properties that we want. The claim is that it must, because of how we chose h: specifically, the image of g in G’ is still the element of the largest order, because its order is unchanged!
Why? Observe that (g⟨h⟩)n=⟨h⟩ if and only if gn is ⟨h⟩, so the order of g in G’ is reduced if and only if ⟨g⟩ and ⟨h⟩ share some element other than 1. But the order of h is p, so all non-identity elements in ⟨h⟩ are generators. So such an intersection is forbidden by the fact that h is not in ⟨g⟩.
So, we choose g⟨h⟩ as the element of the largest order in G’ and get H/⟨h⟩ accordingly—that is, we have an isomorphism
We claim that
is also an isomorphism. That it is a homomorphism is obvious. Is it surjective? Yes: we know that every element in G is of the form gnkhm for some k in H. But since h is in H, khm is too.
Is it injective? If gnk=1, we know that gn and k must belong to ⟨h⟩ (from the injectivity of the earlier map). But this can only occur if g=1 by what we have already discussed, which in turn proves that k=1. We are done. □
Theorem: Every finite abelian group can be written (up to isomorphism) as a product
where the pi are (not necessarily distinct!) primes. Moreover, up to reordering the terms, this decomposition is unique.
Proof: We already proved that we can decompose the group into p-groups Gp. For existence, it remains to show that each p-group is a product of cyclic groups. This is accomplished with the aid of our lemma: start with Gp and choose an element with the largest possible order. Then we may write Gp≅ℤ/pk1ℤ×Gp,1. Now, repeat this analysis with Gp replaced by Gp,1, which has fewer elements. This process cannot go on forever: G has only finitely many elements in it, and the size of the remaining group shrinks on each iteration. Eventually, we get our desired decomposition.
I leave proving uniqueness to the reader—exercises to that effect are part of the next (and last!) problem set, below. □
The classification of finite abelian groups has many consequences. For example: in any finite abelian group, the order of any element divides the largest order. Why? Well, what is the largest order of an element in
Let q1, q2,…, qm be the distinct primes that show up, and let k1, k2,… km be the largest powers that show up for each such prime. I claim that the maximal order will be
Indeed, raising any element of any cyclic group that makes up the product to this exponent will get you back to the identity. Is there an element that has this order? Yes, (1, 1, 1,…, 1) does!
Will the order of any other element have to divide this? Yes, because we just explained that raising any element to this exponent will kill it!
This fact alone is quite useful. Here’s one of my favorite applications: you can use it to prove that the unit group of any finite field is cyclic.
Let’s define the terms here. A field, for those who haven’t seen it before, is an algebraic structure 𝔽 with two operations +, ⋅ with corresponding identities 0, 1 such that
(𝔽,+,0) is an abelian group,
(𝔽-{0},⋅,1) is an abelian group, and
⋅ distributes over + (i.e. x⋅(y+z)=x⋅y+x⋅z).
The rationals, the reals, and the complex numbers are all examples of infinite fields. There are also finite ones, like 𝔽p:=ℤ/pℤ (where multiplication is also modulo p), where p is a prime. That this example is a field follows from the work we did when we developed the Diffie-Hellman key exchange.
The unit group of a field is simply all of the non-zero elements—by assumption, this is an abelian group. Therefore, the unit group of a finite field must be a finite, abelian group, from which we know that we can apply our classification theorem!
Let k be the largest order of an element in the unit group, and consider the polynomial P=Xk-1. Polynomials over fields behave much like complex polynomials: a polynomial cannot have more roots than its degree. I will eventually give a full proof of this once I post my number theory notes, but we gave the vague idea of the proof when we covered Shamir secret sharing.
Therefore, P cannot have more than k roots—or, to put it another way, there cannot be more than k elements with order dividing k. But we know that all of the elements in the unit group have order dividing k! Therefore, k cannot be any smaller than the number of elements in the unit group. And so 𝔽 is cyclic.
This isn’t just a neat piece of mathematical trivia—the fact that the multiplicative group modulo p is cyclic is very important in cryptography, and it is actually a potent tool for building some efficient prime-generating algorithms.
But, again, that will have to wait until I post the number theory notes.
Upgrade to a paid subscription to see additional content. (E.g., extra examples, problem sets, etc.)
I’m confused how we concluded the unit group is cyclic. We showed there can’t be more than k elements with order dividing k and we know every element of the unit group divides k so we should get the inequality |F^x|<=k.
I also don’t understand how stating k=p-1 would imply that F^x is cyclic. This seems to be assuming that |F|=p, but in general a finite field can have size p^n and we would then have k=p^n-1. But I don’t understand the equality anyway and I don’t understand why that equality would say anything about F^x being cyclic?