An Example Using Modular Addition
Last time, we saw algebraic structures whose underlying sets were infinitely large (e.g., the real numbers ). Are finite groups possible?
Consider the structure . Is it a group? No, it isn’t even a magma: ! Is there a different operation that would produce closure?
Modular arithmetic is the mathematics of clocks. Clocks “loop around” after 12 hours. We can use modulo-4 arithmetic, or , on . For example, .
To check for closure, we need to add all pairs of numbers together, and verify that each sum has not left the original set. This is possible with the help of a Cayley table. You may remember these as elementary school multiplication tables 😛 .
By inspecting this table, we can classify .
- Does it have closure? Yes. Every element in the table is a member of the original set.
- Does it have associativity? Yes. (This cannot be determined by the table alone, but is true on inspection).
- Does it have identity? Yes. The rows and columns associated with 0 express all elements of the set.
- Does it have inverse? Yes. The identity element appears in every row and every column.
- Does it have commutativity? Yes. The table is symmetric about the diagonal.
Therefore, is an abelian group.
An Example Using Roots of Unity
Definition 1. A group is said to be order if its underlying set has cardinality .
So is order 4. What other order-4 structures exist?
Consider the equation . Its solutions, or roots, is the set . This set is called the fourth roots of unity.
So what is the Cayley table of this set under multiplication ? In the following table, recall that , thus .
Something funny is going on. This table (and its colors) are patterned identically to ! Recall that a binary operation is just a function . Let’s compare the function maps of our two groups:
These two groups for structurally identical: two sides of the same coin. In other words, they are isomorphic, we write . Let us call this single structure .
But why are these examples of modular arithmetic and complex numbers equivalent?
One answer involves an appeal to rotational symmetry. Modular arithmetic is the mathematics of clocks: the hands of the clock rotating around in a circle. Likewise, if the reals are a number line, complex numbers are most naturally viewed as rotation on a number plane.
This rotation interpretation is not an accident. It helps use more easily spot other instances of . Consider, for instance, the following shape.
On this shape, the group of rotations that produce symmetry is . Inspection reveals that this, too, is isomorphic to !
Towards The Presentation Formalism
We describe as a cyclic group, for reasons that will become clear later.
Theorem 2. For every cyclic group , there exists some generator in its underlying set such that every other set element can be constructed by that generator.
Definition 3. When a generator has been identified, we can express a group’s underlying set with generator-dependent names. Two notation are commonly used in practice:
- In multiplicative notation, the elements are renamed , where r is any generator.
- Similarly, in additive notation, the elements become .
These two notation styles are interchangeable, and a matter of taste. In my experience, most mathematicians prefer multiplicative notation.
What generators exist in ? Let’s look at our three instantiations of this group:
- In modular arithmetic, you can recreate all numbers by . But you can also recreate them by .
- In complex numbers, you can visit all numbers by multiplying by , or multiplying by . Only fails to be a generator.
- In our rotation symmetry shape, two generators exist: clockwise rotation, and counterclockwise rotation.
For now, let’s rename all elements of to be .
Okay. But why is not a generator in ?
Theorem 4. For finite groups of order , each generator must be coprime to . That is, their greatest common divisor .
- not a generator in because it is a divisor of .
- What are the generators in ? All non-identity elements: .
- What are the generators in ? Only 1 and 5: .
We just spent a lot of words discussing generators. But why do they matter?
Generators are useful because they allow us to discover the “essence” of a group. For example, the Rubik’s cube has configurations. It would take a long time just writing down such a group. But it has only six generators (one for a rotation along each of its faces) which makes its presentation extremely simple.
Another way to think about it is, finding generators is a little bit like identifying a basis in linear algebra.
Towards Cayley Diagrams
Definition 5. We are used to specifying groups as set-operator pairs. A presentation is an generator-oriented way to specify the structure of a group. A relator is defined as constraints that apply to generators. A presentation is written
- In multiplicative notation: .
- In additive notation: .
The suffix is often left implicit from presentations (e.g., ) for the sake of concision.
Definition 6. A Cayley diagram is used to visualize the structure specified by the presentation. Arrow color represents the generator being followed.
Note that Cayley diagrams can be invariant to your particular choice of generator:
The shape of the Cayley diagram explains why is called a cyclic group, by the way!
With these tools in hand, let’s turn to more complex group structures.
Cyclic groups have rotational symmetry. Dihedral groups have both rotational and reflectional symmetry. The dihedral group that describes the symmetries of a regular n-gon is written . Let us consider the “triangle group” , generated by a clockwise rotation and a horizontal flip .
With triangles, we know that three rotations returns to the identity . Similarly, two flips returns to the identity . Is there some combination of rotations and flips that are equivalent to one another? Yes. Consider the following equality:
Analogously, it is also true that .
Definition 7. Some collection of elements is a generating set if combinations amongst only those elements recreates the entire group.
Cyclic groups distinguish themselves by having only one element in their generating set. Dihedral groups require two generators.
We can write each dihedral group element based on how it was constructed by the generators:
Alternatively, we can instead just write the presentation of the group:
We can visualize this presentation directly, or as a more abstract Cayley graph:
The Cayley table for this dihedral group is:
This shows that is not abelian: its multiplication table is not symmetric about the diagonal.
By looking at the color groupings, one might suspect it is possible to summarize this table with a table. We will explore this intuition further, when we discuss quotients.
Until next time.
- Finite groups can be analyzed with Cayley tables (aka multiplication tables).
- The same group can have more than one set-operation expressions (e.g., modular arithmetic vs. roots of unity vs. rotational symmetry).
- Generators, elements from which the rest of the set can be generated, are a useful way to think about groups.
- Group presentation is an alternate way to describing group structure. We can represent presentation visually with the help of a Cayley diagram.
- Cyclic groups (e.g., ) have one generator; whereas dihedral groups (e.g., ) have two.
- This post is based on Professor Macaulay’s Visual Group Theory lectures, which in turn is based on Nathan Carter’s eponymous textbook.
- Related to this style of teaching group theory are Dana Ernst’s lecture notes.
- If you want to see explore finite groups with software, Group Explorer is excellent.
- For a more traditional approach to the subject, these Harvard lectures are a good resource.