Combing nilpotent and polycyclic groups

Robert H. Gilman, Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ 07030, USA,

e-mail: rgilman@stevens-tech.edu

Derek F. Holt, Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK, e-mail: dfh@maths.warwick.ac.uk

Sarah Rees, Department of Mathematics, University of Newcastle, Newcastle NE1 7RU, UK, e-mail: Sarah.Rees@ncl.ac.uk

Abstract

The notable exclusions from the family of automatic groups are those nilpotent groups which are not virtually abelian, and the fundamental groups of compact 3-manifolds based on the Nil or Sol geometries. Of these, the 3-manifold groups have been shown by Bridson and Gilman to lie in a family of groups defined by conditions slightly more general than those of automatic groups, that is, to have combings which lie in the formal language class of indexed languages. In fact, the combings constructed by Bridson and Gilman for these groups can also be seen to be real-time languages (that is, recognised by real-time Turing machines).

This article investigates the situation for nilpotent and polycyclic groups. It is shown that a finitely generated class 2 nilpotent group with cyclic commutator subgroup is real-time combable, as are also all 2 or 3-generated class 2 nilpotent groups, and groups in specific families of nilpotent groups (the finitely generated Heisenberg groups, groups of unipotent matrices over Z and the free class 2 nilpotent groups). Further it is shown that any polycyclic-by-finite group embeds in a real-time combable group. All the combings constructed in the article are boundedly asynchronous, and those for nilpotent-by-finite groups have polynomially bounded length functions, of degree equal to the nilpotency class, c; this verifies a polynomial upper bound on the Dehn functions of those groups of degree c+1.

AMS subject classifications: 20F10, 20-04, 68Q40, secondary: 03D40

The first author was partially supported by the National Science Foundation. The second and third authors would like to thank the Fakultät für Mathematik of the Universität Bielefeld for its hospitality while this work was carried out, and the Deutscher Akademischer Austauschdienst and EPSRC for financial support.

1 Introduction

The aim of this article is to investigate which finitely generated nilpotent and polycyclic groups have real-time combings, or rather asynchronous combings which are real-time languages.

The concept of a combing for a finitely generated group has grown out of the definition of an automatic group (as introduced in [9]). A formal definition is given in Section 2; informally, a combing is an orderly set of strands through the Cayley graph of the group, alternatively a set of words mapping onto the group for which words which represent closely related group elements are also closely related as words; automatic groups possess (synchronous) combings which are regular languages. We remark that, by [6], the existence of any combing, synchronous or asynchronous, for G implies that G is finitely presented, with exponential isoperimetric inequality, and hence soluble word problem.

Our interest in combings in other formal language classes arises out of work in [7], which shows that the fundamental group of any compact geometrisable 3-manifold has an indexed combing, that is, a combing in the formal language class of indexed languages. (The indexed languages lie above the context-free languages in the formal language hierarchy, and are defined by automata with an attached system of nested stacks.) It seems natural to ask whether or not the family of indexed combable groups is large enough also to contain all finitely generated nilpotent groups. This paper arose out of an attempt to answer that question. However, our attention was diverted to the class of real-time languages by our realisation that all the combings constructed in [7] lay in that class. Further, while the combing for Z^{2} which was fundamental to the construction of the others in [7] is an indexed language, it seems unlikely that the analogous combing for Z^{n} is indexed (we have not yet proved this), but it is a real-time language. The real-time languages, recognised by real-time Turing machines, are, in particular, recognisable in linear time. Hence in this paper we address the following question: ‘Does every finitely generated nilpotent group have a real-time combing?’

We certainly need to go some way up the language hierarchy to find combings for nilpotent groups. By [9], nilpotent groups, unless virtually abelian, cannot have regular combings, and by [7], if such a group has a context-free combing, it cannot be bijective (that is, it cannot contain unique representatives of each group element). Further, Burillo has proved in [8] that neither the groups U_{n}(Z) of n-dimensional unipotent upper-triangular matrices over Z, nor the 2n + 1-dimensional Heisenberg groups, defined by the presentations

H_{2n+1} = ⟨x_{1}, … x_{n}, y_{1}, … y_{n}, z | [x_{i}, y_{i}] = z, ∀i,
[x_{i}, x_{j}] = [y_{i}, y_{j}] = [x_{i}, y_{j}] = 1, ∀i, j, i ≠ j⟩

can have synchronous, quasigeodesic combings. (Thurston had already proved in [9] that the 3-dimensional Heisenberg group does not satisfy a quadratic isoperimetric inequality, and hence cannot be synchronously combable by quasigeodesics; Burillo’s result was proved by consideration of higher dimensional isoperimetric inequalities.) In fact both U_{n}(Z) and H_{2n+1} have asynchronous combings; see the end of Section 4.

We do not have a complete answer to our question, but have some interesting partial answers. We prove that a finitely generated class 2 nilpotent group has a real-time combing if it has cyclic commutator group, or can be generated by at most 3 of its elements; we do so by relating such a group to a semidirect product, and applying a result of Bridson ([5]). We give an example of a 4-generated class 2 nilpotent group which cannot be related to a semidirect product in this way (but so far we have not proved that this group does not have such a combing for some other reason). Finally we show that any polycyclic-by-finite group (and hence, of course, any finitely generated nilpotent group) embeds in a real-time combable group. We verify that all these combings have fairly good geometrical properties. In particular, those for class c nilpotent groups have length functions which are bounded by a polynomial of degree c. By [6], the existence of such a combing implies a polynomial upper bound of degree c + 1 on the Dehn function of the group, verifying a conjecture commonly attributed to Gersten; this suggests that the combings are in some sense optimal. (The existence of a polynomial upper bound for the Dehn function of a nilpotent group is proved in [10], and Gersten’s conjecture is verified for various nilpotent groups, including many of those considered here, in [19, 3].)

An entirely different approach towards the construction of combings is outlined by Gromov in [14], chapter 5, and described in rather more detail by Pittet in [19]. Asynchronous combings for homogeneous nilpotent groups are constructed out of homotopic combings of Lie groups in which they embed. (Essentially a homotopic combing of a Lie group is a set of continuous rectifiable paths in the underlying manifold satisfying a continuous form of the fellow traveller condition of this paper.) The construction is geometric, and depends on particular properties of the Lie group; the language theoretic complexity of these combings is not examined. Gromov comments that the Heisenberg groups and free class c nilpotent groups (the quotients of free groups by the n-th terms of their lower central series) are homogeneous. Pittet deduces, from the combings which can be constructed for the free nilpotent groups and the groups

G_{c} = ⟨a_{1}, … a_{c}, t | [a_{i}, a_{j}] = 1, a_{i}^{t} = a_{i}a_{i+1}, i ≠ c, a_{c}^{t} = a_{c}⟩

(defined in [3], and also class c nilpotent), that these groups consequently have polynomial Dehn functions of degree c + 1. The results of this article produce real-time combings for the groups G_{c}, the Heisenberg groups and the class 2 free nilpotent groups, but not obviously for the higher class free nilpotent groups.

The work of this paper relates also to work of Baumslag, Shapiro and Short in [4]. There the class of parallel poly-pushdown groups is defined, and proved to contain the fundamental groups of all compact geometrisable 3manifolds and every class 2 nilpotent group. Further, every finitely generated torsion-free nilpotent group is proved to embed in a parallel polypushdown group. Hence the results are analogous to ours. However the class of parallel poly-pushdown groups generalises the concept of an automatic group in a rather different way; the language associated with a parallel poly-pushdown group satifies a weaker condition (which can be checked by pushdown automata) than the fellow traveller condition of this paper, and so is not necessarily a combing.

2 Definitions and notations

Let G be a group, with identity element 1, and finite generating set X. Without loss of generality, we may assume that X is inverse closed, that is, contains the inverse of each of its elements; we shall make this assumption throughout this paper. We call a product of elements in X a word over X, and denote by X^{∗} the set of all such words. Let Γ = Γ_{G,X} be the Cayley graph for G over X, with vertices corresponding to the elements of G, and, for each x ∈ X, a directed edge from the vertex g to the vertex gx, labelled by x. Let d_{G,X} measure (graph theoretical) distance between vertices of Γ_{G,X}. For words w, v ∈ X^{∗}, we write w = v if w and v are identical as words, w =_{G} v if w and v represent the same element of G. We define l(w) to be the length of w as a string, and l_{G}(w) to be the length of the shortest word in X^{∗} representing the same element of G as w, that is, the geodesic length of w. It is straightforward to extend d_{G,X} to a metric on the 1-skeleton of Γ. Then each word w can be associated with a path from 1 labelled by w, and parameterised by t ∈ [0, ∞), such that, for t < l(w), the path from 1 to w(t) has length t, and for t ≥ l(w), w(t) = w(l(w)).

Suppose that v, w are words in X^{∗}, and that K ∈ N. We say that v and w asynchronously K-fellow-travel if there is a differentiable function h : R → R, mapping [0, l(v) + 1] onto [0, l(w) + 1] and strictly increasing on [0, l(v) + 1], with the property that, for all t > 0, d_{G,X}(v(t), w(h(t))) ≤ K. (The only point of adding 1 to l(v) and l(w) in this definition is to deal with the cases where one of the two words is trivial.) We call h the relative-speed function. If h is the identity function, we say that v and w synchronously K-fellow-travel. If for some M, and all t, h satisfies 1/M ≤ h′(t) ≤ M, we say that v and w boundedly asynchronously fellow-travel with bound M.

We define a language for G over X to be a set L of words over X which contains at least one representative for each element of G; L is said to be bijective if it contains exactly one representative of each group element. We call a language L for G an asynchronous combing (or just combing) if for some K the asynchronous K-fellow-traveller condition is satisfied by all pairs of words v, w ∈ L for which w =_{G} vx for some x ∈ X ∪ {1}; if relevant pairs of words synchronously fellow-travel, then L is a synchronous combing, while if relevant pairs of words boundedly asynchronously fellow-travel, for some global bound M, then L is a boundedly asynchronous combing.

If L is a combing for G over X then, following [6], we define the length function f : N → N for L by the rule that f(n) is the maximum length of a word in L of geodesic length at most n. The language L is a geodesic combing if f(n) = n for all n.

A group G is automatic if it has a synchronous combing L which is a regular language (that is, recognised by a finite state automaton, see [17]), and asynchronously automatic if it has a regular asynchronous combing. (In fact it is proved in [9], Theorem 7.2.4 that any group with a regular, asynchronous combing must have a regular boundedly asnchronous combing.) Since (see below) the regular languages form a subfamily of both the indexed and the real-time languages, any automatic, or even asynchronously automatic group is clearly both real-time and indexed combable.

When G is automatic, for each x ∈ X ∪ {1}, the set L′_{x} of pairs of words v, w ∈ L for which w =_{G} vx can also be interpreted as a regular set (over an alphabet of ordered pairs from X); in fact the existence of a regular language L for G for which each such L′_{x} is also regular can be taken as an alternative definition for an automatic group. Unfortunately, this alternative view only has limited application when we generalise to other types of combings. For synchronous combings, we can still construct finite state automata to recognise the regular sets L′′_{x} of all pairs of synchronously Kfellow travelling words w, v with w =_{G} vx (for some K). However the sets L′_{x} are not regular or even in the same formal language family as L; the regularity of L′ in the case of automatic groups depends on particular properties of the regular languages (basically, their closure as a language family under Boolean operations), which do not hold for other language families. For an asynchronously combable group, the corresponding sets L′′_{x} are no longer regular, but automata which read their input asynchronously from 2 strings can be built to recognise the fellow traveller property.

A systematic analysis of combings of various types (that is, associated with a range of fellow-travel properties) and lying in various formal language classes is given in [21]; in this article we restrict attention to real-time combable groups, that is to groups with asynchronous combings which lie in the formal language class of real-time languages. Further, the combings we construct will all be seen to be boundedly asynchronous, and will often have polynomially bounded length functions.

In this paper we assume familiarity with the basics of formal language theory, such as the definitions of Turing machines and finite state automata. An introduction to the subject, directed towards geometric group theorists, can be found in [12]; [17] is an excellent standard reference. Below we give a brief description of real-time languages. A definition of indexed languages can be found in [1], and of the nested stack automata which define them in [2], while the indexed grammars which define them are described in [7].

Real-time languages (see Rabin’s paper [20] for a full definition) are the languages accepted by deterministic real-time Turing machines. These have a fixed number of tapes, one of which is designated as the input tape, and contains just the input string. The other tapes can be taken to be infinite in both directions. With each transition, the machine must read one input symbol and move along the input tape to the next input symbol. For each of the other tapes, the machine may write a symbol or a blank, and then either stay still or move one place to the left or right. The computation halts when it reaches the end of input. Real-time languages do not have as many nice closure properties as the others considered in this paper (for example, they are not necessarily closed under concatenation with regular languages or under homomorphism). Furthermore, it can be difficult to determine whether a given language is real-time or not. However, they do represent a very natural model of linear-time computation, and they seem to be the most appropriate language for many of the combings that arise in this paper. All of {a^{n^{2}} : n ∈ Z^{+}}, {a^{2^{n}} : n ∈ Z^{+}}, {a^{n}b^{n^{2}} : n ∈ Z^{+}}, {a^{n!} : n ∈ Z^{+}} and {(ab^{n})^{n} :∈ Z^{+}} are real time languages. The first three are also indexed ([17]), but the latter two are not ([13, 16]). It is proved in [23] that the language

{a^{n_{1}}ba^{n_{2}}b … a^{n_{r−1}}ba^{n_{r}}c^{s}a^{n_{r−s+1}} |r, s, n_{1}, …, n_{r} ∈ Z^{+}}

is deterministic context-free but not real-time

In the formal language hierarchy, the real-time languages form a subfamily of the context-sensitive languages which contains all the regular languages, but (as we see from the example above) not all context-free languages. The indexed languages lie between the context-sensitive and the context-free languages. Since every regular language is both real-time and indexed, it is clear that every automatic, or even asynchronously automatic group is both real-time combable and indexed combable.

The following, rather surprising, result shows that real-time combings are only really interesting when they satisfy additional restrictions.

Proposition 2.1 If G has an asynchronous combing which is recursively enumerable, then G has a real-time asynchronous combing.

Proof: Let L be a recursively enumerable combing for G over X accepted by a Turing machine M. We construct a real-time combing L′ for G over a larger alphabet X ∪{e} by replacing each w ∈ L by a word of the form we^{m}, where e is an alphabet symbol representing the identity and m is the sum of the length of w and the number of moves which M needs to accept w.

Note that Proposition 4.1, which we shall prove later, implies the existence of a further real-time combing for G over the original generating set X.

L′ is accepted by a real-time Turing machine which, given an input word w′, first copies each symbol up to the first occurrence of e onto its work tape, and then operates as M on the contents of that tape, while continuing to read from the input tape. It accepts w′ provided that it reads only e’s while operating as M, and that M halts in an accept state just as the end of the input is reached. □

However, a real-time combing defined as above is in general not obviously constructible; its length function f(n) (defined earlier in this section) might not be recursive. By contrast, the combings constructed in this paper are much better behaved. For instance, they will all be boundedly asynchronous; this, as we shall now show, implies that the length function is at worst exponential. In fact, where the groups involved are nilpotent-by-finite, we shall see later that the length function is polynomially bounded.

Proposition 2.2 Let L be a boundedly asynchronous combing for G. Then the length function for L is at worst exponential.

Proof: The boundedness of the combing implies that there is an integer M with the property that, if h : R → R is the relative-speed function of two words v and w that asynchronously fellow-travel, then (l(w)+1)/(l(v)+1) ≤ M. Let c be the length of a shortest word w_{0} ∈ L satisfying w_{0} =_{G} 1; the above shows that any other representative of the identity has length less than (c + 1)M. Now let w ∈ L be a word having geodesic length n > 0. We shall show by induction on n that l(w) < (c + 1)M^{n}, which will prove the result. If n = 1, then w fellow-travels with w_{0}, so |l(w)| < (c + 1)M. If n > 1, then w =_{G} ux, where u has geodesic length n − 1 and x is a generator of G. By induction, any word in the combing for u has length at most (c + 1)M^{n−1}, but such a word fellow-travels with w, which therefore has length at most (c + 1)M^{n}. □

3 A particularly symmetric combing for Z^{n}

The combings in this paper are all constructed using a particularly well behaved combing of the free abelian group Z^{n}, due to Martin Bridson; it generalises a combing from [5]. The combing is synchronous and geodesic, and behaves particularly well under automorphisms of the group, due to the fact that it is almost-linear, that is, there is a constant K depending only on n such that for any x ∈ Z^{n} the combing path in Z^{n} from the origin to x and the corresponding straight line in R^{n} are synchronous K-fellow-travellers. Here we are considering Z^{n} as embedded in the usual way in R^{n} and thinking of a path in Z^{n} as a sequence of elements of Z^{n} with successive elements distance one apart.

Let e_{1}, …, e_{n} be a basis for Z^{n}. Take Σ_{n} = {a_{1}, a_{1}^{−1}, …, a_{n}, a_{n}^{−1}}, and define Σ_{n}^{∗} to be the free monoid over Σ_{n}. The correspondence a_{i} → e_{i}, a_{i}^{−1} → −e_{i} induces a monoid homomorphism from Σ_{n}^{∗} to Z^{n}. Denote by \overline{w} the image of w ∈ Σ_{n}^{∗} under this homomorphism. For example \overline{ϵ} = 0 where ϵ is the empty word and 0 is the identity element of Z^{n}. We do not distinguish between w ∈ Σ_{n}^{∗} and the corresponding path in Z^{n} from the origin to \overline{w}.

For any point p = ∑ p_{i}e_{i} ∈ Z^{n} parameterise the straight line from 0 to p by x_{i} = p_{i}te_{i}, 0 ≤ t ≤ 1. Start at t = 0, and each time some x_{i} assumes a positive integer value write down a_{i}, each time some x_{i} assumes a negative integer value write down a_{i}^{−1}. If two or more x_{i}’s assume integer values at the same time, write down the corresponding a_{i}’s in order of decreasing i. Figure 1 shows the combing path for (4, 3).

[figure: (0, 0)]
Figure 1: The combing path for (4, 3) is a_{1}a_{2}a_{1}a_{2}a_{1}a_{2}a_{1}.

Let L_{n} ⊂ Σ_{n}^{∗} be the language defined by the recipe above. Clearly L_{n} is a combing of Z^{n}, and it is straightforward to show that L_{n} has the desired fellow-traveller property.

It is shown in [7] that L_{2} is an indexed language. We devote the remainder of Section 3 to the proof of the following result:

Theorem 3.1 The language L_{n} is a real-time language for all n ≥ 1.

Proof: For n = 1 the proof is trivial. For n ≥ 2, the proof divides into two parts, a reduction to the consideration of a subset L_{2}^{+} of Σ_{2}^{∗}, followed by a demonstration that L_{2}^{+} is real-time.

3.1 Reduction to a 2-dimensional problem

First we shall reduce to the positive orthant. For any S ⊂ {1, …, n} define f : Σ_{n}^{∗} → Σ_{n}^{∗} to be the monoid homomorphism which interchanges a_{i} and a_{i}^{−1} for i ∈ S and fixes all other a_{i}’s. A moment’s consideration convinces us that f maps L_{n} to itself. Let L_{n}^{+} be the sublanguage of all paths in L_{n} which lie in the positive orthant, i.e., the set of words w ∈ L_{n} with \overline{w} = ∑ p_{j}e_{j}, p_{j} ≥ 0. Then L_{n} is the union of the images of L_{n}^{+} under the monoid isomorphisms f corresponding to all S ⊂ {1, …, n}. As real-time languages are closed under union, it follows that L_{n} is real-time if L_{n}^{+} is.

Next for each 1 ≤ i < j ≤ n let f_{i,j} : Σ_{n}^{∗} → Σ_{2}^{∗} be the monoid homomorphism which sends a_{i} to a_{1}, a_{j} to a_{2}, and all other generators to ϵ. We claim that L_{n}^{+} is the intersection of the inverse images of L_{2}^{+} under all the f_{i,j}’s. Since realtime languages are closed under inverse homomorphism and intersection, it will follow that L_{n}^{+} is real-time if L_{2}^{+} is.

It follows from the definition of L_{n} that f_{i,j} maps L_{n}^{+} to L_{2}^{+}. Hence L_{n}^{+} ⊂ ∩f_{i,j}^{−1}(L_{2}^{+}). For the converse suppose w is in the intersection, and \overline{w} = ∑ p_{k}e_{k}. For each i, j, f_{i,j}(w) is the combing path for p_{i}e_{1} + p_{j}e_{2}. Consequently f_{i,j}(w) = f_{i,j}(v) where v is the combing word in L_{n} for ∑ p_{k}e_{k}. But it is straightforward to check that if f_{i,j}(w) = f_{i,j}(v) for all i, j, then w = v. We conclude that ∩f_{i,j}^{−1}(L_{2}^{+}) ⊂ L_{n}^{+}.

3.2 The 2-dimensional problem

It now suffices to show that L_{2}^{+}, is real-time. From now on, for ease of notation, we shall rewite a_{1} as a and a_{2} as b, and so consider L_{2}^{+} as a subset of {a, b}^{∗}. Since b^{∗} is a regular language, it is enough to show that L_{2}^{#} = L_{2}^{+} \ b^{∗} is real-time. We work with L_{2}^{#} because it has the following recursive definition.

w = w_{k}^{n} for some k ≥ 0 and n ≥ 1  (1)
w_{j} = w_{j−1}^{i_{j}}w_{j−2} for 2 ≤ j ≤ k and i_{j} ≥ 1  (2)

and

If k is odd, then w_{1} = b^{i_{1}}a and w_{0} = b  (3)
If k is even, then w_{1} = a^{i_{1}}b and w_{0} = a.  (4)

That is, L_{2}^{#} is the collection of all words w ∈ Σ^{∗} satisfying some instance of (1-4). For example the sequence w_{0} = a, w_{1} = ab, w_{2} = (ab)^{3}a yields abababa, the combing path for (4, 3).

We shall not verify in this paper that L_{2}^{#} is so defined. This fact follows almost immediately from parts of the the proof of Theorem (3.10) of [7], which verifies that the same language (known in that paper as L_{1}) is an indexed language.

We construct a real-time Turing machine T which accepts the language L_{2}^{#}, working with the recursive definition of L_{2}^{#} above. In our proof, we shall consider only inputs beginning with a, but our arguments will always extend to the other case.

The valid inputs of T in a^{∗}b^{∗} are a and a^{i_{1}}b, and by (2) any valid input not in a^{∗}b^{∗} (and beginning with a) must have the form a^{i_{1}}ba . . .. It is straightforward to cope with inputs in a^{∗}b^{∗} and to arrange things so that after reading a^{i_{1}}ba, T has one work tape containing w_{0} = a, a second containing w_{1} = a^{i_{1}}b, and so that the tape heads for these tapes are positioned at the ends of their tape contents. We shall call configurations like this distinguished.

Definition 3.2 T is in a distinguished configuration if its input is a solution to (1-4), and for some j ≥ 1

1. T has read w_{j}w_{j−1} from its input;

2. T has one work tape containing w_{j−1}, and a second containing w_{j};

3. The tape heads for these tapes are each positioned either at the end of their tape contents or at the beginning.

4. On the work tape containing w_{j}, the squares at distance |w_{j−1}| from each end of the tape contents are marked.

Lemma 3.5 below tells us that if T is in a distinguished configuration, then either there is a longer input prefix w_{j+1}w_{j}, or the total input is w_{j+1} or w_{j}^{n} (for some n > 1). T will verify that the input has one of these forms, and in the first case it will simultaneously update the work tape containing w_{j−1} so that after coming to the end of the input prefix w_{j+1}w_{j} the work tape contains w_{j+1} and T is in another distinguished configuration. In the second case the input will be accepted before T has time to update the work tape. Thus T will accept all words in L_{2}^{#}. Of course for input not in L_{2}^{#}, T will reach a point where it is not able to do a required verification, and it will reject that input.

During its computation T will need to compare w_{j} to segments of input. It will do this by traversing the work tape containing w_{j} in either direction. For this method to be feasible we need to know that w_{j} is essentially a palindrome. We shall use the following notation. For any word v with length |v| ≥ 2, Φ(v) is v with its last two letters reversed. Notice that if u = Φ(v), then v = Φ(u); and uΦ(v) = Φ(uv). Also note that |w_{j}| ≥ 2 if j ≥ 1. Lemma 3.3, which refers to any solution to equations (1-4), is easy to prove by induction, and we omit the proof.

Lemma 3.3 For all j ≥ 1, w_{j}w_{j−1} = w_{j−1}Φ(w_{j}) and w_{j−1}w_{j} = Φ(w_{j}w_{j−1}).

To complete our proof of Theorem 3.1, we need Lemmas 3.4 and 3.5 below, which we also state without proof. (They follow fairly easily from Lemma 3.3.) They also refer to any solution to equations (1-4).

Lemma 3.4 For all j ≥ 1, w_{j} consists of a palindrome followed by ab or ba.

Lemma 3.5 Suppose j > 0, and w_{j}w_{j−1} is a prefix of w. One of the following holds.

1. j < k and w has a prefix w_{j+1}w_{j} = w_{j}w_{j−1}Φ(w_{j})^{i_{j+1}−1}w_{j};

2. j = k − 1, n = 1, and w = w_{j+1} = w_{j}w_{j−1}Φ(w_{j})^{i_{j+1}−1};

3. j = k, n > 1, and w = w_{j}^{n} consists of w_{j}w_{j−1}Φ(w_{j})^{n−1} with the suffix w_{j−1} deleted.

Now suppose that T is in a distinguished configuration as in Definition 3.2. T need only check that its input continues in one of the three ways indicated in Lemma 3.5, namely a power of Φ(w_{j}) followed by w_{j}, or a power of Φ(w_{j}), or a power of Φ(w_{j}) with the suffix w_{j−1} deleted. (Notice that the value of i_{j+1} is determined by the occurrence of a substring w_{j} of the input.) In the first case T must update the worktape containing w_{j−1} so that it contains w_{j+1} with the prefix and suffix of length |w_{j}| marked, and then position each of its tape heads at one end of the contents of its tape; afterwards T is again in a distinguished configuration. In each of the other two cases T comes to the end of its input and accepts the input. Actually T must also verify the parity condition of (3-4), but this task is accomplished by checking that the input ends in a.

Using Lemma 3.4 it is straightforward to design T so that by traversing the worktape containing w_{j} in either direction it can check that the next segment of length |w_{j}| of the input is either Φ(w_{j}) or w_{j}. If the input ends with Φ(w_{j}), then T accepts. If w_{j} is encountered, then once we show how the appropriate worktape is updated by the time w_{j} is read from the input, T will be in another distinguished configuration, namely the one corresponding to Definition 3.2 with j replaced by j +1. Finally using the markings on the work tape containing w_{j}, T can also tell when its input ends after a power of Φ(w_{j}) with the suffix w_{j−1} deleted.

It remains to see how T updates the worktape containing w_{j−1} while it is traversing the worktape containing w_{j} i_{j+1} times. Call the first worktape tape 1 and the second tape 2. Suppose that T is at the end of w_{j−1} on tape 1. Since w_{j+1} = w_{j}^{i_{j+1}}w_{j−1} = w_{j−1}Φ(w_{j})^{i_{j+1}}, T need only move to the right writing Φ(w_{j}) on the tape 1 each time it traverses the contents of tape 2. The square on tape 2 which marks the beginning of the suffix w_{j−1} of w_{j} will mark the end of the prefix of length |w_{j}| of w_{j+1} the first time Φ(w_{j}) is copied onto tape 1. In order to mark the appropriate suffix of w_{j+1}, T makes a temporary mark at the beginning of each Φ(w_{j}) which it writes. The first time it scans w_{j+1} in processing the next distinguished configuration all except the first of these marks are deleted, and the first mark is made permanent. Of course, the marks from the previous iteration also need to be deleted.

If T starts at the left of w_{j−1} on tape 1, then the procedure is similar. As w_{j+1} = w_{j}^{i_{j+1}}w_{j−1}, T need only move to the left writing w_{j} from right to left each time it traverses tape 2. As w_{j} is essentially a palindrome, this can be done. The markings are done the same way as before with obvious modifications.

This completes the proof of Theorem 3.1. □

4 Properties of the families of real-time combable groups

We shall construct real-time combings for nilpotent groups by showing that the groups can be constructed out of free abelian pieces with combings of type L_{n}, as already described. In this section we prove the necessary closure properties for the families of real-time combable groups which ensure that this strategy is valid. In fact, in the following lemma we prove more than we need (asynchronous results would be enough).

Proposition 4.1 Let G be a finitely generated group.

(a) If G is synchronously, asynchronously or boundedly asynchronously realtime combable, then it is so with respect to any generating set.

(b) Let H be a subgroup of finite index in G. Then G is synchronously, asynchronously or boundedly asynchronously real-time combable if and only if H is.

In each of the above cases, wherever the original combing has a polynomially bounded length function, the new combing has a length function which is bounded by a polynomial of the same degree.

Similar results for asynchronous and synchronous combings in other languages families are proved in [7] and [21]. Although real-time languages do not possess the necessary properties for all of those results to apply directly, many of the ideas can be used.

Proof: To prove (a), let L be a real-time combing for G, over a finite (inverse closed) generating set X = {x_{1}, … x_{m}}, and suppose that Y = {y_{1}, … y_{n}} is a second (inverse closed) generating set for G. The natural way to define a combing L′ over Y is to find a set of words w_{1}, … w_{m} over Y, with w_{i} equal in G to x_{i}, and then define L′ to be the set of words over Y formed by substituting w_{i} for each occurrence of x_{i} in each word of L. The language L′ naturally inherits asynchronous fellow-traveller properties from L.

We can ensure that L′ is recognisable by a real-time Turing machine by requiring that each of the substituting words w_{i} is distinct and terminated by a string y_{1}y_{1}^{−1}, which appears nowhere else, If all the w_{i} have the same length k, then L′ satisfies synchronous fellow traveller properties; although in general we cannot organise this, we can at least arrange that all have length either k or k − 1, and pad out the shorter w_{i}’s by strings y_{1}^{−1}y_{1} on alternate substitutions.

To prove (b), suppose that H is a subgroup of finite index in G, and let T be a finite transversal for H in G, containing the identity element.

If H has a real-time synchronous or (boundedly) asynchronous combing, then the language for G formed by concatenating that combing with the elements of T is certainly a real-time combing of the same type for G.

Now suppose that L is a real-time synchronous or (possibly boundedly) asynchronous combing for G over an (inverse closed) generating set X. Let T be a finite transversal for H in G. An appropriate language for H over the Schreier generators for H with respect to X and T can be constructed using the Reidemeister-Schreier rewriting process; the construction is described in [21]. That the language is real-time is not hard to verify. (The arguments of [21] do not in fact always apply to real-time languages, but can be modified. For instance, where the arguments require that the language family under consideration is closed under GSM-mappings, the closure of the family of real-time languages under inverse GSM-mappings can be seen to be sufficient for the proof.)

Finally we need to verify that the various combings constructed have polynomially bounded length functions, given that the same is true of the original combings.

We observe first that the substitutions corresponding to change of generators have the effect of changing the length of a word by at most a constant factor (the maximum length of the old generators written as words in the new ones). Similarly, the geodesic length of the substituted word is smaller than the geodesic length of the original word by at most another constant factor (the maximum length of the new generators written as words in the old). Hence changing the generating set changes the length function by at most a constant factor, which can be expressed in terms of the above constants and the polynomial degree of the original length function.

For each of the remaining cases, the proofs that the length function continues to be polynomial degree are very similar. Hence we shall give details of the proof only in one case. Suppose that H has finite index in G, and associated transversal T. Given a combing L_{H}, with polynomial length function f, we want to show that the combing L_{H}T for G has polynomial length function.

We suppose that L_{H} is defined over a generating set X for H, and that Y is the set of Schreier generators for H associated with X ∪T and T. A geodesic representative w′ over X ∪T of a word w in L_{H} can be rewritten as a word of the same length over Y (using the Reidemeister-Schreier rewriting process). Its geodesic length over X is at most a constant factor longer than this (since both X and Y are generating sets for H). So, for words representing elements of H, geodesic lengths over X ∪ T are at most a constant factor less than those over X, and hence, for some c, cf(n) bounds the length of any word in L_{G} which represents an element of H and has geodesic length n over X ∪ T. It remains, for each t, to consider elements of L_{G} which represent elements of Ht. For such a word vt, of geodesic length n over X ∪ T, consideration of v, which must have geodesic length at most n + 1, shows that vt has length at most cf(n + 1) + 1. The result follows. □

Proposition 4.2 A direct product of real-time combable groups is real-time combable. If the factors have boundedly asynchronous combings, then so does the direct product. If the combing of each of the factors has polynomially bounded length function, then so does the combing constructed for the direct product.

Proof: The concatenation of combings for the direct factors is clearly an asynchronous combing. Since disjoint generating sets can be chosen for the two factors, the concatenation of the two languages is easily seen to be in the same family of languages as the original languages (The concatenation of two real-time languages over non-disjoint alphabets need not be a real-time language).

Bounded asynchronicity is straightforward to check. The final statement follows from the fact that geodesic words in the direct product can always be found which are concatenations of geodesic words in each of its factors. □

Proposition 4.3 Let G = Z^{n}>⊲H be a split extension of an n-generated free abelian group and a combable group H. Let L_{H} be the given combing for H, and let L_{n} be the combing for Z^{n} described in Section 3.

Then L_{G} = L_{H}L_{n} is a combing for G. If L_{H} is boundedly asynchronous then so is L_{G}. If L_{H} is a real-time language, then so is L_{G}.

Proof: The proof that L_{G} is a combing is given in [5] (Theorem B). Since the concatenation of real-time languages over disjoint alphabet sets is easily seen to be a real-time language, the fact that L_{G} is real-time follows immediately from Theorem 3.1. That the asynchronicity of the combing is bounded is not proved in [5], but is clear from examination of the proof. □

In order to get a polynomial bound on the length functon for a combing of a nilpotent group of the form Z^{n}>⊲H, we need to look more closely at the action associated with the extension. We say that a group H acting on a group N acts nilpotently if a series N = N_{0} ⊇ N_{1} ⊇ … N_{k} = 1 of subgroups of N can be found with [N_{i}, H] ⊆ N_{i+1} for 0 ≤ i < k. We call such a series an H-central series for N. We define the relative class of the action (or of the associated split extension) to be the minimum such k. If N is Z^{n} and H acts nilpotently on N, with relative class k, then it can be shown that an H-central series for N of length k can be found in which the factors N_{i}/N_{i+1} are all torsion-free. This will be proved in Section 5, Lemma 5.4. Note that if N>⊲H is nilpotent of class c, then H acts nilpotently on N with relative class at most c.

Proposition 4.4 Let G = Z^{n}>⊲H be as in the previous lemma, and assume in addition that H acts nilpotently on Z^{n}, with relative class k, and that the combing L_{H} of H has polynomially bounded length function of degree m.

Then a generating set for Z^{n} can be found such that the associated combing L_{G} = L_{H}L_{n} of G has length function bounded by a polynomial of degree at most the maximum of m and k.

Proof: Lemma 5.4 ensures the existence of an H-central series Z^{n} = N_{0} ⊇ N_{1} ⊇ … N_{k} = 1 of Z^{n} with torsion-free factors. Select the generating set X = {x_{1}, …, x_{n}} for Z^{n} so that x_{i_{j}+1}, …, x_{n} generate N_{j} minimally, for each j < k, i_{0} = 0 and i_{k} = n. Let c be the maximum of the lengths in X of any of the elements x_{j}^{y}, where y is an element of the generating set Y of H over which L_{H} is defined. For each y ∈ Y, if i_{j} < i ≤ i_{j+1}, then x_{i}^{y} = x_{i}w, for some word w of length at most c − 1 in x_{i_{j+1}+1}, … x_{n}. We now establish a bound on the length of x_{i}^{h} in terms of l(h), c and k. Let h = y_{t_{1}}y_{t_{2}} … y_{t_{l}} with y_{t_{j}} ∈ Y. Define elements g_{0}, g_{1}, … g_{l} ∈ Z^{n} by g_{0} = x_{i}, g_{j} = g_{j−1}^{y_{t_{j}}} for 1 ≤ j ≤ l, and hence g_{l} = x_{i}^{h}. It is convenient to assign dates to the occurrences of the generators x_{r} in the words g_{0}, … g_{l}. The single occurrence of x_{i} has date 0, and in general, if an occurrence of x_{r} in g_{j−1} has date m and x_{r}^{y_{t_{j}}} = x_{r}w, then the corresponding occurrences of x_{r} and the generators of w in g_{j} have dates m and m + 1 respectively. Let t(j, m) be the total number of occurrences of generators of date m in the word g_{j}. Then the generators of date m in g_{j+1} include those same t(j, m) generators together with at most (c − 1)t(j, m − 1) new ones arising from the conjugations by y_{t_{j+1}}. Hence t(j + 1, m) ≤ t(j, m) + (c − 1)t(j, m − 1).

From this inequality and the conditions t(j, 0) = 1 for all j and t(0, m) = 0

for all m > 0, it follows by induction that t(j, m) ≤ (\begin{matrix}j \\ m \end{matrix})(c − 1)^{m} for all

j, m. However, since t(j, m) = 0 for all m ≥ k, we have l(x_{i}^{h}) ≤ a × l(h)^{k−1} for some constant a which depends on c and k.

Now let v be a geodesic word over X ∪ Y, containing r generators from X and s from Y. Let u be the concatenation of the s generators in Y in the order in which they appear in v, and let u′ ∈ L_{H} with u′ =_{H} u. Then we have v =_{G} u′w′, where w′ is a product of r elements of X each conjugated by some suffix of u. From the preceding paragraph, there exists v′ ∈ L_{G} with v′ =_{G} v and with v′ equal to u′ times a word of length at most r × a × s^{k−1}. Since, by assumption, l(u′) is bounded by a polynomial of degree at most m in l(u) = s and ras^{k−1} ≤ a(r + s)^{k}, the result follows. □

The following corollary follows immediately from repeated application of this lemma.

Corollary 4.5 Suppose that the nilpotent group G is isomorphic to a tower of split extensions of the form Z^{n_{1}}>⊲(Z^{n_{2}}>⊲(Z^{n_{3}}>⊲ … Z^{n_{r}}) …). Then G has a real-time combing L_{G}, whose length function is bounded by a polynomial with degree the maximum, k, of the relative classes of the extensions.

Note that k is no larger than the nilpotency class of G.

Corollary 4.6 For any n, the unipotent groups U_{n}(Z) and the Heisenberg groups H_{2n+1}, as defined in Section 1, as well as the free nilpotent groups of class 2, F r_{n}/γ_{2}(F r_{n}), are real-time combable. The combings are boundedly asynchronous, with length functions bounded by polynomials of degrees n−1, 2 and 2, respectively.

Proof: For the Heisenberg and free nilpotent groups we apply Propositions 4.3 and 4.4; for the unipotent groups we apply Corollary 4.5, observing that U_{n}(Z) is a split extension of Z^{n−1} by U_{n−1}(Z). □

The following result shows that many soluble groups which are far from being nilpotent are also boundedly asynchronously real-time combable.

Corollary 4.7 If G is polycylic, metabelian and torsion-free with centre disjoint from G′, then G has an boundedly asynchronous real-time combing.

Proof: That G is polycyclic and metabelian implies that G′ is finitely generated. We now apply a result of Robinson ([22]). The particular form of this rather general result which we need is stated in [24], namely that if A is a finitely generated, free abelian normal subgroup of a group G such that G/A is finitely generated and nilpotent, and such that C_{A}(G) = 1, then some subgroup of finite index in G is a split extension of A. We set A to be G′, and apply Proposition 4.3 to get our result. □.

As an example of a combable group of this form, we have the group

⟨x, y, z | yz = zy, y^{x} = z, z^{x} = yz⟩

which is certainly not automatic (it has exponential isoperimetric inequality, see [9], Theorem 8.1.3).

These examples are the building blocks of many others. The combability of class 2 nilpotent groups with cyclic commutator subgroup, proved in Section 6, is basically a consequence of the combability of the Heisenberg groups; similarly the embedding theorem for polycyclic-by-finite groups proved in Section 7 follows essentially from the combability of the groups U_{n}(Z).

5 Useful properties of nilpotent groups

In this section, we list some facts about nilpotent groups, which we shall use in the following two sections. They are of a standard nature, and only outlines of proofs will be included. Let G = γ_{1}(G) ⊃ γ_{2}(G) ⊃ … ⊃ γ_{c+1}(G) = 1 be the lower central series of G, where G is nilpotent of class c. The first result is well-known; see, for example, Lemma 2.6, Corollary 1 of [15], and the second is of a similar nature.

Lemma 5.1 If H is a subgroup of the nilpotent group G with HG′ = G, then H = G.

Lemma 5.2 Let H be a subgroup of the finitely generated nilpotent group G for which |G : HG′| is finite. Then |G : H| is finite.

Proof: Using induction on the class c, we may assume that |G : Hγ_{c}(G)| is finite, and so we must show that |Hγ_{c}(G) : H| = |γ_{c}(G) : H ∩ γ_{c}(G)| < ∞.

An element of γ_{c}(G) is a product of commutators [g, k] with g ∈ G and k ∈ γ_{c−1}(G). Let |G : HG′| = m and |γ_{c−1}(G) : (H ∩ γ_{c−1}(G))γ_{c}(G)| = l. Then g^{m} ∈ HG′ and k^{l} ∈ (H ∩ γ_{c−1}(G))γ_{c}(G), and so [g, k]^{ml} = [g^{m}, k^{l}] ∈ H ∩ γ_{c}(G). Thus γ_{c}(G)/(H ∩ γ_{c}(G)) is finitely generated of finite exponent, and the result follows. □

The next result allows us to reduce consideration of an arbitrary nilpotent group G to one where both G and G/G′ are torsion free.

Lemma 5.3 Let G = ⟨g_{1}, … g_{n}⟩ be a finitely generated nilpotent group. Then G has an n-generator subgroup G_{0} of finite index such that both G_{0} and G_{0}/G′_{0} are torsion-free.

Proof: By Theorem 7.8 of [15], there is an integer r such that G^{r} is torsionfree. Let H = ⟨g_{1}^{r}, …, g_{n}^{r}⟩. Then |G : HG′| is finite, so by Lemma 5.2, |G : H| is finite. Since H ⊆ G^{r}, H is torsion-free.

Now choose h_{1}, …, h_{m} ∈ H such that h_{1}H′, … h_{m}H′ freely generate a maximal free abelian subgroup of H/H′, and let G_{0} = ⟨h_{1}, …, h_{m}⟩. Clearly m ≤ n. By Lemma 5.2, |H : G_{0}| and hence |G : G_{0}| is finite. Finally, since G′_{0} ⊆ H′, G_{0}/G′_{0} is itself free abelian of rank m and hence torsion-free, so the result follows. □

Lemma 5.4 If H acts nilpotently on N = Z^{n} with relative class k, then N has an H-central series of length k with torsion-free factors.

Proof: Let the given H-central series be M_{0} = 1 ⊆ M_{1} ⊆ M_{2} ⊆ … M_{k} = N, and define the series Z_{0} = 1 ⊆ Z_{1} ⊆ Z_{2} ⊆ … by letting Z_{i+1} be the inverse image in N of C_{N/Z_{i}}(H) for all i ≥ 0. Induction shows that M_{i} ⊆ Z_{i} for all i. Hence Z_{k} = N.

We show that Z_{i+1}/Z_{i} is torsion-free by induction on i. This is clear for i = 1. For i > 1, let g ∈ Z_{i+1} \ Z_{i} and suppose that g^{m} ∈ Z_{i}. Then there exists h ∈ H with [h, g] ∉ Z_{i−1}; but [h, g]^{m}Z_{i−1} = [h, g^{m}]Z_{i−1} = Z_{i−1}, contradicting the induction hypothesis. □

6 Class 2 nilpotent groups

In the following we shall denote by F_{k,c} (or sometimes, where there is no ambiguity, simply by F) the free nilpotent group on k generators of class c, that is the quotient of the free group F r_{k} on k generators by its subgroup γ_{c+1}(F r_{k}).

Suppose that G is nilpotent of class 2. In this section we prove that if G has cyclic commutator subgroup, or can be generated by at most 3 of its elements, then it is real-time combable. The method is basically to decompose finite index subgroups of G as split extensions, and then to apply the results of Section 4. However, we have an example of a 4 generator class 2 nilpotent group which has no finite index subgroup which is a split extension.

Lemma 6.1 Suppose that G is finitely generated nilpotent of class 2, and that G/G′ is torsion-free. Then, for some k, G can be expressed as a quotient F_{k,2}/K with K ⊆ F′_{k,2}.

Proof: By Lemma 5.1, if G/G′ has rank k, then G can be generated by k elements. The result follows. □

Theorem 6.2 Any class 2 finitely generated nilpotent group G with G′ cyclic has a real-time combing. The combing is boundedly asynchronous and has a length function which is at most quadratic.

Proof: By Lemma 5.3 and Proposition 4.1 (b), we may assume that both G and G/G′ are torsion free. Let G′ = ⟨c⟩. We claim that some finite index subgroup of G decomposes as a direct product of a central abelian subgroup Z and a subgroup H = ⟨a_{1}, … a_{n}, b_{1}, … b_{n}⟩ such that for any i, [a_{i}, b_{i}] is a power of c, but for i ≠ j, [a_{i}, a_{j}] = [a_{i}, b_{j}] = 1. Then H decomposes as a semidirect product of the subgroups ⟨a_{1}, … a_{n}, c⟩ and ⟨b_{1}, … b_{n}⟩, and the results of Section 4 imply that G is real-time combable. We establish the claim by induction on the size of a minimal generating set X for G. By Lemma 5.1, |X| is equal to the rank of G/G′.

First we select any two non-commuting elements a_{1}, b_{1} ∈ X and suppose that [a_{1}, b_{1}] = c^{i} For each other x ∈ X, where [a_{1}, x] = c^{j} and [b_{1}, x] = c^{k}, the element y = a_{1}^{k}b_{1}^{−j}x^{i} commutes with a_{1} and b_{1}. Let G_{1} be the group generated by all such elements y. Then |G : ⟨a_{1}, b_{1}, G_{1}⟩| is finite, and G_{1} ∩ ⟨a_{1}, b_{1}⟩ ⊆ ⟨c^{i}⟩. If G_{1} is abelian, then G_{1} ∩ ⟨a_{1}, b_{1}⟩ = 1, and we have the required decomposition with Z = G_{1}. Otherwise we apply induction to G_{1}.

Bounded asynchronicity and the quadratic bound on the length function follow from Propositions 4.1 and 4.3, and Corollary 4.4. □

Theorem 6.3 Any two or three generator class 2 nilpotent group G has a real-time combing. The combing is boundedly asynchronous and has a length function which is at most quadratic.

Proof: The two generator groups are covered by Theorem 6.2, so we assume that G is three generated. Lemma 5.3 and the results of Section 4 allow us to assume that G and G/G′ are torsion-free.

By Lemma 6.1, G is a quotient of F_{3,2} by a normal subgroup K in the commutator subgroup. Since we may assume that G′ ≅ F′_{3,2}/K is noncyclic and torsion-free, and since F′_{3,2} has rank 3, we need only consider the case where K is 1-generated, that is, where G is defined by one relator which is a product of commutators. In this case, the single relator can be put into the form [a, b]^{k}[a^{i}b^{j}, c]^{−1}. We consider the cases i = 0 and i ≠ 0 separately.

First let i ≠ 0, and let N = ⟨a^{i}b^{j}, [a, b]⟩, H = ⟨b, c⟩. Then |G : NH| is finite, and N is abelian and normal in G. Working mod G′, we see that, since a ∉ H, N ∩ H ⊆ ⟨[a, b]⟩. Hence if N ∩ H ≠ 1 we have a relation between [b, c] and [a, b]; but such a relation cannot be a consequence of the relator [a, b]^{k}[a^{i}b^{j}, c]^{−1}. So NH is a split extension, and hence, by the results of Section 4, G has a real-time combing.

When i = 0, the one relation can be written as [b, a^{k}c^{j}] = 1. Then the group ⟨a^{k}, b, c^{j}⟩, which has finite index in G, can be written as a semidirect product of N = ⟨a^{k}c^{j}, [a, c]⟩ and H = ⟨b, a^{k}⟩. Hence again G has a real-time combing.

Bounded asynchronicity and the quadratic bound on the length function follow again from Propositions 4.1, 4.3, and 4.4. □

Once we move to four generators, the situation is much less clear. Let F be the free nilpotent group of class two and rank four, with generating set {a, b, c, d}. Then F/F′ is free abelian of rank 4, and F′ = Z(F) is free abelian of rank 6, and is generated by the six commutators [a, b], [a, c], [a, d], [b, c], [b, d], [c, d]. Let K be the subgroup ⟨[a, b][c, d]⟩ of F, and let G = F/K. Then G′ = F′/K is free abelian of rank 5, and G/G′ ≅ F/F′.

Proposition 6.4 No subgroup G_{0} of finite index in G can be decomposed as a semidirect product N>⊲H, where N is a nontrivial abelian normal subgroup of G_{0}.

For the proof, assume that there is such a subgroup with a decomposition of this form. Note that, since G is torsion-free, N must be a nontrivial free abelian group. The idea is to show that the free abelian groups [N, G_{0}] ⊆ N and H′ ⊆ H both have rank 3. Since both lie within G′, which has rank 5, they must then intersect non-trivially. Hence N and H intersect nontrivially, which is a contradiction. This argument follows from a series of lemmas.

Lemma 6.5 Let E be any subgroup of F with 3 (or fewer) generators. Then no nontrivial element of K lies in E′.

Proof: Let E = ⟨e, f, g⟩ and suppose that 1 ≠ ([a, b][c, d])^{t} ∈ E′. Choose an odd prime p that does not divide t, and let P = F/F^{p}. Then P is a special p-group of order p^{10}, with |P′| = p^{6}, and P′ is generated by the six commutators of the pairs of the generators. Let Q = EF^{p}/F^{p}.

To simplify notation, we shall use a, b, c, d, e, f, g to denote the images of these elements in P. Note that 1 ≠ ([a, b][c, d])^{t} ∈ Q′. We can regard e, f, g as elements of the vector space P/P′, and assume that they are in reduced echelon form with respect to the basis a, b, c, d, and we may as well assume that none of e, f, g equals zero in P/P′. This leaves the following four essentially different possibilities for e, f, g:

\begin{matrix}(i) b, c, d; & (ii) ab^{i}, c, d (0 ≤ i < p); \\ (iii) ac^{i}, bc^{j}, d (0 ≤ i, j < p); & (iv) ad^{i}, bd^{j}, cd^{k} (0 ≤ i, j, k < p). \end{matrix}

In all cases, Q′ = ⟨[e, f], [e, g], [f, g]⟩. Cases (i) and (ii) are impossible, since none of [e, f], [e, g], [f, g] involves [a, b]. In Case (iv), we have [e, f] = [a, b][a, d]^{j}[b, d]^{−i}, [e, g] = [a, c][a, d]^{k}[c, d]^{−i} and [f, g] = [b, c][b, d]^{k}[c, d]^{−j}. Of these, only [e, g] involves [a, c] and only [f, g] involves [b, c], so ([a, b][c, d])^{t} would have to be a power of [e, f], which it clearly is not. A similar argument rules out Case (iii). □

Lemma 6.6 If [g, h] = 1 with g, h ∈ F, then ⟨g, h⟩F′/F′ is cyclic.

Proof: Since F′ is central in F, we may assume that g = a^{i}b^{j}c^{k}d^{l} and h = a^{i′}b^{j′}c^{k′}d^{l′} for some i, j, k, l, i′, j′, k′, l′ ∈ Z and then

[g, h] = [a, b]^{ij′−ji′}[a, c]^{ik′−ki′}[a, d]^{il′−li′}[b, c]^{jk′−kj′}[b, d]^{jl′−lj′}[c, d]^{kl′−lk′},

and so we have ij′ = ji′, etc. It can be checked that, for any solution of these six equations, g and h are powers of a common element, and the result follows. □

Lemma 6.7 NG′/G′ is an infinite cyclic group.

Proof: NG′/G′ is free abelian, because G/G′ is. We cannot have N ⊆ G′, because this would imply HG′ = G_{0}, and then H′ = G′_{0} would have finite index in G′, so N ∩ H could not be trivial. So we may assume that N contains two elements ḡ and h̄ such that ⟨ḡ, h̄⟩G′/G′ is not cyclic. But then, if g and h are inverse images of ḡ and h̄ in F, ⟨g, h⟩F′/F′ is also not cyclic, so [g, h] ≠ 1 by Lemma 6.6. But N is abelian, so [ḡ, h̄] = 1, which means that [g, h] ∈ K, contradicting Lemma 6.5 (applied to ⟨g, h⟩). □

Lemma 6.8 HG′/G′ is free abelian of rank 3.

Proof: Again HG′/G′ is free abelian, and Lemma 6.7 implies that its rank is at least 3. But if it had rank 4, |G : HG′| would be finite. so (by Lemma 5.2) |G : H| and |G′ : H′| would be finite, and N ∩ H could not be trivial. □

Lemma 6.9 [N, G_{0}] is free abelian of rank 3.

Proof: Let N̂ and F_{0} be the complete inverse images of N and G_{0} in F. Then N̂F′/F′ is infinite cyclic by Lemma 6.7; let gF′/F′ be a generator. Considering the homomorphism ϕ : F/F′ → [F, N̂] defined by h ↦ [g, h], we see that F/C_{F} (N̂)F′ ≅ [F, N̂], and so these groups are free abelian of the same rank. By Lemma 6.6, the group C_{F} (N̂)F′/F′ has rank exactly one. Thus F/C_{F} (N̂)F′ and [F, N̂] have rank 4 − 1 = 3; since |F : F_{0}| is finite, the same is true of [F_{0}, N̂].

Now the cyclicity of N̂F′/F′ implies that all elements of [N̂, F_{0}] are commutators of the form [g^{i}, h]. Then Lemma 6.5 applied to E = ⟨g, h⟩ implies that [N̂, F_{0}] ∩ K = 1, and the result follows. □

Lemma 6.10 H′ is free abelian of rank 3.

Proof: Let Ĥ be the complete inverse image of H in F. Then, by Lemma 6.8, ĤF′/F′ is free abelian of rank 3; let ĤF′/F′ = ⟨eF′, fF′, gF′⟩. Then Ĥ′ = ⟨[e, f], [e, g], [f, g]⟩, so its rank is at most 3. If it were less than 3, then we would have [e, f]^{x}[e, g]^{y}[f, g]^{z} = 1 for integers x, y, z not all zero. But it can be shown that this product of commutators is equal to a single commutator [h, k] for some h, k ∈ F with ⟨h, k⟩F′/F′ non-cyclic, which contradicts Lemma 6.6.

To finish, we need only show that Ĥ′ ∩ K = {1}, which follows from Lemma 6.5. □

This completes the proof of theorem 6.4

7 Embedding in real-time combable groups

In this section we prove the following result.

Theorem 7.1 Any polycyclic-by-finite group embeds as a subgroup of a realtime combable group. Furthermore, any nilpotent-by-finite group embeds as a subgroup of a group with a real-time combing with polynomially bounded length function.

This result seems interesting in the context of the result of Gersten and Short ([11]) that no polycyclic group can embed in a biautomatic group, unless abelian by finite.

Proof: We start by applying results of Malc̆ev and Hall ([18, 15]), which imply that any polycyclic group (and hence also any polycyclic-by-finite group) G has a subgroup G_{0} of finite index which embeds in a group T_{n}(F) of upper triangular matrices over an algebraic number field F. In fact, by using a result in an Exercise on page 36 of [24], we can even embed G_{0} into T_{n}(O), where O is the ring of integers of an algebraic number field. Note that T_{n}(O) is a finitely generated group. By inducing this representation from G_{0} to G, we see that G itself embeds in T_{n}(O)wrS_{m}, where m = |G : G_{0}|.

To finish the general, polycyclic-by-finite case, we need only to observe that T_{n}(O)wrS_{m} is real-time combable. T_{n}(O) can be decomposed as a semidirect product of the form E_{n}(O)>⊲(T_{n−1}(O)×A), where E_{n}(O) is the group of n × n matrices over O with 1’s on the diagonal, and the only other nonzero entries being in the right hand column, and A is the group of of n × n diagonal matrices with a unit of O in the bottom right hand corner, and all other diagonal entries equal to 1. Both E_{n}(O) and A are clearly finitely generated and abelian; an obvious induction argument (on n), using Propositions 4.3 and 4.2, then proves that T_{n}(O) is real-time combable. Then since T_{n}(O)wrS_{m} contains a direct product of copies of T_{n}(O) as a subgroup of finite index, Propositions 4.1 and 4.2 now imply that T_{n}(O)wrS_{m} is real-time combable.

When G is in fact nilpotent-by-finite, G has a subgroup G_{1}, of finite index m′, which is torsion-free nilpotent, and hence embeds in some U_{n′}(Z), by [15], Theorem 7.5. Then G embeds in U_{n′}(Z)wrS_{m′}, which is real-time combable with polynomially bounded length function, by Corollary 4.6 and Propositions 4.1 and 4.2. □

References

[1] Alfred V. Aho, Indexed grammars - an extension of context-free grammars, J. Assoc. Comp. Math 15 (1968), 647–671.

[2] Alfred V. Aho, Nested stack automata, J. Assoc. Comp. Mach. 16 (1969), 383–406.

[3] G. Baumslag, C.F. Miller III and H. Short, Isoperimetric inequalities and the homology of groups, Invent. Math. 113 (1993), 531–560.

[4] Gilbert Baumslag, Michael Shapiro and Hamish Short, Parallel poly pushdown groups, to appear in J. Pure and Applied Algebra.

[5] Martin R. Bridson, Combings of semidirect products and 3-manifold groups, Geometric and Functional Analysis 3 (1993), 263–278.

[6] Martin R. Bridson, On the geometry of normal forms in discrete groups, Proc. London Math. Soc. 67 (1993), 596–616.

[7] M.R. Bridson and R. H. Gilman, Formal language theory and the geometry of 3-manifolds, Commentarii Math. Helv. 71 (1996) 525–555.

[8] José Burillo, Lower bounds of isoperimetric functions for nilpotent groups, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 25, AMS 1996, 1–8.

[9] David B.A. Epstein J.W. Cannon, D.F. Holt, S. Levy, M. S. Patterson and W. Thurston, Word processing in groups, Jones and Bartlett, 1992.

[10] S.M. Gersten, Isodiametric and isoperimetric inequalities in group extensions, preprint (available electronically), University of Utah, 1991.

[11] S.M. Gersten and H. B. Short, Rational subgroups of biautomatic groups, Ann. Math. (2) 134 (1991) 125–158.

[12] Robert H. Gilman, Formal languages and infinite groups, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, AMS 1996, 27–51.

[13] Robert H. Gilman, A shrinking lemma for indexed languages, Theoret. Comput. Sci. 163 (1996) 277–281.

[14] M. Gromov, Geometric Group Theory, Vol. 2, Asymptotic invariants of infinite groups LMS Lecture Notes Series 181, ed. Graham A. Niblo and Martin A. Roller, CUP 1993.

[15] Philip Hall, Nilpotent groups, Notes of lectures given at the Canadian Mathematical Congress, Alberta, 1957, re-published by Queen Mary College, University of London, 1969.

[16] T. Hayashi, On derivation trees of indexed grammars, Publ. RIMS Kyota Univ. 9 (1973) 61–92.

[17] John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.

[18] A I Malc̆ev, On some classes of infinite soluble groups, Mat. Sbornik 28 (1951) 567-88 and Amer. Math. Soc. Transl (2) 2 (1956) 1–21.

[19] Christophe Pittet, Isoperimetric inequalities for homogeneous nilpotent groups, in Geometric group Theory, Ohio State University Mathematical Research Institute Publ. 3, ed. R. Charney, M. Davis and M. Shapiro, De Gruyter, Berlin 1995, 159–164.

[20] Michael O. Rabin, Real time computation, Israel J. Math 1 (1963) 203– 211.

[21] Sarah Rees, A language theoretic analysis of combings, preprint, 1997.

[22] Derek J.S. Robinson, Splitting theorems for infinite groups, Symposia Mathematica 17, Convegni del Novembre e del Dicembre 1973, Academic Press, 1976, 441–470.

[23] A. Rosenberg, Real-Time Definable Languages, J. Assoc. Comput. Mach., 14 (1967) 645–662.

[24] D. Segal, Polycyclic Groups, Cambridge University Press, 1983.