Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Do you know the answer for f.g. groups? (maybe with solvable word problem) –  YCor Jul 15 '13 at 14:01
    
No, but if there are such examples, then I would prefer a f.p. example with solvable word problem. –  Derek Holt Jul 15 '13 at 14:12
    
@Derek: Such a group probably can be constructed with some (possibly significant) effort. What is the motivation? –  Mark Sapir Jul 15 '13 at 14:53
    
a group with finitely many conjugacy classes trivially satisfies your condition. it is very plausible that some of them have a nonsolvable conjugacy problem –  YCor Jul 15 '13 at 17:52
1  
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. –  Mark Sapir Jul 15 '13 at 21:14

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.