Group theory

Prerequisites: Basic concepts of abstract algebra, Permutations and arrangements

Introduction

Group theory mainly studies groups as algebraic structures.

To study the structure of groups, one needs some basic tools, including subgroups, group homomorphisms, and group actions. The groups most relevant to algorithm competitions are groups related to number theory (for example, the multiplicative group of integers modulo $n$, $(\mathbf Z/n\mathbf Z)^\times$) and permutation groups; this article focuses on the relevant concepts. Other parts of group theory not covered here, such as the structure theory of finite groups and the theory of linear representations of groups, are best pursued in specialist books.

Notation

When there is no risk of ambiguity, this article may write $g\cdot h$ as $gh$, and may write the group $(G,\cdot)$ simply as the group $G$.

Abstract algebra cannot be understood without examples. As an example for the concepts below, we discuss the spatial symmetry group $D_6$ of an equilateral triangle.

Example: the spatial symmetry group $D_6$ of an equilateral triangle

As shown in the figure, for a given equilateral triangle there are exactly six different operations that make it coincide with itself.

Here, let $r$ denote a clockwise rotation, and let $s$ denote reflection along the line from vertex $1$ to the center of the triangle. Operations are composed from right to left, so $sr$ means rotating first ($r$) and then reflecting ($s$). Two operations are different if and only if some vertex of the triangle ends up in different positions after the two operations.

Notation	Operation	Order	Permutation representation
$e$	Identity transformation, doing nothing	1	$(1)$
$r$	Clockwise rotation by $120^\circ$	3	$(123)$
$r^2$	Clockwise rotation by $240^\circ$	3	$(132)$
$s$	Reflection along the line from $1$ to the center	2	$(23)$
$sr$	Rotate by $120^\circ$ first, then reflect	2	$(13)$
$sr^2$	Rotate by $240^\circ$ first, then reflect	2	$(12)$

It is easy to verify that these operations do form a group. For example, the identity element of the group is $e$, and the inverse of $sr$ is itself. Moreover, $D_6$ is not an abelian group; for instance, one can directly verify that $rs=sr^{-1}$.

The operations recorded in the table are not the only symmetry operations represented by the corresponding notation. For example, reflection along the line from $2$ to the center is also a symmetry operation of the triangle. It is not in the table, but its result is the same as that of “rotate by $120^\circ$ first, then reflect”. The concepts of “order” and “permutation representation” in the table will be explained below.

Subgroups

To understand the structure of a given group, one can first analyze its substructures. A substructure of a group is a subset of the group that is still a group under the same operation. This gives the following definition.

Subgroup

For a group $(G,\cdot)$ and a subset $H\subseteq G$, if $(H,\cdot)$ is also a group, then $H$ is called a subgroup of $G$, written $H\le G$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

In $D_6$, it is easy to verify that its subgroups are $\{e\}$, $\{e,s\}$, $\{e,sr\}$, $\{e,sr^2\}$, $\{e,r,r^2\}$, and $D_6$ itself, six in total. Apart from $D_6$, these subgroups have simpler structures and contain some information about the original group.

To determine whether a given subset $H\subseteq G$ is a subgroup, it is not necessary to verify the group axioms one by one: associativity holds automatically. It is enough for the subset to be closed under the binary operation, contain the identity, and be closed under taking inverses. In fact, these conditions can be summarized as follows.

Theorem (subgroup test)

A subset $H$ of a group $G$ is a subgroup if and only if $g^{-1}h\in H$ for all elements $g,h \in H$.

Subgroups generated by subsets

In general, given a subset $S$ of a group $G$, the set of all results obtainable by starting with elements of $S$ and repeatedly applying multiplication and inversion finitely many times is a subgroup of $G$. This is called the subgroup generated by $S$.

Subgroup generated by a subset

For a group $G$ and a nonempty subset $S\subseteq G$, if $H$ is the smallest subgroup of $G$ (under inclusion) that contains $S$, then $H$ is called the subgroup generated by the subset $S$, written $\langle S\rangle$. In particular, if $S=\{x\}$ is a singleton, then $\langle S\rangle$ is also written $\langle x\rangle$ and is called the cyclic subgroup of the powers of $x$.

It can be proved that such a subgroup always exists for every such subset $S$: $\langle S\rangle$ can be constructed as the intersection of all subgroups of $G$ containing $S$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

In $D_6$, choose the rotation $r$ and repeatedly apply it and its inverse. This gives the subgroup $\{e,r,r^2\}$, which can be written as $\langle r\rangle$. Every nontrivial subgroup of $D_6$ can be generated by choosing a suitable operation.

Some subsets generate the group itself. Such subsets are especially important and are called generating sets of the group.

Generating set of a group

If a subset $S\subseteq G$ of a group $(G,\cdot)$ satisfies $\langle S\rangle=G$, then $S$ is called a generating set of $G$. The elements in the generating set $S$ are called generators.

The group itself is a trivial generating set of itself. More interesting are cases where the generating set is much smaller than the group.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

One can verify that $D_6=\langle s,r\rangle$. That is, every symmetry operation of the equilateral triangle can be obtained by composing rotations and reflections.

Cyclic groups

The structure of a group generated by a single element is very simple. Such a group is called a cyclic group.

Cyclic group

For a group $G$, if there exists $x\in G$ such that $G=\langle x\rangle$, then $G$ is called a cyclic group.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

All nontrivial subgroups of $D_6$, as well as $\{e\}$, are cyclic groups.

It can be proved that the structure of a cyclic group is uniquely determined by its size. If a cyclic group is infinite, it necessarily has the same group structure as the additive group of the integers $(\mathbf Z,+)$, written $C_\infty$ or $\mathbf Z$. Otherwise, if the number of elements of the group is $n\in\mathbf N_+$, it necessarily has the same group structure as the additive group $(\mathbf Z/n\mathbf Z,+)$ of congruence classes modulo $n$, written $C_n$ or $\mathbf Z_n$. A rigorous statement of this result requires the concept of group isomorphism introduced below, which precisely describes the fact that two groups have the same structure.

Classification theorem for cyclic groups

A finite cyclic group $G$ of size $n$ is isomorphic to $C_n$; an infinite cyclic group $G$ is isomorphic to $C_\infty$.

Proof

Given a cyclic group $G=\langle x\rangle$, it can always be written as $G=\{x^n:n\in\mathbf Z\}$. If $G$ is finite, there must be natural numbers $n<m$ such that $x^n=x^m$; by cancellation, $x^{m-n}=e$. Now take the smallest positive integer $n\in\mathbf N_+$ such that $x^n=e$. Then the sequence $\{x^k\}$ is periodic with period $n$, and the elements within one period are all distinct (otherwise the minimality of $n$ would be violated). The map $x^k\mapsto\bar k$ therefore gives an isomorphism $G\rightarrow\mathbf Z/n\mathbf Z$, that is, $G\cong C_n$. Conversely, if $G$ is infinite, all elements of $G$ are distinct, and the map $x^k\mapsto k$ gives an isomorphism $G\rightarrow\mathbf Z$, that is, $G\cong C_\infty$.

All cyclic groups are Abelian groups. The example $D_6$ in this article shows that even if all nontrivial subgroups of a group are cyclic, the group itself need not be Abelian.

Order

The order of a group is the number of elements in the group. The order of a given element in a group is the order of the cyclic subgroup generated by that element. Thus we have the following definitions:

Order of a group

The order of a group $G$ is its number of elements, written $|G|$. The order of an infinite group is also infinite.

Order of an element

The order of an element $x\in G$ in a group $G$ is the smallest positive integer $n$ such that $x^n=e$, written $|x|$. If no such $n$ exists, the order of $x$ is called infinite and written $|x|=\infty$.

The order of an element is never greater than the order of the group; in fact, as will be proved below, the order of an element always divides the order of the group. However, the order of a group is not always the maximum order of its elements. For example, $D_6$ is a group of order six, but the maximum order of an element is $3$. Nor is the order of a group always the least common multiple of the orders of all its elements. For example, the order of the Klein four-group¹ $V_4$ is $4$, but it contains only elements of orders $1$ and $2$.

Theorem

In the finite cyclic group $C_n=\langle x\rangle$, the order of the element $x^k$ is

$$\frac{n}{\gcd(k,n)}.$$

In particular, the number of generators of $C_n$ is $\varphi(n)$, where $\varphi(\cdot)$ is the Euler totient function.

As an application of the discussion above, note that the order of the multiplicative group of integers modulo $n$ is $\varphi(n)$. The order of every element $a$ in this group divides it, so necessarily $a^{\varphi(n)}=1$. This is Euler's theorem, because the elements of this group are precisely the integers relatively prime to $n$.

Cosets

The elements outside a subgroup are not structurally disorganized within the group either.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

Consider the subgroup $\langle r\rangle$ in $D_6$. The remaining elements $\{s,sr,sr^2\}$ have a structure very similar to $\langle r\rangle$: each operation in this set can be obtained by composing $s$ with an operation in $\langle r\rangle$. Similarly, consider the subgroup $\langle s\rangle$. The remaining elements of the group can be divided into two classes, $\{r,sr\}$ and $\{r^2,sr^2\}$, which can be obtained by composing the elements of $\langle s\rangle$ with $r$ and $r^2$, respectively. This phenomenon is general.

Given a subgroup, one can define its cosets.

Cosets

Let $G$ be a group and let $H\le G$ be a subgroup. The left coset and right coset of $H$ containing $g$ are respectively defined as

$$\begin{aligned} gH &= \{gh:h\in H\},\\ Hg &= \{hg:h\in H\}. \end{aligned}$$

An element in a coset is called a representative element of the coset.

The subgroup itself is also one of its cosets. Given a subgroup, all its cosets form a partition of the group; that is, the group is the disjoint union of all the cosets. A partition can always be viewed as the set of equivalence classes of some equivalence relation. For the partition into left cosets, this relation is $g_1\sim g_2$ if and only if $g_1^{-1}g_2\in H$; for the partition into right cosets, it is $g_1\sim g_2$ if and only if $g_1g_2^{-1}\in H$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

In the language of cosets, the example above says that $D_6$ can be partitioned as $\langle r\rangle\cup s\langle r\rangle$ and as $\langle s\rangle\cup \langle s\rangle r \cup \langle s\rangle r^2$. The former partitions the group into left cosets, while the latter partitions it into right cosets. It is worth noting that the choice of representative is not special; for example, one can verify that $s\langle r\rangle=sr\langle r\rangle$. Every element in a coset is a representative of that coset.

Different cosets of the same subgroup all have the same size, equal to the size of the corresponding subgroup. Since all cosets of a given subgroup form a partition of the group, the order of a finite group must be an integer multiple of the order of the subgroup. This is Lagrange's theorem.

Lagrange's theorem

For a finite group $G$ and a subgroup $H\le G$, $|G|=[G:H]|H|$, where $[G:H]$ denotes the number of left (or right) cosets of $H$ in $G$, called the index of $H$ in $G$.

Proof

Consider left multiplication by $g$, the map $h\mapsto gh$. It and the map $h\mapsto g^{-1}h$ are inverse maps, so both are bijections. Thus $|H|=|gH|$ always holds.

Since the order of an element is the order of the cyclic subgroup generated by it, the order of an element must also divide the order of the group.

Normal subgroups

In general, the left and right cosets of a given subgroup are not the same.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

In $D_6$, $\langle s\rangle r=\{r,sr\}$, whereas $r\langle s\rangle=\{r,sr^2\}$. However, if we consider the subgroup $\langle r\rangle$, the left and right cosets are always the same, because the group then has only two cosets and the subgroup, being one of the cosets, must coincide with itself.

Whether the left and right cosets are the same reflects a property of the corresponding subgroup.

Normal subgroup

Let $N\le G$ be a subgroup of a group $G$. If $ghg^{-1}\in N$ for every $h\in N$ and $g\in G$, or equivalently, $gNg^{-1}\subseteq N$ for every $g\in G$, then $N$ is called a normal subgroup of $G$, written $N\trianglelefteq G$.

The condition in this definition is equivalent to $gN=Ng$ always holding. Every group $G$ has the trivial normal subgroups $\langle e\rangle$ and $G$ itself.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

In the group $D_6$, $\langle s\rangle$ is not a normal subgroup, whereas $\langle r\rangle$ is a normal subgroup.

Quotient groups

Normal subgroups are an especially important class of subgroups, one reason being that quotient groups can be defined from them.

For a group $G$ and a normal subgroup $N\trianglelefteq G$, consider the set of all cosets

$$G/N = \{gN:g\in G\}.$$

The left and right cosets are now equal, so there is no need to distinguish them. Starting from the operation in $G$, define a binary operation $\circ$ on $G/N$ by

$$g_1N\circ g_2N=(g_1g_2)N.$$

It can be proved that the result of the operation is independent of the choice of representatives². Then $(G/N,\circ)$ indeed has a group structure, and is called the quotient group of $G$ modulo $N$. The quotient group $G/N$ is not a subgroup of $G$; each of its elements is a subset of $G$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

In $D_6$, the meaning of the quotient group $G/\langle r\rangle$ is particularly clear. It amounts to ignoring, among all these symmetry operations, the angle through which the triangle is rotated and considering only whether the triangle is flipped. The composition of two operations that flip the triangle is equivalent to not flipping the original triangle; if one operation flips the triangle and the other does not, their composition must flip it. The property of whether or not the triangle is flipped also has a group structure. Algebraically, ignoring the details of rotation in $D_6$ and considering only whether there is a flip is quotienting the complicated group $D_6$ by $\langle r\rangle$, producing the quotient group $D_6/\langle r\rangle$. These statements do not work for the subgroup $\langle s\rangle$, because if we ignore whether the triangle is flipped, there is no way to determine the rotation angle; this is why $G/\langle s\rangle$ does not have the structure of a quotient group.

The quotient group of a group can simplify a complicated group, allowing us to observe part of its structure in order to understand the original group. This is why quotient groups are also called factor groups. A group with no normal subgroups other than the trivial normal subgroups is called a simple group; such groups cannot be simplified into smaller groups. Like prime numbers, they are the building blocks of more complicated group structures.

Group homomorphisms

A second way to understand the structure of a given group is to compare the structures of two groups.

To compare two groups structurally, one constructs a map between them. However, such a map cannot be arbitrary: it must preserve the group structure, that is, keep the group operation consistent before and after mapping. Such a map is called a group homomorphism.

Group homomorphism

Let $\varphi:G\rightarrow H$ be a map from the group $(G,\cdot)$ to the group $(H,\odot)$. If $\varphi$ preserves the group operation, meaning that $\varphi(g_1\cdot g_2)=\varphi(g_1)\odot\varphi(g_2)$ for all $g_1,g_2\in G$, then $\varphi$ is called a homomorphism from $G$ to $H$.

A group homomorphism necessarily maps the identity to the identity and maps inverses to inverses.

Notation

Below, when there is no risk of ambiguity, we will not distinguish the operation symbols in $G$ and $H$, and will omit them for concision.

Group isomorphisms

Given a homomorphism $\varphi:G\rightarrow H$ from $G$ to $H$, a natural question is to what extent this homomorphism $\varphi$ reflects the fact that $G$ and $H$ have the same structure. For this purpose, consider the image $\varphi(G)$ of $G$ under $\varphi$, which maps the structure of $G$ into $H$. On the one hand, $\varphi(G)$ is a subgroup of $H$; but if $\varphi$ is not surjective, $\varphi(G)$ is not the same as $H$. On the other hand, $\varphi$ need not be injective; if it is not injective, $\varphi(G)$ reflects only part of the structure of $G$. Only when $\varphi$ is bijective are the structures of $G$ and $H$ completely identical. This special kind of group homomorphism is called a group isomorphism.

Group isomorphism

Let $\varphi:G\rightarrow H$ be a homomorphism from $G$ to $H$. If $\varphi$ is bijective, then $\varphi$ is called an isomorphism between $G$ and $H$, written $G\cong H$.

Two isomorphic groups have exactly the same structure. If we care only about group structure, there is no need to distinguish isomorphic groups. The classification theorem for cyclic groups above was stated in terms of isomorphism.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

Returning to the earlier example, each symmetry operation of the equilateral triangle corresponds uniquely to a permutation of the set of vertices. All permutations of the vertex set also form a group, namely $S_3$. It is easy to verify that the resulting map $\varphi:D_6\rightarrow S_3$ is a group homomorphism; moreover, it is a group isomorphism. Thus $D_6\cong S_3$. In fact, up to isomorphism, a group of order six is either $C_6$ or $S_3$ (the proof is given below).

Classifying the structures of finite groups of a given order is an important topic in group theory, but it is beyond the scope of this article.

The kernel of a homomorphism

For a general homomorphism, one can further ask how much information about the group structure is lost in the homomorphism. Continuing with the notation above, we know that $\varphi(G)$ is a subgroup of $H$. The key question is now the relationship between $\varphi(G)$ and $G$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

Consider the map $\varphi: D_6 \rightarrow C_2 = \langle x\rangle$ defined by

$$\varphi(e)=\varphi(r)=\varphi(r^2)=e,\ \varphi(s)=\varphi(sr)=\varphi(sr^2)=x.$$

It is easy to verify that $\varphi$ is a group homomorphism; it is surjective but not injective. Its meaning is clear: every symmetry operation of the group is mapped to whether or not it includes a flip. The information about the rotation angle in $D_6$ is what this homomorphism compresses. For example, without a flip, a rotation by any angle is mapped to the identity element of $C_2$.

This example suggests using the preimage of $\{e\}$ to measure the structural information lost in a homomorphism. This gives the following definition.

Kernel of a homomorphism

Let $\varphi:G\rightarrow H$ be a homomorphism from $G$ to $H$. The kernel of $\varphi$ is $\ker\varphi=\{g\in G:\varphi(g)=e\}$, where $e$ is the identity element of $H$.

Fundamental theorem of group homomorphisms

The kernel $\ker\varphi$ does indeed characterize the structural information lost in a group homomorphism. The precise statement is the fundamental theorem of group homomorphisms (also called the first isomorphism theorem).

Fundamental theorem of group homomorphisms (first isomorphism theorem)

Let $\varphi:G\rightarrow H$ be a homomorphism from $G$ to $H$. Then $\ker\varphi\trianglelefteq G$, and $G/\ker\varphi\cong\varphi(G)\le H$.

Proof

First, $N=\ker\varphi$ is a normal subgroup, because for any $h\in N$ we have $\varphi(ghg^{-1})=\varphi(g)\varphi(h)\varphi(g)^{-1}=\varphi(g)\varphi(g)^{-1}=e$, so $ghg^{-1}\in\ker\varphi$. Next, consider the map $\Phi:G/N\rightarrow\varphi(G)$ satisfying $\Phi(gN)=\varphi(g)$. The map is well-defined, because if $g_1N=g_2N$, then $g_1^{-1}g_2\in N$, so $\varphi(g_1^{-1}g_2)=e$, which means $\varphi(g_1)=\varphi(g_2)$. The map $\Phi$ is clearly surjective; it is also injective because $\ker\Phi=\{gN:\varphi(g)=e\}=\{N\}$. Thus $\Phi$ is a group isomorphism. Finally, $\varphi(g_1)\varphi(g_2)^{-1}=\varphi(g_1g_2^{-1})\in\varphi(G)$, so by the subgroup test, $\varphi(G)$ must be a subgroup.

Corollary

The homomorphism $\varphi:G\rightarrow H$ is injective if and only if $\ker\varphi=\{e\}$. In this case, $G$ is isomorphic to a subgroup of $H$, namely $G\cong\varphi(G)\le H$.

In other words, the kernel $\ker\varphi$ of $\varphi$ is a normal subgroup of $G$; the quotient group $G/\ker\varphi$ is isomorphic to the image $\varphi(G)$ of the homomorphism, and this image is a subgroup of $H$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

The kernel of the homomorphism $\varphi: D_6 \rightarrow C_2$ given above is $\langle r\rangle$. As already explained in the discussion of normal subgroups, $D_6/\langle r\rangle$ is indeed isomorphic to $C_2$.

Natural homomorphisms

This conclusion is not surprising. When constructing the homomorphism $\varphi: D_6 \rightarrow C_2$, we used precisely the geometric meaning of the quotient group $D_6/\langle r\rangle$. This phenomenon is common. In fact, for every quotient group, one can construct a group homomorphism whose image is isomorphic to the given quotient group.

Natural homomorphism

For a group $G$ and a normal subgroup $N\trianglelefteq G$, the map $\pi: G\rightarrow G/N$ given by $\pi(g)=gN$ is a surjective homomorphism from $G$ to $G/N$, called the natural homomorphism or natural map from $G$ to the quotient group $G/N$.

This also shows that for every normal subgroup of a given group, there is a corresponding group homomorphism whose kernel is exactly that normal subgroup. The fundamental theorem of group homomorphisms above says that the kernel of every homomorphism is a normal subgroup. Thus, normal subgroups and kernels of homomorphisms are two sides of the same coin.

Using the concept of the natural map, the fundamental theorem of group homomorphisms can in fact be expressed by the following commutative diagram.

Here, all arrows are group homomorphisms, $N=\ker\varphi$ is the kernel of $\varphi$, and $\varphi(G)$ is the image of $\varphi$. The maps, in order, are $\pi:g\mapsto gN$, the natural map from $G$ to $G/N$ (a surjective homomorphism); $\Phi:gN\mapsto\varphi(g)$, an isomorphism; and $\iota$, an embedding (an injective homomorphism). The commutativity means that the compositions of the two different paths from $G$ to $H$ in the diagram give the same result, namely $\varphi=\iota\circ\Phi\circ\pi$. The diagram clearly shows that the information lost by $\varphi$ is reflected in $\pi$ and $\iota$.

Isomorphism theorems for groups

A powerful tool for understanding group structure is the collection of isomorphism theorems. The first isomorphism theorem was already given above. For completeness, here are some other common isomorphism theorems.

The second isomorphism theorem involves the product of subgroups.

Product of subsets

For a group $G$ and subsets $A,B\subseteq G$, the product of $A$ and $B$ is the subset $AB=\{ab:a\in A,b\in B\}$.

The product of subgroups is not always a subgroup. For example, in $D_6$, let $A=\langle s\rangle$ and $B=\langle sr\rangle$. Their product is $AB=\{e,s,r,sr\}$, which is not a subgroup of $G$, because $(sr)s=r^2\notin AB$. In fact, a counterexample of the form $a\in A$, $b\in B$, but $ba\notin AB$ is precisely the fundamental reason that the product is not a subgroup. The following theorem addresses this.

Theorem

For a group $G$ and subgroups $A,B\le G$, the product $AB$ is a subgroup if and only if $AB=BA$.

Proof

If the product $AB$ is a subgroup, then for every $a\in A$ and $b\in B$, $ba=(a^{-1}b^{-1})^{-1}\in AB$, so $BA\subseteq AB$. Conversely, if $AB=BA$, then for any $a_1,a_2\in A$ and $b_1,b_2\in B$, $(a_1b_1)(a_2b_2)^{-1}=a_1b_1b_2^{-1}a_2^{-1}\in a_1BA=a_1AB=AB$. Therefore, by the subgroup test, $AB$ must be a subgroup.

The second isomorphism theorem (a.k.a. the diamond isomorphism theorem) gives a simpler sufficient condition under which a product of subgroups is still a subgroup, and further determines its structure.

Second isomorphism theorem

Let $G$ be a group and $A,B\le G$ be subgroups satisfying $A\le N_G(B)$. Then $AB\le G$, $B\trianglelefteq AB$, $A\cap B\trianglelefteq A$, and $AB/B\cong A/(A\cap B)$. Here, $N_G(B)$ is the normalizer of $B$. In particular, a sufficient condition for $A\le N_G(B)$ is $B\trianglelefteq G$.

Proof

Since $A\le N_G(B)$, we have $aBa^{-1}=B$ for every $a\in A$, which is equivalent to $aB=Ba$. Therefore $AB=BA$, so the theorem above shows that $AB$ is a subgroup. As a subgroup of $AB$, the subgroup $B$ has equal left and right cosets, so $B\trianglelefteq AB$.

Consider the map $\varphi:A\rightarrow AB/B$ satisfying $\varphi(a)=aB$. It is surjective, and its kernel is $\ker\varphi=\{a\in A:aB=B\}=A\cap B$. The result follows from the fundamental theorem of group homomorphisms.

The third isomorphism theorem gives the correspondence between normal subgroups and quotient groups of a quotient group and normal subgroups and quotient groups of the original group. It explains why the idea of decomposing a quotient group further is valid.

Third isomorphism theorem

Let a group $G$ have normal subgroups $H,K\trianglelefteq G$ with $H\le K$. Then $K/H\trianglelefteq G/H$, and $(G/H)/(K/H)\cong G/K$.

Proof

Consider the map $\varphi:G/H\rightarrow G/K$ satisfying $\varphi(gH)=gK$. It is a surjective group homomorphism, and $\ker\varphi=\{gH:g\in K\}=K/H$. The result follows from the fundamental theorem of group homomorphisms.

This result can be extended to the fourth isomorphism theorem, also called the correspondence theorem, which further gives a correspondence between the subgroup lattice of a group and the subgroup lattice of a quotient group.

Correspondence theorem

Let a group $G$ have a normal subgroup $N\trianglelefteq G$. Then there is a bijection $\varphi:\mathcal H\rightarrow\mathcal S$ between the subgroups $\mathcal H=\{H:N\subseteq H\subseteq G\}$ of $G$ containing $N$ and the subgroups $\mathcal S=\{S:S\le G/N\}$ of the quotient group $G/N$, mapping $H\in\mathcal H$ to $H/N\in\mathcal S$. This bijection preserves inclusion between subgroups, and normal subgroups of $G$ are always mapped to normal subgroups of $G/N$.

About the isomorphism theorems

The content and names of the isomorphism theorems for groups may differ between textbooks. Here we use one common version.Wikipedia summarizes the differences in content and naming among common textbooks.

Group actions

A third way to understand the structure of a given group is to examine its action on a set.

For example, the spatial symmetry group of the equilateral triangle discussed in this article is defined through the action of its elements (the symmetry operations) on the triangle. Likewise, the symmetric group $S_M$ can be defined through the action of its elements on the set $M$. Here, an action means that each element of the group corresponds to a permutation of a set.

Group action on a set

For a group $G$, a set $X$, and a map $G\times X\rightarrow X$, write the image of $(g,x)$ under the map as $g\cdot x$. If the map satisfies $g_1\cdot(g_2\cdot x)=(g_1g_2)\cdot x$ and $e\cdot x=x$ for all $g_1,g_2\in G$ and $x\in X$, then it is called a group action of $G$ on $X$.

“Left action” and “right action”

The definition of group action used here is called a left action in some sources³, because in the notation $g\cdot x$, the group element is written to the left of the element of the set. Accordingly, when the product $g_1g_2$ of group elements acts on the set, the action of $g_2$ must be performed first, followed by the action of $g_1$. One can of course define a right action analogously, written $x\cdot g$. In that case, the order of composition of group elements is reversed from a left action: $x\cdot (g_1g_2)=(x\cdot g_1)\cdot g_2$. The two differ only in notation and not in substance, so this article uses left-action notation by default.

For a group action satisfying the definition above, we naturally obtain the following construction

$$\begin{aligned} \varphi:{\color{Maroon}{G}}\rightarrow {\color{Orchid}{S_X}}&\\ {\color{Maroon}{g}}\mapsto {\color{Orchid}{\varphi_g}}&: {\color{RoyalBlue}{X}}\rightarrow{\color{YellowGreen}{X}}\\ &\quad {\color{RoyalBlue}{x}}\mapsto {\color{YellowGreen}{g\cdot x}}. \end{aligned}$$

This map assigns to every element $g$ of $G$ a permutation $\varphi_g$ of the set $X$, and the permutation $\varphi_g$ maps $x$ to $g\cdot x$.

By definition, the bijection $\varphi_e$ corresponding to the identity element $e$ of the group is the identity map on $X$. The map $\varphi_g$ corresponding to $g$ and the map $\varphi_{g^{-1}}$ corresponding to its inverse $g^{-1}$ are inverse maps (which also explains why $\varphi_g$ is always bijective). One can verify that $\varphi_{g_1g_2}=\varphi_{g_1}\varphi_{g_2}$, so $\varphi$ is a group homomorphism from $G$ to $S_X$.

This group homomorphism $\varphi$ is called the permutation representation of the group action; it maps $G$ into a permutation group.

Permutation group

If a group $G$ is a subgroup of some symmetric group, then $G$ is called a permutation group.

The kernel of this group homomorphism is also called the kernel of the group action. If the kernel is trivial, meaning that the homomorphism is injective, then the group action is called faithful: its permutation representation faithfully reflects information about the group structure. In this case, $G$ is isomorphic to the permutation group obtained from its permutation representation.

Notation

For convenience, the $\cdot$ symbol in group actions will be omitted below.

Orbits

A group action is a binary map. Fixing an element $g$ of the group gives a permutation $\varphi_g$ of the set. Fixing an element $x$ of the set instead gives all possible results of the group acting on that element.

Orbit

For an action of a group $G$ on a set $X$ and $x\in X$, the orbit of $x$ under the action of $G$ is the subset $Gx=\{gx:g\in G\}$.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

For example, consider the action of $\langle s\rangle\le D_6$ on the set of vertices of an equilateral triangle. The orbit of vertex $1$ is $\{1\}$, while the orbits of vertices $2$ and $3$ are $\{2,3\}$. By contrast, the action of $\langle r\rangle\le D_6$ on the vertex set has only one orbit, namely the entire vertex set.

It is easy to prove that under the action of $G$, all orbits of $X$ form a partition of the set, written $X/G$. Unlike cosets, however, these orbits do not necessarily have equal sizes.

Stabilizers

Under a group action, the length of the orbit of an element of the set depends on how many group elements correspond to permutations that fix it.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

For example, the orbit of vertex $1$ under the action of $\langle s\rangle\le D_6$ has length one because every element of the group maps vertex $1$ to itself. The orbit of vertex $2$ has length two because only the identity element $e$ maps vertex $2$ to itself.

This motivates the following definition.

Stabilizer

For an action of a group $G$ on a set $X$ and $x\in X$, the stabilizer of $x$ in $G$ is the subgroup $G_x=\{g\in G:gx=x\}$.

The kernel of a group action is the intersection of the stabilizers of all elements of the set.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

Consider the action of $D_6$ on the vertex set. The stabilizer of vertex $1$ is $\{e,s\}=\langle s\rangle$. This is a subgroup of $D_6$. Since $D_6$ can be partitioned into the left cosets $\langle s\rangle$, $r\langle s\rangle$, and $r^2\langle s\rangle$, it is easy to see that every left coset produces the same result when acting on vertex $1$.

This example shows that the elements in an orbit correspond one-to-one with the left cosets of the stabilizer. This gives the following result.

Theorem

For an action of a group $G$ on a set $X$, the stabilizer $G_x$ of an element $x\in X$ is a subgroup of $G$, and the left cosets of $G_x$ are in bijection with the orbit $Gx$.

Proof

It suffices to verify that the map $gG_x\mapsto gx$ is a well-defined bijection.

Lagrange's theorem connects the length of an orbit with the number of cosets of the stabilizer. This is the orbit-stabilizer theorem.

Orbit-stabilizer theorem

For an action of a finite group $G$ on a set $X$ and $x\in X$, $|Gx|=[G:G_x]=|G|/|G_x|$.

This conclusion can be verified in the example above.

Burnside's lemma

This lemma gives a formula for the number of orbits of a group action.

Burnside's lemma

For an action of a group $G$ on a set $X$, the number of orbits equals the average number of fixed points of the permutations corresponding to the elements of the group, namely

$$|X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|.$$

Here, $X^g=\{x\in X:gx=x\}$ is the set of fixed points of the permutation corresponding to $g\in G$.

Proof

The proof of this theorem is very short. Notice that the number of orbits can be written as

$$|X/G|=\sum_{o\in X/G}1=\sum_{x\in X}\frac{1}{|Gx|}=\frac1{|G|}\sum_{x\in X}|G_x|.$$

The last equality is the preceding corollary; the right-hand side differs from the expression to be proved only by a Fubini theorem, because both sums count the set $\{(g,x)\in G\times X:gx=x\}$, with the right-hand side summing over $g$ first and the target expression summing over $x$ first.

This theorem has many uses in combinatorics and can be used to count objects that are “essentially different”. For more examples and discussion, see Pólya enumeration.

Cayley's theorem

To study group structure using group actions, one needs to choose a suitable set. In fact, the group itself is such a set. We therefore consider two common actions of a group on itself and use them to analyze the group structure.

The first is the left multiplication action of the group on itself. Its permutation representation is

$$\begin{aligned} \varphi:G\rightarrow S_G&\\ g\mapsto \varphi_g&: G\rightarrow G\\ &\quad x\mapsto gx \end{aligned}$$

The left multiplication action of a group is necessarily faithful because groups satisfy cancellation. Thus, by the fundamental theorem of group homomorphisms, $G$ can be embedded into the symmetric group $S_G$. This means that every group is isomorphic to some permutation group⁴.

Cayley's theorem

A group $G$ is isomorphic to a subgroup of the symmetric group $S_G$.

This group action has only one orbit, and the stabilizer of every element is $\{e\}$.

Conjugation action

The second action of a group on itself is called the conjugation action. Its permutation representation is

$$\begin{aligned} \varphi:G\rightarrow S_G&\\ g\mapsto \varphi_g&: G\rightarrow G\\ &\quad x\mapsto gxg^{-1} \end{aligned}$$

Under the conjugation action of a group, orbits and stabilizers have special names.

Conjugacy class

For a group $G$ and $g\in G$, the conjugacy class of $g$ in $G$ is the orbit of $g$ under the conjugation action. If elements $g$ and $h$ lie in the same conjugacy class, then $g$ and $h$ are said to be conjugate.

Centralizer

For a group $G$ and $a\in G$, the centralizer of $a$ in $G$ is $C_G(a)=\{g\in G:ga=ag\}$.

Center

For a group $G$, with $a$ as the dummy variable, the center is $Z(G)=\cap_{a\in G}C_G(a)=\{g\in G:\forall a\in G(ga=ag)\}$.

The center of a group is the set of elements that commute with every element of the group; because it is the kernel of a group action, it must be a normal subgroup. The size of the center indicates how far the group is from being abelian. The centralizer of a given element is the set of all elements that commute with that element; it is also the largest among the subgroups whose centers contain that element, which explains its name. At the same time, because it is the stabilizer of an element under the conjugation action, it is a subgroup. A conjugacy class is generally not a subgroup.

Example: the spatial symmetry group $D_6$ of an equilateral triangle (continued)

Returning to $D_6$, its center is $\{e\}\neq G$, showing that it is not an abelian group. The centralizer of $r$ is $C_G(r)$, namely $\langle r\rangle$, and the centralizer of $s$ is $C_G(s)$, namely $\langle s\rangle$. In general, $\langle g\rangle\le C_G(g)$ for every $g\in G$. The group $D_6$ has three conjugacy classes, namely $\{e\},\{r,r^2\},\{s,sr,sr^2\}$. It is easy to see that conjugate elements always have the same order⁵.

The conjugation action partitions the group into conjugacy classes. Thus we can write the class equation.

Class equation

For a group $G$, let $\{\mathcal K_i\}_{i=1}^r$ be all conjugacy classes of length greater than one, and let $g_i$ be a representative of $\mathcal K_i$. Then

$$|G|=|Z(G)|+\sum_{i=1}^r[G:C_G(g_i)].$$

It can be used to analyze the structure of groups, for example to prove the Sylow theorems below.

Normalizers and centralizers

In fact, the power set of a group can also be the object of a group action. Here we focus on the conjugation action of a group on the set of all its subsets, $X=\mathcal P(G)$. Its permutation representation is

$$\begin{aligned} \varphi:G\rightarrow S_X&\\ g\mapsto \varphi_g&: X\rightarrow X\\ &\quad S\mapsto gSg^{-1} = \{gsg^{-1}:s\in S\} \end{aligned}$$

Under this conjugation action, one can likewise define conjugacy classes of subsets of the group. Its kernel is still the center of the group. Its stabilizer is called the normalizer.

Normalizer

For a group $G$ and a subset $S\subseteq G$, the normalizer of $S$ in $G$ is $N_G(S)=\{g\in G:gSg^{-1}=S\}$.

The normalizer is the stabilizer of $S$ under the conjugation action, so it must be a subgroup of $G$. The normalizer of $S$ is the largest subgroup among those whose normal subgroups contain $S$, which explains the name. In particular, for a singleton $\{a\}$, $N_G(\{a\})=C_G(a)$.

The centralizer can likewise be generalized to subsets.

Centralizer

For a group $G$ and a subset $S\subseteq G$, the centralizer of $S$ in $G$ is $C_G(S)=\{g\in G:\forall s\in S(gsg^{-1}=s)\}$.

The centralizer is in fact the kernel of the conjugation action of the group $N_G(S)$ on $S$. Therefore $C_G(S)\trianglelefteq N_G(S)\le G$, and by transitivity of subgroup inclusion, the centralizer is also a subgroup. In particular, the center $Z(G)=C_G(G)\trianglelefteq N_G(G)=G$ must be a normal subgroup.

Sylow theorems

Further analysis of the conjugation action of a finite group yields the Sylow theorems. They are powerful tools for handling the structure of finite groups and can quickly determine the structure of many small-order groups.

$p$-group

For a group $G$, if there are a prime $p$ and a positive integer $\alpha$ such that $|G|=p^\alpha$, then it is called a $p$-group (also written $p$-group).

About the definition of a $p$-group

There is another definition of a $p$-group: a group in which the order of every element is a power of a prime. The two definitions are equivalent for finite groups, but the second also applies to infinite groups. Moreover, different sources may disagree about the definition of a $p$-group and about whether to count $\{e\}$ as a $p$-group; readers should distinguish these conventions when reading.

$p$-subgroup

For a group $G$ and a subgroup $P\le G$, if $P$ itself is a $p$-group, then $P$ is called a $p$-subgroup (also written $p$-subgroup).

Cauchy's theorem

If a prime $p$ divides the order of a group $G$, then there must be an element of order $p$.

Cauchy's theorem guarantees the existence of $p$-subgroups. A more detailed analysis gives a stronger result, namely the existence of Sylow $p$-subgroups.

Sylow $p$-subgroup

For a group $G$ and a subgroup $P\le G$, if $|G|=p^\alpha m$, $p\perp m$, and $|P|=p^\alpha$, then $P$ is called a Sylow $p$-subgroup (also written Sylow $p$-subgroup).

In other words, a Sylow $p$-subgroup is a largest $p$-subgroup. The Sylow theorems assert the existence of Sylow $p$-subgroups, providing a partial converse to Lagrange's theorem.

Sylow theorems

Let the order of a finite group $G$ be expressible as $|G|$ in the form $p^\alpha m$, where $p$ is prime and $p$ does not divide $m$. Then:

1. A Sylow $p$-subgroup exists.
2. For a Sylow $p$-subgroup $P$ and a $p$-subgroup $Q$ of $G$, there exists $g\in G$ such that $Q\le gPg^{-1}$; in particular, all Sylow $p$-subgroups are conjugate.
3. The number $n_p$ of Sylow $p$-subgroups in $G$ satisfies $n_p\equiv 1\pmod p$, $n_p\mid m$, and $n_p=[G:N_G(P)]$, where $P$ is any Sylow $p$-subgroup.

Proof

To prove the first part, use induction on $|G|$. Consider the class equation

$$|G|=|Z(G)|+\sum_{i=1}^r[G:C_G(g_i)].$$

If $p\mid|Z(G)|$, choose a subgroup $N\le Z(G)$ of order $p$. Then $N\trianglelefteq Z(G)\trianglelefteq G$, so $G/N$ is a smaller group. By the induction hypothesis it has a Sylow $p$-subgroup $P/N$; the corresponding preimage $P$ under the natural homomorphism is a Sylow $p$-subgroup of the original group $G$. It remains to consider the case where $p$ does not divide $|Z(G)|$. Then one can choose $g_i\in G$ such that $p$ does not divide $[G:C_G(g_i)]$, so all powers of $p$ occurring in $|G|$ occur in $|C_G(g_i)|$. Again by the induction hypothesis, $|C_G(g_i)|$ has a Sylow $p$-subgroup $P$, which is a Sylow $p$-subgroup of the original group $G$.

To prove the second and third parts, let the conjugacy class of a Sylow $p$-subgroup $P$ of $G$ be $\mathcal S=\{gPg^{-1}:g\in G\}$, and consider the result of restricting the conjugation action of $G$ on $\mathcal S$ to a $p$-subgroup $Q$. The set $\mathcal S$ can be partitioned into several orbits under this action. Suppose there are $r$ orbits, with representative $P_i$ for each orbit. Then

$$|\mathcal S|=\sum_{i=1}^r[Q:Q\cap N_G(P_i)].$$

Here $Q\cap N_G(P_i)$ is the stabilizer of $P_i$ under the action above. Let $H=Q\cap N_G(P_i)$. Clearly $H\le N_G(P_i)$, so by the second isomorphism theorem, $P_iH/P_i\cong H/(P_i\cap H)$. Therefore $|P_iH|=|P_i||H|/|P_i\cap H|$. The right-hand side is a power of $p$, so the left-hand side must also be a power of $p$, and $|P_i|\le |P_iH|$. But $P_i$ already has the largest possible power of $p$ among the subgroups of $G$, so $P_i=P_iH$. Substituting this into the isomorphism above gives $H=P_i\cap H=Q\cap P_i$. Here we used the obvious relation $P_i\le N_G(P_i)$. Thus the stabilizer $Q\cap N_G(P_i)$ is actually $Q\cap P_i$, and the equation becomes

$$|\mathcal S|=\sum_{i=1}^r[Q:Q\cap P_i].$$

This equality holds for every $p$-subgroup $Q$.

Naturally, the Sylow $p$-subgroup $P$ is also a $p$-subgroup. Substitute $P$ for $Q$ in the equation above. Exactly one term on the right has size $1$, while all the others are multiples of $p$. Therefore, the size $|\mathcal S|$ of the conjugacy class of the Sylow $p$-subgroup $P$ is congruent to $1$ modulo $p$. At the same time, since this equation holds for every $p$-subgroup $Q$, there must exist $g\in G$ such that $Q\le gPg^{-1}$. Otherwise, every $P_i$ in the equation above would satisfy $|Q\cap P_i|<|Q|$, contradicting $|\mathcal S|\equiv 1\pmod p$. If $Q$ is now taken to be a Sylow $p$-subgroup different from $P$, then necessarily $Q=gPg^{-1}$ for some $g\in G$, so all Sylow $p$-subgroups are conjugate. Consequently, the number $n_p$ of Sylow $p$-subgroups is $|\mathcal S|$, and it satisfies $n_p\equiv 1\pmod p$. Finally, note that $n_p=|\mathcal S|=[G:N_G(P)]$ and $P\le N_G(P)$, so $n_p\mid m$. This completes the proof of the second and third parts of the theorem.

Application: up to isomorphism, the only groups of order six are $C_6$ and $S_3$

Let $G$ have order $6$. By the Sylow theorems, it has a Sylow $2$-subgroup, whose number satisfies $n_2\equiv 1\pmod 2$ and $n_2\mid 3$. Thus there are only two possibilities: $n_2=1$ or $n_2=3$. Similarly, one can prove that $G$ has exactly one Sylow $3$-subgroup, namely $n_3=1$.

In the case $n_2=1$, the group $G$ has one Sylow $2$-subgroup and hence one element of order $2$. It also has one Sylow $3$-subgroup and hence two elements of order $3$. The group $G$ has one identity element as well. By Lagrange's theorem, the order of each remaining element must divide $6$. It cannot be a new element of order $2$ or $3$, since that would produce a new Sylow $p$-subgroup different from the ones above. Thus the remaining element must have order $6$. The existence of an element whose order equals the order of the group means that $G$ is cyclic, so $G\cong C_6$. For the case $n_2=3$, the group $G$ has three conjugate Sylow $3$-subgroups. Consider the conjugation action of $G$ on these three Sylow $3$-subgroups. For any Sylow $3$-subgroup $P$, Sylow's theorem gives $|N_G(P)|=2$; but we also have $P\le N_G(P)$, so $P=N_G(P)$. Therefore, the intersection of the normalizers of these three Sylow $3$-subgroups, which is the kernel of this conjugation action, is trivial. Thus, the action is faithful, and it embeds $G$ into the permutation group on these three Sylow $3$-subgroups, namely $S_3$. However, since $|G|=|S_3|$, we must have $G\cong S_3$.

Finitely Generated Abelian Groups

Having learned the basic tools for analyzing group structure, we now focus on a particular class of groups.

As mentioned in the overview, Abelian groups have a simpler structure than other groups because their elements commute. The simplest among them are those that can be generated by finitely many elements.

Finitely generated

If a group $G$ has a finite generating set, then group $G$ is called finitely generated (finitely generated).

The classification theorem in this section states that finitely generated Abelian groups can be viewed as simple combinations of finitely many cyclic groups. Most groups arising in algorithm competitions are finite. Finite Abelian groups are necessarily finitely generated, so this conclusion always applies.

Direct Products

The preceding analysis of groups focused mainly on how to decompose a group into smaller groups; conversely, it is natural to ask how to combine two groups into a larger one. Among all possible ways to combine them, the direct product of groups is the simplest.

The basic idea of the direct product of groups is to take two groups $G$ and $H$, consider their Cartesian product $G\times H$, and define the operation on a pair $(g,h)$ componentwise, with the components independent of each other. The result is clearly a larger group, and the original two groups embed naturally into it.

Direct product

The direct product (direct product) of groups $(G,\cdot_G)$ and $(H,\cdot_H)$ is the group $(G\times H,\cdot)$, where the binary operation $\cdot:(G\times H)\times(G\times H)\rightarrow G\times H$ is defined by $(g_1,h_1)\cdot(g_2,h_2)=(g_1\cdot_G g_2,h_1\cdot_H h_2)$. The direct product of groups $G$ and $H$ is denoted by $G\times H$.

For the direct product $G\times H$, there are obvious embedding maps $g\mapsto(g,e_H)$ and $h\mapsto(e_G,h)$. Conversely, the maps $(g,h)\mapsto g$ and $(g,h)\mapsto h$ are group homomorphisms, whose kernels are $\{e_G\}\times H$ and $G\times\{e_H\}$, respectively. These two kernels are exactly the images of the embedding maps above, and their intersection is trivial, namely $\{(e_G,e_H)\}$. Thus, the direct product $G\times H$ contains two subgroups, both normal, with trivial intersection, whose product is the direct product $G\times H$ itself.

This analysis in fact gives necessary and sufficient conditions for a group to be expressible as the direct product of two of its subgroups.

Theorem

For a group $G$ and its subgroups $H_1,H_2\le G$, $G\cong H_1\times H_2$ if and only if $H_1,H_2\trianglelefteq G$, $H_1\cap H_2=\{e\}$, and $G=H_1H_2$.

Proof

The necessity of these conditions was discussed in the main text; here we prove their sufficiency. Consider the map $\varphi:G\rightarrow H_1\times H_2$ defined by $h_1h_2\mapsto(h_1,h_2)$. The map $\varphi$ is well-defined, because for any $h_1,k_1\in H_1$ and $h_2,k_2\in H_2$, the equality $h_1h_2=k_1k_2$ implies $h_1=k_1$ and $h_2=k_2$; this follows from $k_1^{-1}h_1=k_2h_2^{-1}\in H_1\cap H_2=\{e\}$. To show that $\varphi$ is a group homomorphism, it suffices to show $(h_1h_2)(k_1k_2)=h_1k_1h_2k_2$, which is equivalent to $k_1$ and $h_2$ commuting, or $k_1h_2k_1^{-1}h_2^{-1}=e$. To prove this relation, note that $k_1h_2k_1^{-1}h_2^{-1}=(k_1h_2k_1^{-1})h_2^{-1}\in (k_1H_2k_1^{-1})H_2=H_2$; similarly, $k_1(h_2k_1^{-1}h_2^{-1})\in H_1$, and hence $k_1h_2k_1^{-1}h_2^{-1}\in H_1\cap H_2=\{e\}$. Thus $\varphi$ is a group homomorphism. It is clearly bijective, so it is an isomorphism, and therefore $G\cong H_1\times H_2$.

In a direct product, elements from the two direct factors necessarily commute, because $hg=(e_G,h)(g,e_H)=(g,h)=gh$. Therefore, if both direct factors are Abelian groups, their direct product must also be Abelian.

Not every group can be written as the direct product of two nontrivial subgroups.

Example: The spatial symmetry group $D_6$ of an equilateral triangle (continued)

For example, the group $D_6=\langle r,s\rangle$ is not isomorphic to $\langle r\rangle\times\langle s\rangle$, because the latter, being the direct product of two cyclic groups, must be Abelian.

The classification theorem below states that every finitely generated Abelian group can be written as the direct product of finitely many cyclic groups.

Classification Theorem

For finitely generated Abelian groups, we have the following classification theorem. It is called the fundamental theorem of finitely generated Abelian groups (fundamental theorem of finitely generated Abelian groups).

Fundamental Theorem of Finitely Generated Abelian Groups

For a finitely generated Abelian group $G$, there exist an integer $r\ge0$ and integers $n_1,\cdots,n_s\ge 2$ such that

$$G\cong C_\infty^r\times C_{n_1}\times\cdots\times C_{n_s}.$$

In particular, $r$ is uniquely determined and is called the rank of the group $G$, and

• the integers $n_1,\cdots,n_s$ can be chosen to satisfy $n_1\ge2,\ n_1|n_2,\ \cdots,\ n_{s-1}|n_s$; in this case, the integers $n_1,\cdots,n_s$ are uniquely determined, and the factors $C_{n_i}$ are called the invariant factors of $G$;
• the integers $n_1,\cdots,n_s$ can also be chosen to all be prime powers; in this case, these prime powers are also uniquely determined, and the factors $C_{n_i}$ are called the elementary divisors of group $G$.

The theorem first asserts that every finitely generated Abelian group is the direct product of finitely many cyclic groups.

Proof

Here is a formally simple proof⁶; a deeper proof should refer to the structure theorem for finitely generated modules over a principal ideal domain⁷. For convenience, we use additive notation instead of the multiplicative notation of a general group in this proof: $0$ denotes the identity element, and the notation $mx$ denotes the power of $x$ taken $m$ times.

Suppose that $G$ can be generated by $k$ elements, with the number of generators minimal. The proof proceeds by induction on $k$. When $k=1$, the conclusion is trivial. When $k>1$, among all generating tuples of group $G$, written $\langle x_1,x_2,\cdots,x_k\rangle$, choose one whose $x_1$ has the smallest order. We will show that $G=\langle x_1\rangle\times\langle x_2,\cdots,x_k\rangle$; by the induction hypothesis, the latter can already be decomposed as the direct product of $(k-1)$ cyclic groups, proving the inductive step.

By the characterization of direct products of groups, if the direct-product decomposition does not hold, there must be a relation $m_1x_1+m_2x_2+\cdots+m_kx_k=0$ with $m_1x_1\neq 0$. For negative coefficients $m_i$, we can use the inverse $-x_i$ in place of $x_i$, so all coefficients $m_i$ may be taken to be nonnegative integers. Moreover, we may take $0< m_1 <|x_1|$. If we further set $d=\gcd(m_1,m_2,\cdots,m_k)$ and $c_i=m_i/d$, then there must be a $y_1=c_1x_1+c_2x_2+\cdots+c_kx_k$ satisfying $dy_1=0$, and hence $|y_1|\le d\le m_1< |x_1|$; that is, $y_1$ is an element of smaller order than $x_1$.

We next prove that $y_1$ can be extended to a generating set of $G$. In other words, there exist elements $y_2,\cdots,y_k\in G$ such that $G=\langle y_1,y_2,\cdots,y_k\rangle$. The only known condition here is that $y_1$ can be written as $c_1x_1+c_2x_2+\cdots+c_kx_k$, where the coefficients $c_i$ are natural numbers and their greatest common divisor is one. Without loss of generality, suppose that the coefficients are arranged in nonincreasing order. Then $y_1$ can also be written as $(c_1-c_2)x_1+c_2(x_1+x_2)+\cdots+c_kx_k$. Comparing this with the previous condition, we see that the coefficients are still all natural numbers, their greatest common divisor is still one, and $G=\langle x_1,x_1+x_2,x_3,\cdots,x_k\rangle$, but the sum of all coefficients has decreased by $c_2$. If $c_2=0$, then necessarily $c_1=1$, and the conclusion is trivial; otherwise, the sum of the coefficients has strictly decreased. This means that, by induction on the sum of the coefficients, we can prove that a $y_1$ satisfying the above conditions can always be extended to a generating set of $G$.

Thus, relative to $x_1$, we have found a generator $y_1$ of smaller order, contradicting the choice of $x_1$. Therefore, the direct-product decomposition must hold, and the desired conclusion follows from the induction principle.

Of course, cyclic groups may have infinite or finite order; these are respectively the $C_\infty$ and $C_{n_i}$ parts of the decomposition above. The theorem then gives the structure of finite cyclic groups $C_n$. The elementary-divisor part of the theorem in fact relies on the following observation.

Lemma

If $m$ and $n$ are coprime, then $C_{mn}\cong C_m\times C_n$.

Proof

Let $x$ and $y$ be generators of $C_m$ and $C_n$, respectively. Since $(m,n)=1$, we have $|(x,y)|=mn=|C_m\times C_n|$. Thus, $(x,y)$ is a generator of $C_m\times C_n$, that is, $C_m\times C_n=\langle(x,y)\rangle$. Therefore, it is a cyclic group of order $mn$ and must be isomorphic to $C_{mn}$.

Given a cyclic group $C_{n}$, if the fundamental theorem of arithmetic gives $n=p_1^{r_1}\cdots p_k^{r_k}$, then repeated application of the lemma proves that $C_n=C_{p_1^{r_1}}\times\cdots\times C_{p_k^{r_k}}$. After these two decompositions, we have in fact obtained the elementary-divisor decomposition in the theorem. Then, by regrouping these prime-power-order cyclic groups according to the required conditions, we obtain the invariant-factor decomposition in the theorem. The uniqueness in the theorem can be proved by induction.

Example: Classification of Abelian Groups of Order 24

As an example, the theorem shows that there are exactly three Abelian groups of order 24, listed below.

Invariant-factor decomposition	Elementary-divisor decomposition
$C_{24}$	$C_{3}\times C_{8}$
$C_{2}\times C_{12}$	$C_2\times C_{3}\times C_4$
$C_2\times C_2\times C_6$	$C_2\times C_2\times C_2\times C_3$

References and Notes

• Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3rd Edition, John Wiley & Sons, Inc.
• Milne, J.S. (2021) Group Theory.
• Group (mathematics) - Wikipedia
• Group theory - Wikipedia
• Group - Wolfram MathWorld
• Visual Group Theory

Footnotes

1. This group can be represented as the permutation group $\{(1),(12)(34),(13)(24),(14)(23)\}$, and can also be written as $C_2\times C_2$. ↩

2. For a general subgroup $H\le G$, one can also try to define a similar operation on all left (or right) cosets. However, such an operation is well-defined if and only if $H$ is a normal subgroup of $G$. ↩

3. For example, see Group action - Wikipedia. ↩

4. Cayley's theorem itself does not reveal much information about the structure of the group, because the group $S_G$ is usually very large, making it difficult to say what definite properties a subgroup of size exactly $|G|$ might have. However, the early development of group theory focused mainly on permutation groups. Thus, Cayley's theorem is really saying that all possible group structures are among these objects that have already been studied extensively, even though more refined tools are needed in actual research. ↩

5. More generally, conjugate elements in a permutation group necessarily have the same type. ↩

6. See page 25 of Milne, J.S. (2021) Group Theory. ↩

7. See Structure theorem for finitely generated modules over a principal ideal domain - Wikipedia. ↩