Coset enumeration problem

This article describes a basic computational problem in computational group theory

This article describes a problem in the setup where the group(s) involved is/are defined by means of a presentation -- viz in terms of generators and relations

Description

Given data

A group $G$ is specified by a presentation, viz a generating set $X$ subject to a set of relations $R$. A subgroup $H$ of $G$ is specified (again by means of generators).

Goal

We need to count the number of cosets of $H$ in $G$, and also to explicitly compute the permutation representation of $G$ on the coset space of $H$.

Algorithms

Two popular algorithms

The following are the typical algorithms for this problem:

• The Todd-Coxeter algorithm
• The Knuth-Bendix algorithm

Difficulty with algorithms

The problem is that the algorithms may take very long. This is essentially because even for the trivial groups , the presentations could be arbitrarily complicated.

For finite groups, we have the guarantee that the Todd-Coxeter algorithm for coset enumeration terminates eventually in finitely many steps. However, this finite number could be arbitrarily large even if we restrcti attention to the trivial group.