5
$\begingroup$

We say that a semigroup $S$ has solvable power problem if there is an algorithm that takes as input an element $s \in S$ and decides whether or not there exist $m,n \in \mathbb{N}$ with $m \neq n$ and $s^m=s^n$.

Does anybody know an "easy" (like finitely presented with relatively few relations) example of a semigroup with solvable word problem but unsolvable power problem?

I would also be interested in an example of a group with solvable word problem but unsolvable power problem, if anybody has such an example.

$\endgroup$
1
  • 3
    $\begingroup$ The power problem asks for every $a,b$ whether $b=a^n$ for some $n$. It is not the same as what you wrote. In the case of groups your problem is known as the order problem (find out if an element is of finite order). $\endgroup$
    – user6976
    Apr 11, 2011 at 18:23

1 Answer 1

6
$\begingroup$

The only known way to construct this example (say, in the case of groups, the case of semigroups is similar) is the following. First consider the free Abelian group $F$ with free generators $a_1,a_2,...$. Pick a recursively enumerable non-recursive set $I$ and impose relations $a_n^{m!}=1$ if $n$ is the $m$th number from $I$ (we assume that there exists a computer that lists numbers in $I$ in some order one by one). That group, call it $A$, has solvable word problem. Indeed, consider any word $w=a_{i_1}^{k_1}\ldots a_{i_s}^{k_s}.$ That word is equal to 1 in $A$ iff each $k_i$ is divisible by $m!$ such that $a_i$ is the $m$-th number in $I$. That gives restriction to $m$. So given $w$ we start the computer that lists $I$ and wait till we have the first (not in the natural order!) $k_1+...+k_s$ numbers from $I$ listed. The power problem in $A$ is not decidable of course. Since $A$ has solvable word problem, by Higman's theorem, it embeds into a finitely presented group $G$. By Clapham's theorem, we can assume that $G$ has decidable word problem. But the power (order) problem in $G$ is not decidable.

There are no examples which are given by very few defining relations. The reason is that the solvability of the order problem is not easy to achieve without Higman embedding (I do not know any such way without getting undecidable word problem also) which is very implicit.

$\endgroup$
1
  • $\begingroup$ This is an old answer, but a reference for this is [McCool, James: The order problem and the power problem for free product sixth-groups. Glasgow Math. J. 10 (1969), 1–9]. The example in this answer appears at the very end, together with an example of a group with decidable order problem, but undecidable power problem. $\endgroup$ Feb 10, 2020 at 15:56

Your Answer

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

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