35
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A restatement is whether in a finitely presented group with solvable word problem, the set of finite order elements is recursive (it's clearly recursively enumerable). I'm not sure of the details of Higman's theorem, but doesn't it embed every f.g. group with solvable word problem into a finitely presented one? This would help to get rid of the somewhat constraining finite presentability assumption. $\endgroup$ – YCor Oct 5 '16 at 13:44
  • $\begingroup$ @YCor Yes, Boone-Higman, 1974 says a finitely generated group G has solvable word problem if and only if it can be embedded in a simple subgroup of some fintiely presented group. $\endgroup$ – Derek Holt Oct 5 '16 at 14:02
  • $\begingroup$ The question is interesting (and I believe unknown) for automatic groups. But for automatic groups it iseems possible that the answer might be yes, and I would be very surprised if it was yes more generally. $\endgroup$ – Derek Holt Oct 5 '16 at 14:05
  • $\begingroup$ @DerekHolt I forgot to say that I need the image to be a recursive subset, so we would need in addition this, and that the f.p. group itself has a solvable word problem (possibly this follows from the original construction) $\endgroup$ – YCor Oct 5 '16 at 14:25
  • $\begingroup$ @YCor This does not answer your question, but there is a result by Birget, Olshanskii, Rips, Sapir that a finitely generated group with word problem in NP embed quasi-isometrically as a subgroup of a finitely presented group with polynomial Dehn function. $\endgroup$ – Derek Holt Oct 5 '16 at 14:50
37
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I've checked the paper: it seems to indeed have unsolvable "infinite order" problem (this does not formally follow from having unsolvable order problem: e.g., if a group is torsion, the "infinite order problem" is trivially solvable, but maybe not the order problem). $\endgroup$ – YCor Oct 5 '16 at 16:47
  • 10
    $\begingroup$ If you know how to check the word problem then you can check the powers of an element and see if some power is trivial and what is the smallest so you just need to be able to check if the order is infinite. $\endgroup$ – Benjamin Steinberg Oct 5 '16 at 16:54
  • $\begingroup$ Thanks, I hadn't realized this! of course while the infinite order problem is solvable iff the order problem is solvable, the problem become different if we care of effectiveness (but this is not the point here). $\endgroup$ – YCor Oct 5 '16 at 17:18
  • $\begingroup$ I thought about these things back when I used to study the submonoid membership problem of which the order problem is a special case. $\endgroup$ – Benjamin Steinberg Oct 5 '16 at 17:18
  • $\begingroup$ Benjamin, could you please tell what is interesting is known and unknown about the membership problem for submonoids? $\endgroup$ – Al Tal Oct 5 '16 at 18:38
21
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Unless Collins is using a different definition of the power problem than McCool I think the power problem should have a higher Turing degree than the order problem $\endgroup$ – Benjamin Steinberg Oct 5 '16 at 17:51
  • $\begingroup$ At the moment I have no access to the full paper. However, the abstract says: The chapter concludes by proving a lemma that shows that groups with a soluble power problem and an insoluble order problem have an unexpected algebraic property, so it seems that he is actually able to provide examples where the power problem has a lower Turing degree than the order problem. $\endgroup$ – Francesco Polizzi Oct 5 '16 at 18:01
  • $\begingroup$ Maybe his version is not unidirectional $\endgroup$ – Benjamin Steinberg Oct 5 '16 at 18:11
  • 1
    $\begingroup$ Indeed, Collins uses a special notation. For him, the identity element $1_G$ is a $0$-th power of all elements, so $(x,1)$ all belong to the set of power pairs. Therefore, the power problem may indeed have Turing degree below the order problem. $\endgroup$ – Al Tal Oct 5 '16 at 18:29
  • 2
    $\begingroup$ @FrancescoPolizzi, don't you mean the answer is no (it is not decidable in general), rather than yes (it is decidable in general)? $\endgroup$ – Tanner Swett Oct 5 '16 at 23:50
15
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.