Intermediate Group Theory (5)

Free Groups

To motivate the concept of free groups, let’s consider some typical group G and elements ab of G. Recall that H=\left<a,b\right>, the subgroup generated by {ab}, 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 {ab}. What does H look like? It certainly contains all expressions in ab and their inverses:

e, a^{-1}, b^2, ab^{-1}, a^3 b^2 a^{-1}, b^6 a b^{-2}a^2, \ldots

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. The free group generated by S, denoted F(S), is the set of all words in the set of abstract symbols \{s, s^{-1} : s\in S\}, together with “e”. Group product is given by concatenation and simplification, via s * s^{-1} = e.

Hence, the free group generated by a singleton set is isomorphic to Z. The free group generated by {ab} 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 i:S \to F(S) which sends s\in S to a single-character word “s” in F(S).

Universal Property. For any function f:S \to G to a group G, there is a unique group homomorphism g:F(S) \to G such that g\circ i=f.

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

e, a^{-1}, b^2, ab^{-1}, a^3 b^2 a^{-1}, b^6 a b^{-2}a^2, \ldots

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

e, f(a)^{-1}, f(b)^2, f(a)f(b)^{-1}, f(a)^3 f(b)^2 f(a)^{-1}, f(b)^6 f(a) f(b)^{-2} f(a)^2, \ldots

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

\text{Fun}(S, G) \cong \text{Hom}(F(S), G),\quad g\circ i\leftrightarrow g,

where Fun(XY) is the set of all functions X → Y and Hom(GH) 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 S3 which is generated by x = (1, 2, 3) and y = (1, 2). Thus, corresponding to the map {ab} → S3 which takes ab to (1, 2, 3), (1, 2) respectively, there is a surjective group homomorphism:

g : F(\{a,b\}) \to S_3, \quad a \mapsto x=(1, 2, 3), b \mapsto y=(1, 2).

The kernel N then gives an isomorphism F({ab})/N ≡ S3. What kind of elements lie in N? These comprise of all strings in ab, such that if we substitute them with xy respectively, the result is the identity element of S3. For example, since x^3 = y^2 = e, we must have a^3, b^2 \in N. Likewise, since yxy = (1, 3, 2) = x^2 we also have baba^{-2} \in N.

Thus, the normal subgroup H of F({ab}) 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({ab})/H can be represented by aibj for some integers i and j;
  • since a3 and b2 are in H, we can take i = 0, 1, 2 and j = 0, 1;
  • so F({ab})/H has at most 6 elements, and the surjective map F({ab})/H → F({ab})/N is bijective since its image has 6 elements exactly. ♦

Now we consider the general case.

Definition Let S be a set and F(S) be the free group on S. Consider a subset T \subseteq F(S). The group generated by S with relations in T is 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 {ab} with relations a^3 = b^2 = baba^{-2} = e is isomorphic to S3. A common way to write this group is:

G = \left<a, b : a^3 = b^2 = baba^{-2} = e\right>  or  G = \left<a, b : a^3 = b^2 = e, ba = a^2 b\right>.

Example 1. Prove that the relations a^3 = b^2 = e are not sufficient to define S3.

Proof. In short, we need to show a3 and b2 do not generate the normal subgroup N in the epimorphism F({ab}) → S3 which maps ab 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 a3 and b2.

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({ab})/N → Z/6

which sends ab to 2, 3 respectively. But we already know F({ab})/N is isomorphic to S3. So this gives an epimorphism S3 → 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 → cx. Prove that this group is isomorphic to the group generated by ab with relations a2b2e.

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

F(\{a,b\})/N(a^2, b^2) \to G, \quad a \mapsto f, b\mapsto g.

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 cx.
  • injectivity: on the LHS, since a2 and b2 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 → xn 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 G = H \rtimes K is isomorphic to the group generated by {ab} with relation baa-1b.

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 m(i, j), 1 \le i, j\le n 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 group is the group generated by elements s_1, s_2, \dots, s_n and relations (s_i s_j)^{m(i,j)} = e for any i, j.

In particular, we have s_i^2 = e for all i. For m(ij) = 2, this just means s_i s_j s_i s_j = e \implies s_i s_j = s_j s_i since s_i^2 = s_j^2 = e. It turns out the word problem for a reflection group is effectively solved. Furthermore, given any string of the si‘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. ]

This entry was posted in Notes and tagged , , , , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s