Non-positively curved groups III – combable, automatic, semi-hyperbolic, and all that

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 ${X}$ is convex. We now turn to what this means for a group ${\Gamma}$ which acts properly cocompactly by isometries on ${X}$ .

We fix a base point ${x_0 \in X}$ . For ${\gamma \in \Gamma}$ , a geodesic from ${x_0}$ to ${\gamma x_0}$ can be carried into a Cayley graph ${C_A(\Gamma)}$ 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 ${1}$ to ${\gamma}$ , or equivalently a word ${\sigma_{\gamma}}$ on ${A^{\pm 1}}$ representing ${\gamma}$ . This gives us a family of quasi-geodesic words ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ representing the elements of ${\Gamma}$ . It is convenient to write ${t \mapsto \sigma_{\gamma}(t)}$ for the path — that begins at the identity at ${t=0}$ and then travels at constant speed until reaching the end of the path at ${\gamma}$ , where it stops.

Recall that convexity of the metric concerns pairs of geodesics ${c_1, c_2}$ in ${X}$ . In the special case where those geodesics begin at the same place — that is, ${c_1(0) = c_2(0)}$ — it implies that there exists ${k>0}$ such that for all ${\gamma, \gamma' \in \Gamma}$ , and for all ${t \geq 0}$ ,

$\displaystyle d(\sigma_{\gamma}(t), \sigma_{\gamma'}(t))) \ \leq \ k d(\gamma, \gamma')$

— see the diagram below. Equivalently, for all ${\gamma \in \Gamma}$ and ${a \in A^{\pm1}}$ , we have ${d(\sigma_{\gamma}(t), \sigma_{\gamma a}(t))) \leq k}$ for all ${t}$ . This condition on ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ is known as ${k}$ –fellow–travelling.

Definition (Combable, combing). A group ${\Gamma}$ with finite generating set ${A}$ is combable when it admits a combing — that is, a ${k}$ –fellow–travelling (for some ${k >0}$ ) family ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ of words on ${A^{\pm1}}$ such that for all ${\gamma \in \Gamma}$ , ${\sigma_{\gamma}}$ represents ${\gamma}$ .

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 ${\Gamma = \langle A \rangle}$ is automatic when it admits a combing such that ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ is a regular language and the ${\sigma_{\gamma}}$ 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:

Open question (attributed to Gersten and to Rips). Is Thompson’s group F automatic?

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 ${\Gamma}$ with finite generating set ${A}$ is bicombable when it admits a bicombing — that is, as before, a family ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ of words on ${A^{\pm1}}$ such that ${\sigma_{\gamma}}$ represents ${\gamma}$ , but this time there is a ${k>0}$ such that they ${k}$ –fellow–travel in this sense: for all ${\gamma \in \Gamma}$ , all ${a, a' \in A^{\pm 1} \cup \{1\}}$ , and all ${t \geq 0}$ ,

$\displaystyle d(a \sigma_{a^{-1}\gamma a'}(t), \sigma_{\gamma}(t))) \ \leq \ k.$

This condition is more natural than it may first appear. The word ${\sigma_{\gamma}}$ describes a path from ${1}$ to ${\gamma}$ in ${C_A(\Gamma)}$ . And ${\sigma_{a^{-1}\gamma a'}}$ describes the path between a pair of points ( ${a}$ and ${\gamma a'}$ ) a distance one or zero from ${1}$ and ${\gamma}$ , respectively. The condition demands that a pair of points travelling along any such ${\sigma_{\gamma}}$ and ${\sigma_{a^{-1}\gamma a'}}$ at unit speed, always remain ${\leq k}$ apart.

If we additionally insist the ${\sigma_{\gamma}}$ 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 ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ in which the ${\sigma_{\gamma}}$ are all quasi–geodesic words.

Hyperbolic groups are semi–hyperbolic: if one takes the ${\sigma_{\gamma}}$ 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 ${\{ \sigma_{\gamma} \mid \gamma \in \Gamma \}}$ 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 ${F_n \rtimes {\mathbb Z}}$ 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).

Open question. (Bridson, Bridson–Vogtmann) Which free–by–cyclic groups ${F_n \rtimes {\mathbb Z}}$ are CAT(0) and which are automatic?

Non-positively curved groups III – combable, automatic, semi-hyperbolic, and all that

About berstein

Leave a comment Cancel reply

Blogroll

Archives

Meta

Non-positively curved groups III – combable, automatic, semi-hyperbolic, and all that

Share this:

Related

About berstein

Leave a comment Cancel reply

Blogroll

Archives

Meta