Homomorphisms and Tietze transformations

Section 1.6 Homomorphisms and Tietze transformations

Let's return to group presentations. In the previous lectures we drew Cayley graphs for \(D_{6 \times 3}\) and \(\ZZ^2\text{,}\) we will now try to compute presentations. Before continuing a word of caution: in general, working with presentations is very tricky. Specifically (and we will discuss this properly in a couple lectures) there is not general procedure which determines if a finite presentation gives a nontrivial group.

Let's start with a presentation for \(D_{2\times 3}\text{.}\) We saw in Section 1.5 that \(D_{2\times 3}\) was generated by elements \(\rho,r\text{.}\) Therefore by the universal property of free groups there is a surjective homomorphism:

\begin{align*} \amp \varphi: F(r,\rho) \onto D_{2\times 3}\\ \amp \Rightarrow D_{2\times 3} \approx F(r,\rho)/\ker(\varphi) \end{align*}

and we are left to find a normal generating set for \(\ker(\varphi)\text{.}\) We must be careful because adding relations has consequences, so we must not add too many. We first note that the following elements are trivial in \(D_{2\times 3}\text{:}\)

\begin{equation*} \rho\rho\rho=_{D_{2\times 3}} rr =_{D_{2\times 3}} r\rho r \rho =_{D_{2\times 3}} 1. \end{equation*}

It therefore follows that \(\ncl{\rho\rho\rho,rr,r\rho r\rho} \leq \ker\varphi\) which means that there is a surjective homomorphism

\begin{equation} \pres{r,\rho}{\rho\rho\rho,rr,r\rho r\rho}\onto D_{2\times 3}.\label{eq_d6_pres}\tag{1.6.1} \end{equation}

In other words, we have not added too many relations, we must now verify that we have added sufficiently many relations. In order to show this we will use a normal forms argument. We will show that for the group \(H = \pres{r,\rho}{\rho\rho\rho,rr,r\rho r\rho}\text{,}\) we will be able to use the relations to rewrite any element as

\begin{equation} w(r,\rho) =_H \rho^i r^j; 0\leq i \leq 2, 0\leq j \leq 1\label{eq_d6_nf}\tag{1.6.2} \end{equation}

so that \(H\) has only 6 elements and there fore the mapping (1.6.1) is not only surjective, but also injective and therefore and isomorphism.

The relations \(\rho\rho\rho=1\) and \(rr=1\) imply that any word \(w(\rho,r)\) in \(H\) can be written as an alternation of powers of \(\rho\) of exponent between 0 and 2, and of the letter \(r\text{,}\) for example

\begin{equation*} \rho^2 r \rho^2 r \rho r \rho. \end{equation*}

We now want to show that any word can be brought to the desired form.

Suppose that the final factor was of the form \(\rho^m\) so that

\begin{equation*} w = \cdots r \rho^m \end{equation*}

then we can splice-in the inverse of a relation so that:

\begin{equation*} w = \cdots r \rho \rho^{m-1} = \cdots r \rho (\rho^{-1}r^{-1}\rho^{-1}r^{-1})\rho^{m-1} = \cdots \rho^{-1}r^{-1} \rho^{m-1} \end{equation*}

and since

\begin{equation*} r^{-1} = r^{-1}(rr) =r \end{equation*}

we have

\begin{equation*} w = \cdots\rho^{-1}r \rho^{m-1} \end{equation*}

repeating this process removes the last \(\rho\) power syllable. This is progress, but the argument is tiresome!

Although we could do everything by splicing in and deleting relations, applying elementary reductions and their inverses, we can also just use group theory to replace subwords by equal elements.

In \(H\) we have

\begin{equation} r \rho r \rho =1 \Rightarrow r \rho = \rho^{-1}r^{-1} = \rho^2 r \label{eq_d6_commute}\tag{1.6.3} \end{equation}

which means we can can simply replace any subword \(\cdots r\rho \cdots\) by \(\cdots \rho^2r\cdots \text{.}\) In this manner, we can "commute" all the \(\rho\) symbols to the left of the word, giving \(w = \rho^k r^j\text{,}\) and since \(\rho^3=r^2=1\) the exponents \(k,j\) can be taken to be division remainders so we can rewrite any word in \(H\) as in (1.6.2). Therefore the 3 relations \(\rho\rho\rho, rr, r\rho r\rho\) ensure the group has 6 elements.

Let us now consider homomorphisms given from groups with presentations.

Lemma 1.6.1.

Let \(G\) be some group and let \(H = \pres X R\) be a group given by a presentation. A mapping \(\varphi^*:X \to G\) extends to homomorphism \(\varphi:H \to G\) if and only if for each \(r(X) = x_1^{\epsilon_1}\cdots x_n^{\epsilon_n} \in R\text{,}\) where \(x_i \in X, \epsilon_i \in \{\pm 1\}\) upon substitution in \(G\) we get:

\begin{equation*} \varphi^*(x_1)^{\epsilon_1} \cdots \varphi^*(x_n)^{\epsilon_n} =_G 1. \end{equation*}

One consequence of this equations. Let \(G\) be a group, let \(x_1,\ldots,x_n\) be a collection of unknowns and consider a system of equations:

\begin{equation*} \mathcal{E} :\left\{ \begin{array}{l} r_1(X) = x_{i_{11}}^{\epsilon_{11}}\cdots x_{i_{1c_1}}^{\epsilon_{1c_1}}=_G 1\\ \cdots\\ r_m(X) = x_{i_{m1}}^{\epsilon_{m1}}\cdots x_{i_{mc_m}}^{\epsilon_{mc_m}}=_G 1\\ \end{array} \right., \end{equation*}

where \(x_{i_{jk}} \in X\) and \(\epsilon_{jk} \in \{\pm 1\}\text{.}\) Then the solutions of \(\mathcal E\) are precisely the given by the homomorphisms

\begin{equation*} \pres{x_1,\ldots,x_n}{r_1,\cdots,r_m} \to G. \end{equation*}

As we saw in the previous lecture, different choices of generating sets gave different Cayley graphs. We will now describe all possible presentations of a group.

Let \(\mathcal P = \pres X R\) be a presentation (not a group, but a formal presentation) and consider the following three Tietze transformations.

T1: The dictionary transformation.
\begin{equation*} \pres X R \to \pres{X \cup \{y\}}{R\cup\{y^{-1}w(X)\}}, \end{equation*}
where \(y \not\in X\) and \(w(X)\) is a word in \(X\text{.}\) Informally, add a new symbol for an element \(y\) and say that
\begin{equation*} y = w(X) \Leftrightarrow y^{-1}w(X)=1. \end{equation*}
So that they new symbol \(y\) is just "shorthand" for the element \(w(X)\text{.}\)
T2: Add a redundant relation.
\begin{equation*} \pres X R \to \pres{X}{R\cup\{r'\}}, \end{equation*}
where \(r' \in \ncl R\text{.}\) Informally, add a relation \(r'\) which is already a consequence of the relations in \(R\text{.}\)
T3: Rename a symbol. Take some symbol \(z \not\in X\text{,}\) take \(X'=(X\setminus \{x\})\cup\{z\}\) and do
\begin{equation*} \pres X R \to \pres{X'}{R'}, \end{equation*}
where \(R'\) is obtained by replacing every instance of \(x\) by \(z\) in every word in \(R.\)

Exercise 1.6.1.4 is to show that these transformations yield presentations defining isomorphic groups. Note that the inverse of T1 involves deleting a generator and a very specific type of relation and the inverse of T2 involves removing a relation that is a consequence of the remaining relations.

As promised we have the following:

Theorem 1.6.2.

Two finite presentations \(\pres X R\) and \(\pres Y S\) define isomorphic groups if and only if \(\pres Y S\) can be obtained from \(\pres X R\) by a sequence of Tietze transformations and their inverses.

The proof is deferred to Exercise 1.6.1.5.

Exercises 1.6.1 Exercises

1.

Prove that

\begin{equation*} \ZZ^2 = \pres{a,b}{a^{-1}b^{-1}ab}\text{.} \end{equation*}

Hint: Use the same approach as for \(D_{2\times 3}\text{,}\) use the normal forms \(a^nb^m, n,m \in \ZZ\text{.}\)

2.

Prove Lemma 1.6.1.

3.

Deduce the result of (1.6.3), namely that we can substitute \(r\rho\) by \(\rho^2 r\text{,}\) only by using insertions and deletions of relations, elementary cancellations or their inverses. Or at least try and appreciate how useful the axioms of group theory and generalized associativity are.

4.

Prove that all three Tietze transformations give isomorphisms.

5.

Prove Theorem 1.6.2.

Hint: One direction is obvious. To show the converse one approach is to construct an intermediate presentation

\begin{equation*} \pres{X \cup Y}{ R \cup S \cup D} \end{equation*}

which is obtainable from \(\pres X R\) and from \(\pres Y S\) by a sequence of Tietze transformations. \(D\) will be a bunch of dictionary relations.

Some dictionary relations will be needed. To find them consider an isomorphism \(\varphi: \pres X R \to \pres Y S.\) This will map each \(x \in X\) to some word in \(Y\text{.}\) You will also need \(\varphi^{-1}\) and add relations.