Intermediate Group Theory (5)

Free Groups

To motivate the concept of free groups, let’s consider some typical group G and elements a, b of G. Recall that $H=\left<a,b\right>$ , 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:

$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 {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 $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 {a, b} 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(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₃ which is generated by x = (1, 2, 3) and y = (1, 2). Thus, corresponding to the map {a, b} → S₃ which takes a, b 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({a, b})/N ≡ S₃. 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₃. 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({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ⁱb^j for some integers i and j;
since a³ and b² 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.

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 {a, b} with relations $a^3 = b^2 = baba^{-2} = e$ is isomorphic to S₃. 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 S₃.

Proof. In short, we need to show a³ and b² do not generate the normal subgroup N in the epimorphism F({a, b}) → S₃ 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³ and b².

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₃. So this gives an epimorphism S₃ → 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² = b² = 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

$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 c–x.
injectivity: on the LHS, since a² and b² 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)ⁿ or (gf)ⁿ.
- 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 $G = H \rtimes K$ is isomorphic to the group generated by {a, b} with relation ba = a^-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(i, j) = 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 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. ]

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages