The role of the Automatic Groups in the history of Geometric Group Theory

Question

What is the role of the theory of Automatic Groups in the history of Geometric Group Theory?

Motivation:

When I read through the "Word Processing in Groups" I was amazed by the supreme beauty and elegance of the theory and of how robust it is. (That it started from conversations between (true artists) Cannon and Thurston made it a bit less shocking)

I'm aware of the early great results and that it was a big thing. I also read somewhere that it was one of the pillars of Geometric Group Theory in the 80s, but I also noticed that many (great, young) people in the field don't know about this theory. Is it less central? If yes, why? Many basic early questions are open...

Sometimes in such a fast moving field (ggt) a beginner loose perspective...

Answer 1

I think there are a few different ways in which Automatic Groups affected the history of Geometric Group Theory.

One was mentioned by Derek Holt, which I will spin in a slightly different way: if you really want to know the group, and if it has an automatic structure, you had better know that structure. For an individual group, the way to find out is to plug its presentation into the programs that Derek mentions. For classes of groups things can be trickier, but the effort is rewarding and sometimes even quite beautiful, for instance the proofs on automaticity of braid groups and Euclidean groups in "Word processing in groups", and the proof by Niblo and Reeves on biautomaticity of cubulated groups; and I retain a lot of affection for my paper proving automaticity of mapping class groups (and no offense taken, Misha).

Another thread of influence is the theory of biautomatic groups. To me, this theory is not yet played out, although as others say perhaps the open questions are hard. However, there are various beautiful pieces of this theory which had some interesting effects, and I think there is still some gold to mine here. The theory starts with the papers of Gersten and Short. Some applications of that theory are: the proof by Bridson and Vogtmann that $Out(F_n)$ is not biautomatic when $n \ge 3$; and my proof that direct factors of biautomatic groups are biautomatic. I also like the beautiful papers of Neumann and Shapiro which describe completely all possible automatic and biautomatic structures on $Z^n$, and the paper of Neumann and Reeves and its followup by Neumann and Shapiro which describe how to construct biautomatic structures on central extensions. I like to think that one of the effects of the Gersten/Short theory is that it gives a hint to a "hierarchical" structure on a biautomatic group. Farb's thesis follows this idea up with his notion of relatively automatic and bi-automatic groups, and the thesis of my student Donovan Rebbechi pins some of this down by giving rigorous proofs of some statements in Farb's thesis regarding bi-automatic structures on relatively hyperbolic groups. The theory of biautomatic groups is definitely still alive; poking around on MathSciNet just this very moment I find a paper that slipped my notice and that I want to go read right now, by Bridson and Reeves studying the isomorphism problem for biautomatic groups.

A separate and very important thread of influence is how the theory of automatic groups stoked interest in certain classes of quasi-isometry invariants. Gromov had already proved that hyperbolicity of a group is equivalent to linearity of the Dehn function (the isoperimetric function). One of the big applications of an automatic structure is Thurston's theorem that an automatic group has a quadratic (or better) Dehn function, which combined with the theorem that every subquadratic Dehn function is actually linear proves that nonhyperbolic automatic groups have quadratic Dehn functions on the nose. Thurston's proof of the quadratic upper bound introduced the concept of a combing of a group, and this led to a whole industry of studying different classes of combings, and the upper bounds they impose on the Dehn function. I particularly like the proof by Hatcher and Vogtmann finding an exponential upper bound to the Dehn function of $Out(F_n)$, which proceeds by finding a quite broadly stretched (pun intended) combing for $Out(F_n)$. Finding bounds on Dehn functions, and pinning down exact Dehn functions can be far from obvious, e.g. Robert Young's proof that $SL(n,Z)$ has quadratic Dehn function for $n \ge 5$, and the proof by Handel and myself of the exponential lower bound for the Dehn function of $Out(F_n)$. The issue of lower bounds is not particularly connected to automatic groups in any mathematical sense, but the historical connection is what I am trying to emphasize. Combings and Dehn functions have continued to grow from these and various seeds, and although I don't want to overstate the particular influence of Thurston's theorem in this context, nonetheless it is (besides Gromov's) one of the earliest concrete computations of Dehn functions.

Answer 2

My own interest in automatic groups has been principally algorithmic, and I believe that this was Thurston's original motivation for studying them - they provided a method for carrying out practical computations in a variety of interesting groups with negative curvature. Once a (geodesic) automatic structure has been computed, you can compute the growth function of the group (this was of particular interest to Thurston), you can reduce words to normal form rapidly, you can usually compute the orders of elements, you can solve the membership problem for quasiconvex subgroups, and so on.

It is true that research into the theory of automatic groups has to some extent ground to a halt, because the remaining open problems seem very hard. For example, there are very few techniques for proving that a group is not automatic, particularly if it has quadratic Dehn function. Although nobody seems to believe that all automatic groups are biautomatic, people seem to have given up on trying to find an example.

But, for a simple computational group theorist like myself, the wonderful thing is that, if you are given a group defined by a finite presentation, then you do not need to know in advance whether the group defined is automatic. You can just run the programs and try and prove that it is. Informally, this results from the nice property of finite state automata, that you can often construct other automata that prove that your original automata do what they are supposed to do - in this case, prove that they define an automatic structure of the group. Of course, for many groups (such as non-automatic groups!) this won't work, but it usually becomes clear very quickly if the programs are not going to work, because the fellow-travelling property of automatic groups appears not to hold.

There have been several examples of groups for which it was not known whether they were finite or infinite, which were proved infinite using the automatic groups programs. One such was the Heineken group defined by the presentation

$$\langle x,y,z | [x,[x,y]]=z, [y,[y,z]]=x, [z,[z,x]]=y \rangle$$

which had been open for many years, as a candidate for a finite group with a balanced presentation. It turned out that it was infinite, and word-hyperbolic. (Incidentally, this seems to me to be a possible counterexample to the suggestion that all hyperbolic groups might be residually finite, but I have no idea how to go about investigating that.)

Other examples are proofs that some of the groups in families defined by Coxeter are infinite, such as members of the family

$$(l,m,n;q) = \langle x,y \mid x^l=y^m=(xy)^n=[x,y]^q=1 \rangle.$$

A year or two ago, with the help of a large and difficult computation, we managed to prove that $(3,5,7;2)$ is automatic and infinite. There are now only three groups in this family that remain to be resolved.

Answer 3

My (admittedly subjective) take on it that development of mathematics is driven by proofs of hard theorems and (in most cases linked to it) development of new technique. Just think of, say, Mostow Rigidity Theorem, Gromov's Polynomial Growth theorem or Rips work on group actions on trees, Thurston/Perelman Geometrization theorems, etc. Most "easy" results in AGT were proven by early 1990s; hard problems are still there, it is just that none of them were solved (not for the lack of trying) and no new technique was introduced (also not for the lack of trying). So, people moved onto something else.

Edit: My feeling for the first question (historic role) is the same as Zhou Enlai's about French Revolution. (The entire field is way too unsettled.) However, if you were to press me for a definition answer I'd say "not particularly significant so far". The key reason: Lack of truly deep theorems/powerful techniques. All this, of course, might suddenly change if one finds a way to bring, say, number theory (or ergodic theory, or model theory, or nonlinear PDEs...) into the picture, addressing, say, the problem of automaticity of uniform lattices of higher rank.