Todd–Coxeter algorithm

Todd–Coxeter algorithm

In group theory, the Todd–Coxeter algorithm, discovered 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. 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.

Description of the algorithm

One implementation of the algorithm proceeds as follows. Suppose that G = langle X mid R angle , where X is a set of generators and R is a set of relations and denote by X' the set of generators X and their inverses. Let H = langle h_1, h_2, ldots, h_s angle where the h_i are words of elements of X' . There are three types of tables that will be used: a coset table, a relation table for each relation in R , and a subgroup table for each generator h_i of H . 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 H and a column for each element of X' . Let C_i denote the coset of the "i"th row of the coset table, and let g_j in X' 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 C_k = C_ig_j .

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 R is maintained. Let 1 = g_{n_1} g_{n_2} cdots g_{n_t} be a relation in R , where g_{n_i} in X' . The relation table has rows representing the cosets of H , 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 C_k = C_i g_{n_1} g_{n_2} cdots g_{n_j} . In particular, the (i,t)'th entry is initially "i", since g_{n_1} g_{n_2} cdots g_{n_t} = 1.

Finally, the subgroup tables are similar to the relation tables, except that they keep track of possible relations of the generators of H . For each generator h_n = g_{n_1} g_{n_2} cdots g_{n_t} of H , with g_{n_i} in X' , we create a subgroup table. It has only one row, corresponding to the coset of H itself. It has "t" columns, and the entry in the "j"th column is defined (if known) to be "k", where C_k = H g_{n_1} g_{n_2} cdots g_{n_j} .

When a row of a relation or subgroup table is completed, a new piece of information C_i = C_j g , g in X' , 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 C_i = C_j g and C_j = C_i g^{-1} .

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 C_i = C_j , with i < j . 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 g in X' . (This is needed to guarantee that the algorithm will terminate provided |G : H| is finite.)

When all the tables are filled, the algorithm terminates. We then have all needed information on the action of G on the cosets of H .

See also

* Coxeter group


* J.A. Todd, H.S.M. Coxeter, "A practical method for enumerating cosets of a finite abstract group". Proc. Edinb. Math. Soc., II. Ser. 5, 26-34 (1936). Zbl|0015.10103, JFM|62.1094.02
* H.S.M. Coxeter, W.O.J. Moser, "Generators and relations for discrete groups". Fourth edition. Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas] , 14. Springer-Verlag, Berlin-New York, 1980. ix+169 pp. ISBN 3-540-09212-9 MathSciNet|id=0562913
*Seress, A. "An Introduction to Computational Group Theory" Notices of the AMS, June/July 1997.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Harold Scott MacDonald Coxeter — H. S. M. Donald Coxeter Born February 9, 1907(1907 02 09) London, England …   Wikipedia

  • Word problem for groups — In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a recursively presented group G is the algorithmic problem of deciding whether two words represent the same element. Although it… …   Wikipedia

  • 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 known finite… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • History of group theory — The history of group theory, a mathematical domain studying groups in their various forms, has evolved in various parallel threads. There are three historical roots of group theory: the theory of algebraic equations, number theory and geometry.… …   Wikipedia

  • List of group theory topics — Contents 1 Structures and operations 2 Basic properties of groups 2.1 Group homomorphisms 3 Basic types of groups …   Wikipedia

  • Computational group theory — In mathematics, computational group theory is the study of groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups. The subject has attracted interest because… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”