Project topics and materials
Get Complete Project Material File(s) Now! »
Todd-Coxeter algorithm for the chain of groups G(m,1,n)
To understand the structure of a group from its presentation is, in general, a difficult task. A basic method for finitely presented groups is the Todd-Coxeter algorithm, created by J.A. Todd and H.S.M. Coxeter in 1936. Given a subgroup H of a group G, it attempts to find the index |G : H|, by enumerating cosets of H in G in a systematic trial and error procedure. If |G : H| is finite then the Todd- Coxeter algorithm terminates in a finite (but unknown) number of steps. It returns the index |G : H|, together with a complete coset table, which is equivalent to the permutation representation of G on the space of the cosets. The Todd-Coxeter method has a wide range of applications, in particular, it may be used to construct a normal form for group elements [35], to test whether H is a normal subgroup in G or to determine a minimal presentation for a given concrete group3 [11, 19]. Sometimes, it solves the so called word problem4. The procedure of enumerating the cosets is sufficiently mechanical and can be carried out by computer (first implementation in 1953).
Todd-Coxeter coset enumeration procedure
Let G = hE|Ri be a finite presentation for a group G where E = {g1 , . . . , gn} is a set of generators and R = {r1 = e, . . . , rk = e} is a set of defining relations. Each “relator” ri is a word in the alphabet E = {g1 , . . . , gn, g1−1 , . . . gn−1}. Let H = hh1, . . . hpi be a subgroup of G generated by a finite set of words in E. At each step, three types of partially defined tables are reactualized [10, 40]:
• A coset table: this is a matrix M whose rows are labelled by cosets of H existing at this step, and columns by elements of E. The entries, if defined, are cosets, M(k, g) = ` if ` is such that kg = `.
• A relation table for each relator r = gi1 gi2 · · · git : this is a matrix Mr with t columns; rows are labelled by existing cosets. The entry Mr(k, a), if defined, is the coset kgi1 · · · gia . Since r = e in G, we have Mr(k, t) = k.
• A subgroup table for each generator h = gj1 · · · gjt of H: this is matrix Sh with only one row corresponding to the coset 1 := H and t columns. The entry S(1, a) is the coset 1gj1 · · · gja . Since Hh = H, we have Sh(1, t) = 1.
After the tables have been initialized, the Todd-Coxeter procedure consists of listing cosets of H , starting with 1 = H, then proceeding e.g. with 2 := 1g1±1 , 3 := 1g3±1, or 3 := 2g1±1 etc. with the only rule that a coset `α must be defined by an equation `α = `βg, β < α, g ∈ E , if the place of `β g in the coset table is still unoccupied. As soon as the coset `α has been defined, the α -th rows of the coset table and the relation tables are initialized. This definition and its trivial consequence `α g−1 = `β are then filled into all possible vacant places of the various tables. The aim of the process is to obtain information about equality or inequality of cosets that have been given different numbers. When a row in a relation table or a subgroup table is completed, we get an extra piece of information of the kind `αg = `β for some cosets `α, `β and g ∈ E. This is called deduction. If the 3The starting point of Todd and Coxeter was to prove that a set of relations for a given concrete group is complete.
4The problem of deciding whether two words in a finitely presented group define the same element is one of three fundamental decision problems formulated by Max Dehn in 1911. P. Novikov (1955) and W. Boone (1958) constructed finitely presentable groups for which the question is undecidable in the sense that it cannot be answered by a recursive algorithm.
entry M(`α, g) is not yet defined then we fill the entries M (`α, g), M(`β, g−1), and insert this information into all other relevant places in the other tables. If M(`α, g ) is already filled with a coset, say `γ, different from that given by the deduction then we realise that `α and `γ denote the same coset of H. This is called coincidence. When a coincidence is found, we leave only one coset, usually the one that appeared earlier. We propagate this information to other cosets that have been defined as `αg or `γg for some g ∈ E. In turn, this may lead to further deductions and coincidences. The process terminates when all entries of all tables are filled. The obtained coset table corresponds to a permutation representation of G.
Schreier coset graph for the chain of groups G(m, 1, n)
Definition 3. Given a finitely presented group G = hE|Ri and a subgroup H of finite index in G, a Schreier coset graph of (G, H ) is a directed graph whose vertices are the right cosets of H and whose edges are of the form (Hg, Hgx) for x ∈ E. By convention, the edge (Hg, Hgx) has label x. The Schreier graph depicts the action of G on the space of cosets. For a given edge label g, every vertex has exactly one outgoing edge and one incoming edge with that label. A path g1 · · · gk from a vertex s has each gi in E, and we follow the path in left-to-right order, so that sg1 · · · gk is a vertex at the end of the path. Since the map Hg 7→(Hg)−1 = g−1H defines a bijection between the right cosets and left cosets of H, encodes as well the action of G by left multiplication on the left cosets. Given a path g1−1 · · · gk−1 in left-to-right order from a vertex s, gk−1gk−−11 · · · g1−1s corresponds then to a left coset at the end of the path. The Schreier graph may be obtained from the coset table or, directly, by a graphical procedure [9, 28] equivalent to the Todd-Coxeter algorithm.
Rewriting rules for the chain of groups G(m,1,n)
In symbolic computation with finitely presented groups the defining relations are inter-preted as rewriting rules. These are the instructions to replace the left hand side by the right hand side. The procedure of replacing subwords which are left sides of rewriting rules with the corresponding right sides is called rewriting. A word is said to be reduced, with respect to the given set of rewriting rules, if no rewriting can be performed on it. Consider an element s2s1s2t ∈ G(2, 1, 3). There are two possibilities to rewrite it by applying the defining relations R = {(3), (4)}: The words s1s2 s1t and s2s1ts2 are reduced with respect to R. Supplementary instructions are required to equalize them. More generally, we are faced to the already mentioned word problem (see footnote 4). For a given presentation of the group the word problem is solved if one finds an algorithm that takes a word and rewrites it in a unique way, called a canonical form for the corre-sponding element of the group. The normal form given in previous paragraph guarantees the existence of such an algorithm for the group G(m, 1, n). In order to build an algorithm that takes as input a word in generators of G(m, 1, n + 1) and their inverses, and returns its normal form as in (8) one only needs to know the normal form of the words ψkj(n)x = sn · · · s1tks1 · · · sjx for all generators x of G(m, 1, n + 1), k = 0, . . . , m −1 and j = 0, . . . , n. Below is the list of rewriting rules we recursively established and implemented in Mathematica (the equalities are to be understood as “replace by”).
Table of contents :
Introduction
1 Complex reflection groups of type G(m,1,n)
1.1 Generalities about reflection groups
1.2 Groups G(m,1,n)
1.3 Rotational permutations of m-cards
1.4 Todd-Coxeter algorithm for the chain of groups G(m,1,n)
2 Shuffle analogues in G(m,1,n) group algebra
2.1 Symmetrizers and shuffles
2.2 Shuffle analogues in G(m,1,n) group algebra
2.3 Minimal polynomial and multiplicities of eigenvalues
2.4 m-derangement numbers
2.5 Cyclotomic algebras
2.6 Asymptotic analysis of top-to-random shuffling
Conclusion
Acknowledgements
References
