In group theory , the Todd-Coxeter algorithm , found by J. A. Todd and Coxeter in 1936 , is an algorithm for solving the problem of listing adjacent classes . For specific group assignments and subgroups at algorithm lists adjacent classes by and describes the representation by permutations on the space of adjacent classes.
If the order of the group is relatively small and the subgroup is simple (for example, a cyclic group), then the algorithm can be executed manually and gives a convenient description of the group . Using their algorithm, Coxeter and Todd showed that specific systems of relations between the generating elements of some well-known groups are complete, that is, they make up a system of defining relations .
The Todd-Coxeter algorithm can be applied to infinite groups and ends after a finite number of steps, provided that the index at is finite. On the other hand, in the general case for a pair consisting of specifying a group and a subgroup, the number of its steps is not limited by any computable function of the index of the subgroup and the size of the data.
The execution of the algorithm is as follows. Suppose it where - many generators, - many relationships . Many generators and their inversions denote . Let be Where - elements . There are three types of matrices that will be used: an adjacent class of matrices, correlation matrices for each relation in , and subgroup matrices for each set of generators from . Information is gradually added to these matrices, and as soon as they are filled in, all adjacent classes will be listed and the algorithm will end. An adjacent matrix class is used to store relationships between known adjacent classes when multiplied by many generators. It has rows representing adjacent classes. and columns for each item . Let be denotes adjacent classes th row of adjacent classes of matrices, and let denotes many generators columns. Entering adjacent classes of matrices is consistent, and defined so that it is (if known) where - such that . Matrix ratios are used to detect when some of the related classes that we found are actually equivalent. Run: one matrix ratio for each ratio in . Let be - ratio in where gni oX '. matrix relation has series representing adjacent classes of H, as in adjacent classes of matrices. It has columns, and input into row and the column is determined to be (if known) where Ck = Cig1g2 ... gj. In particular, the i-th input is initially i, while . Finally, the matrices of the subgroup are similar to the matrices of the relation, except that they hold a trace of the possible relations of the set of generators H. For each set of generators hn = gn1gn2 ... gnt from H, with gniOH ', we create a matrix of the subgroup. It has only one row, corresponding to adjacent classes of H itself. It has t columns, and the input in the jth column is defined (if known) to be k, where . When a series of ratios or matrices of a subgroup is completed, new information found. This is known as subtraction. From subtraction, we may be able to fill in the additional entries of the relations and matrices of the subgroup, leading to a possible additional subtraction. We can fill in the entries of adjacent classes of matrices corresponding to the equations and . However, filling in the adjacent classes of matrices, it is possible that we may already have input for the equation, but input has different values. In this case, we found that two of our adjacent classes are actually the same, known as a match. Suppose , with . We replace all cases of j in matrices with i. Then, we fill in all possible entries of the matrices, possibly leading to more subtraction and matches. If there are empty entries in the matrix after all subtraction, and coincidences were taken care of, we add a new adjacent class to the matrix and repeat the process. We make sure that by adding an adjacent class, if Hx is a known adjacent class, then Hxg will be added at some point for all . (This is necessary to ensure that the algorithm ends up secured. finite.) When all matrices are full, the algorithm ends. We got all the information about the action of G on adjacent classes of H.
- JA Todd, HSM 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
- HSM Coxeter, WOJ 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 MR0562913
- G. S. M. Coxeter, W. O. J. Moser Generating elements and defining relations of discrete groups. - M., Science, 1980, - 240 p.
- Seress, A. "An Introduction to Computational Group Theory" Notices of the AMS, June / July 1997.