View source for Group calculus

An [[Associative calculus|associative calculus]] in which the natural group requirement of the existence of an inverse operation is effectively fulfilled. In fact, an associative calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452401.png" /> is said to be a group calculus [[#References|[1]]], [[#References|[15]]] if it is possible to construct for it an inverting algorithm, i.e. an [[Algorithm|algorithm]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452402.png" /> such that for any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452403.png" /> over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452404.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452405.png" /> the following conditions are satisfied: 1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452406.png" /> is defined and is also a word over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452407.png" />; 2) the words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452408.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g0452409.png" /> are equivalent to the empty word in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524010.png" /> (here, the term  "algorithm"  must be understood in some exact meaning of the word, e.g. as a [[Normal algorithm|normal algorithm]]).

The most useful group calculi are those of a special type (the so-called inversive calculi, cf. [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524011.png" /> there exists an explicit inverse letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524012.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524013.png" />.

The importance of group calculi consists in the fact that they are representations of finitely-presented groups (cf. also [[Finitely-presented group|Finitely-presented group]]). A group calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524014.png" />, like any other associative calculus, generates in a standard manner (cf. [[Associative calculus|Associative calculus]]) a finitely-presented associative system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524015.png" />, which is a group since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524016.png" /> has an inverting algorithm. The [[Algorithmic problem|algorithmic problem]] of recognizing word equivalence in a group calculus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524017.png" /> is the identity problem (word problem) for the finitely-presented group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045240/g04524018.png" />, 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 [[#References|[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 [[#References|[4]]]. P.S. Novikov in 1952 ([[#References|[5]]], [[#References|[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|Turing machine]] or a [[Normal algorithm|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|Church thesis]]). Other examples of such group calculi were introduced later (see, for example, , [[#References|[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 [[#References|[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 [[#References|[10]]], [[#References|[11]]], [[#References|[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 [[#References|[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 [[#References|[14]]].

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



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

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

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.D. Hurwitz,   "A survey of the conjugacy problem"  ''Contemp. Math.'' , '''33'''  (1984)  pp. 278–298</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  W.W. Boone (ed.)  F.B. Cannonito (ed.)  R.C. Lyndon (ed.) , ''Word problems'' , North-Holland  (1973)</TD></TR></table>