9
$\begingroup$

Could there exist a finitely presented group with unsolvable conjugacy problem, in which it is decidable whether a word over the group generators is a shortest representative of an element in its conjugacy class?

Here is some motivation. For many of the known families of automatic groups, such as hyperbolic groups, virtually abelian groups, Coxeter groups, Garside groups, Artin groups of large type, it can be shown that the set of all geodesic words (at least over an appropriate generating set) is a regular set. Conversely, if you assume that the geodesics form a regular set, then you cannot (apparently) deduce anything much at all about the group, beyond the fact that it has solvable word problem. But in fact the set of geodesic words being recursively enumerable is already enough to imply solvable word problem.

Moving on to the conjugacy problem, it seems that in at least some of these classes of groups, such as hyperbolic groups and Artin groups of extra-large type (not sure yet about large type), the set of all words that are shortest representatives of elements in their conjugacy class forms a regular set. But in that case, the converse hypothesis (regular or perhaps recursive set of shortest words in the conjugacy class) does not appear to imply solvable conjugacy problem.

$\endgroup$
11
  • $\begingroup$ Do you know the answer for f.g. groups? (maybe with solvable word problem) $\endgroup$
    – YCor
    Jul 15, 2013 at 14:01
  • $\begingroup$ No, but if there are such examples, then I would prefer a f.p. example with solvable word problem. $\endgroup$
    – Derek Holt
    Jul 15, 2013 at 14:12
  • $\begingroup$ @Derek: Such a group probably can be constructed with some (possibly significant) effort. What is the motivation? $\endgroup$
    – user6976
    Jul 15, 2013 at 14:53
  • $\begingroup$ a group with finitely many conjugacy classes trivially satisfies your condition. it is very plausible that some of them have a nonsolvable conjugacy problem $\endgroup$
    – YCor
    Jul 15, 2013 at 17:52
  • 1
    $\begingroup$ There are finite number of representatives of conjugacy classes. Every word is conjugate to one of them. Almost all words are longer than any of these finite number. The conjugacy to a smaller word is decidable by assumption. So if the word problem is solvable, then reduce your word to a very small length, then if the word problem is solvable, the problem is no longer a mass problem, and you can pre-compute all the necessary info. Conjugacy is a transitive binary relation. $\endgroup$
    – user6976
    Jul 15, 2013 at 21:14

0

Your Answer

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