Conjugacy-separable and all homomorphisms to any finite group can be listed in finite time implies solvable conjugacy problem
Suppose is a finitely generated group that is both a conjugacy-separable group and a finitely generated group for which all homomorphisms to any finite group can be listed in finite time. Then, is a group with solvable conjugacy problem.
- Residually finite and all homomorphisms to any finite group can be listed in finite time implies solvable word problem
- Finitely presented and residually finite implies solvable word problem (obtained by combining with finitely presented implies all homomorphisms to any finite group can be listed in finite time)
Note that in order to solve the conjugacy problem, it is sufficient to come up with an algorithm that can, in finite time, show that two given words do not represent conjugate elements if indeed they does not. This is because there already exists an algorithm (for every finitely generated group) that can show in finite time that two given words do represent conjugate elements.
The algorithm is as follows:
- Consider the list of all finite groups up to isomorphism. Enumerate them as .
- For each : Construct the list of all homomorphisms from to (possible by assumption on ). For each homomorphism, evaluate the image of the two words under the homomorphism as elements of . If the images are not conjugate in , then return that the word does not represent the identity element of .
Since is conjugacy-separable, it is the case that for any two non-conjugate elements, there exists a finite quotient where their . This finite quotient equals some , so homomorphisms to will detect that the two elements are not conjugate. Thus, for two non-conjugate elements, the algorithm returns in finite time that they are not conjugate.
Note that unlike the analogous result for residually finite groups, it is not possible here in general to simply consider a countable collection of finite groups such that every finite group embeds in one of them, because the embedding need not be as a conjugacy-closed subgroup.