Adian–Rabin theorem

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 $A\_+$ with property P.
3. There exists a finitely presentable group $A\_-$ that 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 $A\_+$ to be the trivial group and we can take $A\_-$ to be the infinite cyclic group $\backslash mathbb\{Z\}$.

In modern sources, the Adyan–Rabin theorem is usually stated as follows:Roger Lyndon and Paul Schupp, [https://books.google.com/books?id=aiPVBygHi_oC&q=lyndon+and+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. 192G. Baumslag. [https://books.google.com/books?id=5tYi8ETy1ZAC&dq=G.+Baumslag.+%22Topics+in+combinatorial+group+theory%22&pg=PA8 Topics in combinatorial group theory.] Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1993. {{isbn|3-7643-2921-1}}; Theorem 5, p. 112Joseph Rotman, [https://books.google.com/books?id=4x8BCAAAQBAJ&dq=%22adian+rabin+theorem%22&pg=PA502 An Introduction to the Theory of Groups], Graduate Texts in Mathematics, Springer, 4th edition; {{isbn|0387942858}}; Theorem 12.32, p. 469

Let P be a Markov property of finitely presentable groups. Then there does not exist an algorithm that, given a finite presentation $G=\backslash langle\; X\; \backslash mid\; R\backslash rangle$, decides whether or not the group $G$ defined by this presentation has property P.

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

:$\backslash langle\; x\_1,\; x\_2,\; x\_3,\; \backslash dots\; \backslash mid\; R\backslash rangle$

(where $x\_1,\; x\_2,\; x\_3,\; \backslash dots$ is a fixed countably infinite alphabet, and $R$ is a finite set of relations in these generators and their inverses)

defining groups with property P, is not a recursive set.

The statement of the Adyan–Rabin theorem generalizes a similar earlier result for semigroups by Andrey Markov, Jr.,A. Markov, "Невозможность алгорифмов распознавания некоторых свойств ассоциативных систем" [The impossibility of algorithms for the recognition of certain properties of associative systems]. {{in lang|ru}} Doklady Akademii Nauk SSSR vol. 77, (1951), pp. 953–956.C.-F. Nyberg-Brodda, [https://arxiv.org/abs/2208.08560 The Adian-Rabin theorem: an English translation]. 2022. proved by analogous 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, 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 Adyan–Rabin theorem.

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

Let $P$ be a Markov property and let $A\_+,\; A\_-$ be as in the definition of the Markov property above.

Let $G=\backslash langle\; X\; \backslash mid\; R\backslash rangle$ 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 $w$ in the generators $X\backslash cup\; X^\{-1\}$ of $G$, outputs a finitely presented group $G\_w$ such that if $w=\_G\; 1$ then $G\_w$ is isomorphic to $A\_+$, and if $w\backslash ne\_G\; 1$ then $G\_w$ contains $A\_-$ as a subgroup. Thus $G\_w$ has property $P$ if and only if $w=\_G\; 1$. Since it is undecidable whether $w=\_G\; 1$, it follows that it is undecidable whether a finitely presented group has property $P$.

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

1. Being the trivial group.
2. Being a finite group.
3. Being an abelian group.
4. Being a free group.
5. Being a nilpotent group.
6. Being a solvable group.
7. Being a amenable group.
8. Being a word-hyperbolic group.
9. Being a torsion-free group.
10. Being a polycyclic group.
11. Being a group with a solvable word problem.
12. Being a residually finite group.
13. Being a group of finite cohomological dimension.
14. Being an automatic group.
15. Being a simple group. (One can take $A\_+$ to be the trivial group and $A\_-$ 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 $A\_-$ does not embed into any finitely presentable simple group. Hence being a finitely presentable simple group is a Markov property.)
16. Being a group of finite asymptotic dimension.
17. Being a group admitting a uniform embedding into a Hilbert space.

Note that the Adyan–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) Donald J. Collins, [https://link.springer.com/article/10.1007%2FBF01899291?LI=true On recognizing Hopf groups], Archiv der Mathematik, vol. 20, 1969, pp. 235–240. proved that the property of being Hopfian is undecidable for finitely presentable groups, while neither being Hopfian nor being non-Hopfian are Markov.

• Higman's embedding theorem
• Bass–Serre theory

{{Reflist}}

• C. F. Miller, III, [https://doi.org/10.1007/978-1-4613-9730-4_1 Decision problems for groups — survey and reflections]. Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), pp. 1–59, Math. Sci. Res. Inst. Publ., 23, Springer, New York, 1992, {{isbn|0-387-97685-X}}

{{DEFAULTSORT:Adian-Rabin theorem}}

Category:Theorems in group theory

Category:Geometric group theory

Category:Undecidable problems