5

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}$?

1 Answers1

3

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.

Benjamin Steinberg
  • 37,275
  • Does Higman embedding involve something non-constructive like law of excluded middle or axiom of choice? –  Apr 22 '21 at 15:33
  • 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 – Benjamin Steinberg Apr 22 '21 at 15:35
  • I think it depends on the way you set up the definitions. –  Apr 22 '21 at 15:39
  • I don't think much about excluded middle but I seriously doubt it is used in a serious way. – Benjamin Steinberg Apr 22 '21 at 15:40