A presentation for a group G consists of a set X such that every element can be written as a word in G and a set R of relations such that the equivalence classes of words with respect to R correspond to the elements of G. A group G is said to be finitely-presented if both X and R are finite. In that case, G is said to be a finitely-presented group (fp-group).
Two basic properties of an fp-group G frequently sought are (a) whether G is the identity group or a non-trivial group and (b) whether G is finite or infinite. Novikov and Boone have shown that all such questions are undecidable in general. However, Magma has a range of tools that can frequently answer these questions.
The Todd–Coxeter procedure takes a group G and a set of words defining a subgroup H of G and attempts to enumerate the cosets of H in G. The Todd–Coxeter implementation used in Magma is essentially the ACE program of G. Havas and C. Ramsay. The version of this program installed in Magma allows about 109 cosets to be defined in the case of a 2-generator group.
If the procedure terminates the result is a table known as the coset table, which gives the action of G on the cosets and thus provides a permutation representation of G. The coset table of H in G makes it possible to show that G is non-trivial (true if the index of H is greater than 1)), test membership of elements of G in H, determine if H is normal in G, construct a homomorphism φ of G onto a subgroup of Sym(n) defined by the action of G on the cosets of H, and compute the kernel of φ.
If the group G is finite and not too large, then the Todd–Coxeter procedure can be used to enumerate the cosets of the identity and hence determine the order of the group. A much better approach is to try to find a subgroup H of known order and attempt to enumerate its cosets. Enumerating the cosets of the identity subgroup of G gives us the regular permutation representation of G. Tools are available in Magma which will attempt to transform this representation into a faithful permutation representation for G of much smaller degree.
The procedure will not terminate if H has infinite index in G, or if the index is much too large for the computation to fit into the computer's memory. However, even if the index is small, there exist presentations that cause the Todd–Coxeter procedure to define such a large number of redundant cosets that the enumeration will never complete in practice.
It is possible to enumerate the conjugacy classes of subgroups for an fp-group having small index. This employs an algorithm of C. Sims which enumerates the coset tables corresponding to distinct conjugacy classes of subgroups of G. The algorithm constructs the coset tables by using a backtrack algorithm to run through the possible tables but otherwise builds the tables in a similar manner to the Todd–Coxeter procedure. Although it sometimes cannot complete the enumeration for indices as small as 10, it can get much further for many groups. For example, in the case of the infinite triangle group < x,y | x2, y3, (xy)7 > the low index algorithm in Magma finds the 3,037,698 conjugacy classes of subgroups having index not greater than 100 in 414 seconds.
The low index algorithm is very useful. For example, it is a good first choice when attempting to prove that a group is non-trivial. Also it can be used to search for subgroups with certain properties such as having an infinite abelian quotient. Overall, it is a key tool in heuristic algorithms which attempt to prove that a group is infinite.
In 2006 an algorithm was developed by D. Holt and D. Firth which searches for low index normal subgroups (LINS). The algorithm searches for small quotients of G by a systematic enumeration of the possibilities for a composition series for the quotient. It was implemented in Magma by Holt. In favourable circumstances it can search for normal subgroups of index up to 1,000,000. In the case of the triangle group mentioned above, LINS finds the 35 normal subgroups of index not exceeding 100,000 in 1344 seconds.
In the previous subsection techniques have been described for locating subgroups of small index in an fp-group G. The Reidemeister–Schreier algorithm enables the user to construct a presentation for a subgroup H on Schreier generators for H. The main drawback is that the number of generators and the number of relations produced for H are each a multiple of [G,H]. This problem can be reduced somewhat by performing simplification (see below) on the Reidemeister–Schreier presentation. However, once the index [G,H] gets up towards 100 even the simplified presentation may be too huge for some applications.
An alternative function attempts to construct a presentation for H in terms of the generators originally used to define H. This has the advantage that they may be more meaningful to the user and it is likely that there are many fewer of them. This uses a variant of ACE called extended coset enumeration whereby information such as coset definitions are stored as words as the Todd–Coxeter proceeds.
In various situations it is desirable to simplify a presentation. In particular, presentations constructed by the Reidemeister–Schreier algorithm typically have a huge number of unnecessary generators and relations. Tietze transformations comprise four basic operations that can be performed on any presentations with the property that the group defined does not change. Tietze showed that any presentation for G can be obtained from any other presentation for G using only Tietze transformations. Magma contains code due to G. Havas and C. Ramsay for performing simplification of presentations using Tietze transformations.
The simplification program often produces a good result when applied to presentations with many redundant generators and relations; the number of generators is typically reduced to less than 10. However, some of the relations become exceedingly long and this can make subsequent computations perform badly. Two typical operations one wants to do with a subgroup of G is obtain its abelian quotient or some more general quotient such as a p-quotient. Both of these are somewhat forgiving of large presentations.
A tactic often used when investigating an fp-group G is to construct homomorphisms onto groups with solvable word problems and where the group structure can easily be computed. Note that a coset table defines a homomorphism of G onto a permutation group. Below other quotient constructions are listed.
Perhaps the most common question a user wants answered about an fp-group G is whether the group is finite or infinite. As with most computational problems relating to general fp-groups there is no algorithmic solution to the problem. Instead, various procedures are applied in the hope that one will provide an answer. If there is no strong information suggesting one possibility is more likely than the other then equal effort has to be invested in trying to establish each of the possibilities.
The standard approach to proving that a group is finite is to examine the presentation for G and try to identify a subgroup H which is clearly finite. Dihedral groups are often found in a group having some generators of order 2. Then one tries to enumerate the cosets of H in G. If this fails then other choices of H are sought. If the direct enumeration of the cosets of a finite subgroup fails then the techniques of the previous section are applied to try to find non-trivial quotients. The quotients may directly show that G is infinite but if that fails, they can be used to provide a lower bound on the order of G.
There are few useful methods for proving that a group is infinite. By far the most effective is to demonstrate the existence of a subgroup H of G that has an infinite section. The easiest way of doing this is to locate a subgroup of G that has an infinite abelian quotient. The low index subgroups and low index normal subgroups algorithms are an important source of subgroups. If the low index searches are unsuccessful (or there are no subgroups of small enough index to find) quotient groups and their subgroups are another important source. A program of J. Cannon has automated the systematic application of these and other tests to try to establish that an fp-group is infinite. Applied to the fundamental groups of the 11126 hyperbolic 3-manifolds having small volume compiled by J. Weeks the program was able to produce a proof that all but 10 of the these fundamental groups are infinite.
For certain families of fp-groups, presentations are known which provide a solution to the word problem for all groups in that family. A simple example is the class of abelian fp-groups. Five important families supported in Magma are introduced below but will not be discussed further in this document.
A solution to the word problem for finite soluble fp-groups is provided by the power-commutator presentation which defines a normal form for each element and an algorithm (collection) that will normalise an arbitrary word. A group given by a power-commutator presentation is known as a pc-group. A large collection of efficient algorithms has been developed for pc-groups.
The appropriate generalisation of pc-group to an infinite soluble group is the polycyclic group which is a group admitting a subnormal series with cyclic factors. While no practical method is known for deciding whether an infinite fp-group is polycyclic, W. Plesken has described an algorithm for constructing a polycyclic quotient from a general fp-group. Some structural algorithms have been developed for the subclass of polycyclic groups that are nilpotent.
A Coxeter group is one given by a presentation where all the relations have either the form x2 = 1 or (xy)k = 1. They are abstract reflection groups. An algorithm due to B. Brinck and R. Howlett gives a solution to the word problem for these groups. Hence element arithmetic and the calculation of growth functions are supported. Computation with parabolic subgroups, their cosets, and double cosets is also implemented.
The family of infinite groups known as braid groups Bn, 1 < n, can be defined as fundamental groups of a configuration space. They also have an intuitive definition in terms of bunches of strings with a composition operation. The groups have a nice presentation due to Artin which has a solvable word problem. A substantial facility for computing with braid groups has been developed by V. Gebhardt (Magma).
An automatic group is an finitely generated group G together a finite state automata and associated regular languages. Let G have a finite monoid generating set A. Then G is an automatic group if there is a language L over A such that the natural map π: L ↦ G is onto and certain associated languages are regular. Automatic groups have a soluble word problem and a word can be put into normal form in quadratic time. Based on D. Holt's kbmag package, Magma can attempt to find an automatic structure and, if successful, determine finiteness, perform element arithmetic, and compute growth functions.