Adian–Rabin theorem

In the mathematical subject of group theory, the Adian–Rabin theorem is a result which states that most "reasonable" properties of finitely presentable groups are algorithmically undecidable. The theorem is due to Sergei Adian (1955)[1] and, independently, Michael O. Rabin (1958).[2]

Markov propertyEdit

A Markov property P of finitely presentable groups is one for which:

  1. P is an abstract property, that is, P is preserved under group isomorphism.
  2. There exists a finitely presentable group   with property P.
  3. There exists a finitely presentable group   which cannot be embedded as a subgroup in any finitely presentable group with property P.

For example, being a finite group is a Markov property: We can take   to be the trivial group and we can take   to be the infinite cyclic group  .

Precise statement of the Adian–Rabin theoremEdit

In modern sources, the Adian–Rabin theorem is usually stated as follows:[3][4][5]

Let P be a Markov property of finitely presentable groups. Then there does not exist an algorithm that, given a finite presentation  , decides whether or not the group   defined by this presentation has property P.

The word 'algorithm' here is used in the sense of recursion theory. More formally, the conclusion of Adian–Rabin theorem means that set of all finite presentations

 

(where   is a fixed countably infinite alphabet, and   is a finite set of relations in these generators and their inverses) defining groups with property P, is not a recursive set.

Historical notesEdit

The statement of the Adian–Rabin theorem generalizes a similar earlier result for semigroups by Andrey Markov, Jr.,[6] proved by different methods. It was also in the semigroup context that Markov introduced the above notion that that group theorists came to call the Markov property of finitely presented groups. This Markov, a prominent Soviet logician, is not to be confused with his father, the famous Russian probabilist Andrey Markov after whom Markov chains and Markov processes are named.

According to Don Collins,[7] the notion Markov Property, as defined above, was introduced by William Boone in his Mathematical Reviews review of Rabin's 1958 paper containing Rabin's proof of the Adian–Rabin theorem.

Idea of the proofEdit

In modern sources,[3][4] the proof of the Adian–Rabin theorem proceeds by a reduction to the Novikov–Boone theorem via a clever use of amalgamated products and HNN extensions.

Let   be a Markov property and let   be as in the definition of the Markov property above. Let   be a finitely presented group with undecidable word problem, whose existence is provided by the Novikov–Boone theorem.

The proof then produces a recursive procedure that, given a word   in the generators   of  , outputs a finitely presented group   such that if   then   is isomorphic to  , and if   then   contains   as a subgroup. Thus   has property   if and only if  . Since it is undecidable whether  , it follows that it is undecidable whether a finitely presented group has property  .

ApplicationsEdit

The following properties of finitely presented groups are Markov and therefore are algorithmically undecidable by the Adian–Rabin theorem:

  1. Being the trivial group.
  2. Being a finite group.
  3. Being an abelian group.
  4. Being a finitely generated free group.
  5. Being a finitely generated nilpotent group.
  6. Being a finitely presentable solvable group.
  7. Being a finitely presentable amenable group.
  8. Being a word-hyperbolic group.
  9. Being a torsion-free finitely presentable group.
  10. Being a polycyclic group.
  11. Being a finitely presentable group with a solvable word problem.
  12. Being a finitely presentable residually finite group.
  13. Being a finitely presentable group of finite cohomological dimension.
  14. Being an automatic group.
  15. Being a finitely presentable simple group. (One can take   to be the trivial group and   to be a finitely presented group with unsolvable word problem whose existence is provided by the Novikov-Boone theorem. Then Kuznetsov's theorem implies that   does not embed into any finitely presentable simple group. Hence being a finitely presentable simple group is a Markov property.)
  16. Being a finitely presentable group of finite asymptotic dimension.
  17. Being a finitely presentable group admitting a uniform embedding into a Hilbert space.

Note that the Adian–Rabin theorem also implies that the complement of a Markov property in the class of finitely presentable groups is algorithmically undecidable. For example, the properties of being nontrivial, infinite, nonabelian, etc., for finitely presentable groups are undecidable. However, there do exist examples of interesting undecidable properties such that neither these properties nor their complements are Markov. Thus Collins (1969) [7] proved that the property of being Hopfian is undecidable for finitely presentable groups, while neither being Hopfian nor being non-Hopfian are Markov.

See alsoEdit

ReferencesEdit

  1. ^ S. I. Adian, Algorithmic unsolvability of problems of recognition of certain properties of groups. (in Russian) Doklady Akademii Nauk SSSR vol. 103, 1955, pp. 533–535
  2. ^ Michael O. Rabin, Recursive unsolvability of group theoretic problems, Annals of Mathematics (2), vol. 67, 1958, pp. 172–194
  3. ^ a b Roger Lyndon and Paul Schupp, Combinatorial group theory. Reprint of the 1977 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2001. ISBN 3-540-41158-5; Ch. IV, Theorem 4.1, p. 192
  4. ^ a b G. Baumslag. Topics in combinatorial group theory. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1993. ISBN 3-7643-2921-1; Theorem 5, p. 112
  5. ^ Joseph Rotman, An Introduction to the Theory of Groups, Graduate Texts in Mathematics, Springer, 4th edition; ISBN 0387942858; Theorem 12.32, p. 469
  6. ^ A. Markov, "Невозможность алгорифмов распознавания некоторых свойств ассоциативных систем" [The impossibility of algorithms for the recognition of certain properties of associative systems]. (in Russian) Doklady Akademii Nauk SSSR vol. 77, (1951), pp. 953–956.
  7. ^ a b Donald J. Collins, On recognizing Hopf groups, Archiv der Mathematik, vol. 20, 1969, pp. 235–240.

Further readingEdit