Todd-Coxeter algorithm

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

algorithm

Let be a finite group and a subgroup of . The Todd-Coxeter algorithm is a method of counting the minor classes of in . In addition, the algorithm can also determine the operation of on the set of secondary classes. ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$

The Todd-Coxeter algorithm achieves the goal with a finite number of steps, but the computing time is not predictable.

A finite presentation of the group and a finite generating system of the subgroup must be specified explicitly for a calculation . Therefore, assume that the generators and the relations specifically represent: ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle x_{1},...,x_{m}}$ ${\displaystyle r_{1},...,r_{k}}$

${\displaystyle G=\left\langle x_{1},...,x_{m};r_{1},...,r_{k}\right\rangle }$

This is implemented as a factor group , where the free group is on the set and a normal divisor of which contains. Furthermore, it is assumed that the subgroup is given by a set of words in the free group: whose images produce in the subgroup . ${\displaystyle G}$ ${\displaystyle F/N}$ ${\displaystyle F}$ ${\displaystyle \lbrace x_{1},...,x_{m}\rbrace }$ ${\displaystyle N}$ ${\displaystyle F}$ ${\displaystyle \lbrace r_{1},...,r_{k}\rbrace }$ ${\displaystyle H}$ ${\displaystyle \lbrace h_{1},...,h_{s}\rbrace }$ ${\displaystyle G}$ ${\displaystyle H}$

As an example, let the group be defined by the three generators and the relations and, as a subgroup, the cyclic subgroup generated by : ${\displaystyle G}$ ${\displaystyle x,y,z}$ ${\displaystyle x^{3},y^{2},z^{2},xyz}$ ${\displaystyle H}$ ${\displaystyle z}$

${\displaystyle G=\left\langle x,y,z;x^{3},y^{2},z^{2},xyz\right\rangle }$, generated by ${\displaystyle H}$ ${\displaystyle \lbrace z\rbrace }$

Since the operations on secondary classes are to be determined and these can be described as a permutation representation, it must be determined how these are to be specified explicitly. Let it be established that the right operation is performed. The set of right secondary classes is denoted as. In order to explicitly state the operation from to , the permutation induced by the generating elements will be described. ${\displaystyle G}$ ${\displaystyle Hg}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle x,y,z}$

The following rules apply to operations on : ${\displaystyle {\mathcal {K}}}$

1. Every generator (here:) operates as a permutation. ${\displaystyle x,y,z}$
2. The relation (here:) operates trivially. ${\displaystyle x^{3},y^{2},z^{2},xyz}$
3. The generators of (here:) leave the secondary class fixed. ${\displaystyle H}$ ${\displaystyle z}$ ${\displaystyle H1}$
4. The operation on the set of minor classes is transitive .

The first rule is a general property of group operations that follows from the invertibility of group elements. The second rule applies because the relation in represents the element and actually the group operates. Rules 3 and 4 are special properties of the operation on minor classes. ${\displaystyle G}$ ${\displaystyle 1}$ ${\displaystyle G}$

example

Animation of a tetrahedron

Consider the tetrahedron group of the twelve rotational symmetries of a regular tetrahedron . The rotations around the angle around two different corner points clockwise and counterclockwise are referred to as and . This results in the rotation around the center point of an edge - the product is to be read from right to left - around . The following relationships apply: ${\displaystyle T}$ ${\displaystyle {\tfrac {2\pi }{3}}}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle xy=z}$ ${\displaystyle \pi }$

${\displaystyle x^{3}=1,\quad y^{3}=1,\quad xyxy=1.}$

It will be shown that the relations mentioned define T. To do this, look at the group . Since the relations in the tetrahedral group are fulfilled, the mapping property of factor groups provides a homomorphism . Since x and y create the group T , the homomorphism is surjective . To prove that is injective , it must be shown that the order of group G is 12. ${\displaystyle G=\left\langle x,y;x^{3},y^{3},xyxy\right\rangle }$ ${\displaystyle \varphi \colon G\to T}$ ${\displaystyle \varphi }$

To achieve this, it could be the cosets of the trivial subgroup count and so the order of G determined. However, that would not be very efficient. It is more convenient to use a nontrivial subgroup H of G , such as the one generated by y . Because of this, this subgroup H has at most order 3. It is sufficient to show that the order of H is even 3 and the index of H in G is 4. It would follow that G has order 12. ${\displaystyle H={1}}$ ${\displaystyle y^{3}=1}$

According to the algorithm, the permutation representation of G is determined, which describes the operation on the set of secondary classes. Numbers 1, 2, 3, ... are used as a designation for the secondary classes, with 1 being reserved for the secondary class H 1. Since the number of secondary classes is not yet known, it is not yet possible to decide how many numbers are required. During the process, new numbers will be introduced gradually as they are needed.

The procedure provides the following table:

${\displaystyle x\ x\ x}$				${\displaystyle y\ y\ y\ }$			${\displaystyle x\ y\ x\ y\ }$
1	2	3	1	1	1	1	2	3	1	1
2	3	1	2	3	4th	2	3	4th	4th	2
3	1	2	3	4th	2	3	1	1	2	3
4th	4th	4th	4th	2	3	4th	4th	2	3	4th

The associated permutation representation results from the method

${\displaystyle x=(123),\quad y=(234).}$

Since there are four digits, the index of H in G is 4. y has order 3 because because of the relation the order can be at most 3 and it is at least 3 because the permutation assigned to y has order 3. The order of G is thus equal to 12. The permutation representation also provides an isomorphism of T on the group generated by the permutation. One can convince oneself that this is the alternating group . Thus the tetrahedral group T is isomorphic to . ${\displaystyle y^{3}=1}$ ${\displaystyle A_{4}}$ ${\displaystyle A_{4}}$

literature

• Michael Artin : Algebra , Birkhäuser Verlag, 1993, ISBN 3-7643-2927-0 , pp. 252-257.

Web links

• Essay on the Todd-Coxeter Algorithm (French)