Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. 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}