Every group we have seen so far has been defined concretely: permutations, matrices, integers mod . There is a fundamentally different approach: describe a group by generators and relations. This leads to group presentations, which are both computationally useful and theoretically important. The key player is the free group, the “most general” group on a given set of generators.
3.6.1 Words and Reduced Words
Definition 3.6.1 (Alphabet and words). Let be a set (the alphabet). Let be a set of formal symbols in bijection with and disjoint from it. The elements of are letters; for a letter we write for its partner, so that . A word in is a finite sequence of letters, The empty word, with , is denoted . The concatenation of words and is ; it is associative, with identity .
Example 3.6.2. If , then ,,, and are words. We abbreviate as and as .
We want words to form a group, but and are different words that “should” be equal. So we cancel adjacent inverse letters.
Definition 3.6.3 (Reduction). An elementary reduction of a word deletes two adjacent letters of the form , for a letter . A word is reduced if no elementary reduction applies, that is, no letter is immediately followed by its inverse.
Example 3.6.4. The word can be reduced in two ways: The first path deletes and then ; the second deletes and then . Both end at the reduced word .
Theorem 3.6.5 (Unique reduced form). Every word can be turned into a reduced word by a finite sequence of elementary reductions, and the reduced word obtained does not depend on the sequence chosen.
Proof.Existence. Each elementary reduction shortens the word by two letters, so repeated reductions stop after finitely many steps, at a reduced word.
Uniqueness. Let be the set of reduced words. For each letter define by In both cases the result is reduced. We claim . If does not begin with , then , which begins with , so . If , then , and does not begin with because is reduced, so .
For an arbitrary word , put (and ). If is obtained from by deleting an adjacent pair , then , because . If is reduced, then : by induction on ,, which does not begin with because is reduced, so applying gives .
Now suppose some sequence of elementary reductions takes to a reduced word . Then , so , which depends only on .∎
Write for the reduced word obtained from . If can be reduced to (by any sequence of elementary reductions), then , since a reduction sequence from to a reduced word extends one from to . In particular, for any words ,
In a reduced word, a maximal block of consecutive letters from consists of copies of only or of only. Grouping such blocks, every reduced word can be written uniquely as and conversely every such expression, written out letter by letter, is a reduced word. For this is the form with .
3.6.2 The Free Group
Definition 3.6.6 (Free group). The free group on , denoted , is the set of reduced words in with the operation For we write , the free group on generators.
Proposition 3.6.7 (The free group is a group). The set is a group under this operation. Its identity is the empty word, and the inverse of is .
Proof. The product of two reduced words is reduced by definition.
Inverses: Let be reduced and . This word is reduced: an adjacent pair cancels only if , and then would cancel in . In the middle pair cancels, then , and so on, until we reach . So , and likewise .∎
If is reduced, then it is the product in of its one-letter words, and the one-letter word is the inverse of . So is generated by (identifying with the one-letter word), and the grouped form above expresses each element as a product of powers of generators. Renaming the letters shows that whenever there is a bijection .
Example 3.6.8 (Free group on one generator). consists of the reduced words , that is, , with . So .
Example 3.6.9 (Free group on two generators). is much more interesting. Its elements include , infinitely many distinct reduced words. Since and are different reduced words, , and is non-abelian. In fact contains subgroups isomorphic to for every ; Question 3.6 below proves this.
3.6.3 The Universal Property
The free group is “free” because no relations hold among its generators beyond those forced by the group axioms. This is captured by a universal property.
Theorem 3.6.10 (Universal property of free groups). Let send to the one-letter word . For any group and any function , there is a unique homomorphism with .
Proof.Existence. Extend to letters by , and define on arbitrary words by , with . Then for all words . An elementary reduction does not change , because for every letter ; hence . Let be the restriction of to reduced words. Then so is a homomorphism, and .
Uniqueness. A homomorphism with for all satisfies , and since in ,∎
Note. The universal property says that to define a homomorphism out of, it suffices to say where the generators go, and there are no constraints: any choice of images in any group extends uniquely. This is why is called “free.” Chapter 8 studies universal properties of this kind in general.
Corollary 3.6.11 (Every group is a quotient of a free group). If elements () generate , then the homomorphism with is surjective, and for its kernel .
Proof. The image is a subgroup containing every , so it is all of . Apply the First Isomorphism Theorem. ∎
So is the “largest” group with generators: every group generated by elements is a quotient of .
3.6.4 Group Presentations
To describe as a quotient , we would like to specify by a few of its elements. Since is normal, it then also contains all conjugates of those elements.
Proposition 3.6.12 (Normal closure). Let be a subset of a group . The set of all finite products is the smallest normal subgroup of containing : it is a normal subgroup containing , and every normal subgroup containing contains it. It is called the normal closure of .
Proof. The set contains (take ) and ; it is closed under products by construction, and under inverses because and the inverse of a product is the product of the inverses in reverse order. It is normal because , so a conjugate of such a product is again such a product. Finally, a normal subgroup containing contains every , hence every such product. ∎
Definition 3.6.13 (Group presentation). Let be a set and a set of words. The group presented by generators and relations is A presentation of a group is an isomorphism . The group is finitely presented if it has a presentation with and finite; we then write . A relation is often written as an equation: stands for the relation .
In , write for the image of . The generate the group, and every relation becomes the identity: . The presented group is the largest group with these properties, in the following sense.
Proposition 3.6.14 (Mapping out of a presentation). Let be a group and a function such that for every (we say the relations hold in ). Then there is a unique homomorphism with for all . It is surjective if and only if the elements generate , and it is an isomorphism if and only if, in addition, .
Proof. The kernel of is a normal subgroup containing , so it contains (Proposition 3.6.12). By Theorem 3.3.2, factors through a homomorphism with the same image as , namely the subgroup generated by the , and with kernel . This kernel is trivial exactly when . Uniqueness holds because the generate .∎
This gives the standard method for proving that a group has a given presentation. First, choose generators of and check that the relations hold in ; this gives a surjection . Second, show that the relations are complete. When is finite, it suffices to show that has at most elements, usually by using the relations to rewrite every element in a normal form; a surjection between finite sets of the same size is a bijection.
Example 3.6.15 (Presentations of familiar groups).
Cyclic groups:. The relation holds for the generator , giving a surjection. In every element is a power , and , so there are at most elements .
Infinite cyclic group:, with no relations.
Klein four-group:. The relations hold for and , which generate. In the presented group and , so every element is with : at most 4 elements.
The symmetric group :, with and . This is the case of Theorem 3.6 below.
Proposition 3.6.16 (Presentation of the dihedral group). For ,. (The last relation says .)
Proof. By Proposition 2.2.15, has order and is generated by a rotation and a reflection with and . So the relations hold in , and Proposition 3.6.14 gives a surjection from the presented group onto . In , the relations give , hence for all , and also and . So any product of the generators and their inverses can be rewritten by moving each to the right, in the form with and . Thus , and the surjection is an isomorphism. ∎
Proposition 3.6.17 (Free abelian groups)., where . Moreover , so is the abelianization of .
Proof. Let be the presented group and the element with in position and elsewhere. Since is abelian, the relations hold for , and the generate , so we get a surjection . In the generators commute pairwise, hence so do their inverses, and therefore any two products of generators and their inverses commute: is abelian. Collecting powers, every element of is for some , and sends it to . So is injective, hence an isomorphism.
For the second statement, is contained in , which is a normal subgroup containing the (Proposition 3.3.10). Conversely is abelian, so by Proposition 3.3.10(b). Hence .∎
The symmetric group has a presentation in terms of the adjacent transpositions , which generate it by Proposition 3.4.9.
Theorem 3.6.18 (Presentation of the symmetric group). For , let be the group with generators and relations Then defines an isomorphism . Equivalently, these relations are the Coxeter relations.
Proof. Given , the relation is equivalent to , and to ; so the two lists of relations define the same group. The relations hold in :; has order 3; and are disjoint for , so they commute. Since the generate , Proposition 3.6.14 gives a surjection . It remains to show , by induction on . For , has no generators and is trivial.
Let and let be the subgroup of generated by . These elements satisfy the relations defining , so Proposition 3.6.14 gives a surjection , and by induction. Put and for , and let , a union of right cosets of . We claim that for every . Fix and .
If , then .
If (so ), then .
If , then commutes with each of , so , and ; hence .
If , then . Since commutes with , and commutes with , and since ; hence .
So is again one of the cosets , proving the claim. Since , every element of is a product , and starting from and multiplying on the right by one generator at a time, we stay in . Hence , and . So the surjection is an isomorphism. ∎
Chapter 12 continues the study of presentations, with Cayley graphs, normal forms, the braid group, and .
Proposition 3.6.19 (Every group has a presentation). For every group there are and with .
Proof. Take , regarded as a set, and . By Corollary 3.6.11, is surjective. Let . Since is already normal, , and by the First Isomorphism Theorem. ∎
This presentation is enormous, but it exists. Finding small presentations is an art.
3.6.5 The Word Problem
Presentations raise a fundamental computational question.
Definition 3.6.20 (Word problem). Given a presentation and two words in , the word problem asks whether and represent the same element of ; equivalently, whether .
The following theorem, due to Novikov (1955) and Boone (1959), is beyond the scope of this book; a proof can be found in J. J. Rotman, An Introduction to the Theory of Groups, 4th ed., Chapter 12.
Theorem 3.6.21 (Novikov–Boone). There exists a finitely presented group for which the word problem is undecidable: no algorithm can determine, for every pair of words, whether they represent the same element of .
Note. This is a sobering result. Group presentations look like a convenient computational tool, but they are so expressive that they can encode arbitrary computation: the word problem for a suitable presentation can simulate a Turing machine. This does not make presentations useless. For many specific groups, such as ,, and free groups, the word problem is decidable; but there is no algorithm that works for all finitely presented groups.
Question 3.6.22.
Prove that contains a subgroup isomorphic to . More generally, show that contains a subgroup isomorphic to for every .
Find a presentation for the quaternion group , with ,,,.
Prove that .
Show solution
(a) Let , fix , and let . By the universal property there is a homomorphism with . We show that is injective; then . For this is the subgroup .
Let be a reduced word in the , written in grouped form with ,, and . Since , Every exponent of is nonzero, and every interior exponent of is nonzero. Deleting the outer factors and if their exponents are zero, we obtain a grouped form in which adjacent letters differ and all exponents are nonzero. This is a reduced word, and it contains , so it is not empty. Hence ,, and is injective.
(b) We show ; the relations say ,, and .
The relations hold in :;; and . Also and generate , since ,, and . So we get a surjection from the presented group onto .
has at most 8 elements: In (writing for their images), , so and , and every element is a product of nonnegative powers of and . The relation gives , so we can move every to the right: every element is with . Using and , we may take and . So , and .
(c) Let , and write for the images of the generators in .
A surjection onto : Send and . The relations hold: ,, and , whose square is . The subgroup generated by and contains elements of orders 2 and 3, so its order is divisible by 6, and it is all of . By Proposition 3.6.14 we get a surjection .
has at most 6 elements: From and we get , so and hence for all . Moving every to the right, every element of is with and . So , and .