Will Todd-Coxeter algorithm always determine the order of the group?

Question

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?

Answer 1

For some groups it is undecidable what their order is. In particular there are finitely presented groups for which it is undecidable whether they are trivial. The algorithm will not determine the order in this case because no algorithm will.

As to why it can be undecidable, it turns out that there are some things that computers just can't do, like determine whether an arbitrary program will ever finish. Mathematically it also means that ZFC is not expressive enough to show that the group is or is not trivial, much like the continuum hypothesis.

Answer 2

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.