Invariants And Pictures: Low-dimensional Topology And Combinatorial Group Theory. Vassily Olegovich Manturov

alt="figure"/>.

      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.

1.4The Diamond lemma

      In the present section we briefly consider a well-known Newman lemma (also known as the Diamond lemma in the literature) [Newman, 1942]. This lemma is a very powerful tool for constructing a minimal form, proving uniqueness theorems and solving word and other problems.

      Let A be a set and let → denote a binary relation on the set A.

      Definition 1.10. A relation → is called well-founded (or Noetherian) if every non-empty subset X ⊂ A has a minimal element, that is, there exists a ∈ X such that the relation a → b does not hold for any b ∈ X.

      Alternatively, one can say that a relation is well-founded if the set A does not contain any infinite decreasing chains in the sense of that relation.

      For a relation → let us denote by its reflexive transitive closure.

      Definition 1.11. A relation → is called locally confluent if for every three elements a, b, c ∈ A such that

      there exists an element d ∈ A such that

      

      This condition is sometimes formulated in the form “every covering is bounded below” in the system (A, →).

      Definition 1.12. The relation → is called confluent if for every three elements a, b, c ∈ A such that

      there exists an element d ∈ A such that

      Lemma 1.5 (The Diamond lemma [Newman, 1942]). If a relation → is well-founded and locally confluent, then the relation → is confluent.

      Proof. Let the relation → be well-founded and locally confluent and let a, b, c ∈ A be elements such that a b, a c. We need to prove the existence of an element d ∈ A such that b d, c d.

      Let us call two elements y, z ∈ A joinable if there exists an element h ∈ A such that y h and z h. The proof is by the following induction made possible by the well-foundedness of the relation →. Let us say that the property P is satisfied for an element x ∈ A and write P(x) if any elements y, z ∈ A, such that x y and x z, are joinable. Obviously the statement of the lemma is equivalent to P(x) for all x ∈ A.

      If we denote by →⁺ the transitive closure of the relation →, the induction is of the form “to show P(x) under the assumption P(t) for all t such that x →⁺ t”. This induction is valid because the relation → is well-founded.

      Now let us consider an element x ∈ A and the divergence x y, x z. If x = y or x = z, y and z are joinable immediately. Otherwise, we have x → y₁ y, x → z₁ z. Due to local confluency of the relation →, there exists an element u such that y₁ u, z₁ u. By induction, there exists an element v such that y v, u v. Finally, by induction again, there exists an element w such that v w, z w. Therefore the elements y and z are joinable. This construction is depicted in Fig. 1.4.

      This lemma essentially means that, if the conditions of well-foundedness