Conjugacy-separable and all homomorphisms to any finite group can be listed in finite time implies solvable conjugacy problem

From Groupprops
Jump to: navigation, search

Suppose G 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, G is a group with solvable conjugacy problem.

Related facts

Similar facts

Applications

Proof

Proof outline

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:

  1. Consider the list of all finite groups up to isomorphism. Enumerate them as K_1,K_2,\dots,.
  2. For each i: Construct the list of all homomorphisms from G to K_i (possible by assumption on G). For each homomorphism, evaluate the image of the two words under the homomorphism as elements of K_i. If the images are not conjugate in K_i, then return that the word does not represent the identity element of G.

Since G 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 K_n, so homomorphisms to K_n 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.