\newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \part{Automatic and Biautomatic Groups} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In the late 1980s and early 1990s the theory of automatic groups was rapidly developed by a number of different researchers and the basic theory was recorded in a book and a survey article that were both published in 1992. These continue to be two of the main sources of basic information about automatic groups. The book is ``Word processing in groups'' by David Epstein, Jim Cannon, Derek Holt, Silvio Levy, Michael Paterson and Bill Thurston \cite{ECHLPT92}. It carefully defines automatic, biautomatic, asynchronously automatic, combable, bicombable and asynchronously bicombable groups, and many foundational results about these classes of groups appear there in print for the first time.\footnote{The introduction also contains a detailed description of the early history of these concepts.} The survey article is ``Automatic Groups: A Guided Tour'' by Benson Farb \cite{Fa92}. It is a short and leisurely introduction to the theory that surveys the basic ideas, major results, key examples and non-examples without delving too far into the details of the proofs. (A third source of basic information is the proceedings of the 1989 MSRI conference on algorithms in combinatorial group theory \cite{MSRI92}, also published in 1992.) The main drawback of these sources is that they were published $15$ years ago, and thus their descriptions of open problems need to be brought up to date. Since 1990 there have been significant papers on \begin{itemize} \item biautomaticity and small cancellation groups (Gersten and Short \cite{GeSh90,GeSh91b}), \item rational subgroups of biautomatic groups (Gersten and Short \cite{GeSh91a}), \item automaticity of Coxeter groups (Brink and Howlett \cite{BrHo93}). \item biautomaticity of finite-type Artin groups (Charney \cite{Ch95}), \item automaticity of mapping class groups (Mosher \cite{Mo95}), \item central quotients of biautomatic groups (Mosher \cite{Mo97}), \item biautomaticity of fundamental groups of nonpositively curved cube complexes (Niblo and Reeves \cite{NiRe98}), \item introduction and biautomaticity of Garside groups (Dehornoy \cite{De02}), \item biautomaticity of many Coxeter groups (Niblo and Reeves \cite{NiRe03}) \end{itemize} (via actions on cube complexes), and the 2003 paper by Martin Bridson that finally distinguished the classes of automatic, combable and bicombable groups \cite{Bri03}. \mcomment{Q: Any other highpoints that I overlooked? include Neumann-Shapiro, and Rebecchi somewhere} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Eight Families of Groups} Let $\Gamma$ be a connected graph with a cocompact group action. There are eight closely-related families of groups that are defined by the existence of such a graph $\Gamma$ together with a collection of distinguished paths in $\Gamma$ with additional properties. Such properties might include that the collection be recognized by a finite state automaton, that every path in the collection must be a $(k,\epsilon)$-quasi-geodesic, or that the paths in the collection that start and/or end close together must $k$-fellow travel. The schematic relationships among the eight families are shown in Figure~\ref{fig:8groups} and their definitions can easily be found in the references, particularly \cite{ECHLPT92}, except for semi-hyperbolic groups which were only introduced by Alonso and Bridson in 1995 \cite{AlBr95}. For semi-hyperbolic groups, \cite{BrHa99} is a good reference. \begin{figure}[ht] $\begin{CD} \textrm{hyperbolic} @>\neq >> \textrm{biautomatic} @>?>> \textrm{automatic} @>\neq >> \textrm{asyn. automatic}\\ @V\neq VV @V\neq VV @V\neq VV @V\neq VV\\ \textrm{semi-hyperbolic} @>? >> \textrm{bicombable} @>\neq >> \textrm{combable} @>? >> \textrm{asyn. combable} \end{CD}$ \caption{Eight related families of groups.\label{fig:8groups}} \end{figure} In Figure~\ref{fig:8groups} an arrow $A\rightarrow B$ indicate that every group of type $A$ is a group of type $B$. Thus Gromov hyperbolic groups are the most and asynchronously combable groups are the less restrictive of the eight classes depicted. The question marks and inequality signs indicate whether or not these inclusions are known to be strict. Some of the counterexamples are easy. The group $\Z^2$ is biautomatic and semi-hyperbolic but not hyperbolic and it is shown in \cite{ECHLPT92} that the non-solvable Baumslag-Solitar groups are asynchronouslly automatic but not automatic. \mcomment{Some of the other questionmarks probably have easy counterexamples that I am overlooking.} For a long time it was an open question whether combable groups were automatic or bicombable, but in 2003 Martin Bridson gave examples of combable groups that are not bicombable and examples of combable groups that are not automatic \cite{Bri03}. An asynchronously combable but not asynchronously automatic example can be found in \cite{Bri93} and is further explored in \cite{BrGi95} and \cite{BrGi96}. In addition, there is a free-by-cyclic group that a bicombable but not biautomatic group constructed by Brady and Bridson (unpublished) and this example is not even automatic (Bridson and Reeves, also unpublished). At this point there are at least three major questions along these lines that are still wide open. \begin{q}[Automatic vs. Biautomatic] Is every automatic group biautomatic? \end{q} Most experts agree that the answer is probably no, and several potential counterexamples have been suggested. \mcomment{add citations} \begin{q}[$\cat(0)$ vs. Biautomatic]\label{q:cat-aut} Is every $\cat(0)$ group biautomatic? \end{q} The class of $\cat(0)$ groups is contained in the class of semi-hyperbolic groups and its relationship to hyperbolicity is a well-known open problem. Some partial positive results are discussed below in \S\ref{sec:npc}. The converse of Question~\ref{q:cat-aut} is known to be false. \mcomment{add cites} The third question along these lines is the biautomatic analog of Thurston's hyperbolization conjecture. \begin{q}[Hyperbolic vs. Biautomatic] Is every biautomatic group with no $\Z\times \Z$ subgroup word hyperbolic? \end{q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Basic Structural Properties} There were two early problem collections focused on automatic groups: one collected by Steve Gersten and published in \cite{Ge92} and the other in Benson Farb's survey article \cite{Fa92}. The two lists have significant overlap, and neither seriously addresses the open questions about the then recently invented theory of biautomatic groups. \comment{Finish pulling together the next several jotted notes} The principal examples of automatic groups are finite groups, Euclidean groups, negatively curved groups (including word-hyperbolic groups), various small cancellation groups, Coxeter groups, geometrically finite groups and braid groups. Many of these Groups that have been shown to not support an automatic structre include infinite torsion groups, nilpotent groups that are not virtually abelian, ${\rm SL}_n(Z)$ for $n\geq 3$, and non-solvable Baumslag-Solitar groups. Some of the most important properties of automatic groups are that they are finitely presented and have solvable word problem. They are closed under direct and free products (with finite amalgamated subgroup) and under finite extension. Biautomatic groups are known to have a solvable conjugacy problem, polycyclic subgroups of biautomatic groups are abelian by finite, the Baumslag-Solitar group $BS(1,2)$ cannot be isomorphic to a subgroup of a biautomatic group, and the center of a biautomatic group is always finitely generated. Biautomatic groups include all word hyperbolic groups, all fundamental groups of finite volume hyperbolic and Euclidean orbifolds, the braid groups and central extnensions of word hyperbolic groups. %question $7$ has an affirmative solution for biautomatic groups, Is % this the infinite cyclic subgroup one? Several important structural results about subgroups and quotients of biautomatic groups were shown by Gersten and Short in \cite{GeSh91a} and Lee Mosher in \cite{Mo97}. Together these two papers establish all of the following results. \begin{thm} If $G$ is a biautomatic group and $H$ is the centralizer in $G$ of a finite set of elements, then $H$ is biautomatic. If $C$ is a subgroup of the center of $G$ then $G/C$ is biautomatic. If $L$ is a direct factor of $G$ then $L$ is biautomatic. If $K$ is a polycyclic subgroup of $G$ then $K$ is virtually abelian. And finally, the group $G$ does not contain any subgroups isomorphic to $BS(k,l)$ with $|k|\neq |l|$. \end{thm} Combined with the foundational results shown in \cite{ECHLPT92}, we thus know that free products, direct products, free factors and direct factors of biautomatic groups are biautomatic. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Structural Questions} The care that needs to be taken to distinguish between automatic and biautomatic is illustrated by their known closure properties. For the most part, every closure property that is known to hold for automatic groups, is also known to hold for biautomatic groups with one glaring exception: every virtually automatic group (i.e. a group that contains a finite index automatic subgroup) is itself automatic. This is an open question for biautomatic groups. \begin{q}[Finite Extensions] Is a virtually biautomatic group biautomatic? \end{q} With that sole exception, the rest of the questions posed here are either open for both automatic and biautomatic groups or they are known for biaumatic groups and open for automatic groups. \mcomment{Any progress on these? Are any others known for biautomatic?} \begin{p}[Conjugacy Problem] Biautomatic groups are known to have a solvable conjugacy problem. Determine whether or not every automatic group has a solvable conjugacy problem. \end{p} \begin{q}[Tits alternative] Do either automatic or biautomatic groups satisfy the Tits alternative? That is, does every subgroup that is not virtually abelian contain a copy of a non-abelian free group? \mcomment{Are these both still open?} \end{q} \begin{q}[Hopfian]\label{q:aut-hopf} Are automatic groups Hopfian? Are biautomatic groups? \end{q} %GL8 \begin{q}[Center] Is the center of an automatic group finitely generated? Is there a bound on the order of the torsion elements in the center? \end{q} The center of a biautomatic group is known to be finitely generated. \mcomment{add cite} \begin{q}[Retracts] Is a retract of an automatic group automatic? \mcomment{Known for biautomatic?} \end{q} %GL14 \begin{q}[Cyclic Amalgamations] Let $G = A \ast_C B$ where $A$ and $B$ are automatic and $C$ is infinite cyclic. Is $G$ automatic? \mcomment{Known for biautomatic?} \end{q} The next four questions ask about properties of subgroups of automatic and biautomatic groups. %GL16 \begin{q}[Finite-index subgroups] Is every automatic group residually finite? Does an automatic group necessarily have even one nontrivial subgroup of finite index? Similar questions can be asked about biautomatic groups. \end{q} %GL7 \begin{q}[Cyclic subgroups] Let $G$ be a automatic group and let $x \in G$ be an element of infinite order. Is the map of the set of integers into the Cayley graph of $G$ given by $n \mapsto x^n$ a quasi-isometry? \end{q} %GL4 \begin{q}[Polycyclic subgroups] Every polycyclic subgroup of a biautomatic group and every virtuallly nilpotent subgroup of an automatic group is virtually abelian. Must every polycyclic subgroup of an automatic group be virtually abelian? \end{q} \begin{q}[Baumslag-Solitar subgroups] Biautomatic groups do not contain any subgroups isomorphic to $BS(k,l)$ with $|k|\neq |l|$. Is the same true for automatic groups? More specifically, can an automatic group contain a $BS(1,2)$ subgroup? \end{q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Connections to Negative and Nonpositive Curvature}\label{sec:npc} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% There are many results that connect presence of negative or nonpositive curvature to the existence of an automatic or biautomatic struture. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Riemannian Manifolds} \comment{Describe the key automaticity results about Riemannian manifolds (in arbitary dimensions) with strictly negative sectional curvature. Include the finite volume hyperbolic and euclidean orbifold results, and mention the Neumann and Shapiro \cite{NeSh95} paper that classifies \emph{all} automatic and biautomatic structures on geometrically finite hyperbolic groups.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Piecewise Euclidean Complexes} In modern terminology, two of the main results that Gersten and Short proved in \cite{GeSh90} and \cite{GeSh91b} are that groups that act freely, cellularly and cocompactly on either (1) $\cat(0)$ square complexes or (2) $\cat(0)$ triangle complexes, are biautomatic. A triangle complex is a simplicial $2$-complex in which every edge has unit length and the $2$-cells are isometric to equilateral triangles. Since {\'S}wi{\.a}tkowski \cite{Sw06} recently proved a theorem (using what he calls regular path systems) that allows many previous theorems proving biautomaticity that assumed the group actions on various complexes were free to be weakened to actions that are merely proper, the Gersten and Short results can be strengthened to assert that all groups acting geometrically on $\cat(0)$ square complexes or on $\cat(0)$ triangle complexes are biautomatic. Both of these results have been generalized to higher dimensions. The square complex result was generalized to cube complexes by Niblo and Reeves \cite{NiRe98}. Combined with {\'S}wi{\.a}tkowski's results, we now know that groups that act geometrically on $\cat(0)$ cube complexes are biautomatic. The triangle complex result have been generalized by Januszkiewicz and {\'S}wi{\.a}tkowski through their theory of simplicial non-positive curvature \cite{JaSw06}. It is still an open question whether the straightforward $\cat(0)$ generalization of the triangle complex result is true. \begin{conj}\label{conj:simplicial} If $G$ acts geometrically on a $\cat(0)$ piecewise Euclidean simplicial complex with unit edge lengths, then $G$ is biautomatic. \end{conj} Recently, Rena Levitt has shown \cite{Le-biaut} that any group that acts geometrically on a $\cat(0)$ triangle-square complex is biautomatic. By a triangle-square complex, I mean a piecewise Euclidean complex with unit edge lengths in which each $2$-cell is a triangle or a square. This leads to the following conjecture that would encompass cube complexes and Conjecture~\ref{conj:simplicial} as special cases. Call a piecewise Euclidean cell complex a \emph{simplicial product complex} if every cell is isometric to a direct product of regular Euclidean simplices with edges of unit length. \begin{conj} If $G$ acts geometrically on a $\cat(0)$ simplicial product complex, then $G$ should be biautomatic. \end{conj} Alternatively, find conditions similar to Januszkiewicz and {\'S}wi{\.a}tkowski simplicial nonpositive curvature that ensure biautomaticity. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Relations with Standard Classes of Groups} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Much of the recent work on automaticity and biautomaticity has been on directed towards clarifying how these concepts interact with well-known classes of groups. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{$3$-Manifold Groups} \comment{Describe the geometrization-automatic results from \cite{ECHLPT92}. Thurston's geometries and the no nil or sol pieces implies automatic.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Mapping Class Groups} In 1995, Lee Mosher proved that all mapping class groups are automatic \cite{Mo95}, a result that can be viewed as a vast generalization of the automaticity of the braid groups. This leads to an obvious question that remains wide open. \begin{q}[Mod(\script{S}) biautomaticity] Are mapping class groups biautomatic? \end{q} Based on Mosher's result and the usual analogy between mapping class groups and automorphisms of free groups, one might conjecture that $\aut(\F_n)$ and $\out(\F_n)$ would at the least be automatic, but Martin Bridson and Karen proved in \cite{BrVo95} that this is not the case. \begin{thm} For $n\geq 3$ the groups $\aut(\F_n)$ and $\out(\F_n)$ do not admit a bounded bicombing of subexponential length. As a consequence, they are not biautomatic, or semihyperbolic, or $\cat(0)$. \end{thm} \begin{q} Is $\aut(\F_n)$ or $\out(\F_n)$ automatic? \end{q} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Free-by-$\Z$ Groups} A related class of groups are those that can be constructed from a single free group automorphism. %GL10 \begin{p}[Free-by-$\Z$ Groups] For a finitely generated free group $\F$ and each $\phi\in \aut(\F)$, let $G = \F \rtimes_\phi \Z$ be the corresponding mapping torus. When is $G$ automatic? when is $G$ biautomatic? \end{p} Martin and Noel have an example showing that not all are biautomatic and then Martin and Lawrence have shown that the same example is not automatic. The example is the $\F_3 \rtimes_\phi \Z$ defined by the automorphism $\phi$ sending $a\mapsto a$, $b\mapsto ba$, and $c\mapsto ca^2$. Gersten previously proved that this example is not $\cat(0)$. \comment{add cites} Note that Martin Bridson and Daniel Groves have recently been able to show that all finitely generated free-by-$\Z$ groups have a quadratic isoperimetric inequality. \mcomment{add cites and other partial results} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Lattices in Lie Groups} Two questions from the original problem lists asked about the automaticity of lattices in specific Lie groups. In particlular, he asked whether every lattice in $\SL_3(\R)$ is automatic and whether every cocompact irreducible lattice in $\isom(\hyp^2)\times \isom(\hyp^2)$ is automatic. Notice that this is a completely explicit class of groups. \comment{Cite Dave Witte-Morris} These questions can be placed in a larger context. \begin{p}[Lattices] Classify which lattices in Lie groups are automatic and which ones are biautomatic. \end{p} \mcomment{Ask Benson} The original questions are still open. Of course many non-cocompact lattices can be immediately ruled out by the strong restrictions on nilpotent subgroups. %%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Tubular Groups} Tubular groups include several particular examples that are potential counterexamples to other open questions. In particular, the groups \[G_{p,p} = \langle a,b,s,t\ |\ ab=ba, s^{-1}a^p s=a^p b, t^{-1}a^p t = a^p b^{-1} \rangle\] have a quadratic Dehn function \cite{BraBri00} but are not $\cat(0)$ \cite{Ge94} or biautomatic (Brady and Bridson, unpublished), and $G_{1,1}$ at least is asynchronously automatic \cite{El00}. \begin{q} Are the tubular groups $G_{p,p}$ automatic? \end{q} The tubular group $W=\langle a,b,s,t\ |\ ab=ba, s^{-1}as = (ab)^2, t^{-1}bt = (ab)^2 \rangle$ is known as \emph{Wise's group}. Dani Wise has shown \cite{Wi96} that it is $\cat(0)$ and non-Hopfian, and Murray Elder has found an asynchronous automatic structure on $W$ \cite{El00}. It is unknown whether or not it is automatic. \begin{q}[Wise's group]\label{q:wise-gp} Is Wise's tubular group automatic? \end{q} Resolving this Question~\ref{q:wise-gp} in either direction would answer an open question about automatic groups. It either provides an example of a $\cat(0)$ group that is not automatic (Question~\ref{q:cat-aut}), or it provides an example of an automatic group that is not Hopfian (Question~\ref{q:aut-hopf}). %%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Coxeter groups} As is the case for mapping class groups, the automaticity of Coxeter groups has been known for a while now. Brink and Howlett proved that all Coxeter groups are automatic in 1993 \cite{BrHo93}. Progress on biautomaticity has been slower. \begin{q}[Coxeter Groups] Are all Coxeter groups biautomatic? \end{q} Significant progress on this question occured when Graham Niblo and Lawrence Reeves were able to show in \cite{NiRe03} that all Coxeter groups act on properly discontinuously by isometries on $\cat(0)$ cube complexes, and in many cases, these actions are cocompact. In particular, they were able to prove the following result. \begin{thm} If $G$ is a finitely generated Coxeter group that contains only finitely many conjugacy classes of subgroups isomorphic to triangle groups, then $G$ is biautomatic. \end{thm} The analysis of the conditions under which the action is cocompact was completed by Niblo's Ph.D. student Ben William in his dissertation \cite{Wi99}. On a separate note, Bill Cassell has written a survey article that describes how to efficiently carry out computations in Coxeter groups using the $\gap$ package called $\chevie$ \cite{Ca02}. Several of the algorithms he describes are based on the work of du Cloux \cite{duCl99} and the automatic structures on Coxeter groups figure heavily in these algorithms. See also, the webpages he has set up based on the 2002 CRM conference on compuatations in Coxeter groups \cite{Ca-web}. %\comment{Many many many are biautomatic (Bahls,Caprace-Muehlheer,etc.)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Artin groups and Garside structures} In the same paper where Garside groups were first defined, Patrick Dehornoy showed that every group with a Garside structure is biautomatic \cite{De02}. One consequence of this theorem is that it shows that every Artin group of finite type is biautomatic (a result first proved by Ruth Charney in \cite{Ch95}). In particular, this reproves once again the basic result that the braid groups are biautomatic. \begin{p}[Artin groups] Determine which Artin groups are biautomatic, automatic, or asynchronously automatic. \end{p} This problem remains wide open, predominantly because for most Artin groups, we do not even know how to solve the word problem. First things, first. Eventually, this may become an interesting question. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{One relator groups} The class of one-relator groups have an uneasy relationship with the classes of groups under discussion since it clearly contains many hyperbolic examples (such as any one-relator group with torsion), but it also contains groups such as $BS(1,2)$ that are asynchronously automatic but not automatic, and groups such as Baumslag's group that are not even asynchronously combable. In particular, it is not yet clear which one-relator groups belong to which classes. \begin{p}[One-relator groups]\label{p:one-relator} Determine which one-relator groups are hyperbolic, biautomatic, automatic, or asynchronously automatic. \end{p} Although Problem~\ref{p:one-relator} is wide open, some answers have been conjectured. \begin{conj} A one-relator group is hyperbolic iff it contains no Baumslag-Solitar subgroups, and it is automatic iff it contains no metabelian subgroups. \end{conj}