Presentations of groups

Quick description

If you want to prove that a group exists with certain properties, then the best way to do so may well be to define a group $G$ by means of a presentation. Sometimes one can show easily that if any group has the property in question, then $G$ does. See the article on universal constructions for a more general discussion of this phenomenon.

Prerequisites

Basic group theory.

Disclaimer

This article is incomplete. It is also written by a non-expert and could almost certainly benefit from expert attention.

General discussion

A presentation of a group $G$ is a way of describing $G$ by means of generators (that is, elements of some subset $A$ of $G$ such that every element of $G$ can be written as a product of elements of $A$ and their inverses) and relations (that is, equations that the generators satisfy, from which all other equations in the group can be deduced).

Example 1

For example, let $G$ be the symmetry group of a square, let $\rho$ be a rotation through $90^o$ anticlockwise and let $\sigma$ be a reflection about one of the main diagonals of the square. It is not hard to check that every element of $G$ can be written in the form $\rho^i\sigma^j$ , where $0\leq i\leq 3$ and $0\leq j\leq 1$ . It is also not hard to prove that $\rho\sigma=\sigma\rho^{-1}.$

This allows us to deduce the multiplication table of $G$ . For instance, let us work out the product of $\rho\sigma$ and $\rho^3\sigma$ . Note first that $\sigma\rho\sigma=\sigma\sigma\rho^{-1}=\rho^{-1}$ . Also, $\sigma\rho^k\sigma=(\sigma\rho\sigma)^k$ (since if you write out the product on the right-hand side and cancel out all the internal $\sigma^2$ you end up with the left-hand side). From these two facts it follows that $\sigma\rho^k\sigma=\rho^{-k}$ . Returning to the product $\rho\sigma\rho^3\sigma$ , the observations we have just made show that it equals $\rho\rho^{-3}$ , which equals $\rho^{-2}$ , which equals $\rho^2$ .

We may therefore say that in the group $G$ there are no equations satisfied by $\rho$ and $\sigma$ that cannot be deduced from the equations $\rho^4=1$ , $\sigma^2=1$ , and $\rho\sigma=\sigma\rho^{-1}$ . The last equation can be rewritten as $(\rho\sigma)^2=1$ . We say that $(\rho,\sigma;\rho^4,\sigma^2,(\rho\sigma)^2)$ is a presentation of $G$ .

General discussion

Informally speaking, if you are given a set of generators $\sigma_1,\dots,\sigma_k$ of a group $G$ and a set of ways of making the identity of $G$ out of those generators and their inverses, then this is called a presentation of $G$ if the entire multiplication table of $G$ can be deduced from the fact that these expressions give the identity.

This does not sound like a useful method for building groups, since it appears to be a way of describing a group that has already been defined. However, that appearance is deceptive: given a set of symbols $\sigma_1,\dots,\sigma_k$ and a set of "words" formed from those symbols and their inverses (things like $\sigma_1\sigma_2^{-1}\sigma_1\sigma_1\sigma_3$ ), we can define a group $G$ as follows: the symbols $\sigma_1,\dots,\sigma_k$ are called generators, the specified words are called relations, and the elements of $G$ are all words that can be formed out of the generators and their inverses, with two such words counted as equivalent if one can convert one into the other by cancelling out or inserting relations. (We are also allowed to cancel out or insert inverse pairs, that is, pairs such as $\sigma_2\sigma_2^{-1}$ .) To multiply two words, we just write one after the other. That is, the operation on the group is that of concatenation. (More precisely, given two elements of the group, we choose words in the corresponding equivalence classes, concatenate them, and take the equivalence class of the concatenation. It is not hard to prove that this operation is well-defined.)

Example 1, continued

Returning to the example we had earlier, from this new point of view we would say that $G$ is the group generated by the two symbols $\rho$ and $\sigma$ , and that the set of relations was $\rho^4$ , $\sigma^2$ and $(\rho\sigma)^2$ . Then a word such as $\rho^{-1}\sigma\rho\rho\rho\sigma$ is equivalent to $\rho^{-1}\sigma\rho\sigma\sigma\rho\sigma\sigma\rho\sigma$ , since we are allowed to insert $\sigma\sigma$ (which is longhand for $\sigma^2$ ). We can then insert the pair $\rho^{-1}\rho$ after the second $\sigma$ , obtaining $\rho^{-1}\sigma\rho\sigma\rho^{-1}\rho\sigma\rho\sigma\sigma\rho\sigma$ . Then we can cancel out the $\rho\sigma\rho\sigma$ to obtain $\rho^{-1}\sigma\rho\sigma\rho^{-1}\sigma\rho\sigma$ . Inserting another $\rho^{-1}\rho$ , this time before the first $\sigma$ , we can can again cancel a $\rho\sigma\rho\sigma$ , obtaining the word $\rho^{-1}\rho^{-1}\rho^{-1}\sigma\rho\sigma$ . And doing the same again results in the word $\rho^{-1}\rho^{-1}\rho^{-1}\rho^{-1}$ . Finally, inserting the word $\rho\rho\rho\rho$ at the beginning and then cancelling inverse pairs four times we end up with the identity (represented by the "word of length zero").

Applying this kind of argument more systematically, we can prove that every word in $\rho$ , $\sigma$ and their inverses is equivalent to exactly one word of the form $\rho^i\sigma^j$ with $0\leq i\leq 3$ and $0\leq j\leq 1$ . From this we can also deduce the multiplication table of the group, since the concatenation of two such words is equivalent to exactly one other.

Question

What sorts of problems can be solved by means of presentations? Here is an example.

Example 2

Is there an infinite group generated by two elements, both of order 3?

If you don't happen to know a group with this property, then generators and relations are the obvious method to turn to. Why? Well, we want a group that is generated by two elements, $a$ and $b$ , say. It is required that $a^3=b^3=1$ . If we want it to be infinite, then the bigger the group is, the better. And the fewer relations we have between $a$ and $b$ , the fewer words in the generators and their inverses will be equivalent to each other, so the more likely the group is to be infinite. So if anything is going to work, the group with presentation $(a,b;a^3,b^3)$ will.

It remains to prove that this group really is infinite. To do this we shall find a standard form for the elements of $G$ : that is, a collection of words such that every word in the generators is equivalent to exactly one from the collection.

The set of words is a very obvious one: we take all words in $a$ and $b$ with the property that no generator appears more than twice in a row. For example, the words $aababbaba$ and $bbabbabba$ belong to the collection, but $ababbba$ does not.

Once this set of words has been defined, there are two stages to the rest of the proof (of which only one is really necessary): we must show that any word is equivalent to a word of this form, and that no two words of this form are equivalent. (It is the second fact that will allow us to prove that the group is infinite.)

To prove the first fact, note first that any occurrences of $a^{-1}$ and $b^{-1}$ can be replaced by $a^2$ and $b^2$ , respectively. (This is proved by inserting $a^3$ or $b^3$ and cancelling out an inverse pair.) Next, note that if any word contains a string of at least three $a$ s or at least three $b$ s, then these can be cancelled out. The resulting word is shorter, so the cancelling-out process eventually terminates, and when it does we have a word of the required form.

The above proof gives rise to an algorithm for reducing words to standard form: first replace all $a^{-1}$ and $b^{-1}$ by $aa$ and $bb$ , respectively, and then repeatedly choose the first string of three identical letters and eliminate it. Let us now show that inserting $aaa$ or $bbb$ into a word does not change the output of this algorithm. After the first stage of the algorithm, the effect will still be an insertion of $aaa$ or $bbb$ . As for the second, either we insert the triplet into another triplet that will at some stage be the first one, or we do not. In the first case, if we have a substring such as $abbb$ into which we have inserted $aaa$ to obtain a string such as $abbaaab$ , then when we come to that string we will first eliminate $aaa$ and then we will be back in our original situation. A similar argument shows that inserting an inverse pair makes no difference: at the first stage of the algorithm we will change it into a triplet and then the previous analysis applies.

What if we delete a triplet or an inverse pair? In this case, we can simply reinsert it and apply the algorithm. The above argument shows that the reinsertion does not affect the output, from which it follows that the deletion does not affect the output. (It might have done, because the order in which we remove triplets has now changed.) The proof is complete.

General discussion

The method above has some characteristic advantages and disadvantages. First the main advantage: it was very easy to define the group that turned out to have the desired property, in the strong sense that the definition was not just simple but also simple to think of. Furthermore, the fact that we chose the largest group that satisfied the hypotheses of the question meant that we gave ourselves the best possible chance of finding an example. The main disadvantage of the approach was that once we had defined the example it was not completely straightforward to prove that it was infinite. In fact, it has been shown that this kind of problem cannot be solved systematically: there is no algorithm that will take a set of generators and relations and tell you whether the resulting group is infinite.

Given that the group we defined had to be an example if any example existed, was there any conceivable alternative approach to the problem? Yes. We could have tried to think of an infinite group that we could prove was generated by two elements of order 3. Then coming up with the group would have been significantly harder, but proving that it was infinite might have been significantly easier. And in fact, such an approach is possible, as we shall now show.

Example 2, continued (without presentations)

If we are trying to define an infinite group generated by two elements of order 3, then we might consider defining it as a group of transformations of a set $X$ . If we did so, then an obvious way of guaranteeing that the group was infinite would be to show that some element $x$ of $X$ had infinite orbit. (The orbit of $x$ is the set of all images of $X$ by transformations in the group.)

It then might occur to us to think of the two generators as permutations of $X$ , and then to turn the problem round: can we find an infinite set $X$ and two permutations of $X$ that have order 3 (or equivalently that are products of disjoint 3-cycles), such that some $x$ in $X$ has infinite orbit? Once we think of it this way the answer becomes obvious. We may as well let $X$ be $\mathbb{N}$ and we may as well let $x$ be $1$ . Let $\pi$ and $\sigma$ be the two products of 3-cycles. If we want $1$ to have infinite orbit then we want to be able to compose $\pi$ and $\sigma$ repeatedly to produce an infinite sequence of images. Without loss of generality, one of the 3-cycles that makes up $\pi$ is $(123)$ . That gives us $1$ , $2$ and $3$ in the orbit of $1$ . We could then let $(345)$ be one of the 3-cycles that makes up $\sigma$ , which means that the orbit of $1$ contains the set $\{1,2,3,4,5\}$ . Continuing in this way leads to the example (which is one of many) $\pi=(123)(567)(9\ 10\ 11)\dots$ and $\sigma=(345)(789)(11\ 12\ 13)\dots$ .

General discussion

So far we have talked about defining a group directly. But many of the most powerful uses of presentations are as ways of building new groups out of old ones. Three of these are free products, amalgamated free products, and HNN extensions ...

This article is incomplete. It would be good to have a discussion of these more sophisticated constructions.