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 order, coset enumeration gives the order of G as well.
Mathematics includes the study of such topics as quantity, structure (algebra), space (geometry), and change. It has no generally accepted definition.
In mathematics, if G is a group, and H is a subgroup of G, and g is an element of G, then
In mathematics, a group is a set equipped with a binary operation that combines any two elements to form a third element in such a way that four conditions called group axioms are satisfied, namely closure, associativity, identity and invertibility. One of the most familiar examples of a group is the set of integers together with the addition operation, but groups are encountered in numerous areas within and outside mathematics, and help focusing on essential structural aspects, by detaching them from the concrete nature of the subject of the study.
For small groups it is sometimes possible to perform a coset enumeration by hand. However, for large groups it is time-consuming and error-prone, so it is usually carried out by computer. Coset enumeration is usually considered to be one of the fundamental problems in computational group theory.
A computer is a machine that can be instructed to carry out sequences of arithmetic or logical operations automatically via computer programming. Modern computers have the ability to follow generalized sets of operations, called programs. These programs enable computers to perform an extremely wide range of tasks. A "complete" computer including the hardware, the operating system, and peripheral equipment required and used for "full" operation can be referred to as a computer system. This term may as well be used for a group of computers that are connected and work together, in particular a computer network or computer cluster.
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 for many interesting groups (including most of the sporadic groups) it is impractical to perform calculations by hand.
The original algorithm for coset enumeration was invented by John Arthur Todd and H. S. M. Coxeter. Various improvements to the original Todd–Coxeter algorithm have been suggested, notably the classical strategies of V. Felsch and HLT (Haselgrove, Leech and Trotter). A practical implementation of these strategies with refinements is available at the ACE website. [1] The Knuth–Bendix algorithm also can perform coset enumeration, and unlike the Todd–Coxeter algorithm, it can sometimes solve the word problem for infinite groups.
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. If the order of a group G is relatively small and the subgroup H is known to be uncomplicated, 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.
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with involution on A to the group G. If B is another finite generating set for G, then the word problem over the generating set B is equivalent to the word problem over the generating set A. Thus one can speak unambiguously of the decidability of the word problem for the finitely generated group G.
The main practical difficulties in producing a coset enumerator are that it is difficult or impossible to predict how much memory or time will be needed to complete the process. If a group is finite, then its coset enumeration must terminate eventually, although it may take arbitrarily long and use an arbitrary amount of memory, even if the group is trivial. Depending on the algorithm used, it may happen that making small changes to the presentation that do not change the group nevertheless have a large impact on the amount of time or memory needed to complete the enumeration. These behaviours are a consequence of the unsolvability of the word problem for groups.
A gentle introduction to coset enumeration is given in Rotman's text on group theory. [2] More detailed information on correctness, efficiency, and practical implementation can be found in the books by Sims [3] and Holt et al. [4]
