The toddcox program enumerates the cosets of a subgroup H of a group G. The simplest way to use it is to start it and respond to the prompts. Here is a sample run in which G is the alternating group on four letters, with two generators a,b and relations a3 = b3 = (ab)2 = 1. The subgroup H is the cyclic group generated by a. User input is shown in red.
$ ./toddcox
This program uses the Todd-Coxeter procedure to compute the
index in a finitely presented group G of a subgroup H. You
will be prompted to enter the number of generators of G, the
defining relators of G, and the generators of H. Use
a,b,... for the generators of G and A,B,... for their
inverses.
Number of generators: 2
Enter the relators for G, one per line; press Enter when finished:
> aaa
> bbb
> abab
> <--- user pressed Enter
Enter the generators of H, one per line; press Enter when finished:
> a
> <--- user pressed Enter
The index of H in G is 4.
The coset table had size 4 before compression.
Compressed and standardized coset table:
a A b B
1: 1 1 2 3
2: 3 4 3 1
3: 4 2 1 2
4: 2 3 4 4
Here is a second example. The group G is the Mathieu group M12, which is a simple group of order 95040, with three generators a,b,c and relations
a11 = b2 = c2 = (ab)3 = (ac)3 =(bc)10 = 1, a2(bc)2 =(bc)2a-1The subgroup H is the trivial group.
$ ./toddcox This program uses the Todd-Coxeter procedure to compute the index in a finitely presented group G of a subgroup H. You will be prompted to enter the number of generators of G, the defining relators of G, and the generators of H. Use a,b,... for the generators of G and A,B,... for their inverses. Number of generators: 3 Enter the relators for G, one per line; press Enter when finished: > aaaaaaaaaaa > bb > cc > ababab > acacac > bcbcbcbcbcbcbcbcbcbc > aabcbcaCBCB > Enter the generators of H, one per line; press Enter when finished: > The index of H in G is 95040. The coset table had size 573191 before compression. Enter file name for output, or press Enter to quit: >
Note that the coset table was not printed on the terminal because it was too large. In this case the user is given the option of specifying a file to which to print the table. In the example above the user simply pressed Enter to quit without printing the table.
To save typing, we can put the group-theoretic information in a file, exactly as we would enter it in response to the prompts (including blank lines). We then specify the filename as a command-line argument to the program. For example, suppose we have a file M12.in with the following contents:
3
aaaaaaaaaaa
bb
cc
ababab
acacac
bcbcbcbcbcbcbcbcbcbc
aabcbcaCBCB
<--- blank line
<--- blank line
We could then repeat the example above by giving the command toddcox M12.in. The Toddcox distribution contains several such input files in the examples subdirectory, as well as a README file describing the examples.
There are several methods for carrying out coset enumeration. See, for instance, Handbook of Computational Group Theory by Holt et al, which describes three methods (HLT, HLT+lookahead, and Felsch). The toddcox program uses the HLT method by default, but command-line options can make it use the other two methods. For example, one can give the command
toddcox --felsch [FILE]to use the Felsch method. Here [FILE] is an optional input file, such as M12.in. For HLT+lookahead, the user specifies a positive integer threshold. The program then proceeds as in the HLT method, but if a step in that method causes the coset table to get bigger than threshold, the program uses lookahead to try to reduce the size to at most threshold. If it succeeds, processing continues. Here is an example that uses a threshold of 200,000 on the Mathieu group mentioned above. We assume the presentation is given in a file M12.in as above.
$ ./toddcox --threshold 200000 M12.in Threshold exceeded; table size is 200006. Looking ahead... Table size is now 68727. Continuing. Threshold exceeded; table size is 200006. Looking ahead... Table size is now 91503. Continuing. The index of H in G is 95040. The coset table had size 121996 before compression. Enter file name for output, or press Enter to quit: >
Toddcox is free software, licensed under the GNU General Public License GPLv3.
Ken Brown
Department of Mathematics
Cornell University
Ithaca, NY 14853
Email: kbrown@cornell.edu