The Novikov--Boone Theorem, which is perhaps the archetypal local unsolvability result in group theory, states existence of a finitely presented group whose word problem is recursively unsolvable. Recall that the word problem asks whether there exists an algorithm to decide whether an arbitrary word in generators of the group $G$ is trivial. Closely related is the equality problem, which asks whether there exists an algorithm to distinguish between two given words in generators of the group $G$. Clearly an algorithm solving one of these problems gives rise to an algorithm solving the other, but it's not clear to me what non-existence of an algorithm implies for subsets.

Question: Given a finitely presented group $G$ with unsolvable word problem and a subset $C$ of $G$ closed under conjugation by elements in $G$ (in the case of interest $C$ is a right coset), might it happen that the equality problem is solvable in $C$? Is there a characterization of when this happens?

In a different language, $C$ is a conjugation quandle, and I'm asking whether a conjugation quandle (with its conjugation structure) might be algorithmically better behaved than the group in which it sits (with its product structure). I'm interested also in algorithmic complexity, but first in recursive solvability of the equality problem in particular. Intuitively I can't see why the quandle couldn't computationally be simpler than the group, but I don't know a good non-trivial example when this happens.


If C is a right-coset Hg then the equality problem in C is equivalent to the word problem in H. The word problem in H can be solvable even if the word problem in G is unsolvable, as long as the membership problem for H is unsolvable.

For instance, take a group G' with unsolvable word problem and set $G= G'\times H$ where $H$ is any group with solvable word problem.

By the way, in this case the condition that Hg is conjugation-closed translates into the requirement that g is central in G'. To construct lots of interesting examples of this form you could use Ould Houcine's paper 'Embeddings in finitely presented groups which preserve the center'.


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.