Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Todd–Coxeter algorithm
Summary
In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets (given by the left multiplication action). If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relations.
The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the index of H in G is finite. On the other hand, for a general pair consisting of a group presentation and a subgroup, its running time is not bounded by any computable function of the index of the subgroup and the size of the input data.
One implementation of the algorithm proceeds as follows. Suppose that , where is a set of generators and is a set of relations and denote by the set of generators and their inverses. Let where the are words of elements of . There are three types of tables that will be used: a coset table, a relation table for each relation in , and a subgroup table for each generator of . Information is gradually added to these tables, and once they are filled in, all cosets have been enumerated and the algorithm terminates.
The coset table is used to store the relationships between the known cosets when multiplying by a generator. It has rows representing cosets of and a column for each element of . Let denote the coset of the ith row of the coset table, and let denote generator of the jth column. The entry of the coset table in row i, column j is defined to be (if known) k, where k is such that .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.