Finitely Presented & Infinite Groups

Most of the group theory covered so far in this app deals with groups that are finite from the start: permutation groups, matrix groups, PC-groups. But a huge part of computational group theory is about groups that may be infinite, given only by generators and defining relations. Magma calls these finitely presented groups (fp-groups), and around them sits a whole family of related categories: free groups, abelian groups given by presentations, polycyclic groups, braid groups, rewriting systems, automatic groups, straight-line programs, and finitely presented semigroups and monoids.

This lesson is a survey, not a deep dive. The goal is to give you a mental map — what each category is for and when you'd reach for it — rather than to walk through every intrinsic. There are roughly a dozen chapters behind this one lesson; treat it as a table of contents you can return to.

Why "finitely presented" is hard

A finitely presented group is given as < generators | relations >: a free group on some generators, modulo a set of relator words. This is an extremely expressive way to describe a group — almost any group you can write down on paper is naturally an fp-group — but it comes at a cost. The word problem (deciding whether a word represents the identity) is undecidable in general for fp-groups, a result proved by Novikov in 1955. Every algorithm in this area is therefore necessarily partial: it may succeed on your group, or it may run forever or fail outright. Choosing the right tool for a given fp-group — Todd-Coxeter, a rewriting system, automatic structure, or something else — is much of the practical skill involved.

Free groups and free abelian groups

Before presentations make sense, you need the free objects they're quotients of. FreeGroup(n) builds the free group of rank n (category GrpFP, words are just reduced strings in the generators and their inverses, no relations at all), and FreeAbelianGroup(n) builds its abelian analogue (category GrpAb). Every finitely presented group, abelian or not, is constructed as a quotient of one of these.

> F<x, y> := FreeGroup(2);
> A := FreeAbelianGroup(2);

Finitely generated abelian groups get their own dedicated chapter (GrpAb) separate from general fp-groups, because their structure theory — invariant factors, direct sums of cyclic groups — is completely understood and much cheaper to compute with than the general case.

Finitely presented groups: the core machinery

The GrpFP chapter is the heart of this area, and it's one of the largest chapters in the whole Handbook. A group is created with quo< F | R > or FPGroup< X | R > from a free group F and a list of relators R. Once you have such a group, Magma offers: Tietze transformations to simplify a presentation, the Todd-Coxeter procedure to enumerate cosets of a subgroup of finite index (the workhorse behind most other fp-group algorithms), tools for working with finite-index subgroups via their coset tables, the Reidemeister-Schreier algorithm to derive a presentation for a subgroup, searches for homomorphisms onto permutation or PC-groups, and property tests such as finiteness, perfectness, and small cancellation. Because this territory is so large, there is a separate short "intro" chapter (GrpFPInt) that walks new users through the handful of intrinsics that matter most before sending them to the full reference.

> Q<a, b> := quo< F | x^2, y^3, (x*y)^5 >;
> #Q;
60

Polycyclic and braid groups: special classes with better algorithms

Two chapters specialize the general fp-group picture to classes where the word problem is solvable. General polycyclic groups (GrpGPC) are possibly-infinite groups possessing a polycyclic presentation — a subnormal series with cyclic factors, generalizing the finite PC-groups you may already know from the GrpPC chapter. Braid groups (GrpBrd) are the classical groups $B_n$ generated by Artin's generators with the braid relations; Magma supports both the Artin presentation and the Birman-Ko-Lee presentation, and provides braid-specific algorithms (e.g. normal forms via Garside theory) rather than generic fp-group methods, because braid groups' extra structure makes bespoke algorithms far more efficient.

> B := BraidGroup(4);

Rewriting systems and automatic groups: attacking the word problem directly

Three chapters wrap Derek Holt's KBMAG package to give Magma-level access to Knuth-Bendix completion. GrpRWS builds a rewrite group by running Knuth-Bendix on a monoid presentation of an fp-group, producing (if completion succeeds) a confluent rewriting system whose reduction machine solves the word problem efficiently. MonRWS does the same thing one level more general, for monoids rather than groups. GrpAtc goes further still: it constructs an automatic structure — a family of finite state automata witnessing the "fellow traveller" property of the group's Cayley graph — which also makes equality and enumeration decidable, and includes a procedure to test whether a group is word hyperbolic, an important subclass of automatic groups arising from Gromov's theory. All three techniques can fail to terminate on genuinely hard groups, but when they succeed they turn an undecidable-in-general problem into an efficient decision procedure for the specific group at hand.

Straight-line programs: words as expression trees

GrpSLP is a more technical, "under the hood" category. A straight-line program represents a group word not as a flat list of generator-exponent pairs but as an expression tree with shared subexpressions (products, powers, conjugates). This makes evaluating a homomorphism defined on the generators dramatically faster when words are long and repetitive, since common subwords are computed once. You'll mostly meet SLPs indirectly, as the representation other Magma algorithms use internally to pass around long words efficiently.

Semigroups and monoids

Finally, SgpFP extends the fp-group idea to semigroups: FreeSemigroup(n) and FreeMonoid(n) are the free objects, and finitely presented semigroups/monoids are built as quotients of them by relations, with much of the same flavor (and much of the same undecidability) as the group case.

The big picture

When you meet an infinite or presentation-defined group in Magma, the questions to ask are: is it abelian (use GrpAb)? Does it have extra structure like being polycyclic or a braid group (use GrpGPC/GrpBrd)? Do I just need to decide the word problem (try GrpRWS or GrpAtc)? Or am I doing genuinely general combinatorial group theory (use GrpFP and its Todd-Coxeter-based toolkit)? This map is the starting point for answering that question.