7
$\begingroup$

The following question arose in the comments on this question, and it seems like a reasonable question to ask in its own right. I've added some additional details.

The word problem in any fixed finitely presented simple group $G$ is decidable; this is Kuznetsov's theorem. However, the procedure by which one solves it is not uniform. Indeed, given a word $w$ over the generators (of the fixed presentation for $G$), the procedure for deciding if $w=_G 1$ first begins by saying "if $G$ is trivial, then return 'yes'; if $G$ is not trivial, then choose a non-trivial element of $G$ such that... (etc.)". Of course, whether $G$ or not is trivial is a fixed property of $G$, so for a fixed $G$ there is a (trivial) Turing machine which returns whether or not $G$ is trivial (either the machine that always says "yes", or the machine which always says "no" will do).

Thus the procedure in Kuznetsov's theorem is not uniform. This raises the following interesting question.

($\ast$) Is the word problem uniformly decidable for finitely presented simple groups?

The procedure for non-trivial finitely presented simple groups (i.e. the continuation of the above procedure after one has chosen a non-trivial element) is, on the other hand, uniform (see below [1]). In particular, if one has an oracle which, on input a (presentation of a) finitely presented simple group, outputs whether or not the group is trivial, then the answer to ($\ast$) is yes: first decide whether the group is trivial or not by the oracle: if it is trivial, then the word problem is trivially solvable; if it is non-trivial, it can be uniformly decided by the above procedure.

Thus, the above question ($\ast$) is equivalent to the following:

($\ast'$) Is the triviality problem decidable for finitely presented simple groups?

Note that the triviality problem for finitely presented groups is, in general, undecidable, by the Adian-Rabin theorem, as being trivial is a Markov property of groups. However, one might suspect that this question is easier if one is promised that the groups given as input are always simple.

(Note: the above questions and statements can be identically considered for recursively presented groups.)

[1] To see that the word problem is uniformly decidable for non-trivial finitely presented simple groups, the following procedure can be used, as sketched by Ben Steinberg in the comments on this question. Let $\langle A \mid R \rangle$ be a presentation of a non-trivial finitely presented simple group $G$. Let $w$ be a word over the generators $A$ and their inverses. If $w=_G 1$, then we can detect this by enumerating the consequences of the relations $R$ until we find a finite sequence of derivations taking $w$ to $1$. On the other hand, if $w \neq_G 1$, then $\langle A | R \cup \{ w \} \rangle$ is a non-trivial quotient of $G$. But $G$ is simple, so the group $H$ presented by this presentation is necessarily trivial; now $H$ is trivial if and only if each generator $A$ is trivial in $H$, which we can detect by enumerating consequences of $R \cup \{ w \}$ until we have for every generator $a$ in $A$ found a finite derivation sequence taking $a$ to $1$. Thus, we can detect if we are in the case $w \neq_G 1$. By running the two algorithms above in parallel, we hence eventually end up detecting $w =_G 1$ or $w \neq_G 1$, so we have solved the word problem. Of course this also works for recursively presented groups.

$\endgroup$
6
  • 1
    $\begingroup$ Maybe this principle ncatlab.org/nlab/show/too+simple+to+be+simple should be applied to eliminate the trivial group? In fact they don't consider the trivial group to be simple $\endgroup$ Aug 7, 2021 at 14:04
  • 1
    $\begingroup$ The trivial group is not simple, so I'm confused... $\endgroup$
    – YCor
    Aug 7, 2021 at 14:31
  • $\begingroup$ @YCor Sure, this is slightly abusive notation, as in the previous discussion; the term "simple group" here is really meant as "a group with no non-trivial quotient". $\endgroup$ Aug 7, 2021 at 14:48
  • $\begingroup$ ok, it means "simple or trivial". (In such a context I don't think it's "slightly abusive", but highly non-standard — by the way every simple group is a nontrivial quotient of itself, so you rather mean no non-trivial proper quotient.) One could ask whether there's an algorithm which inputs a finite presentation, and, if it defines a (simple or trivial) group, recognizes whether it's trivial. $\endgroup$
    – YCor
    Aug 7, 2021 at 17:34
  • 1
    $\begingroup$ This "highly nonstandard" notation may be my fault -- apologies. I had no idea that the trivial group isn't usually considered simple, although I suppose it makes sense, by analogy with primes. It's also along the same lines as the (unfortunately not universal) convention that the empty set is not connected. $\endgroup$
    – HJRW
    Aug 8, 2021 at 16:26

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.