Regular path systems and (bi)automatic groups.

Jacek Świa̧tkowski *

Instytut Matematyczny, Uniwersytet Wrocławski pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland

Running headline: Regular path systems and (bi)automatic groups

Abstract

We develop a new method of proving that groups acting on various classes of spaces are automatic or biautomatic. We apply this method to buildings, CAT (0) cubical complexes, 6-systolic simplicial complexes and Cayley graphs of groups acted upon by other groups.

Keywords: automatic group, biautomatic group, building, wreath product.

AMS MSC (2000): 20F65, 20F10, 57S30.

Introduction

Few systematic methods are known to derive the fact that a group acting on a space is automatic (or biautomatic) out of the properties of the space. One of them, used for example in the context of CAT (0) cubical complexes in [NR1] and in the context of Euclidean buildings in [N], is the method of automatic (or biautomatic) fundamental grupoids. However, this method is limited to the case of free actions only. To deal with actions that allow nontrivial, though finite, stabilizers one would like to have some orbispace analogue of this method, which seems to be not yet developed.

In this paper we present a method as desired above. It is based on the newly introduced notions of automata over graphs and regular path systems in graphs and other spaces. The main tool of this method, Theorem 1.1 of Section 1, allows to conclude that a group acting on a space properly discontinuously and cocompactly is automatic (or biautomatic) if there is an appropriate regular path system in the space. The details and proofs related to the method are presented in Sections 1-3.

As an addition to the above method we present also a (less inventive) idea of local recognition for paths in a space, proving that locally recognized path systems are regular (Section 7). This idea, implicitely present in the proofs in [GS2], [NR1] or [N], allows to establish automaticity (or biautomaticity) of some groups in purely geometric terms, as formulated in Corollary 7.2.

Using the method of this paper we prove new results in several directions. First, we extend some previously known results to bigger classes of groups, by relaxing assumption that a group acts freely to assumption that it acts properly discontinuously (Subsections 8.1 and 8.3). Second, we show that groups acting properly discontinuously and cocompactly

* Partially supported by the Polish State Committee for Scientific Research (KBN) grant 2 P03A 017 25. on so called 6-systolic simplicial complexes (introduced in [JS], being sort of simplicial analogues of CAT (0) cubical complexes) are biautomatic (Subsection 8.2). Third, we prove that type-preserving groups acting in some natural way on arbitrary buildings are automatic, and discuss a sufficient condition for them to be biautomatic (Section 6). Finally, we give a sufficient condition for a finite semidirect extension of a biautomatic group to be biautomatic (Section 4, Corollary 4.5), and use it to prove that the wreath product of a biautomatic group by a finite group is biautomatic (Section 5). We also prove that if quotient of a group by a finite normal subgroup is biautomatic then the group is also biautomatic (Section 4, Corollary 4.3).

As a curiosity, we present (in Subsection 8.4) an alternative proof of the well known fact that any Gromov hyperbolic group is biautomatic, based on the ideas developed in the paper.

1. Automata over graphs and regular path systems.

In this section we introduce the basic new notions of the paper and formulate the main technical result (Theorem 1.1). The proof of this result is given in Section 3, and uses the construction presented in Section 2.

Let X be a (finite or infinite) connected 1-dimensional cell complex. For brevity, we will refer to X as a graph, but the reader should remember that loops and multiple edges are admitted. Denote by E_{X} the set of all oriented edges in X. Given e ∈ E_{X}, denote by i(e) and t(e) the initial and the terminal vertex of e (which coincide if e is a loop). Denote also by e^{−1} the edge e with reversed orientation. Denote by V_{X} the set of all vertices in X.

A path in X is a sequence e_{1}, …, e_{n} (of arbitrary finite length n > 0) of oriented edges such that t(e_{i}) = i(e_{i+1}) for i = 1, …, n − 1. We say that this path goes from i(e_{1}) to t(e_{n}). Denote by P_{X} the set of all paths in X. A path system P in X is any subset of P_{X}.

A directed graph is a graph in which every edge has a distinguished orientation. An automaton is a triple M = (M, S_{0}, S_{Ω}), where M is a (finite or infinite) directed graph, while S_{0}, S_{Ω} ⊂ V_{M} are subsets of the vertex set of M called the sets of start and accept vertices respectively. Vertices of M are traditinally called states. We denote the set of all directed edges in M by D_{M}. The elements of D_{M} are traditionally called arrows. An internal path in an automaton (M, S_{0}, S_{Ω}) is a sequence a_{1}, …, a_{n} of arrows in M such that i(a_{1}) ∈ S_{0}, t(a_{n}) ∈ S_{Ω} and t(a_{i}) = i(a_{i+1}) for i = 1, …, n − 1. We donote the set of all internal paths in (M, S_{0}, S_{Ω}) by P (M, S_{0}, S_{Ω}).

An automaton over a graph X is a quadruple M = (M, m, S_{0}, S_{Ω}) in which (M, S_{0}, S_{Ω}) is an automaton and m : M → X is a nondegenerate simplicial map. The path system P (M) in X consisting of the images through m of all internal paths of (M, S_{0}, S_{Ω}), P (M) = {m ∘ γ : γ ∈ P (M, S_{0}, S_{Ω})}, is called the path system induced (or recognized, or accepted) by M. An automaton M over X is finite-to-one if the preimage by m of any vertex in V_{X} is finite.

An automorphism of a graph X is a bijection of the set E_{X} ∪ V_{X} that preserves the relations of being the initial and the terminal vertex of an oriented edge, as well as the relation of being the edge with reversed orientation. Suppose G is a group acting on X by automorphisms. An automaton over (X, G) is an automaton M = (M, m, S_{0}, S_{Ω}) over X equipped with an action of G on M (by automorphisms which respect the distinguished orientations on edges) satisfying the following properties:

(1) the sets S_{0} and S_{Ω} (of start and accept vertices in M respectively) are G-invariant;

(2) the map m : M → X is G-equivariant, i.e. m(g · v) = g · m(v) for any v ∈ V_{M} and any g ∈ G.

The action of G on X induces the action of G on the set P_{X} of all paths in X given by g · (e_{1}, …, e_{n}) = (ge_{1}, …, ge_{n}). In particular, this allows to speak of G-invariant path systems in X. Observe that if M is an automaton over (X, G) then the induced path system P (M) is G-invariant. A G-invariant path system P in X is regular if there is a finite-to-one automaton M over (X, G) such that P = P (M).

Given a path γ = (e_{1}, …, e_{n}) in X, put γ(0) = i(e_{1}), γ(j) = t(e_{j}) for 1 ≤ j ≤ n and γ(j) = t(e_{n}) for j > n. Put also γ(∞) = t(e_{n}). Denote by d_{X} the metric on the vertex set V_{X} given by the minimal number of edges in a path connecting vertices. A path system P is said to satisfy the fellow traveller property if there are constants C > 0 and D > 0 such that for any two paths γ_{1}, γ_{2} ∈ P with γ_{1}(0) = γ_{2}(0) we have for all natural j

d_{X}(γ_{1}(j), γ_{2}(j)) ≤ C · d_{X}(γ_{1}(∞), γ_{2}(∞)) + D.

A path system P is said to satisfy the 2-sided fellow traveller property if there are constants C > 0 and D > 0 such that for any two paths γ_{1}, γ_{2} ∈ P we have for all natural j

d_{X}(γ_{1}(j), γ_{2}(j)) ≤ C · max[d_{X}(γ_{1}(0), γ_{2}(0), d_{X}(γ_{1}(∞), γ_{2}(∞))] + D.

Given a subset W ⊂ V_{X}, we say that a path system P in X is transitive on W if for any two distinct vertices v, w ∈ W there is a path in P from v to w.

The main new idea of this paper is contained in the following.

1.1 Theorem. Suppose a group G acts on X by automorphisms properly discontinuously and cocompactly. Suppose P is a path system in X satisfying the following properties:

(1) P is G-invariant and regular;

(2) there is v_{0} ∈ V_{X} such that each path in P starts and terminates at vertices from the orbit G(v_{0}) and P is transitive on G(v_{0});

(3) P satisfies the fellow traveller property. Then G is automatic. Moreover, if instead of (3) P satisfies the 2-sided fellow traveller property then G is biautomatic.

Note that in the above theorem we do not assume the action of G on X to be rigid or effective. Note also that the assumptions imply that the graph X is (uniformly) locally finite.

2. Fibered product.

In this section we present a usefull construction of automata over graphs by means of the operation of fiber product. We will apply this construction often in the next sections.

Let f : Y → X be a nondegenerate cellular map between graphs, and let M = (M, m, S_{0}, S_{Ω}) be an automaton over X. A fibered product of M by f is an automaton M^{f} = (M^{f}, m^{f}, S_{0}^{f}, S_{Ω}^{f}) over Y defined as follows. As the vertex set in M^{f} take

V_{M^{f}} = {(u, s) ∈ V_{Y} × V_{M} : f(u) = m(s)}.

The set of directed edges in M^{f} consists of all objects of form b = [e, a], with e ∈ E_{Y}, a ∈ D_{M} and f(e) = m(a) (as oriented edges), where we put i(b) = (i(e), i(a)) and t(b) = (t(e), t(a)). Clearly, the fibred product graph M^{f} is equipped with canonical nondegenerate maps π_{Y} : M^{f} → Y and π_{M} : M^{f} → M (induced by the projections of V_{Y} × V_{M} and E_{Y} ×D_{M} onto factors), where π_{M} respects the distinguished orientations of directed edges. We then take m^{f} = π_{Y}, S_{0}^{f} = π_{M}^{−1}(S_{0}) and S_{Ω}^{f} = π_{M}^{−1}(S_{Ω}).

To describe properties of fibered product automata we need some preparations. Given a nondegenerate cellular map f : Y → X and a path γ in X, a lift of γ through f is a path γ̃ = (e_{1}, …, e_{n}) in Y such that f ∘ γ̃ = γ, where f ∘ γ̃ = (f(e_{1}), …, f(e_{n})). Note that in general γ may have many distinct lifts (e.g. when f is a covering), as well as no lift at all. Given a path system P in X, we denote by P^{f} the set of all lifts through f of all paths in P. By the construction of the fibered product automaton we obviously get the following.

2.1 Fact. Let f : Y → X be a nondegenerate cellular map between graphs and let M be an automaton over X. Then the fibered product automaton M^{f} has the following properties.

(1) The path system P (M^{f}) coincides with the lifted path system P (M)^{f}.

(2) If M is finite-to-one then so is M^{f}.

If M is an automaton over (X, G) and a cellular nondegenerate map f : Y → X is Gequivariant (with respect to some fixed actions of G on X and Y by automorphisms) then the fibred product graph M^{f} carries the natural G-action given by g · (u, s) = (g · u, g · s) and g ·[e, a] = [g ·e, g ·a]. The map m^{f} : M^{f} → Y is clearly equivariant with respect to this action, and the sets S_{0}^{f}, S_{Ω}^{f} are G-invariant, so the fibred product M^{f} is an automaton over (Y, G). These observations together with Fact 2.1 imply the following.

2.2 Fact. Let f : Y → X be a G-equivariant nondegenerate cellular map between graphs X, Y acted upon by a group G (by automorphisms) and let P be a G-invariant and regular path system in X. Then the lifted path system P^{f} in Y is G-invariant and regular.

3. Proof of Theorem 1.1.

The proof will proceed as follows. We shall first describe a suitable finite set A of semigroup generators for the group G. We will call them Shreier generators because of some analogy with the Schreier generators for a subgroup. Next, we shall describe a language L over A derived in a natural way from the path system P. The facts that this language surjects on G and satisfies fellow traveller property will follow easily from the construction. To prove that the language is regular, we shall first construct, out of a finiteto-one G-equivariant automaton for P, an infinite automaton M for L with a cocompact action of G. A finite state automaton for L will be then the quotient automaton G\M.

3.1. Schreier generators for G.

Fix a set V_{0} of representatives of G-orbits in the vertex set V_{X}, so that the vertex v_{0} as in the theorem is contained in V_{0}. For each v ∈ V_{X} denote by v̄ the representative of the G-orbit containing v and put Λ_{v} = {g ∈ G : gv̄ = v}.

3.1.1 Fact. Λ_{v} = g · Gv̄ for any g ∈ Λ_{v}, where Gv̄ is the stabilizer of G at v̄.

For an oriented edge e ∈ E_{X} with i(e) = v_{1} and t(e) = v_{2} put Λ_{e} = Λ_{v_{1}}^{−1} · Λ_{v_{2}}.

3.1.2 Lemma. (1) For any e ∈ E_{X} we have Λ_{e^{−1}} = Λ_{e}^{−1}.

(2) For any e ∈ E_{X} and any g ∈ G we have Λ_{ge} = Λ_{e}.

(3) The set

A := G_{v_{0}} ∪ ⋃_{e∈E_{X}} Λ_{e}

is a finite symmetric set generating G as a semigroup.

Proof: Part (1) is obvious and part (2) follows easily from Fact 3.1.1. Since the action of G on X is properly discontinuous, the stabilizers of vertices are finite. It follows from the same Fact 3.1.1 that the sets Λ_{v}, and hence also the sets Λ_{e}, are all finite. Since the action of G on X is cocompact, it follows from (2) that there are only finitely many different sets among Λ_{e} and, since they are finite, the set A is finite too. The fact that A is symmetric follows easily from (1).

It remains to prove that A generates G as a semigroup. Let g ∈ G be arbitrary nontrivial element. We need to express g in terms of elements from A. We may assume that gv_{0} ≠ v_{0}, since otherwise g ∈ G_{v_{0}} ⊂ A. By connectivity of the graph X, there is a path γ = (e_{1}, …, e_{n}) from v_{0} to gv_{0}. Put v_{i} = t(e_{i}) for i = 1, …, n and note that v_{n} = gv_{0}. For each 0 ≤ i ≤ n − 1 choose arbitrarily an element g_{i} ∈ Λ_{v_{i}}, denote g_{n} = g ∈ Λ_{v_{n}}, and put λ_{j} = g_{j−1}^{−1}g_{j} for 1 ≤ j ≤ n. We then have g_{0} ∈ Λ_{v_{0}} = G_{v_{0}} (because v_{0} ∈ V_{0}), λ_{j} ∈ Λ_{e_{j}} and g = g_{0}λ_{1} … λ_{n}, hence the lemma.

3.2 The language L over A.

Let L be the set consisting of all one-letter strings g with g ∈ G_{0} and all strings of form g_{0}λ_{1} … λ_{n} as in the proof of Lemma 3.1.2 above, for all paths γ ∈ P started at v_{0}, and for all choices of g_{i} ∈ Λ_{v_{i}} as in this proof. In other words, the language L consists of all strings α_{0} … α_{n} over A for which α_{0} ∈ G_{v_{0}} and, denoting g_{i} = α_{0} … α_{i} ∈ G, the sequence of vertices g_{i} · v_{0} for 0 ≤ i ≤ n corresponds to a path γ ∈ P started at v_{0}.

3.2.1 Lemma.

(1) The evaluation map from the language L to G is surjective.

(2) L satisfies the same variant of fellow traveller property as P does.

Proof: Part (1) follows from the fact that the path system P connects v_{0} to any other vertex of the orbit G(v_{0}).

To prove (2), observe that, since G acts on X properly discontinuously, the map q(g) = gv_{0} from G to X is a quasiisometry. Observe also that a path in the Cayley graph C(G, A) induced by a string of form g_{0}λ_{1} … λ_{n}, after mapping it to X through q, is universally uniformly close to the path γ ∈ P from which this string was obtained (because the set V_{0} of representatives is finite). This induces the corresponding variant of the fellow traveller property from P to L.

For the proof that the language L is regular we will need the following.

3.2.2 Lemma. If g_{0}λ_{1} … λ_{n} ∈ L, then for any g′_{0} ∈ G_{v_{0}} we have g′_{0}λ_{1} … λ_{n} ∈ L.

Proof: Let g_{i} = g_{0}λ_{1} … λ_{i} for 0 ≤ i ≤ n. Then the sequence v_{i} = g_{i} · v_{0} corresponds to a path γ ∈ P. Let g′_{0} = hg_{0}, where h ∈ G_{v_{0}}. Putting g′_{i} = g′_{0}λ_{1} … λ_{n} we have g′_{i} = hg_{i} for 0 ≤ i ≤ n. This means that the sequence of vertices g′_{i} · v_{0} = h · g_{i} · v_{0} = h · v_{i} corresponds to the path h · γ. Since h ∈ G_{v_{0}}, we have h · v_{0} = v_{0}, so the path h · γ starts at v_{0}. By G-invariance of the path system P, we have h · γ ∈ P. This shows that g′_{0}λ_{1} … λ_{n} ∈ L, as required.

Consider the language L′ consisting of all substrings λ_{1} … λ_{n} in the strings of L obtained by deleting the first letter g_{0}. Then, according to Lemma 3.2.2, L can be reconstructed from L′ by adding at the beginning of any string from L′ (including the nullstring) any letter g ∈ G_{v_{0}}. Clearly, to prove that L is regular it is sufficient to prove that L′ is regular.

3.3 Infinite automaton M′ for L′.

Recall that an automaton over an alphabet is an automaton whose directed edges a are assigned with labels μ(a) from the alphabet. The language induced by an automaton over an alphabet is the set of strings of form μ(a_{1}) … μ(a_{n}) for all internal paths a_{1} … a_{n} in the automaton.

Let Y be the graph defined as follows. The vertex set V_{Y} is the set of pairs (v, g) ∈ V_{X} × G with g ∈ Λ_{v}, where we have the maps π_{X} : V_{Y} → V_{X} and π_{G} : V_{Y} → G induced by the projections of V_{X} × G onto factors. The set E_{Y} of oriented edges consists of all objects [u_{1}, u_{2}, e] ∈ V_{Y} × V_{Y} × E_{X} for which π_{X}(u_{1}) = i(e) and π_{X}(u_{2}) = t(e), where we have i([u_{1}, u_{2}, e]) = u_{1}, t([u_{1}, u_{2}, e]) = u_{2} and [u_{1}, u_{2}, e]^{−1} = [u_{2}, u_{1}, e^{−1}].

We define the map f : Y → X as the extension of the map π_{X} given by f([u_{1}, u_{2}, e]) = e. Clearly, this defines a nondegenerate cellular map between graphs. Note that the construction of Y and f easily implies the following.

3.3.1 Fact. Let γ be a path in X and let x_{0}, …, x_{n} be the corresponding sequence of vertices in X. Then a sequence (u_{0}, g_{0}), …, (u_{n}, g_{n}) of vertices in Y corresponds to a lift of γ to Y through f iff u_{i} = x_{i} and g_{i} ∈ Λ_{x_{i}} for 0 ≤ i ≤ n.

Another interesting property of graph Y is that it carries the natural action of G by automorphisms, given by

h · (v, g) = (h · v, hg) and h · [u_{1}, u_{2}, e] = [h · u_{1}, h · u_{2}, h · e].

Moreover, the maps f : Y → X and π_{G} : V_{Y} → G are G-equivariant with respect to this action. This, together with Fact 3.3.1, implies the following.

3.3.2 Fact. If γ ∈ P then a sequence (u_{0}, g_{0}), …, (u_{n}, g_{n}) of vertices in Y corresponds to a lift of γ to Y through f iff, in addition to the conditions as in Fact 3.3.1, the string λ_{1} … λ_{n} obtained from the sequence g_{0}, …, g_{n} by putting λ_{i} = g_{i−1}^{−1}g_{i} for 1 ≤ i ≤ n belongs to the language L′.

Proof: By Fact 3.3.1, the assertion is true for all paths γ ∈ P started at v_{0}. For other paths γ ∈ P this follows from G-invariance of the lifted path system P^{{}, and the fact that each γ ∈ P starts, up to a G-translate in X, at v_{0} (this follows from assumption (2) in Theorem 1.1).

Let M = (M, m, S_{0}, S_{Ω}) be a finite-to-one automaton over (X, G) with P (M) = P. Then the fibered product automaton M^{f} = (M^{f}, m^{f}, S_{0}^{f}, S_{Ω}^{f}) is a finite-to-one automaton over (Y, G). Moreover, since the path system induced by M^{f} coincides with the lifted path system P^{f} (Fact 2.1(1)), the paths in this system satisfy the properties as in Fact 3.3.2.

We now modify the automaton M^{f} over (Y, G) to an automaton over the alphabet A by replacing the map m^{f} : M^{f} → Y with the label function μ : D_{M^{f}} → A given by μ(a) = π_{G}(i(m^{f}(a)))^{−1}π_{G}(t(m^{f}(a))).

3.3.3 Fact. The induced language for the automaton M′ coincides with L′.

Proof: Note first that, by G-invariance of the maps m^{f} and π_{G}, the labelling μ on the set D_{M^{f}} projects through m^{f} to the labelling on the set of those oriented edges in Y which are in the image of D_{M^{f}} through m^{f}. We denote this labelling also by μ. It follows that the language induced by M′ coincides with the set of strings μ(e_{1}) … μ(e_{n}) for all paths (e_{1}, …, e_{n}) ∈ P^{f} = P (M^{f}). Since, denoting i(e_{i}) = (u_{i−1}, g_{i−1}) and t(e_{i}) = (u_{i}, g_{i}), we have μ(e_{i}) = g_{i−1}^{−1}g_{i}, the fact follows from Fact 3.3.2.

3.4 Finite state quotient automaton G\M′.

Start with the following observation, which follows directly from the definition of μ and from G-equivariance of the maps m^{f} and π_{G}.

3.4.1 Fact. Let M′ = (M^{f}, μ, S_{0}^{f}, S_{Ω}^{f}) be the automaton over the alphabet A described in Subsection 3.3 above. Then the action of G on M^{f} has the property that μ(g ·a) = μ(a) for any a ∈ D_{M^{f}} and any g ∈ G.

Consider the quotient automaton (G\M^{f}, G\S_{0}^{f}, G\S_{Ω}^{f}) and note that, due to Fact 3.4.1, the label function μ induces the label function on the set D_{G\M^{f}}, which we denote also by μ. Thus, we get the quotient automaton G\M = (G\M^{f}, μ, G\S_{0}^{f}, G\S_{Ω}^{f}) over the alphabet A.

The proof that the language L′ (and hence also the language L) is regular will be completed with the proof of the following.

3.4.2 Lemma.

(1) The set of internal paths in G\M^{f} coincides with the set of images of the internal paths in M^{f} through the quotient map M^{f} → G\M^{f}.

(2) The language induced by G\M^{f} coincides with the language L′.

(3) G\M^{f} is a finite state automaton, i.e. it contains finitely many vertices.

Proof: Observe that the action of G on the vertex set of the graph Y is free, and hence the action on the vertex set of the fiber product M^{f} is also free. The quotient map M^{f} → G\M^{f} is then a covering, hence (1). In view of Fact 3.3.3, (2) follows from (1). To prove (3), observe that, by cocompactness, the action of G on the vertex set of X has finitely many orbits. Choose a set X_{0} of representatives of these orbits. Then any orbit of the G-action on the vertex set of Y has a representative of form (v, g) with v ∈ X_{0}. Since for any fixed v ∈ X_{0} the number of such representatives with this v is finite (bounded by the cardinality of the finite set Λ_{v}), it follows that G has finitely many orbits in its action on V_{Y}. Again, choose a set Y_{0} of representatives of these orbits, and note that any G-orbit in the vertex set of the fiber product M^{f} has a representative of form (y, s) ∈ V_{Y} ×V_{M} with y ∈ Y_{0}. But the automaton M^{f} inherits from the automaton M the property of being finite-to-one (see Fact 2.1(2)), and hence there are finitely many orbits of the G-action on the vertex set of M^{f}. This implies that the quotient has finitely many vertices, which finishes the proof.

Regularity of L, together with Lemma 3.2.1, imply that the group G is automatic or biautomatic (depending on the version of the fellow traveller property in the assumption), and this completes the proof of Theorem 1.1.

4. Actions on Cayley graphs.

In this section we study Cayley graphs of automatic (respectively biautomatic) groups and the path systems in them induced by the corresponding regular languages in these groups. These path systems are easily seen to be G-invariant, transitive and to satisfy the corresponding version of the fellow traveller property. We show these path systems are also regular (in the sense of Section 1). Then we apply Theorem 1.1 to several classes of groups acting appropriately on such Cayley graphs. At the end of the section we focus attention on finite semidirect extensions of biautomatic groups, preparing background for the results of Section 5.

Let G be a group and A a set of its semigroup generators. The Cayley graph C(G, A) is the directed graph with the vertex set G, in which the set of directed edges is the set of all objects of form [g, ga; a] : g ∈ G, a ∈ A, where i([g, ga; a]) = g and t([g, ga; a]) = ga. This variant of Cayley graph, slightly different from the classical one, is particularly usefull for our purposes in this paper. Note that if the unit element 1 of the group G is in A (which is the case in some situations that we consider), then we have the loop [g, g; 1] at each vertex g in C(G, A). Note also that if a ∈ A has order 2 then there are two distinct edges [g, ga; a] and [ga, g; a] between the vertices g and ga. Obviously, the Cayley graph C(G, A) is equipped with the canonical G-action (by automorphisms which respect the orientations of the edges) given by h · g = hg and h · [g, ga; a] = [hg, hga; a].

Another directed graph that we associate to the pair (G, A), denoted C_{0}(G, A), is the graph consisting of the single vertex and having one directed loop edge e_{a} for each a ∈ A (including e_{1} if the unit 1 is in A). Consider the nondegenerate cellular map q : C(G, A) → C_{0}(G, A) between directed graphs defined by q([g, ga; a]) = e_{a}. Observe that, if we view C_{0}(G, A) as equipped with the trivial G-action, q is G-equivariant. Moreover, the graph C_{0}(G, A) can be identified with the quotient graph G\C(G, A) and the map q with the quotient map C(G, A) → G\C(G, A).

Let L be a language over an alphabet A ⊂ G as above. Denote by P_{L} the path system in the Cayley graph C(G, A) consisting of all paths induced by the strings of the language L and all their left G-translates. More precisely, given a string w = a_{1} … a_{n} over A, put γ_{w} = (e_{a_{1}}, …, e_{a_{n}}) to be the path in C_{0}(G, A). Consider the path system L_{0} in C_{0}(G, A) given by L_{0} = {γ_{w} : w ∈ L}. Define P_{L} to be the path system in C(G, A) lifted from L_{0} through q, i.e. P_{L} := L_{0}^{q}.

4.1 Lemma.

(1) For any language L over A the path system P_{L} is G-invariant.

(2) If the evaluation map from L to G is surjective, then P_{L} is transitive on the vertex set G in C(G, A).

(3) If L is regular then P_{L} is regular;

(4) if (A, L) is an automatic (respectively biautomatic) structure for G then P_{L} satisfies the (respectively 2-sided) fellow traveller property.

Proof: Parts (1) and (2) of the lemma follow easily from the definition of the path system P_{L}. Part (4) follows from the standard characterisation of (bi)automatic structures in terms of paths in Cayley graphs (compare Theorem 2.3.5 and Lemma 2.5.5 in [E+]). To prove part (3), note that a finite automaton M = (M, μ, S_{0}, S_{Ω}) for L can be easily modified to an automaton M_{0} = (M, m, S_{0}, S_{Ω}) over C_{0}(G, A) inducing path system L_{0}. Namely, it is sufficient to define the map m : M → C_{0}(G, A) by m(e) = e_{μ(e)} for each directed edge e in M. According to Lemma 2.1, the path system P_{L} is then induced by the fiber product automaton M_{0}^{q} over C(G, A), which is finite-to-one. This shows that P_{L} is regular, thus finishing the proof.

Lemma 4.1 together with Theorem 1.1 imply the following.

4.2 Corollary. Suppose a group H acts properly discontinuously and cocompactly on the Cayley graph C(G, A) by left G-translates (i.e. by automorphisms from the canonical G-action on C(G, A)).

(1) If G is automatic then H is automatic.

(2) If A is symmetric and G is biautomatic then H is biautomatic.

Proof: There are few things that need a comment. First, recall from [E+] that if G is automatic (respectively biautomatic) and if A is a (respectively symmetric) set of semigroup generators in G, then there is a language L over A such that the pair (A, L) is an automatic (respectively biautomatic) structure for G. We then consider the corresponding path system P_{L} for such a language L.

To apply Theorem 1.1, fix a vertex v_{0} in C(G, A) and consider the path subsystem P ⊂ P_{L} consisting of all paths that start and terminate at a vertex from the orbit H(v_{0}). The subsystem P is clearly H-invariant and inherits the corresponding variant of the fellow traveller property from P_{L}. To see that P is regular, it is sufficient to modify slightly a finite-to-one automaton M over (C(G, A), G) that determines P_{L}. Assuming that M = (M, m, S_{0}, S_{Ω}), we only change the sets S_{0} and S_{Ω}. Namely, we take as the new sets of start and accept vertices the smaller sets S_{0} ∩ H(v_{0}) and S_{Ω} ∩ H(v_{0}) respectively. We skip other obvious details of the argument.

A group H acts on the Cayley graph C(G, A) as in the above corollary iff the action is determined by a homomorphisms H → G with finite kernel and finite index image. The particular cases of this situation happen when

(1) H is a subgroup of finite index in G;

(2) H contains a finite normal subgroup N such that H/N = G. This allows to split Corollary 4.2 into results for the particular cases as above, among which the following seems to be new.

4.3 Corollary. Suppose a group H contains a finite normal subgroup N such that the quotient group H/N is biautomatic. Then H is biautomatic.

We now turn to the case when a group H acts on the Cayley graph C(G, A) not only by left G-translates. In practice, we will be interested in a particular subcase of this case described in the following well known fact.

4.4 Fact. Suppose Q is a finite group acting by (group theoretic) automorphisms on a group G, and suppose that A is a finite Q-invariant set of semigroup generators for G. Consider the induced action of Q on the Cayley graph C(G, A) given by q · g = q(g) and q ·[g, ga; a] = [q(g), q(ga); q(a)]. Then the semidirect product of G by Q acts canonically on the Cayley graph C(G, A), properly discontinuously and cocompactly, by automorphisms that are compositions of the left G-translates and the above described automorphisms from the induced Q-action on C(G, A).

Note that under notation and assumptions as in the above fact, Q acts on the set A, and this induces the action on the monoid A^{∗} of all strings over A given by q · a_{1} … a_{n} = q(a_{1}) … q(a_{n}). We say that a language L over A is Q-invariant if it is invariant with respect to this action. Note that if L is Q-invariant then so is the induced path system P_{L} in the Cayley graph C(G, A). In view of this and Fact 4.4, Theorem 1.1 and Lemma 4.1 imply the following.

4.5 Corollary. Let Q be a finite group of automorphisms of a group G and let (A, L) be an automatic (respectively biautomatic) structure for G. Suppose also that the set A is Q-invariant and the language L is Q-invariant with respect to the induced Q-action on the monoid A^{∗}. Then the semidirect product of G by Q is automatic (respectively biautomatic).

The above corollary is not very exciting in the case of automatic assumption and assertion, since it is well known that if a finite index subgroup is automatic then the ambient group is also automatic. However, the question wheather the same property holds for biautomatic groups remains open. In the next section we answer this question affirmatively for some (rather restricted) class of finite extensions, including the wreath product with a finite group.

5. Wreath product.

In this section we prove, using the methods developed in the previous sections, that the wreath product GwrF of a biautomatic group G by a finite group F is biautomatic. This is in fact a special case of a slightly more general result that we prove.

Recall that the wreath product GwrF (by a finite group F) is the semidirect extension of the direct product G^{k} = G × … × G of k = |F | copies of G by the group F permuting the factors in the product in the same way as F permutes its own elements acting from the left. We start with few rather well known observations concerning the direct product G^{k}.

Let G be a group with biautomatic structure (A, L). Consider the action of the symmetric group S_{k} on G^{k}, by group automorphisms, given by

σ · (g_{1}, …, g_{k}) = (g_{σ(1)}, …, g_{σ(k)}).

Our first aim is to construct an S_{k}-invariant biautomatic structure (A_{k}, L_{k}) on G^{k}.

Put A_{k} := (A ∪ {1})^{k}, where 1 is the unit element in G, and note that this set clearly generates G^{k} as a semigroup. Let L′ be the language over A ∪ {1} consisting of all strings of form α_{1} … α_{n}1 … 1 with α_{1} … α_{n} ∈ L, where the number of the letters 1 at the end is any nonnegative integer. Note that regularity of L easily implies that L′ is also regular. Define the language L_{k} over A_{k} to consist of all strings

(a_{11}, …, a_{1k}) … (a_{n1}, …, a_{nk})

such that a_{1i} … a_{ni} ∈ L′ for each 1 ≤ i ≤ k.

5.1 Lemma. The language L_{k} is regular.

Proof: The reader familiar with many-variable languages and their associated padded extensions ([E+], Section 1.4) can easily realize that the lemma can be proved in the same way as the well known fact that the padded extension of the product language L^{k} = L × … × L is regular (compare [BGSS], Lemma 5.1). For completeness, we sketch this proof here.

Let M = (M, μ, S_{0}, S_{Ω}) be a finite state automaton for the language L′, with the label function μ : D_{M} → A ∪ {1}. Define the automaton M_{k} = (M_{k}, μ_{k}, S′_{0}, S′_{Ω}) over A_{k} as follows. For the vertex set of M_{k} take the product V_{M}^{k} = V_{M} × … × V_{M} and for the set of directed edges the set of objects of form (e_{1}, …, e_{k}) ∈ D_{M} × … × D_{M}, where i((e_{1}, …, e_{k})) = (i(e_{1}), …, i(e_{k})) and t((e_{1}, …, e_{k})) = (t(e_{1}), …, t(e_{k})). Define the label function μ_{k} : D_{M_{k}} → A_{k} by μ_{k}((e_{1}, …, e_{k})) = (μ(e_{1}), …, μ(e_{k})). Finally, put S′_{0} = S_{0}^{k} = S_{0} × … × S_{0} and S′_{Ω} = S_{Ω}^{k} = S_{Ω} × … × S_{Ω}. We leave it as an exercise to check that the language induced by M_{k} coincides with L_{k}. This finishes the proof.

5.2 Lemma. The language L_{k} satisfies the 2-sided fellow traveller property.

Proof: Note that for any two elements g, h ∈ G^{k}, where g = (g_{1}, …, g_{k}) and h = (h_{1}, …, h_{k}), we have d_{C(G^{k},A_{k})}(g, h) = min{d_{C(G,A)}(g_{i}, h_{i}) : 1 ≤ i ≤ k}. Note also that since L satisfies the 2-sided fellow traveller property, the same is true for L′. The above two facts easily imply the lemma.

Above two lemmas and the obvious fact that L_{k} surjects on G^{k} imply that (A_{k}, L_{k}) is a biautomatic structure on G^{k}. It is also clear that this structure is S_{k}-invariant.

5.3 Proposition. Let G be a biautomatic group and F a finite group. Suppose that F acts on the direct product G^{k} in the way induced by a homomorphism φ : F → S_{k}, i.e.

f · (g_{1}, …, g_{k}) = (g_{φ(f)(1)}, …, g_{φ(f)(k)}).

Then the semidirect product of G^{k} by F is biautomatic.

Proof: Let (A, L) be a biautomatic structure in G, and let (A_{k}, L_{k}) be the corresponding S_{k}-invariant biautomatic structure in the direct product G^{k}, as constructed in the first part of this section. Then this structure is also F -invariant, and the proposition follows by applying Corollary 4.5.

Note that if k = |F | and if φ induces the action of F on a set with cardinality k which is isomorphic to the action of F on itself (by left multiplication), then the semidirect product as in the Proposition is (isomorphic to) the wreath product GwrF. Thus we get the following.

5.4 Corollary. If G is biautomatic and F finite then the wreath product GwrF is biautomatic.

6. Groups acting on buildings.

In this section we study groups G acting on buildings by type preserving automorphisms. We show that if an action as above satisfies certain geometrically natural condition (i.e. it is proper discontinuous and cocompact on the Davis’ realization of the building) then the corresponding group G is automatic. We also show that if, in addition to the above assumptions, the Coxeter system (W, S) associated to the building admits a geodesic biautomatic structure (S, L) then the group G is biautomatic.

A building Δ associated to a Coxeter system (W, S) is a simplicial complex of dimension d = |S| − 1 satisfying certain (rather restrictive) list of conditions, for which we refer the reader to [T], [R, Chapter 3.1] or [Br, Chapter IV]. We recall here only some necessary terminology and basic properties of buildings that follow from their definition. The d-dimensional simplices of a building Δ are called chambers and Δ is a chamber complex, i.e. it is the union of its chambers. We denote the set of all chambers in Δ by chamΔ. Two distinct chambers of Δ are adjacent if they share a face of codimension 1 (i.e. of dimension d − 1). A gallery in Δ is a sequence C_{1}, …, C_{n} of chambers in Δ such that any two consecutive chambers in this sequence are disinct and adjacent. All buildings Δ are gallery connected, which means that any two chambers in Δ can be joined by a gallery. Any building Δ admits a (essentially unique, due to gallery connectedness) nondegenerate simplicial map p : Δ → σ_{S}, where σ_{S} is a simplex of dimension d whose codimension one faces are labelled bijectively with the generators s ∈ S of the associated Coxeter system. We will call this map a projection. This map equips all codimension 1 faces in Δ with labels from S, called types, by pulling back the corresponding labels in σ_{S}. Given a face (of any dimension) in Δ, its residue is the set of all chambers that contain this face.

A simplicial automorphism φ of Δ induces bijections of the sets chamΔ and the set of codimansion 1 faces in Δ. We say that φ is type preserving if the induced bijection on the latter set preserves types. We say that the action of a group on Δ by simplicial automorphisms is cofinite if the induced action on the set chamΔ has finitely many orbits.

An automatic or biautomatic structure (A, L) in a group H is geodesic if all paths in the Cayley graph C(H, A) induced by the strings of L are geodesics, i.e. their length is equal to the distance in C(H, A) between their endpoints.

Our main result in this section is the following.

6.1 Theorem. Let Δ be a building with the associated Coxeter system (W, S) and let G be a group acting by simplicial automorphisms on Δ. Suppose that the residues of codimension 1 faces in Δ are finite and that the action of G is type-preserving, cofinite and the stabilizers of chambers are finite. If the group W admits a geodesic automatic (respectively biautomatic) structure (S, L) then G is automatic (respectively biautomatic).

Remark. The assumptions that the residues of codimension 1 faces in Δ are finite, the action of G on Δ is cofinite and the stabilizers of chambers are finite are together equivalent to a geometrically natural condition that G acts properly discontinuously and cocompactly on the so called Davis’ realization of Δ (see [D], Section 10).

Before giving a proof of the above theorem we discuss its consequences and compare them with earlier results from the literature.

Recall that, according to the result of B. Brink and R. Howlett [BHo], each Coxeter group admits a geodesic automatic structure. In view of this, Theorem 6.1 implies the following.

6.2 Corollary. Let G be a group acting by simplicial automorphisms on a building Δ with all residua of faces of codimension 1 finite. Suppose that the action is type-preserving, cofinite and that the stabilizers of chambers are finite. Then G is automatic.

The question wheather any Coxeter group (W, S) admits a geodesic biautomatic structure (S, L) seems to be open. In fact, it is even not known wheather all Coxeter groups are biautomatic (with no further requirements on the structure). Biautomatic structures are known to exist on affine Coxeter groups (see [E+], Section 4.2) and on Coxeter groups that contain only finitely many conjugacy classes of subgroups isomorphic to triangle groups (see [NR2]). The latter class contains all Gromov hyperbolic Coxeter groups and all right angled ones. In general, the known biautomatic structures for the above classes of groups are not geodesic and hence do not satisfy the assumptions of Theorem 6.1. However, the conclusion of Theorem 6.1 for the corresponding classes of buildings is known to be true by other arguments. For example, in the Gromov hyperbolic case, a group G acting on an associated building is also hyperbolic (see [CS] or the final remark in [D]), and as such it is known to be biautomatic. In the right angled case, an associated (right angled) building admits a realization as a CAT (0) cubical complex on which a group G as in Theorem 6.1 acts properly discontinuously and cocompactly (see [D], Remark 9.4). In this case G is known to be biautomatic by the general argument for CAT (0) cubical groups (see [NR] and Section 8.1 of this paper). In both above cases the assertion (that G is biautomatic) remains valid even if we drop the assumption that the action of G is type-preserving.

Except for the above mentioned cases of Gromov hyperbolic and right angled buildings, it is also known that a group G acting freely and cocompactly on a Euclidean building of one of the types Ã_{n}, B̃_{n}, C̃_{n} or G̃_{2} is biautomatic (see [N], [GS2] and [GS3]). Except in the cases Ã_{2} and G̃_{2}, the action of G above is also required to be order preserving (this is slightly weaker than type-preserving, see [N]). The author does not know wheather the corresponding (affine) Coxeter groups have biautomatic structures satisfying the assumptions of Theorem 6.1, but this seems very likely. The existence of such structures would allow to extend the above result beyond the range of free actions. In Section 8.3 we show how to extend this result from free actions to proper discontinuous ones, with all other assumptions unchanged, using a different argument.

Proof of Theorem 6.1.

Define X = X_{Δ} to be a directed graph with the veretex set V_{X} = chamΔ, with the set of directed edges coinciding with the set of all ordered pairs of adjacent chambers. This means that the vertices corresponding to any pair of adjacent chambers are connected by two distinct and oppositely oriented edges. The action of G on Δ induces the action on X, by automorphisms respecting the distinguished orientations on edges. Moreover, under assumptions of Theorem 6.1, this induced action is proper discontinuous and cocompact.

Consider the nondegenerate simplicial map f : X → C_{0}(W, S) between the directed graphs (where C_{0}(W, S) is as in Section 4), defined as follows. For any ordered pair (C_{1}, C_{2}) of adjacent chambers in Δ, with the common face of codimension 1 labelled s, the directed edge corresponding to this pair is mapped on the directed loop edge e_{s} in C_{0}(W, S). It means that the two edges in X between C_{1} and C_{2} are mapped on e_{s} in two opposite ways. Consider the trivial action of G on C_{0}(W, S) and note that, since the action of G on Δ preserves types, the map f is G-equivariant.

Let (S, L) be a geodesic automatic or biautomatic structure in W, and let M = (M, μ, S_{0}, S_{Ω}) be an automaton over S with the induced language L. Consider the modified automaton M_{0} = (M, m, S_{0}, S_{Ω}) over the graph C_{0}(W, S), as described in the proof of Lemma 4.1, and view it as an automaton over (C_{0}(W, S), G), for the trivial action of G on C_{0}(W, S). Consider also the fibered product automaton M_{0}^{f} = (M^{f}, m^{f}, S_{0}^{f}, S_{Ω}^{f}) over (X, G), as defined in Section 2. Denote by P_{0}^{f} the path system in X induced by M_{0}^{f}. By Facts 2.1 and 2.2 we get the following.

6.3 Fact. The path system P_{0}^{f} in X is G-invariant and regular.

To proceed further, we need to recall more terminology related to and more properties of buildings.

Given a Coxeter system (W, S), the Coxeter complex Σ(W, S) is a chamber complex of dimension d = |S| − 1 whose chambers correspond to elements of W, where the chambers correcponding to w_{1}, w_{2} ∈ W are adjacent iff w_{1} = w_{2}s for some s ∈ S. Moreover, there is the projection map p_{W,S} : Σ(W, S) → σ_{S}, which is nondegenerate and such that the common codimension 1 face of any two chambers corresponding to w and ws is mapped to the codimension 1 face of σ_{S} labelled s, for any w ∈ W and any s ∈ S.

If Δ is a building assosiated to a Coxeter system (W, S) then, by definition, it is equipped with a family of subcomplexes isomorphic to the Coxeter complex Σ(W, S), called appartments in Δ. We assume that each appartment Σ is equipped with a distinguished isomorphism Σ → Σ(W, S). For each appartment Σ in Δ, the restriction of the projection map p : Δ → σ_{S} to Σ coincides (or is canonically identified) with the projection map p_{W,S}.

A gallery C_{0}, …, C_{n} in a building or in a Coxeter complex is minimal if there is no shorter (i.e. consisting of less chambers) gallery between C_{0} and C_{n}. In any building, all minimal galleries between any two fixed chambers are contained in a single appartment in this building. Moreover, a gallery in a building is minimal iff it is minimal in any appartment that contains it.

Observe that galleries in the Coxeter complex Σ(W, S) are in one-to-one correspondence with paths in the Cayley graph C(W, S). Moreover, a path in C(W, S) is geodesic iff the corresponding gallery in Σ(W, S) is minimal. Note also that galleries in a building Δ are in one-to-one correspondence with paths in the associated graph X = X_{Δ}. The above observations imply that for any appartment Σ in Δ, and its associated identification with Σ(W, S), we get the corresponding embedding i_{Σ} of the Cayley graph C(W, S) in X, respecting the structure of directed graphs. Furthermore, in view of the above mentioned properties of minimal galleries, i_{Σ} is an isometric embedding (with respect to the path metrics on the corresponding vertex sets).

6.4 Lemma. The path system P_{0}^{f} in X is transitive on V_{X}, i.e. for any two vertices u, v in X there is a path in P_{0}^{f} from u to v.

Proof: Let u, v be any two distinct vertices in X, and C, D the corresponding chambers in Δ. Let Σ be an appartment in Δ containing both C and D (such an appartment exists since Δ is gallery connected and thus has a minimal gallery from C to D, which is contained in a single appartment). Identify Σ with the Coxeter complex Σ(W, S) and then C, D with the corresponding vertices in the Cayley graph C(W, S). Let γ be a path in C(W, S) from C to D corresponding to (a left translate of) a string in L. The projection of γ to C_{0}(W, S) through the map q : C(W, S) → C_{0}(W, S) (as defined in Section 4), i.e. the path q(γ), clearly belongs to the language L_{0} induced by the automaton M_{0}. On the other hand, the image path i_{Σ}(γ) through the isometric embedding i_{Σ} : C(W, S) → X corresponding to Σ is a path in X connecting u to v. Moreover, since we have f ∘ i_{Σ} = q, it follows that i_{Σ}(γ) is a lift of q(γ) through the map f : X → C_{0}(W, S). By Fact 2.1(1) we get that i_{Σ}(γ) ∈ P_{0}^{f}, hence the lemma.

Recall from [R, Property 3.1(iv)] the following property of galleries in Δ.

Property. Let C_{0}, …, C_{n} be a gallery in Δ, and for 1 ≤ i ≤ n let s_{i} be the type of the common codimension 1 face of the chambers C_{i−1} and C_{i}. If the string s_{1} … s_{n} induces a geodesic path in the Cayley graph C(W, S) then the gallery C_{0}, …, C_{n} is minimal.

By the definition of the path system P_{0}^{f}, the above property implies the following.

6.5 Fact. The galleries in Δ corresponding to the paths in X from the path system P_{0}^{f} are all minimal.

6.6 Lemma. The path system P_{0}^{f} satisfies the fellow traveller property. Moreover, if (S, L) is a biautomatic structure then P_{0}^{f} satisfies the 2-sided fellow traveller property.

Proof: We will use the notation concerning the fellow traveller property as in Section 1. Observe that, as for the first part of the lemma, it is sufficient to prove that there is a constant K > 0 such that if γ_{1}, γ_{2} ∈ P_{0}^{f}, γ_{1}(0) = γ_{2}(0) and d_{X}(γ_{1}(∞), γ_{2}(∞)) = 1 then D_{X}(γ_{1}(j), γ_{2}(j)) ≤ K for all natural j.

Let γ_{1}, γ_{2} be paths as above, and let C_{0}, …, C_{n} and D_{0}, …, D_{m} be the corresponding galleries in Δ, which are minimal due to Fact 6.5. By our assumptions on γ_{1}, γ_{2} we have that C_{0} = D_{0} and that the chambers C_{n} and D_{m} are adjacent. Assuming, without loss of generality, that n ≥ m, we consider the following three cases.

Case 1: n > m. Note that D_{0}, …, D_{m}, C_{n} is a gallery from C_{0} to C_{n}. Then, by minimality of C_{0}, …, C_{n}, we have m + 1 ≥ n, hence n = m + 1 and the gallery D_{0}, …, D_{m}, C_{n} is minimal. Let Σ be an appartment containing both minimal galleries D_{0}, …, D_{m}, C_{n} and C_{0}, …, C_{n} from C_{0} = D_{0} to C_{n}, and let i_{Σ} : C(W, S) → X be the corresponding embedding of directed graphs. Since the paths γ_{1}, γ_{2} are in the image of i_{Σ}, we lift them to the paths γ′_{1}, γ′_{2} in C(W, S). By the definition of the path system P_{0}^{f}, the lifts γ′_{1}, γ′_{2} correspond to some strings in the language L, and since this language gives an automatic structure in W, we have

d_{C(W,S)}(γ′_{1}(j), γ′_{2}(j)) ≤ C · d_{C(W,S)}(γ′_{1}(∞), γ′_{2}(∞)) + D,

for some universal constants C, D. Since i_{Σ} is an isometric embedding, this inequality implies that d_{X}(γ_{1}(j), γ_{2}(j)) ≤ C + D for any natural j.

Case 2: n = m and C_{n} = D_{n}. In this case both minimal galleries C_{0}, …, C_{n} and D_{0}, …, D_{n} from C_{0} = D_{0} to C_{n} = D_{n} are contained in a single appartment Σ in Δ. The argument as in the previous case shows that

d_{X}(γ_{1}(j), γ_{2}(j)) ≤ C · d_{X}(γ_{1}(∞), γ_{2}(∞)) + D = D

for any natural j, because γ_{1}(∞) = γ_{2}(∞).

Case 3: n = m and C_{n} ≠ D_{n}. Let σ be the common face of codimension 1 in the adjacent chambers C_{n} and D_{n}, and let R_{σ} denote the residue of σ. By another property of buildings (see [R, Corollary 3.9], [Br, Lemma 1 in Section IV.6] or [T, 3.19]), there is a chamber E in R_{σ} with the gallery distance from C_{0} smaller by 1 than for all other chambers in R_{σ}. It follows that E is distinct from both C_{n} and D_{n} and there is a minimal gallery E_{0}, …, E_{n−1} with E_{0} = C_{0} and E_{n−1} = E. Furthermore, by transitivity of the path system P_{0}^{f} (Fact 6.3) we may assume that the path γ_{0} in X corresponding to the gallery E_{0}, …, E_{n−1} is a path from P_{0}^{f} (because the paths in P_{0}^{f} are geodesic). Applying the arguments as in Case 1 to the pairs γ_{0}, γ_{i} for i = 1, 2 we get

d_{X}(γ_{1}(j), γ_{2}(j)) ≤ d_{X}(γ_{1}(j), γ_{0}(j)) + d_{X}(γ_{0}(j), γ_{2}(j)) ≤ 2C + 2D

for any natural j.

Summarizing, the first part of the lemma follows by putting K = 2C + 2D.

To prove the second part of the lemma, it is sufficient to show the existence of a constant L > 0 such that if γ_{1}, γ_{2} ∈ P_{0}^{f}, γ_{1}(∞) = γ_{2}(∞) and d_{X}(γ_{1}(0), γ_{2}(0)) = 1 then D_{X}(γ_{1}(j), γ_{2}(j)) ≤ L for all natural j. This can be proved in the same way as the first part of the lemma, by referring to the 2-sided fellow traveller property of the path system in C(W, S) determined by the language L.

This finishes the proof of Lemma 6.6.

To complete the proof of Theorem 6.1, it is sufficient to apply Theorem 1.1 to the path system P ⊂ P_{0}^{f} in X consisting of all paths that start and terminate at vertices from the orbit G(v_{0}), for any fixed vertex v_{0} in X. It follows easily from Lemma 6.6 that P satisfies the appropriate variant of the fellow traveller property. Transitivity of P on G(v_{0}) follows from Lemma 6.4. It is also obvious that P is G-invariant. The fact that P is regular follows from Fact 6.3 by modifying an automaton that induces P_{0}^{f} as in the last part of proof of Proposition 7.1. Since P satisfies the assertions of Theorem 1.1, we get that G is automatic (respectively biautomatic), and the theorem follows.

We devote the remaining part of this section to groups that act on buildings not in type-preserving way. An automorphism φ of a building Δ induces a bijection on the corresponding set S of types, and this bijection extends uniquely to an automorphism φ̂ of the associated Coxeter group W. Denote by Sym(W, S) the group of all bijections of S that extend to an automorphism of W, and by Ĝ the image of the homomorphism G → Sym(W, S) given by φ → φ̂.

The proof of Theorem 6.1 as presented above, with obvious minor modifications, gives the following generalization of Theorem 6.1.

6.7 Theorem. Let Δ and G be as in Theorem 6.1, except that we do not assume G is type-preserving, and let Ĝ ⊂ Sym(W, S) be as defined above. If the group W admits a Ĝ-invariant geodesic automatic (or biautomatic) structure (S, L) then G is automatic (respectively biautomatic). In particular, if W admits a Sym(W, S)-invariant geodesic automatic (or biautomatic) structure (S, L) then any group G acting on Δ as above is automatic (respectively biautomatic).

The problem of existence of automatic structures (S, L) in Coxeter groups with additional symmetries, as in the above theorem, seems to be open.

7. Locally recognized path systems.

In this section we introduce a geometric criterion for a path system that implies its regularity. Roughly speaking, we show that a path system consisting of all paths whose local pieces fit to a finite collection of patterns is a regular path system. This result, together with Theorem 1.1, allows to establish in purely geometric terms that groups acting with nontrivial stabilizers on various families of spaces are (bi)automatic.

Let X be a graph acted upon by a group G properly discontinuously and cocompactly. For a path γ = (e_{1}, …, e_{n}) in X, denote by |γ| its length n. For m < n denote by γ|_{m} the prefix path of length m in γ, i.e. the path e_{1}, …, e_{m}. A subpath in γ is a path of form e_{i}, e_{i+1}, …, e_{j} for any 1 ≤ i ≤ j ≤ n.

Paths γ_{1}, γ_{2} in X are G-congruent if there is g ∈ G such that g ·γ_{1} = γ_{2}. Denote by S_{k} the set of G-congruence classes of paths of length k in X and note that, by cocompactness of the G-action on X, S_{k} is finite for any natural k. For any path γ, denote by [γ] ∈ S_{|γ|} its G-congruence class.

For a subset R ⊂ S_{k} let P_{R} be the path system in X consisting of all paths γ satisfying any of the following two conditions:

(1) if |γ| ≥ k then for any subpath η of length k in γ we have [η] ∈ R;

(2) if |γ| < k then there is a path η such that [η] ∈ R and γ is a prefix of η, i.e. γ = η|_{|γ|}. Note that for any R the path system P_{R} is G-invariant.

A path system P in X is k-locally recognized if for some R ⊂ S_{k} we have P = P_{R}. It is locally recognized if it is k-locally recognized for some k.

7.1 Proposition. Given X and G as above, any locally recognized path system P in X is regular. Moreover, if for some v_{0} ∈ V_{X} we restrict P to the path system P_{0} consisting of those paths from P which have the initial and the final vertex in the orbit G(v_{0}), then P_{0} is also regular.

Proof: Suppose that P = P_{R} for a subset R ⊂ S_{k}. We shall construct a finite-to-one automaton M = (M, m, S_{0}, S_{Ω}) over (X, G) such that P (M) = P_{R}.

For the set S_{0} of start vertices take the set V_{X} (of all vertices in X). For the set S_{Ω} of accept vertices take the set {γ ∈ P_{R} : |γ| ≤ k} and put V_{M} = S_{0} ∪ S_{Ω}.

Define the set μ of directed edges in M as consisting of the following three parts. First, for any v ∈ V_{X} and any path e ∈ P_{R} of length 1 with i(e) = v, take the directed edge (v, e) from the start state v to the state e. Second, for any path γ ∈ S_{Ω} with |γ| ≥ 2, express γ as γ′e, where γ′ = γ|_{|γ|−1} and e is the final edge in γ, and take the directed edge (γ′, γ). Third, for any path γ ∈ P_{R} of length k + 1, express γ as e_{1}ηe_{2}, where e_{1}, e_{2} are the initial and the final edge in γ respectively, η is the middle subpath in γ of length k − 1 (in particular, η is a nullpath if k = 1), and take the directed edge (e_{1}η, ηe_{2}). Define the map m : M → X by putting m(v) = v for any v ∈ V_{X} = S_{0}, m(γ) = t(γ) (the terminal vertex in γ) for any γ ∈ S_{Ω}, and extending this to edges by m((v, e)) = e, m((γ′, γ′e)) = e and m((e_{1}η, ηe_{2})) = e_{2}. We omit the details of the easy arguments showing that so defined automaton M is finite-to-one, the natural G-action on it is as required, and that P (M) = P_{R}.

To prove that the subsystem P_{0} is also regular, it is sufficient to modify slightly the automaton M, by restricting the sets of start and accept vertices. More precisely, for the new set of start vertices take the orbit G(v_{0}) and for the new set of accept vertices the set S_{Ω} ∩ m^{−1}(G(v_{0})). The graph M and the map m remain unchanged.

Proposition 7.1 and Theorem 1.1 imply the following.

7.2 Corollary. Let X be a graph acted upon by a group G properly discontinuously and cocompactly, and let P be a path system in X satisfying the following conditions:

(1) P is locally recognized;

(2) there is v_{0} ∈ V_{X} such that any two distinct vertices from the orbit G(v_{0}) are connected by a path from P;

(3) P satisfies the fellow traveller property. Then G is automatic. Moreover, if instead of (3) P satisfies the 2-sided fellow traveller property then G is biautomatic.

In the next section we apply Corollary 7.2 to extend numerous results from the literature, where groups acting freely on some spaces are shown to be biautomatic, to groups acting with finite stabilizers. We also offer an alternative proof that hyperbolic groups are biautomatic.

8. Applications to groups acting on various spaces.

We apply the results of the previous sections (summarized in Corollary 7.2) to groups acting properly discontinuously and cocompactly on various classes of spaces.

8.1. CAT (0) cubical complexes.

The main reference for this subsection is the paper by G. Niblo and L. Reeves [NR1]. Recall that a cubical complex K is CAT (0) iff it is simply connected and its link K_{v} at any vertex v is a flag (simplicial) complex. For a cell C in K, denote by Res(C, K) the union of all (closed) cells in K that contain C as a face.

We associate to a cubical complex K the graph X_{K} as follows. The vertex set V_{X_{K}} coincides with the vertex set of K, while two vertices are connected with an edge iff they are contained in a common cubical cell (of any dimension) in K. In other words, edges in X_{K} correspond to all diagonals in all cells in K, including ”diagonals” of 1-cells, i.e. the edges in K.

Given an (oriented or not) edge e in X_{K}, denote by C_{e} the (unique) smallest cubical cell in K that contains both endpoints of e. In Section 3 of [NR1] the authors introduce the so called normal cube-paths in K. In our setting, these are the paths γ = (e_{1}, …, e_{n}) in X_{K} satisfying the following property: for each i = 1, …, n − 1 we have

(8.1.1)  Res(C_{e_{i}}, K) ∩ C_{e_{i+1}} = {t(e_{i})}.

It is shown in [NR1] that if K is CAT (0) then any two vertices in X_{K} are connected with a normal cube-path. Moreover, it is shown that normal cube-paths satisfy the 2-sided fellow traveller property in X_{K}.

If G is a group acting on K by automorphisms properly discontinuously and cocompactly, we have the induced action of G on X_{K}, which is also properly discontinuous and cocompact. Moreover, it follows immediately from the condition (8.1.1) that the system of all normal cube-paths in X_{K} is 2-locally recognized. By applying Corollary 7.2 to the path system P of all normal cube-paths in X_{K} we get the following extension of the main result proved in [NR1].

8.1.2 Corollary. Let K be a CAT (0) cubical complex and let G be a group acting on K by automorphisms properly discontinuously and cocompactly. Then G is biautomatic.

8.2. 6-systolic simplicial complexes.

The 6-systolic simplicial complexes have been introduced and extensively sudied in the paper by T. Januszkiewicz and the author [JS]. These are the simply connected simplicial complexes of arbitrary dimension that satisfy some local (combinatorial) condition that resembles nonpositive curvature. In dimension 2 the 6-systolic complexes coincide with the so called (in [GS2]) simplicial complexes of type A_{2} of nonpositive curvature. It is shown in [JS] that groups acting by automorphisms properly discontinuously and cocompactly on 6-systolic simplicial complexes are biautomatic. Here we indicate that this result can be also proved using the general framework of ideas developed in this paper.

Recall briefly the definition of a 6-systolic simplicial complex. A full cycle in a simplicial complex is a full subcomplex isomorphic to a triangulation of the circle S^{1}. A simplicial complex is 6-large if it is flag and contains no full cycle with less than 6 edges. A simplicial complex K is 6-systolic if it is simply connected and its link K_{v} at any vertex v is 6-large. This simple definition describes spaces with surprisingly rich geometric (but expressed in purely combinatorial terms) structure. For our purposes it is necessary to recall from [JS] the definition and basic properties of the so called directed geodesics in 6-systolic complexes.

For a simplex σ in a simplicial complex K we denote by Res(σ, K) the union of all (closed) simplices in K that contain σ as a face. Moreover, denote by B_{1}(σ, K) the union of all simplices in K that intersect (equivalently, share a face with) σ. Given a 6-systolic simplicial complex K, a directed geodesic in K is a sequence σ_{0}, σ_{1}, …, σ_{n} of simplices in K satisfying the following conditions:

(1) for each i = 1, …, n the simplices σ_{i−1} and σ_{i} are disjoint and span a simplex in K (this simplex is unique and we denote it σ_{i−1} ∗ σ_{i});

(2) for each i = 1, …, n − 1 we have Res(σ_{i−1}, K) ∩ B_{1}(σ_{i+1}, K) = σ_{i}.

Denote by X_{K} the 1-skeleton of the barycentric subdivision K′ of K and recall that the vertices in K′ correspond bijectively to the simplices in K. This correspondence has the form σ → b_{σ}, where b_{σ} is the barycenter of σ. Clearly, if K is acted upon by a group G properly discontinuously and cocompactly, then the same properties hold for the induced action of G on X_{K}.

A directed geodesic σ_{0}, …, σ_{n} in K determines uniquely a path e_{1}, …, e_{2n} in X_{K} such that for i = 1, …, n we have

i(e_{2i−1}) = b_{σ_{i−1}}, t(e_{2i−1}) = b_{σ_{i−1}∗σ_{i}}, i(e_{2i}) = b_{σ_{i−1}∗σ_{i}}, t(e_{2i}) = b_{σ_{i}}.

It is proved in [JS] that the path system P consisting of all paths in X_{K} associated to directed geodesics in K as above satisfies the 2-sided fellow traveller property. Moreover, it is shown that for any two vertices p, q in K there is a directed geodesic σ_{0}, …, σ_{n} with σ_{0} = p and σ_{n} = q. This means that if we chose for v_{0} a vertex in X_{K} corresponding to a vertex in K, then P fulfills assumptions (2) and (3) of Corollary 7.2. We will show that P is also locally recognized.

The conditions for directed geodesics in K can be rephrased into the following conditions for the corresponding paths in P. For a vertex v in X_{K} denote by σ(v) the simplex in K such that v = b_{σ(v)}. For a simplex σ and its face τ denote by σ − τ the face of σ ”opposite” to τ, i.e. spanned by all vertices of σ not in τ. Then a path γ = (e_{1}, …, e_{2n}) is in P iff the following two conditions are satisfied:

(1) for i = 1, …, n the simplices σ(i(e_{2i−1})) and σ(t(e_{2i})) are disjoint and span the simplex σ(i(e_{2i}));

(2) for i = 1, …, n − 1 we have

Res(σ(i(e_{2i})) − σ(t(e_{2i})), K) ∩ B_{1}(σ(t(e_{2i+1})) − σ(i(e_{2i+1})), K) = σ(t(e_{2i})).

Note that by condition (1), the simplex σ(t(e_{2i})) is a proper face in the simplex σ(i(e_{2i})) for i = 1, …, n − 1, and similarly σ(i(e_{2i+1})) in σ(t(e_{2i+1})), so that the opposite faces occuring in condition (2) make sense.

Since the above conditions depend on pairs of consecutive edges in a path, and have G-invariant character, it follows that the path system P is 2-locally recognized. Corollary 7.2 implies then the following.

8.2.1 Corollary. Let G be a group acting simplicially properly discontinuously and cocompactly on a 6-systolic simplicial complex K. Then G is biautomatic.

Note that the special case of the above result, for 2-dimensional complexes and free cocompact actions, was proved in [GS2].

8.3. Euclidean buildings of types Ã_{n}, B̃_{n} and C̃_{n}.

G. Noskov in [N] proves that order preserving groups of automorphisms acting freely and cocompactly on Euclidean buildings of types Ã_{n}, B̃_{n}, C̃_{n} are biautomatic. In this subsection we show how to extend this result to order preserving groups acting properly discontinuously and cocompactly.

Let Δ be a Euclidean building of one of the types Ã_{n}, B̃_{n}, C̃_{n}. Denote by X_{Δ} the 1-skeleton of Δ and note that if a group G acts by automorphisms on Δ properly discontinuously and cocompactly then we get the induced action on X_{Δ} which is also properly discontinuous and cocompact. In Section 4 of [N] the author describes the combing C in Δ, which is nothing else than certain path system in X_{Δ} consisting of paths connecting the so called special vertices in Δ. In Section 5 of [N] it is shown that C satisfies the 2-sided fellow traveller property. In Section 7 Noskov describes a (obviously) 2-locally recognized path system C′ in X_{Δ}, and shows that C = C′. Thus, choosing v_{0} to be any special vertex in Δ, we get all the assumptions of Corollary 7.2 satisfied by the path system C, which implies the following.

8.3.1 Corollary. A group G acting by automorphisms on a Euclidean building of type Ã_{n}, B̃_{n} or C_{n} properly discontinuously cocompactly and in order preserving way is biautomatic.

8.4. Hyperbolic groups and local recognition.

This subsection contains alternative proof of the well known fact that hyperbolic groups are biautomatic. Instead of cone types, the proof exploits the fact that, for k sufficiently large, k-local geodesics in the Cayley graph of a hyperbolic group are quasigeodesics (with uniform constants).

Let G be a hyperbolic group and X its Cayley graph (with respect to any generating set). Then X is acted upon by G freely and cocompactly. Let P_{k} be the path system in X consisting of all paths whose subpaths of length ≤ k are geodesics. Then P_{k} is clearly k-locally recognized.

Recall (e.g. from [BH], chapter III.H) that if k > 8δ (where δ is the hyperbolicity constant for X) then a k-local geodesic in X is a (λ, ε)-quasi-geodesic, with λ and ε depending only on δ and k. It is also known that for fixed constants λ and ε the family of (λ, ε)-quasi-geodesics satisfies the 2-sided fellow traveller property.

From what was said above it follows that, if k > 8δ, then the path system P_{k} in X satisfies all the assumptions of Corollary 7.2, which shows G is biautomatic.

References

[B] K. Brown: Buildings, Springer-Verlag, 1989.

[BH] M. Bridson, A. Haefliger: Metric spaces of non-positive curvature, Springer-Verlag, 1999.

[BHo] B. Brink, R. Howlett: A finiteness property and an automatic structure for Coxeter groups, Math. Annalen 296 (1993), 179–190.

[CS] D. Cartwright, M. Shapiro: Hyperbolic buildings, affine buildings and automatic groups, Michigan Math. J. 42 (1995), 511–523.

[D] M. Davis: Buildings are CAT (0), in Geometry and Cohomology in Group Theory, P. Kropholler, G. Niblo and R. Stohr (eds.), LMS Lecture Notes Series, Cambridge University Press, 1998.

[E+] D. Epstein, J. Cannon, D. Holt, S. Levy, M. Patterson and W. Thurston: Word processing in groups, Jones and Barlett, Boston, 1992.

[GS1] S. Gersten, H. Short: Rational subgroups of biautomatic groups, Annals of Math. 134 (1991), 125-158.

[GS2] S. Gersten, H. Short: Small cancellation theory and automatic groups, Invent. Math. 102 (1990), 305–334.

[GS3] S. Gersten, H. Short: Small cancellation theory and automatic groups, II, Invent. Math. 105 (1991), 641–662.

[JS] T. Januszkiewicz, J. Świa̧tkowski: Simplicial non-positive curvature (in preparation).

[N] G. Noskov: Combing Euclidean buildings, Geometry & Topology 4 (2000), 85–116.

[NR1] G. Niblo, L. Reeves: The geometry of cube complexes and the complexity of their fundamental groups, Topology 37 (1998), 621–633.

[NR2] G. Niblo, L. Reeves: Coxeter groups act on CAT(0) cube complexes, Journal of Group

Theory, to appear.

[R] M. Ronan: Lectures on buildings, Academic Press, 1989.

[T] J. Tits: Buildings of spherical type and finite BN-pairs, Lecture Notes in Math. 386, Springer-Verlag, 1974.