5
$\begingroup$

Let $G$ be a group with an explicit finite presentation. Assume $G$ has a decidable word problem.

Can there exist an explicit word $w\in G$ such that there is no algorithm deciding if a given word $w'\in G$ is equal to $w^k$ for some $k\in \mathbb{Z}$?

$\endgroup$
2
  • $\begingroup$ This has been answered on previous MO questions $\endgroup$ – Benjamin Steinberg Apr 22 at 15:08
  • 2
    $\begingroup$ It's called the power problem and if you Google undecidability of the power problem you will find a reference to either McCool of Collins I believe. I forget which. $\endgroup$ – Benjamin Steinberg Apr 22 at 15:15
4
$\begingroup$

This question is very similar to Is it decidable to check if an element has finite order or not? and has the same answer. Namely, an example was constructed by McCool. He also constructs in that paper a finitely presented group with solvable word problem where you cannot decide if an element has finite order, known as the order problem. I'm pretty sure that the power problem, which is what you asked for here has also been answered before on Mathoverflow.

Note the group is explicitly constructed via a recursive presentation and then uses Higman embedding to get the finite presentation so it may not be as explicit as you would like because you would have to chase the Higman embedding but the word $w$ is explicitly given and fixed modulo the Higman embedding.

$\endgroup$
4
  • $\begingroup$ Does Higman embedding involve something non-constructive like law of excluded middle or axiom of choice? $\endgroup$ – Oniqa Apr 22 at 15:33
  • $\begingroup$ Not that I know of. It's just a particular construction you can find in any combinatorial group theory. Certainly it doesn't use choice. I'm not a logician but isn't excluded middle used to get the halting problem undecidable? You do a bunch of HNN extensions like in the construction of a group with unsolvable word problem $\endgroup$ – Benjamin Steinberg Apr 22 at 15:35
  • $\begingroup$ I think it depends on the way you set up the definitions. $\endgroup$ – Oniqa Apr 22 at 15:39
  • $\begingroup$ I don't think much about excluded middle but I seriously doubt it is used in a serious way. $\endgroup$ – Benjamin Steinberg Apr 22 at 15:40

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.