Science Fair Project Encyclopedia
The Todd-Coxeter algorithm, discovered by Todd and Coxeter in 1936, is a procedure that can solve the coset enumeration problem. Given a group presentation , where X is a set of generators and R is a set of relations, and a subgroup , we wish to compute the action of G on H. The Todd-Coxeter algorithm is guaranteed to succeed in a finite number of steps provided | G:H | is finite, although the running time is unpredictable. Specifically, no recursive function of | G:H | and the input can bound the running time.
One implementation of the algorithm proceeds as follows. Define X' to be the set of generators X and their inverses. Let where the hi are words of elements of X'. There are three types of tables that will be used: a coset table, a relation table for each relation in R, and a subgroup table for each generator hi of H. 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 stored the relationships between the known cosets when multiplying by a generator. It has rows representing cosets of H and a column for each element of X'. Let Ci 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 Ck = Cigj.
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 R is maintained. Let be a relation in R, where . The relation table has rows representing the cosets of H, 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 itth entry is initially i, since .
Finally, the subgroup tables are similar to the relation tables, except that the keep track of possible relations of the generators of H. For each generator of H, with , we create a subgroup table. It has only one row, corresponding to the coset of H 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 Ci = Cjg, , 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 Ci = Cjg and Cj = Cig - 1.
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 Ci = Cj, with i < j. 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 | G:H | is finite.)
When all the tables are filled, the algorithm terminates. We then have all needed information on the action of G on the cosets of H.
to be written
- Seress, A. "An Introduction to Computational Group Theory" Notices of the AMS, June/July 1997.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details