ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 9, Pages 40–50 (June 24, 2003) S 1079-6762(03)00110-0

THE CONJUGACY PROBLEM FOR GROUPS, AND HIGMAN EMBEDDINGS

A. YU. OL’SHANSKII AND M. V. SAPIR

(Communicated by Efim Zelmanov)

Abstract. For every finitely generated recursively presented group G we construct a finitely presented group H containing G such that G is (Frattini) embedded into H and the group H has solvable conjugacy problem if and only if G has solvable conjugacy problem. Moreover, G and H have the same r.e. Turing degrees of the conjugacy problem. This solves a problem by D. Collins.

In 1961, G. Higman [Hi] published the celebrated theorem that a finitely generated group is recursively presented if and only if it is a subgroup of a finitely presented group. Along with the results of Novikov and Boone [Rot] this result showed that objects from logic (in that case, recursively enumerable sets) have group theoretic characterizations (see Manin [Ma] for the philosophy of Higman embeddings).

Clapham [Cla] (see also corrections in [Va]) was probably the first to investigate properties preserved under Higman embeddings. In particular, he slightly modified the original Higman construction and showed that his embedding preserves solvability (and even the r.e. Turing degree) of the word problem. Valiev [Va] gave a new construction of Higman embedding, and sketched a proof of a much stronger result: every finitely generated recursively presented group G embeds into a finitely presented group H such that the word problem in H reduces to the word problem in G in polynomial time. This implies that if the word problem of a finitely generated group is in P (i.e., can be solved in polynomial time by a deterministic Turing machine), then it can be embedded into a finitely presented group whose word problem is also in P. In [BORS], Birget, Rips and the authors of this paper obtained a group theoretic characterization of NP (nondeterministic polynomial time): a finitely generated group G has word problem in NP if and only if G is embedded into a finitely presented group with polynomial Dehn function.

The conjugacy problem turned out to be much harder to preserve under embeddings. Gorjaga and Kirkinskiĭ [GK] and Collins and Miller [CM] proved that even subgroups of index 2 of finitely presented groups do not inherit solvability or unsolvability of the conjugacy problem.

\begin{matrix}c \\ ◯ \end{matrix}2003 American Mathematical Society

Received by the editors March 2, 2003.

2000 Mathematics Subject Classification. Primary 20F10; Secondary 03D40, 20M05.

Both authors were supported in part by the NSF grant DMS 0072307. In addition, the research of the first author was supported in part by the Russian Fund for Basic Research 02-01-00170 and by the INTAS grant 99-1224; the research of the second author was supported in part by the NSF grant DMS 9978802 and the US-Israeli BSF grant 1999298.

In 1976 D. Collins [KT] posed the following question (problem 5.22): Does there exist a version of the Higman embedding theorem in which the degree of unsolvability of the conjugacy problem is preserved?

It was quickly realized that the main problem would be in preserving the smallest Turing degree, that is, the solvability of the conjugacy problem. In 1980, Collins [Col] analyzed existing proofs of Higman’s theorem and discovered 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 the conjugacy problem in B implies certain properties of C which are much stronger than solvability of the conjugacy problem. 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.”

Recall that a subgroup G of a group H is called Frattini embedded if any two elements of G that are conjugate in H are also conjugate in G. Clearly, if G is Frattini embedded into H and H has solvable conjugacy problem, then G has solvable conjugacy problem.

The following theorem solves the problem of Collins:

Theorem 1. A finitely generated group G has conjugacy problem of recursively enumerable Turing degree α if and only if G can be Frattini embedded into a finitely presented group H with conjugacy problem of the same Turing degree. In particular, 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.

Consider the case when G = ⟨A | E⟩ has decidable conjugacy problem and we want to embed it into a finitely presented group with decidable conjugacy problem (the case when the conjugacy problem in G has an arbitrary r.e. Turing degree is similar). The standard idea is to start with a machine that recognizes the set E and then interpret this machine in a group. Of course we would like to have a machine which is easier to interpret. The most suitable machines for our purposes are the so called S-machines invented by the second author in [SBR] and successfully used in [SBR], [BORS], [OlSa01]. An S-machine works with words which can have complicated structure. Different parts of these words can be elements of different groups (so we do not distinguish between words whose respective parts are equal in the corresponding groups). As in Turing machines, every rule of an S-machine replaces subwords containing state letters by other subwords. The advantage of S-machines is that they are very easily simulated by groups.

Let us start with an S-machine which essentially goes back to C. Miller [Mil] (although Miller did not use S-machines). Assume that A is a symmetric set, that is, it contains the formal inverses of its elements, and let us embed G = ⟨A | E⟩ into some finitely presented group Ḡ = ⟨A ∪ Y | Ē⟩ using, say, the standard Higman embedding. Now consider the S-machine M with one state letter q and the tape alphabet A ∪ Y regarded as a generating set of the free group, and the following commands (each command says which subwords of a word should be replaced and gives the replacement word):

• [q → a^{−1}qa], for every a ∈ A ∪ Y,

[figure: T_{1}; T_{2}; T_{3}; P_{1}; P_{2}; P′_{2}; P′_{1}; T_{m}] Figure 1.

• [q → rq], for every r ∈ Ē.

The first set of rules allows the state letter to move freely along a word of the form uqv, where u, v are words from the free group on A ∪ Y. Such words are called admissible words for M.

The second set of rules allows us to insert any relation from Ē into the word (we are also allowed to insert and remove subwords of the form aa^{−1} because A ∪ Y is a generating set of a free group).

It is easy to see that a word qu, where u is a word over A, is recognized by this machine (that is, the machine takes it to the word q) if and only if u = 1 in the group Ḡ, that is, if and only u = 1 in G (because G is embedded into Ḡ).

Now we present the ideas of a Higman embedding based on M. Let T_{1}, T_{2}, …, T_{m} = W_{0} be an accepting computation of M, that is, a sequence of admissible words such that T_{i+1} is obtained from T_{i} by applying an S-rule of M, the last word in this sequence being equal to q in the free group.

Suppose that some words P_{i} and P′_{i} over a certain alphabet (it is included in the finite generating set of the group we are constructing) correspond to this S-rule, and modulo some set of group relations Z we have, for every i = 1, …, m − 1,

P_{i}T_{i} = T_{i+1}P′_{i} ,

that is, we have a van Kampen diagram with the boundary label P_{i}T_{i}(P′_{i})^{−1}T_{i+1}^{−1}. Then P T_{1} = W_{0}P′, where P = P_{m−1} … P_{2}P_{1}, P′_{i} = P′_{m−1} … P′_{2}P′_{1}. The corresponding van Kampen diagram Δ has the form of a trapezoid (Figure 1).

For example, if we use the S-machine M described above, then the presentation Z is easy to describe: for every rule τ = [q → uqv] we have the following relations in Z: θ_{τ}^{−1}qθ_{τ} = uqv, θ_{τ} a = aθ_{τ} for every a ∈ A ∪ Y (the letters θ_{τ} corresponding to the rules of M are added to the generating set). In this case the words P_{i}, P′_{i} are of length 1, and are equal to θ_{τ}.

The words P and P′ contain the history of our computation, because P_{i} and P′_{i} correspond to S-rules applied during the computation. The words T_{1} and T_{m} are labels of the bottom and the top of the trapezoid.

If the set of relations Z is chosen carefully (see [SBR], [BORS], [OlSa01]), then the converse is also true. Thus the word P T_{1}(P′)^{−1}W_{0}^{−1} is written on the boundary of a trapezoid if and only if the word T_{1} is accepted.

[figure: hub; 1; ⋯; 2; N]

Figure 2.

The next step is to consider N ≥ 1 copies of our trapezoid with labels taken from different alphabets. For technical reasons (similar to the hyperbolic graphs argument in [SBR], [Ol2], [BORS]) we need N to be even and large enough (say, N ≥ 8). Let us choose disjoint alphabets in different copies of the trapezoid. Then we can glue two copies of the trapezoid by using a special letter k which conjugates letters on the right side of the first trapezoid with letters on the left side of the mirror image of the other copy. Notice that if P and P′ are copies of each other then we can also glue the right side of one trapezoid to the left side of the other without taking mirror images. Of course the conjugacy relations involving letter k should be added into the set of group relations Z.

Suppose that T_{m} is equal to q, i.e., the word T_{1} is accepted by the machine. If we connect the first copy of Δ with the second copy, then with the third copy, and finally connect the Nth copy with the first copy, using different letters k_{2}, …, k_{N}, k_{1}, we get an annular diagram, a ring. The outer boundary of this ring has label K(T_{1}) of the form k_{1}T′_{1}k_{2}^{−1}(T′′_{1})^{−1} … (here we use the fact that N is even). The words T′_{1}, …, T_{1}^{(N)} are different copies of T_{1}. The inner boundary has label k_{1}q′k_{2}^{−1}(q′′)^{−1} … (this word is called the hub) ( Figure 2 shows the diagram in the case of N = 4).

We add the hub to the list of defining relations Z. Now with every word T of the form uqv, where u, v are words in A ∪ Y, we have associated the word K(T), and we see that if T is accepted, then K(T) is equal to 1 modulo Z. Again, if Z is chosen carefully, then the converse is also true: if K(T) is equal to 1 modulo Z then T is accepted by S. Thus we have an interpretation of S in the group generated by the tape alphabet and the state alphabet of S, the set Θ, and the set {k_{1}, …, k_{N}}, subject to the relations from Z.

The diagram on Figure 2 is called a disk. The trapezoids forming this disk are numbered in the natural order (from 1 to N).

We assume that the copy of the alphabet A used in the first subtrapezoid of a disk coincides with A itself (the generating set of G).

Denote the group given by the presentation Z we have got so far by G(M). There are several ways to use the group G(M) to embed G into a finitely pre-

sented group. We use a method described in [OlSa01].

Consider N − 1 new copies of the trapezoid Δ. Number these trapezoids by 2′, …, N′. Identify the copy of A (but not Y) and the state letter q in the trapezoid number i′ with the copy of A and the copy of q in the “old” trapezoid number i. Now glue the trapezoid number 2′ with the trapezoid number 3′ using the letter k_{3} (as before), then glue in the trapezoid number 4′ and so on, but glue the trapezoid number N′ with the trapezoid number 2′ using k_{1}qk_{2}^{−1} (that will be possible because, as it turns out, in that case the words P, P′ will be copies of each other). Thus, conjugation of the letters on the side of the trapezoid number N′ by k_{1}qk_{2}^{−1} gives the letters of the side of the mirror image of the trapezoid number 2′. Let us add the relations used in the new trapezoids and the conjugation relations (involving k_{i}) to Z.

The resulting picture is an annular diagram. The inner boundary of it is labelled by the hub. If we add the hub to the diagram, we get a van Kampen diagram which also looks like a disk but has N − 1 sectors. The outer boundary of this new disk is labelled by the word k_{1}qk_{2}^{−1}V, where V is the suffix of K(qu) staying after k_{2}^{−1}. Thus the word k_{1}qk_{2}^{−1}V and the word k_{1}quk_{2}^{−1}V are both equal to 1 modulo Z, so Z implies u = 1. We denote by H the group given by the set of relations Z that we have constructed.

We have proved that the identity map on A can be extended to a homomorphism from G to the subgroup ⟨A⟩ of the group H given by the set of relations Z. It is possible to show that this homomorphism is injective, so G is embedded into H.

Unfortunately, even if G has solvable conjugacy problem, H may have unsolvable conjugacy problem. In fact the difficulties are similar to those described in [Col]. Let us give just one example.

Consider two pairs of words u_{1}, u_{2} and v_{1}, v_{2} over the alphabet A (we can view these words as elements of G). Let q be the first state letter in K(qu). Consider the words W_{1} = q^{−1}u_{1}qu_{2}q^{−1} and W_{2} = q^{−1}v_{1}qv_{2}q^{−1}. Suppose that there exists a word W (A) in the alphabet A such that W (A)u_{1}W (A)^{−1} = v_{1}, W (A)u_{2}W (A)^{−1} = v_{2}. Let W (A) = a_{1}a_{2} … a_{k}, a_{i} ∈ A. For every a ∈ A, let θ(a) correspond to the S-rule of the form [q → a^{−1}qa]. Consider the word W (Θ) = θ(a_{1})θ(a_{2}) … θ(a_{k}). Then it is easy to see that W (θ)W_{1}W (θ^{−1}) = W_{2}. Thus if the pair (u_{1}, u_{2}) is conjugate to the pair (v_{1}, v_{2}) in G, then the words W_{1} and W_{2} are conjugate in G. One can also prove that the converse statement is true. In this example, pairs of words can be obviously replaced by any t-tuples of words, t ≥ 2. Therefore, if the conjugacy problem is solvable in G, then the conjugacy of t-tuples of elements in G is solvable. It is known [Col] that there exists a finitely generated group G with solvable conjugacy problem and unsolvable problem of conjugacy for sequences of elements. For such a group G the group H has undecidable conjugacy problem.

Fortunately, since S-machines are easier to simulate in groups than other types of Turing machines, we can overcome this difficulty (and many others) by modifying our machine M (see below).

It is important to mention that we cannot allow all parts of the admissible words to be arbitrary group words. To avoid long computations without inserting new relation from Ē, we had to require that certain subwords of admissible words stay positive during the computation. This is a major difference between the S-machine used in the proof of Theorem 1 and the S-machine used in our previous papers.

In order to keep these subwords positive we use a trick that goes back to Novikov, Boone and Higman (see Rotman [Rot]). They used a special letter x and Baumslag-Solitar relations of the form a^{−1}xa = x^{2} for every a in the tape alphabet of the machine. The idea is that if we have relations a^{−1}xa = x^{2} for all a ∈ A and a word u^{−1}xu, where u is a reduced word in A, is equal modulo these relations to a power of x, then the first letter of u is positive. Notice that one problem with using the x-letters and Baumslag-Solitar relations is that, since N − 1 is odd, we cannot use x-letters in the second disk described above (indeed, otherwise it would be impossible to glue the N −1 sectors together since the words P and P′ would not be copies of each other). Thus we need to consider two S-machines (one responsible for the first disk, the other for the second disk) which are very similar but have different “hardware”: the admissible words of the first machine must have positive parts described above, and the admissible words of the second machine do not have to satisfy this restriction.

Now let us briefly describe the strategy of the proof that the conjugacy problem in H is solvable. As in our previous papers, the main tool in this paper is bands (other people call them “strips”, “corridors”, etc.).

In terms of annular (Schupp) diagrams, our task is the following: given two words u and v in generators of H, find out if there exists an annular diagram over the presentation of H with boundary labels u and v. It turns out that any annular diagram over H (after removing some parts of recursively bounded size) becomes a diagram of one of three main types: a ring (where the boundary labels contain k-letters but do not contain θ-letters, where k-letters and θ-letters belong to the alphabets K and Θ∪Θ̄, respectively, defined below, and all maximal θ-bands are annuli surrounding the hole of the diagram), a roll (where the boundary label does not contain k-letters but contains θ-letters; all maximal k-bands are annuli surrounding the hole), and a spiral (where the boundary labels contain both kletters and θ-letters; both the k-bands and the θ-bands start and end on different boundary components, and each θ-band crosses each k-band many times. Different methods are used to treat different cases. Roughly speaking, the study of rings amounts to studying the lengths of computations of our S-machines, the study of rolls amounts to the study of the space complexity (how much space is needed by the machines during a computation), and the study of spirals amounts to the study of computations with periodic history. The x-letters and the Baumslag-Solitar relations allow us to treat the case of rings, but they cause the main technical difficulties in the cases of rolls and spirals.

Remark 1. Notice that even though the conjugacy problem in H is solvable provided it is solvable in G, the computational complexity of the conjugacy problem in H can be higher than in G. In particular, the algorithm solving the conjugacy problem in H uses Makanin’s algorithm [Mak] for solving systems of equations in the free group. Thus we do not know whether it is possible to embed any finitely generated group with conjugacy problem, say, in NP into a finitely presented group with conjugacy problem in NP.

Now let us give a precise description of the S-machines S and S̄ and the group H simulating these machines.

Fix an even number N ≥ 8. Let A = {a_{1}, …, a_{m}}, A ∪ Y = {a_{1}, …, am̄}. The set K of state letters of S consists of letters z_{j}(r, i), where z ∈ {K, L, P, R}, j = 1, …, N, r ∈ Ē, i ∈ {1, 2, 3, 4, 5}.

We also define the set of basic letters K̃ which consists of letters z_{j}, where z ∈ {K, L, P, R}, j = 1, …, N, and their inverses. If z is a basic letter, r ∈ Ē, i ∈ {1, 2, 3, 4, 5}, then z(r, i) ∈ K. If U is a word in K̃ and other letters, r ∈ Ē, i ∈ {1, 2, 3, 4, 5}, then U(r, i) is a word obtained from U by replacing every letter z ∈ K̃ by z(r, i). The parameters r and i in the letter z(r, i) or in the word U(r, i) will be called the Ē-coordinate and the Ω-coordinate of the word.

The set A^{±1} of tape letters of the machine S consists of letters a_{i}(z)^{±1}, where i = 1, …, m̄, z ∈ K̃. For every z ∈ K̃ we define A(z) as the set of all a_{i}(z), i = 1, …, m̄.

Let Σ̃ be the following word (considered as a cyclic word):

K_{1}L_{1}P_{1}R_{1}K_{2}^{−1}R_{2}^{−1}P_{2}^{−1}L_{2}^{−1}K_{3}L_{3}P_{3}R_{3}K_{4}^{−1} … K_{N}^{−1}R_{N}^{−1}P_{N}^{−1}L_{N}^{−1}.

Notice that for every basic letter z precisely one of z and z^{−1} occurs in the word Σ̃. The word Σ = Σ̃(∅, 1) will be called the hub.

For every z ∈ K̃ ∪ K̃^{−1} we denote by z_{−} the letter immediately preceding z in the cyclic word Σ̃ or in Σ̃^{−1}. If z′ = z_{−} then we set z = z′_{+}. Similarly we define z_{−} and z_{+} for z ∈ K.

The language of admissible words of the machine S consists of all reduced words of the form W ≡ y_{1}u_{1}y_{2}u_{2} … y_{t}u_{t}y_{t+1}, where y_{1}, …, y_{t+1} ∈ K^{±1}, u_{i} are words in A(y_{i}), i = 1, 2, …, t, and for every i = 1, 2, …, t, either y_{i+1} ≡ (y_{i})_{+} or y_{i+1} ≡ y_{i}^{−1}. (Here ≡ is the letter-for-letter, or graphical, equality of words.) The projection of y_{1} … y_{t+1} onto K̃ is called the base of the admissible word W. The subword y_{i}u_{i}y_{i+1} is called the y_{i}y_{i+1}-sector of the admissible word W, i = 1, 2, …. The word u_{i} is called the inner part of the y_{i}y_{i+1}-sector. We assume that the inner part of any zL_{j}-, zP_{j}- or R_{j}z-sector of W and W^{−1} is a positive word (z ∈ K̃), that is, it does not contain a^{−1} for any a ∈ A.

All rules of S have the form [k_{1} → v_{1}k′_{1}u_{1}, …, k_{n} → v_{n}k′_{n}u_{n}], where the projections k_{i} and k′_{i} on K̃ will always be the same, and the Ē-coordinates and the Ω-coordinates of all state letters k_{1}, …, k_{n} (resp. k′_{1}, …, k′_{n}) will be the same. In addition, each u_{i} (resp. v_{i}) will contain only letters from A(k_{i}) (resp. A((k_{i})_{−})), i = 1, …, n.

For every word W in the alphabet {a_{1}, …, am̄} and every k ∈ K̃, W (k) will denote the word obtained from W by substitution a_{i} → a_{i}(k), i = 1, …, m̄.

In order to simplify notation, we shall write a rule τ of the S-machines S in the form

[k_{1} → v_{1}k_{1}u_{1}, …, k_{n} → v_{n}k_{n}u_{n}; r → r′, ω → ω′],

where k_{i} ∈ K̃, v_{i} are words in A((k_{i})_{−}), and u_{i} are words in A(k_{i}). We shall also omit k in u(k) if the value of k is obvious from the context.

Some of the arrows in a rule τ can have the form k_{i}→^{ℓ}. This means that the rule τ can be applied to an admissible word W only if the inner part of k_{i}k′_{i}-sectors and k_{i′′}(k_{i})_{+}-sectors in W are empty words and k′_{i} = (k_{i})_{+}, k_{i′′} = k_{i} (i.e., k′_{i} ≠ k_{i}^{−1} and k_{i′′} ≠ (k_{i})_{+}^{−1}). In that case u(k) and v(k) must be empty.

Let us expand the definition of u_{τ} (k), v_{τ} (k_{−}) to the base letters not occurring in the rule by assuming that in this case u_{τ} (k) and v_{τ} (k_{−}) are empty.

By definition, to apply the rule τ = [z_{1} → v_{1}z_{1}u_{1}, …, z_{s} → v_{s}z_{s}u_{s}; r → r′, ω → ω′] to an admissible word W = y_{1}w_{1}y_{2} … w_{k}y_{k+1} means to replace each y_{i}(r, ω) with v_{i}y_{i}(r′, ω′)u_{i}, reduce the resulting word, and trim the prefix v_{τ} ((y_{1})_{−}) from the beginning and the suffix u_{τ} (y_{k+1}) from the end of the resulting word. The rule τ is called applicable to W if:

(1) for every z ∈ K̃ such that τ locks zz_{+}-sectors, the inner parts of zz_{+}-sectors in W are empty words, and W does not have zz^{−1}-sectors or z_{+}^{−1}z_{+}-sectors; (2) the resulting word W′ is again admissible (that is, the inner parts of all

sectors which are supposed to be negative or positive are such). The rules from S^{+} ⊂ S, described below, will be called positive, the inverses

of these rules will be called negative, and each rule of S will be either positive or negative.

The set S^{+} consists of 10 subsets S^{+}(ω), ω ∈ {1, 12, 2, 23, 3, 34, 4, 45, 5, 51}. The set S^{+}(1) consists of rules τ(1, ∅, i), where i = 1, …, m̄. The rule τ(1, ∅, i)

has the form

[(L_{j})_{−} →^{ℓ} (L_{j})_{−}, P_{j} → a_{i}P_{j}a_{i}^{−1}, R_{j} →^{ℓ} R_{j}, j = 1, …, N; ∅ → ∅, 1 → 1].

The meaning of this set of rules is that the state letter P_{j} can freely move (if the (Ē, Ω)-coordinates are (∅, 1), and L_{j}-letters and R_{j}-letters stay next to K_{j}-letters).

The set S^{+}(12) consists of one rule τ(12, r) for each r ∈ Ē\{∅}:

[(L_{j})_{−} →^{ℓ} (L_{j})_{−}, R_{j} →^{ℓ} R_{j}, j = 1, …, N; ∅ → r, 1 → 2].

This rule does not insert any tape letters; it simply changes the Ē- and Ω-coordinates of state letters. This rule prepares the machine for step 2.

The set S^{+}(2) consists of rules τ(2, r, i), where r ∈ Ē, i = 1, …, m̄:

τ(2, r, i) = [L_{j} → a_{i}L_{j}a_{i}^{−1}, R_{j} →^{ℓ} R_{j}, j = 1, …, N; r → r, 2 → 2].

The meaning of these rules is that they allow the state letters L_{j} to move freely while R_{j} stays next to (R_{j})_{+}.

The set S^{+}(23) consists of one rule for each r ∈ Ē:

τ(23, r) = [L_{j} →^{ℓ} L_{j}, R_{j} →^{ℓ} R_{j}; r → r, 2 → 3].

The meaning of this rule is that the machine can start step 3 when L_{j} and P_{j} meet (that is when the inner parts of L_{j}z-sectors are empty).

The set S^{+}(3) consists of one rule for each r ∈ Ē and each i from 1 to m̄:

τ(3, r, i) = [L_{j} →^{ℓ} L_{j}, R_{j} → a_{i}^{−1}R_{j}a_{i}, j = 1, …, N; r → r, 3 → 3].

These rules allow the state letter R_{j} to move freely between P_{j} and (R_{j})_{+}. The set S^{+}(34) consists of one rule for each nonempty r ∈ Ē:

τ(34, r) = [L_{j} →^{ℓ} rL_{j}, P_{j} →^{ℓ} P_{j}, j = 1, …, N; r → r, 3 → 4].

This rule can be applied when the state letters L_{j}, P_{j}, R_{j} meet together; it inserts r to the left of the state letters L_{j}, and prepares the machine for step 4.

The set S^{+}(4) consists of rules τ(4, r, i), r ∈ Ē, i = 1, …, m̄:

τ(4, r, i) = [L_{j} → a_{i}L_{j}a_{i}^{−1}, P_{j} →^{ℓ} P_{j}, j = 1, …, N; r → r, 4 → 4].

These rules allow the state letter L_{j} to move freely between (L_{j})_{−} and P_{j}. The set S^{+}(45) consists of one rule for each r ∈ Ē:

τ(45, r) = [(L_{j})_{−} →^{ℓ} (L_{j})_{−}, P_{j} →^{ℓ} P_{j}, j = 1, …, N; r → r, 4 → 5].

The machine can start step 5 when L_{j} and (L_{j})_{−} meet.

The set S^{+}(5) consists of one rule for each r ∈ Ē, i = 1, …, m̄:

τ(5, r, i) = [(L_{j})_{−} →^{ℓ} (L_{j})_{−}, R_{j} → a_{i}^{−1}R_{j}a_{i}, j = 1, …, N; r → r, 5 → 5].

These rules allow R_{j} move freely between P_{j} and (R_{j})_{+}.

Finally the set S^{+}(51) consists of one rule for each r ∈ Ē:

τ(51, r) = [(L_{j})_{−} →^{ℓ} (L_{j})_{−}, R_{j} →^{ℓ} R_{j}, j = 1, …, N; r → ∅, 5 → 1].

The cycle is complete, the machine can start step 1 again when (L_{j})_{−} meets L_{j}, and R_{j} meets (R_{j})_{+}.

The S-machine S̄ is similar to S, so we only present the differences between S and S̄.

We introduce disjoint copies of sets K, K̃, A, and denote them by K̄, ¯ K̃, Ā, respectively. In order to make S and S̄ “communicate”, we identify z_{j}(∅, 1) with z̄_{j}(∅, 1), z ∈ {K, L, P, R}, j = 1, …, N, and a_{i}(P_{j}) with ā_{i}(P̄_{j}), i = 1, …, m, j = 1, …, N. Notice that we do not identify a_{m+1}, …, am̄ with their “bar”-brothers ā_{m+1}, …, ām̄, and we do not identify a_{i}(z) with ā_{i}(z) for z ≠ P_{j}. Notice also that this identification of letters makes the word Σ̄ coincide with the hub Σ.

Admissible words of S̄ have the same form as admissible words of S except for the following differences:

• All letters are replaced by their “bar”-brothers.

• We drop the restriction that certain parts of admissible words are positive (negative).

• The K̄_{1}z-, L̄_{1}z-, P̄_{1}z- and R̄_{1}z-sectors must be empty (z ∈ K̃). Thus in every admissible word of S̄ the part between K̄_{1} and K̄_{2}^{−1} contains no Ā-letters.

The rules of S̄ are obtained from the corresponding rules of S by replacing every letter by its “bar”-brother and by removing letters from Ā(z̄_{1}), z ∈ {K, L, P, R}. Thus rules of S̄ do not insert any Ā-letters in the interval between K̄_{1} and K̄_{2}^{−1}, and work in other parts of the admissible words just as S.

In order to convert the machine S into a list of defining relations, we need to introduce one more set of letters X = {x(a, τ) | a ∈ A\ ⋃_{j} A(P_{j}), τ ∈ S^{+}}.

For every τ ∈ S, we also consider a map α_{τ} from A to the free group generated by A and X ∪ X^{−1}. Let τ ∈ S^{+}, a ∈ A(z), z ∈ K̃. Then

α_{τ} (a) = \{ \begin{matrix}x(a, τ)a & if z = K_{j}, j = 1, …, N, \\ x(a, τ)a & if z = L_{j}, j = 1, …, N, \\ a & if z = P_{j}, j = 1, …, N, \\ ax(a, τ) & if z = R_{j}, j = 1, …, N. \end{matrix}

The definition of α_{τ^{−1}}, τ ∈ S^{+}, is obtained from the definition of α_{τ} by replacing all X -letters with their inverses.

We expand these maps to all words in the alphabet A ∪ A^{−1} ∪ K ∪ K^{−1} in the natural way (mapping letters from K ∪ K^{−1} to themselves).

Also with every τ ∈ S^{+}, we associate a set of letters

Θ(τ) = {θ(τ, z) | z ∈ {K_{j}, L_{j}, P_{j}, R_{j}}, j = 1, …, N}.

Let Θ(z) = {θ(τ, z) | τ ∈ S^{+}}, z ∈ {K_{j}, L_{j}, P_{j}, R_{j}}. Finally the union of all Θ(τ) is denoted by Θ.

Let τ = [U_{1} → V_{1}, …, U_{k} → V_{k}; r → r′, l → l′] be one of the rules of S^{+}. Let u(z), v(z), z ∈ K̃, be the words associated with this rule as above.

Then we associate with τ the following list of main relations:

θ(τ, z_{−})^{−1}z(r, l)θ(τ, z) = α_{τ^{−1}}(v_{i})z(r′, l′)α_{τ^{−1}}(u_{i}), i = 1, …, k.

Let z ∈ {K_{j}, L_{j}, P_{j}, R_{j}}, j = 1, …, N, a, b ∈ A(z). Then we add auxiliary Θ-relations:

θ(τ, z)^{−1}α_{τ} (a)θ(τ, z) = α_{τ^{−1}}(a) if τ does not lock thezz_{+}-sector

\begin{matrix}ax(b, τ)a^{−1} = x(b, τ)^{4} & if z = K_{j} or z = L_{j}, \\ a^{−1}x(b, τ)a = x(b, τ)^{4} & if z = R_{j}. \end{matrix}

Finally let b′ be the “brother” of b in the alphabet A(z_{−}) if z = K_{j} or z = L_{j}. Then we need auxiliary (k, x)-relations:

\begin{matrix}z(r, i)x(b, τ) = x(b′, τ)z(r, i) & if z = K_{j}, \\ z(r, i)x(b, τ) = x(b′, τ)^{4}z(r, i) & if z = L_{j}. \end{matrix}

Let R(S) be the set of all relations corresponding to the set of S-rules S^{+}. To convert S̄ into a set of relations we do not need X -letters, but we need “bar”-

brothers of the letters from Θ. Denote this set by Θ̄. The easiest way to explain how to convert an S-rule of S̄ to a set of relations is the following: convert it above, then add bars to all letters, replace all letters from X and from ⋃ Ā(z_{1}), z ∈ {K, L, P, R} by 1. Let R(S̄) be the set of all relations corresponding to S̄^{+}.

Finally the group H is given by the set of generators K ∪ K̄ ∪ A ∪ Ā∪ Θ ∪ Θ̄ ∪ X and the set of relations R = R(S) ∪ R(S̄) ∪ {Σ}.

The complete proof of Theorem 1 can be found in [OlSa02].

References

[BORS] J. C. Birget, A. Yu. Ol’shanskii, E. Rips, M. V. Sapir. Isoperimetric functions of groups and computational complexity of the word problem. Annals of Mathematics, 156, 2 (2002), 467–518.

[Cla] C. R. J. Clapham. An embedding theorem for finitely generated groups, Proc. London. Math. Soc. (3), 17 (1967), 419–430. MR 36:5199

[Col] Donald J. Collins. Conjugacy and the Higman embedding theorem. Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), pp. 81–85, Stud. Logic Foundations Math., 95, North-Holland, Amsterdam-New York, 1980. MR 81m:20051

[CM] D. J. Collins, C. F. Miller III. The conjugacy problem and subgroups of finite index. Proc. London Math. Soc. (3) 34 (1977), no. 3, 535–556. MR 55:8187

[GK] A. V. Gorjaga, A. S. Kirkinskiĭ. The decidability of the conjugacy problem cannot be transferred to finite extensions of groups. Algebra i Logika 14 (1975), no. 4, 393–406. (Russian) MR 54:2813

[Hi] G. Higman. Subgroups of finitely presented groups. Proc. Roy. Soc. Ser. A, 262 (1961), 455–475. MR 24:A152

[KT] Kourovka Notebook. Unsolved Problems in Group Theory. 5th edition, Novosibirsk, 1976.

[Mak] G. S. Makanin. Equations in a free group. Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199–1273, 1344; English transl., Math. USSR-Izv. 21 (1983), 546–582. MR 84m:20040

[Ma] Yu. I. Manin. The computable and the noncomputable, “Sovetskoe Radio”, Moscow, 1980 MR 82i:03002

[Mil] Charles F. Miller III. On group-theoretic decision problems and their classification. Annals of Mathematics Studies, No. 68. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 46:9147

[Ol2] A. Yu. Ol’shanskii. On distortion of subgroups in finitely presented groups. Mat. Sb. 188 (1997), no. 11, 51–98; English transl., Sb. Math. 188 (1997), no. 11, 1617–1664. MR 99a:20038

[OlSa01] A. Yu. Ol’shanskii, M. V. Sapir. Length and area functions on groups and quasi-isometric Higman embeddings. Internat. J. Algebra Comput. 11 (2001), no. 2, 137–170. MR 2002b:20058

[OlSa02] A. Yu. Olshanskii, M. V. Sapir. The Conjugacy Problem and Higman Embeddings. Preprint arXiv:math.GR/0212227.

[Rot] J. Rotman. An Introduction to the Theory of Groups. Allyn & Bacon, third edition, 1984. MR 85f:20001

[SBR] M. V. Sapir, J. C. Birget, E. Rips. Isoperimetric and isodiametric functions of groups, Annals of Mathematics, 157, 2 (2002), 345–466.

[Va] M. K. Valiev. On polynomial reducibility of the word problem under embedding of recursively presented groups in finitely presented groups. Mathematical foundations of computer science 1975 (Fourth Sympos., Mariánské Lázně, 1975), pp. 432–438. Lecture Notes in Comput. Sci., Vol. 32, Springer, Berlin, 1975. MR 54:413

Mathematics Department, Vanderbilt University, Nashville, Tennessee 37240, and Mechanics-Mathematics Department, Chair of Higher Algebra, Moscow State University, Moscow, Russia

   E-mail address: alexander.olshanskiy@vanderbilt.edu   olshan@shabol.math.msu.su

Mathematics Department, Vanderbilt University, Nashville, Tennessee 37240

   E-mail address: msapir@math.vanderbilt.edu