# x^5 – x – 1

One of the strange and wonderful facts of mathematics is the general unsolvability of quintic polynomials. If you haven’t heard about this, prepare to have your mind pleasantly blown. Most people memorize the quadratic equation, the general expression for the roots of any quadratic polynomial, in high school:

And even though very few people learn it in school, it turns out that we know a general solution to any cubic polynomial as well. It’s a little cumbersome to write, but just like the quadratic equation, it expresses the zeroes of any cubic polynomial as a function of its coefficients.

ax3 + bx2 + cx + d = 0
x = (some big complicated function of a, b, c, and d)

And in fact we have a general solution for any quartic polynomial as well, even more cumbersome.

ax4 + bx3 + cx2 + dx + e = 0
x = (some even bigger and more complicated function of a, b, c, d, and e)

Mathematicians struggled for a long time to find a general solution for the roots of quintic polynomials (ax5 + bx4 + cx3 + dx2 + ex + f = 0). Eventually, some mathematicians began to suspect that no such general solution existed. And then in the first few decades of the 1800s, a few mathematicians put out proofs to that effect. The most complete of these proofs was provided by Évariste Galois before he died in a duel at the age of 20 (we really need a big Hollywood movie about Galois’ life).

I recently found a fantastic 15-minute video sketching the proof of the unsolvability of the quintic. The approach taken in this proof is different from any of the original proofs, and it’s much simpler in a bunch of ways.

Here’s the video:

And briefly, here’s a summary of the proof:

1. The roots of any quintic polynomial obviously depend on the coefficients of the polynomial.
2. If you imagine taking a particular quintic polynomial (ax5 + bx4 + cx3 + dx2 + ex + f), and making small continuous changes in the coefficients (a, b, c, d, e, f), then the set of zeroes of this polynomial should make similar continuous changes.
3. If you move each coefficient in a loop in the complex plane, ending at the same value it started at, then you should end up with the same set of zeroes as you started with (the same set, by the way, which doesn’t guarantee that each solution ends at the same place it started).
4. However, moving each coefficient in a loop in the complex plane sometimes ends up with the solutions switching places. (Illustration below)
5. For any “ordinary” function of the coefficients (a function that can be written using a finite number of rational numbers and the symbols +, -, ×, /, exp(), log(), √, and so on), you can find loops that don’t cause the solutions to switch places.
6. But for some quintic polynomials, you can always finds one of these loops that does cause the roots to switch places.
7. So there are quintic polynomials whose roots cannot be written as any ordinary function of the coefficients (since you can find a loop that permutes the solutions of the quintic but don’t permute the values of any ordinary function).

There are obviously holes in this proof that need to be filled. (1) through (3) should be pretty self-explanatory. And (4) can be illustrated by thinking about functions that involve square roots… on the complex plane, taking a square root of an expression means halving the angle to the expression. So rotating an expression around the complex plane by 2π only ends up rotating its square root by π (and thus bringing it to a different point). Observe:

And in general, a function involving an nth root of some ordinary expression will take n rotations around the complex plane to return each solution to its starting point. Take a look for n = 3:

For (5), you can prove this by using commutator loops (which are formed from two smaller loops L1 and L2 by putting them together as follows: L1 L2 L1-1 L2-1). Ultimately, this works for expressions with roots in them because solutions switch places exactly when you circle the origin of the complex plane, and commutators circle the origin a net zero times. For expressions with one nested root, you actually need to use commutators of commutators (first to return the inner root to its starting value, and then to return the outer root to its starting value). And with two nested roots, you use commutators of commutators of commutators. And so on. In this way, you can construct a loop in the complex plane for any expression you construct from roots and ordinary functions that will bring all values back to their starting points.

And finally, (6) is a result of the structure of the permutation group on five elements (S5). If you look at all commutators of permutations of five elements, you are looking at the commutator subgroup of S5, which is A5 (the set of even permutations of five elements). And the commutator subgroup of A5 is just A5 itself. This means that you can find always find some commutator, or some commutator of commutators, or some commutator of commutators of commutators, (and so on) that is not equal to the identity permutation! (After all, if all commutators of commutators of commutators ended up just being the identity permutation, then the group of commutators of commutators of commutators would just be the trivial group {e}. But we already know that the group of commutators of commutators of commutators is just the commutator subgroup of the commutator subgroup of the commutator subgroup of S5. I.e. the commutator subgroup of A5, which is A5.

And that’s the proof! You can see the whole thing sketched out in much more detail here.

Now, notice that the conclusion was that there are quintic polynomials whose roots cannot be written as any ordinary function of the coefficients. Not that all quintic polynomials’ roots can’t be written as such. Obviously, there are some quintics whose solutions can be written easily. For example…

x5 – 1 = 0
Solutions: x = e2πik/5 for k = 0, 1, 2, 3, 4

But there also exist many quintic polynomials whose roots just have no way of being finitely expressed through ordinary functions! An example of this is the real root of x5 – x – 1.

x5x – 1 = 0
at x ≈ 1.167304…

There is no way to write this number using a finite number of the symbols +, -, ×, /, exp(), log(), √, sin(), cos(), and rational numbers. And this is the case even though this number is an algebraic number! I don’t know if there’s a name for this category of “algebraic numbers that cannot be explicitly expressed using ordinary functions” but there should be.

Of course, you can define a function into existence that just returns the solutions of the quintic (which is what the Bring radical allows one to do). And you can also write the solution with ordinary functions if you’re allowed to use an infinity of them. For example, you can use a repeated fifth root:

x5x – 1 = 0
x5 = x + 1
x = (1 + x)1/5
x = (1 + (1 + x)1/5)1/5
x = (1 + (1 + (1 + x)1/5)1/5)1/5
x = (1 + (1 + (1 + (…))1/5)1/5)1/5

But while an infinity of symbols suffices to express this 1.167304…, no finite number cuts it!

# Group Theory: The Mathematics of Symmetry?

Often you’ll hear people describe group theory as being “the mathematics of symmetry.” If you’ve been exposed to a little bit of group theory, you might find this a little mystifying. While there are some subsets of group theory that explicitly pertain to symmetry (in particular, the dihedral groups, representing the symmetries of regular polygons), there are many more groups that seem to have nothing to do with symmetry (the rational numbers, for example, or the dicyclic groups). Much of group theory involves proving theorems about the structure of groups in abstract, and many of these theorems again seem to tell us little to nothing about symmetry (what does “for every prime p that divides the size of a group G, there is a subgroup of G with order p” mean as a statement about the nature of symmetry?). So what’s up? Why this identification between groups and symmetry?

Well, I think we can start with asking what we even mean by ‘symmetry’. The first thing I think of when I hear the word ‘symmetry’ is geometric symmetry – the rotations, translations, and reflections that hold fixed a given shape. This is indeed one big part of symmetry, but not all of it. Symmetry is huge in physics as well, and the meaning in this context is rarely geometric symmetry. Instead, ‘symmetry’ finds its deepest application in the notion of symmetries of nature, meaning transformations that hold fixed the form of the laws of nature. For instance, the behavior of physical systems would be identical if we were to uniformly “slide” the universe in one direction by some fixed amount. So the laws of nature must be invariant with respect to this type of uniform translation, and we say that uniform spatial translation is a symmetry of nature. But the behavior of physical systems would be affected if we, say, began uniformly accelerating all of space in some direction. So uniform acceleration is not a symmetry of nature, and the laws of nature will be sensitive to these types of transformations. In this context, symmetry is more or less synonymous with invariance.

What’s the similarity between these two senses of symmetry? Invariance really is the key. Geometric symmetries are transformations that hold fixed certain geometric properties; physical symmetries are transformations that hold fixed certain physical properties. Fundamentally, symmetries are transformations that hold fixed some quantity. When you choose strange abstract qualities, your symmetries can get pretty weird (like the invariance of magnetic fields with respect to addition of curl-less vector fields to the magnetic vector potential, one of the two gauge symmetries of Maxwell’s equations). But they are symmetries nonetheless!

Now, how does this expansive concept of symmetries relate to groups? Well, looking at the group axioms, it becomes fairly obvious that they do actually fit pretty well with the concept. Let’s think of the elements of a group as transformations one could perform upon a system, and the group operation as being ‘transformation composition’ for successive transformations. And finally, we think of the group as being a complete set of symmetries. Now we’ll look at what the group axioms say, one at a time.

1. Closure
For any two elements a, b in G, a•b is in G.
– Translation: If two transformations each individually hold fix some quantity, then doing the two transformations successively will also hold fixed the quantity.
2. Associativity
For any a, b, c in G, (a•b)•c = a•(b•c)
– Translation: The order in which transformations are applied to an object is all that determines the nature of the net transformation. The notion of parentheses doesn’t make sense in this context, there is only the left-to-right order of the application of transformations.
3. Identity
There is an element e in G such that for any a in G, a•e = e•a = a.
– Translation: Doing nothing at all holds fixed whatever quantity you choose.
4. Inverses
For any a in G, there is an element a’ in G such that a•a’ = e
– Translation: Any transformation that holds fixed some quantity will also hold fixed that quantity if done in reverse.

Put together, we see that it makes sense to think about a group as the complete set of reversible transformations that hold fixed a certain quantity. (To be clear, this indicates that any such set of symmetries can be treated as a group, not necessarily that any group can be regarded as a set of symmetries. However, this does turn out to be the case! And in fact, any group whatsoever can be considered as a set of geometric symmetries of some abstract object!)

“Complete” needs to be fleshed out a bit more. When talking about a set of transformations, we need to be picking from a well-defined starting set of ‘allowed transformations’. For example, sets of geometric symmetries of objects are usually drawn from the set of all isometries (transformations that keep all distances the same, i.e. rotations, reflections, and translations). Instead of this, we could also consider the allowed transformations to be restricted to the set of all rotations, in which case we’d just be looking at the set of all rotations that don’t change the object. But in general, we are not allowed to talk about the set of possible transformations as just being some subset of the set of all rotations. Why? Because we require that the set of allowed transformations be closed. If a certain rotation is in consideration as an allowed transformation of an object, then so must be twice that rotation, thrice it, and so on. And so must be the reverse of that rotation. Not all sets of rotations satisfy this constraint!

The general statement is that the set of allowed transformations from which we draw our set of symmetries must be closed. And if it is, then the resulting set of symmetries is well described as some group!

So there is a fairly simple sense in which group theory is the study of symmetries. There are the obvious geometric symmetries that I already mentioned (the dihedral groups). But now we can think further about what other familiar groups are actually symmetries of. (, +) is a group, so what are the integers symmetries of? There’s actually a few answers that work here. One is that is the set of translational symmetries of an infinite line of evenly spaced dots. Translating to the right corresponds to positive numbers, to the left is negatives, and no translation at all is 0. What about (n, +)? It is the set of rotational symmetries of a circle with n dots placed evenly along its perimeter. I encourage you to try to think about other examples of groups (symmetric and alternating groups, ℚ, and so on), and how to think about them as symmetry groups.

This way of thinking about groups is more than just visually appealing, it actually helps clarify some otherwise opaque results in group theory. For example, why is the stabilizer of a group action always a subgroup? Well, the group action defines a set of allowed transformations, and the stabilizer of x is exactly the set of transformations that hold x fixed! So we have an invariant quantity x, and thus it is perfectly reasonable that the stabilizer should be a group.

Thinking of groups as sets of symmetries also allows us a nice physical interpretation of the idea of conjugacy classes, a hugely important tool in group theory. Remember, the conjugacy class of an element x in G is just the set of all conjugates of x; Cl(x) = {gxg-1 for all g in G}. This ABA-1 pattern might be familiar to you if you’ve studied a little bit of matrix representations of coordinate systems in physics. In this context, ABA-1 just represents a coordinate transformation of B! First we apply some transformation A that changes our reference frame, then we apply B, and then we undo A to come back to the original reference frame. The result is basically that we get a transformation that are just like B, but in a different reference frame! So it makes perfect sense to think of the conjugacy class of an element x as just the set of all elements of the same “type” as x.

For a dihedral group, we get one conjugacy class for the identity, another for all rotations, and another for all flips. Why? Well every flip can be represented as any other flip in a rotated reference frame! And similarly, every rotation can be represented as any other rotation in a flipped reference frame. And of course, the do-nothing transformation will look the same in all reference frames, which is why the identity has its own conjugacy class. And for another example, you can see some great visualizations of the conjugacy class breakdown of the cube’s symmetry group here, under Examples at the top. In general, looking at conjugacy classes is a good way to get a sense of the natural breakdown of categories in your set of symmetries.

Now, the famous theorems about group structure (Lagrange, Cauchy, Sylow) all have intriguing interpretations as applied to symmetries. Why must it be that any object with a prime number of symmetries cannot have any non-trivial smaller complete sets of symmetries? And doesn’t it seem totally non-obvious that an object that has a complete set of symmetries whose size is divisible by 3, say, must also have a smaller complete set of symmetries (one drawn from a smaller closed set of allowed transformations) whose size is 3? But it’s true! Think about the symmetries of a regular triangle. There are six of them, and correspondingly there’s a closed set of symmetries of size 3, namely, the do-nothing transformation and the two rotations! And the same thing applies for any symmetry group of size 3N.

Furthermore, Sylow’s theorems give us really strong constraints on the number of subgroups of various sizes, none of which seem at all intuitive. Why must it be that if an object has 9N symmetries for some N that’s not divisible by 3, then N must be divisible by the number of smaller complete sets of symmetries?? Thinking about and trying to make intuitive sense of these connections is quite mind-boggling to me.

# Symmetries of Platonic Solids

Definition: A polyhedron is regular if all its faces are the same regular polygon, and all angles are equal.

It turns out that there are only five Platonic solids (convex regular polyhedra).

Here’s a quick proof:

• For a regular n-gon, the sum of its interior angles is (n – 2)π.
• So the angle at any one of its corners must be (n – 2) π/n.
• Now, suppose we have r faces (each a regular n-gon) meeting at every vertex.
• Since the meeting point for each face is a corner with angle (n – 2)π/n, we have that the sum of the angles is r (n – 2) π/n.
• And since the polyhedron is convex we must have r (n – 2) π/n < 2π.
• This can be rewritten as (r – 2)(n – 2) < 4.
• The only positive integers satisfying this are (nr) = (3, 3), (4, 3), (3, 4), (5, 3), (3, 5).
• These are our five Platonic solids!

(3,3): Tetrahedron

Symmetry group: S4

(4,3): Cube

Symmetry group: S4 × 2

(3,4): Octahedron

Symmetry group: S4 × 2

(5,3): Dodecahedron

Symmetry group: A5 × 2

(3,5): Icosahedron

Symmetry group: A5 × 2

— — —

Here’s one more thing to notice; when looking at small dihedral groups, we saw that Dih3 (the symmetry group for a regular triangle) was isomorphic to S3 (the set of permutations of three items). We also saw that this isomorphism did not hold for higher order dihedral groups. In other words, the only regular polygon whose symmetry group was some symmetric group was the triangle.

Now we see that the tetrahedron (which we might consider to be the closest thing to a three-dimensional version of a regular triangle) has as its symmetry group S4. In other words, we get to S4 not by moving to polygons with more sides, but by moving to a higher dimension!

This may bring a conjecture to our minds: perhaps in general, moving up dimensions is the way to get regular geometric shapes that are isomorphic to higher order symmetric groups. That is, perhaps the symmetry group of a regular “triangle-like” objects in n dimensions is isomorphic to Sn. So this would predict that there is some 4D version of the 2D triangle and 3D tetrahedron whose symmetry group is S5. And guess what; this turns out to be right!

The higher dimensional generalization of a triangle and tetrahedron is called a n-simplex. And the symmetry group for each of these simplexes is in fact a symmetric group! So all symmetric groups can be considered to be descriptions of the set of symmetries of some possibly very high-dimensional tetrahedron! This is a fun little piece of trivia that I don’t know quite what to make of.

# Some Curious Group Isomorphisms

## Curiosity Number One

The additive group of polynomials with integer coefficients is isomorphic to the multiplicative group of positive rational numbers: ([x], +) (ℚ+, ).

Any element of [x] can be written like a0 + a1x + a2x2 + … + anxn, where all coefficients a0, a1, …, an are integers. Consider the following mapping: φ: (a0 + a1x + a2x2 + … + anxn) (p0a0p1a1pnan), where pk refers to the kth prime number. Now, this is a homomorphism from [x] to ℚ+ because φ(p(x) + q(x)) = φ(p(x))φ(q(x)). You can also easily show that it is onto and one-to-one, using the uniqueness of prime factorization. Therefore φ is an isomorphism!

I think this is a good example to test the intuitive notion that once one “knows” a group, one also knows all groups that it is isomorphic to. It’s often useful to think of isomorphic groups as being like one book written in two different languages, with the isomorphism being the translation dictionary. But the non-obviousness of the isomorphism here makes it feel like the two groups in fact have a considerably different internal structure.

## Curiosity Number Two

Your friend comes up to you and tells you, “I’m thinking of some finite group. All I’ll tell you is that it has at least two order-2 elements. I’ll give you \$20 if you can tell me what the group that’s generated by these two elements is (up to isomorphism)!“

What do you think your chances are of getting this \$20 reward? It seems intuitively like your chances are probably pretty dismal… there are probably hundreds or maybe even an infinity of groups that match her description.

But it turns out that you can say exactly what group your friend is thinking of, just from this information!

Call the group G. G is finite and has two order-2 elements, which we’ll call a and b. So we want to find out what <a,b> is. Define r = ab and n = |r|.  Then ara = a(ab)a = (aa)ba = ba = (ab)-1 = r-1 = rn-1. So ara = rn-1, or in other words ar = rn-1a. Also, since b = ar, we can write the group we’re looking for either as <a,b> or as <a,r> (these two are equal).

Thus the group we’re looking for can be described as follows:

<a, r | a2 = rn = e, ar = rn-1a>.

Look familiar? This is just the dihedral group of size 2n; it is the group of symmetries of a regular n-gon, where a is a flip and r is a rotation!

So if G is a finite group with at least two order-2 elements a and b, then <a, b> Dih|ab|.

This serves to explain the ubiquity and importance of the dihedral groups! Any time a group contains more than one order-two element, it must have a dihedral group of some order as a subgroup.

## Curiosity Number Three

If K  H G, then H/K G/K and (G/K) / (H/K) ≅ G/H.

(G/K) / (H/K) is a pretty wild object; it is a group of cosets, whose representatives are themselves cosets. But this theorem allows us to treat it as a much less exotic object, an ordinary quotient group with representatives as elements from G.

I don’t have much else to say about this one, besides that I love how the operation of forming a quotient group behaves so much like ordinary division!

# Extending Cauchy’s Theorem

Here I present an extension of Cauchy’s theorem that I haven’t seen anywhere else.

In our earlier proof of Cauchy’s theorem, we saw that r, the number of p-tuples (g,g,…,g) of elements of G whose product is e, had to be a multiple of p. Since (e,e,…,e) was one such p-tuple, we knew that r was greater than zero, and therefore concluded that there must be at least one other element g in G such that gp = e. And that was how we got Cauchy’s theorem. But in our final step, we weakened our state of knowledge quite a bit, from “r = pn (for some positive n)” to “r > 1”. We can get a slightly stronger result than Cauchy’s theorem by just sticking to our original statement and not weakening it.

So, we know that r = pn for some n. Does this mean that there are pn elements of order p? Not quite. One of these p-tuples is just (e,e,…,e), and e is order 1, not p. So there are really (pn – 1) elements of order p.

Furthermore, each of these elements forms a subgroup of size p. Every non-identity element in any of these subgroups is also order p. So this tells us that the number of elements of order p must be k(p – 1), where k is the number of subgroups of order p.

Putting these together, we see that (pn – 1) = k(p – 1). Crucially, this equation can’t be satisfied for all n and p! In particular, for k to be an integer, the value of n must be such that pn – 1 is divisible by p – 1. Let’s look at some examples.

p = 2

2n – 1 must be divisible by 1. This is true for all n.
So k, the number of subgroups of order 2, is 2n – 1 for any positive n.
k = 1, 3, 5, 7, …

p = 3

3n – 1 must be divisible by 2. This is only true for odd n.
So k, the number of subgroups of order 3, is (3n – 1)/2 for any odd n.
k = 1, 4, 7, 10, …

p = 5

5n – 1 must be divisible by 4. This is only true for n = 1, 5, 9, 14, …
So k = 1, 6, 11, 16, …

See the pattern? In general, the number of subgroups of order p can only be 1 + mp for any m ≥ 0. And the number of elements of order p is therefore mp2 – (m – 1)p – 1.

Needless to say, this is a much stronger result than what Cauchy’s theorem tells us!

## An Application

Say we have a group G such that |G| = 15 = 3⋅5. By Cauchy, we know that there’s at least one subgroup of size 3 and one of size 5. But now we can do better than that! In particular we know that:

Number of subgroups of size 3 = 1, 4, 7, 10, …
Number of subgroups of size 5 = 1, 6, 11, 16, …

For each subgroup of size 3, we have 2 unique elements of order 3. And for each subgroup of size 5, we have 4 unique elements of order 5.

Number of elements of order 3 = 2, 8, 14, …
Number of elements of order 5 = 4, 24, 44, 64, …

But keep in mind, we only have 15 elements to work with! This immediately rules out a bunch of the possibilities:

Number of subgroups of size 3 = 1, 4, or 7
Number of subgroups of size 5 = 1

So we know that there is exactly one subgroup of size 5, which means that 4 of our 15 elements are order 5. This leaves us with only 10 non-identity elements left, ruling out 7 as a possible number of subgroups of size 3. So finally, we get:

Number of subgroups of size 3 = 1 or 4
Number of subgroups of size 5 = 1

This is as far as we can go using only our extended Cauchy theorem. However, we can actually go a little further using Sylow’s Third Theorem. This allows us to rule out there being four subgroups of size 3 (since 4 doesn’t divide 5). So the “subgroup profile” of G is totally clear: G has one subgroup of size 3 and one of size 5. You can use this fact to show that there is exactly one group of size 15, and it is just 15.

15 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
Subgroup of size 3 = <5> = {0, 5, 10}
Subgroup of size 5 = <3> = {0, 3, 6, 9, 12}
All other elements generate the whole group.

# Strong Induction Proofs of Cauchy’s Theorem and Sylow’s First Theorem

Here are three really fun little proofs of some of the strongest results in group theory, all of which use very similar methods (strong induction and the class equation) in subtly different ways. They require a little bit of background (only some of which I’ve provided), and you should not expect to grasp it with a quick read-through. I encourage you to read through slowly and carefully, making sure you understand each step of the proofs. I promise it will feel rewarding once you’re done!

# Background

These proofs mostly rely on the Class Equation. I’ll spend a little bit of time showing where it comes from. (You can skip this section if you already know or don’t care where it comes from.)

Partition Equation: Suppose G acts on X. Then the orbits of this action partition X. That is, the orbits of any two elements either share all their elements or none of them, and every element in X is in some orbit. So |X| = ∑|orb(x)|, where the sum is taken over representatives from each orbit.

Orbit Stabilizer Theorem: For any x in X, |orb(x)||stab(x)| = |G|. Here stab(x) refers to the subset of G that fixes x (“stabilizes” it) under the group action. So stab(x) = {g in G : g•x = x}.

Stabilizers are Subgroups: The stabilizer of any x in X is a subgroup of G.

Now we look at the special case of G acting on itself by conjugation. I.e. we define g • x = gxg-1. The orbit of any element x is its conjugacy class Cl(x), and stab(x) is x’s centralizer C(x). So the partition equation for the conjugacy action is |G| = ∑|Cl(x)|, where the sum is taken over representatives of conjugacy classes. And the Orbit Stabilizer Theorem becomes |Cl(x)|⋅|C(x)| = |G|.

Cl(x) = {gxg-1 for all g ∈ G}
C(x) = {g in G such that gx = xg}

You can easily show that for any central element in G (that is, for any element that commutes with every other element in G), its conjugacy class just contains itself. This means that |Z(G)| terms in this sum are equal to 1. So we can rewrite our equation, taking this into account. This gives us the Class Equation.

Class Equation: |G| = |Z(G)| + ∑|Cl(x)|, where the sum is taken over non-central representatives of conjugacy classes.

• Z(G) is a subgroup of G, so |Z(G)| ≥ 1.
• Since the terms in the sum are by definition sizes of conjugacy classes of non-central elements, none of them have size 1. That is, |Cl(x)| > 1 for every non-central x.
• All terms divide |G|. This follows for Z(G) by Lagrange’s theorem (because it’s a subgroup). And it must be true for each |Cl(x)| by the Orbit-Stabilizer Theorem.

That’s all we need! We’re ready to prove Cauchy’s Theorem and Sylow’s First Theorem!

# Proof of Cauchy’s Theorem

Cauchy’s theorem: G has a subgroup of size p for every prime p that divides |G|.

Part 1: First we show that Cauchy’s theorem holds for all abelian groups. This can be proven by strong induction. The base case is |G| = p, which trivially has a subgroup of size p (itself). Now we take a look at any larger group G such that p divides |G|. The strong inductive hypothesis is that Cauchy’s theorem holds for all abelian groups of size less than |G|.

Now, take any non-identity element g in G. Let H = <g>.

• Case 1: Suppose p divides |H|. Then g|H|/p is an element of order p.
• Case 2: Suppose p doesn’t divide |H|. Then p must divide |G/H| (since |G| = |H|⋅|G/H|). Since G is an abelian group, G/H is also an abelian group. And since we chose g to be non-identity, |H| > 1, so |G/H| < |G|. Thus by the inductive hypothesis, G/H contains an element xH of order p. But this implies that |x| is a multiple of p. After all, xH is order p, and (xH)|x| = x|x|H = eH = H. So x|x|/p is an element of order p. Done!

Now that we’ve proven Cauchy’s theorem for all abelian groups, we go on to prove it for all groups.

Part 2: We use strong induction again. The base case is |G| = p, which is trivial. Now, suppose G is a group such that |G| is divisible by prime p. The strong induction hypothesis is that Cauchy’s theorem holds for all groups of size less than |G|.

Let’s examine the Class Equation: |G| = |Z(G)| + ∑|Cl(x)|.

• Case 1: Suppose that for some x, |Cl(x)| is not divisible by p. Then for this x, |C(x)| must be divisible by p (since |Cl(x)||C(x)| = |G|). Since centralizers are subgroups, C(x) is a subgroup with size divisible by p. Furthermore, since |Cl(x)| > 1, |C(x)| < |G|. So by the induction hypothesis, C(x) has a subgroup of size p.
• Case 2: For all x, |Cl(x)| is divisible by p. But so is |G|. So |Z(G)| must be divisible by p as well. But Z(G) is abelian, so it must have a subgroup of size p (by Part 1).

And we’re done!!

With this result in hand, we can go even deeper and prove Sylow’s First Theorem. This one is slightly more involved, so take a breather if you need one…

… And now let’s dive into it!

# Proof of Sylow’s First Theorem

Here’s Sylow’s First Theorem: For every prime power in the factorization of |G|, there is a subgroup of that size. In other words, if G is a finite group such that pn divides |G| for some prime p, then G has a subgroup of order pn.

Again, we proceed by strong induction. Our base case is |G| = p, which is trivial. Now we look at a larger group G, and assume that the theorem is true for all groups of size less than |G|.

Class Equation: |G| = |Z(G)| + ∑|Cl(x)|.

• Case 1: Suppose at least one of the terms in the sum ∑|Cl(x)| isn’t divisible by p. Then for this x, |C(x)| must be divisible by pn (since |Cl(x)||C(x)| = |G|). Since centralizers are subgroups, we have a subgroup with size divisible by pn. Furthermore, since each |Cl(x)| > 1, |C(x)| < |G|. So by the induction hypothesis, C(x) has a subgroup of size pn.
• Case 2: Each |Cl(x)| is divisible by p, as is |G|. So |Z(G)| must be divisible by p. So by Cauchy, Z(G) has an element of order p, say g. Define N = <g>. N is normal, since it’s in the center. So G/N is a group. |G/N| = |G|/|N| = |G|/p, so by induction, G/N has a subgroup H of size pn-1. Now, consider the canonical homomorphism φ: G → G/N defined by φ(g) = gN. It turns out that φ-1(H), the inverse image of H, is a subgroup of G with size pn, just what we were looking for!
• Why is |φ-1(H)| = pn? Well, each element of G/N is a coset, and all cosets have the same size, namely |N|. This means that |N| elements are mapped to any given coset by φ. H is a subset of G/N, so it contains |H| cosets, each of which is mapped to by |N| elements. Since cosets are disjoint, there is no overlap. So φ-1(H) = |N|⋅|H| = p⋅pn-1 = pn.

(Proofs can be found in Judson’s Abstract Algebra)

# Table of Small Finite Groups

## Order 1: 1 Group

 Abelian Cyclic Simple ℤ1 = S1 = A2 Y Y Y

## Order 2: 1 Group

 Abelian Cyclic Simple ℤ2 = S2 Y Y Y

## Order 3: 1 Group

 Abelian Cyclic Simple ℤ3 = A3 Y Y Y

## Order 4: 2 Groups

 Abelian Cyclic Simple ℤ4 Y Y ℤ22 = K4 Y

## Order 5: 1 Group

 Abelian Cyclic Simple ℤ5 Y Y Y

## Order 6: 2 Groups

 Abelian Cyclic Simple ℤ6 = ℤ3 × ℤ2 Y Y Dih3 = S3

## Order 7: 1 Group

 Abelian Cyclic Simple ℤ7 Y Y Y

## Order 8: 5 Groups

 Abelian Cyclic Simple ℤ8 Y Y ℤ4 × ℤ2 Y ℤ23 Y Dih4 Dic2 = Q8

## Order 9: 2 Groups

 Abelian Cyclic Simple ℤ9 Y Y ℤ3 × ℤ3 Y

## Order 10: 2 Groups

 Abelian Cyclic Simple ℤ10 = ℤ5 × ℤ2 Y Y Dih5

## Order 11: 1 Group

 Abelian Cyclic Simple ℤ11 Y Y Y

## Order 12: 5 Groups

 Abelian Cyclic Simple ℤ12 = ℤ4 × ℤ3 Y Y ℤ6 × ℤ2 = ℤ3 × ℤ22 Y Dic3 A4 Dih6 = Dih3 × ℤ2

## Order 13: 1 Group

 Abelian Cyclic Simple ℤ13 Y Y Y

## Order 14: 2 Groups

 Abelian Cyclic Simple ℤ14 = ℤ7 × ℤ2 Y Y Dih7

## Order 15: 1 Group

 Abelian Cyclic Simple ℤ15 = ℤ5 × ℤ3 Y Y

## Order 16: 14 Groups

 Abelian Cyclic Simple ℤ16 Y Y ℤ8 × ℤ2 Y ℤ42 Y ℤ4 × ℤ22 Y ℤ24 Y Dih8 Dic4 Dih4 × ℤ2 Dic2 × ℤ2 K4 ⋊ ℤ4 ℤ4 ⋊ ℤ4 ℤ8 ⋊ ℤ2 (ℤ4 × ℤ2) ⋊ ℤ2 QD16

## Order 17: 1 Group

 Abelian Cyclic Simple ℤ17 Y Y Y

## Order 18: 5 Groups

 Abelian Cyclic Simple ℤ18 = ℤ9 × ℤ2 Y Y ℤ6 × ℤ3 = ℤ32 × ℤ2 Y Dih9 S3 × ℤ3 (ℤ3 × ℤ3) ⋊ ℤ2

## Order 19: 1 Group

 Abelian Cyclic Simple ℤ19 Y Y Y

## Order 20: 5 Groups

 Abelian Cyclic Simple ℤ20 = ℤ5 × ℤ4 Y Y ℤ10 × ℤ2 = ℤ5 × ℤ3 × ℤ2 Y Dih10 = Dih5 × ℤ2 Dic5 ℤ5 ⋊ ℤ4

## Order 21: 2 Groups

 Abelian Cyclic Simple ℤ20 = ℤ7 × ℤ3 Y Y ℤ7 ⋊ ℤ3

## Order 22: 2 Groups

 Abelian Cyclic Simple ℤ22 = ℤ11 × ℤ2 Y Y Dih11

## Order 23: 1 Group

 Abelian Cyclic Simple ℤ23 Y Y Y

## Order 24: 14 Groups

 Abelian Cyclic Simple ℤ24 = ℤ8 × ℤ3 Y Y ℤ12 × ℤ2 = ℤ6 × ℤ4 Y ℤ6 × ℤ22 = ℤ3 × ℤ23 Y Dih12 Dih6 × ℤ2 Dih4 × ℤ3 S4 S3 × ℤ4 A4 × ℤ2 Dic6 Dic3 × ℤ2 Dic2 × ℤ3 ℤ3 ⋊ ℤ8 ℤ3 ⋊ Dih4 SL(2,3) = 2T

## Order 25: 2 Groups

 Abelian Cyclic Simple ℤ25 Y Y ℤ52 Y

## Order 26: 2 Groups

 Abelian Cyclic Simple ℤ26 = ℤ13 × ℤ2 Y Y Dih13

## Order 27: 5 Groups

 Abelian Cyclic Simple ℤ27 Y Y ℤ9 × ℤ3 Y ℤ33 Y ℤ32 ⋊ ℤ3 ℤ9 ⋊ ℤ3

## Order 28: 3 Groups

 Abelian Cyclic Simple ℤ28 = ℤ7 × ℤ4 Y Y ℤ14 × ℤ2 = ℤ7 × ℤ22 Y Dih14 Z7 ⋊ Z4

## Order 29: 1 Group

 Abelian Cyclic Simple ℤ29 Y Y Y

## Order 30: 4 Groups

 Abelian Cyclic Simple ℤ30 = ℤ15 × ℤ2 = ℤ10 × ℤ3 = ℤ6 × ℤ5 Y Y Dih15 Dih5 × ℤ3 S3 × ℤ5

## Order 31: 1 Group

(Order p)

 Abelian Cyclic Simple ℤ31 Y Y Y

## Order 32: 51 Groups

I’m not going to list these all here, but seven of them are abelian.

(All cycle graphs stolen from Wikipedia)

# Notable Groups

A5: Smallest simple group that isn’t cyclic. Order 60.

22: Smallest non-cyclic group.

Dih3: Smallest non-abelian group.

A4: First example where n divides |G| but there is no element of order n. (n = 6)

Z7 ⋊ Z3: Smallest non-abelian group of odd size.

Dih3: Smallest group with a normal subgroup that isn’t isomorphic to one of its subgroups.

# General Patterns

1 group of order p
2 groups of order p2
5 groups of order p3
15 groups of order p4, for p > 2
2 groups of order pq for q-1 divisible by p
1 group of order pq for q-1 not divisible by p

# Some Group Factoids

## Groups of Size 2n

Most finite groups are size 2n. For example, over 99% of all groups of size 2000 or less are size 1024.

## How to Decompose a Group Into a Direct Product

If H and K are subgroups of G with trivial intersection, HK = G, and all elements of H commute with all elements of K, then G is isomorphic to H × K.

## Kernel of Homomorphism Is Normal Subgroup

If φ: G → G’ is a homomorphism, then ker(φ) = φ-1(eG’) is a normal subgroup of G.

A homomorphism is a function from one group G to another group G’ that maintains the group structure: φ(ab) = φ(a)•φ(b). It’s similar to an isomorphism, but is not required to be one-to-one or onto (so multiple elements of G can be mapped to the same element of G’). The kernel of φ is the set of elements in G that are sent by φ to the identity in G’.

## Cayley’s Theorem

Every group of size n is a subgroup of Sn, the the set of all permutations of n items. In addition, Sn contains Sm for all m < n.

This means that if you want to all groups of size 2000 or less, you just need to look at the structure of S2000 (which has 2000! elements). In some sense, then, the study of finite groups is just the study of the structure of large permutation groups.

## Group Presentation Undecidability

A group presentation looks like S|R, where S is a set of generators for the group, and R is a set of relations among the generators.

For example: a | an = e is the cyclic group of size n (Zn). Another example: r,f | rn = e, f2 = e, fr = rn-1f is the dihedral group of size 2n (the set of symmetries of a regular n-gon).

A finite presentation for a group is just a presentation where S and R are both finite. All finite groups have a finite presentation (easy proof: let S contain all the members of the group, and R be its Cayley table), as do some infinite groups (for example, a | ∅⟩, the group generated by a with no constraints).

Now, you can ask whether there exists an algorithm that takes as input a finite presentation, and figures out whether the group it represents has a certain property (like, is it the trivial group? Is it a finite group? Is it abelian? Is it simple? And so on.) It turns out that for each of these, the answer is no! In addition, the question of if two arbitrary words (e.g. for Dihn, frfrfr and rfrrf) represent the same element is undecidable. So is the question of if two finite presentations represent isomorphic groups.

In general, for pretty much any non-trivial property of a group (a property that isn’t shared by all groups), there is no general algorithm that decides whether a finite presentation has that property!

# The Toolkit

1. The Group Axioms
1. Closure: a,b ∈ G, a•b ∈ G
2. Associativity: a,b,c ∈ G, (a•b)•c = a•(b•c)
3. Identity: ∈ G s.t. ∈ G, e•a = a•e = a
4. Inverses: ∈ G, a’ ∈ G s.t. a’•a = e
2. Cancellation Rule
(a•b = a•c) (b = c)
3. Order Doesn’t Matter
You can write a Cayley table with the elements in any order that’s convenient.
4. Sudoku Principle
Each row and column in the Cayley table for a group G contains every element in G exactly once.
5. Lagrange’s Theorem
H ≤ G |G| is divisible by |H|
6. Elements Generate Subgroups
∈ G, <g> = {gk for all integer k} ≤ G.
(|<g>| = n) (gn = e).
7. Cauchy’s Theorem
(|G| = pk for prime p) (∈ G s.t. gp = e)
8. Classification of Finite Abelian Groups
Every finite abelian group is isomorphic to Zn or direct products of Zn
9. Orbit-Stabilizer Theorem
|orb(x)||stab(x)| = |G|
10. Partition Equation
∑|orb(x)| = |X|. The sum is taken over one representative for each orbit.
11. Center is a Normal Subgroup
Z(G), the center of G, is a normal subgroup. So G/Z is a group.
12. Class Equation
|G| = |Z| + ∑|Cl(x)|, where all terms divide |G| and each |Cl(x)| is neither 1 nor |G|. The sum is taken over non-central representatives of conjugacy classes.
13. G/Z is Cyclic Implies G is Abelian
G/Z is cyclic  G is abelian
14. Size of Product of Subgroups
|AB| = |A| |B| / |A B|
15. Sylow’s First Theorem
If |G| = pnk for prime p and k not divisible by p, then G has a subgroup of size pn.
16. Sylow’s Third Theorem
If |G| = pnk for prime p and k not divisible by p, then the number of subgroups of size pn must be 1 mod p, and must divide k.

# Exercises

## Example 1: Solving the group of size 3

Suppose |G| = 3. By the Identity Axiom (1.3), G has an identity element e. Call the other two elements a and b. So G = {e, a, b}. Let’s write out the Cayley table for the group:

 e a b e e a b a a b b

By the Cancellation Rule (2), a•a ≠ a. By Lagrange’s Theorem (5), a•a ≠ e, as then the set {e, a} would be a subgroup of size 2, which doesn’t divide 3. Therefore by Closure (1.1), a•a = b.

 e a b e e a b a a b b b

We can fill out the rest of the Cayley table by the Sudoku principle (4).

 e a b e e a b a a b e b b e a

## Example 2: Solving the group of size 5

 e a b c d e e a b c d a a b b c c d d

If a•a = e, then {e,a} would be a subgroup of size 2. By Lagrange’s theorem, then, a•a ≠ e. Also, by the Sudoku principle, a•a ≠ a. Thus we can choose the order of the rows/columns such that a•a = b (3).

 e a b c d e e a b c d a a b b b c c d d

Now look at a•b = a•(a•a) = a3. If a3 = e, then <a> would be a subgroup of size 3 (by 6). 3 doesn’t divide 5, so a•b ≠ e (Lagrange’s theorem again). By the Sudoku principle, a•b also isn’t a or b. So we can arrange the Cayley table so that a•b = c. Since a•b = a3 =  b•a, b•a = c as well.

 e a b c d e e a b c d a a b c b b c c c d d

Now we can use the Sudoku principle to fill out the rest!

 e a b c d e e a b c d a a b c d e b b c d e a c c d e a b d d e a b c

## Example 3: Solving all groups of prime order

Suppose |G| = p, where p is some prime number. By Lagrange’s theorem every subgroup of G has either size 1 (the trivial subgroup {e}) or size p (G itself). Since the set generated by any element is a subgroup, any element g in G must have the property that |<g>| = 1 or p.

Choose g to be a non-identity element. <g> includes e and g, so |<g>| ≥ 2. So |<g>| = p. So <g> = G. So G is a cyclic group (generated by one of its elements). This fully specifies every entry in the Cayley table (gn•gm = gn+m), so there is only one group of size p up to isomorphism.

## Example 4: Solving size 6 groups

Suppose |G| = 6.

By Cauchy’s theorem (7), there exists at least one element of order 2 and at least one element of order 3. Name the order-2 element a and the order-3 b. Fill in the Cayley table accordingly:

 e a b ? ? ? e e a b a a e b b ? ? ?

Suppose b2 = a. Then (b2)2 = a2 = e, so b is order 4. But b is order 3. So b2 ≠ a. Also, b2 ≠ e for the same reason, and ≠ b by the Cancellation Rule . So b2 is something new, which we’ll put in our next column:

 e a b b2 ? ? e e a b b2 a a e b b b2 b2 b2 ? ?

b3 = e, so we can fill out b • b2 and b2 • b, as well as b2 • b2 = b3 • b = b

 e a b b2 ? ? e e a b b2 a a e b b b2 e b2 b2 e b ? ?

By the Sudoku principle, we can clearly see that a • b is none of e, a, b, or b2. So whatever it is, we’ll put it in the next column as “ab”:

 e a b b2 ab ? e e a b b2 ab a a e ab b b b2 e b2 b2 e b ab ab ?

Looking at a•b2, we can again see that it is none of the elements we’ve identified so far. So whatever it is, we’ll put it in the next column as “ab2”.

 e a b b2 ab ab2 e e a b b2 ab ab2 a a e ab ab2 b b b2 e b2 b2 e b ab ab ab2 ab2

Associativity (1.2) allows us to use the algebraic rules a2  = e and b3 = e to fill in a few more spots (like a•ab = a2b = b).

 e a b b2 ab ab2 e e a b b2 ab ab2 a a e ab ab2 b b2 b b b2 e b2 b2 e b ab ab ab2 a ab2 ab2 a ab

Now everything else in the table is determined by a single choice: should we assign b•a to ab, or to ab2? Each leads to a Cayley table consistent with the axioms, so we write them both out, using the Sudoku principle to finish each one entirely.

Group 1: (ba = ab)

 e a b b2 ab ab2 e e a b b2 ab ab2 a a e ab ab2 b b2 b b ab b2 e ab2 a b2 b2 ab2 e b a ab ab ab b ab2 a b2 e ab2 ab2 b2 a ab e b

Group 2: (ba = ab2)

 e a b b2 ab ab2 e e a b b2 ab ab2 a a e ab ab2 b b2 b b ab2 b2 e a ab b2 b2 ab e b ab2 a ab ab b2 ab2 a e b ab2 ab2 b a ab b2 e

These two groups are clearly not isomorphic, as one is commutative and the other not. This proves that there are two groups of size 6 up to isomorphism!

## Example 5: Solving groups of prime order, again

Suppose |G| = p, where p is some prime number. The center of G, Z(G), is a subgroup of G (by 11). So by Lagrange’s theorem, |Z| = 1 or p.

By the Class Equation (12), |G| = |Z| + ∑|Cl(x)|. All terms divide p and each |Cl(x)| ≠ 1, so we have p = |Z| + ∑p. This is only possible if |Z| = 0 or there are no non-central elements. Z contains e, so |Z| ≠ 0. So there are no non-central elements. Thus G = Z, which is to say G is abelian.

By the Classification of Finite Abelian Groups (8), G is isomorphic to Zp.

## Example 6: Prime power groups have non-trivial centers

Suppose |G| = pn, where p is some prime number and n is some positive integer. The Class Equation tells us that |G| = |Z| + ∑|Cl(x)|, where |Z| = 1, p, p2, …, or pn and each |Cl(x)| = p, p2, …, or pn-1. Taking the Class Equation modulo p we find that |Z| = 0 (mod p), so |Z| cannot be 1. So G has a non-trivial center!

## Example 7: Solving groups of prime-squared order

Suppose |G| = p2, where p is some prime number. The Class Equation tells us that |G| = |Z| + ∑|Cl(x)|, where |Z| = 1, p, or p2 and each |Cl(x)| = p. So we have p2 = |Z| + ∑p. Taking this equation mod p we find that |Z| = 0 (mod p), so |Z| is non-trivial. (This is just a special case of Example 6 above.) So |Z| = p or p2.

Suppose |Z| = p. Then |G/Z| = p2/p = p. So G/Z is cyclic. But then G is abelian (by 13). So G = Z, which implies that |Z| = p2. Contradiction. So |Z| = p2, i.e. G is abelian.

By the classification of finite abelian groups we see that there are two possibilities: G is isomorphic to integers mod p2 or G is isomorphic to Zp x Zp. These are the only two groups (up to isomorphism) of size p2.

## Example 8: Proving Cauchy’s Theorem

Suppose |G| = n, where n is divisible by some prime p.

Let X be the subset of p-tuples of elements from G whose product is e. That is, X = {(g1,g2,…,gp) Gp s.t. g1g2…gp = e}. Notice that the number of elements in X is |G|p-1 (there are |G| choices for each of the first p-1 elements, and then the final one is fully determined by the constraint). Let the integers mod p (Zp) act on X by the following rule: the action of 1 on an element of X is 1 • (g1,g2,…,gp) = (gp,g1,g2,…,gp-1). (From this we can deduce the action of all the other integers mod p.)

By the Orbit Stabilizer Theorem (9), the possible orbit sizes for this action must divide the size of the cyclic group. That is, for every x X, |orb(x)| = 1 or p. Let r be the number of orbits of size 1 and s be the number of orbits of size p. Then by the Partition Equation (10), we have r + sp = |X| = |G|p-1. By our starting assumption, we have that the right hand side is divisible by p. And since sp is divisible by p, r must also be divisible by p. That is, r = 0, or p, or 2p, and so on.

Notice that the p-tuple (e,e,…,e) is in X, and that its orbit size is 1. So r is at least 1. So r = p, or 2p, and so on. That means that there is at least one more element of X with orbit size 1. This element must look like (a,a,…,a) for some a G. And since it’s in X, it must satisfy our constraint, namely: ap = e! So there is at least one non-identity element of order p.

## Example 9: Subgroups of Group of Size 20

Suppose |G| = 10 = 22*5

By Cauchy’s Theorem and Sylow’s First Theorem (15), we know there must be subgroups of size 2, 4, and 5. We can learn more about the number of subgroups of sizes 4 and 5 using Sylow’s Third Theorem (16).

If N is the number of subgroups of size 4, then N divides 5 (1 or 5), and N = 1 (mod 2). So N = 1 or 5.

If N is the number of subgroups of size 5, then N divides 4 (1, 2, 4), and N = 1 (mod 5). So N = 1.

## Example 10: Subgroups of Group of Size p2q

Suppose |G| = p2q, for primes p and q where 2 < p < q and q-1 is not a multiple of p.

Then by (15) we have subgroups of size p2 and q. Again, we use (16) to learn more about these subgroups.

If N is the number of subgroups of size p2, then N divides q (1 or q), and N = 1 (mod p). q ≠ 1 (mod p), N cannot be q. So N = 1.

If N is the number of subgroups of size q, then N divides p2 (1, p, or p2), and N = 1 (mod q) (so N is 1, or q+1, or 2q+1, and so on). But p is smaller than q, so N can’t be p. And if N = p2, then p2 – 1 must be a multiple of q. But p2 – 1 = (p+1)(p-1). Both of these values are too small to contain factors of q. So their product cannot be a multiple of q. So N ≠ p2 either. So N = 1!

## Example 11: Subgroups of Group of Size pqn

Suppose |G| = pqn, where p and q are primes and 2 < p < q.

Using Sylow III (16): If N is the number of subgroups of size qn, then N divides p (1 or p) and N = 1 (mod q). p is too small to be a multiple of q plus 1, So N = 1.

## Example 12: Classifying Groups of Size 2p

Suppose |G| = 2p for some prime p > 2. Let’s use everything in our toolkit to fully classify the possibilities!

By Cauchy, we have elements of of order 2 and p. Let a be an element of order 2 and b an element of order p. Let A = <a> = {e, a} and B = <b> = {e, b, b2, …, bp-1}. A and B are both cyclic of different orders, so their intersection is trivial. So by (14), |AB| = |A| |B| / |A B| = 2p. So AB = G. This means we can write all the elements of G as follows:

 e b b2 … bp-1 e e b b2 … bp-1 a a ab ab2 … abp-1

So G = {e, b, b2, …, bp-1, a, ab, ab2, …, abp-1}. Call N2 the number of subgroups of size 2 and Np the number of subgroups of size p. Applying Sylow III, it is easy to see that there are two possibilities: (N2 = 1 and Np = 1), or (N2 = p and Np = 1).

Case 1: N2 = p and Np = 1.

Since N2 = p and Np = 1, there are p elements of order 2 (one for each subgroup) and p-1 elements of order p. Adding in e, this accounts for all of G.

Order 1: e
Order p: b, b2, …, bp-1
Order 2: a, ab, ab2, …, abp-1 (the remaining members of G)

Now, since a and b are in G, so must be ba. And since G = AB, ba AB. It’s not e or a power of b (apply the Cancellation Rule), so ba must be abn for some n. This means that ba is order 2, so (ba)2 = e. Expanding and substituting, we get (ba)2 = (ba)(ba) = (ba)(abn) = ba2bn = bn+1 = e = bp.

So n = p – 1, or in other words, ba = abp-1. This actually allows us to fully fill out the rest of the Cayley table, as we can take any expression and move the ‘b’s all the way to the right, ending up with something that looks like anbm.  This is the dihedral group of degree p (the group of symmetries of a regular p-gon)!

Case 2: N2 = 1 and Np = 1.

Order 1: e
Order p: b, b2, …, bp-1
Order 2: a

No other elements can be order 1, 2, or p, so all other elements must be order 2p (think Lagrange’s theorem). For instance, (ab)2p = e and (ab)p ≠ e . You can show that this only works if ab = ba, which allows you to freely move ‘a’s and ‘b’s around in any expression. ((ab)2p = a2p b2p = (a2)p (bp)2 = e, and (ab)p = ap bp = ap = a ≠ e).

Again, we can use this to fill out the entire Cayley table. The group we get is isomorphic to Z2p (the integers mod 2p)!

So if |G| = 2p for some prime p > 2, then G is either the group of symmetries of a regular p-gon, or it’s the integers mod p. Fantastic! If you follow this whole line of reasoning, then I think that you have a good grasp of how to use the toolkit above.

# The sweet spot on the structure spectrum

If you’ve looked into abstract algebra at all, you might be intimidated by the variety of strange-sounding names; things like like monoids, magmas, semigroups, loops, fields, and so on. What are all these names about?

In general, the procedure is as follows: Choose some number of sets, equipped with some number of binary operations. Then endow these operations with some general structural constraints (things like commutativity, associativity, and so on). The result is some abstract mathematical object that might be very interesting or just medium interesting, depending on the constraints that you’ve applied. The different subfields within abstract algebra are just the studies of what you get when you apply particular <sets, operations, constraints> triples! Let’s take a little tour of these subfields.

We start with the most basic. The simplest choice you could make for the sets and operations would be one set S with one binary operation • on that set, denoted as (S, •). The most primitive constraint that you can apply to this operation is closure, which is the condition that the output of the binary operation must always be an element of S. Common constraints added on top of this include:

• Associativity (A): For all a, b, and c in S, (a • b) • c = a • (b • c)
• Identity (E): there is an element e in S such that for all a in S, e • a = a
• Invertibility (V): for all a in S, there is an element a’ in S such that a’ • a = e
• Commutativity (C): for all a and b in S, a • b = b • a

Now we can consider the different types of mathematical objects that arise from different combinations of these constraints!

AEVC = Abelian group
AEV = Group
AEC = Commutative Monoid
AE = Monoid
A = Semigroup
Only closure = Magma

These are just a few examples, and this is all for the case of a single set with a single operation. Two of the biggest objects of study in abstract algebra are rings and fields, both of which involve one set and two binary operations, usually denoted as + and •. The constraints for rings are as follows:

(R, +, •)
(R,+) is an abelian group (AEVC)
(R,•) is a monoid (AE)
Distributivity (of multiplication with respect to addition): a • (b + c) = a•b + a•c

(Rings also have a slightly more bare-bones cousin called rngs, which are basically rings without a multiplicative identity.)

Fields involve even more structure than rings:

(F, +, •)
(F, +) is an abelian group (AEVC) (call its identity 0)
(F \ {0}, •) is an abelian group (AEVC)

There are so many other mathematical objects besides these, each of which has its own field of study. When you survey these fields at a high level of abstraction, an interesting pattern becomes apparent.

Observation 1: More structured objects are simpler and easier to fully characterize.

Think about vector spaces. A vector space has two sets (call them F and V) and four binary operations (two on F x F, one on V x V, and one on F x V). F forms a field with its two operations, and V forms an abelian group with its operation. And there are a few more constraints on the final operation, ensuring that it is well-behaved in a bunch of ways. Overall, vector spaces are highly constrained in many ways. And as such, linear algebra (the study of vector spaces) is a completely solved field. There are pretty much no interesting new discoveries in linear algebra, because there are only a few interesting things you can say about such well-structured objects, and all such things have been quickly discovered. (A quick caveat: linear algebra finds all sorts of applications in more complicated domains of math, many of which have unsolved problems. I’m not considering these problems as part of understanding vector spaces. There are also more applied open questions about, say, how to most efficiently calculate the product of two n x n matrices, which I again do not consider to reflect a lack of understanding of the structure of vector spaces.) And by the way, this is not a knock on linear algebra! I love vector spaces. It’s just that I think there are even more interesting objects out there!

Take another example, fields. Fields are less structured than vectors in a bunch of ways, but all the same, we can fully characterize all finite fields with a few simple equations. The work required to do this is fairly trivial; you can prove the classification theorems in a couple of minutes with barely any background required. For instance, you can quickly prove that all finite fields have sizes that are powers of primes. And furthermore, all finite fields of the same size are isomorphic! So if you were to write out a function f(n) for the number of non-isomorphic fields of size n, it would just be 1 for every prime power and 0 for everything else.

Similarly, compare abelian groups to groups. Abelian groups are strictly more structured objects that groups, being that they are just groups that satisfy the additional constraint of commutativity. They are also significantly less structured than fields, being that they only have to satisfy the constraints for one operation and thus don’t have to worry about distributivity between two operations. It turns out that just like with fields, you can actually classify all finite abelian groups, and write out a (relatively simple) equation for the number of finite abelian groups of size n. This number is the product of the partition numbers of the exponents of each prime in the prime factorization of n. Proving this takes a lot more work than the classification of fields, and the function is clearly much more complicated than the corresponding function for fields. But it’s enormously simpler than classifying all finite groups!

As far as I’m aware, there is no known formula that takes in a number N and returns the number of non-isomorphic groups of size N. Although there are lots of little facts known about the values of this function for particular values of N (for example, for any prime p, f(p) = 1 and f(p^2) = 2), classification in general is enormously difficult. Here are the numbers of finite groups of order N, for small values of N starting at 1.

[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51, 1, 2, 1, 14, 1, 2, 2, 14, 1, 6, 1, 4, 2, 2, 1, 52, 2, 5, 1, 5, 1, 15, 2, 13, 2, 2, 1, 13, 1, 2, 4, 267]

(Fun exercise, try seeing how many of these you can prove for yourself!)

Here’s a plot of this sequence, to give you a sense of how complicated and strange it is:

Furthermore, there are bizarre things like the sporadic groups with their stubborn resistance to categorization, and the king of the sporadic groups, the enormous Monster group. All this structure immediately vanishes as soon as you introduce commutativity, leaving you with a much less interesting object!

Observation 2: Highly unstructured objects also become easy to characterize. Think about magmas (M, •), whose only constraint is closure. How many magmas are there of size N? Well, for any two elements in M, there are N choices for the value of their product. So it’s just the number of ways of placing elements from M in N^2 spots, i.e. N^(N^2). Simple! The lack of structure here actually makes classification of the finite magmas extremely quick and easy.

Another example: Take a slightly more structured object, magmas with identity. This basically just fills in 2N – 1 of our slots (for all m, we get that e•m = m and m•e = m), so that our new classification is just N^(N^2 – 2N + 1). What if we add commutativity? Well, that just cuts our degrees of freedom roughly in half, since every time you choose the value of a•b, you have also chosen b•a! (It’s not exactly half, because of the elements that look like a•a).

But if you now add associativity, you end up with a commutative monoid. These objects are vastly more complicated and difficult to characterize. In general, associativity is probably the most interesting single property you can give to an operation (at least, of the commonly used properties we’ve discussed). By constraining an operation to be associative, you automatically endow your mathematical object with a great degree of interesting structure.

The conclusion I’ve drawn from these observations is that there is a sweet spot of subjective “interestingness” that exists between the highly structured and the highly unstructured. I think that objects like groups and rings occupy this sweet spot, and as you go further in either direction of the structure spectrum the objects you find become less interesting and harder to find surprising results about.