My book say that we can let our subgroup be the trivial subgroup which only contains the identity. Then my book claims that all elements will have their own coset and there will be many indices produced for the algorithm.
My book claims that in some cases we will not be able to determine the order of the group this way. Does letting the subgroup equal the identity and using the algorithm, how can we not find the order of the group?
Also I know using the counting formula we can find the order our group when we know the number of cosets and the subgroup size.
How can it be that some groups will not reveal their order?
Best Answer
If the group defined by the presentation is finite, then the Todd-Coxeter procedure (it's a procedure, not an algorithm) is guaranteed to complete eventually and to tell you the order.
The fly in the ointment is that even if the order turns out to be something small, it is impossible to predict in advance how long the computation might take and how much computer memory it might require.
It is possible to write down reasonably short presentations of the trivial group (and which can be proved to define the trivial group) that would take the standard Todd-Coxeter procedure longer than the expected life of the universe to prove trivial.
Edit, July 2024. There is a question in the comments about how to prove that the Todd-Coxeter procedure is guaranteed to terminate (given enough time and memory) whenever $|G:H|$ is finite, where $H$ is a given finitely generated subgroup of the finitely presented group $G$. This property depends on the assumption that for any coset $Hg$ and any group generator $x$, the cosets $Hx$ and $Hx^{-1}$ are defined at some point. In fact some of the standard strategies used (such as HLT+Lookahead) do not satisfy this assumption a priori, so they have to be modified so that they satisfy it.
With this assumption, there is a technical proof of the property in Proposition 1.3 of Chapter 5 of the book "Computation in Finitely Presented Groups" by Charles Sims. An alternative proof can be found in Theorem 5.5 of "Handbook of Computational Group Theory" by Holt, Eick and O'Brien. This second proof says in outline that, if the procedure does not terminate, then it constructs the infinite coset table of $G$ on the cosets of $H$, contradicting the assumption that $|G:H|$ is finite. Some people are suspicious of a proof that relies on a procedure that constructs an infinite object, but (not surprisingly) I think it is OK.