Todd–Coxeter algorithm

Last updated

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.

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 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 .

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 ith row and jth 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 jth column is defined (if known) to be k, where .

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

Related Research Articles

Abelian group Commutative group (mathematics)

In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With the addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel.

In linear algebra, the determinant is a scalar value that can be computed from the elements of a square matrix and encodes certain properties of the linear transformation described by the matrix. The determinant of a matrix A is denoted det(A), det A, or |A|. Geometrically, it can be viewed as the volume scaling factor of the linear transformation described by the matrix. This is also the signed volume of the n-dimensional parallelepiped spanned by the column or row vectors of the matrix. The determinant is positive or negative according to whether the linear mapping preserves or reverses the orientation of n-space.

Lagranges theorem (group theory) group theory

Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph-Louis Lagrange.

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 a set R of relations among those generators. We then say G has presentation

In linear algebra, an orthogonal matrix is a square matrix whose columns and rows are orthogonal unit vectors.

Matrix multiplication Mathematical operation in linear algebra

In mathematics, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The result matrix, known as the matrix product, has the number of rows of the first and the number of columns of the second matrix.

Weyl group Subgroup of a root systems isometry group

In mathematics, in particular the theory of Lie algebras, the Weyl group of a root system Φ is a subgroup of the isometry group of the root system. Specifically, it is the subgroup which is generated by reflections through the hyperplanes orthogonal to the roots, and as such is a finite reflection group. Abstractly, Weyl groups are finite Coxeter groups, and are important examples of these.

In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections. Indeed, the finite Coxeter groups are precisely the finite Euclidean reflection groups; the symmetry groups of regular polyhedra are an example. However, not all Coxeter groups are finite, and not all can be described in terms of symmetries and Euclidean reflections. Coxeter groups were introduced as abstractions of reflection groups, and finite Coxeter groups were classified in 1935.

In mathematics, the GrassmannianGr(k, V) is a space which parameterizes all k-dimensional linear subspaces of the n-dimensional vector space V. For example, the Grassmannian Gr(1, V) is the space of lines through the origin in V, so it is the same as the projective space of one dimension lower than V.

In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information about the representation in a more condensed form. Georg Frobenius initially developed representation theory of finite groups entirely based on the characters, and without any explicit matrix realization of representations themselves. This is possible because a complex representation of a finite group is determined by its character. The situation with representations over a field of positive characteristic, so-called "modular representations", is more delicate, but Richard Brauer developed a powerful theory of characters in this case as well. Many deep theorems on the structure of finite groups use characters of modular representations.

In group theory, a field of mathematics, a double coset is a collection of group elements which are equivalent under the symmetries coming from two subgroups. More precisely, let G be a group, and let H and K be subgroups. Let H act on G by left multiplication while K acts on G by right multiplication. For each x in G, the (H, K)-double coset of x is the set

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in where is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.

In mathematics, a (B, N) pair is a structure on groups of Lie type that allows one to give uniform proofs of many results, instead of giving a large number of case-by-case proofs. Roughly speaking, it shows that all such groups are similar to the general linear group over a field. They were introduced by the mathematician Jacques Tits, and are also sometimes known as Tits systems.

Dihedral group of order 6 Non-commutative group with 6 elements

In mathematics, D3 (sometimes also denoted by D6) is the dihedral group of degree 3, which is isomorphic to the symmetric group S3 of degree 3. It is also the smallest possible non-abelian group.

In cryptography, XTR is an algorithm for public-key encryption. XTR stands for 'ECSTR', which is an abbreviation for Efficient and Compact Subgroup Trace Representation. It is a method to represent elements of a subgroup of a multiplicative group of a finite field. To do so, it uses the trace over to represent elements of a subgroup of .

In mathematics, the Burnside ring of a finite group is an algebraic construction that encodes the different ways the group can act on finite sets. The ideas were introduced by William Burnside at the end of the nineteenth century. The algebraic ring structure is a more recent development, due to Solomon (1967).

In the theory of quantum communication, the entanglement-assisted stabilizer formalism is a method for protecting quantum information with the help of entanglement shared between a sender and receiver before they transmit quantum data over a quantum communication channel. It extends the standard stabilizer formalism by including shared entanglement . The advantage of entanglement-assisted stabilizer codes is that the sender can exploit the error-correcting properties of an arbitrary set of Pauli operators. The sender's Pauli operators do not necessarily have to form an Abelian subgroup of the Pauli group over qubits. The sender can make clever use of her shared ebits so that the global stabilizer is Abelian and thus forms a valid quantum error-correcting code.

In ring theory and Frobenius algebra extensions, areas of mathematics, there is a notion of depth two subring or depth of a Frobenius extension. The notion of depth two is important in a certain noncommutative Galois theory, which generates Hopf algebroids in place of the more classical Galois groups, whereas the notion of depth greater than two measures the defect, or distance, from being depth two in a tower of iterated endomorphism rings above the subring. A more recent definition of depth of any unital subring in any associative ring is proposed in a paper studying the depth of a subgroup of a finite group as group algebras over a commutative ring.

In the mathematical field of group theory, an Artin transfer is a certain homomorphism from an arbitrary finite or infinite group to the commutator quotient group of a subgroup of finite index. Originally, such mappings arose as group theoretic counterparts of class extension homomorphisms of abelian extensions of algebraic number fields by applying Artin's reciprocity maps to ideal class groups and analyzing the resulting homomorphisms between quotients of Galois groups. However, independently of number theoretic applications, a partial order on the kernels and targets of Artin transfers has recently turned out to be compatible with parent-descendant relations between finite p-groups, which can be visualized in descendant trees. Therefore, Artin transfers provide a valuable tool for the classification of finite p-groups and for searching and identifying particular groups in descendant trees by looking for patterns defined by the kernels and targets of Artin transfers. These strategies of pattern recognition are useful in purely group theoretic context, as well as for applications in algebraic number theory concerning Galois groups of higher p-class fields and Hilbert p-class field towers.

In geometry, H. S. M. Coxeter called a regular polytope a special kind of configuration.