**These pages are not updated anymore.
They reflect the state of
.
For the current production of this journal, please refer to
http://www.math.psu.edu/era/.
**

%_ ************************************************************************** %_ * The TeX source for AMS journal articles is the publishers TeX code * %_ * which may contain special commands defined for the AMS production * %_ * environment. Therefore, it may not be possible to process these files * %_ * through TeX without errors. To display a typeset version of a journal * %_ * article easily, we suggest that you retrieve the article in DVI, * %_ * PostScript, or PDF format. * %_ ************************************************************************** % Author Package file for use with AMS-LaTeX 1.2 \controldates{2-JUL-2001,2-JUL-2001,2-JUL-2001,2-JUL-2001} \documentclass{era-l} \issueinfo{7}{09}{}{2001} \dateposted{July 3, 2001} \pagespan{63}{71} \PII{S 1079-6762(01)00095-6} \usepackage{eucal,latexsym} \copyrightinfo{2001}{American Mathematical Society} \newcommand{\pr}{\pageref} \newcommand{\iv}{^{-1}} \newcommand{\vk}{van Kampen } \newcommand{\ct}{contiguity } \newcommand{\topp}{{\bf top}} \newcommand{\hra}{H_{ra}} \newcommand{\nee}{\not\equiv} \newcommand{\maa}{H_a} \newcommand{\bott}{{\bf bot}} \newcommand{\hnka}{H^*_{ka}} \newcommand{\hkra}{H_{kra}} \newcommand{\base}{\hbox{{\bf base}}} \newcommand{\suff}{\hbox{{\bf suff}}} \newcommand{\oo}{{\bf 0}} \newcommand{\rf}{{\hbox{ref}}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\kr}{$\mathcal K$-projection } \newcommand{\bc}{{\bf c}} \newcommand{\bbc}[1]{\overline{{\bf c}_{#1}}} \newcommand{\krs}{$\mathcal K$-projections } \newcommand{\bk}{{\bf \rho}} \newcommand{\bt}[1]{\overline{\tau(#1)}} \newcommand{\tk}{{\bf \lambda}} \newcommand{\rt}{\hbox{root}} \newcommand{\kk}{\overline{\bf K}} \newcommand{\pq}{$p_1q_1p_2q_2$} \newcommand{\lk}{\overleftarrow{{\bf \kappa}}} \newcommand{\rk}{\overrightarrow{{\bf \kappa}}} \newcommand{\tool}{\stackrel{\ell}{\too} } \newcommand{\aaa}{{\bf A}} \newcommand{\bkk}{{\bf K}} \newcommand{\rr}{{\bf R}} \newcommand{\ttt}{{\mathcal T}} \newcommand{\rp}{${\mathcal R}$-projection } \newcommand{\rps}{${\mathcal R}$-projections } \newcommand{\ee}{{\mathcal E}} \newcommand{\pp}{{\mathcal P}} \newcommand{\qq}{{\mathcal Q}} \newcommand{\Lab}{\phi} \newcommand{\Bigcup}{\cup} \newcommand{\cd}{command } \newcommand{\sr}{ strange} \newcommand{\sss}{{\mathbb{S}}} \newcommand{\too}{\to} \newcommand{\yyy}{{\mathcal Y}} \newcommand{\xxx}{{\bf X}} \newcommand{\bb}{{\mathcal B}} \newcommand{\zzz}{{\mathcal Z}} \newcommand{\ww}{{\mathcal W}} \newcommand{\tz}{Z(\sss,ra)} \newcommand{\tza}{Z(\sss,\Lambda,ra)} \newcounter{ppp} \setcounter{ppp}{1} \newcounter{band} \newcounter{annulus} \newcounter{nonannulus} \newcounter{ovals} \newcounter{innermost} \newcounter{touch} \newcounter{bigons} \newcounter{spokes} \newcounter{triple} \newcounter{derived} \newcounter{pone} \newcounter{spone} \newcounter{sptwo} \newcounter{figone} \newcounter{ab} \newcounter{abone} \newcounter{theta} \newcounter{three} \newcounter{pdfour} \newcounter{pdfive} \newcounter{pfive} \newcounter{psix} \newcounter{pdsix} \newcounter{pdseven} \newcounter{pdeight} \newcounter{pdnine} \newcounter{pdten} \newcounter{pdeleven} \newcounter{pdtwelve} \newcounter{pdthirteen} \newcounter{pdfourteen} \newcounter{aan} \newcounter{pdfifteen} \newcounter{pdsixteen} \newcounter{pdseventeen} \newcounter{pdeighteen} \newcounter{pdnineteen} \newcounter{pdtwenty} \newcounter{pdtwentyone} \newcounter{pdtwentytwo} \newcounter{pdtwentythree} \newcounter{pdtwentyfour} \newcounter{pdtwentyseven} \newcounter{pdtwentyfive} \newcounter{pdtwentysix} \newcounter{pdtwentyeight} \newcounter{pdtwentynine} \newcounter{pdthirty} \newcounter{pdthirtyone} \newcounter{pdthirtytwo} \newcounter{pdfourty} \newcounter{p2} \newcounter{p3} \newcounter{p4} \newcounter{p5} \newcounter{p6} \newcounter{p7} \newcounter{peight} \newcounter{pnine} \newcounter{pten} \newcounter{peleven} \newcounter{ptwelve} \newcounter{p13} \newcounter{p14} \newcounter{p15} \newcounter{p16} \newcounter{p17} \newcounter{p18} \newcounter{p19} \newcounter{p20} \newcounter{p21} \newcounter{p22} \newcounter{p23} \newcounter{move} \newcounter{adjust} \newcounter{p24} \newcounter{p25} \newcounter{p26} \newcounter{p27} \newcounter{p28} \newcounter{p29} \newcounter{p30} \newcounter{p31} \newcounter{p32} \newcounter{p33} \newcounter{p34} \newcounter{p35} \newcounter{p36} \theoremstyle{plain} \newtheorem{theo}{Theorem}[section] \newtheorem{lm}[theo]{Lemma} \newtheorem{cy}[theo]{Corollary} \newtheorem{prop}[theo]{Proposition} \theoremstyle{definition} \newtheorem{df}[theo]{Definition} \newtheorem{prob}[theo]{Problem} \theoremstyle{remark} \newtheorem{remark}[theo]{Remark} \begin{document} \title{Non-amenable finitely presented torsion-by-cyclic groups} \author{A. Yu. Ol'shanskii} \address{Department of Mathematics, Vanderbilt University, Nashville, TN 37240, and Department of Mechanics and Mathematics, Moscow State University, Moscow, Russia} \email{olsh@math.vanderbilt.edu} \email{olshan@shabol.math.msu.su} \thanks{Both authors were supported in part by the NSF grant DMS 0072307. In addition, the research of the first author was supported in part by the Russian fund for fundamental research 99-01-00894, and the research of the second author was supported in part by the NSF grant DMS 9978802.} \author{M. V. Sapir} \address{Department of Mathematics, Vanderbilt University, Nashville, TN 37240} \email{msapir@math.vanderbilt.edu} \urladdr{http://www.math.vanderbilt.edu/$\sim$msapir} \subjclass[2000]{Primary 20F05, 43A07} \date{January 9, 2001} \keywords{Amenable group, Burnside groups, free subgroups} \commby{Efim Zelmanov} \begin{abstract} We construct a finitely presented non-amenable group without free non-cyclic subgroups thus providing a finitely presented counterexample to von Neumann's problem. Our group is an extension of a group of finite exponent $n\gg 1$ by a cyclic group, so it satisfies the identity $[x,y]^n=1$. \end{abstract} \maketitle \section{Short history of the problem} Hausdorff \cite{Haus} proved in 1914 that one can subdivide the 2-sphere minus a countable set of points into three parts $A$, $B$, $C$ such that each of these three parts can be obtained from each of the other two parts by a rotation, and the union of any two of these parts can be obtained by rotating the third part. This implied that one cannot define a finitely additive measure on the 2-sphere which is invariant under the group $SO(3)$. In 1924 Banach and Tarski \cite{BT} generalized Hausdorff's result by proving, in particular, that in $\mathbb{R}^3$, every two bounded sets $A, B$ with non-empty interiors can be decomposed $A=\bigcup_{i=1}^n A_i$, $B=\bigcup_{i=1}^n B_i$ so that $A_i$ can be rotated to $B_i$, $i=1,\dots,n$ (the so called Banach-Tarski paradox). Von Neumann \cite{vN} was first who noticed that the cause of the Banach-Tarski paradox is not the geometry of $\mathbb{R}^3$ but an algebraic property of the group $SO(3)$. He introduced the concept of an amenable group (he called such groups ``measurable") as a group $G$ which has a left invariant finitely additive measure $\mu$, $\mu(G)=1$, noticed that if a group is amenable, then any set it acts upon freely also has an invariant measure, and proved that a group is not amenable provided it contains a free non-abelian subgroup. He also showed that groups like $PSL(2, \mathbb{Z})$, $SL(2,\mathbb{Z})$ contain free non-abelian subgroups. So analogs of Banach-Tarski paradox can be found in $\mathbb{R}^2$ and even $\mathbb{R}$. Von Neumann showed that the class of amenable groups contains abelian groups, finite groups and is closed under taking subgroups, extensions, and infinite unions of increasing sequences of groups. Day \cite{day} and Specht \cite{Specht} showed that this class is closed under homomorphic images. The class of groups without free non-abelian subgroups is also closed under these operations and contains abelian and finite groups. The problem of existence of non-amenable groups without non-abelian free subgroups probably goes back to von Neumann and became known as the ``von Neumann problem" in the 1950's. As far as we know, the first paper where this problem was formulated was the paper by Day \cite{day}. It is also mentioned in the monograph by Greenleaf \cite{Greenleaf} based on his lectures given at Berkeley in 1967. Tits \cite{Tits} proved that every non-amenable matrix group over a field of characteristic $0$ contains a non-abelian free subgroup. In particular every semisimple Lie group over a field of characteristic $0$ contains such a subgroup. First counterexamples to the von Neumann problem were constructed by Ol'shan\-skii \cite{OlAmen}. He proved that the groups with all proper subgroups cyclic, constructed by him, both torsion-free \cite{OlTar} and torsion \cite{OlTar1} (the so called ``Tarski monsters"), are not amenable. Later Adian \cite{Adian} showed that the non-cyclic free Burnside group of odd exponent $n>665$ with at least two generators (that is the group given by the presentation $\langle a_1,\dots,a_m\ |\ u^n=1\rangle$ where $u$ runs over all words in the alphabet $\{a_1,\dots,a_m\}$) is not amenable. %It is interesting that the possibility of using torsion groups %and, in particular, Burnside groups as potential counterexamples %to von Neumann's problem was mentioned by Day \cite{day}, %conjectured by Kesten \cite{Kesten1}, and by B.H. Neumann's in his %review of Specht's paper \cite{Specht} in Zentralblatt. Notice that examples in \cite{OlAmen} and \cite{Adian} are based on Grigorchuk's criterion of amenability \cite{Grigorchuk}, which is a refined version of Kesten's criterion from \cite{Kesten2}. Both Ol'shanskii's and Adian's examples are not finitely presented: in the modern terminology these groups are inductive limits of word hyperbolic groups, but they are not hyperbolic themselves. Since many mathematicians (especially topologists) are mostly interested in groups acting ``nicely" on manifolds, it is natural to ask if there exists a finitely presented non-amenable group without non-abelian free subgroups. This question was explicitly formulated, for example, by Grigorchuk in \cite{Kour} and by Cohen in \cite{Cohen}. This question is one of a series of similar questions about finding finitely presented ``monsters", i.e., groups with unusual properties. Probably the most famous problem in that series is the problem of finding a finitely presented infinite torsion group. Other similar problems ask for a finitely presented divisible group (a group where every element has roots of every degree), finitely presented Tarski monster, etc. In each case a finitely generated example can be constructed as a limit of hyperbolic groups (see \cite{book}), and there is no hope to construct finitely presented examples as such limits. One difficulty in constructing a finitely presented non-amenable group without free non-abelian subgroups is that there are ``very few" known finitely presented groups without free non-abelian subgroups. Most non-trivial examples are solvable or ``almost" solvable (see \cite{KhSap}), and so they are amenable. The only known examples of finitely presented groups without free non-abelian subgroups for which the problem of amenability is non-trivial, are R. Thompson's group $F$ and its close ``relatives". The fact that $F$ does not contain free non-abelian subgroups was proved by Brin and Squier in \cite{BS}. A conjecture that $F$ is not amenable was formulated first by Geoghegan \cite{Geogh}. A considerable amount of work has been done to prove this conjecture (see \cite{CFP}) but it is still open. One approach to constructing a finitely presented counterexample to the von Neumann problem would be in using the Higman embedding theorem which states that every recursively presented group can be embedded into a finitely presented group. Thus, one can take a known finitely generated non-amenable group without non-abelian free subgroups and embed it into a finitely presented group. Of course, the resulting group will be non-amenable since the class of amenable groups is closed under taking subgroups. Unfortunately all known constructions of Higman embeddings (see, for example, \cite{BORS}, \cite{talk}) use amalgamated products and non-ascending HNN extensions, which immediately leads to non-abelian free subgroups. Nevertheless Higman-like embeddings play an important role in our construction. Our main result is the following. \begin{theo} \label{main} For every sufficiently large odd $n$, there exists a finitely presented group \label{g1} ${\mathcal G}$ which satisfies the following conditions. \begin{enumerate} \item\label{2} ${\mathcal G}$ is an ascending HNN extension of a finitely generated infinite group of exponent $n$. \item\label{3} ${\mathcal G}$ is an extension of a non-locally finite group of exponent $n$ by an infinite cyclic group. \item\label{4} ${\mathcal G}$ contains a subgroup isomorphic to a free Burnside group of exponent $n$ with two generators. \item\label{5} ${\mathcal G}$ is a non-amenable finitely presented group without free subgroups. \end{enumerate} \end{theo} Notice that parts \ref{2} and \ref{4} of Theorem \ref{main} immediately imply part \ref{3}. By a theorem of Adian \cite{Adian}, part \ref{4} implies that ${\mathcal G}$ is not amenable. Thus parts \ref{2} and \ref{4} imply part \ref{5}. Note that the first example of a finitely presented group which is a cyclic extension of an infinite torsion group was constructed by Grigorchuk \cite{Grig}. But the torsion subgroup in Grigorchuk's group does not have a bounded exponent and his group is amenable (it was the first example of a finitely presented amenable but not elementary amenable group). \section{The scheme of the proof} \label{intro} Let us present the main ideas of our construction. We first embed the free Burnside group \label{bmn}$B(m,n)=\langle {\mathcal B}\rangle$ of odd exponent $n>>1$ with $m>1$ generators $\{b_1,\dots,b_m\}={\mathcal B}$ into a finitely presented group ${\mathcal G}'=\langle {\mathcal C}\mid {\mathcal R}\rangle$ where ${\mathcal B}\subset {\mathcal C}$. This is done in a similar way as in our papers \cite{OS}, \cite{talk} but we need a more complicated $S$-machine than in \cite{OS} ($S$-machines were introduced by Sapir in \cite{SBR}). Then we take a copy \label{a11}${\mathcal A}=\{a_1,\dots,a_m\}$ of the set ${\mathcal B}$, and a new generator ${\bf t}$, and consider the group given by the following three sets of relations: \begin{enumerate} \item[(1)] \label{rrel} the set ${\mathcal R}$ or relations over a set ${\mathcal C}$, corresponding to our $S$-machine $\sss$ (it is denoted in the paper by $Z(\sss,\Lambda)$), i.e., the relations of the finitely presented group ${\mathcal G}'$ containing $B(m,n)$; \item[(2)] \label{urel}($u$-relations) $y=u_y$, where $u_y, y\in {\mathcal C},$ is a certain word in ${\mathcal A}$ (we shall discuss the choice of these words later; for now one can think of them as satisfying a very strong small cancellation condition); these relations make ${\mathcal G}'$ (and $B(m,n)$) embedded into a finitely presented group generated by ${\mathcal A}$; \item[(3)] \label{rhorel} (${\bf t}$-relations) ${\bf t}\iv a_i{\bf t} =b_i, i=1,\dots,m$; these relations make $\la {\mathcal A}\ra$ a conjugate of its subgroup of exponent $n$ (of course, the group $\la {\mathcal A}\ra$ gets factorized). \end{enumerate} The resulting group ${\mathcal G}$ is obviously generated by the set ${\mathcal A}\cup \{{\bf t}\}$ and is an ascending HNN extension of its subgroup $\langle {\mathcal A}\rangle$ with the stable letter ${\bf t}$. Every element in $\la {\mathcal A}\ra$ is a conjugate of an element of $\langle {\mathcal B}\rangle$, so $\la {\mathcal A}\ra$ is an $m$-generated group of exponent $n$. This immediately implies that ${\mathcal G}$ is an extension of a group of exponent $n$ (the union of the increasing sequence of subgroups ${\bf t}^s\la {\mathcal A}\ra {\bf t}^{-s}, s=1,2,\dots)$ by a cyclic group. Hence it remains to prove that $\la {\mathcal A}\ra$ contains a copy of the free Burnside group $B(2,n)$. In order to prove that, we construct a list of defining relations of the subgroup $\la {\mathcal A}\ra$. As we have pointed out, the subgroup $\la {\mathcal A}\cup {\mathcal C}\ra=\la {\mathcal A}\ra$ of ${\mathcal G}$ clearly satisfies all \label{burnsrel} {\em Burnside relations} of the form $v^n=1$. Thus we can add all Burnside relations, \begin{enumerate} \item[(4)] \label{berrel} $v^n=1$ where $v$ is a word in ${\mathcal A}\cup {\mathcal C}$, \end{enumerate} to the presentation of group ${\mathcal G}$ without changing the group. If Burnside relations were the only relations in ${\mathcal G}$ among letters from ${\mathcal B}$, the subgroup of ${\mathcal G}$ generated by ${\mathcal B}$ would be isomorphic to the free Burnside group $B(m,n)$, and that would be the end of the story. Unfortunately there are many more relations in the subgroup $\la {\mathcal B}\ra$ of ${\mathcal G}$. Indeed, take any relation $r(y_1,\dots,y_s)$, $y_i\in {\mathcal C}$, of ${\mathcal G}$. Using $u$-relations (2), we can rewrite it as $r(u_1,\dots,u_s)=1$ where $u_i\equiv u_{y_i}$. Then using ${\bf t}$-relations, we can substitute each letter $a_j$ in each $u_i$ by the corresponding letter $b_j\in {\mathcal B}$. This gives us a relation $r'=1$ which will be called a relation {\em derived} from the relation $r=1$, and the operator producing derived relations will be called the \label{rhoop}{\em ${\bf t}$-operator}. We can apply the ${\bf t}$-operator again and again producing the second, third, \dots, derivatives $r''=1,r'''=1,\dots$ or $r=1$. We can add all \label{derrrel}{\em derived relations}, \begin{enumerate} \item [(5)\label{derrel}] $r'=1, r''=1,\dots$ for all relations $r\in {\mathcal R}$, \end{enumerate} to the presentation of ${\mathcal G}$ without changing ${\mathcal G}$. Now consider the group $H$ generated by ${\mathcal C}$ subject to the relations (1) from ${\mathcal R}$, the Burnside relations (4) and the derived relations (5). (In the paper, this group is denoted by $H_{kra}(\infty)$.) The structure of the relations of $H$ immediately implies that $H$ contains subgroups isomorphic to $B(2,n)$. Thus it is enough to show that the natural map from $H$ to ${\mathcal G}$ is an embedding. So far our argument was completely generic. We have not used any specific properties of words $u_y$, and the $S$-machine $\sss$. Let us explain now (in general terms) what these properties are and how they come into play. The idea is to consider two other auxiliary groups. The group ${\mathcal G}_1$ generated by ${\mathcal A}\cup {\mathcal C}$ subject to the relations (1) from ${\mathcal R}$, $u$-relations (2), the Burnside relations (4), and the derived relations (5). We are not claiming so far that ${\mathcal G}_1$ is the subgroup of ${\mathcal G}$ generated by ${\mathcal A}$ (although it is going to be so). It is clear that ${\mathcal G}_1$ is generated by $\mathcal A$ and is given by relations (1) and (5) where every letter $y\in{\mathcal C}$ is replaced by the corresponding word $u_y$ in the alphabet ${\mathcal A}$ plus all Burnside relations (4) in the alphabet ${\mathcal A}$. Let $L$ be the normal subgroup of the free Burnside group $B({\mathcal A},n)$ (freely generated by ${\mathcal A}$) generated as a normal subgroup by all relators (1) from ${\mathcal R}$ and all derived relators (5) where letters from ${\mathcal C}$ are replaced by the corresponding words $u_y$. Then ${\mathcal G}_1$ is isomorphic to $B({\mathcal A},n)/L$. Consider the subgroup $U$ of $B({\mathcal A},n)$ generated (as a subgroup) by $\{u_y| y\in {\mathcal C}\}$. The words $u_y$, $y\in {\mathcal C}$, are chosen in such a way that the subgroup $U$ is a free Burnside group freely generated by $u_y$, $y\in {\mathcal C}$, and it satisfies the \label{cepp}{\em congruence extension} property, namely every normal subgroup of $U$ is the intersection of a normal subgroup of $B({\mathcal A},n)$ with $U$. (The existence of such a subgroup with infinite number of generators is non-trivial. It is also of independent interest because it immediately implies, in particular, that every countable group of exponent $n$ is embeddable into a finitely generated group of exponent $n$. This was first proved by Obraztsov (see \cite{book}).) All defining relators of ${\mathcal G}_1$ are inside $U$. Since $U$ satisfies the congruence extension property, the normal subgroup $\bar L$ of $U$ generated by these relators is equal to $L\cap U$. Hence $U/\bar L$ is a subgroup of $B({\mathcal A},n)/L={\mathcal G}_1$. But by the choice of $U$, there exists a (natural) isomorphism between $U$ and the free Burnside group $B({\mathcal C},n)$ generated by ${\mathcal C}$, and this isomorphism takes $\bar L$ to the normal subgroup generated by relators from ${\mathcal R}$ and the derived relations (5). Therefore $U/\bar L$ is isomorphic to $H$ (since, by construction, $H$ is generated by ${\mathcal C}$ subject to the Burnside relations, relations from ${\mathcal R}$ and derived relations)! Hence $H$ is a subgroup of ${\mathcal G}_1$. Let ${\mathcal G}_2$ be the subgroup of $H$ generated by ${\mathcal B}$. Therefore we have \[{\mathcal G}_1 \ge H \ge {\mathcal G}_2.\] Notice that the map $a_i\to b_i$, $i=1,\dots,m$, can be extended to a homomorphism \label{phi1}$\phi_{1,2}: {\mathcal G}_1\to {\mathcal G}_2$. Indeed, as we mentioned above, ${\mathcal G}_1$ is generated by ${\mathcal A}$ subject to Burnside relations, all relators from ${\mathcal R}$ and all derived relators (5) where letters from ${\mathcal C}$ are replaced by the corresponding words $u_y$. If we apply $\phi_{1,2}$ to these relations, we get Burnside relations and derived relations which hold in ${\mathcal G}_2 \le H$. The main technical statement of the paper shows that $\phi_{1,2}$ is an isomorphism, that is, for every relation $w(b_1,\dots,b_m)$ of ${\mathcal G}_2$ the relation $w(a_1,\dots,a_m)$ holds in ${\mathcal G}_1$. This implies that the HNN extension $\la {\mathcal G}_1,{\bf t} \mid {\bf t}\iv {\mathcal G}_1{\bf t} ={\mathcal G}_2\ra$ is isomorphic to ${\mathcal G}$. Indeed, this HNN extension is generated by ${\mathcal G}_1$ and ${\bf t}$, subject to relations (1), (2), (4), (5) of ${\mathcal G}_1$ plus relations (3). So this HNN extension is presented by relations (1)--(5), which is the presentation of ${\mathcal G}$. Therefore ${\mathcal G}_1$ is a subgroup of ${\mathcal G}$, hence $H$ is a subgroup of ${\mathcal G}$ as well. The proof of the fact that $\phi_{1,2}$ is an isomorphism requires a detailed analysis of the group $H$. This group can be regarded as a factor-group of the group $H'$ generated by ${\mathcal C}$ subject to the relations (1) from ${\mathcal R}$ and derived relations (5) (this group is denoted in the paper by $H_{kra}$) over the normal subgroup generated by Burnside relations (4). In other words, $H$ is the {\em Burnside factor} of $H'$. Burnside factors of free groups and free products have been studied first by Adian and Novikov in \cite{AN}, \cite{Adian2}. Geometric approach based on the notion of $A$-map was employed in the study of Burnside factors of these and more complicated groups in \cite{book}. The papers \cite{Ol95}, \cite{OlIvanov} extend this approach to Burnside factors of hyperbolic groups. The main problem we face in this paper is that $H'$ is ``very" non-hyperbolic. In particular, the set of relations ${\mathcal R}$ contains many commutativity relations, so $H'$ contains non-cyclic torsion-free abelian subgroups, which cannot happen in a hyperbolic group. Nevertheless (and this is one of the main ideas of the proof), one can make the Cayley graph of $H'$ look hyperbolic if one divides the generators from ${\mathcal C}$ into two sets and consider letters from one set as zero letters, and the corresponding edges of the Cayley graph as edges of length 0. Thus the \label{lop}{\em length of a path} in the Cayley graph or in a \vk diagram over the presentation of $H$ is the number of non-zero edges of the path. More precisely, the group $H'$ is similar to the group $G(\sss)$ of \cite{SBR}, \cite{talk}, \cite{OS}. As we mentioned above, it corresponds to an $S$-machine $\sss$. The set ${\mathcal C}$ consists of tape letters (the set $\aaa$), state letters (the set $\bkk$) and command letters (the set $\rr$). Recall that unlike an ordinary Turing machine, an $S$-machine works with elements of a group, not elements of the free semigroup. It turns out that the most productive point of view is to regard an $S$-machine as an inverse semigroup of partial transformations of a set of states which are special ({\em admissible}) words of the group $\hnka$ which is the free product of the free group generated by $\bkk$ and the subgroup of $H'$ generated by $\aaa$. The generators of the semigroup are the $S$-{\em rules} (each one of them simultaneously replaces certain subwords in a word by other specified subwords). The machine $\sss$ is the set of the $S$-rules. Every computation of the machine corresponds to a word over $\sss$ which is called the \label{history}{\em history of computation}, i.e., the string of commands used in the computation. With every computation $h$ applied to an admissible element $W$, one associates a \vk diagram $T(W,h)$ (called a trapezium) over the presentation of $H'$ (see Figure \ref{figure1}). %(see \setcounter{pdeleven}{\value{ppp}} Figure \thepdeleven). \begin{figure}[h] %***Picture \unitlength=1.00mm %\special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(108,58)(18,0) %\begin{picture}(108.72,66.94) \put(53.72,5.94){\line(1,0){36.33}} \put(90.06,5.94){\line(1,3){15.67}} \put(105.72,52.94){\line(-1,0){56.00}} \put(49.72,52.94){\line(-1,0){6.00}} \put(43.72,52.94){\line(1,-5){9.33}} \put(59.06,5.94){\line(-1,0){6.33}} \put(57.39,5.94){\line(-1,5){9.33}} \put(85.72,5.94){\line(1,3){15.67}} \put(101.39,52.61){\line(1,0){4.33}} \put(101.72,52.78){\line(1,0){4.00}} \put(52.39,9.11){\line(1,0){4.33}} \put(51.56,12.78){\line(1,0){4.50}} \put(50.72,17.28){\line(1,0){4.33}} \put(49.89,22.28){\line(1,0){4.33}} \put(48.89,27.28){\line(1,0){4.33}} \put(47.89,31.67){\line(1,0){4.33}} \put(47.06,36.44){\line(1,0){4.33}} \put(46.06,40.94){\line(1,0){4.33}} \put(45.06,46.11){\line(1,0){4.33}} \put(86.72,9.11){\line(1,0){4.50}} \put(87.89,12.78){\line(1,0){4.50}} \put(89.56,17.33){\line(1,0){4.17}} \put(91.06,22.33){\line(1,0){4.50}} \put(92.89,27.28){\line(1,0){4.17}} \put(92.89,27.28){\line(1,0){4.33}} \put(94.39,31.67){\line(1,0){4.33}} \put(95.89,36.33){\line(1,0){4.33}} \put(97.39,41.00){\line(1,0){4.33}} \put(99.06,46.00){\line(1,0){4.50}} \put(49.39,46.00){\line(1,0){50.00}} \put(53.22,46.00){\line(0,1){6.83}} \put(61.39,46.00){\line(0,1){6.83}} \put(61.39,53.00){\line(0,0){0.00}} \put(79.22,46.00){\line(0,1){6.83}} \put(89.72,46.00){\line(0,1){6.83}} \put(71.22,46.00){\line(0,1){6.83}} \put(37.39,29.61){\makebox(0,0)[cc]{History $h$}} \put(108.72,29.94){\makebox(0,0)[cc]{History $h$}} \put(70.06,2.94){\makebox(0,0)[cc]{Starting word $W$}} \put(70.06,56.94){\makebox(0,0)[cc]{Last word $W\cdot h$}} \put(46.00,41.00){\line(1,0){54.33}} \put(49.33,36.33){\line(1,0){49.00}} \put(50.67,31.67){\line(1,0){46.00}} \put(51.00,27.28){\line(1,0){44.67}} \put(51.33,22.33){\line(1,0){42.33}} \put(53.00,17.33){\line(1,0){38.67}} \put(54.33,12.67){\line(1,0){35.67}} \put(54.67,9.00){\line(1,0){35.00}} \put(53.33,45.67){\line(0,-1){4.67}} \put(61.33,46.00){\line(0,-1){5.00}} \put(79.33,46.00){\line(0,-1){5.00}} \put(89.67,46.00){\line(0,-1){5.00}} \put(57.67,41.00){\line(0,-1){4.67}} \put(66.00,41.00){\line(0,-1){23.67}} \put(76.33,53.00){\line(0,-1){47.00}} \put(79.33,53.00){\line(0,-1){47.00}} \put(83.33,41.00){\line(0,-1){35.00}} \put(71.33,40.67){\line(0,-1){34.67}} \put(61.67,17.33){\line(0,-1){4.67}} \put(66.00,12.67){\line(0,-1){6.67}} \put(89.67,41.00){\line(0,-1){13.67}} \put(61.33,43.33){\line(0,-1){21.00}} \put(53.33,36.33){\line(0,1){7.33}} \put(66.00,46.00){\line(0,-1){5.00}} \end{picture} \caption{ }\label{figure1} \end{figure} %\begin{center} %\nopagebreak[4] Fig. \theppp. %\end{center} %\addtocounter{ppp}{1} The first and the last words of the computation are written on the bases of the trapezium; copies of the history of the computation are written on the vertical sides. The horizontal strips (bands) of cells correspond to applications of individual rules in the computation. The trapezia $T(W,h)$ play a central role in our study of the Burnside factor $H$ of $H'$. As in \cite{book}, the main idea is to construct a graded presentation ${\mathcal R}'$ of $H$ where longer relations have higher ranks and such that every \vk diagram over the presentation of $H'$ has the so called property A from \cite{book}. In all diagrams over the graded presentation of $H$, cells corresponding to the relations from ${\mathcal R}$ and derived relations are regarded as $0$-cells or cells of rank $1/2$, and cells corresponding to Burnside relations from the graded presentation are regarded as cells of ranks $1, 2,\dots$\,. So in these \vk diagrams ``big" Burnside cells are surrounded by ``invisible" 0-cells and ``small" cells. The main part of property A from \cite{book} is the property that if a diagram over ${\mathcal R}'$ contains two Burnside cells $\Pi_1, \Pi_2$ connected by a rectangular {\em \ct} subdiagram $\Gamma$ of rank 0 where the sides contained in the contours of the two Burnside cells are ``long enough", then these two cells cancel, that is, the union of $\Gamma$, $\Pi, \Pi'$ can be replaced by a smaller subdiagram. This is a ``graded substitute" to the classic property of small cancellation diagrams (where \ct subdiagrams contain no cells). Roughly speaking nontrivial \ct subdiagrams of rank 0 turn out to be trapezia of the form $T(W,h)$ (after we clean them of Burnside $0$-cells), so properties of \ct subdiagrams can be translated into properties of the machine $\sss$ and the inverse semigroup described above. Three important properties of this inverse semigroup can be singled out: \begin{itemize} \item If an element $W$ is in the domain of $h^2$, then it is in the domain of $h^s$ for every integer $s$. In other words, if a sequence of rules can be applied twice in a row, it can be applied any number of times. That lemma is used in the geometric part of the proof when we are cleaning \ct subdiagrams of Burnside 0-cells. \item If a word $W$ is stabilized by $h$, $ghg\iv$ and $g\iv hg$, then it is stabilized by $g^shg^{-s}$ for any integer $s$. This fact is used when we consider long and narrow \ct subdiagrams with periodic top and bottom sides. \item Two words $h_1$ and $h_2$ in the alphabet $\sss$ define the same partial transformation on the intersection of their domains provided $h_1$ and $h_2$ are equal modulo Burnside relations. Thus the work of the $S$-machine is ``compatible" with the Burnside relations. \end{itemize} As an intermediate step in studying the group $H$, we construct a graded presentation of the Burnside factor of the subgroup of $H'$ generated by $\rr\cup\aaa$. To avoid repeating the same arguments twice, for $H'$ and for the subgroup, we formulate certain key properties (Z1), (Z2), (Z3) of a presentation of a group with a separation of generators into zero and non-zero generators, so that there exists a graded presentation of the Burnside factor of the group which satisfies property A. In order to roughly explain these conditions, consider the following example. Let $P=F_A\times F_B$ be the direct product of two free groups of rank $m$. Then the Burnside factor of $P$ is simply $B(m,n)\times B(m,n)$. Nevertheless the theory of \cite{book} cannot be formally applied to $P$. Indeed, there are arbitrarily thick rectangles corresponding to relations $u\iv v\iv uv=1$ in the Cayley graph of $P$ so diagrams over $P$ are not A-maps in the terminology of \cite{book} (i.e., they do not look like hyperbolic spaces). But one can obtain the Burnside factor of $P$ in two steps. First we factorize $F_A$ to obtain $Q=B(m,n)\times F_B$. After that we consider all edges labeled by letters from $A$ in the Cayley graph of $Q$ as edges of length 0. As a result the Cayley graph of $Q$ becomes a hyperbolic space. This allows us to apply the theory of A-maps from \cite{book} to obtain the Burnside factor of $Q$. The real reason for the theory from \cite{book} to work in $Q$ is that $Q$ satisfies our conditions (Z1), (Z2), (Z3). But the class of groups satisfying these conditions is much larger and includes groups corresponding to $S$-machines considered in this paper. In particular (Z3) holds in $Q$ because all 0-letters centralize $F_B$. This does not happen in more complicated situations. But we associate with every cyclically reduced non-0-element $w$ a ``personal" subgroup $\oo(w)$ consisting of $0$-elements, which is normalized by $w$. Although in our study of Burnside factors of groups satisfying (Z1), (Z2), (Z3), we follow the general scheme of \cite{book}, we encounter new significant difficulties. One of the main difficulties is that non-zero elements can be conjugates of zero elements. The full proof of Theorem \ref{main} will appear in \cite{OSamen}. \begin{thebibliography}{10} \bibitem{Adian} S.~I. Adian. Random walks on free periodic groups. Izv. Akad. Nauk SSSR, Ser. Mat. 46 (1982), 1139--1149. \MR{84m:43001} %\bibitem{Adian1} S.~I. Adian. %{\em The Burnside problem and identities in groups.} Ergebnisse %der Mathematik und ihrer Grenzgebiete [Results in Mathematics and %Related Areas], 95. Springer-Verlag, Berlin-New York, 1979, 311 %pp. \bibitem{Adian2} S.~I. Adian. Periodic products of groups. Number theory, mathematical analysis and their applications. Trudy Mat. Inst. Steklov. 142 (1976), 3--21, 268. \MR{80m:20030} \bibitem{BT} S. Banach, A. Tarski. Sur la d\'{e}composition des ensembles de points en parties respectivement congruentes. Fund. Math 6 (1924), 244--277. \bibitem{BORS} J. C. Birget, A.~Yu. Ol'shanskii, E.~Rips, M. V. Sapir. Isoperimetric functions of groups and computational complexity of the word problem, 1998 (submitted to Annals of Mathematics), preprint available at \texttt{http://www.math.vanderbilt.edu/\-$\sim$msapir/publications.html.} \bibitem{BS} M.~G.~Brin and C.~C.~Squier. Groups of piecewise linear homeo\-mor\-phisms of the real line. Invent. Math. 79 (1985), 485--498. \MR{86h:57033} \bibitem{CFP} J.~W.~Cannon, W.~J.~Floyd and W.~R.~Parry. Introductory notes on Richard Thompson's groups. L'Enseignement Math\'ematique (2) 42 (1996), 215--256. \MR{98g:20058} \bibitem{Cliff-Prest} A.H. Clifford and G.B. Preston, {\em The algebraic theory of semigroups}. Vol. I. Mathematical Surveys, No. 7. American Mathematical Society, Providence, R.I. 1961. \MR{24:A2627} \bibitem{Cohen} J. M. Cohen. Cogrowth and amenability of discrete groups. J. Funct. Anal. {\bf 48} (1982), no.~3, 301--309. \MR{85e:43004} \bibitem{day} Mahlon M. Day. Amenable semigroups. Illinois J. Math. 1 (1957), 509--544. \MR{19:1067c} \bibitem{Geogh} Open problems in infinite-dimensional topology. Edited by Ross Geoghegan. The Proceedings of the 1979 Topology Conference (Ohio Univ., Athens, Ohio, 1979). Topology Proc. 4 (1979), no. 1, 287--338 (1980). \MR{82a:57015} \bibitem{Greenleaf} F. P. Greenleaf. {\em Invariant means on topological groups and their applications.} Van Nostrand Reinhold, New York, 1969. \MR{40:4776} \bibitem{Grigorchuk} R.~I. Grigorchuk. Symmetrical random walks on discrete groups. Multicomponent random systems. Adv. Probab. Related Topics, 6, Dekker, New York, 1980, 285--325. \MR{83k:60016} \bibitem{Grig} R.~I. Grigorchuk. An example of a finitely presented amenable group that does not belong to the class {E}{G}. {\em Mat. Sb.} 189 (1) (1998), 79--100. \MR{99b:20055} \bibitem{Haus} F. Hausdorff. {\em Grundz\"{u}ge der Mengenlehre}. Leipzig, 1914. \bibitem{OlIvanov} S. V. Ivanov and A.~Y. Ol'shanskii. Hyperbolic groups and their quotients of bounded exponents. Trans. Amer. Math. Soc. 348 (1996), no. 6, 2091--2138. \MR{96m:20057} \bibitem{Kesten2} Harry Kesten. Full {B}anach mean values on countable groups. Math. Scand. {\bf 7} (1959), 146--156. \MR{22:2911} %\bibitem{Kesten1} Harry Kesten. Symmetric random walks on groups. Trans. Amer. Math. Soc. {\bf 92} (1959), %336--354. \bibitem{KhSap} O.~G. Kharlampovich and M.~V. Sapir. Algorithmic problems in varieties. Internat. J. Algebra Comput. 5 (1995), no. 4-5, 379--602. \MR{96m:20045} \bibitem{Kour} {\em Kourovka Notebook}. Unsolved Problems in Group Theory. 8th edition, Novosibirsk, 1982. \MR{84m:20002} \bibitem{LS} Roger Lyndon and Paul Schupp. {\it Combinatorial group theory}. Springer-Verlag, 1977. \MR{58:28182} \bibitem{vN} J. von Neumann. Zur allgemeinen Theorie des Masses. Fund. Math. 13 (1929), 73--116. \bibitem{AN} P. S. Novikov and S.~I. Adian. Infinite periodic groups. I, II, III, (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 32 (1968), 212--244, 251--524, 709--731. \MR{39:1532a}; \MR{39:1532b}; \MR{39:1532c} \bibitem{OlTar}A.~Yu. Ol'shanskii. An infinite simple torsion-free Noetherian group. Izv. Akad. Nauk SSSR Ser. Mat. 43 (1979), no. 6, 1328--1393. \MR{81i:20033} \bibitem{OlTar1} A.~Yu. Ol'shanskii. An infinite group with subgroups of prime order. Izv. Akad. Nauk SSSR Ser. Mat. 44 (1980), no. 2, 309--321. \MR{82a:20035} \bibitem{OlAmen} A.~Yu. Ol'shanskii. On the question of the existence of an invariant mean on a group. (Russian) Uspekhi Mat. Nauk 35 (1980), no. 4 (214), 199--200. \MR{82b:43002} \bibitem{book} A.~Yu. Ol'shanskii. {\it The geometry of defining relations in groups}, Nauka, Moscow, 1989. \MR{91i:20035} \bibitem{Ol95} A. Yu. Ol'shanskii. The SQ-universality of hyperbolic groups, Mat. Sb. 186 (1995), no. 8, 119--132. \MR{97b:20057} %\bibitem{OlDist} A. Yu. Ol'shanskii. % On distortion of subgroups in finitely presented groups. Mat. %Sb., 1997, V.188, N 11, 51-98. \bibitem{OS} A. Yu. Ol'shanskii, M. V. Sapir. Embeddings of relatively free groups into finitely presented groups. Contemporary Mathematics, 264 (2000), 23--47. \CMP{2001:05} \bibitem{talk} A.~Yu. Ol'shanskii and M.~V. Sapir. Length and area functions on groups and quasi-isometric Higman embeddings. To appear, IJAC, 2000. \bibitem{OSamen} A.~Yu. Ol'shanskii and M.~V. Sapir. Non-amenable finitely presented torsion-by-cyclic groups. (Submitted). %\bibitem{Sa87} %M. V. Sapir. % Problems of {Burnside} type and the finite basis property in % varieties of semigroups. % Izv. Akad. Nauk. SSSR. Ser. Mat., 51(2), 1987, 319--340. \bibitem{SBR} M. V. Sapir, J. C. Birget, E. Rips. Isoperimetric and isodiametric functions of groups, 1997, submitted to Annals of Mathematics, preprint available at\newline \texttt{http://www.math.vanderbilt.edu/$\sim$msapir/publications.html.} \pagebreak \bibitem{Specht} W. Specht. Zur {T}heorie der messbaren {G}ruppen. {Math. Z.} {74} (1960), 325--366. \MR{25:4058} \bibitem{Tits} J. Tits. Free subgroups in linear groups. J. Algebra 20 (1972), 250--270. \MR{44:4105} \end{thebibliography} \end{document}