Around 1945, Alfred Tarski proposed several questions concerning the elementary theory of non-abelian free groups. These remained open for 60 years until they were proved by O. Kharlampovich and A. Myasnikov and independently by Z. Sela. The proofs, by both sets of authors, were monumental and involved the development of several new areas of infinite group theory. In this paper we explain precisely the Tarski problems and what has been actually proved. We then discuss the history of the solution as well as the components of the proof. We then provide the basic strategy for the proof. We finish this paper with a brief discussion of elementary free groups.
KeywordsNon-Abelian Free GroupElementary TheoryTarski ProblemsElementary Free GroupsAlgebraic Geometry over Groups
Kharlamapovich, O. and Myasnikov, A. (1998) Irreducible Affine Varieties over a Free Group: I. Irreducibility of Quadratic Equations and Nullstellensatz. Journal of Algebra, 200, 472-516. http://dx.doi.org/10.1006/jabr.1997.7183
Kharlamapovich, O. and Myasnikov, A. (1998) Irreducible Affine Varieties over a Free Group: II. Systems in Triangular Quasi-Quadratic Form and Description of Residually Free Groups. Journal of Algebra, 200, 517-570.
Kharlamapovich, O. and Myasnikov, A. (2005) Implicit Function Theorem over Free Groups. Journal of Algebra, 290, 1-203. http://dx.doi.org/10.1016/j.jalgebra.2005.04.001
Kharlamapovich, O. and Myasnikov, A. (2005) Effective JSJ Decompositions. Contemporary Mathematics, 378, 87-212. http://dx.doi.org/10.1090/conm/378/07012
Kharlamapovich, O. and Myasnikov, A. (2006) Elementary Theory of Free Non-Abelian Groups. Journal of Algebra, 302, 451-552. http://dx.doi.org/10.1016/j.jalgebra.2006.03.033
Sela, Z. (2001) Diophantine Geometry over Groups I: Makanin-Razborov Diagrams. Publications Mathématiques de l’Institut des Hautes études Scientifiques, 93, 31-106. http://dx.doi.org/10.1007/s10240-001-8188-y
Sela, Z. (2003) Diophantine Geometry over Groups II: Completions, Closures and Formal Solutions. Israel Journal of Mathematics, 134, 173-254. http://dx.doi.org/10.1007/BF02787407
Sela, Z. (2005) Diophantine Geometry over Groups III: Rigid and Solid Solutions. Israel Journal of Mathematics, 147, 1-73. http://dx.doi.org/10.1007/BF02785359
Sela, Z. (2004) Diophantine Geometry over Groups IV: An Iterative Procedure for Validation of a Sentence. Israel Journal of Mathematics, 143, 1-130. http://dx.doi.org/10.1007/BF02803494
Sela, Z. (2005) Diophantine Geometry over Groups V: Quantifier Elimination. Israel Journal of Mathematics, 150, 1-197.
Fine, B., Gaglione, A., Myasnikov, A., Rosenberger, G. and Spellman, D. (2014) The Elementary Theory of Groups. Walter de Gruyter, Berlin. http://dx.doi.org/10.1515/9783110342031
Bell, J.L. and Slomson, A.B. (1971) Models and Ultraproducts: An Introduction. 2nd Revised Printing, North-Holland, Amsterdam.
Chang, C.C. and Keisler, H.J. (1977) Model Theory. 2nd Edition, North-Holland, Amsterdam.
Magnus, W., Karrass, A. and Solitar, D. (1966) Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Interscience Publishers, John Wiley and Sons, Inc., New York, London, Sydney.
Lyndon, R.C. and Schupp, P.E. (1977) Combinatorial Group Theory. Springer-Verlag, Berlin. http://dx.doi.org/10.1007/978-3-642-61896-3
Merzlyakov, Y.I. (1966) Positive Formulas on Free Groups. Algebra i Logika, 5, 25-42.
Sacerdote, G.S. (1972) Elementary Properties of Free Groups. Transactions of the American Mathematical Society, 178, 127-138. http://dx.doi.org/10.1090/S0002-9947-1973-0320146-4
Baumslag, B. (1967) Residually Free Groups. Proceedings of the London Mathematical Society, 17, 635-645.
Gaglione, A. and Spellman, D. (1993) Even More Model Theory of Free Groups. In: Corson, J., Dixon, M., Evans, M. and Rohl, F., Eds., Infinite Groups and Group Rings, World Scientific Press, Singapore City, 37-40. http://dx.doi.org/10.1142/9789814503723_0004
Chiswell, I. (1976) Abstract Length Functions in Groups. Mathematical Proceedings of the Cambridge Philosophical Society, 80, 451-463. http://dx.doi.org/10.1017/S0305004100053093
Ciobanu, L., Fine, B. and Rosenberger, G. (2015) Classes of Groups Generalizing a Theorem of Benjamin Baumslag. To Appear-Comm. in Alg.
Lyndon, R.C. (1960) Groups with Parametric Exponents. Transactions of the American Mathematical Society, 96, 518-533. http://dx.doi.org/10.1090/S0002-9947-1960-0151502-6
Makanin, G.S. (1982) Equations in a Free Group (Russian). Izv. Akad. Nauk SSSR, Ser. Mat., 46, 1199-1273. Transl. in Math. USSR Izv., V. 21, 1983, MR 84m:20040.
Makanin, G.S. (1985) Decidability of the Universal and Positive Theories of a Free Group. Mathematics of the USSR-Izvestiya, 25, 75-88. http://dx.doi.org/10.1070/IM1985v025n01ABEH001269
Razborov, A.A. (1984) On Systems of Equations in Free Groups. Izv.Akad. Nauk SSSR, 48, 779-832. Englisg transl: Math, USSR Izv., 25, 115-162.
Baumslag, G., Myasnikov, A. and Remeslennikov, V. (2002) Discriminating Completions of Hyperbolic Groups. Geometriae Dedicata, 92, 115-143. http://dx.doi.org/10.1023/A:1019687202544
Baumslag, G., Myasnikov, A. and Remeslennikov, V. (1999) Algebraic Geometry over Groups I. Algebraic Sets and Ideal Theory. Journal of Algebra, 219, 16-79. http://dx.doi.org/10.1006/jabr.1999.7881
Carstensen, C., Fine, B. and Rosenberger, G. (2012) Abstract Algebra. De Gruyter, Berlin.
Bryant, R. (1977) The Verbal Topology of a Group. Journal of Algebra, 48, 340-346. http://dx.doi.org/10.1016/0021-8693(77)90312-X
Guba, V. (1986) Equivalence of Infinite Systems of Equations in Free Groups and Semigroups to Finite Subsystems. Mat. Zametki, 40, 321-324.
Lyndon, R.C. (1959) The Equation in Free Groups. Michigan Mathematical Journal, 6, 155-164.
Lorenc, A.A. (1963) The Solution of Systems of Equations in One Unknown in Free Groups. Dokl. Akad. Nauk SSSR, 148, 262-266.
Appel, K.I. (1968) One-Variable Equations in Free Groups. Proceedings of the American Mathematical Society, 19, 912-918. http://dx.doi.org/10.1090/S0002-9939-1968-0232826-3
Csorgo, P., Fine, B. and Rosenberger, G. (2002) On Certain Equations in Free Groups. Acta Sci. Math., 68, 95-105.
Comerford, L. and Edmonds, C. (1989) Solutions of Equations in Free Groups. Proceedings of Conference in Group Theory Singapore 1987, Springer-Verlag, Berlin, 347-355.
Grigorchuk, R.I. and Kurchanov, P.F. (1992) On Quadratic Equations in Free Groups. Contemporary Mathematics, 131, 159-171. http://dx.doi.org/10.1090/conm/131.1/1175769
Grigorchuk, R. and Kurchanov, P. (1990) Some Questions of Group Theory Related to Geometry. In Itogi Nauki i Techniki, Sovremennye problemy matematiki. Fundamental’nye napravlenia, VINITI, 58. Encyclopedia of math. sciences, English Translation in 1993.
Rips, E. and Sela, Z. (1997) Cyclic Splittings of Finitely Presented Groups and the Canonical JSJ Decomposition. Annals of Mathematics, 146, 53-109. http://dx.doi.org/10.2307/2951832
Howie, J. (2004) Some Results on One-Relator Surface Groups. Boletín de la Sociedad Matemática Mexicana, 10, 255-262.
Bogopolski, O. (2005) A Surface Groups Analogue of a Theorem of Magnus. Cont. Math, 352, 55-89.
Bogopolski, O. and Sviridov, K. (2008) A Magnus Theorem for Some One-Relator Groups. The Zieschang Gedenkschrift, 14, 63-73.
Fine, B., Gaglione, A., Rosenberger, G. and Spellman, D. (2013) Something for Nothing: Some Consequences of the Solution of the Tarski Problems. To Appear Proc. of Groups St Andrews.
Fine, B., Gaglione, A., Rosenberger, G. and Spellman, D. (2015) On Elementary Free Groups. To Appear Cont. Math.
Gaglione, A., Lipschutz, S. and Spellman, D. (2009) Almost Locally Free Groups and a Theorem of Magnus. Journal of Groups, Complexity, Cryptology, 1, 181-198.
Bumagin, I., Kharlampovich, O. and Myasnikov, A. (2007) The Isomorphism Problem for Finitely Generated Fully Residually Free Groups. Journal of Pure and Applied Algebra, 208, 961-977. http://dx.doi.org/10.1016/j.jpaa.2006.03.025
Fine, B., Kharlampovich, O., Myasnikov, A., Remeslennikov, V. and Rosenberger, G. (2012) Tame Automorphisms of Elementary Free Groups. Communications in Algebra, 1, 1-15.
Fine, B., Gaglione, A., Myasnikov, A., Rosenberger, G. and Spellman, D. (1998) A Classification of Fully Residually Free Groups of Rank Three or Less. Journal of Algebra, 200, 571-605. http://dx.doi.org/10.1006/jabr.1997.7205
Kharlamapovich, O. and Myasnikov, A. (1998) Hyperbolic Groups and Free Constructions. Transactions of the American Mathematical Society, 350, 571-613. http://dx.doi.org/10.1090/S0002-9947-98-01773-5
Sela, Z. (1995) The Isomorphism Problem for Hyperbolic Groups I. Annals of Mathematics, 141, 217-283. http://dx.doi.org/10.2307/2118520
Gildenhuys, D., Kharlampovich, O. and Myasnikov, A. (1995) CSA Groups and Separated Free Constructions. Bulletin of the Australian Mathematical Society, 52, 63-84. http://dx.doi.org/10.1017/S0004972700014453
Baumslag, G. (1962) On Generalised Free Products. Mathematische Zeitschrift, 78, 423-438. http://dx.doi.org/10.1007/BF01195185
Fine, B. and Rosenberger, G. (2011) Faithful Representations of Hyperbolic Limit Groups. Groups Complexity Cryptology, 3, 349-355.
Fine, B. and Rosenberger, G. (2013) Faithful Representations of Limit Groups II. Groups Complexity Cryptology, 5, 91-96. http://dx.doi.org/10.1515/gcc-2013-0005