21
$\begingroup$

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...

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ I think that lots of people know about automatic groups; certainly I spent lots of time with ECHLPT in grad school. But the remaining open questions are really hard, so not too many people are actively working on them. That happens to a lot of subjects. Eventually someone will come along with a big idea and the subject will start moving again... $\endgroup$
    – Andy Putman
    May 10, 2013 at 22:33
  • $\begingroup$ Thank you for the comment, I suspected this. I still feel is a bit underrated now. I m very still very curious about my first question... $\endgroup$
    – Dan Sălăjan
    May 10, 2013 at 23:00

3 Answers 3

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you for answering the original question by giving concrete instances where AG infuenced the development of GGT. (I also accept the answer, especially that it leads to the awards of two badges) $\endgroup$
    – Dan Sălăjan
    May 13, 2013 at 21:11
17
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Out of curiosity, are there specific groups which specialists suspect would separate biautomatic from automatic? $\endgroup$
    – Dan Sălăjan
    May 11, 2013 at 12:49
  • 1
    $\begingroup$ I am not aware of any specific examples at present. Many such examples in the past have turned out not to work, which may explain why people have given up! $\endgroup$
    – Derek Holt
    May 11, 2013 at 13:28
  • $\begingroup$ I did not know about Heineken group: Its presentation looks awfully similar to the one of Higman group, which is probably why it could be a candidate for the failure of residual finiteness (since Higman group has no nontrivial finite quotients). $\endgroup$
    – Misha
    May 11, 2013 at 14:50
8
$\begingroup$

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.

Improve this answer
$\endgroup$
17
  • 1
    $\begingroup$ @Misha : I largely agree with you on the significance of automatic group theory within geometric group theory. But they do have a few triumphs. For instance, I know of no proof that mapping class groups have quadratic isoperimetric inequalities that does not use Mosher's theorem they they are automatic (or at least its proof). $\endgroup$
    – Andy Putman
    May 11, 2013 at 0:14
  • 1
    $\begingroup$ Andy: I agree on Mosher's theorem, to which I would add biautomaticity of compact 3-manifold groups (not containing Sol and Nil components), which is the only way I know how to solve conjugacy problem for such groups. Still, none of the results was a "game-changer" (I hope, Lee will not get offended). Game-changing results (almost only) happen in GGT when one brings some "outside" tools. I might have forgotten something, but the only counter-example to this rule I can think of is the work of Wise. $\endgroup$
    – Misha
    May 11, 2013 at 0:28
  • 2
    $\begingroup$ Misha - a small correction. Fundamental groups of non-geometric 3-manifolds (graph manifolds, say) are known to be automatic but not known to be biautomatic. Therefore, this is not how you solve the conjugacy problem in this setting. The conjugacy problem was solved by Préaux. You can also deduce it from the fact that 3-manifold groups are conjugacy separable (Hamilton--W--Zalesskii), though unlike Préaux's work this uses some heavy machinery: Wise's deep work, and a very nice theorem of Minasyan. $\endgroup$
    – HJRW
    May 11, 2013 at 13:13
  • 3
    $\begingroup$ @Dan: I think that the class of automatic groups may be much wider than the class of CAT(0)-groups. For example, it is quite possible that the R. Thompson group $F$ is automatic (as was conjectured by Rips about 20 years ago). $\endgroup$
    – user6976
    May 12, 2013 at 0:14
  • 3
    $\begingroup$ There are three pieces of evidence that $F$ is automatic: it is $FP_\infty$ (Brown and Geoghegan), has a regular set of normal forms (Guba and myself), and has quadratic Dehn function (Guba). $\endgroup$
    – user6976
    May 12, 2013 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.