In
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...
, the Todd–Coxeter algorithm, created by
J. A. Todd and
H. S. M. Coxeter in 1936, is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for solving the
coset enumeration In mathematics, coset enumeration is the problem of counting the cosets of a subgroup ''H'' of a group ''G'' given in terms of a presentation. As a by-product, one obtains a permutation representation for ''G'' on the cosets of ''H''. If ''H'' has a ...
problem. Given a
presentation of a group
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
''G'' by generators and relations and a
subgroup
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
Formally, given a group (mathematics), group under a binary operation  ...
''H'' of ''G'', the algorithm enumerates the
coset
In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...
s of ''H'' on ''G'' and describes the
permutation representation
In mathematics, the term permutation representation of a (typically finite) group G can refer to either of two closely related notions: a representation of G as a group of permutations, or as a group of permutation matrices. The term also refers ...
of ''G'' on the space of the cosets (given by the left multiplication action). If the
order of a group
In mathematics, the order of a finite group is the number of its elements. If a group is not finite, one says that its order is ''infinite''. The ''order'' of an element of a group (also called period length or period) is the order of the sub ...
''G'' is relatively small and the subgroup ''H'' is known to be uncomplicated (for example, a
cyclic group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
), 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
Index (: indexes or indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on the Halo Array in the ...
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
Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...
of the index of the subgroup and the size of the input data.
Description of the algorithm
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 ''i''th row of the coset table, and let
denote generator of the ''j''th column. The entry of the coset table in row ''i'', column ''j'' is defined to be (if known) ''k'', where ''k'' is such that
.
The relation tables are used to detect when some of the cosets we have found are actually equivalent. One relation table for each relation in
is maintained. Let
be a relation in
, where
. The relation table has rows representing the cosets of
, as in the coset table. It has ''t'' columns, and the entry in the ''i''th row and ''j''th column is defined to be (if known) ''k'', where
. In particular, the
'th entry is initially ''i'', since
.
Finally, the subgroup tables are similar to the relation tables, except that they keep track of possible relations of the generators of
. For each generator
of
, with
, we create a subgroup table. It has only one row, corresponding to the coset of
itself. It has ''t'' columns, and the entry in the ''j''th column is defined (if known) to be ''k'', where
. In particular, the last entry is ''H'', since
.
When a row of a relation or subgroup table is completed, a new piece of information
,
, is found. This is known as a ''deduction''. From the deduction, we may be able to fill in additional entries of the relation and subgroup tables, resulting in possible additional deductions. We can fill in the entries of the coset table corresponding to the equations
and
.
However, when filling in the coset table, it is possible that we may already have an entry for the equation, but the entry has a different value. In this case, we have discovered that two of our cosets are actually the same, known as a ''coincidence''. Suppose
, with
. We replace all instances of ''j'' in the tables with ''i''. Then, we fill in all possible entries of the tables, possibly leading to more deductions and coincidences.
If there are empty entries in the table after all deductions and coincidences have been taken care of, add a new coset to the tables and repeat the process. We make sure that when adding cosets, if ''Hx'' is a known coset, then ''Hxg'' will be added at some point for all
. (This is needed to guarantee that the algorithm will terminate provided
is finite.)
When all the tables are filled, the algorithm terminates. We then have all needed information on the action of
on the cosets of
.
See also
*
Coxeter group
In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean ref ...
References
*
*
*
{{DEFAULTSORT:Todd-Coxeter algorithm
Computational group theory