POLYNOMIAL DEHN FUNCTIONS AND THE LENGTH

OF ASYNCHRONOUSLY AUTOMATIC STRUCTURES

Martin R. Bridson

University of Oxford

Abstract. We extend the range of observed behaviour among length functions of optimal asynchronously automatic structures. We do so by means of a construction that yields asynchronously automatic groups with finite aspherical presentations where the Dehn function of the group is polynomial of arbitrary degree. Many of these groups can be embedded in the automorphism group of a free group. Moreover, the fact that the groups have aspherical presentations makes them useful tools in the search to determine the spectrum of exponents for second order Dehn functions. We contribute to this search by giving the first exact calculations of groups with quadratic and superquadratic exponents.

It is now well-known that there exist sequences of finitely presented groups such that the (first order) Dehn function of the nth group in the sequence is polynomial of degree n (see [Gr], [BMS], [BP]). The first such sequences to be discovered were nilpotent groups, as one might expect with a polynomial phenomenon in group theory. The first purpose of the present paper is to construct examples of a quite different nature. These examples arise in two areas of group theory where the only nilpotent groups that arise are virtually abelian, namely the study of automorphisms of free groups and automatic group theory.

We shall prove the following result in Section 3 by combining some general results about the Dehn functions of semi-direct products (in particular Corollary 2.8) with results concerning the growth of automorphisms of free groups (see 3.3). Our general results concerning semidirect products can be used to calculate isoperimetric functions in a number of other geometrically and algebraically interesting situations (e.g., Examples 2.9 and 3.8).

Theorem A. For every positive integer d there exist finitely presented free-by-free groups Γ_{d} such that the Dehn function of Γ_{d} is ≃ polynomial of degree d.

A simple embedding lemma, 4.1, yields the following consequence of Theorem A. I do not know if the the inequality m ≤ n − 1 in this corollary is optimal.

Typeset by AMS-TEX

The author is an EPRSC Advanced Fellow. The research presented in this article was also funded in part by NSF grant DMS-9401362 and a Fellowship from the FNRS (Switzerland).

Corollary B. Let Out(F_{n}) denote the outer automorphism group of a free group of rank n. For every positive integer m ≤ n−1 there exist finitely presented subgroups of Out(F_{n}) whose Dehn functions are ≃ polynomial of degree m.

Automatic group theory is the study of groups which lend themselves to calculations on finite state automata — one-tape automata in the case of synchronously automatic groups and two-tape automata in the case of asynchronously automatic groups. (See Section 2 for basic definitions concerning automatic structures and their length functions and see [E+] for a comprehensive introduction to automatic group theory.) In both the synchronous and asynchronous case, the existence of the automata implies that one has a regular combing of the group (as defined in Section 2 below). In the synchronous case, the workings of the one-tape comparator automata force this combing to be quasi-geodesic, so in particular the length of the combing line joining the identity to each element of the group g ∈ G is bounded above by a linear function of d(1, g). Among the groups whose structures have been explored in the literature, one finds only two types of behaviour among the length functions of optimal asynchronously automatic structures — linear and exponential. We add to this list of possibilities.

Finitely presented free-by-free groups are asynchronously automatic, and the method that we shall use to prove Theorem A establishes the following result.

Theorem C. For each positive integer d there exists an asynchronously automatic group Γ_{d} such that the length of the optimal asynchronously automatic structures for Γ_{d} is polynomial of degree d.

A significant respect in which the examples described in Theorem A differ from the early examples of groups with polynomial Dehn functions is that they have aspherical presentations. (Aspherical examples whose Dehn functions display a much greater range of behaviour were subsequently discovered by Sapir et al. [SBR]; see also [BB1]). This asphericity property, together with certain additional properties of diagrams for these groups (see 1.5 and 3.4), has played an important role in recent work on second order Dehn functions (see [A+], [WP] and references therein). The second order Dehn function of a group (which is defined in Section 5 below) measures the difficulty of filling 2-spheres in the 3-skeleton of any Eilenberg-MacLane space K(G, 1) with compact 3-skeleton. More generally, the kth order Dehn function measures the difficulty of filling k-spheres in a K(G, 1) with compact (k + 1)-skeleton.

Sections 5 and 6 of the present article are dedicated to the study of second and higher order Dehn functions. In the course of our brief discussion of the foundations of the subject, we shall describe what might be an interesting invariant with which to study aspherical 2-complexes (see 5.10). Our main goal, though, is to extend the current state of knowledge concerning the spectrum of second order Dehn exponents.

Theorem D. There exist finitely presented groups Γ_{2} and Γ_{3}, each with a compact 3-dimensional Eilenberg-MacLane space, such that the second order Dehn function of Γ_{2} is quadratic and the second order Dehn function of Γ_{3} is cubic.

Most of the material in the first four sections of this paper was written while I was visiting the University of Geneva for the year 1992-93. I thank André Haefliger for arranging this visit and the Swiss National Science Foundation for financing it. The impetus for updating and publishing this material now came from its applications to second order Dehn functions — see [A+] and [WP]. I thank Steve Pride for his interest in my results and for his part in animating them with applications. I also wish to thank him for a stimulating conversation at the BMC in April 1999. In that conversation Steve brought to my attention the fact that there were no calculations describing second order Dehn functions that were exactly ≃ equivalent to n^{2} or any super-quadratic function (question 1 of [WP]), and my attempts to provide such calculations resulted in Sections 5 and 6 of the present article. Finally, I thank that referee for his/her careful reading and useful comments.

Section 1: First Order Dehn functions Section 2: The Length of Automatic Structures Section 3: Theorems A and C, and the Growth of Automorphisms Section 4: Subgroups of Aut(F_{n}) Section 5: Second and Higher Order Dehn functions Section 6: Showing n^{2} and n^{3} to be Second Order Dehn functions

Section 1: First Order Dehn functions

We recall some basic definitions concerning first order Dehn functions.

Given a finitely presented group G = ⟨A | R⟩ and a word w in the generators A^{±1} that represents 1 ∈ G, one defines

Area(w) = min{N ∈ ℕ^{+} | ∃ equality w = ∏_{j=1}^{N} u_{j}r_{j}u_{j}^{−1} in F (A) with r_{j} ∈ R^{±1}} .

The Dehn function δ(n) of the finite presentation ⟨A | R⟩ is defined by

δ(n) = max{Area(w) | w ∈ ker(F (A) ↠ G), |w| ≤ n } ,

where |w| denotes the length of the word w. It is straightforward to show (see [A]) that the Dehn functions of any two finite presentations of the same group are ≃ equivalent in the following sense (and modulo this equivalence relation it therefore makes sense to talk of “the” Dehn function of a finitely presented group).

Given two functions f, g : [0, ∞) → [0, ∞), one defines f ≼ g if there exists positive constants a, b, c, d, e such that

f(n) ≤ ag(bn + c) + dn + e for all n ≥ 0;

if f ≼ g and g ≼ f, then one says that f and g are ≃ equivalent.

For future reference, we note that in order to get ≼ bounds on increasing functions, it suffices to consider relatively rare sequences of integers:

1.1 Remark. Let f, g : [0, ∞) → [0, ∞) be non-decreasing functions and let (n_{i}) be an increasing sequence of positive integers with n_{0} = 0 and n_{i+1} ≤ Cn_{i} for all i ≥ 1, where C ≥ 1 is constant. If f(n_{i}) ≤ g(n_{i}) for all i ≥ 1 then f ≼ g. Indeed, given x ∈ [0, ∞) there exists i such that n_{i} ≤ x ≤ n_{i+1}, whence f(x) ≤ f(n_{i+1}) ≤ g(n_{i+1}) ≤ g(Cn_{i}) ≤ g(Cx).

According to van Kampen’s lemma (see [vK], [LS] or [BH, I.8A]) an equality w = ∏_{j=1}^{N} u_{j}r_{j}^{±1}u_{j}^{−1} in the free group A can be portrayed by a finite, 1-connected, planar, combinatorial 2-complex with basepoint: this complex is called a van Kampen diagram for w; its oriented 1-cells are labelled by elements of A^{±1}; the boundary label on each 2-cell (read with positive orientation from one of its vertices) is an element of R^{±1}; and the boundary cycle of the complex (read with positive orientation from the basepoint) is the word w. If N = Area(w) then the number of 2-cells in the van Kampen diagram portaying the given equality is N. Conversely, a van Kampen diagram with M 2-cells gives rise to an equality in F (A) expressing the word labelling the boundary cycle of the diagram as a product of M conjugates of the defining relations. Thus Area(w) is the minimum number of 2-cells among all van Kampen diagrams for w.

Canonically associated to the presentation ⟨A | R⟩ there is a combinatorial 2complex X = K(A; R) whose 1-cells ε_{a} correspond to the generators A and whose 2-cells e_{r} correspond to the relators R: associated to ε_{a} we have the two directed edges ε_{a}^{+} and ε_{a}^{−}; there is a natural correspondence between words in the free monoid on A^{±1} and edge-paths in X — the word ∏_{i=1}^{n} a_{i}^{ϵ_{i}}, where ϵ_{i} = ±1, corresponds to the concatenation of the edges ε_{i}^{ϵ_{i}}; the attaching map of the 2-cell corresponding to r ∈ R is a monotone parameterization of the path corresponding to the word r.

Let C be the Cayley graph of G = ⟨A | R⟩ with respect to A. The 1-skeleton X̃^{(1)} of the universal cover X̃ of X has a labelling induced from X. By choosing a base vertex v_{0} ∈ X̃ and identifying each g ∈ G with g.v_{0} ∈ X̃ we obtain an identification of labelled graphs X̃^{(1)} ≅ C. Edge-paths in X lift uniquely to edge-paths in X̃^{(1)} beginning at v_{0}; a word represents the identity if and only if this lifted path is a loop (i.e., ends at v_{0}). Van Kampen diagrams describe (combinatorial) null-homotopies of these edge-loops. Given a van diagram D for w there is a unique label-preserving combinatorial map D → X̃ sending the basepoint of D to v_{0} ∈ X̃; this map sends the boundary of D to the loop labelled w; we denote this map D̃.

Area for Aspherical Presentations.

The following simple observation provides a tool for getting lower bounds on Dehn functions (indeed on abelianized isoperimetric functions in the sense of [BMS]

— see remark (3) following the lemma).

1.2 Lemma. Suppose that X = K(A : R) is aspherical. Let D be a van Kampen diagram for w. If the associated map D̃ to X̃ is injective on the complement of the 1-skeleton in D, then the number of 2-cells in D is Area(w).

Proof. Let D′ be a second van Kampen diagram for w. Let ϕ : 𝕊^{1} → D and ϕ′ : 𝕊^{1} → D′ be monotone parameterizations of the boundary cycles ∂D and ∂D′ such that the compositions Φ := D̃|_{∂D} ∘ ϕ and Φ′ := D̃′|_{∂D′} ∘ ϕ′ agree. The maps D̃ and D̃′ together with the map from the annulus A = 𝕊^{1} × [0, 1] to X̃ given by (θ, t) ↦ Φ(θ) induce a continuous map σ : 𝕊^{2} → X̃, where 𝕊^{2} is viewed as the quotient of D ∐ A ∐ D′ by the relation [(θ, 0) ∼ ϕ(θ), (θ, 1) ∼ ϕ′(θ), ∀θ ∈ 𝕊^{1}].

Let p : X̃ → \overline{X} be the quotient of X̃ by the equivalence relation that identifies the 1-skeleton to a point. \overline{X} is the one-point union of 2-spheres indexed by the 2-cells of X̃, so π_{2}\overline{X} is the free abelian group on the set of 2-cells. Since π_{2}X̃ = 0, we see that [p ∘ σ] ∈ π_{2}\overline{X} is 0. But [p ∘ σ] is the sum of the generators of π_{2}\overline{X} corresponding to the faces of D and the faces of D′. Since the former must cancel out the latter, D′ has at least as many faces as D. □

Remarks.

(1) In order that D̃ should satisfy the hypothesis of (1.2), it suffices (but is not necessary) that it be injective on the 0-skeleton of D.

(2) Instead of invoking homotopy at the end of the proof of (1.2) we could have worked with homology: one can regard D̃ − D̃′ as a 2-cycle in the cellular chain complex of X̃; since there are no 3-cells and H_{2}X̃ is trivial, this 2-cycle must be zero, and since the 2-cells in the image of D̃ are all distinct, the 2-cells in D̃′ must cancel them out. This argument actually shows something a little stronger than the statement of (1.2): if D̃ = ∑_{i=1}^{N} c_{i} in the cellular chain complex of X̃ (where the c_{i} are 2-cells) then N ≥ Area(w). Thus one can use (1.2) to obtain lower bounds on homological isoperimetric functions (cf. [Ge]).

Lower Bounds and t-Corridors.

The preceding lemma provides a tool for establishing lower bounds on Dehn functions. We shall need one other technique for doing so — t-corridors, whose use is now well-established. This technique is useful in situations where one has finite presentations of the form P_{0} = ⟨A, t_{1}, …, t_{n} | R⟩, where the symbols t_{j} are not elements of A and the only relators involving any t_{j} are of the form t_{j}^{−1}u_{i}t_{j}v_{i} ∈ R, where u_{i}, v_{i} ∈ F (A). Consider a van Kampen diagram D over such a presentation and focus on an edge in the boundary labelled t ∈ {t_{1}, …, t_{n}}. If this edge lies in the boundary of a 2-cell, then the boundary cycle of this 2-cell has the form t^{−1}utv (read with suitable orientation from a suitable point). In particular, there is a unique other edge in the boundary of the 2-cell that is labelled t; crossing this edge we enter another 2-cell with a similar boundary label. Iterating the argument we get a chain of 2-cells running across the diagram; this chain terminates at an edge of ∂D which (following the orientation of ∂D in the direction of our original edge labelled t) is labelled t^{−1}. This chain of 2-cells is called a t-corridor. Topologically, a t-corridor is a map [0, 1] × [0, 1] → D that is injective on (0, 1) × [0, 1]. We can make this map a morphism of labelled combinatorial 2-complexes by pulling back the cell structure and labelling from D. The labels on the 1-cells in [0, 1] × {0, 1} (the top and bottom sides of the corridor) are letters from A^{±1}; the remaining 1-cells are of the form {s} × [0, 1], and these are labelled t.

We refer to [BG] for a more detailed account of t-corridors. We shall need only three (basic and evident) facts:

(1) distinct t-corridors have disjoint interiors;

(2) if P is the edge-path in D running along the top or bottom of a t-corridor, then P is labelled by a word in the letters A^{±1} that is equal in |P_{0}| to the words labelling the subarcs of ∂D which share the endpoints of P (given appropriate orientations);

(3) and if k = min{max_{i} |u_{i}|, max_{i} |v_{i}|}, then the number of 2-cells in the tcorridor is at least 1/k times the length of P.

1.3 Lemma. Let ϕ be an automorphism of the finitely presented group B = ⟨A | S⟩. For each a ∈ A, choose a word v_{a} ∈ F (A) representing ϕ(a) ∈ B. Let G = ⟨A, t_{1}, t_{2} | R⟩, where R = S ∪ {t_{j}^{−1}at_{j} = v_{a} | a ∈ A, j = 1, 2}. Then the Dehn function of G is ≃ bounded below by

n ↦ n max_{b}{d_{A}(1, ϕ^{n}(b)) | d_{A}(1, b) ≤ n}.

Proof. For each positive integer n, we choose a word β of length at most n in the generators A^{±1} so as to maximize d_{A}(1, ϕ^{n}(b)), where b is the image of β in G.

Let u_{n} := t_{1}^{−n}βt_{1}^{n} and let w_{n} := u_{n}(t_{2}t_{1}^{−1})^{n}u_{n}^{−1}(t_{2}t_{1}^{−1})^{−n}, a word of length at most 10n. Note that w_{n} = 1 in G. Note also that no proper subword of w_{n} is equal to 1 ∈ G (one sees this easily using the natural retraction G → F (t_{1}, t_{2}) and the fact that t_{j}^{−i}βt_{j}^{i} ≠ 1 for all i). It follows that any van Kampen diagram for w_{n} is a disc, in particular every edge of ∂D lies in the closure of some 2-cell, and therefore a t_{j}-corridor emanates from each edge of ∂D labelled t_{j}, for j = 1, 2.

The simple fact that distinct t_{j}-corridors cannot cross (fact (1)) implies that the pattern of t_{2}-corridors in any van Kampen diagram for w_{n} must be as shown in figure 1.1. The words in the letters A^{±1} labelling the bottom of each t_{2}-corridor is equal in G to u_{n}, as is the top of the t_{1}-corridors between them. Hence (fact (3)) each of these corridors contains at least d_{A}(1, ϕ^{n}(b)) 2-cells. And there are n such corridors. □

Fig. 1.1. Pattern of t-corridors for w_{n} and v_{n}

1.4 Example. Consider the presentation of G given in (1.3). Choose a word β′ of length at most n so as to maximize the sum ∑_{i=0}^{n} d_{A}(1, ϕ^{i−1}(b′)), where b′ is the image of β′ in G. Let v_{n} = t_{1}^{−n}β′t_{1}^{n}t_{2}^{−n}β′^{−1}t_{2}^{n}. By counting the area of corridors (see figure 1.1) we see that

Area(v_{n}) ≥ 2 max_{b}{∑_{i=0}^{n−1} d_{A}(1, ϕ^{i}(b)) | d_{A}(1, b) ≤ n}.

If B is free, we claim that one gets an exact calulcation for the area of the words w_{n} and v_{n}:

Area(v_{n}) = 2 ∑_{i=0}^{n−1} d_{A}(1, ϕ^{i}(b′))

Area(w_{n}) = 2 ∑_{i=0}^{n−1} d_{A}(1, ϕ^{i}(b′)) + 2d_{A}(1, ϕ^{n}(b)).

In the light of (1.2) and (1.3), in order to prove this assertion it suffices to exhibit van Kampen diagrams D for w_{n} and v_{n} such that the associated map D̃ is injective on the 1-skeleton and to calculate the area of D. To obtain such a diagram for v_{n}, one begins with a collection of t-corridors as shown in figure 1.1, where the words on the top side of each corridor in the upper half of the diagram and bottom side in the lower half are reduced words. One reduces the labels on the remaining sides as shown in figure 1.2. One then identifies the sides of the adjacent (folded) corridors to obtain the desired injective diagram D. (A simple calculation with HNN normal form shows that the map D̃ is injective on the 0-skeleton of D.) The construction for w_{n} is entirely similar.

Fig. 1.2. Folding Corridors

Section 2. The Length of Automatic Structures

Let G be a group with finite generating set A. A combing (or normal form) for G consists of a choice of a word in the free monoid on A^{±1} to represent each g ∈ G. In other words, a combing is a section of the natural projection μ : (A^{±1})^{∗} → G.

In order to compare words geometrically it is useful to regard (A^{±1})^{∗} as a subset of the set of discrete paths in G (eventually constant maps ℕ → G). To do so, one identifies w ∈ (A^{±1})^{∗} with the path t ↦ w(t), where w(t) is the image in G of the prefix of length t in w. (This also allows one to compare words from different finite generating sets for G.) We consider the following pseudometric on discrete paths.

2.1 Definitions. Fix a word metric d on G. Given eventually constant paths p_{1}, p_{2} : ℕ → (G, d), define

D(p_{1}, p_{2}) := min_{ρ,ρ′∈R} { max_{t∈ℕ} {d(p_{1}(ρ(t)), p_{2}(ρ′(t))}},

where

R = {ρ : ℕ → ℕ | ρ(0) = 0; ρ(n + 1) ∈ {ρ(n), ρ(n) + 1} ∀n; ρ unbounded}.

A combing σ : G → (A^{±1})^{∗} is said to be asynchronously bounded if there is a constant k > 0 such that D(σ(g), σ(h)) ≤ k d(g, h) for all g, h ∈ G. And two combings σ : G → (A^{±1})^{∗} and σ′ : G → (B^{±1})^{∗} are said to be equivalent if there exists a constant K > 0 such that D(σ(g), σ′(g)) ≤ K for all g ∈ G. (The existence of the constants k and K does not depend on the choice of word metric d, but their values do.)

A combing σ : G → (A^{±1})^{∗} is an asynchronously automatic structure for G if σ is asynchronously bounded and σ(G) ⊂ (A^{±1})^{∗} is a regular language (i.e. there is a finite state automaton that decides membership of σ(G)). Groups which admit asynchronously automatic structures are called asynchronously automatic. We refer to [E+] for the basic theory of (asynchronously) automatic groups.

Following [B1], we define the length of a combing σ : G → (A^{±1})^{∗} to be the function

L_{σ}(n) := max {|σ(g)| | d(1, g) ≤ n},

where |σ(g)| denotes word length. Since any two word metrics on G are Lipschitz equivalent, the ≃ equivalence class of L_{σ}(n) is independent of the choice of d, but simple examples show that it is not independent of the choice of σ within its equivalence class.

2.2 Lemma. Let G be a finitely generated group. If two asynchronously automatic structures σ, σ′ on G are equivalent, then their length functions are ≃ equivalent.

Proof. By definition, there exists a constant K > 0 such that D(σ(g), σ′(g)) ≤ K for all g ∈ G. Fix g ∈ G and choose parameterizations ρ and ρ′ that yield the minimum in the definition of D. We may assume that until ρ and ρ′ finally become constant, at least one of {ρ(n + 1), ρ(n)} and {ρ′(n + 1), ρ′(n)} has cardinality two.

We claim that there is a bound on how long σ′(g) ∘ ρ′ can remain static before reaching its endpoint. Indeed if this were not the case then there would be arbitrarily long subwords of σ(g) that were contained in the K-neighbourhood of some point of G. But this would force σ(g) to revisit some element x ∈ G more than V times, where V is the number of states in a finite state automaton recognising the regular language σ(G). This would imply that some subword u of σ(g) (a subword corresponding to the subpath traversed between visits to x) was the label on a loop in the automaton. This would mean that we could replace u in σ(g) by an arbitrary power u^{r} without leaving the regular language σ(G). The words obtained from σ(g) in this manner would be equal to g in G, contradicting the fact that the natural map σ(G) → G is a bijection. □

By replacing σ′(g) with σ(g′) in the above proof, we see that there is a constant K′ > 0 such that the difference between |σ(g)| and |σ(g′)| is at most K′ if d(g, g′) = 1. Iterating this estimate we obtain:

2.3 Lemma. L_{σ}(n) ⪯ 2^{n} for all asynchronously automatic structures σ.

2.4 Questions.

(1) Which ≃ equivalence classes of functions arise as the length functions of asynchronously automatic structures?

(2) Given an asynchronously automatic group G, does there exist an optimal asynchronously automatic structure, i.e. an asynchronously automatic structure σ such that L_{σ}(n) ⪯ L_{σ′}(n) for all asynchronously automatic structures σ′ on G.

(3) Which ≃ equivalence classes of functions arise as the length functions of optimal asynchronously automatic structures?

(4) Are (synchronously) automatic groups precisely those asynchronously automatic groups with an optimal structure of ≃ linear length?

One can often get upper bounds on the length of asynchronously automatic structures for a group G by analyzing explicit constructions. One can get lower bounds by calculating Dehn functions and appealing to the following fact from [B2].

2.5 Proposition. If a finitely generated group G admits a combing σ that is asynchronously bounded, then G is finitely presented and its Dehn function is ⪯ nL_{σ}(n).

2.6 Examples. There are many asynchronously automatic groups with exponential Dehn functions, e.g. ⟨a, t | t^{−1}at = a^{2}⟩. By combining Lemma 2.3 and Proposition 2.5 we see that every asynchronously automatic structure σ on such a group satisfies L_{σ}(n) ≃ 2^{n}. The class of synchronously automatic groups provides numerous examples of groups for which the optimal asynchronously automatic structures have length ≃ n. One of the main points of this article is to provide examples of asynchronously automatic groups Γ_{m} for which the length of the optimal structures is polynomial of degree m, where m is any positive integer. This is the content of Theorem C, which was stated in the introduction and will be proved in the next section. Here is one such class of groups:

Γ_{m} = ⟨a_{1}, …, a_{m}, t_{1}, t_{2} | for j = 1, 2, t_{j}^{−1}a_{m}t_{j} = a_{m} & t_{j}^{−1}a_{i}t_{j} = a_{i}a_{i+1}, i < m ⟩.

Given a linearly-ordered finite set A, one has the associated Lex-least ordering on the free monoid A^{∗} — one word is less than another if it is shorter or else has the same length but occurs first in the dictionary. The Lex-least combing of a group H with a linearly-ordered finite generating set A = A^{−1} is the map H → A^{∗} that associates to each h ∈ H the Lex-least word in A^{∗} representing h.

The following is a special case of the Main Lemma in [B2].

2.7 Proposition. Let H be a hyperbolic group with a finite, ordered, generating set A = A^{−1} and let σ_{H} : H → A^{∗} be the associated Lex-least combing. Let F be a group with an asynchronously automatic structure σ_{F} : F → B^{∗}.

Given a homomorphism Φ : F → Aut(H), written f ↦ Φ_{f}, one obtains an asynchronously automatic structure for the associated semi-direct product H ⋊_{Φ} F by defining σ(fh) := σ_{F} (f)σ_{H}(h) for all h ∈ H and f ∈ F. Moreover,

L_{σ}(n) ⪯ L_{σ_{F}} (n) + λ_{Φ}(n),

where

λ_{Φ}(n) := max{d_{A}(1, Φ_{V_{1}}(u_{1}) … Φ_{V_{m}}(u_{m})) | V_{i} = v_{i} … v_{m}, ∑_{i=1}^{m} |u_{i}| + ∑_{i=1}^{m} |v_{i}| = n}.

In particular, if L_{σ_{F}} (n) ≃ n then L_{σ}(n) ≃ λ_{Φ}(n).

Proof. The only point that is not explicit in [B2] is the calculation of L_{σ}. Given h ∈ H and f ∈ F one chooses a geodesic u_{1}v_{1} … u_{m}v_{m} representing fh where u_{i} is a word in the letters A^{±1} and v_{i} is a word in the letters B^{±1}. Writing V_{i} = v_{i} … v_{m}, in the free group on A ∪ B we have the equality

u_{1}v_{1} … u_{m}v_{m} = V_{1}U_{1} … U_{m},

where U_{i} := V_{i}^{−1}u_{i}V_{i}. By definition U_{i} = Φ_{V_{i}}(u_{i}) in H, and hence the geodesic σ_{H}(h), whose endpoint in H is U_{1} … U_{m}, has length d_{A}(1, Φ_{V_{1}}(u_{1}) … Φ_{V_{m}}(u_{m})). And |V_{1}| ≤ n, so σ_{F} (f) = σ_{F} (V_{1}) has length at most L_{σ_{F}} (n). □

2.8 Corollary. Let H be a hyperbolic group and let F be a finitely generated free group of rank at least two. Suppose that the kernel of Φ : F → Aut(H) is nontrivial. Then

(1) H ⋊_{Φ} F has an asynchronously automatic structure of length ≃ λ_{Φ}(n) and this is optimal;

(2) the Dehn function of H ⋊_{Φ} F is ≃ nλ_{Φ}(n).

Proof. Part (1) is an immediate consequence of (2), the proposition, and (2.5).

In order to prove (2), we choose a finite presentation ⟨A | R⟩ for H and fix a nontrivial element t ∈ F. Since passing to a subgroup of finite index in F does not effect the assertions that we are trying to prove, we may appeal to Marshall Hall’s theorem and assume that t is primitive, belonging to a basis B say. By appending relations S describing the action of B on H, from ⟨A | R⟩ we obtain a presentation ⟨A, B | R, S⟩ for H ⋊_{Φ} F in which the only relations involving t are the commutators [a, t], a ∈ A. Let W_{n} be a word u_{1}v_{1} … u_{m}v_{m} in the form considered in the preceding proof, chosen with |W_{n}| ≤ n so as to maximize d_{A}(1, Φ_{V_{1}}(u_{1}) … Φ_{V_{m}}(u_{m})) where V_{i} = v_{i} … v_{m}. As in Lemma 1.3, a simple estimate with t-corridors implies that w_{n} := W_{n}t^{n}W_{n}^{−1}t^{−n} has area at least nλ_{Φ}(n). Thus we obtain the desired lower bound on the Dehn function of H ⋊_{Φ} F. The complementary upper bound is an immediate consequence of the proposition and (2.5). □

2.9 Example. A renowned construction due to Chuck Miller [Mi] gives examples of residually finite groups in which the conjugacy problem is unsolvable. These groups are of the form Γ = F_{n} ⋊_{Φ} F_{m}, where F_{n} and F_{m} are finitely generated free groups. One can easily show that λ_{Φ}(n) ≃ n^{2}, and the kernel of Φ contains primitive elements. Thus we see that the Dehn functions of these groups are cubic.

Section 3: Theorems A and C, and the Growth of Automorphisms

In this section we shall prove Theorems A and C. In order to do so, we specialize the preceding discussion to the case where F is free and Φ : F → Aut(H) has cyclic image, ⟨ϕ⟩ say. We shall use the notation H ⋊_{(ϕ)} F to denote this situation. Note that one can choose a basis {t_{1}, …, t_{r}} for F so that each t_{j} acts as ϕ, or (replacing t_{i} by t_{i}t_{1}^{−1} for i > 1) one can choose t_{1} to act as ϕ and the other t_{i} to act trivially. In particular, Corollary 2.8 applies, so in order to calculate the Dehn function of H ⋊_{(ϕ)} F we need only calculate λ_{Φ}(n). In the current setting, λ_{Φ}(n) is a measure of the growth of ϕ ∈ Aut(H). Let us consider how it relates to other measures of growth.

3.1 Definitions. Let G be a group with a fixed finite generating set A and associated word metric d. To each automorphism ϕ we can associate the integer ∥ϕ∥ := max{d(1, ϕ(a)) | a ∈ A}. We wish to disuss the growth of ϕ. To this end we consider the following functions.

g_{0,ϕ}(n) = ∥ϕ^{n}∥.

g_{1,ϕ}(n) = ∑_{r=1}^{n} ∥ϕ^{r}∥

g_{2,ϕ}(n) = max{∑_{i=1}^{n} d(1, ϕ^{i}(b)) : d(1, b) ≤ n}.

g_{3,ϕ}(n) = max{d_{A}(1, ϕ^{r_{1}}(u_{1}) … ϕ^{r_{m}}(u_{m})) | ∑_{i=1}^{m} |u_{i}| ≤ n, ∑_{i=1}^{m} |r_{i} −r_{i−1}| ≤ n, r_{0} = 0}

It is easy to see that all of these functions are ≃ independent of the choice of word metric.

Note that, in the notation of Section 2, the function g_{3,ϕ}(n) is ≃ equivalent to λ_{Φ}(n) in the case where Φ : ℤ → Aut(G) has image ⟨ϕ⟩ (indeed we could have made them identical if we did not want the convenience of having slightly different sums bounded by n in the general case).

According to the context, one of the above measures of growth may be more appropriate than the others, or one may wish to consider some variation on these definitions.

3.2 Proposition. If G is a free group or a free abelian group, then n g_{0,ϕ}(n) ≃ g_{1,ϕ}(n) ≃ \frac{1}{n}g_{2,ϕ}(n) ≃ g_{3,ϕ}(n).

Proof in the abelian case. We fix a basis A for G ≅ ℤ^{m}, thus realising ϕ^{n} ∈ Aut(G) as an integer matrix. The norm ∥ϕ^{n}∥ is then the maximum of the ℓ_{1} norms of the columns of ϕ^{n}, and n ↦ ∥ϕ^{n}∥ is either exponential (the case where ϕ has an eigenvalue of absolute value bigger than one) or else some power of ϕ is unipotent in which case ∥ϕ^{n}∥ ≃ n^{r}, where (r + 1) is the size of the largest block in the Jordan form of that power — see [BG]. The proposition is trivial in the exponential case. Thus we may concentrate on the polynomial case, where there is an obvious reduction to the case where ϕ is a unipotent matrix consisting of a single Jordan block.

We are left to consider the growth of an (m, m) matrix M that has ones on the diagonal and super-diagonal and all other entries zero. If p > m, the largest entry in M^{p} will be \binom{p}{m−1} in the top right corner. Thus the maximum of the ℓ_{∞}-norms of the columns of M^{p} is \binom{p}{m−1} ≃ p^{m−1}, and this maximum is always realised by the right-most column.

The largest entry in M^{−p}, for all p ∈ ℕ, is also in the top right corner. This entry is (−1)^{m−1}\binom{p+m−2}{m−1}.

Since the ℓ_{∞}-norm on the columns of M is Lipschitz equivalent to the ℓ_{1}-norm, we deduce that the functions ℕ → ℕ given by n ↦ ∥M^{n}∥ and n ↦ ∥M^{−n}∥ are both ≃ n^{m−1}, and moreover one can restrict attention to a single basis element a ∈ A when calculating all but finitely many ∥M^{n}∥. The ≃ equivalences asserted in the proposition (and, in fact, Lipschitz equivalence) follow easily.

The nonabelian case. (cf. Remark 3.7(2)) In the case where G is a non-abelian free group, one uses the existence of relative train-track representatives in place of Jordan form (see [BeH]). Again one gets a dichotomy of exponential versus polynomial growth (see [BFH1,2]), and in the polynomial case one can calculate norms of iterates by looking at what happens to a single generator. But in order to make what follows independent of the train-track technology, instead of giving more details of the proof in the general case we work through an example that is sufficient for the proofs of Theorems A and C.

3.3 Example. Let G = F_{m} be the free group with basis A = {a_{1}, …, a_{m}} and let ϕ be the automorphism

ϕ(a_{m}) = a_{m} and ϕ(a_{i}) = a_{i}a_{i+1} for i < m.

The inverse of ϕ fixes a_{m} and for i < m

ϕ^{−1}(a_{i}) = a_{i}a_{i+2}a_{i+4} … a_{m}^{(−1)^{m−i}} … a_{i+3}^{−1}a_{i+1}^{−1}

(where symbols with subscripts greater than m are by convention the empty word). Because ϕ is a positive automorphism, for all positive integers n we have ∥ϕ^{n}∥ = ∥ϕ_{ab}^{n}∥, where ϕ_{ab} ∈ GL(m, ℤ) describes the action of ϕ on the abelianization of F_{m}, and where both norms are taken with respect to the fixed basis A. With respect to this basis ϕ_{ab} is a unipotent matrix with a single Jordan block, i.e. it has ones on the diagonal and super-diagonal and all other entries are zero. Thus n ↦ ∥ϕ^{n}∥ is polynomial of degree (m − 1).

Although ϕ^{−1} is not a positive automorphism, we claim that it is still true that ∥ϕ^{−n}∥ = ∥ϕ_{ab}^{−n}∥. To see this, note that as one takes successive iterates ϕ^{−n}(a_{i}), with a_{i} fixed, the letters a_{i+2k} (“even i-index letters”) spawn positive powers of other even i-index letters and negative powers of odd i-index letters, and likewise the symbols of odd i-index a_{i+2k+1}^{−1} will spawn only positive powers of even iindex letters and negative powers of odd i-index letters. It follows that there is no cancellation when we take the image in ℤ^{m} of the (naively expanded) word ϕ^{−n}(a_{i}), and therefore ∥ϕ^{n}∥ = ∥ϕ_{ab}^{n}∥ for all n ∈ ℤ. In particular, following the above discussion of the growth of integer matrices, we see that g_{1,ϕ}(n) is polynomial of degree m and n g_{0,ϕ}(n) ≃ g_{1,ϕ}(n) ≃ \frac{1}{n}g_{2,ϕ}(n) ≃ g_{3,ϕ}(n). Moreover, r ∥ϕ^{n}∥ = d_{A}(1, ϕ^{n}(a_{1}^{r})) for all positive integers r, n.

3.4 Proof of Theorems A and C. Let ϕ ∈ Aut(F_{m}) be as in the preceding example and consider Γ_{m} = F_{m} ⋊_{(ϕ)} F_{r}, where r ≥ 2. (An explicit presentation for the groups Γ_{m} in the case r = 2 is given in (2.6).)

As we noted above, in this setting λ_{Φ}(n) ≃ g_{3,ϕ}(n), and we have just seen that g_{3,ϕ}(n) ≃ n^{m}. The remark at the end of the first paragraph of this section allows us to apply (2.8). Thus we deduce that the Dehn function of Γ_{m} is polynomial of degree m+1 and the optimal length of asynchronously automatic structures on Γ_{m} is polynomial of degree m. □

The following remark is important for the applications in [A+] and [WP]. We shall indicate why in Lemma 5.3.

3.5 Remark. Consider the presentation of Γ_{m} given in (2.6) and consider the sequence of words v_{n} = t_{1}^{−n}a_{1}^{n}t_{1}^{n}t_{2}^{−n}a_{1}^{−n}t_{2}^{n}. In Example 1.4 we described a minimalarea van Kampen diagram for v_{n} — this is a disc which maps injectively to the universal covering of the standard 2-complex associated to the given presentation of Γ_{m} and its area is

Area(v_{n}) = 2 ∑_{i=0}^{n−1} d_{A}(1, ϕ^{i}(a_{1}^{n})).

It follows from the last sentence of (3.3) that, as a function of n, the sum on the right is ≃ n^{m+1}, the Dehn function of Γ_{m}.

By using the non-abelian case of Proposition 3.2 instead of Example 3.3 in the proof of Theorem A one obtains:

3.6 Theorem. Let F_{m} be a free group of rank m and let ϕ ∈ Aut(F_{m}). For all r ≥ 2, the Dehn function of F_{m} ⋊_{(ϕ)} F_{r} is ≃ n^{2}∥ϕ^{n}∥, which is exponential or else polynomial of (integer) degree at most m + 1.

3.7 Remarks.

(1) It follows from the Nielsen-Thurston classification of surface automorphisms (see [CB]) that if Σ is a compact 2-manifold and ϕ is a non-trivial automorphism of π_{1}Σ induced by a surface automorphism, then for every γ ∈ π_{1}Σ the function n ↦ d(1, ϕ^{n}(γ)) grows either linearly or exponentially, with respect to any word metric, and n g_{0,ϕ}(n) ≃ \frac{1}{n}g_{2,ϕ}(n) ≃ g_{3,ϕ}(n). The arguments in this section show that the Dehn function of any semidirect product of the form π_{1}Σ ⋊_{(ϕ)} F_{r} is either quadratic (the case where ϕ is periodic in Out(π_{1}Σ)), cubic (the case where ϕ has a power whose geometric realisation is a product of Dehn twists in a system of disjoint curves), or exponential (the case where the geometric realisation of ϕ has a pseudo-anosov component).

(2) Theorem 3.6 and the non-abelian case of Proposition 3.2 are the first steps in the following programme of research, which I intend to pursue in partnership with a student.

The Main Theorem of [B3] classifies the Dehn functions of all semidirect products ℤ^{m} ⋊ F where F is finitely generated and free. Kolchin’s theorem plays a key role in the proof of that theorem, and it ought to be possible to establish a similarly authorative result about free-by-free groups (generalizing Theorem 3.6) using the Bestvina-Feighn-Handel analogue of Kolchin’s theorem for free group automorphisms [BFH2]. One could then approach the general case H ⋊ F_{r} with H hyperbolic by using Sela’s description of Out(H) in terms of the JSJ decomposition of the group [Se].

(3) Fix a basis {a_{1}, …, a_{r}} for the free group F_{r} such that each a_{i} acts as ϕ ∈ Aut(F_{n}) in F_{n} ⋊_{(ϕ)} F_{r}. There is an embedding F_{n} ⋊_{(ϕ)} F_{r} ↪ (F_{n} ⋊_{ϕ} ⟨t⟩) × F_{r}, sending each a_{i} in the domain to ta_{i}, and sending the visible normal F_{n} in the domain to the one in the target by “the identity map” (i.e., the isomorphism implicit in the notation).

In the light of Theorem 3.6, we know that if ϕ is not periodic in Out(F_{n}), then the Dehn function of F_{n}⋊_{(ϕ)}F_{r} is exponential or polynomial of degree at least three. Many free-by-cyclic groups are biautomatic, indeed the first examples that are not biautomatic were only discovered recently [BB2]. The embedding F_{n} ⋊_{(ϕ)} F_{r} ↪ (F_{n} ⋊_{ϕ} ⟨t⟩) × F_{r} described above gives examples of subgroups of automatic groups where the Dehn function of the subgroup is exponential or polynomial of high degree. This is the easiest construction that is known of subgroups of automatic groups which are not themselves automatic [BBMS].

3.8 Dehn functions of 4-dimensional surface bundles.

Let S be a compact orientable surface of genus at least 2 and let Σ be a closed surface of genus at least one. Consider the usual presentation ⟨a_{1}, b_{1}, …, a_{g}, b_{g} | ∏_{i=1}^{g}[a_{i}, b_{i}]⟩ of π_{1}S, where the a_{i} and b_{i} are represented by simple closed curves on S (in the standard way). One can regard S as the boundary of a handlebody where the a_{i} generate the fundamental group F_{g} of the handlebody and the b_{i} lie in the kernel of the map π_{1}S → F_{g} induced by S ↪ F_{g}.

We cut S along a simple closed curve C in the free homotopy class of b_{1} to obtain a surface S′ with two boundary circles C_{1} and C_{2} (with a distinguished homeomorphism i : C_{1} → C_{2} – “the identity of C”). Given a homeomorphism ϕ of Σ, one can build a closed 4-manifold M from S′ × Σ by gluing C_{1} × Σ to C_{2} × Σ by means of the relation (t, x) ∼ (i(t), ϕ(x)). The fundamental group of the resulting manifold is π_{1}Σ ⋊_{Φ} π_{1}S, where Φ(a_{1}) = ϕ and Φ : π_{1}S → π_{1}Σ factors through the obvious retraction π_{1}S → F_{g} → ⟨a_{1}⟩. In particular, π_{1}Σ ⋊_{Φ} π_{1}S retracts onto the subgroup generated by π_{1}Σ and gp{a_{1}, …, a_{g}}, which is isomorphic to π_{1}Σ⋊_{(ϕ)} F_{g}. Thus, since retractions do not increase Dehn functions [AWP], the Dehn function of π_{1}M is bounded below by that of π_{1}Σ ⋊_{(ϕ)} F_{g}, which can be calculated as in 3.7(2). In fact, the Dehn function of π_{1}M is ≃ equivalent to that of π_{1}Σ ⋊_{(ϕ)} F_{g}, because (2.7) provides a complementary upper bound on π_{1}M.

4. Subgroups of Aut(F_{n})

4.1 Some Embeddings.

(1) For all positive integers m < n one can embed Aut(F_{m}) into Aut(F_{n}) by making the elements of Aut(F_{m}) fix the last (n − m) elements of a basis for F_{n} while acting in the obvious way on the subgroup generated by the first m elements. The image of this embedding does not contain any inner automorphisms, thus one can embed Aut(F_{m}) into Out(F_{n}).

One can extend this to an embedding of Aut(F_{m}) × Aut(F_{n−m}) into Out(F_{n}) by making the second factor act trivially on the first m elements of a fixed basis for F_{n}. In particular, since Aut(F_{2}) contains non-abelian free groups, one can embed any Aut(F_{m}) × F_{r} into Out(F_{n}) if m < n − 1.

(2) As in 3.7(3) (see [BBMS] for more details) one can always embed a semidirect product of the form G ⋊_{(ϕ)} F_{r} into (G ⋊_{ϕ} ℤ) × F_{2}. In particular, if one can embed F_{m} ⋊_{ϕ} ℤ into a group U then one can embed F_{m} ⋊_{(ϕ)} F_{r} into U × F_{2}.

(3) We wish to embed semidirect products P = F_{m} ⋊_{ϕ} ⟨t⟩ into Aut(F_{m}). To this end, working with the presentation P = ⟨a_{1}, …, a_{m}, t | ta_{i}t^{−1} = ϕ(a_{i})⟩, we send a_{i} ∈ P to the inner automorpism by a_{i} and send t to ϕ. One checks easily that this map is a homomorphism. It is injective if and only if the image of ϕ in Out(F_{m}) has infinite order.

If ϕ is inner, then P ≅ F_{m} × ℤ, which can even be embedded in Aut(F_{2}): send the generator a_{i} ∈ F_{m} × {1} to the inner automorphism of F (x, y) by y^{i}xy^{−i}, and send the generator of {1} × ℤ to the automorphism (x, y) ↦ (x, yx). We leave the reader to consider what happens when a power of ϕ is inner.

Returning to the general case, by composing the natural embedddings P ↪ Aut(F_{m}) and Aut(F_{m}) ↪ Out(F_{m+1}), we obtain an embedding P ↪ Out(F_{m+1}).

(4) There are other (non-conjugate) embeddings of P into Out(F_{m+1}). For example, in analogy with the usual embedding of ℤ^{n} ⋊_{ϕ} ⟨t⟩ into GL(n + 1, ℤ) (see 4.4(2)), one can map P into Aut(F_{m+1}) by fixing a basis {x_{1}, …, x_{m+1}} for F_{m+1} and sending a_{j} ∈ P to the map R_{j} ∈ Aut(F_{m+1}) that sends x_{m+1} to x_{m+1}x_{j} and fixes the remaining x_{i}. In this way, sending t ∈ P to the automorphism ϕ̃ that fixes x_{m+1} and restricts to ϕ on gp{x_{1}, …, x_{m}} one obtains an embedding of P into Aut(F_{m+1}) that intersects Inn(F_{m+1}) trivially.

4.2 Lemma. Let P = F_{m} ⋊_{ϕ} ℤ. Suppose that no power of ϕ ∈ Aut(F_{m}) is inner and suppose that the fixed subgroup of ϕ is non-abelian (i.e., has rank at least two). Then P × F_{2} embeds in Out(F_{m+1}).

Proof. Given W ∈ gp{x_{1}, …, x_{m}}, we write L_{W} for the element of Aut(F_{m+1}) that fixes x_{i} for i = 1, …, m and sends x_{m+1} to W x_{m+1}. Note that if W is non-trivial then L_{W} does not lie in the image of the embedding P ↪ Aut(F_{m+1}) described in 4.3(4). Note too that L_{W} commutes with the automorphisms R_{i} described there, and it commutes with ϕ̃ if and only if ϕ(W) = W. In particular, if W_{1}, W_{2} ∈ Fix(ϕ) generate a free subgroup of rank 2, then the image of P ↪ Aut(F_{m+1}) and gp{L_{W_{1}}, L_{W_{2}}} ≅ F_{2} generate a subgroup S ≅ P × F_{2} in Aut(F_{m+1}).

A typical element of S has the form ϕ̃^{n}yL_{W}, where y ∈ gp{R_{1}, …, R_{m}}. Since yL_{W} acts trivially on the S-invariant subgroup gp{x_{1}, …, x_{m}}, and the action of ϕ̃^{n} is assumed not to be inner, S does not contain any non-trivial inner automorphisms, and hence injects into Out(F_{m+1}). □

4.3 Proof of Corollary B. Let Γ_{m} = F_{m} ⋊_{(ϕ)} F_{2} be as in (2.6). We have seen that the Dehn function of Γ_{m} is polynomial of degree (m + 1). The fixed subgroup of ϕ contains a_{m} and a_{m−1}a_{m}a_{m−1}^{−1}, which generate a free subgroup of rank two. And we may apply the preceding lemma to embed (F_{m} ⋊_{ϕ} ℤ) × F_{2} in Out(F_{m+1}). Thus, in the light of 4.1(2), we obtain Γ_{m} ↪ Out(F_{m+1}). □

4.4 Other Embeddings.

(1) By starting with 4.1(3) instead of 4.1(4), and appealing to 4.1(1) and 4.1(2), one obtains embeddings of the form (F_{m} ⋊_{(ϕ)} F_{r}) ↪ Out(F_{m+2}).

(2) Recall that one can embed any semidirect product ℤ^{n} ⋊_{ϕ} ⟨t⟩ into GL(n+1, ℤ) as follows: one fixes a basis for ℤ^{n} and then identifies this with the obvious basis for the group of unipotent matrices whose only non-zero off-diagonal entries are in the right-hand column; one then sends t to the (n, n)-matrix representation of ϕ placed in the top left corner of an (n + 1, n + 1)-matrix with a 1 in the last diagonal place. As in 4.1(2), one can embed ℤ^{n} ⋊_{(ϕ)} F_{r} into GL(n + 1, ℤ) × GL(2, ℤ) ⊂ GL(n + 3, ℤ). Taking ϕ to be the unipotent matrix consisting of a single Jordan block, this construction gives examples of subgroups of GL(n + 3, ℤ) whose Dehn functions are polynomial of degree n + 1.

Section 5: Second and Higher Order Dehn Functions

In this section we discuss second (and higher) order Dehn functions. The kth order Dehn function is a function δ^{(k)} : ℕ → ℕ defined for any group G that is of type F_{k} (i.e., it has a K(G, 1) with finite k-skeleton — equivalently, G has a finite (k + 1)-presentation in the sense defined below). Up to ≃ equivalence, δ^{(k)} is an invariant of the group. The definition of these functions that we shall give is equivalent to that given by Alonso, Wang and Pride [AWP], but is phrased in more geometric language. We shall explain the relationship between our definition and that of Gromov [Gr] and Epstein-Thurston [E+] in (5.10).

First we need some terminology. Recall that a (non-singular) combinatorial map between CW complexes is a map that sends open cells homeomorphically onto open cells, and a combinatorial complex K is a CW complex such that the attaching maps ϕ_{e} : ∂D^{n+1} → K^{(n)} of its cells are combinatorial with respect to some combinatorial structure on 𝕊^{n} = ∂D^{n+1}. (This definition involves a recursion on dimension.) In what follows it will be natural for us to work in a larger categrory of complexes: we define a singular combinatorial morphism f : L → K between CW complexes to be a continuous map such that for every open n-cell e in L, either f|_{e} is a homeomorphism onto an open cell of K or else f(e) is contained in the (n − 1)- skeleton of L. A singular combinatorial complex K is a CW complex such that the attaching maps ϕ_{e} : ∂D^{n+1} → K^{(n)} of its cells are singular morphisms with respect to some combinatorial structure on 𝕊^{n} = ∂D^{n+1}.

An important point about singular morphisms is that there is a natural notion of (combinatorial) volume for them. Specifically, if L is compact and n-dimensional and f : L → K is a singular morphism, then one can define the volume of f to be the number of n-cells e in L such that the restriction of f to e is a homeomorphism.

Recall the standard construction in Section 1 that assigns a compact combinatorial 2-complex K = K(A; R) to a finite presentation of a group G = ⟨A | R⟩. We have π_{1}K = G. In order to build a complex that contains more information about the group (for example its cohomology), one should enlarge K so as to make its universal cover highly-connected. To this end, if π_{2}K is finitely generated as a G-module, one chooses a finite number of generators, the homotopy classes of maps ψ_{i} : 𝕊^{2} → K, say, and then one attaches a 3-cell to K for each of these generators — the attaching map of the ith 3-cell is ψ_{i}. One can choose the maps ψ_{i} to be singular morphisms (with respect to suitable combinatorial structures on 𝕊^{2}), but in general they will not be combinatorial maps. The presentation ⟨A | R⟩ together with the choice of maps ψ_{i} is sometimes called a 2-presentation for G. (When this terminology is used, it is often assumed that the maps ψ_{i} are described in terms of pictures, in the sense of [Pr], but we shall not take that viewpoint.)

If the group G satisfies suitable finiteness properties then one can continue the above process through higher dimensions, attaching finitely many cells by singular morphisms at each stage so as to obtain a finite singular combinatorial complex whose universal cover is highly-connected — if one makes it k-connected, then it is reasonable to call the totality of data used to attach cells up to that stage a k-presentation for G.

Words representing 1 ∈ G correspond to combinatorial loops 𝕊^{1} → K̃. The volume, as defined above, of this loop (singular morphism) is simply the length of the word. A van Kampen diagram Δ for w describes a homotopy contracting this loop to the constant loop at the basepoint; the area (number of 2-cells) in Δ is the number of times that one pushes the loop across a 2-cell in the course of this homotopy. (Note that one is allowed to make homotopies in the 1-skeleton — free reductions and insertions — between each push.) This area is the volume of the (singular) combinatorial map Δ̃ : Δ → K̃ associated to the diagram (see Section 1). We know that the area of a minimal diagram for w can be defined algebraically: it is the least integer N such that there is a free equality

w = ∏_{j=1}^{N} u_{j}r_{j}u_{j}^{−1}

with r_{j} ∈ R^{±1}. We now wish to define a similar measure of how many pushes across (k + 1)-cells are required to contract a k-sphere mapped into the universal cover of the complex associated to a finite k-presentation of G. And as with the (first order) Dehn function, we wish to formulate the definition algebraically.

Thus we assume that K is a compact complex with one vertex and fundamental group G such that the universal covering K̃ is k-connected. Following convention, we write K^{(n)} to denote the n-skeleton of K. We fix a basepoint p ∈ K and consider π_{k}(K^{(k)}, p), viewed as homotopy classes of singular combinatorial maps (𝕊^{k}, ∗) → (K^{(k)}, p) (which by homotopy lifting is the same as homotopy classes of singular combinatorial maps f : (𝕊^{k}, ∗) → (K̃^{(k)}, p̃)). By construction, π_{k}(K^{(k)}, p) is generated as a G-module by the classes of the attaching maps [∂e_{j}] of the (k +1)- cells of K.

If f_{2} : 𝕊^{k} → K^{(k)} is obtained from f_{1} by pushing across a (k + 1)-cell in the orbit of e_{j}, then [f_{2}] = [f_{1}] + g.[∂e_{j}] for some g ∈ G. Thus if one can contract f to the constant map by making N pushes (where one is allowed to make homotopies in the k-skeleton between each push), then there is an equality

(*)  [f] = ∑_{i=1}^{N} g_{i}.[∂e_{j(i)}^{k+1}]

in the G-module π_{k}(K^{(k)}, p). The least integer N among all equalities of this form is defined to be the filling volume of f (and its homotopy class [f]), and is denoted FVol(f). The boundary volume, written ∂Vol(f) is the number of open k-cells in f that map homeomorphically to open k-cells in K^{(k)}.

5.1 Definition. Let X, with basepoint p, be the universal cover of the compact (k + 1)-dimensional complex associated to a finite k-presentation of the group G. The k-th order Dehn function of the given k-presentation is

δ^{(k)}(n) = sup_{f}{FVol(f) | f : (𝕊^{k}, ∗) → (X^{(k)}, p), ∂Vol(f) ≤ n}.

It is proved in [AWP] that up to ≃ equivalence this function depends only on G. Because of this fact, we often write δ_{G}^{(k)}(n), with the understanding that this function if only well-defined up to ≃ equivalence.

(One can define the k-th order Dehn function of any k-connected singular combinatorial complex in a similar manner to the special case treated above; it is shown in [AWP] that if two such complexes admit discrete cocompact group actions and are quasi-isometric (with respect to the combinatorial metrics on their 1-skeleta), then their k-th order Dehn functions will be ≃ equivalent.)

5.2 Remarks. (1) If ∂Vol(f) is minimal among all maps in [f] ∈ π_{k}(K̃, p), then ∂Vol(f) is the ℓ_{1}-norm of α([f]) with respect to the natural (Whitehead) basis for the free G-module π_{k}(K̃^{(k)}, K̃^{(k−1)}, p), where α : π_{k}(K̃^{(k)}, p) = π_{k}(K̃^{(k)}, p, p) → π_{k}(K̃^{(k)}, K̃^{(k−1)}, p) is the natural map (cf. [Wh] and page 85 of [AWP]).

(2) In the case k = 2, one can represent elements of π_{2}K as pictures rather than singular morphisms (roughly speaking these are dual objects) and ∂Vol(f) can be taken to be the number of discs in the picture (see [AWP]).

In analogy with Lemma 1.2 we have:

5.3 Lemma. Suppose that we are given a finite k-presentation of a group G and let X be the universal cover of the corresponding (k + 1)-dimensional complex. Let F : D → X̃ be a combinatorial map from a (k + 1)-dimensional disc and consider [f] ∈ π_{k}(X^{(k)}, p), the homotopy class of f := F |_{∂D}. If F is injective on the complement of the k-skeleton in D, then the number of (k + 1)-cells in D is FVol([f]).

Proof. The proof is essentially the same as that of Lemma 1.2. Given an equality such as (*), one can realise the right hand side geometrically as a map from a bouquet of stalked k-spheres: the stalk of the ith sphere is sent to an edge path joining the basepoint p ∈ X to g_{i}.p, and the ith sphere is mapped to the lift of the attaching map ∂e_{i} at that vertex. Regard this bouquet as a subset of ℝ^{k+1} and map the ball enclosed by the ith sphere to the corresponding (k + 1)-cell in X. Enclose the entire bouquet in a k-sphere S with the same basepoint. Map S to X^{(k)} by f.

The equality (*) states precisely that one can map the region between S and the bouquet to X^{(k)} so that the union of the maps defined so far is continuous. Let B be the ball enclosed by S, identify 𝕊^{k+1} with D ∪_{S} B and define Φ : 𝕊^{k+1} → X to be F (the given map) on D and the map we have just constructed on B. One now finishes as in (1.2) by noting that the image of Φ in π_{k+1}(X/X^{(k)}) must be trivial. □

5.4 Remark. As we noted following (1.2), one can use homology instead of homotopy in the final step of this proof and by doing so one obtains a lower bound on the norm of expressions for [F] in the cellular chain complex of X. Thus Lemma 5.3 gives lower bounds not only on δ^{(k)} but also on the filling function described in (5.10).

5.5 Amalgams and Analogues of t-corridors.

If G is a group of type F_{n} and H ⊂ G is of type F_{n−1}, then any HNN extension of the form G∗_{H} is of type F_{n}, and hence has a well-defined (n − 1)st order Dehn function. Indeed one obtains a finite (n − 1)-presentation of G∗_{H} by realising the monomorphisms ϕ_{0}, ϕ_{1} : H → G implicit in the notation by singular combinatorial maps ϕ̃_{i} : K(H, 1) → K(G, 1) and then taking the n-skeleton of K := K(G∗_{H}, 1) = K(G, 1) ∐(K(H, 1) × [0, 1])/∼, where K(H, 1) and K(G, 1) are taken to have a single vertex each, K(H, 1)^{(n−1)} and K(G, 1)^{(n)} both have finitely many cells, and ∼ is generated by ϕ̃_{i}(x) ∼ (x, i) for i = 0, 1 and all x ∈ K(H, 1). We shall refer to the images of the cells from K(H, 1)^{(n−1)} × [0, 1] as t-cells.

As we saw with t-corridors and first order Dehn functions in previous sections, there are circumstances in which one can use a count of t-cells to get sharp lower bounds on Dehn functions. We leave the reader to consider the various ways of performing similar counts in higher dimensions.

A mapping-cylinder construction similar to that which we have described in the HNN case shows that if G_{1} and G_{2} are of type F_{n} and H is of type F_{n−1} then any amalgamated free product of the form G_{1} ∗_{H} G_{1} is of type F_{n}. And iterating these constructions, one sees that the fundamental group of any finite graph of groups with vertex groups of type F_{n} and edge groups of type F_{n−1} is of type F_{n}. In this setting one can again count t-cells to obtain lower bounds on Dehn functions, although one must be careful to take account of the topology of the filling.

5.6 Examples of Second Order Dehn functions.

(1) By definition, the second order Dehn function of any group with a finite aspherical presentation is linear. The second order Dehn function of every (word) hyperbolic group H is also linear, as is the direct product of H with any finitely generated free group [A+].

(2) The second order Dehn function of any finitely generated abelian group with torsion-free rank greater than two is ≃ n^{3/2}.

(3) Theorem C of [BB1] shows that the set of numbers α such that n^{α} is a second order Dehn function is dense in [3/2, 2).

(4) There are also second order Dehn functions of the form n log n and n^{2}/ log n (see [A+] and [Wa]).

(5) There is a second order Dehn function δ^{(2)}(n) with e^{\sqrt{n}} ⪯ δ^{(2)}(n) ⪯ e^{n} (see [WP]).

(6) Using the properties of groups Γ_{m} that were established in (3.5) above, in [WP] Wang and Pride showed that there are infinitely many non ≃ equivalent second order Dehn functions that are super-quadratic and polynomially bounded. Indeed they proved that for every positive integer r there exists a group of type F_{3} whose second order Dehn function lies between n^{(r+2)/2} and n^{r+1}.

(7) Isoperimetric inequalities bounding the Dehn functions of various groups of classical interest can be found in [Gr], [E+] and [HV]. (These results are phrased in the more geometric language described in (5.10).)

The upper bounds on second order Dehn functions that we shall need in the next section are obtained by appealing to the following result of Pride and Wang. This is a special case of Theorem 1 of [WP] and the remark that follows it.

5.7 Proposition. Let G be a group of type F_{3}, let m > 0 be an integer and for i = 1, …, m let ϕ_{i} : H_{0,i} → H_{1,i} be an automorphism between finitely presented subgroups of G that have aspherical presentations. Suppose that the first order Dehn function of H_{0,i} is quadratic. Then the second order Dehn function of the multiple HNN extension

Ĝ = ⟨G, t_{1}, …, t_{m} | t_{i}^{−1}ht_{i} = ϕ_{i}(h) ∀h ∈ H_{0,i}, i = 1, …, m⟩

is δ(2) ; Ĝ(n) ⪯ \overline{δ}_{G}^{(2)}(n^{2}) + n^{2} (where the overbar denotes sub-negative closure).

Combining this result with examples 5.6(1) and 5.6(2) we get:

5.8 Corollary.

(1) The second order Dehn function of any HNN extension of ℤ^{2} with finitely many stable letters is ⪯ n^{2}.

(2) The second order Dehn function of any HNN extension of ℤ^{3} with finitely many stable letters is ⪯ n^{3}, provided that the amalgamated subgroups are all of infinite index in ℤ^{3}.

As an indication of how one gets lower bounds on the examples in (5.6), we give a sample application of Lemma 5.3.

5.9 A Sample Lower Bound. Let K be a compact aspherical 2-complex with basepoint ∗ and let H = π_{1}(K, ∗). Suppose that there exists a sequence of injective combinatorial maps f_{n} : 𝔻_{n}^{2} → K̃ such that there are at least n^{α} 2-cells in the combinatorial disc 𝔻_{n}^{2} and at most kn 1-cells in ∂𝔻_{n}^{2}, where k and α are constants. Then for any group G of type F_{3} that contains H, the second order Dehn function of the HNN extension Ĝ = (G, t | [t, h] ∀h ∈ H) is ⪰ n^{2− \frac{1}{α}}. (Examples of such groups H with the values of α dense in [2, ∞) are given in [BB1].)

One assembles X = K(Ĝ, 1) with a compact 3-skeleton from K(G, 1) and K × [0, 1] as in (5.4); in the present setting we may assume that ϕ_{0} = ϕ_{1} (notation of (5.4)) is injective. We fix a basepoint x_{1} ∈ X̃ above x_{0} := ϕ_{i}(∗) and identify K̃ with the connected component of the preimage of K × {0} containing x_{1}.

By hypothesis, we have injective combinatorial maps f_{n} : 𝔻_{n}^{2} → K̃. We may assume that a vertex in ∂𝔻_{n}^{2} is mapped to the base vertex 1 ∈ K̃. We begin to construct a sequence of injective combinatorial maps F_{n} : 𝔻_{n}^{3} → X̃ by endowing the topological 3-disc (drum) 𝔻_{n}^{2} × [0, 1] with the natural (product) combinatorial structure obtained by first partitioning [0, 1] with extra vertices 0 = t_{0} < t_{1} < ⋯ < t_{m} = 1. Let F_{n}|_{𝔻_{n}^{2}×{0}} = f_{n} and F_{n}|_{𝔻_{n}^{2}×{t_{i}}} = τ^{i}.f_{n}, where the deck transformation τ is the element of Ĝ = π_{1}(K(Ĝ, 1), x_{0}) defined by the 1-cell ε = {∗} × 𝕊^{1} ⊂ K × [0, 1]/∼. We complete the description of F_{n} by sending the remaining 1-cells of 𝔻_{n}^{2} × [0, 1] homeomorphically onto lifts ε̃ of this 1-cell, and sending the closed 3-cells in 𝔻_{n}^{2} × [0, 1] to closed 3-cells of the form e × ε̃, where e is a closed 2-cell in K̃. It is clear from the injectivity of f_{n} that F_{n} is injective.

If the number of 1-cells in ∂𝔻_{n}^{2} is l_{n} and the number of 2-cells in 𝔻_{n}^{2} is A_{n}, then the number of 3-cells in the domain of F_{n} is m.A_{n} while the number of 2-cells in the boundary of 𝔻_{n}^{2} × [0, 1] is ml_{n} + 2A_{n}. In particular, since l_{n} ≤ kn and A_{n} ≥ n^{α}, taking m = \frac{1}{k} n^{α−1} we obtain a lower bound on δ(2) ; Ĝ (as calculated from X = K(Ĝ, 1)):

δ(2) ; Ĝ(3n^{α}) ≥ n^{2α−1}.

Since the sequence (3n^{α}) is not unduly sparse (in the sense of (1.1)), we deduce

δ(2) ; Ĝ(r) ⪰ r^{2− \frac{1}{α}}.

5.10 Alternative approaches to filling.

We close this section by describing how the above definition of higher order Dehn functions (which is equivalent to that in [AWP]) is related to the definitions in [Gr] and [E+]. The main difference is that in these earlier works, given a null-homotopic map f : 𝕊^{k} → X, one examines not only “fillings” 𝔻^{k+1} → X, but all expressions of f as the boundary of (geometrically well-behaved) (k + 1)-dimensional cycles in X. In other words, one does not restrict the topology of the fillings considered; indeed one might consider a whole range of Dehn-like filling functions by placing various restrictions on the topology of the fillings allowed.

We have preferred the definition in which one allows only fillings 𝔻^{k+1} → X because this is the direct analogue of the first order Dehn function, which is quite definitely a homotopical rather than a homological construction.

I should also note that in the context of (singular) combinatorial complexes, the definition of volume given in [E+] assigns to a singular morphism f not the number of open top-dimensional cells in the domain that are mapped homeomorphically by f (as we did above), but instead counts the total number of top-dimensional cells in the domain of f. This definition (which is well-adapted to the nature of the arguments in [E+]) has the disadvantage that if f is homotopic to f′ then in general f and f′ will not have the same volume. Thus one must take an infimum in order to define the volume of a homotopy class of maps. Once this is done, it is easy to check that the resulting definition of Dehn function is ≃ equivalent to that which we have adopted (if one allows only filling by discs).

We mention one other significant variation on the definition of higher order Dehn functions; this leads to a substantially different notion but keeps one within the realms of homotopy theory (rather than passing to homology). This is similar to the direct notion of filling used in [HV].

One might modify the definition of a singular combinatorial map ϕ by requiring that if an open cell e does not map homeomorphically to an open cell in the image then ϕ(e) must be contained in ϕ(∂e). Thus one obtains a class of maps in which open cells are either mapped homeomorphically or else are collapsed in a welldefined sense. If one is dealing with maps between simplical complexes then this is the same as requiring the map to be simplicial. Again it is natural to consider the Dehn function associated to maps f : 𝕊^{k} → X and fillings F : 𝔻^{k+1} → X in this class.

In this setting there is a curious and enticing difference between the approach to volume taken in [E+] and [HV], where one counts all top-dimensional cells in the domain, and the approach that we have adopted in which one only counts cells that are not collapsed. Indeed with the latter approach it is clear that the second order Dehn function of an aspherical 2-complex is trivial, whereas in the former approach this is not at all clear. Thus the former type of Dehn function may provide an interesting invariant for aspherical 2-complexes. This remark is closely related to the fact that in the definition of the standard second order Dehn function we allowed homotopies in the 2-skeleton between pushes across 2-cells (see the italicized remark prior to equation (*)). And in the case of the second order Dehn function, unlike the first order Dehn function, the sequence of moves hidden in these homotopies might by necessity be wildly complicated.

Let me amplify this point in algebraic terms. Fix a complex K. The elements of π_{2}K^{(2)} can be regarded as equivalence classes of identity sequences (see [Pr]). In 1-dimensional homotopy, free reductions and insertions generate an equivalence on words determining equality in F (A) = π_{1}K^{(1)}; in the 2-dimensional case equivalence is generated by (more complicated) Peiffer moves.^{1} In the 1-dimensional case, if a word n represents 1 ∈ π_{1}K^{(1)} then one can reduce it to the empty word by performing at most n moves (cancellations), whereas in the 2-dimensional case there is no a priori bound on the number of Peiffer moves that one must peform on an identity sequence of a given length in order to show that it is trivial in π_{2}K^{(2)}. This number, quantified as a function of the length of the identity sequence, might be worthy of study in relation to classical problems concerning aspherical 2-complexes.

Section 6: Showing n^{2} and n^{3} are Second Order Dehn Functions

6.1 Proposition (Quadratic Example). The second order Dehn function of the following group is δ_{G}^{(2)}(n) ≃ n^{2}:

G = ⟨a, b, s_{1}, s_{2} | [a, b], s_{1}^{−1}as_{1}a^{−2}, s_{1}^{−1}bs_{1}b^{−2}, s_{2}^{−1}as_{2}a^{−2}, s_{2}^{−1}bs_{2}b^{−2}⟩.

(This is an HNN extension whose base group is free abelian of rank two; there are two stable letters s_{i} and each acts on the base group by squaring every element.)

Proof. Let T = 𝕊^{1} × 𝕊^{1}, regard 𝕊^{1} as the unit circle in ℂ and endow T with the following combinatorial structure: ∗ = (1, 1) is the only 0-cell, the 1-cells are {1} × (𝕊^{1} ∖ {1}) (which we orient and label a) and (𝕊^{1} ∖ {1}) × {1} (which we orient and label b), and there is one 2-cell. Give T ×[0, 1] the obvious (product) cell structure and place the label s_{1} on the 1-cell {∗} × [0, 1]. Let ∼ be the equivalence relation on T ×[0, 1] generated by (x, 1) ∼ (x^{2}, 0) for all x ∈ T, and give the quotient Y = T × [0, 1]/∼ the induced cell structure and labelling of 1-cells. We identify T with the image of T × {0} in Y.

1One might also represent elements of π_{2} by pictures and the ensuing discussion would then be about the number of standard moves to be made on a picture to realise an equivalence.

Take two copies Y_{1}, Y_{2} of Y and let X be the quotient of their disjoint union by the equivalence relation that identifies the two copies of T. By the Seifert-van Kampen Theorem, the map G → π_{1}(X, ∗) that sends each of the given generators of G to the homotopy class of the 1-cell with the same name is an isomorphism. Note that X is 3-dimensional and aspherical. X has two 3-cells, as shown in figure 6.1.

Fig. 6.1. The 3-cells in X

Corollary 5.8(1) gives an upper bound of ⪯ n^{2} on δ_{G}^{(2)}(n). According to Lemma 5.3, in order to establish the complementary lower bound it suffices to exhibit a sequence of injective combinatorial maps f_{n} : 𝔹_{n} → X̃ from 3-balls to the universal covering of X so that the number of 3-cells in 𝔹_{n} is a quadratic function of n while the number of 2-cells in ∂𝔹_{n} is a linear function of n. In fact we need only exhibit such a map for each number of the form n = 2^{m} (see remark 1.1).

Fix n = 2^{m}. Let D_{n}(1) be as shown in figure 6.2. This is a combinatorial 2disc whose boundary label, read in the clockwise direction from the basepoint ∗ is a^{n}b^{n}a^{−n}b^{−n}; at its centre this disc has a 2-cell labelled aba^{−1}b^{−1}; this central 2-cell is surrounded by m annuli, the jth of which A_{j} has its outer boundary loop labelled W (j) := a^{2^{j}}b^{2^{j}}a^{−2^{j}}b^{−2^{j}} and its inner loop labelled W (j −1); the jth annulus has 2^{j} faces with boundary label s_{1}a^{2}s_{1}^{−1}a^{−1} and 2^{j} faces with boundary label s_{1}b^{2}s_{1}^{−1}b^{−1}. Let D_{n}(2) be the labelled combinatorial 2-disc obtained from D_{n}(1) by replacing each edge-label s_{1} by the label s_{2}. We identify the boundaries of D_{n}(1) and D_{n}(2) to obtain a combinatorial 2-sphere S_{n}.

Let B_{n}(1) be the labelled combinatorial 3-ball obtained by attaching to D_{n}(1) the thickened combinatorial discs (“slabs”) Σ_{j}(1), j = 1, …, m shown in figure 6.3: the top of the jth slab is the unique minimal-area van Kampen diagram for W (j) over the presentation ⟨a, b | [a, b]⟩, the bottom is the minimal area diagram for W (j − 1), and the interior of the slab is filled with 2^{2j−2} copies of the 3-cell E(1) portrayed in figure 6.1; the boundary annulus of the slab is identified with the annulus A_{j} ⊂ D_{n}(1) in the obvious way, the bottom of Σ_{1}(1) is identified with the central square in D_{n}(1), and for j = 1, …, m − 1 the top of Σ_{j}(1) is identified with the bottom of Σ_{j+1}(1) in the obvious way.

Σ_{j}(2) and B_{n}(2) are obtained from Σ_{j}(1) and B_{n}(1) by simply changing each occurence of the label s_{1} to s_{2}. Let 𝔹_{n} be the labelled combinatorial 3-ball obtained from B_{n}(1) ∐ B_{n}(2) by identifying the top faces of Σ_{m}(1) and Σ_{m}(2) in the obvious way.

There is a unique morphism of labelled graphs 𝔹_{n}^{(1)} → X̃^{(1)} sending the basepoint ∗ ∈ S_{2} = D_{n}(1) ∪ D_{n}(2) to the base-vertex of X̃. This map extends to a

Fig. 6.2. The discs D_{n}(i)

Fig. 6.3. The slabs Σ_{j}(i) in the combinatorial ball B_{n}(i)

combinatorial map f_{n} : 𝔹_{n} → X̃^{(2)}, which we claim is injective. To see that this is the case, it suffices to note that each vertex in 𝔹_{n} can be reached from ∗ by an obvious (and unique) path in 𝔹_{n}^{(1)} with a label of the form s_{i}^{n}a^{p}b^{q}, and since these words are in HNN normal form, their images in X̃^{(0)} ≅ G are all distinct.

The area of each of D_{n}(1) and D_{n}(2) is 2^{m+2} − 3, each having m annuli. And hence the area of S_{n} is 2^{m+3} − 6 = 2n − 2. The volume of the slab Σ_{j}(i) ⊂ B_{n}(i) is (2^{j−1})^{2} and hence the volume of 𝔹_{n} is 2(4^{m} − 1)/3 = 2(n^{2} − 1)/3. □

6.2 Proposition (Cubic Example). The second order Dehn function of the following group is δ_{Γ}^{(2)}(n) ≃ n^{3}:

Γ = ⟨x_{1}, x_{2}, x_{3}, t_{1,2}, t_{1,3}, t_{2,3} | [x_{i}, x_{j}], t_{i,j}^{−1}x_{k}t_{i,j} = x_{k}^{2},
for i, j = 1, 2, 3 with i < j and k ∈ {i, j}⟩.

(This is an HNN extension of a free abelian group of rank three obtained by choosing a basis for ℤ^{3} and then adding three stable letters to conjugate the distinct pairs of basis elements to their squares.)

Proof. Let Y and T ⊂ Y be as in the first paragraph of the proof of the preceding proposition. For each of the three pairs integers i, j ∈ {1, 2, 3} with i < j we take a copy of Y and change the labels on the three 1-cells of Y from a, b, s_{1} to x_{i}, x_{j}, t_{i,j}. Let Y_{i,j} denote the resulting copy of Y. Endow the 3-torus 𝕋^{3} = 𝕊^{1}×𝕊^{1}×𝕊^{1} with its usual combinatorial structure (following the first paragraph of the preceding proof) and assume that the oriented 1-cells corresponding to the three coordinate circles are labelled x_{1}, x_{2}, x_{3} respectively. Let Z be the combinatorial 3-complex obtained from 𝕋^{3} ∐ Y_{1,2} ∐ Y_{1,3} ∐ Y_{2,3} by identifying each of the subcomplexes T_{i,j} ⊂ Y_{i,j} with the corresponding coordinate 2-torus in 𝕋^{3} in the obvious (label-preserving) way. Note that the 1-cells of Z inherit a natural labelling.

By the Seifert-van Kampen Theorem, the map Γ → π_{1}(Z, ∗) that sends each of the given generators of Γ to the homotopy class of the 1-cell with the same name is an isomorphism. Note that X is 3-dimensional and aspherical.

Corollary 5.8 gives a cubic upper bound on the second order Dehn function of G in this case. In order to establish the complementary lower bound, for each positive integer of the form n = 2^{m} we shall exhibit an injective combinatorial map f_{n} : 𝔻_{n} → Z̃ where 𝔻_{n} is a combinatorial 3-ball in which the number of 3-cells is a cubic function of n while the number of 2-cells in ∂𝔻_{n} is a linear function of n. To this end, for each of our three coordinate pairs (x_{i}, x_{j}) we consider a copy of the combinatorial 3-ball B_{n}(r) portrayed in figure 6.3; we replace the labels a, b, s_{r} on the 1-cells of B_{n}(r) by x_{i}, x_{j}, t_{i,j} respectively and denote the resulting (labelled) complex B_{n}(i, j). Let 𝔻_{n} be the combinatorial 3-ball obtained by attaching the disjoint union of two copies of each B_{n}(i, j), i, j ∈ {1, 2, 3}, to a combinatorial cube of side length n in the universal covering of 𝕋^{3} (see figure 6.4, where the cube is drawn in bold).

Fig. 6.4. Fillings 𝔻_{n} of cubic volume

By fixing a basepoint at the corner of the cube and mapping this to the base vertex 1 ∈ Γ ≅ Z̃^{(0)}, we obtain a unique label-preserving map 𝔻_{n}^{(1)} → Z̃^{(1)}. As in the previous proposition, a simple observation concerning HNN normal forms shows that this map is injective, so it only remains to check that the unique extension of this map to a combinatorial map f_{n} : 𝔻_{n} → Z̃ has the desired volume and surface area.

The number of 2-cells in the boundary of 𝔻_{n} is three times the surface area of the ball 𝔹_{n} in (6.1), while the number of 3-cells in 𝔻_{n} is three times the number in 𝔹_{n} plus the number in the cube, that is n^{3} + 2(n^{2} − 1). □

The proof of Proposition 6.1 provides a host of similar examples of groups with a quadratic second order Dehn function. For example:

6.3 Proposition. Let G be a group of type F_{3} that has a linear second order Dehn function and contains a subgroup A ≅ ℤ^{2}. (For example G could be the direct product of any infinite hyperbolic group and a finitely generated free group.) Let p ≥ 2 be an integer. Then the second order Dehn function of the HNN extension

(G, s, t | s^{−1}as = t^{−1}at = a^{p} ∀a ∈ A⟩.

is ≃ equivalent to n ↦ n^{2}.

A key feature of A in the above proposition is that there is an injective endomorphism whose iterates expand the area of an embedded disc in the universal cover of the standard 2-complex of A at an exponential rate. One could apply the same construction to any other aspherical group that admits such an endomorphism.

References

[A] J. M. Alonso, Inégalités isopérimétriques et quasi-isométries, C.R.A.S. Paris Série 1 311 (1990), 761–764.

[A+] J. Alonso, W. Bogley, R. Burton, S. J. Pride, X. Wang,, Second order Dehn functions of groups, Quart. J. Math. (Oxford) 49 (1998), 1–30.

[AWP] J. Alonso, X. Wang, S. J. Pride,, Higher-dimensional isoperimetric (Dehn) functions of groups, J. Group Theory 2 (1999), 81–112.

[BB1] N. Brady and M. R. Bridson, There is only one gap in the isoperimetric spectrum, Geom. Funct. Anal. (GAFA) 10 (2000), 1053–1070.

[BB2] N. Brady and M. R. Bridson, On the absence of biautomaticity for graphs of abelian groups, Preprint, University of Oxford, 2001..

[BF] M. Bestvina and M. Feighn, A combination theorem for negatively curved groups, J. Diff. Geom. 35 (1992), 85–101.

[BFH1] M. Bestvina, M. Feighn and M. Handel, The Tits alternative for Out(F_{n}) I: Dynamics of exponentially growing automorphisms, Ann. of Math. 151 (2000), 517–623.

[BFH2] M. Bestvina, M. Feighn and M. Handel, The Tits alternative for Out(F_{n}) II: A Kolchin type theorem, Preprint, University of Utah, 1999..

[BeH] M. Bestvina and M. Handel, Train tracks and automophisms of free groups, Ann. of Math. 135 (1992), 1–51.

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

[BBMS] G. Baumslag, M. R. Bridson, C. F. Miller III, and H. Short, Subgroups of automatic groups and their isoperimetric inequalities, J. London Math. Soc.(2) 56 (1997), 292– 304.

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

[B2] M.R. Bridson, Combings of semidirect products and 3-manifold groups, GAFA 3 (1993), 263–278.

[B3] M. R. Bridson, Optimal isoperimetric inequalities for abelian-by-free groups, Topology 34 (1995), 547–564.

[BG] M. R. Bridson and S. M. Gersten, The optimal isoperimetric inequality for torus bundles over the circle, Quart. J. Math. 47 (1996), 1–23.

[BH] M.R. Bridson and A. Haefliger, Metric Spaces of Non-Positive Curvature, Grund. der math. Wiss., Vol. 319, Springer Verlag, Berlin, Heidelberg, New York, 1999.

[BP] M. R. Bridson and Ch. Pittet, Isoperimetric inequalities for the fundamental groups of torus bundles over the circle, Geom. Dedicata 27 (1994), 203–219.

[CB] A. Casson and S. Bleiler, Surface automorphisms after Nielsen and Thurston, LMS Student Texts, Cambridge Univ. Press, 1989.

[E+] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston, Word processing in groups, Bartlett and Jones, Boston, 1992.

[Ge] S. M. Gersten, Dehn functions and ℓ_{1}-norms of finite presentations, Algorithmic problems and classification in group theory (G. Baumslag and C. F. Miller III, eds.), MSRI Series, vol. 23, Springer-Verlag, 1992.

[Gr] M. Gromov, Asymptotic invariants of infinite groups, Geometric Group Theory (G. A. Niblo and M. A. Roller, ed), LMS Lecture Notes 182, Cambridge Univ. Press, 1993, 75–263.

[HV] A. Hatcher and K. Vogtmann, Isoperimetric inequalities for automorphism groups of free groups, Pacific J. Math 173 (1996), 425–441.

[vK] E. R. van Kampen, On some lemmas in the theory of groups, Amer. J. Math. 55 (1933), 268–273.

[LS] R. C. Lyndon and P. E. Schupp, Combinatorial group theory, Springer-Verlag, 1977.

[Mi] C. F. Miller III, On group-theoretic decision problems and their classification, Annals of Mathematics Studies, No. 68, Princeton Univ. Press, 1971.

[P] S.J. Pride, Identities among relations of group presentations, Group Theory from a Geometrical Viewpoint (E. Ghys, A. Haefliger, A. Verjovsky, ed.), World Scientific, Singapore, 1991, pp. 687–717.

[PW] S.J. Pride and Jing Wang, Rewriting systems, finiteness conditions, and associated functions, Algorithmic Problems in Groups and Semigroups (Proc. Lincoln, Nebraska, 1998), to appear.

[SBR] M. Sapir, J-C. Birget, E. Rips, Isoperimetric and isodiametric functions of groups, Ann. of Math., to appear.

[Sela] Z. Sela, Endomorphisms of hyperbolic groups I: The Hopf property, Topology 38 (1999), 301–323.

[W] X. Wang, Second order Dehn functions of finitely presented groups and monoids, PhD Thesis, University of Glasgow, 1996.

[Wh] J. H. C. Whitehead, Combinatorial homotopy II, Bull. Amer. Math. Soc. 55 (1949), 453–496.

[WP] X. Wang and S. J. Pride, Second order Dehn functions and HNN-extensions, J. Austral. Math. Soc. 67 (1999), 272–288.

Mathematical Institute, University of Oxford, 24–29 St Giles’, OX1 3LB

E-mail address: bridson@maths.ox.ac.uk