THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 7
Consider N 1 new copies of the trapezium A. Number these trapezia
by
2/',
...,iV. Identify the copy of A (but not Y) and the state letter q in
the trapezium number i' with the copy of A and the copy of q in the "old"
trapezium number i. Now glue the trapezium number 2' with the trapezium
number 3' using letter ks (as before), then glue in the trapezium number 4/
and so on, but glue the trapezium number
N;
with the trapezium number
2! using kiqk^1 (that would be possible because as it will turn out in that
case the words P, P' will be copies of each other). That is conjugation of the
letters on the side of the trapezium number N' by k\qk^1 gives the letters
of the side of the mirror image of the trapezium number
2/'.
Let us add the
relations used in the new trapezia and the conjugation relations (involving
hi) 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-l sectors. The outer
boundary of this new disk is labelled by the word k\qk^ V where V is the
suffix of %{qu) staying after
fc^"1.
Thus the word kiqk^V and the word
kiquk^V are both equal to 1 modulo Z, so Z implies u = 1. Let us call the
group given by the set of relations Z that we have constructed by Oi.
We have proved that the identity map on A can be extended to a homo-
morphism from 9 to the subgroup (A) of the group !K given by the set of
relations Z. It is possible to show that this homomorphism is injective, so
9 is embedded into !K.
Suppose that 9 has solvable conjugacy problem. Is it true that !K has
solvable conjugacy problem? The answer is "not always". Let us give two
examples.
Exampl e 1. Consider two pairs of words u\,U2 and v\,V2 over the
alphabet A (we can view these words as elements of S). Let q be the first
state letter in X(qu). Consider the words W\
q~lu\qu2q~l
and W2
q~lv\qv2q~l. Suppose that there exists a word W(A) in the alphabet A such
that
W(A)uiW{A)~l
=
vl,W{A)u2W{A)-1
= v2. Let W(A) = a1a2...ak,
di G A. For every a G A let 9(a) correspond to the S-rule of the form
[q
a~1qa\.
Consider the word W(Q) 6 (ai)0(a2)...0(a/c). Then it is easy
to see that W(6)W\W(9~l) = W2. Thus if the pair (1^1,^2) is conjugated
to the pair (t'l, ^2) in S then the words W\ and W2 are conjugate in S- One
can also prove that the converse statement is also 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 9 then the conjugacy of
t-tuples of elements in S is solvable. It is known [Col] that there exists a
finitely generated group S with solvable conjugacy problem and unsolvable
problem of conjugacy for sequences of elements. For such a group 9 the
group 3i has undecidable conjugacy problem.
Example 2. Take two pairs of words (1/1,^2), (^1^2) over one of the
copies of the alphabet A, say, A! 7^ A, let q! be the corresponding copy of
Previous Page Next Page