Читать книгу Invariants And Pictures: Low-dimensional Topology And Combinatorial Group Theory - Vassily Olegovich Manturov - Страница 17

In this section we give a brief overview of two algorithmic problems in the combinatorial group theory which were already mentioned in the context of group diagrams — the word problem and the conjugacy problem.

Consider a group G given by its presentation (1.1) which is effective in the sense that for every word R we can algorithmically determine whether it lies in the set or not. There are two fundamental problems in the combinatorial group theory:

(1)The word problem: is there an algorithm which for any pair of words U, V in the group alphabet determines whether those words are equal in the group G or not?

(2)The conjugacy problem: is there an algorithm which for any pair of words U, V in the group alphabet determines whether those words are conjugate in the group G or not?

Naturally the word problem can be reformulated in the form

“is there an algorithm which for any word W in the group alphabet determines whether W = 1 is in the group G or not?”

because U = V is in the group G if and only if UV⁻¹ = 1 is in the group G.

It turns out that the small cancellation theory is a very useful instrument in the study of the word and conjugacy problems. In particular, the following algorithm (originally due to Dehn, see [Schupp, 1968]) solves the word problem in the groups with the condition C′(λ), .

The Dehn algorithm. The algorithm is inductive, so we may assume that for any word V of the length less than n we can algorithmically determine whether V = 1 is in the group G or not.

Now let W be a word of length n. We may assume that W is cyclically irreducible: for any proper subword of the cyclic word W we may determine by induction whether it equals 1 in the group G or not. If such a subword exists, replacing it with 1 we reduce the length of the word W and by induction solve the word problem for W.

So consider a cyclically irreducible word W, |W| = n. By the Greendlinger theorem if W = 1 in the group G, then the cyclic word W has a subword X such that there exists a relation R = XY ∈ and .

If W does not have such subwords, then we may state that W ≠ 1 in the group G. If such a subword X exists, then replace it with the word Y⁻¹ in the word W. We obtain a word W′ such that W = W′ in the group G and |W′| < |W|, since |Y| < |X|. Therefore by induction we can determine whether W′ = 1 in the group G. Thus the problem for the word W is solved.

The key element of this algorithm is, of course, the Greendlinger theorem which holds for the groups with the condition C′(λ) for .

It is worth mentioning that Goldberg [Goldberg, 1978] proved that for the condition C′(λ) (and the condition C(5) as well) does not give us any relevant information about the group: any group allows a presentation with these conditions. In particular, for such groups the word problem may be algorithmically unsolvable, since it was shown by P.S. Novikov [Novikov, 1955] that there exist finitely defined groups with algorithmically unsolvable word problem.

Note that the Dehn and Goldberg results leave the “gap” for the parameter λ. In fact, Lyndon [Lyndon, 1966] constructed an algorithm for the word problem solution for all groups with the condition C′(λ), and for groups with the condition C(6). It is also worth mentioning that the original Dehn algorithm does not work for the groups with the condition C(6). Those results were obtained by using geometric methods which may be regarded as discreet analogues to the Gauß–Bonnet theorem.