Take the 2-minute tour ×

If you have a group, (say you have group table or any other information), is there an algorithm to find the group presentation? What is the general way of finding presentation of a group?

share|improve this question
Joke: Sure! Just pick generators and figure out the kernel of the canonical map from the corresponding free group to your group! –  Dylan Wilson Mar 3 '11 at 5:18
More realistic: I don't think so. –  Dylan Wilson Mar 3 '11 at 5:21
Or even better/worse, take every element as generator and every product $g\cdot h = gh$ as relation :-) –  Myself Mar 3 '11 at 5:24
If you "have" a group, then a description of this group in the way that you "have it" should give you a way of presenting it. This will generally not be the most "efficient" or "natural" or "elegant" way of presenting the group, but it should nonetheless give you a presentation if you truly "have" the group. Just describe the information that allows you to figure out the products and inverses in the group as your presentation. –  Arturo Magidin Mar 3 '11 at 5:41
@Arturo Magidin: I'm not sure what you mean, e.g figuring out a presentation of $\mathbf{SL}_2(\mathbb Z)$ isn't very easy I think, even though calculating products and inverses is easy. –  Myself Mar 3 '11 at 5:45
show 3 more comments

2 Answers 2

up vote 6 down vote accepted

Here is a very brief description of the method used by computer systems like GAP and Magma to find a presentation of a moderately small finite group (of order up to about $10^7$) on a given generating set $X$. This dates from about 1972 and is due originally to John Cannon.

You start with an initial set of relators $R_0$, which could be empty, or you might include a few obvious short relators like $x^2$. Then run Todd-Coxeter coset enumeration for this presentation over the identity subgroup. It won't complete of course, and the standard tactic is to interrupt it after it has defined $c|G|$ cosets, for some constant $c>1$, such as $c=1.1$. You then look for the first equation between your defined cosets which is true in $G$ but not yet known in your incomplete coset table. This gives the shortest new relator of $G$ that is not an easy consequence of $R_0$, so you adjoin it to $R_0$ and resume the coset enumeration. Then just repeat this process of interrupting the coset enumeration and adding new relators until the coset enumeration completes with $|G|$ cosets. You then have a presentation of $G$.

This tends to produce reasonably good presentations in terms of total relator length, particularly if you retrospectively go through all relators except the last one found, and try removing them to see if they are redundant. The computed presentations will not necessarily be "nice" in the sense that the relators consist of powers, commutators, etc.

There are lots of refinements for handling larger groups, particularly if you do not insist on having the presentation on the given set $X$. For example, for permutation groups with base and strong generating sets, a variant of this method can be used to find a presentation on a set of strong generators.

share|improve this answer
add comment

No, in general there's not an algorithm. In this paper, Bridson and I prove that there are finite sets of integer matrices that generate finitely presented groups, but for which there's no algorithm to compute a presentation.

share|improve this answer
add comment

Your Answer


