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