Groups — A Second Primer

The First Isomorphism Theorem

The meat of our last primer was a proof that quotient groups are well-defined. One important result that helps us compute groups is a very easy consequence of this well-definition.

Recall that if G,H are groups and \varphi: G \to H is a group homomorphism, then the image of \varphi is a subgroup of H. Also the kernel of \varphi is the normal subgroup of G consisting of the elements which are mapped to the identity under \varphi. Moreover, we proved that the quotient G / \ker \varphi is a well-defined group, and that every normal subgroup N is the kernel of the quotient map G \to G/N. These ideas work together to compute groups with the following theorem. Intuitively, it tells us that the existence of a homomorphism between two groups gives us a way to relate the two groups.

Theorem: Let \varphi: G \to H be a group homomorphism. Then the quotient G/ \ker \varphi is isomorphic to the image of \varphi. That is,

G/ \ker \varphi \cong \varphi(G)

As a quick corollary before the proof, if \varphi is surjective then H \cong G / \ker \varphi.

Proof. We define an explicit map f : G/ \ker \varphi \to \varphi(G) and prove it is an isomorphism. Let g \ker \varphi be an arbitrary coset and set f(g \ker \varphi) = \varphi(g). First of all, we need to prove that this definition does not depend on the choice of a coset representative. That is, if g \ker \varphi = g' \ker \varphi, then f(g) = f(g'). But indeed, f(g)^{-1}f(g') = f(g^{-1}g') = 1, since for any coset N we have by definition gN = g'N if and only if g^{-1}g' \in N.

It is similarly easy to verify that f is a homomorphism:

f((g \ker \varphi )(g' \ker \varphi)) = \varphi(gg') = \varphi(g)\varphi(g') = f(g \ker \varphi) f(g' \ker \varphi)

It suffices now to show that f is a bijection. It is trivially surjective (since anything in the image of \varphi is in a coset). It is injective since if f(g \ker \varphi) = 1, then \varphi(g) = 1 and hence g \in \ker \varphi, so the coset g \ker \varphi = 1 \ker \varphi is the identity element. So f is an isomorphism. \square

Let’s use this theorem to compute some interesting things.

Denote by D_{2n} the group of symmetries of the regular n-gon. That is, D_{16} is the symmetry group of the regular octagon and D_{8} is the symmetry group of the square (the 2n notation is because this group always has order 2n). We want to relate D_{16} to D_8. To do this, let’s define a homomorphism f:D_{16} \to D_8 by sending a one-eighth rotation \rho of the octagon to a one-fourth rotation of the square f(\rho) = \rho^2, and using the same reflection for both (f(\sigma) = \sigma). It is easy to check that this is a surjective homomorphism, and moreover the kernel is \left \{ 1, \rho^4 \right \}. That is, D_8 \cong D_{16}/ \left \{ 1, \rho^4 \right \}.

Here is a more general example. If G, H are groups of relatively prime order, then there are no nontrivial homomorphisms G \to H. In order to see this, note that |G/ \ker \varphi| = |G| / |\ker \varphi| as a simple consequence of Lagrange’s theorem. Indeed, by the first isomorphism theorem this quantity is equal to |\varphi(G)|. So |G| = | \ker \varphi| |\varphi(G)|. That is, the order of \varphi(G) divides the order of G. But it also divides the order of H because \varphi(G) is a subgroup of H. In other words, the order of \varphi(G) is a common factor of the orders of G and H. By hypothesis, the only such number is 1, and so |\varphi(G)| = 1 and \varphi(G) is the trivial group.

We will use the first isomorphism theorem quite a bit on this blog. Because it is such a common tool, it is often used without explicitly stating the theorem.

Generators

One extremely useful way to describe a subgroup is via a set of generators. The simplest example is for a single element.

Definition: Let G be a group and x \in G. Then the subgroup generated by x, denoted \left \langle x \right \rangle, is the smallest subgroup of G containing x. More generally, if S \subset G then the subgroup generated by S is the smallest subgroup containing S.

This definition is not quite useful, but the useful version is easy to derive. On one hand, the identity element must always be in \left \langle x \right \rangle. Since x \in \left \langle x \right \rangle and it’s a subgroup, we must have that x^{-1} \in \left \langle x \right \rangle. Moreover, all powers of x must be in the subgroup, as must all powers of the inverse (equivalently, inverses of the powers). In fact that is all that is necessary. That is,

\left \langle x \right \rangle = \left \{ \dots, x^{-2}, x^{-1}, 1, x, x^2, \dots \right \}

For finite groups, this list of elements will terminate. And in fact, the inverse of x will be a power of x as well. To see this, note that if we keep taking powers of x, eventually one of those will be the identity element. Specifically, some power of x must repeat, and if x^n = x^m then x^{n-m} = 1. Hence x^{-1} = x^{n-m-1}.

For subgroups generated by more than one element, these subgroups are more difficult to write down. For example, if x,y \in G then x,y may have a nontrivial relationship. That is, even though all possible products involving x and y are  in the subgroup, it is very difficult to determine whether two such products are the same (in fact, one very general formulation of this problem is undecidable!). Often times one can find a set of generators which generates the entire group G. In this case, we say G is generated by those elements.

A familiar example is the symmetry group of the square. As it turns out this group is generated by \rho, \sigma, where \rho is a quarter turn and \sigma is a reflection across some axis of symmetry. The relationship between the two elements is succinctly given by the equality \rho \sigma \rho \sigma = 1. To see this, try holding our your hand with your palm facing away; rotate your hand clockwise, flip it so your fingers are pointing left, rotate again so your fingers are pointing up, and then flip to get back to where you started; note that the two flips had the same axis of symmetry (the up-down axis). The other (obvious) relationships are that \rho^4 = 1 and \sigma^2 = 1. If we want to describe the group in a compact form, we write

G = \left \langle \rho, \sigma | \rho^4, \sigma^2, \rho \sigma \rho \sigma \right \rangle

This is an example of a group presentation. The left hand side is the list of generators, and the right hand side gives a list of relators, where each one is declared to be the identity element. In particular, the existence of a presentation with generators and relators implies that all possible relationships between the generators can be decuded from the list of relators (kind of like how all relationships between sine and cosine can be deduced from the fact that \sin^2(x) + \cos^2(x) = 1). Indeed, this is the case for the symmetry group (and all dihedral groups); there are only three distinct equations describing the behavior of rotations and reflections.

Here’s a quick definition we will often refer to in the future: a group is called cyclic if it is generated by a single element. Here are some interesting exercises for the beginning reader to puzzle over, which are considered basic facts for experienced group theorists:

  • Every subgroup of a cyclic group is cyclic.
  • There is only one infinite cyclic group: \mathbb{Z}.
  • Every finite cyclic group is isomorphic to \mathbb{Z}/n\mathbb{Z} for some n.

Finally, we will call a group finitely generated if it is generated by a finite set of elements and finitely presented if it has a presentation with finitely many generators and relators. Just to give the reader a good idea about how vast this class of groups is: many basic conjectured facts about finitely generated groups which have “only” one relator are still open problems. So trying to classify groups with two relators (or finitely many relators) is still a huge leap away from what we currently understand. As far as this author knows, this subject has been largely abandoned after a scant few results were proved.

Products and Direct Sums

Just as one does in every field of math, in order to understand groups better we want to decompose them into smaller pieces which are easier to understand. Two of the main ways to do this are via direct products and direct sums.

Definition: Let (G, \cdot_G),(H, \cdot_H) be groups. The product group G \times H is defined to have the underlying set G \times H (pairs of elements), and the operation is defined by entrywise multiplication in the appropriate group.

(g,h) \cdot (g', h') = (g \cdot_G g', h \cdot_H h')

Of course, one must verify that this operation actually defines a group according to the usual definition, but this is a simple exercise. One should note that there are two canonical subgroups of the direct product. Define by p_1 : G \times H \to G the projection onto the first coordinate (that is, (a,b) \mapsto a). This map is obviously a homomorphism, and its kernel is the subgroup of elements (1,h), h \in H. That is, we can identify H as a subgroup of G \times H. Identically, we see with p_2(a,b) = b that G is a subgroup of G \times H.

Note that this allows us to make some very weird groups. For instance, by induction a single direct product allows us to define products of arbitrarily many groups. Note that reordering the terms of such a product does not change the isomorphism class of the group (e.g. \mathbb{Z} \times D_8 \cong D_8 \times \mathbb{Z}). Additionally, there is nothing that stops us from defining infinite product groups. The elements of such a group are sequences of elements from the corresponding multiplicands. For example, the group \mathbb{Z} \times \mathbb{Z} \times \dots is the group of sequences of integers, where addition is defined termwise and the identity is the sequence of all zeroes.

Now infinite products can be particularly unwieldy, but we may still want to talk about groups constructed from infinitely many pieces. Although we have no motivation for this, one such example is the group of an elliptic curve. In order to tame the unwieldiness, we define the following construction which takes an infinite product, and allows only those elements which have finitely many non-identity terms.

Definition: Let G_{\alpha} be a family of groups. Define the direct sum of the G_{\alpha}, denoted by \bigoplus_{\alpha} G_{\alpha}, to be the subgroup of \prod_{\alpha} G_{\alpha} of elements (g_0, g_1, \dots) where all but finitely many g_i are the identity in the corresponding G_i.

[As a quick side note, this is mathematically incorrect: since the family of groups need not be countable, the g_i may not be enumerable. One can fix this by defining the elements as functions on the index set instead of sequences, but we are too lazy to do this.]

Note that we can define a direct sum of only finitely many groups, and for example this would be denoted G \oplus H, but finite sums are trivially the same as finite products. In fact, in this primer and all foreseeable work on this blog, we will stick to finite direct sums of groups, and implicitly identify them with direct products.

Finally, in terms of notation we will write G^n for a direct product of G with itself n times, and G^{\oplus n} for the direct sum of G with itself n times. As we just mentioned, these two are identical, so we will just default to the former for simplicity of reading.

One might wonder: why do we even distinguish these two constructions? The answer is somewhat deep, and we will revisit the question when in our future series on category theory. For now, we can simply say that the distinction is in the case of infinite products and infinite sums, which we won’t discuss anyway except for in passing curiosity.

The Classification of Finitely Generated Abelian Groups

Now we have finally laid enough groundwork to state the first big classification theorem of group theory. In words, it says that any finitely generated abelian group can be written as a direct sum of things isomorphic to \mathbb{Z} and \mathbb{Z}/n\mathbb{Z} for various choices of n. Moreover, the choices of n are related to each other.

In particular, the theorem is stated as follows:

Theorem: Let G be a finitely generated abelian group. Then G is isomorphic to a group of the form:

\displaystyle \mathbb{Z}^m \oplus \mathbb{Z}/p_1^{n_1}\mathbb{Z} \oplus \dots \oplus \mathbb{Z}/p_k^{n_k}\mathbb{Z}

Where p_i are (not necessarily distinct) primes. Moreover, G is completely determined by the choices of primes and exponents above.

In particular, we name these numbers as follows. The \mathbb{Z}^m part of the equation is called the free part, the exponent m is called the rank of G, and the numbers p_i^{n_i} are called the primary factors.

The proof of this theorem is beyond the scope of this blog, but any standard algebra text will have it. All we are saying here that every finitely generated abelian group can be broken up into the part that has infinite order (the free part) and the part that has finite order (often called the torsion part), and that these parts are largely disjoint from each other. For finite groups this is a huge step forward: to classify all finite groups one now only needs to worry about nonabelian groups (although this is still a huge feat in its own).

A quick application of this theorem is as follows:

Corollary: Let G be a finitely generated abelian group which has no elements of finite order. Then G has no nontrivial relators except for those enforcing commutativity.

Proof. Indeed, G \cong \mathbb{Z}^m for some m, and it has a presentation  \left \langle x_1, x_1, \dots, x_m | x_ix_jx_i^{-1}x_j^{-1}, i \neq j \right \rangle, which has no nontrivial relators. \square

Borrowing the free terminology, such groups without relators are called free abelian groups. Indeed, there are also nonabelian “free” groups, and this is the last topic we will cover in this primer.

Free Groups, and a Universal Property

Equivalently to “a group with no relators,” we can define a free group as a group which has presentation \left \langle x_{\alpha} \right \rangle for some potentially infinite family of elements x_{\alpha}. If the number of generators is finite, say there are n of them, then we call it the free group on n generators.

The interesting thing here is that all possible products of the generating elements are completely distinct. For example, the free group on two generators \left \langle a,b \right \rangle contains the elements ab, aba, abab, b^3a^{-5}b^2a, along with infinitely many others. The only way that two elements can be the same is if they can be transformed into each other by a sequence of inserting or deleting strings which are trivially the identity. For example, abb^{-1}a = a^2, but only because of our cancellations of bb^{-1} = 1, which holds in every group.

There is another way to get free groups, and that is by taking free products. In particular, the group \mathbb{Z} = \left \langle a \right \rangle is the free group on a single generator. Given two copies of \mathbb{Z}, we’d like to combine them in some way to get \left \langle a,b \right \rangle. More generally, given any two groups we’d like to define their free product G * H to be the group which contains all possible words using elements in G or H, which has no nontrivial relators, except for those already existing among the elements of G and H before taking a product.

Rigorously, this is very easy to do with group presentations. Give presentations for G = \left \langle x_i | r_j \right \rangle and H = \left \langle y_k | s_m \right \rangle, and define the free product by giving a presentation

G * H = \left \langle x_i, y_k | r_j, s_m \right \rangle

For instance, the free product \mathbb{Z}/3\mathbb{Z} * \mathbb{Z}/4\mathbb{Z} has presentation \left \langle a,b | a^3, b^4 \right \rangle. One interesting fact is that even if G,H are finite, as long as one is nontrivial then the free product will be an infinite group. Another interesting fact, which we’ll explore in future posts on category theory, is that the free product of groups is “the same thing” as the disjoint union of sets. That is, these two operations play the same role in their respective categories.

This “role” is called the universal property of the free product. We will use this directly in our post on the fundamental group, and in general it just says that homomorphisms provided on the two pieces of the free product extend uniquely to a homomorphism of the product. The simpler form is the universal property of the free group, which says that the free group is the “most general possible” group which is generated by these generators.

Theorem (Universal Property of the Free Group): Let S be a set of elements, and let F(S) be the free group generated by the elements of S. Then any set-function S \to G where G is a group extends uniquely to a group homomorphism F(S) \to G.

That is, deciding where the generators should go in G carries with it all of the information needed to define a homomorphism F(S) \to G, and it is uniquely determined in this way. To see this, simply see that once f(a), f(b) are determined, so are f(a^{-1}) = f(a)^{-1}, f(ab) = f(a)f(b), \dots

The corresponding property for free products is similar:

Theorem (Universal Property of the Free Product): Let G_{\alpha} be groups, and let f_{\alpha}: G_{\alpha} \to H be group homomorphisms. Then there is a unique group homomorphism from the free product of the G_{\alpha} to H, i.e. \ast_{\alpha} G_{\alpha} \to H.

The idea is the same as for the first universal property: the free product is the most general group containing the G_{\alpha} as subgroups, and so any group homomorphism from the product to another group is completely determined by what happens to each of the multiplicand groups.

Moreover, we can take a free product and add in extra relators in some reasonable way. This is called an amalgamated free product, and it has similar properties which we won’t bother to state here. The important part for us is that this shows up in topology and in our special ways to associate a topological space with a group.

After these two short primers, we have covered a decent chunk of group theory. Nevertheless, we have left out a lot of the important exercises and intuition that goes into this subject. In the future, we will derive group-theoretic propositions we need as we go (in the middle of other posts). On the other hand, we will continually use groups (and abelian groups, among others) as an example of a category in our exploration of category theory. Finally, when we study rings and fields we will first lay them out as abelian groups with further structural constraints. This will shorten our definitions to a manageable form.

Advertisements

10 thoughts on “Groups — A Second Primer

  1. This is the reason i hate Math. There is no real world application to apply these concepts. Or no one could explain more comprehensive the concepts ?

    Like

    • There are plenty of real-world applications of groups. As I said in the first primer on groups, any time you have symmetry (in ideas, shapes, anything) you can analyze that symmetry as a group. For instance, all crystallography is based on groups. Cryptography is a *huge* application of group theory (RSA and elliptic curve cryptography is all about groups). Want to try to “attack” a modern encryption scheme? You’re going to need to know a lot about groups.

      Groups show up in mathematical biology and mathematical chemistry. I interviewed at Goldman Sachs recently, and they asked me a question about arbitrage schemes. The punchline was that the symmetric group on n letters can be generated by just two elements (and that the set of all possible transactions form this group). They even show up in music (though it’d be dubious to say that groups have taught us anything new about music). And this is not to mention the absolute ubiquity of groups in mathematics, which gives second-hand applications of group theory.

      The reason you hate math is unlikely due to a lack of applications. It’s also unlikely that there’s nobody who can explain the applications. The reason you hate math is probably because it’s difficult and frustrating and it makes you feel stupid when you don’t understand it (I know, because I feel this every single day). Would you “hate” something which is completely useless, but easy to understand? I think that would warrant apathy, not hatred. But you could say this about any hard-to-learn skill. I “hate” physics because I’m not good at it and I wish I were but I don’t have enough time to study it, and what time I do have is wasted because I try to learn things too advanced that aren’t explained in terms of things I already understand.

      The whole point of this blog is to showcase applications of abstract mathematics to real world problems. If you can’t find anything here that makes you think math is useful, then you’re not looking hard enough (or I’m doing something seriously wrong).

      Like

      • Jeremy,

        Don’t bother with the haters. Keep up the good work. I was hoping to pick up some group theory for a long time and your posts made it possible.

        Can you elaborate on arbitrage schemes and their relation to group theory? I was unable to get the whole picture from your off-the-cuff description.

        Like

      • With some obvious assumptions: if you’re in a Forex market trading currency pairs, each possible transaction can be considered an element of a permutation group, and composing transactions should be equivalent to the composed transaction done as a single trade. If it’s not, there’s opportunity for arbitrage (trade one way and then reverse trade the other; the difference is profit). One might ask: how can one quickly check if the market has any opportunities for arbitrage? Put on the additional restriction that querying the market is expensive (which is true; travelling across the internet takes time) and you have a tricky-sounding problem.

        It’s quite easy to see that if there are more than two currencies being traded you can’t capture the entire market with a single transaction. Using group theory, it’s not hard to prove that you can do it with exactly two (one transposition and one n-cycle, the smallest generating set for the symmetry group on n letters).

        Like

  2. “One interesting fact is that even if G,H are finite, as long as one is nontrivial then the free product will be an infinite group.”

    Doesn’t that require them *both* to be non-trivial? For instance, if H = {e}, isn’t G ⋆ H ≅ G?

    Like

  3. the proof of 1st isomorphism thm seems to have typo: ”if g \ker \phi = g’ \ker \phi, then f(g) = f(g’) …” should be if g \ker \phi = g’ \ker \phi (same coset), then g^{-1}g’ \in \ker \phi since \ker \phi is normal. Then, \phi(g)=\phi(g’) by \phi is a homomorphism on G. Now by def of f,
    f(g \ker \phi)=f(g’ \ker \phi), i.e. f does not depend on the choice f rep ele of a coset gen by \ker \phi

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s