2

A. YU. OLSHANSKII AND M. V. SAPIR

It was quickly realized that the main problem would be in preserving

the smallest Turing degree, that is the solvability of conjugacy problem. In

1980, [Col], Collins analyzed existing proofs of Higman's theorem, and dis-

covered that there are essential difficulties. If a finitely generated group C is

embedded into a finitely presented group B using any existing at that time

constructions then the solvability of conjugacy problem in B implies certain

properties of C which are much stronger than solvability of conjugacy prob-

lem. Collins even wrote the following pessimistic comments: "There seems

at present to be no hope to establishing the analogue of Clapham's theorem.

... Furthermore these difficulties seem to be more or less inevitable given the

structure of the proof and probably a wholly new strategy will be needed to

avoid them. For the present the most one can be hoped for is the isolation

of conditions on C that are necessary and sufficient for the preservation of

the solvability of the conjugacy problem in the Higman embedding."

In this paper, we do find a "new strategy" and prove the following result.

Recall (see R. Thompson [Tho]) that a subgroup S of a group !K is called

Frattini embedded if any two elements of 9 that are conjugate in 3i are also

conjugate in 9- Clearly if 9 is Frattini embedded into !K and !K has solv-

able conjugacy problem then 9 has solvable conjugacy problem (by results

from [CM] and [GK], cited above non-Frattini embedded subgroups do not

necessarily inherit solvability of the conjugacy problem).

Theorem 1.1. A finitely generated group has solvable conjugacy problem

if and only if it is Frattini embedded into a finitely presented group with

solvable conjugacy problem.

Moreover we prove the following stronger result solving the original prob-

lem of Collins:

Theorem 1.2. A finitely generated group 9 with recursively enumerable

set of relations has conjugacy problem of r.e. Turing degree a if and only if

9 can be Frattini embedded into a finitely presented group "K with conjugacy

problem of r.e. Turing degree a.

In the forthcoming paper [01Sa4], we will present some corollaries of

these theorems (we did not include the proofs of them here in order not

to increase the difficulty level unnecessarily). In particular, we will show

that one can drop the restriction that 9 is finitely generated in Theorems

1.1, 1.2, replacing it with "countably generated". We shall also show that

a finitely generated group with solvable word, power and order problems

can be embedded into a finitely presented group with solvable word, order,

power, and conjugacy problems. Thus a Higman embedding can greatly

improve algorithmic properties of a group.

In this section, we explain the main ideas which lead us to our construc-

tion. We try to keep notation as simple as possible in this section of the