Is it decidable to check if an element has finite order or not?

Question

Suppose we have a finitely presented group $G$ with decidable word problem. Is it decidable to check whether a given element $x\in G$ has finite order or infinite?

Answer 1

A finitely presented group with decidable word problem and undecidable order problem is in McCool, James Unsolvable problems in groups with solvable word problem. Canad. J. Math. 22 1970 836–838.

Answer 2

The decidability of the word problem does not imply the decidability of the order problem, and in fact the following more general result holds.

Theorem. Let $\mathbf{a}, \, \mathbf{b}, \, \mathbf{c}$ be three recursively enumerable degrees of unsolvability (i.e., Turing degrees) with $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a} \leq \mathbf{c}$. Then there exists a finitely presented group $L$ such that

• the word problem for $L$ is of degree $\mathbf{a};$
• the power problem for $L$ is of degree $\mathbf{b};$
• the order problem for $L$ is of degree $\mathbf{c}.$

See

D. J. Collins: The word, power and order problems in finitely presented groups, in "Word Problems, Decision Problems and the Burnside Problem in Group Theory", Studies in Logic and Fundations of Mathematics 71 (1973).

Answer 3

Inspired by McCool's paper given in Benjamin's answer, here's an explicit example that is finitely generated but not finitely presented:

let $\phi$ be an injective recursive function from positive integers to themselves, whose image is not recursive. Consider the group with recursive presentation $$G=\langle t,x\mid r_{\phi(n)}^{n!}:n\ge 1\rangle,\quad \text{where}\;r_m=[t^mxt^{-m},x].$$ It is not hard to check that $r_{\phi(n)}$ has order $n!$ and $r_m$ has infinite order if $m$ is not in the range of $\phi$ (added: see below for a variant where I justify this claim) . In particular, the infinite order problem (checking if an element has infinite order) is not solvable.

However this group has a solvable word problem. The idea is that given a word of length $n$, it is trivial in $G$ if and only if it is trivial in the partial presentation with only relators $r_{\phi(k)}^{k!}$ for $k\le n$, and word problem in these groups are (I think) simultaneously solvable although I haven't checked details.

Actually McCool says it's enough to embed such a group into a group with solvable word problem, no need to care that the image is recursive. And indeed that's enough (clearly solvability of the infinite order problem passes to finitely generated subgroups).

---

Added: here's a little variant in which I can provide a short argument for the statement on the order: define the wreathed Coxeter group

$$H=\langle t,x\mid x^2,s_{\phi(n)}^{n!}:n\ge 1\rangle,\quad \text{where}\;s_m=x_0x_m,\;x_m=t^mxt^{-m}.$$

Indeed we immediately see that $H$ is a semidirect product $\mathbf{Z}\ltimes W$, where $W$ is the Coxeter group with generators $x_m$, $m\in\mathbf{Z}$, and Coxeter relations $(x_{m+\phi(n)}x_m))^{n!}=1$, where the cyclic group acts by shifting the $x_m$. And it's well-known that in a Coxeter group, the prescribed orders are the genuine orders [we just have to check that we injectively prescribe order, which amounts of the injectivity of $(m,n)\mapsto (m+\phi(n),m)$, which itself follows from injectivity of $\phi$].

By the way, it follows that the same holds if we remove the relator $x^2=1$ in the above presentation.