Working out a Group Presentation

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?

Solution 1:

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.

Solution 2:

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.