Todd–Coxeter algorithm

The Todd - Coxeter algorithm is an algorithm in group theory, which is named after the two British mathematicians John Arthur Todd and Harold Scott MacDonald Coxeter. The algorithm makes it possible to count for a subgroup of a finite group of the sub- classes, when a presentation is given of the group. In particular, enables the algorithm to determine the order of a group.

Algorithm

Let be a finite group and a subgroup of. Todd - Coxeter algorithm is a method to count the cosets of IN. In addition, the algorithm can be also the operation of on the set of cosets determined.

By Todd - Coxeter algorithm leads though with a finite number of steps to the goal, but the computation time is not predictable.

For a calculation of a finite presentation of the group and a finite system of generators of the group must be explicitly specified. Therefore, we suppose, be represented concretely by the generators and relations:

This is implemented as a factor group, the free group on the set and a normal subgroup of that contains. Furthermore, it is assumed that the sub-group with a lot of words in the free group is given: produce their images in the subgroup.

For example, the group is defined by the three generators and relations and as a subgroup of the cyclic subgroup generated:

Since the operations are to be determined in addition to classes and can be described this as a permutation, must be fixed, how they should be explicitly stated. It should be specified that operates from the right. The set of right cosets is called as. To explicitly specify the operation of on that induced by the generating elements permutation is described.

For the operations on the following rules apply:

The first rule is a general property of group operations, which follows from the invertibility of group elements. The second rule applies because the relation represented in the element, and actually the Group operates. Rules 3 and 4 are special characteristics in the operation cosets.

Example

Consider the tetrahedron group of twelve rotational symmetries of a regular tetrahedron. The rotations by the angle at two different vertices clockwise or counter -clockwise are designated respectively. As a result, the rotation around the center of an edge - the product is to be read from right to left - to. There are the following relations:

It will be shown that the above relations define T. But one look at the group. Since the relations are satisfied in the tetrahedral group, the imaging property of factor groups provides a homomorphism. Since x and y generate the group T, the homomorphism is surjective. To prove that is injective, it must be shown that the order of the group G is equal to 12.

To achieve this, one could include the cosets of the trivial subset, and so determine the order of G. However, that would not be very efficient. It is more advantageous to use a non-trivial subgroup H of G, such as that generated by y. This subgroup H has to show for more than the third order, it is sufficient so that the order of H even equal to 3 and the index of H in G is equal to 4. It would follow that G has order 12.

According to the algorithm, the permutation of G is determined, which describes the operation to the amount of the cosets. For the name of cosets for example, using number 1,2,3, ..., where 1 is reserved for the coset H1. Since we do not yet know the number of cosets, you can not even decide how many numbers are needed. During the procedure, gradually new points shall be inserted as soon as they are needed.

The method provides the following table:

For the procedure, the associated permutation results

Since four digits appear, is the index of H in G equals 4 y has order 3, because due to the relation, the order can be the same three highest and it is at least equal to 3, because the y associated permutation has order 3. Thus, the order of G is equal to 12, the permutation is also an isomorphism from T to the subgroup generated by the permutation. One can convince that this is the alternating group of them. Thus, the tetrahedral group T is isomorphic to.