# Conjugacy problem in a conjugacy separable group

Here is a question that has been bothering me for some time:

Let G be a finitely generated conjugacy separable group with solvable word problem. Does it follow that the conjugacy problem in G is solvable?

Background. A group G is said to be conjugacy separable is for any two non-conjugate elements x,y in G there is a homomorphism from G to a finite group F such that the images of x and y are not conjugate in F. Equivalently, G is conjugacy separable if each conjugacy class is closed in the profinite topology on G.

A well-known theorem of Mal'cev states that a finitely presented conjugacy separable group has solvable conjugacy problem (in this case it is possible to recursively enumerate all the finite quotients, simultaneously checking conjugacy of the images of two given elements in each of them).

On the first page of the paper 'Conjugacy separability of certain torsion groups.'
(Arch. Math. (Basel) 68 (1997), no. 6, 441--449.) Wilson and Zalesskii claim that the conjugacy problem is solvable in finitely generated recursively presented conjugacy separable groups (which, of course, implies a positive answer to my question), and refer to a work of J. McKinsey, 'The decision problem for some classes of sentences without quantifiers' (J. Symbolic Logic 8, 61 – 76 (1943)). However, I could not find anything in the latter paper that would allow to deal with infinite recursive presentations. Moreover, the corresponding property for residually finite groups simply fails. More precisely, there exist finitely generated residually finite recursively (infinitely!) presented groups with unsolvable word problem (cf. 'A Finitely Generated Residually Finite Group with an Unsolvable Word Problem' by S. Meskin, Proceedings of the American Mathematical Society, Vol. 43, No. 1 (Mar., 1974), pp. 8-10).

• Ashot, could you say where Mal'cev proved this? I thought the reference for this result was [W. Mostowski, On the decidability of some problems in special classes of groups. Fund. Math. 59 1966 123--135.] – Igor Belegradek Jul 19 '10 at 18:14
• Igor, the reference is [A.I. Mal'cev, On Homomorphisms onto finite groups (Russian). Uchen. Zap. Ivanovskogo Gos. Ped. Inst. 18 (1958), 49-60. English translation in: Amer. Math. Soc. Transl. Ser. 2, 119 (1983) 67-79.] Mostowskii cites Mal'cev's announcement of this result but seems to be unaware of the main paper. In fact, Mal'cev's proof is also based on the above mentioned work of McKinsey. – Ashot Minasyan Jul 19 '10 at 18:36
• I'm struggling to think of a known construction of finitely generated, infinitely presented, conjugacy separable groups. Ashot, do you have any candidates in mind? – HJRW Jul 19 '10 at 20:58
• @ Henry: I think that an appropriately chosen version of the Bowditch-Mess construction has the desired properties. ams.org/mathscinet-getitem?mr=1240944 – Ian Agol Jul 19 '10 at 22:39
• Henry, plenty of such groups exist, e.g. $\mathbb{Z} wr \mathbb{Z}$, lamplighter groups, and, more generally, wreath products of finitely generated abelian groups with conjugacy separable groups (such that the acting group has separable cyclic subgroups) -- by a theorem of V. Remeslennikov [Finite approximability of groups with respect to conjugacy. (Russian) Sibirsk. Mat. Ž. 12 (1971), 1085--1099.] I also proved [see Cor. 2.9 in personal.soton.ac.uk/am4x07/rs/RAAG-conj_sep.pdf ] that all Bestvina-Brady groups are conjugacy separable. – Ashot Minasyan Jul 20 '10 at 11:09

I think that the issue here may be: if you have a finitely generated, residually finite group, with solvable word problem, then can you detect a homomorphism to a finite group?

By this, I mean you have finite set of generators, and an algorithm which will tell you when a word in that set of generators gives the trivial element. One can enumerate potential homomorphisms to a finite group, by sending every generator to every possible element in the finite group. You can tell if such an assignment does not give a homomorphism, by finding an word in the generators which is trivial in the group, but which is not sent to 1 in the finite group. But if it is indeed a homomorphism, you might never definitively know, since you will always find that trivial elements are sent to the trivial element.

A related question is: can you tell when a recursively defined set of polynomial equations defines a trivial affine variety (a single point)? We know that only finitely many polynomials are needed to cut out the variety by the Nullstellensatz, but how do we know how to choose such a finite set algorithmically? If one knew how to do this, then one could answer your question. This might be something well-known to algebraic geometers or logicians.

This is another incomplete answer, but which hopefully can still be useful.

Say that a finitely generated group G has computable finite quotients if there is an algorithm that, on input a finite group F given by a finite presentation and a function that maps the generators of G to those of F, decides whether or not this function could be extended as a homomorphism.

McKinsey’s argument then clearly yields: in a finitely generated, conjugacy separable group, with computable finite quotients, there is an algorithm that decides when two elements are not conjugated. And thus if that group is recursively presented, it must have solvable conjugacy problem.

I studied this property in my article: « Computability of finite quotients of finitely generated groups », where I prove that this property is independent from the solvability of the word problem: a residually finite group can have computable finite quotients while having unsolvable word problem, and there exist finitely generated residually finite groups with solvable word problem but without computable finite quotients. (This answers negatively Ian Agol’s question.)

Because of this, we have no reasons to believe that for finitely generated groups with solvable word problem, being conjugacy separable is a sufficient condition to have solvable conjugacy problem, since this hypothesis cannot be used without the ability to detect finite quotients.

However, no matter how much I would like to plainly answer « no» to your question, I don’t know how to change my construction to build a conjugacy separable group with solvable word problem and without computable finite quotients, less again one with unsolvable conjugacy problem.

Note finally that it follows from an article of René Hartung (Coset enumeration for certain infinitely presented groups, International Journal of Algebra and Computation) that the first Grigorchuk group has computable finite quotients, and thus the article of Wilson and Zalesskii which you mention, and which proves that this group is conjugacy separable, does help proving that it has solvable conjugacy problem.

• Trivial remark: this is very closely connected to this question and an answer where your preprint is cited. – Carl-Fredrik Nyberg Brodda Mar 1 at 13:14
• @E. Rauzy: thanks for your comment, from your result it does seem like the answer to my question should be negative. A side remark: I think that the Furstenberg’s topology on $\mathbb Z$ your refer to in your article is simply the profinite topology on $\mathbb Z$. As far as I am aware, the profinite topology on an arbitrary group was first defined by M. Hall (A Topology for Free Groups and Related Groups, Ann Math. (2) 52 (1950), no. 1, pp. 127-139), which came out 5 years before Furstenberg's paper. – Ashot Minasyan Mar 7 at 15:34
• @AshotMinasyan: Oh, thank you for this remark. This actually was already mentioned to me by an anonymous referee, but your comment makes me notice that I forgot to update the version of my paper that appears on arxiv. – E.Rauzy Mar 9 at 14:04