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 by means of a presentation. Sometimes one can show easily that if any group has the property in question, then
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 is a way of describing
by means of generators (that is, elements of some subset
of
such that every element of
can be written as a product of elements of
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 be the symmetry group of a square, let
be a rotation through
anticlockwise and let
be a reflection about one of the main diagonals of the square. It is not hard to check that every element of
can be written in the form
, where
and
. It is also not hard to prove that
This allows us to deduce the multiplication table of . For instance, let us work out the product of
and
. Note first that
. Also,
(since if you write out the product on the right-hand side and cancel out all the internal
you end up with the left-hand side). From these two facts it follows that
. Returning to the product
, the observations we have just made show that it equals
, which equals
, which equals
.
We may therefore say that in the group there are no equations satisfied by
and
that cannot be deduced from the equations
,
, and
. The last equation can be rewritten as
. We say that
is a presentation of
.
General discussion
Informally speaking, if you are given a set of generators of a group
and a set of ways of making the identity of
out of those generators and their inverses, then this is called a presentation of
if the entire multiplication table of
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 and a set of "words" formed from those symbols and their inverses (things like
), we can define a group
as follows: the symbols
are called generators, the specified words are called relations, and the elements of
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
.) 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 is the group generated by the two symbols
and
, and that the set of relations was
,
and
. Then a word such as
is equivalent to
, since we are allowed to insert
(which is longhand for
). We can then insert the pair
after the second
, obtaining
. Then we can cancel out the
to obtain
. Inserting another
, this time before the first
, we can can again cancel a
, obtaining the word
. And doing the same again results in the word
. Finally, inserting the word
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 ,
and their inverses is equivalent to exactly one word of the form
with
and
. 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, and
, say. It is required that
. If we want it to be infinite, then the bigger the group is, the better. And the fewer relations we have between
and
, 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
will.
It remains to prove that this group really is infinite. To do this we shall find a standard form for the elements of : 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 and
with the property that no generator appears more than twice in a row. For example, the words
and
belong to the collection, but
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 and
can be replaced by
and
, respectively. (This is proved by inserting
or
and cancelling out an inverse pair.) Next, note that if any word contains a string of at least three
s or at least three
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 and
by
and
, respectively, and then repeatedly choose the first string of three identical letters and eliminate it. Let us now show that inserting
or
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
or
. 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
into which we have inserted
to obtain a string such as
, then when we come to that string we will first eliminate
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 . If we did so, then an obvious way of guaranteeing that the group was infinite would be to show that some element
of
had infinite orbit. (The orbit of
is the set of all images of
by transformations in the group.)
It then might occur to us to think of the two generators as permutations of , and then to turn the problem round: can we find an infinite set
and two permutations of
that have order 3 (or equivalently that are products of disjoint 3-cycles), such that some
in
has infinite orbit? Once we think of it this way the answer becomes obvious. We may as well let
be
and we may as well let
be
. Let
and
be the two products of 3-cycles. If we want
to have infinite orbit then we want to be able to compose
and
repeatedly to produce an infinite sequence of images. Without loss of generality, one of the 3-cycles that makes up
is
. That gives us
,
and
in the orbit of
. We could then let
be one of the 3-cycles that makes up
, which means that the orbit of
contains the set
. Continuing in this way leads to the example (which is one of many)
and
.
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 ...
![]() |