Group calculus

An associative calculus in which the natural group requirement of the existence of an inverse operation is effectively fulfilled. In fact, an associative calculus is said to be a group calculus [1], [15] if it is possible to construct for it an inverting algorithm, i.e. an algorithm such that for any word over the alphabet of the following conditions are satisfied: 1) is defined and is also a word over ; 2) the words and are equivalent to the empty word in (here, the term "algorithm" must be understood in some exact meaning of the word, e.g. as a normal algorithm).

The most useful group calculi are those of a special type (the so-called inversive calculi, cf. [2]), in which the existence of the inverting algorithm is ensured by a suitable choice of alphabets and lists of relations: The alphabet of an inversive calculus has even length, for each of its letters there exists an explicit inverse letter , and the list of relations includes a complete collection of the so-called trivial relations, i.e. relations with empty words on their right-hand sides, while the form of their left-hand sides is .

The importance of group calculi consists in the fact that they are representations of finitely-presented groups (cf. also Finitely-presented group). A group calculus , like any other associative calculus, generates in a standard manner (cf. Associative calculus) a finitely-presented associative system , which is a group since has an inverting algorithm. The algorithmic problem of recognizing word equivalence in a group calculus is the identity problem (word problem) for the finitely-presented group , stated in terms of the group calculus. This is the first one of a list of fundamental decidability problems formulated in 1911 by M. Dehn [3] for finitely-presented groups. Several authors found a positive solution of this problem for groups definable by special types of group calculi. It was obtained, in particular, for groups defined by inversive calculi with one non-trivial relation [4]. P.S. Novikov in 1952 ([5], [6]) was the first to construct an example of a finitely-presented group with an unsolvable word problem, i.e. a group generated by a group calculus for which no algorithm in an exact sense of the word (e.g. a Turing machine or a normal algorithm) can be constructed in order to solve the word problem in this calculus. This example gives a negative solution to the word problem for a given finitely-presented group, allowing for the modern precise statement of this problem as given by the theory of algorithms (cf. Church thesis). Other examples of such group calculi were introduced later (see, for example, , [8]).

The example of Novikov just mentioned also gives a negative solution for Dehn's second fundamental problem — the problem on recognizing word pairs which are conjugate in a given group calculus. Subsequently, Novikov [9] gave a simpler negative solution of the conjugacy problem, which is independent of this example.

Of great interest from the algebraic point of view is the study of properties of a group calculus that are invariant under isomorphisms of group calculi; these are then properties of abstract finitely-presented groups. S.I. Adyan [10], [11], [12] in 1955 obtained a very general result, which parallels the result obtained by A.A. Markov for associative calculi, by giving a negative solution to almost-all algorithmic problems connected with fundamental classifications of group calculi then known. In particular, he obtained a negative solution to Dehn's third problem — the problem of isomorphism to some given finitely-presented group. Similar results were subsequently obtained by M. Rabin [13].

The unsolvability of the above-mentioned algorithmic problems connected with group calculi implied negative solutions of several algorithmic problems in topology. Thus, a group calculus with an unsolvable conjugacy problem can be used to construct a two-dimensional polyhedron for which the problem of path homotopy is unsolvable. Building on the results of Adyan, Markov in 1958 obtained a negative solution of the homeomorphism problem [14].

References

[1]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2]	A.A. Markov, "Indistinguishability by invariants in the theory of associative calculi" Izv. Akad. Nauk SSSR Ser. Mat. , 27 : 4 (1963) pp. 907–936 (In Russian)
[3]	M. Dehn, "Ueber unendliche diskontinuierliche Gruppen" Math. Ann. , 71 (1911) pp. 116–144
[4]	W. Magnus, "Ueber diskontinuierliche Gruppen mit einer definierenden Relation (der Freiheitssatz)" J. Reine Angew. Math. , 163 : 2 (1931) pp. 141–165
[5]	P.S. Novikov, "On algorithmic unsolvability of the word problem" Dokl. Akad. Nauk SSSR , 85 (1952) pp. 709–712 (In Russian)
[6]	P.S. Novikov, "On algorithmic unsolvable problems of word identity in group theory" , Amer. Math. Soc. (1958) (Translated from Russian)
[7a]	W.W. Boone, "Certain simple unsolvable problems of group theory I, II" Indag. Math. , 16 (1954) pp. 231–237; 492–497
[7b]	W.W. Boone, "Certain simple unsolvable problems of group theory III" Indag. Math. , 17 (1955) pp. 571–577
[7c]	W.W. Boone, "Certain simple unsolvable problems of group theory IV, V" Indag. Math. , 19 (1957) pp. 22–27; 227–232
[8]	J.L. Britton, "The word problem for groups" Proc. London Math. Soc. (3) , 8 : 32 (1958) pp. 493–506
[9]	P.S. Novikov, "Unsolvability of the conjugacy problem in group theory" Izv. Akad. Nauk SSSR Ser. Mat. , 18 : 6 (1954) pp. 485–524 (In Russian)
[10]	S.I. Adyan, "Algorithmic unsolvablity of problems of recognizing certain properties of groups" Dokl. Akad. Nauk SSSR , 103 (1955) pp. 533–535 (In Russian)
[11]	S.I. Adyan, "Finitely-presented groups and algorithms" Dokl. Akad. Nauk SSSR , 117 : 1 (1957) pp. 9–12 (In Russian)
[12]	S.I. Adyan, "Unsolvability of certain algorithmic problems in the theory of groups" Trudy Moskov. Mat. Obshch. , 6 (1957) pp. 231–298 (In Russian)
[13]	M.O. Rabin, "Algorithmic unsolvability of group theoretic problems" Ann. of Math. , 67 (1958) pp. 172–194
[14]	A.A. Markov, "The unsolvability of the homeomorphism problem" Dokl. Akad. Nauk SSSR , 121 : 2 (1958) pp. 218–220 (In Russian)
[15]	A.A. Markov, N.M. [N.M. Nagornyi] Nagorny, "The theory of algorithms" , Kluwer (1988) (Translated from Russian)

Comments

For a more up-to-date survey of Dehn's problems, especially the conjugacy problem, see [a1] and the extensive bibliography there.

The volume [a2] contains a number of survey articles on word problems and related algorithmic problems in group theory.

References

[a1]	R.D. Hurwitz, "A survey of the conjugacy problem" Contemp. Math. , 33 (1984) pp. 278–298
[a2]	W.W. Boone (ed.) F.B. Cannonito (ed.) R.C. Lyndon (ed.) , Word problems , North-Holland (1973)