Finitely presented groups (henceforth referred to as fp-groups) arise in many branches of mathematics and computation plays a significant role in their study. Unfortunately, answering most basic questions about a given fp-group is often computationally difficult. Over the past 50 years a range of computational tools for investigating fp-groups have been developed and most of these are installed in Magma. Some are straightforward to use but others are complicated.
The word problem for fp-groups asks whether there is an algorithm which given any element of an fp-group can decide whether or not it is the identity. In 1955, Novikov showed that there are specific fp-groups for which the word problem is insoluble. Further results show that other decision problems for fp-groups are also insoluble. Consequently, this limits what we can compute for fp-groups. The algorithms (or procedures) that have been developed can provide some information about many fp-groups but there will be many more groups for which they fail.
The Handbook documentation describing the fp-group facilities runs to more than 200 pages. In order to make the material more accessible this chapter is a terse introduction to the more important tools. Less important intrinsics are omitted and advanced features of those intrinsics that are discussed are often also omitted. The hope is that new users will be able to quickly get enough information from this chapter to be able to make straightforward application of the more important intrinsics and then dip into the detailed expositions in chapter FINITELY PRESENTED GROUPS when they become more proficient.
This chapter is concerned with groups defined by general presentations. Before starting this chapter the user should read the (very short) chapter FREE GROUPS on free groups which is assumed knowledge for this chapter. For groups defined by power-conjugate presentations the user should consult chapters FINITE SOLUBLE GROUPS and POLYCYCLIC GROUPS. For users interested in automatic and hyperbolic groups most of the information concerning them can be found in chapter AUTOMATIC AND HYPERBOLIC GROUPS. The complete list of intrinsics for fp-groups together with their advanced features can be found in chapter FINITELY PRESENTED GROUPS.
The intrinsics considered here are designed for doing what is sometimes referred to as combinatorial group theory. A description of the fundamental algorithms for finitely presented groups can be found in Sims [Sim94] or Holt [HEO05]. The facilities provided for fp-groups in Magma fall into the following categories:-
Let X be a finite set of symbols, called generators in this context. Strings can be formed from X by concatenating the symbols x and x - 1 for x ∈X. Defining multiplication ( * ) of strings over X as concatenation and forcing this multiplication rule to satisfy the group axioms puts a group structure on strings over X. In this group the identity is the empty string and the elements are called words. A group of this type is called the free group of rank n, where n is the cardinality of X. These groups are discussed in detail in chapter FREE GROUPS.
A relation is an equality between two words while a relator consists of a word that equals the identity, that is, it is a relation where the right hand side is understood to be the identity. If a set R of non-trivial relations are imposed on F its elements are partitioned into equivalence classes. This set of equivalence classes form a new group. If X and R are both finite the group they define is called a finitely-presented group (abbreviated to fp-group) and is the subject of this chapter. The pair < X | R > is called a presentation for G. Note that any free group of finite rank is also an fp-group where the set R is empty.
The set of relations R can be converted into a set of relators and the relator words generate a subgroup H of F. If N is the normal closure of H in F then the group G is the quotient group F/N. This observation is the basis for the way in which fp-groups are constructed in Magma. The free group of rank n is constructed by the intrinsic FreeGroup(n). Having constructed an appropriate free group F, an fp-group G is constructed by specifying relations on the generators of F that must be satisfied by the corresponding generators of G. The details of how this is achieved are discussed in the following sections.