Home Research Publications Teaching Links
I am going to divide the discussion of my work into three parts, beginning with the most recent work.
During the last three years my research interests included free groups, groups acting on $\Lambda$-trees, hyperbolic and exponential groups, periodic groups, groups with one defining relation and geometric methods in group theory.
Together with A. Miasnikov I studied first-order properties of free groups. This study culminated in a proof that the elementary theories of all nonabelian free groups coincide and are decidable, answering two old questions raised by Tarski around 1945.
There are three parts to this work each requiring very different techniques from the others: algebraic geometry over free groups (we described irreducible affine varieties over a free group), the theory of free exponential groups, and the generalization of Makanin-Razborov's machinery which deals with equations over free groups and over affine groups of irreducible varieties.
Currently one of the mainstreams of combinatorial group theory is the study of systems of equations over a group. The problem of deciding if a finite system of equations in a group has a solution generalizes the word problem and the conjugacy problem. Makanin and Razborov proved one of the most significant results in this area, namely the algorithmic solvability of systems of equations in free groups. I obtained in collaboration with Miasnikov an algebraic description of existentially free groups ($\exists$-free groups are groups in which the class of $\exists$-formulas, true in one of these groups, is the same as the class of $\exists$-formulas, true in a nonabelian free group). To be $\exists$-free group is the same as to be a fully residually free group. We proved that a finitely generated group is $\exists$-free if and only if it is embeddable in the ${\bf Z}[x]$-completion $F^{{\bf Z}[x]}$ of the free group, where ${\bf Z}[x]$ is the ring of polynomials of one variable with integer coefficients. (Lyndon's attempts to solve Tarski's problem led him to introduce $F^{{\bf Z}[x]}.$) Our result implies that every finitely generated fully residually free group is finitely presented.
An algorithm for solving equations over hyperbolic groups was developed by E. Rips and Z. Sela. G. Baumslag proved that the word problem is decidable in $\bf Q$-free groups. Together with Miasnikov I proved that there exists an algorithm that decides if a given finite system of equations over a free $\bf Q$-group has a solution, and if it does, the algorithm finds a solution. We established the same result for a tensor $\bf Q$-completion of a torsion-free hyperbolic group (joint work with my student E. Lioutikova). My own work in this direction continues and I have some other interesting results.
Another direction that my collaboration with Miasnikov took involves finding necessary and sufficient conditions for HNN-extensions and amalgamated free products of hyperbolic groups over abelian subgroups to preserve hyperbolicity. We also proved some other results about HNN-extensions of hyperbolic groups in much more general situations.
I will now turn to my early work and show how it leads to the middle period of my development.
In the 1930's Turing, Church and others developed a precise concept of algorithm and the algorithmic decidability of mathematical problems. This also made it possible to prove the non-existence of algorithms for solving specific mathematical problems. One of the earliest results in this area was Markov and Post's proof of the undecidability of the word problem for finitely presented semigroups.
The analogous result for groups turned out to be much more complicated. This problem had already been posed by Dehn in 1912, but was only solved in 1952 by Novikov and then by Boone. I.e., he proved that there exists a finitely presented group for which there is no algorithm to determine whether or not a given element of the group is the identity.
Novikov and Adyan then proposed as the next step that a finitely presented group might be found, satisfying a nontrivial identity, with undecidable word problem. An obvious identity is for all commutators to be trivial; i.e., for the group to be abelian. However, it is quite obvious that finitely generated abelian groups have a decidable word problem. Since finitely generated metabelian groups are residually finite (a result of Phillip Hall), the same is true for them.
Novikov and Adyan's problem formally appeared in written form in 1973. In 1980, when I was an undergraduate student, I solved it by constructing a 3-step solvable group, finitely presented in the class of all groups, and with undecidable word problem.
A year earlier, I succeeded in giving a negative answer to a question, posed in 1965 by Kargapolov (also known as Mal'tsev's question), about the algorithmic decidability of the universal theory of the class of all finite nilpotent groups.
For my undergraduate work I was awarded a gold medal from the Soviet Academy of Sciences. One such medal is awarded every two years to the best mathematics student in the Soviet Union.
In the middle period of my work I investigated the connections between algebraic properties and algorithmic properties of varieties of groups and Lie algebras. I looked, in particular, for some boundary, in the class of all varieties of solvable groups (Lie algebras over a field of characteristic 0), between algorithmic decidability and undecidability. In the process, I obtained (modulo the difficult problem about effective boundary for integer solutions of a certain exponential diophantine equation) an almost complete description of the class of varieties of Lie algebras in which every (absolutely) finitely presented algebra has decidable word problem. In the case of relatively finitely presented algebras (or groups), I proved the surprising result that no boundary exists between varieties with decidable and varieties with undecidable word problem. This I did, by demonstrating an infinite chain in the lattice of varieties, in which varieties with decidable and undecidable word problem alternate. I also proved the undecidability of the word problem in the Burnside variety of groups for a large exponent.
In 1995 together with M. Sapir I published a survey, ``Algorithmic Problems in Varieties'' in the International Journal of Algebra and Computation, which summarized my and his research on algorithmic problems in algebra.
Apart from the algorithmic results alluded to above, I also proved various other results in combinatorial group theory and the theory of Lie algebras, for example, the Generalised Freiheitssatz for solvable varieties of Lie algebras, and some results concerning residual finiteness in varieties of groups and Lie algebras.