MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 7 down vote accepted

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

share|cite|improve this answer
Thank you !!!!! – Daniel Moskovich Nov 11 '12 at 8:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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