I have a problem with understanding the initial step in the Todd-Coxeter coset enumeration algorithm. One needs to define a few cosets when you start off, but I'm not sure how to define them.
As an example, I found the following example: For the presentation $\left\langle {x,y\;\left| {{x^3} = {y^3} = {{\left( {xy} \right)}^2} = 1} \right.} \right\rangle$ and subgroup $H = \left\langle x \right\rangle$, I do understand you firstly define $H: = 1$, and hence $1x=1$, but how does one know to define $1y=2$, $2y=3$, $3y=1$, $2x=3$, etc.? I know for example $1y=2$ follows from $Hy=2$ and $2y=3$ follows from $Hy^2=3$, but how does one know in which order to enumerate them? Why was $Hy^2$ not defined to be '$Hy^2=4$' for example?
Another example I found is the presentation $\left\langle {x,y\;\left| {{x^2} = {y^2} = {{\left( {xy} \right)}^3} = 1} \right.} \right\rangle$ and subgroup $H = \left\langle x \right\rangle$. Here, how does one know to initially define $2x=3$, $3y=4$ and $4x=5$?
Best Answer
The simple answer is that you don't know. You have to use your skill and judgement to choose which new coset to define at any stage and, with experience, you get better at it, in the sense that you are more likely to choose definitions that lead to more rapid completion.
Of course, when programming it on a computer you have to choose some strategy (which could include a randomized component). There are two basic strategies that have been used extensively, often in combination with each other.
The first, often called "Felsch" is that you order the generators and their inverses in some way, and then find the smallest coset number $i$ for which there is an undefined entry, and define $ig_j$ where $j$ is minimal with $ig_j$ undefined. You make all possible deductions from this definition before making a new definition.
The second, called "HLT", does something similar, but works through the relations step by step, making definitions to complete the relator tables.
For hand calculations, the first of these, combined with personal experience, is usually preferable. The second one typically results in more unnecessary definitions, but is a little easier to program and runs fast on straightforward examples. As you probably know, making more definitions means that some of the cosets defined turn out to be equal, and then you have to perform a "coincidence" procedure, which is very awkward and tedious to do by hand, but relatively easy for a computer.
Unfortunately, it has been observed that, for every strategy, there exist examples on which that strategy performs badly, and others perform better. So a good coset enumeration implementation (like the ACE system) will allow flexibility and experimentation. (I suspect that the underlying reason for this is that the general question of whether the index $|G:H|$ is finite is theoretically undecidable, whereas a uniformly good strategy for coset enumeration would suggest otherwise - but that's just idle speculation!)
You could google "coset enumeration strategies" for further details.