## Free Groups

To motivate the concept of free groups, let’s consider some typical group *G* and elements *a*, *b* of *G*. Recall that , the subgroup generated by {*a*, *b*}, is defined to be the intersection of all subgroups of *G* containing *a* and *b*. Immediately, we see that *H* satisfies:

- it is a subgroup of
*G*; - any subgroup of
*G*containing both*a*and*b*must contain*H*also.

So in a very real sense, it’s the smallest subgroup of *G* containing {*a*, *b*}. What does *H* look like? It certainly contains all expressions in *a*, *b* and their inverses:

although not all these elements are distinct. On the other hand, the set of all these elements forms a group so *H* is precisely the set of all “words” in *a* and *b*. The idea of a free group is to consider these generic words and form them into a group, with product given by concatenation and simplification.

Definition. Let S be a set. Thefree groupgenerated by S, denoted F(S), is the set of all words in the set of abstract symbols , together with “e”. Group product is given by concatenation and simplification, via .

Hence, the free group generated by a singleton set is isomorphic to **Z**. The free group generated by {*a*, *b*} is the list of all words described above. [ Conceptual quiz: what is the free group generated by the empty set? ]

The intuition behind this is that *F*(*S*) is the “largest” possible group generated by |*S*| elements. The most important feature of *F*(*S*) is its universal property.

Let S be a function and F(S) be the free group generated by S with injection which sends to a single-character word “s” in F(S).

Universal Property. For any function to a group G, there is a unique group homomorphism such that .

To have an idea of what *g* looks like, let’s consider the concrete example of {*a*, *b*} and take the sample words from above:

Then since *g* is a group homomorphism, it has no choice but to map these to:

The correspondence between *f* and *g* can be written as follows:

where Fun(*X*, *Y*) is the set of all functions *X* → *Y* and Hom(*G*, *H*) is the set of group homomorphisms *G* → *H*. From our description of *g*, it’s clear that *g* is surjective if and only if *f*(*S*) generates *G*.

## Generators and Relations

Consider the group *S*_{3} which is generated by *x* = (1, 2, 3) and *y* = (1, 2). Thus, corresponding to the map {*a*, *b*} → *S*_{3} which takes *a*, *b* to (1, 2, 3), (1, 2) respectively, there is a surjective group homomorphism:

The kernel *N* then gives an isomorphism *F*({*a*, *b*})/*N* ≡ *S*_{3}. What kind of elements lie in *N*? These comprise of all strings in *a*, *b*, such that if we substitute them with *x*, *y* respectively, the result is the identity element of *S*_{3}. For example, since , we must have . Likewise, since we also have .

Thus, the normal subgroup *H* of *F*({*a*, *b*}) generated by these three elements is contained in *N*. The question is whether *H*=*N*. The answer is yes: we won’t prove it in detail but merely sketch the outline:

- show that every element of
*F*({*a*,*b*})/*H*can be represented by*a*for some integers^{i}b^{j}*i*and*j*; - since
*a*^{3}and*b*^{2}are in*H*, we can take*i*= 0, 1, 2 and*j*= 0, 1; - so
*F*({*a*,*b*})/*H*has at most 6 elements, and the surjective map*F*({*a*,*b*})/*H*→*F*({*a*,*b*})/*N*is bijective since its image has 6 elements exactly. ♦

Now we consider the general case.

DefinitionLet S be a set and F(S) be the free group on S. Consider a subset . The groupgenerated by S with relations in Tis the quotient F(S)/N(T), where N(T) is the normal subgroup of F(S) generated by T.

For example, we just saw that the group generated by {*a*, *b*} with relations is isomorphic to *S*_{3}. A common way to write this group is:

or .

**Example 1**. Prove that the relations are not sufficient to define *S*_{3}.

**Proof**. In short, we need to show *a*^{3} and *b*^{2} do not generate the normal subgroup *N* in the epimorphism *F*({*a*, *b*}) → *S*_{3} which maps *a*, *b* to (1, 2, 3), (1, 2) respectively. We’ll do this in an indirect manner: suppose, on the contrary, *N* is the normal subgroup generated by *a*^{3} and *b*^{2}.

Now, in the group **Z**/6, elements 2, 3 of also satisfy the relations (3·2 = 2·3 = 0 (mod 6)) and generate **Z**/6. So we get an epimorphism:

*F*({*a*, *b*})/*N* → **Z**/6

which sends *a*, *b* to 2, 3 respectively. But we already know *F*({*a*, *b*})/*N* is isomorphic to *S*_{3}. So this gives an epimorphism *S*_{3} → **Z**/6 which is clearly absurd. ♦

**Example 2**. Consider the group *G* of all bijections of **Z** of the form *x* → *x*+*c* and *x* → *c*–*x*. Prove that this group is isomorphic to the group generated by *a*, *b* with relations *a*^{2} = *b*^{2} = *e*.

**Proof**. The first order of the day is to figure out where to map *a* and *b*. Let’s take *a*, *b* to the maps *f*(*x*) = –*x* and *g*(*x*) = 1-*x* respectively. Clearly *f*(*f*(*x*)) = *g*(*g*(*x*)) = *x* so we do have a homomorphism

It suffices to show the map is bijective.

*surjectivity*: we need to show*G*is generated by*f*and*g*. Indeed,*gf*(*x*) = 1+*x*so we get all translations*x*+*c*. Compose with*f*to get the reflections*c*–*x*.

*injectivity*: on the LHS, since*a*^{2}and*b*^{2}represent the identity, every element can be represented by an alternating sequence …*abab*…, where each side ends in either*a*or*b*. This maps to …*fgfg*… in RHS.- Suppose this result is the identity.
- Since
*f*and*g*have (coeff. of*x*) = -1, there must be an even number of terms, i.e. we have (*fg*)^{n}or (*gf*)^{n}. - But these two functions are respectively
*x*→*x*–*n*and*x*→*x+**n*so they cannot be the identity except when*n*=0, which means …*abab…*is also the identity on the LHS. ♦

**Example 3**. Let *K*=**Z** act on *H*=**Z**, by mapping *m* in *K* to the map *x* →* x*+*m*. We’ll leave it to the reader to prove that the semidirect product is isomorphic to the group generated by {*a*, *b*} with relation *ba* = *a*^{-1}*b*.

## Word Problem

From the above examples, it’s natural to ask for a general algorithm to simplify an element of a group, with given generators and relations. Specifically, we have:

Word Problem. Let G be a group which is generated by finitely many generators, under finitely many relations. Given an arbitrary word (in the generators), determine whether it simplifies to the identity.

In particular, one hopes for a general (Turing) program which takes in a finite set of generators and relations, then determines whether a given word is the identity.

The question was answered negatively by Pyotr Novikov in 1955. In fact, he proved something much stronger: there is a particular finite set of generators and relations, such that no algorithm in the world can possibly take in a given word and determine within finite time whether the said word simplifies to the identity.

But that doesn’t mean the word problem can’t be solved for some particular special classes of groups. For example, we have:

Definition. Let be a collection of positive integers such that m(i, i) = 1 and m(j, i) = m(i, j) > 1 for i ≠ j.A

reflection groupis the group generated by elements and relations for any i, j.

In particular, we have for all *i*. For *m*(*i*, *j*) = 2, this just means since . It turns out the word problem for a reflection group is effectively solved. Furthermore, given any string of the *s _{i}*‘s, one can determine its shortest representation effectively.

*Exercise* : prove that the reflection group is not trivial. [ Hint (highlight to read): define a homomorphism which takes each generator *s* to -1; this defines a homomorphism G → {+1, -1} which takes each generator to -1. The map is surjective and hence G is non-trivial. ]