This post is based, in part, on portions of Martin Bridson’s 2006 ICM article.
As we’ve described, the metric in a CAT(0) space is convex. We now turn to what this means for a group which acts properly cocompactly by isometries on .
We fix a base point . For , a geodesic from to can be carried into a Cayley graph using the quasi–isometry that arrises in the Svarc–Milnor Lemma, as in our previous post. There it manifests as a quasi-geodesic. We tame this quasi–geodesic so that it becomes an edge–path from to , or equivalently a word on representing . This gives us a family of quasi-geodesic words representing the elements of . It is convenient to write for the path — that begins at the identity at and then travels at constant speed until reaching the end of the path at , where it stops.
Recall that convexity of the metric concerns pairs of geodesics in . In the special case where those geodesics begin at the same place — that is, — it implies that there exists such that for all , and for all ,
— see the diagram below. Equivalently, for all and , we have for all . This condition on is known as –fellow–travelling.
Definition (Combable, combing). A group with finite generating set is combable when it admits a combing — that is, a –fellow–travelling (for some ) family of words on such that for all , represents .
As we have already mentioned, in hyperbolic groups, the language of geodesic words is regular — a language of low complexity in the Chomsky hierarchy. Tightening up the combability condition we get:
Definition (Automatic). A finitely generated group is automatic when it admits a combing such that is a regular language and the are all quasi–geodesics.
This class originated in discussions between Jim Cannon and Bill Thurston. Automatic groups allow for particularly efficient calculation. The main reference is the book Word Processing in Groups. There are also helpful surveys in notes by W. Neumann and Shapiro, Gersten’s Banff Notes, and this guided tour by Farb.
Examples. A list of examples of automatic groups from notes by W. Neumann and M. Shapiro (see therein for references): hyperbolic groups, small cancellation groups, fundamental groups of three-manifolds, except for those containing a nil or solv manifold as a connected sum component, Coxeter groups, mapping class groups, braid groups and (more generally) Artin groups of finite type, central extensions of hyperbolic groups, many amalgams of hyperbolic groups along rational subgroups, and many groups that act on affine buildings.
There is a notable absentee from this list:
The combing condition does not fully reflect the convexity–of–the–metric condition as we specialised to the case where the two geodesics begin at the same point. By way of remedy we define:
Definition (bicombable). A group with finite generating set is bicombable when it admits a bicombing — that is, as before, a family of words on such that represents , but this time there is a such that they –fellow–travel in this sense: for all , all , and all ,
This condition is more natural than it may first appear. The word describes a path from to in . And describes the path between a pair of points ( and ) a distance one or zero from and , respectively. The condition demands that a pair of points travelling along any such and at unit speed, always remain apart.
If we additionally insist the are all quasi–geodesic words, we get the class of semi–hyperbolic groups of Alonso and Bridson. These appear to capture much of what it means to be a CAT(0) group in intrinsically group theoretic terms.
Definition (semi–hyperbolic). A finitely generated group is semi–hyperbolic when it admits a bicombing in which the are all quasi–geodesic words.
Hyperbolic groups are semi–hyperbolic: if one takes the to be geodesics, one can use the thin-triangles condition to establish fellow–traveling (Bridson and Haefliger page 473).
Adding regularity to the definition of semi–hyperbolic, we get a class (which also contains all hyperbolic groups):
Definition (biautomatic). A finitely generated group is biautomatic when it is semi–hyperbolic via a family of words which form a regular language.
The fellow-travelling conditions given above are both synchronous — they concern the distance between two points that are both moving along paths at unit speed. They can be relaxed to require only asynchronous fellow–travelling: the points can make their way stutteringly along their respective paths, one advancing whilst the other pauses and then vice versa. This leads to the notions of asynchronously combable, asynchronously bicombable, asynchronously automatic, and asynchronously biautomatic.
Distinguishing classes of non–positively curved groups
Bridson has given examples of groups that are combable but not automatic and others that are combable but not bicombable. In the first case the obstruction lies in the Dehn function. In the second it lies in the structure of the centralizers of certain subgroups. We’ll say something about these obstructions in forthcoming posts. [Bridson writes that Bestvina and Brady have also outlined a construction of a non–automatic combable group.] Mapping class groups are automatic but not CAT(0) — Mosher.
As indicated on Bridson’s map in our first post, a number of classes remain to be distinguished. In particular:
Open question. (attributed to Gersten) Are all automatic groups biautomatic?
Mapping class groups (which are automatic as we just mentioned) are a test case:
Open question. Are mapping class groups biautomatic?
Another outstanding issue concerns the impact of the regularity of the language in the definition of (bi)automaticity.
Open questions. Are all semi–hyperbolic groups automatic (or, better, biautomatic)? Are all automatic (or, indeed, biautomatic) groups semi–hyperbolic?
Bridson suggests that free–by–cyclic groups are a good testing ground for comparing different classes of non–positively curved groups. There are examples of Brady, Bridson and Reeves (unpublished) that are not automatic and others of Gersten that are not CAT(0).