Generators, Presentations and Free Products

Introduction

The previous articles of this category treat groups abstractly and through their actions. This one treats them combinatorially: a group is described by naming some elements and imposing relations among them, and the description is turned into a construction by means of the free group. The three notions are interdependent. A generating set reduces a group to a set of symbols; a free group is the group in which the symbols satisfy no relations at all, so that it is the universal group on that set; a presentation is a free group divided by the relations one wants, and a free product is the group-theoretic coproduct, the construction dual to the direct product. The semidirect product then describes the groups obtained from a normal subgroup and a complement, which is exactly the shape in which the Sylow theorems deliver the groups of small order.

The theory is combinatorial and needs no hypothesis on a base ring; where a group is written additively it is abelian. Throughout, $R$ denotes a commutative ring with identity $1 \neq 0$ and $F$, $K$ denote fields when the occasional linear-group example is mentioned. The notation of Groups is kept: $\langle S \rangle$ for the subgroup generated by a set $S$, $F(X)$ for the free group on $X$, $\langle X \mid R \rangle$ for a presentation, and $N \rtimes_\varphi H$ for a semidirect product. The companion articles Transformation Groups and Group Actions and Structure are being written in parallel; the present article supplies the combinatorial descriptions on which they draw. No physics is invoked.

Generating Sets

The Subgroup Generated by a Set

Definition. Let $G$ be a group and $S \subseteq G$ a subset. The subgroup generated by $S$, written $\langle S \rangle$, is the intersection of all subgroups of $G$ containing $S$. It is the smallest subgroup of $G$ containing $S$; if $\langle S \rangle = G$, the set $S$ generates $G$, and its elements are generators.

Since an intersection of subgroups is a subgroup and $G$ itself is a subgroup containing $S$, the definition is legitimate. The explicit description is more useful than the definition:

$$ \langle S \rangle = \{s_1^{\varepsilon_1} s_2^{\varepsilon_2} \cdots s_n^{\varepsilon_n} : n \geq 0, \ s_i \in S, \ \varepsilon_i \in \{\pm 1\}\}, $$

the empty product being the identity. That the right-hand side is a subgroup containing $S$, and that it is contained in every subgroup containing $S$, is immediate; hence it equals the intersection.

Example. Cyclic groups: $C_n = \langle x \rangle$ for a single generator $x$ of order $n$, the case $S = \{x\}$. The infinite cyclic group is $\mathbb{Z} = \langle 1 \rangle$.

Example. The symmetric group $S_n$ is generated by the transpositions $(1\,2), (2\,3), \ldots, (n-1\,n)$, and also by $(1\,2)$ together with the $n$-cycle $(1\,2 \cdots n)$, as in Groups, §15.

Example. The dihedral group is generated by an element of order $n$ and an involution inverting it, $D_n = \langle r, s \rangle$.

Example. The quaternion group is generated by two elements, $Q_8 = \langle e_1, e_2 \rangle$, and also by $e_1$ and $e_3$.

Definition. A group is finitely generated if it is generated by a finite set. The rank of a finitely generated group is the least cardinality of a generating set, when that minimum is attained.

Every finite group is finitely generated, by itself. An infinite direct sum of copies of $\mathbb{Z}$, for instance $\bigoplus_{n \ge 1} \mathbb{Z}$, is not finitely generated: a finite set $S$ has nonzero coordinates in only finitely many summands, so it generates only the elements supported on those summands.

Generating Sets and Epimorphisms

Generation has a categorical expression that anticipates the free group. If $S \subseteq G$ and $F(S)$ is the free group on $S$, the inclusion $S \hookrightarrow G$ extends to a homomorphism $F(S) \to G$, and $\langle S \rangle$ is the image. Hence:

Proposition. A subset $S$ generates $G$ if and only if the canonical extension $F(S) \to G$ of the inclusion $S \hookrightarrow G$ is surjective.

Thus a generating set is the same thing as an epimorphism from a free group, and choosing generators of $G$ is choosing a free group that maps onto $G$. The kernel of that epimorphism records the relations, which is the subject of presentations below.

Lemma. If $S_i$ are subgroups of $G$ then $\langle \bigcup_i S_i \rangle$, the join of the $S_i$, is the smallest subgroup containing all of them; for two subgroups $H, K$,

$$ \langle H \cup K \rangle = \{h_1 k_1 h_2 k_2 \cdots h_n k_n : h_i \in H, \ k_i \in K\}. $$

Proof. The set displayed is closed under multiplication and inversion (an inverse reverses the order and inverts each factor, staying in the set), contains $H$ and $K$, and is contained in every subgroup containing both.

Remark. The join of two subgroups need not commute: $\langle H \cup K \rangle$ is not the set of products $h k$ unless one of the subgroups is normal, the special case that makes the internal recognition theorems for direct and semidirect products work. This is the technical point at which the two product constructions below diverge.

Free Groups

Words and Reduction

Let $X$ be a set. Form the alphabet $\mathcal{A} = X \sqcup X^{-1}$, where $X^{-1}$ is a disjoint copy of $X$ and $x^{-1}$ is the formal inverse of $x \in X$. A word in $\mathcal{A}$ is a finite sequence $a_1 a_2 \cdots a_n$ of letters, with $n = 0$ giving the empty word $\varepsilon$. A word is reduced if it contains no adjacent pair $x x^{-1}$ or $x^{-1} x$ with $x \in X$.

Concatenation of words does not preserve reducedness, so define the reduction of a word to be the reduced word obtained by repeatedly deleting adjacent inverse pairs. The order of deletions does not matter (deleting at one place cannot create or destroy an adjacent inverse pair at another place that is not already deletable), so the reduction is well defined; this is the diamond property of the cancellation system.

Construction of the Free Group

Let $W$ be the set of reduced words. For $a \in \mathcal{A}$ define a map $\lambda_a : W \to W$ by

$$ \lambda_a(w) = \text{the reduced word obtained from } aw. $$

Lemma. Each $\lambda_a$ is a bijection of $W$, with $\lambda_a^{-1} = \lambda_{a^{-1}}$.

Proof. Let $w \in W$. If $w = \varepsilon$ or $w$ begins with a letter different from $a^{-1}$, then $aw$ is already reduced and $\lambda_a(w) = aw$; applying $\lambda_{a^{-1}}$ gives $a^{-1} a w = w$ after cancellation. If instead $w = a^{-1} u$ with $u$ reduced and with $u$ empty or beginning with a letter different from $a$, then $aw = a a^{-1} u$ reduces to $u$, so $\lambda_a(w) = u$, and $\lambda_{a^{-1}}(u) = a^{-1} u = w$. Thus $\lambda_{a^{-1}} \lambda_a = \mathrm{id}_W$, and exchanging the roles of $a$ and $a^{-1}$ gives the reverse composite.

Definition. The free group on $X$, written $F(X)$, is the subgroup of $\operatorname{Sym}(W)$ generated by the permutations $\lambda_x$ for $x \in X$.

The assignment $x \mapsto \lambda_x$ is injective, because $\lambda_x(\varepsilon) = x$ while $\lambda_y(\varepsilon) = y$ for $y \neq x$. Every element of $F(X)$ is a composite of the generators and their inverses, hence of the form $\lambda_{a_1} \cdots \lambda_{a_n}$; and evaluating at $\varepsilon$ returns the reduced word $a_1 \cdots a_n$. Consequently the map

$$ F(X) \longrightarrow W, \qquad \phi \longmapsto \phi(\varepsilon) $$

is a bijection: distinct reduced words give distinct permutations. In particular a word $a_1 \cdots a_n$ representing the identity is one whose reduction is empty, which is the precise sense in which the only relations in $F(X)$ are the trivial ones $x x^{-1} = e$.

Theorem (universal property of the free group). Let $X$ be a set, $G$ a group, and $f : X \to G$ any function. Then there is a unique homomorphism $\tilde{f} : F(X) \to G$ with $\tilde{f}(\lambda_x) = f(x)$ for all $x \in X$.

Proof. Extend $f$ to words by $f(\varepsilon) = e$, $f(a_1 \cdots a_n) = f(a_1) \cdots f(a_n)$ using $f(x^{-1}) = f(x)^{-1}$. This is multiplicative by construction and respects cancellation, since $f(x) f(x)^{-1} = e$; hence it descends to a homomorphism $\tilde{f} : F(X) \to G$ defined by $\tilde{f}(\lambda_{a_1}\cdots\lambda_{a_n}) = f(a_1)\cdots f(a_n)$. This is well defined because reduced words are in bijection with elements of $F(X)$ and the value depends only on the reduced form. Uniqueness holds because the $\lambda_x$ generate $F(X)$.

Corollary. The pair $(F(X), x \mapsto \lambda_x)$ is determined up to a unique isomorphism: if $F$ is any group with a map $\iota : X \to F$ such that every $f : X \to G$ extends uniquely to a homomorphism $F \to G$, then $F \cong F(X)$ canonically.

Proof. Apply the property of $F$ to $f = \iota_{F(X)}$ to get a homomorphism $F \to F(X)$ extending it, and the property of $F(X)$ to $\iota$ to get $F(X) \to F$; the composites both extend the respective identity embeddings, hence equal the identities by uniqueness.

Elementary Properties of Free Groups

The rank. The cardinality of $X$ is an invariant of $F(X)$; it is the rank. To see this when $X$ is finite of size $n$, the abelianization $F(X)^{\mathrm{ab}}$ is free abelian of rank $n$: the relations of an abelian group force commutativity, so $F(X)^{\mathrm{ab}} \cong \mathbb{Z}^n$, whose rank $n$ is an invariant of the group. For the same reason, $F(X)$ is generated by exactly $n$ elements and no fewer.

Nonabelian-ness. If $|X| \geq 2$, then $F(X)$ is nonabelian: for distinct $x, y \in X$ the reduced word $x y x^{-1} y^{-1}$ is not empty, so $[x, y] \neq e$. If $|X| = 1$ then $F(X) \cong \mathbb{Z}$.

Torsion-freeness. If $|X| \geq 1$, then $F(X)$ is torsion-free. A nonempty reduced word $w$ is cyclically reduced if its first and last letters are not mutually inverse; conjugating $w$ by the inverse of an initial segment of $w$ replaces it by a cyclically reduced conjugate, and conjugate elements have the same order. For a cyclically reduced nonempty $w$ the concatenation $w^n$ is already reduced, hence nonempty, so $w$ has infinite order. The free group is the fundamental example of a torsion-free nonabelian group.

Every group is a quotient of a free group. Take $X = G$ and extend the identity map $G \to G$ to an epimorphism $F(G) \to G$; its kernel is a normal subgroup $N$ and $G \cong F(G)/N$. In particular every group has a presentation, in the sense of the next section.

Subgroups of free groups. A subgroup of a free group is free. This is the Nielsen–Schreier theorem, and its quantitative form, the Nielsen–Schreier index formula, states that a subgroup of finite index $m$ in $F(X)$ with $|X| = n$ is free of rank $mn - m + 1$. The theorem is standard; it is the first hint that the category of groups has a combinatorial, tree-like side not visible in the abelian case.

Example (a subgroup of $F_2$). Let $a, b$ freely generate $F_2$ and let $\varphi : F_2 \to C_2 \times C_2$ be the epimorphism onto the Klein four group sending $a$ and $b$ to the two generators of $C_2 \times C_2$. The kernel $H$ has index $4$, so

$$ \operatorname{rank} H = m n - m + 1 = 4 \cdot 2 - 4 + 1 = 5 . $$

The Schreier construction with the transversal $\{e, a, b, ab\}$ produces the eight Schreier generators

$$ aA, \quad bB, \quad aa, \quad bb, \quad abBA, \quad baBA, \quad abaB, \quad abbA, $$

where $A = a^{-1}$ and $B = b^{-1}$; each lies in $H$ because its image in $C_2 \times C_2$ is trivial. Three of the eight are the trivial word: $aA = a a^{-1}$, $bB = b b^{-1}$, and $abBA = ab (ab)^{-1}$, the last because $ab$ is itself a representative. The remaining five,

$$ aa, \quad bb, \quad baBA, \quad abaB, \quad abbA, $$

are the nontrivial Schreier generators, and they form a free basis of $H$: the Schreier construction shows that they generate $H$, and a generating set of a free group whose size equals the rank is a basis. The count $5$ is exactly the rank computed from the index formula. The same formula shows that $[F_2, F_2]$, the kernel of the abelianisation $F_2 \to \mathbb{Z}^2$, has infinite index and is therefore free of infinite rank, so a finitely generated free group has a finitely generated subgroup exactly when that subgroup has finite index.

Free Products

The Coproduct of Groups

Definition. Let $(G_i)_{i \in I}$ be a family of groups. A free product of the family is a group $G$ together with homomorphisms $\iota_i : G_i \to G$ such that, for every group $H$ and every family of homomorphisms $f_i : G_i \to H$, there is a unique homomorphism $f : G \to H$ with $f \circ \iota_i = f_i$ for all $i$. It is written $*_{i \in I} G_i$, or $G_1 * G_2$ for two factors.

The definition is the universal property of the coproduct, dual to the universal property of the direct product in the next section but one: for a product, maps into each factor determine a map into the product; for a coproduct, maps out of each factor determine a map out of the coproduct.

Theorem (existence). The free product of any family of groups exists and is unique up to a unique isomorphism.

Proof. For each $i$ choose a presentation $G_i \cong \langle X_i \mid R_i \rangle$ with the sets $X_i$ pairwise disjoint and each $G_i$ generated by $X_i$; such a presentation exists by taking $X_i = G_i$ with all products as relations. Put $X = \bigsqcup_i X_i$ and $R = \bigsqcup_i R_i$, let $N = \langle\langle R \rangle\rangle$ be the normal closure of $R$ in the free group $F(X)$, and set $G = F(X)/N$. The inclusion $X_i \hookrightarrow X$ induces $G_i = F(X_i)/\langle\langle R_i\rangle\rangle \to G$, since $N$ contains the images of the $R_i$. Given homomorphisms $f_i : G_i \to H$, choosing representatives of $X_i$ in $G_i$ and composing with $F(X_i) \to G_i$ gives maps $X_i \to H$, hence a map $X \to H$, hence $F(X) \to H$, which kills each $R_i$ and therefore factors through $G$. Uniqueness is the uniqueness part of the universal property of $F(X)$. The uniqueness of the free product up to a unique isomorphism is the standard argument of the corollary in the previous section, applied to two free products.

Normal Forms

Theorem (normal form). Let $G = G_1 * G_2$. Every element of $G$ is uniquely expressible as

$$ g_1 g_2 \cdots g_n, \qquad n \geq 0, \quad g_j \in G_{i_j} \setminus \{e\}, \quad i_j \neq i_{j+1}, $$

the empty product being the identity. A word of this kind is called reduced; uniqueness is up to nothing, the expression being already reduced.

The theorem follows from the presentation construction above and is proved by a rewriting argument: in the free product presented by $\langle \bigsqcup_i X_i \mid \bigsqcup_i R_i\rangle$, applying a relation of $R_i$ to a subword lying inside a single factor replaces one element of $G_i \setminus \{e\}$ by another (or by the identity only if the subword already represented the identity), and the standard induction on the length of a reduced alternating word then shows that no nonempty such word represents the identity. The theorem is standard and is stated here in the classical form.

Corollary. The factors embed in $G_1 * G_2$ as subgroups, and $G_1 * G_2$ is generated by $G_1 \cup G_2$. If both factors are nontrivial, then the free product is infinite and contains elements of infinite order.

Example (infinite dihedral group). $C_2 * C_2 = \langle x, y \mid x^2 = y^2 = e \rangle$ is the infinite dihedral group $D_\infty$, the group generated by two involutions whose product $xy$ has infinite order; the group is the semidirect product $\mathbb{Z} \rtimes C_2$ with $C_2$ acting by inversion.

Example. $C_2 * C_3 = \langle x, y \mid x^2 = y^3 = e \rangle$ is isomorphic to $PSL_2(\mathbb{Z})$, the modular group, which acts on the upper half plane with a fundamental domain whose sides are identified by an involution and an element of order $3$. This is the standard proof that the modular group is the free product of its two torsion subgroups.

Amalgamated Products and the Ping-Pong Lemma

Definition. Let $G_1$ and $G_2$ be groups with a common subgroup $H$, with injective homomorphisms $H \to G_1$ and $H \to G_2$. The free product with amalgamation $G_1 *_H G_2$ is the quotient of $G_1 * G_2$ by the normal closure of $\{h_1 h_2^{-1} : h \in H\}$, where $h_i$ is the image of $h$ in $G_i$.

The universal property is that maps $f_i : G_i \to K$ agreeing on $H$ factor uniquely through $G_1 *_H G_2$. The construction is the group-theoretic pushout, and it is the algebraic model of gluing two spaces along a common subspace, which is why the Seifert–van Kampen theorem computes fundamental groups by exactly this formula.

Lemma (ping-pong). Let $G$ act on a set $X$ and let $G_1, G_2 \leq G$ be subgroups with $G = \langle G_1, G_2 \rangle$ and $|G_1| \geq 3$. Suppose there are nonempty disjoint subsets $X_1, X_2 \subseteq X$ with $g X_2 \subseteq X_1$ for all $g \in G_1 \setminus \{e\}$ and $g X_1 \subseteq X_2$ for all $g \in G_2 \setminus \{e\}$. Then $G \cong G_1 * G_2$.

Proof. Write a reduced word as $v = v_1 \cdots v_m$ with its letters alternating between the two subgroups and $v_m \in G_l$, and let $\bar l$ denote the other index. Induction on $m$ gives

$$ v(X_{\bar l}) \subseteq X_l \ \ (m \text{ odd}), \qquad v(X_{\bar l}) \subseteq X_{\bar l} \ \ (m \text{ even}), $$

for $m = 1$ the first inclusion being the hypothesis and the step applying the induction hypothesis to the tail $v_2 \cdots v_m$ and then the hypothesis to $v_1$. Hence a reduced word of odd length is not the identity, since it maps the nonempty set $X_{\bar l}$ into the disjoint set $X_l$.

Let now $w = g_1 \cdots g_n = e$ be reduced of even length, and suppose first that $g_1 \in G_1$. Then $t = g_2 \cdots g_n = g_1^{-1}$ lies in $G_1 \setminus \{e\}$, and as an odd reduced word with last letter in $G_2$ it satisfies $t(X_1) \subseteq X_2$, while the hypothesis gives $t(X_2) \subseteq X_1$. If $t^2 \neq e$, then $t^2 \in G_1 \setminus \{e\}$ gives $t^2(X_2) \subseteq X_1$ and also $t^2(X_2) = t(t(X_2)) \subseteq t(X_1) \subseteq X_2$; if $t^2 = e$, take $z \in G_1 \setminus \{e, t\}$, which exists because $|G_1| \geq 3$, and then $tz \in G_1 \setminus \{e\}$ gives $(tz)(X_2) \subseteq X_1$ while $(tz)(X_2) = t(z(X_2)) \subseteq t(X_1) \subseteq X_2$. Either way a nonempty subset of $X_2$ lies in $X_1 \cap X_2 = \emptyset$, a contradiction. If instead $g_1 \in G_2$, then $n$ even forces $g_n \in G_1$, so $s = g_1 \cdots g_{n-1} = g_n^{-1}$ lies in $G_1 \setminus \{e\}$ and is an odd reduced word whose last letter, $g_{n-1}$, lies in $G_2$. Thus $s(X_1) \subseteq X_2$ by the parity argument and $s(X_2) \subseteq X_1$ because $s \in G_1 \setminus \{e\}$, and the conclusion follows by replacing $t$ by $s$ in the preceding paragraph. Hence no nonempty reduced word is trivial, and the normal form theorem identifies $G$ with $G_1 * G_2$.

Example (the modular group). In $PSL_2(\mathbb{Z})$ the images of

$$ S = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}, \qquad T = \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix} $$

satisfy $S^2 = T^3 = -I$, so $S$ has order $2$ and $T$ order $3$ in the projective group, while

$$ ST = \begin{pmatrix} -1 & -1 \\ 0 & -1 \end{pmatrix}, \qquad (ST)^n = (-1)^n \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} $$

has infinite order. Applying the ping-pong lemma to the action of $PSL_2(\mathbb{Z})$ on the upper half-plane, with the standard half-plane domains for $S$ and $T$, gives

$$ PSL_2(\mathbb{Z}) = \langle S \rangle * \langle T \rangle \cong C_2 * C_3, $$

the classical presentation of the modular group, and correspondingly $SL_2(\mathbb{Z}) \cong C_4 *_{C_2} C_6$ with the central $C_2$ generated by $-I$. The identification of the abstract free product with the matrix group is the standard application of the ping-pong lemma, and the two orders and the unipotence of $ST$ are the matrix computations displayed above.

Presentations

Definition and Elementary Consequences

Definition. A presentation is a pair $\langle X \mid R \rangle$ consisting of a set $X$ of generators and a set $R$ of relations, that is, words in $X \sqcup X^{-1}$. The group presented is

$$ \langle X \mid R \rangle = F(X) / \langle\langle R \rangle\rangle, \qquad \langle\langle R \rangle\rangle = \text{the normal closure of } R \text{ in } F(X), $$

the smallest normal subgroup of $F(X)$ containing $R$. A relation $r \in R$ is usually written as an equation $r = e$; for instance $\langle x \mid x^n \rangle$ means $F(\{x\})/\langle\langle x^n\rangle\rangle \cong C_n$. A group is finitely presented if it has a presentation with $X$ and $R$ finite, and finitely generated if $X$ can be taken finite.

Theorem (universal property of a presentation). A homomorphism $\langle X \mid R \rangle \to H$ is the same thing as a function $X \to H$ whose extension to $F(X)$ kills every element of $R$. In particular, to define a homomorphism out of a presented group it suffices to give the images of the generators and check the relations.

Every group has a presentation: taking $X = G$ and $R$ the set of words $x y z^{-1}$ for all $x, y \in G$ with $xy = z$ presents $G$, since then the map $F(G) \to G$ has kernel exactly $\langle\langle R\rangle\rangle$. This presentation is enormous, which is why the useful question is not existence but the existence of a small presentation.

Example. $D_n = \langle r, s \mid r^n = s^2 = e, \ (sr)^2 = e \rangle$. The last relation says $s r s = r^{-1}$, and the normal form $r^i s^j$ follows from it.

Example. $Q_8 = \langle e_1, e_2 \mid e_1^4 = e, \ e_1^2 = e_2^2, \ e_2 e_1 e_2^{-1} = e_1^{-1} \rangle$.

Example. $S_n = \langle s_1, \ldots, s_{n-1} \mid s_i^2 = e, \ (s_i s_{i+1})^3 = e, \ (s_i s_j)^2 = e \ (|i - j| > 1) \rangle$, the Coxeter presentation of the symmetric group by adjacent transpositions.

Example. $\mathbb{Z}^2 = \langle x, y \mid x y x^{-1} y^{-1} = e \rangle$. Adding the relations $x^m = y^n = e$ presents the finite abelian group $C_m \times C_n$.

Example. The Baumslag–Solitar group $BS(2, 3) = \langle a, t \mid t a^2 t^{-1} = a^3 \rangle$ is finitely presented and non-Hopfian: the endomorphism sending $a \mapsto a^2$ and $t \mapsto t$ respects the relation, is onto because $a = a^3 a^{-2} = (t a^2 t^{-1}) a^{-2}$ lies in its image, and is not injective because it carries the nontrivial element $a^{-1} t a t^{-1}$ to $a$. Thus a surjective endomorphism of a finitely presented group need not be injective.

Tietze Transformations

Two presentations of the same group are related by elementary moves, the Tietze transformations:

(T1) add a generator $y$ and a relation $y = w$, where $w$ is a word in the old generators; or delete a generator and its defining relation;

(T2) add a relation $r$ that is a consequence of the existing relations; or delete such a relation.

Theorem (Tietze). Two finite presentations present isomorphic groups if and only if one can be obtained from the other by a finite sequence of Tietze transformations.

The theorem reduces the isomorphism problem for finitely presented groups to a rewriting question, and it is the theoretical basis of the practical manipulation of presentations. It does not make the isomorphism problem decidable: the word problem, deciding for a finite presentation whether a given word represents the identity, was proved undecidable by Novikov and Boone, so there is no algorithm that performs the reduction in general.

Deficiency and a Caution

For a finite presentation with $|X| = n$ generators and $|R| = m$ relations, the deficiency of the presentation is $n - m$; the deficiency of a finitely presented group is the maximum of $n - m$ over all its finite presentations. It is finite: for any presentation of $G$, the abelianisation $G^{\mathrm{ab}}$ is presented by the same generators and relations, so $m \geq n - b_1(G)$, where $b_1(G)$ is the torsion-free rank of $G^{\mathrm{ab}}$, and hence $n - m \leq b_1(G)$ bounds the maximum. Every presentation of a nontrivial finite group satisfies $m \geq n$, hence a finite group has deficiency at most $0$: the presentation descends to a presentation of the abelianization $G^{\mathrm{ab}}$ with the same generators and relations, and a finite abelian group generated by $n$ elements needs at least $n$ relations. Groups of positive deficiency are precisely the ones admitting a presentation with fewer relations than generators, the standard examples being free groups and surface groups.

Caution. A presentation is a description, not a solution. The same group has many presentations, presentations do not reveal the order of the group, and a finite presentation may present a group with undecidable word problem. Conversely a group may be finitely generated but not finitely presented, the standard example being the lamplighter-type groups constructed as wreath products.

Direct Products

The Direct Product and Its Universal Property

Definition. For a family $(G_i)_{i \in I}$ of groups, the direct product $\prod_{i \in I} G_i$ is the set of all functions $g : I \to \bigcup_i G_i$ with $g(i) \in G_i$, under componentwise multiplication. When $I$ is finite and $G_i = G$ for all $i$ one writes $G^I$, and for $I = \{1, 2\}$, $G_1 \times G_2$.

Proposition (universal property). The direct product, with its projections $\pi_i : \prod_j G_j \to G_i$, is the product in the category of groups: for every group $H$ and every family of homomorphisms $f_i : H \to G_i$ there is a unique homomorphism $f : H \to \prod_i G_i$ with $\pi_i \circ f = f_i$.

Proof. Define $f(h)(i) = f_i(h)$; componentwise it is a homomorphism, and it is the only map with the required projections.

Internal recognition. If $H, K \trianglelefteq G$ with $G = H K$ and $H \cap K = \{e\}$, then the map $H \times K \to G$, $(h, k) \mapsto h k$, is an isomorphism. The two subgroups are the direct factors, and one writes $G = H \times K$. The commutativity of the elements of $H$ with those of $K$ is automatic here, because for $h \in H$, $k \in K$ the commutator $[h, k]$ lies in $H \cap K = \{e\}$.

Example. $V_4 = C_2 \times C_2$, and $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ when $\gcd(m, n) = 1$.

Remark. The direct product of abelian groups is abelian, so it can build no nonabelian group from abelian factors. The free product, its categorical dual, can: $C_2 * C_2$ is infinite and nonabelian, and in fact the free product of two nontrivial groups is never abelian, since $g_1 g_2 g_1^{-1} g_2^{-1}$ is a nonempty reduced word for nontrivial $g_i \in G_i$. For abelian groups the coproduct is not the free product but the direct sum, the subgroup of the direct product consisting of the finitely supported functions, which is abelian. Thus "direct product", "direct sum" and "free product" are three distinct constructions that agree only in degenerate cases.

Semidirect Products

Construction

Definition. Let $N$ and $H$ be groups and let $\varphi : H \to \operatorname{Aut}(N)$ be a homomorphism. The semidirect product $N \rtimes_\varphi H$ is the set $N \times H$ with the operation

$$ (n_1, h_1)(n_2, h_2) = (n_1 \, \varphi(h_1)(n_2), \, h_1 h_2). $$

When $\varphi$ is trivial this is the direct product. The construction is a group: the identity is $(e_N, e_H)$, the inverse of $(n, h)$ is $(\varphi(h^{-1})(n^{-1}), h^{-1})$, and associativity follows from $\varphi(h_1 h_2) = \varphi(h_1)\varphi(h_2)$ together with the group laws in $H$ and $N$.

The subgroups $\overline N = \{(n, e_H)\}$ and $\overline H = \{(e_N, h)\}$ are isomorphic to $N$ and $H$; $\overline N$ is normal, since $(n_1, h_1)(n, e_H)(n_1, h_1)^{-1} = (n_1 \varphi(h_1)(n) n_1^{-1}, e_H) \in \overline N$, while $\overline H$ need not be normal. Moreover $\overline N \cap \overline H = \{e\}$ and $\overline N \, \overline H$ is the whole group, and the conjugation action of $\overline H$ on $\overline N$ recovers $\varphi$. Hence the semidirect product is exactly the internal situation of the next proposition.

Proposition (internal recognition). Let $G$ be a group with subgroups $N, H$ such that $N \trianglelefteq G$, $G = N H$ and $N \cap H = \{e\}$. Then $G \cong N \rtimes_\varphi H$, where $\varphi(h)(n) = h n h^{-1}$.

Proof. Every element of $G$ is uniquely $n h$ with $n \in N$, $h \in H$: existence from $G = NH$, uniqueness because $n_1 h_1 = n_2 h_2$ gives $n_2^{-1} n_1 = h_2 h_1^{-1} \in N \cap H = \{e\}$. The product is $(n_1 h_1)(n_2 h_2) = n_1 (h_1 n_2 h_1^{-1}) h_1 h_2 = (n_1 \varphi(h_1)(n_2))(h_1 h_2)$, which is the semidirect product law.

Splitting of Exact Sequences

The recognition theorem has a homological formulation. A short exact sequence of groups

$$ 1 \to N \xrightarrow{\iota} G \xrightarrow{\pi} H \to 1 $$

splits if there is a homomorphism $s : H \to G$ with $\pi \circ s = \mathrm{id}_H$. Given a split sequence, $G \cong N \rtimes_\varphi H$ with $\varphi(h)(n) = s(h) n s(h)^{-1}$, and conversely a semidirect product gives a split sequence. Non-split extensions exist and are classified by the second cohomology $H^2(H, N)$; the standard example is the central extension $\{\pm 1\} \to Q_8 \to V_4$, which has no complement because each of the three subgroups of order $4$ in $Q_8$ contains $-1$. The dihedral and dicyclic groups of order $12$ of Group Actions and Structure are on the other hand the split extensions of $C_3$ by $C_2 \times C_2$ and by $C_4$.

Example. $D_n \cong C_n \rtimes C_2$ with the generator of $C_2$ acting by inversion; $S_n \cong A_n \rtimes C_2$ for $n \geq 2$; and for primes $p \mid q - 1$ the nonabelian group of order $pq$ is $C_q \rtimes C_p$ with $C_p$ acting through an automorphism of order $p$.

Example. The affine group of a module $V$ is $\operatorname{Aff}(V) = V \rtimes GL(V)$, with the linear part acting on the translation subgroup $V$ by its natural action. This is the structure group of an affine space, treated in the companion category.

Remark. Complements need not exist, and when they do they need not be unique. The Schur–Zassenhaus theorem states that if $N$ is normal with $\gcd(|N|, |G/N|) = 1$ then a complement exists and any two complements are conjugate; without the coprimality the theorem fails, the simplest instance being the normal subgroup $C_2$ of $C_4$, which has no complement because $C_4$ has a unique subgroup of order $2$. The theorem is standard and is the reason the Sylow analysis of orders $pq$ terminates in a single semidirect product.

Summary

A generating set is the same thing as an epimorphism from the free group on that set. The free group $F(X)$ is constructed from reduced words, has its reduced words as unique normal forms, and satisfies the universal property that every function $X \to G$ extends to a unique homomorphism $F(X) \to G$; it is determined up to a unique isomorphism. Free groups are torsion-free, and $F(X)$ is nonabelian and of rank $|X|$ when $|X| \geq 2$; every group is a quotient of a free group, and every subgroup of a free group is free (Nielsen–Schreier).

The free product is the coproduct of groups, with a normal form in reduced alternating words; its basic nontrivial case is the infinite dihedral group $C_2 * C_2$, and the amalgamated product is the pushout used in the Seifert–van Kampen theorem. A presentation $\langle X \mid R \rangle$ is the quotient of $F(X)$ by the normal closure of $R$; it gives a universal property for homomorphisms out of the group, and two finite presentations define the same group exactly when they are related by Tietze transformations. The word problem for finitely presented groups is undecidable (Novikov–Boone).

The direct product is the product in the category of groups and is recognised internally by normal subgroups with $G = HK$, $H \cap K = \{e\}$; it cannot manufacture nonabelian groups from abelian ones. The semidirect product $N \rtimes_\varphi H$ repairs this, is recognised internally by $N \trianglelefteq G$, $G = NH$, $N \cap H = \{e\}$, and is exactly the data of a split short exact sequence; it is the form in which the groups of order $pq$, the dihedral groups, the symmetric groups and the affine groups are built.

Summary of Notation

Symbol	Meaning
$\langle S \rangle$	Subgroup generated by a set $S$
$F(X)$	Free group on a set $X$
$\lambda_x$	Generator of $F(X)$ acting on reduced words by left multiplication
$W$, $\varepsilon$	Set of reduced words, empty word
$X^{-1}$, $\mathcal{A} = X \sqcup X^{-1}$	Copy of $X$ of formal inverses; the alphabet
$G_1 * G_2$, $*_{i} G_i$	Free product (coproduct of groups)
$G_1 *_H G_2$	Free product with amalgamation over $H$ (pushout)
$D_\infty$	Infinite dihedral group $C_2 * C_2$
$\langle X \mid R \rangle$	Presentation with generators $X$ and relations $R$
$\langle\langle R \rangle\rangle$	Normal closure of $R$ in $F(X)$
$BS(2,3)$	Baumslag–Solitar group $\langle a, t \mid t a^2 t^{-1} = a^3 \rangle$, the standard non-Hopfian example
$\prod_i G_i$, $G_1 \times G_2$	Direct product
$G^I$	Direct power
$N \rtimes_\varphi H$	Semidirect product with action $\varphi : H \to \operatorname{Aut}(N)$
$1 \to N \to G \to H \to 1$	Short exact sequence of groups
$s : H \to G$	Splitting of an exact sequence
$\operatorname{Aff}(V) = V \rtimes GL(V)$	Affine group of a module
$\operatorname{rank} G$	Least cardinality of a generating set
$F_2$, $A = a^{-1}$, $B = b^{-1}$	Free group on $a, b$; the inverse letters
$[G, G]$	Commutator subgroup; $[F_2, F_2] = \ker(F_2 \to \mathbb{Z}^2)$
$SL_2(\mathbb{Z})$, $PSL_2(\mathbb{Z})$	$C_4 _{C_2} C_6$ and its central quotient by $\{\pm I\}$, the modular group $C_2 C_3$
$C_n$	Cyclic group of order $n$