THERE IS ONLY ONE GAP IN THE ISOPERIMETRIC SPECTRUM

Noel Brady and Martin R. Bridson

Abstract. The closure of the set of isoperimetric exponents for finitely presented groups is {1}∪[2, ∞). For each pair of positive integers p ≥ q, one can construct groups with aspherical presentations for which the Dehn function is ≃ n^{2α}, where α = log_{2}(2p/q).

Understanding the complexity of word problems in groups has been one of the central themes of combinatorial group theory in the twentieth century since the pioneering work of Max Dehn. In recent years, following the influential work of Mikhael Gromov [Gr1], attention has focused on estimating the complexity of the word problem by means of isoperimetric inequalities. This approach is based on the close connection between word problems in finitely presented groups and Plateau’s problem concerning the filling of loops in Riemannian manifolds.

A natural approach to the filling problem for loops in the universal cover of a closed Riemannian manifold M is to seek isoperimetric inequalities giving upper bounds on the area of discs with specified boundary and minimal area. The bounds are given as a function of the length of the boundary loop, and the function [0, ∞) → [0, ∞) giving the optimal bound is called F ill_{0}^{M}. Analogously, one can measure the complexity of the word problem in finitely presented groups by seeking isoperimetric inequalities giving upper bounds on the number of relators which one must apply in order to show that a word w in the given generators represents the trivial element in the group. The bounds are given in terms of the length of w, and the function ℕ → ℕ describing the optimal bound is called the Dehn function of the presentation.

The Dehn functions associated to different presentations of a group are equivalent under the relation ≃ generated by composing functions with affine distortions of their range and their domain and adding a linear factor, and the isoperimetric function F ill_{0}^{M} of any closed Riemannian manifold M is ≃ equivalent to the Dehn function of the fundamental group of M.

The most fundamental question concerning isoperimetric inequalities for finitely presented groups is that of determining which ≃ equivalence classes of functions arise as

Typeset by AMS-TEX

The first author received partial support from the EPSRC grant GR/L06928 at the University of Southampton, and from the NSF grant DMS-9704417. The research of the second author is funded by an EPSRC Advanced Fellowship.

Dehn functions. The foremost part of this problem is the determination of the structure of the countable set of numbers

IP = {ρ ∈ [1, ∞) | f(n) = n^{ρ} is ≃ a Dehn function},

which is called the isoperimetric spectrum. If ρ ∈ IP then ρ is called an isoperimetric exponent.

Gromov proved that word hyperbolic groups can be characterized as those which have linear Dehn functions [Gr1] (see also [Sh], [Ol], [Ly]). There are many examples of groups with quadratic Dehn functions (abelian groups, automatic groups, fundamental groups of compact non-positively curved spaces etc.), and several years ago, as the result of efforts by a number of authors ([Gr2], [BMS], [BP]), it was shown that every positive integer is an isoperimetric exponent of some finitely presented group. But what else is contained in IP?

A theorem of Gromov (detailed proofs of which were given by Ol’shanskii [Ol], Bowditch [Bo] and Papasoglu [Pa]) states that IP ∩ (1, 2) is empty. The question of whether or not there are any other gaps in IP has been widely articulated (see e.g. [Ni], [SS]). Bridson [Br1] proved that IP contains infinite discrete sets of non-integral rationals ρ > 4. Sapir, Birget and Rips [SBR] showed that IP ∩ [4, ∞) contains all numbers ρ such that the first n digits of the decimal expansion of ρ can be calculated by a Turing machine in time O(2^{2^{n}}). In particular, IP contains ℚ ∩ [4, ∞), so IP has no gaps beyond 4. The main purpose of the present article is to show that (1, 2) is the only gap in IP.

Theorem A. For all pairs of positive integers p > q, there exists a finitely presented group whose Dehn function f(n) is ≃ n^{2α} where α = log_{2}(2p/q).

Corollary B. The closure of IP is 1 ∪ [2, ∞).

Note that the exponents described in the above theorem are transcendental if they are not integers [Niv, Theorem 10.2].

The basic examples that we shall use to prove the above theorem are fundamental groups of finite aspherical 2-complexes obtained by attaching a pair of annuli to a torus. The present article is one of a series in which we shall analyze the geometry and logical complexity of such groups. Let

G_{p,q} = ⟨a, b, s, t | [a, b] = 1, sa^{q}s^{−1} = a^{p}b, ta^{q}t^{−1} = a^{p}b^{−1}⟩.

We shall show that the Dehn function of this group is n^{2α} where α = 2 log_{2}(2p/q).

Although it does not provide us with information about IP, the case p = q is also interesting: in this case one gets groups with aspherical presentations that satisfy a quadratic isoperimetric inequality but are not biautomatic and do not act properly by semisimple isometries on any complete CAT(0) space (see [BB]).

We are grateful to Steve Pride for pointing out to us that because the above presentation of G_{p,q} is aspherical, and because of the nature of the diagrams used in Section 1 below to get sharp lower bounds on the Dehn function of G_{p,q}, the results in Section 6 of [A+] yield the following consequence of Theorem A:

Theorem C. For each pair of positive integers p ≥ q there exists a finitely presented group whose second order Dehn function is ≃ n^{2− \frac{1}{ρ}}, where ρ = 2 log_{2}(2p/q). In particular, the spectrum of exponents of second order Dehn functions is dense in [3/2, 2].

This paper is organized as follows. In Section 1 we establish the desired lower bound on the Dehn function of G_{p,q}; this is the content of Proposition 1.3. In order to establish this lower bound, we exhibit an explicit sequence of words (“snowflake words”) which have large area. The complementary upper bound is given in Section 3. Our proof for the upper bound relies on the fact that the distortion of the free abelian subgroup gp{a, b} ⊂ G_{p,q} is ≃ n^{α}. The calculation of this distortion is the subject of Section 2. In Section 4 we explain how the techniques used to study G_{p,q} can be applied to larger classes of examples.

§1. The basic examples and the lower bound

Before focusing on our basic examples G_{p,q}, we pause to recall the definition of Area, Dehn function and subgroup distortion.

Given a finitely presented group G = ⟨X | R⟩ and a word w in the free group F (X) that is in the kernel of the natural map F (X) ↠ G, one defines

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

Equivalently, Area(w) is the least number of 2-cells in any van Kampen diagram^{1} for w (see [LS]). Note that if u_{1} = u_{2} = u_{3} in G then Area(u_{1}^{−1}u_{3}) ≤ Area(u_{1}^{−1}u_{2}) + Area(u_{2}^{−1}u_{3}).

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

δ(n) = max{Area(w) | w ∈ Ker(F (X) ↠ G), |w| ≤ n } .

Here |w| denotes the length of the word w in the free group on the generating set X. It is straightforward to show (see [Al]) 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.

Given a pair of groups H ⊂ G, with finite generating sets giving word metrics d_{H} and d_{G}, the function n ↦ max{d_{H}(1, h) | h ∈ H, d_{G}(1, h) ≤ n} is called the distortion of H in G. It is easy to check that, up to ≃ equivalence, this function is independent of the choice of generators.

1We shall use this equivalence repeatedly.

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, where C > 0 is constant. If f(n_{i}) ≤ g(n_{i}) 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).

We wish to examine the following groups

G_{p,q} = ⟨ a, b, s, t | [a, b] = 1, sa^{q}s^{−1} = a^{p}b, ta^{q}t^{−1} = a^{p}b^{−1} ⟩ .

Figure 1. The 2-complex for G_{p,q}

G_{p,q} is the fundamental group of an aspherical 2-complex obtained by attaching two annuli to the 2-torus as follows (see figure 1): regard ⟨a, b | [a, b] = 1⟩ as the fundamental group of the 2-torus; one end of each of the two annuli is attached to the torus along the curve a^{q} (i.e. it wraps q times around the loop labelled a); the other end of the first annulus is identified with the curve a^{p}b; the other end of the second annulus is identified with the curve a^{p}b^{−1}. The universal cover of this 2-complex is a contractible complex that can be obtained by gluing together copies of the plane, indexed by the cosets of gp{a, b} in G_{p,q}, along strips (copies of the line cross an interval) covering the annuli in the quotient (there are two types of strips and each collection is indexed by the cosets of the cyclic subgroup corresponding to the annulus which they cover).

In order to simplify the exposition, we shall first give a proof of the following proposition which exploits the asphericity of the 2-complex just described; we shall then give a proof better suited to the higher-dimensional examples described in Section 4. The apsect of asphericity that we wish to exploit is the following.

1.2 Remark. If one has a van Kampen diagram Δ which embeds in the universal cover K̃ of an aspherical 2-complex K, then any van Kampen diagram with the same boundary label as ∂Δ must have at least as many 2-cells as Δ. To see this, note that if we take a van Kampen diagram D such that ∂D and ∂Δ define the same edge-loop in K, then we can lift D ∪Δ and regard it as a 2-cycle in the cellular chain complex of K̃; since H_{2}(K̃, ℤ) is trivial and there are no 3-cells, the coefficient of each 2-cell in this chain must be zero, and since Δ is embedded, its contribution to the coefficient of each 2-cell in its image is non-zero, hence there must be cells in D that cancel each of the 2-cells in Δ.

1.3 Proposition. The Dehn function δ(n) for the group G_{p,q} satisfies

n^{2α} ≼ δ(n),

where α = log_{2}(2p/q).

Proof. To prove this propostion we shall exhibit a sequence of null-homotopic words W_{k} in the generators {a, s, t} of length l_{k} which have Area of order l_{k}^{2α}, where the sequence (l_{k}) grows in the controlled manner discussed in Remark (1.1). We shall construct these words inductively, keeping in mind the snowflake picture shown below (figure 2), and ensuring that we have embedded van Kampen diagrams for the words so that we can appeal to the above observation concerning asphericity.

Figure 2. The snowflake words W_{k}

We build the words w_{k} labelling the upper part of the boundary of this picture inductively, starting with w_{0} = a^{q} and

w_{1} = sa^{q}s^{−1}ta^{q}t^{−1} .

Note that w_{1} = a^{2p} in G_{p,q}. Let ϵ_{1} be the least positive integer such that (2p + ϵ_{1}) is divisible by q and define w_{2} = sw_{1}a^{ϵ_{1}}s^{−1}tw_{1}a^{ϵ_{1}}t^{−1}. Continuing in this manner, we define

w_{i} = sw_{i−1}a^{ϵ_{i−1}}s^{−1}tw_{i−1}a^{ϵ_{i−1}}t^{−1}

where ϵ_{i} with 0 ≤ ϵ_{i−1} ≤ q − 1 is chosen so that w_{i−1}a^{ϵ_{i−1}} represents a power of a with the exponent divisible by q.

After k steps we have a word w_{k} with 4(2^{k}) ≤ |w_{k}| ≤ (4q)2^{k} such that w_{k} = a^{m_{k}} in G_{p,q}, where

m_{k} = (2p/q)^{k}q + ϵ_{1}(2p/q)^{k−1} + ⋯ + ϵ_{k−1}(2p/q).

For our purposes, it is enough that m_{k} ≥ q(2p/q)^{k}. We shall also need the observation that there is a natural van Kampen diagram portraying the equality w_{k} = a^{m_{k}} and this diagram is embedded in the universal cover of the standard 2-complex for the given presentation of G_{p,q} (see figure 3). The large triangular subdiagram is this picture is the obvious van Kampen diagram for a^{m_{i}} = (a^{p}b)^{m_{i}/p}(a^{p}b^{−1})^{m_{i}/p} over the subpresentation ⟨a, b | [a, b]⟩.

Figure 3. The diagram portraying w_{k} = a^{m_{k}}

The desired snowflake words are the commutators

W_{k} = [sw_{k−1}a^{ϵ_{k−1}}s^{−1} , tw_{k−1}a^{ϵ_{k−1}}t^{−1}].

Note that W_{k} represents the identity in G_{p,q} and has length l_{k} = 2|w_{k}|. This word is the boundary of an embedded Van Kampen diagram in the universal cover of the presentation 2-complex for G_{p,q}, which is constructed from the subdiagrams shown in figure 3 in the manner shown in figure 2. The central square in this picture is a van Kampen diagram over the subpresentation ⟨a, b | [a, b]⟩, and its diagonal is labelled a^{m_{k}}. It follows that there is a constant C > 0 so that the Area of this square subdiagram is at least Cm_{k}^{2}, and hence

Area(W_{k}) ≥ Cm_{k}^{2} ≥ Cq^{2}(2p/q)^{2k}.

Since |W_{k}| = 2|w_{k}| and 4(2^{k}) ≤ |w_{k}| ≤ (4q)2^{k}, in the light of (1.2), we are done. □

1.4 Alternative proof.

For future reference, we shall now explain why asphericity was a convenience rather than a necessity in the above proof. The key point is that one can use standard arguments about (s and t)-corridors (as used in [Br1] and [SBR] for example) to argue that any van Kampen diagram for W_{k} must have the general structure shown in figure 2. In particular, the central square subdiagram must be present and must be bounded by a pair of scorridors and a pair of t-corridors. The sides of these corridors internal to the rectangle are labelled by words in a and b and the product of each of two of the adjacent pairs gives the diagonal a^{m_{k}}.

If the diagram has minimal area, then there will be no s-rings or t-rings within this central square subdiagram (since they would enclose subdiagrams that could be removed by area-reducing surgery), and hence the subdiagram is over the sub-presentation ⟨a, b | [a, b] = 1⟩. As in the proof of (1.3), this yields the desired lower bound on the area of the central square in the diagram and hence the whole diagram.

1.5 Remark. The proof of (1.3) show that if one restricts one’s attention to minimal area diagrams for the snowflake words W_{k}, then the diameter of these diagrams, measured in the natural path metric on the 1-skeleton of the diagram, will be ≃ k^{α}. However there do exist (non-reduced) diagrams of diameter ≃ k for W_{k} (cf. [Br1,2]).

§2. The distortion of the torus subgroup in G_{p,q}

In this section we calculate the distortion of the torus subgroup gp{a, b} in G_{p,q}. This calculation will be needed when we come to establish the upper bound on the Dehn function of G_{p,q} in Section 3.

The arguments used in the next two sections involve several applications of the Hölder inequality:

(∑_{i=1}^{n} x_{i})^{α} ≥ ∑_{i=1}^{n} x_{i}^{α}

for α ≥ 1 and x_{i} > 0. Note that if n = 2 and x_{1} = x_{2}(= x, say), then we get equality if we multiply the right hand side of the above inequality by 2^{α−1}: (x + x)^{α} = 2^{α−1}(x^{α} + x^{α}) .

2.1 Proposition. Let w be a word of length l in the generators {a^{±1}, s^{±1}, t^{±1}}. Let α = log_{2}(2p/q).

(1) If w represents a^{m} in G_{p,q}, then |m| ≤ l^{α}.

(2) If w represents either (a^{p}b)^{m} or (a^{p}b^{−1})^{m} in G_{p,q}, then q|m| ≤ l^{α}.

Proof. We argue by induction on l = |w|. We may assume that w is a geodesic word, i.e. that it has minimal length among all words with the same image in G_{p,q}.

To begin the induction, note that if l ≤ q +1 then w = a^{±l} in G_{p,q} and m = l ≤ l^{α}. The first time that case (2) can arise is when l = q +2 and m = 1, where q ·1 ≤ (q +2) = l ≤ l^{α}.

In order to complete the inductive step in the proof, we need to chop w up into subwords to which the inductive hypothesis can be applied. With the snowflake picture (figure 2) in mind, we see that the natural way to do this is to look at the pattern of prefixes in w that represent the points at which the path which w determines in the Cayley graph of G_{p,q} leaves and re-enters gp{a, b}. These points of departure and re-entry are marked by inverse pairs of symbols (s, s^{−1}), (s^{−1}, s), (t, t^{−1}), (t^{−1}, t).

2.2 Definition. Suppose that

w = x_{1}x_{2} … x_{l}

represents a word in the subgroup gp{a, b} ⊂ G_{p,q} and the x_{i} are in {a^{±1}, s^{±1}, t^{±1}} An inverse pair is an ordered pair (x_{i}, x_{j}), with i < j, such that:

(1) either i = 1 or x_{1} … x_{i−1} ∈ gp{a, b},

(2) x_{1} … x_{k} ∉ gp{a, b} for all i ≤ k ≤ j − 1, and

(3) x_{1} … x_{j} ∈ gp{a, b}.

Using the obvious retraction of G_{p,q} onto the free group on {s, t}, we see that if (x_{i}, x_{j}) is an inverse pair then x_{i} = x_{j}^{−1} ∈ {s^{±1}, t^{±1}}. By definition, the inverse pairs of w are not nested and do not overlap, hence any word that defines an element of subgroup of gp{a, b} ⊂ G_{p,q} has a unique decomposition into a product of subwords of five types:

(1) Type 1. These are the subwords of the form s … s^{−1} which are determined by the inverse pairs (s, s^{−1}). They are equal to powers of (a^{p}b) in G_{p,q}.

(2) Type 2. These are the subwords of the form t … t^{−1} which are determined by the inverse pairs (t, t^{−1}). They are equal to powers of (a^{p}b^{−1}) in G_{p,q}.

(3) Type 3. These are the subwords of the form s^{−1} … s which are determined by the inverse pairs (s^{−1}, s). They are equal to powers of a in G_{p,q}.

(4) Type 4. These are the subwords of the form t^{−1} … t which are determined by the inverse pairs (t^{−1}, t). They are equal to powers of a in G_{p,q}.

(5) Type 5. These are the remaining subwords of w. They are of the form a^{m} for some m ∈ ℤ.

Returning to the inductive step in the proof of Proposition 2.1, we claim that we may assume that our geodesic word w has at most one of each of the subwords of type 1 through 4, and that we can always arrange things so that it contains at most one type 5 subword. To see this, note that each subword of w represents an element of the free abelian group gp{a, b}. Therefore we can rearrange the order of the subwords in w to get a new word w′ in {a, s, t} which represents the same element as w and which also has minimal length. In particular, we can rearrange things so that subwords appear in order of type, beginning with type 1 subwords. Thus we can amalgamate all the type 5 subwords into one. If there is more than one type 1 subword then we get an adjacent s^{−1}s pair of letters contradicting minimality of w′. The same argument applies to subwords of types 2, 3 and 4.

Thus, without loss of generality, we may assume that

w = w_{1}w_{2}w_{3}w_{4}w_{5},

where w_{i} is of type i.

Define l_{i} = |w_{i}|. For i ∈ {1, 2}, define m_{i} to be the integer such that

w_{i} = (a^{p}b^{±1})^{m_{i}}

in G_{p,q}, and for i ∈ {3, 4} define m_{i} to be the integer such that

w_{i} = a^{m_{i}}.

Figure 4. w = w_{1}w_{2}w_{3}w_{4}w_{5}

Claim: If w is equal in G_{p,q} to a power of a, then l_{1} = l_{2}.

First note that since w_{3}, w_{4} and w_{5} all represent powers of a, the powers of b coming from w_{1} and w_{2} must cancel; that is m_{1} = m_{2}. This means that w_{1} = sus^{−1} and w_{2} = tvt^{−1}, where u and v are words in {a, s, t} which represent the same power of a^{q}. If |u| were less than |v|, then we could replace v with u, contradicting the fact that w is a geodesic word. This proves the claim.

To complete the proof of (2.1), we consider cases (1) and (2) separately, beginning with (1), the case w = a^{m}. In this case, projecting the equality w = w_{1}w_{2}w_{3}w_{4}w_{5} into G_{p,q} we get:

a^{m} = (a^{p}b)^{m_{1}}(a^{p}b^{−1})^{m_{2}}a^{m_{3}}a^{m_{4}}a^{l_{5}} .

Hence, counting the exponent of a, we have m = p(m_{1} +m_{2})+m_{3} +m_{4} +l_{5}. Our inductive hypothesis (remember that the induction is on l, not m) gives q|m_{i}| ≤ l_{i}^{α} for i = 1, 2 and m_{i} ≤ l_{i}^{α} for 1 = 3, 4. Thus

|m| ≤ p(|m_{1}| + |m_{2}|) + |m_{3}| + |m_{4}| + l_{5}
≤ (p/q)l_{1}^{α} + (p/q)l_{2}^{α} + l_{3}^{α} + l_{4}^{α} + l_{5} .

Note that (p/q) = 2^{−1}(2p/q) = 2^{log_{2}(2p/q)−1} = 2^{α−1}. Thus, the sum of the first two terms is 2^{α−1}[l_{1}^{α} + l_{2}^{α}]. And since l_{1} = l_{2}, this is equal to (l_{1} + l_{2})^{α}.

Trivially, l_{5} ≤ l_{5}^{α}, so by Hölder’s inequality

m ≤ (l_{1} + ⋯ + l_{5})^{α} = l^{α} .

(In the above argument, when invoking induction, we implictly assumed that at least two of the l_{i} were non-zero. The degenerate cases are easily dealt with. For example, if w = w_{1} = s^{−1}us, then u = u(a, s, t) has length l − 2 and represents the word (a^{p}b)^{m/q}, and the inductive hypothesis gives |m| = q(|m|/q) ≤ (l − 2)^{α} ≤ l^{α}.)

It remains to complete the induction in case (2) of the propositon. In this case w is a geodesic word that represents (a^{p}b^{±1})^{m} and we have to show that q|m| ≤ l^{α}.

We have seen that there is no loss of generality in assuming that w = w_{1} … w_{5}, where w_{i} is a subword of type i. In G_{p,q} this equality becomes

(a^{p}b^{±1})^{m} = (a^{p}b)^{m_{1}}(a^{p}b^{−1})^{m_{2}}a^{m_{3}}a^{m_{4}}a^{l_{5}},

so counting the exponent of a we have pm = p(m_{1} + m_{2}) + m_{3} + m_{4} + l_{5}. And applying our inductive hypothesis to the absolute values of the terms on the right we get:

p|m| ≤ p(|m_{1}| + |m_{2}|) + |m_{3}| + |m_{4}| + l_{5}
≤ (p/q)l_{1}^{α} + (p/q)l_{2}^{α} + l_{3}^{α} + l_{4}^{α} + l_{5} .

Since (q/p) ≤ 1, we deduce:

q|m| ≤ l_{1}^{α} + ⋯ + l_{4}^{α} + l_{5} .

And since l_{5} ≤ l_{5}^{α}, by Hölder we get q|m| ≤ l^{α}. (As in case (1), there are degenerate cases w = w_{i} which are easily dealt with.) □

The upper bound obtained in Proposition 2.1 above combines with estimates established in Section 1 to give a precise calculation of the distortion of gp{a, b} in G_{p,q}.

Corollary 2.3. The distortion function of the torus subgroup gp{a, b} in G_{p,q} is equivalent to n^{α}, where α = log_{2}(2p/q).

Proof. For the snowflake words W_{k} considered in Section 1 we have W_{k} = a^{m_{k}}, in G_{p,q}, where m_{k} ≥ q|W_{k}|^{α}. Thus (in the light of Remark 1.1) we see that the distortion of gp{a, b} in G_{p,q} is ≽ n^{α}.

To obtain the complementary lower bound on distortion, note that for each g ∈ gp{a, b} there are unique integers r and s such that g = a^{r}(a^{p}b)^{s}, and in the word metric d_{A} associated to the generating set {a, a^{p}b}, we have d_{A}(1, g) = |r| + |s|, whereas for the word metric d_{G} associated to the generators {a, s, t} for G_{p,q} we have:

d_{G}(1, g)^{α} ≥ d_{G}(1, a^{r})^{α} + d_{G}(1, (a^{p}b)^{s})^{α}
≥ |r| + q|s|
≥ d_{A}(1, g) ,

where the first inequality is simply the triangle inequality combined with the Hölder inequality, and the second inequality is the content of Proposition 2.1. □

§3. The upper bound on the Dehn function of G_{p,q}

In order to establish the desired upper bounds on Dehn functions we shall give an inductive argument in which the following general remark about the word problem in free abelian groups will be needed.

Lemma 3.1. In the standard presentation of the free abelian group A on the generating set {a, b_{1}, …, b_{k}}, if W_{1}, …, W_{r} ∈ A are geodesic words such that

W_{1} ⋯ W_{r} = a^{n} for some n ∈ ℤ,

then one can realize this equality by applying at most 2m ∑_{i<j} |W_{i}||W_{j}| commutator relations [b_{i}, b_{j}] and [a, b_{i}].

Proof. We realize the equality through a series of shuffles. By a shuffle of a finite sequence of words w_{1}, …, w_{m} we mean a word obtained from the product w_{1} … w_{m} by rearranging the letters in such a way that for each i, if all of the letters originally coming from the w_{j}, j ≠ i were deleted one would regain w_{i}.

We read P_{0} := W_{1} … W_{r} from the right until we come to the first letter β = b_{1}^{±}; we then continue to read from the right looking for the first occurence of β^{−1}. Suppose β lies in W_{j} and β^{−1} lies in W_{i}, and consider the obvious decompositions W_{i} = Xβ^{−1}Y and W_{j} = X′βY′. Note that i ≠ j since the W_{i} are geodesic words. We move β^{−1}Y to the right to get

P_{1} := W_{1} … W_{i−1}XW_{i+1} … W_{j−1}X′(ββ^{−1})Y Y′W_{j+1} … W_{r} .

We then repeat the shuffling process with the prefix of P_{1} ending X′ in place of P_{0}. We continue in this manner until all of occurrences of b_{1}^{±} in P_{0} have been paired-up. We then cancel the subwords (b_{1}b_{1}^{−1})^{±1}. Thus, at the cost of applying at most ∑_{i<j} |W_{i}| |W_{j}| commutator relations we have removed all occurrences of b_{1} from P_{0}. We may then (if we wish) shuffle the resulting word (using less than ∑_{i<j} |W_{i}| |W_{j}| commutator relations) so as to return the remaining letters of P_{0} to their original positions. We then repeat the above process to remove all occurrences of b_{2}, then b_{3}, and so on. □

Proposition 3.2. Let p ≥ q be integers and consider the presentation of G_{p,q} given in the introduction.

There exists a constant C ≥ 1 such that for all m ∈ ℤ, all words w = w(a, s, t), and all words v of the form a^{m} or (a^{p}b^{±1})^{m}, if w = v in G_{p,q} then

Area(wv^{−1}) ≤ C |w|^{2α}

where α = log_{2}(2p/q).

Proof. Arguing by induction on l = |w|, we’ll show that it suffices to take C = 2(p+1)^{4}/q^{2}. The initial steps of the induction are trivial: if |w| ≤ q + 1, then by Britton’s lemma (see [LS]) it freely reduces to v = a^{l} and Area(wv^{−1}) = 0, which is certainly less than Cl^{2α}.

For the inductive step of the proof, we first consider the case where w is a word of one of the five special types listed in (2.2). The stated bound is trivial in the case of type 5. We shall write out a detailed argument in the case where w is of type 1; the other cases are entirely similar.

If the word w is of the form sw′s^{−1}, then in G_{p,q} we have w = v where v = (a^{p}b^{−1})^{m} for some m. Writing v′ = a^{mq}, we have w′ = v′ in G_{p,q}. By induction, Area(w′v′^{−1}) ≤ C |w′|^{2α}. Moreover, sv′s^{−1}v^{−1} is a product of m conjugates of the relation sa^{q}s^{−1}(a^{p}b^{−1})^{−1}. Therefore

Area(wv^{−1}) = Area(sw′s^{−1}v^{−1})
≤ Area(sw′v′^{−1}s^{−1}) + Area(sv′s^{−1}v^{−1})
≤ C |w′|^{2α} + m.

Proposition 2.1 tells us that m ≤ |w|^{α}, and |w′| = |w| − 2, so we have

Area(wv^{−1}) ≤ C (|w| − 2)^{2α} + |w|^{α},

which is less than |w|^{2α}.

Having dealt with the case where w consists of a single word of one of the special types 1 through 5, we may now assume that w decomposes as a product w_{1} … w_{n} of subwords of types 1 through 5 with n ≥ 2. Each w_{i} is equal in G_{p,q} to a unique word of the form a^{m_{i}} or (a^{p}b^{±1})_{i}^{m}, which we denote by v_{i}. Let l_{i} = |w_{i}|. (Look at figure 5: the idea of the proof is that our inductive hypothesis gives us bounds on the subdiagrams attached to the

Figure 5. The diagram to show wv^{−1} = 1 in G_{p,q}

base along the arcs labelled v_{i}, Proposition 2.1 gives us control over the lengths of the v_{i}, and Lemma 3.1 enables us to get a good bound on the area of the base.)

Our inductive hypothesis gives

Area(w_{i}(v_{i})^{−1}) ≤ Cl_{i}^{2α}

for each i. Thus we get

Area(wv^{−1}) ≤ C ∑_{i} l_{i}^{2α} + Area((∏_{j} v_{j})v^{−1}).

Claim. If C = 2(p + 1)^{4}/q^{2}, then

Area((∏_{j} v_{j})v^{−1}) ≤ C ∑_{i} l_{i}^{α} (∑_{j≠i} l_{j}^{α}) .

Using the claim, we get

Area(wv^{−1}) ≤ C_{i}l_{i}^{2α} + C ∑_{i} l_{i}^{α} ∑_{j≠i} l_{j}^{α} = C(∑_{i} l_{i}^{α})^{2} ≤ Cl^{2α},

which completes the induction.

It remains to prove the claim. There are two cases to consider. In the first case v = a^{m} for some m. From Lemma 3.1 we have:

Area((∏_{j} v_{j})v^{−1}) ≤ 2 ∑_{i<j} |v_{i}||v_{j}| .

If v_{i} = a^{m_{i}}, then |v_{i}| ≤ l_{i}^{α} by Proposition 2.1. Also, if v_{i} = (a^{p}b^{±1})^{m_{i}}, then (2.1) implies that q|v_{i}| ≤ (p + 1)l_{i}^{α}. Thus

Area((∏_{j} v_{j})v^{−1}) ≤ 2 (\frac{p + 1}{q})^{2} ∑_{i<j} l_{i}^{α}l_{j}^{α} ≤ 2 (\frac{p + 1}{q})^{2} ∑_{i} l_{i}^{α} ∑_{j≠i} l_{j}^{α} .

In the second case, v = (a^{p}b^{±1})^{m} for some m. Suppose v = (a^{p}b)^{m} (the other case is entirely similar). In this case we can again appeal to Lemma 3.1 if we use the basis x = a^{p}b, y = a for the free abelian group. Note that a = y and b = y^{−p}x, so that the lengths of the v_{i} increase by at most a factor of p + 1 with respect to the new basis. Also note that the commutator relation [x, y] = 1 involves just one use of the relator [a, b]. By Lemma 2.3, using the above translation, we get

Area((∏_{j} v_{j})v^{−1}) ≤ 2(p + 1)^{2} ∑_{i<j} |v_{i}||v_{j}|,

where the lengths are taken with respect to the basis {a, b}. Using Proposition 2.1 (as in the preceding paragraph) we bound the |v_{i}| in terms of l_{i} to obtain:

Area((∏_{j} v_{j})v^{−1}) ≤ 2 (\frac{(p + 1)^{2}}{q} )^{2} ∑_{i} l_{i}^{α} ∑_{j≠i} l_{j}^{α} .

This completes the proof of the claim and hence the proposition. □

Taking v to be the empty word in the above proposition we get the upper bound required to complete the proof of our main theorem:

Corollary 3.3. Suppose w = w(a, s, t) represents the identity in G_{p,q}. Then

Area(w) ≤ C|w|^{2α},

where |w| is the length of w with respect to {a^{±1}, s^{±1}, t^{±1}} and α = log_{2}(2p/q). In particular, the Dehn function for G_{p,q} satisfies

δ_{G_{p,q}}(n) ≼ n^{2α} .

§4. Generalizations

In this article we have focussed on the groups G_{p,q} in order to clarify the exposition as much as possible. However the same techniques apply more generally to fundamental groups of finite graphs of finitely generated abelian groups in which all of the edge groups are cyclic (and to a lesser those with arbitrary edge groups). The Dehn function of such an amalgam is again entirely dependent on the distortion of the vertex groups (equivalently, the amalgamated cyclic subgroups), and one can use the techniques of Section 2 to calculate the distortion. In order to obtain lower bounds on the Dehn function one should follow the proof sketched in (1.4). The argument given in Section 3 can be used to establish upper bounds in the more general setting but one needs the following refinement of Lemma 3.1.

Proposition 4.1. Let u_{1}, …, u_{m} be words in the generators of a free abelian group A of finite rank. There is a constant C, depending only on m and the length of the i_{i}, such that every equality of the form U_{0} = U_{1} … U_{r}, where U_{0}, …, U_{r} are all powers of the elements u_{i}, can be realized by applying at most C ∑_{i≠j} |U_{i}| |U_{j}| commutator relations between the generators of A.

Proof. Let u_{0} denote the u_{i} of which U_{0} is a power. Regarding them as elements in A ⊗ ℚ, choose among the u_{i} a maximal linearly independent set including u_{0}; write the basis elements other than u_{0} as b_{1}, …, b_{N}. Each of the u_{i} that is not in this basis has a minimal positive power that can be written as a ℤ-linear combination of the b_{i}, say u_{i}^{p_{i}} = β_{i} where β_{i} is a geodesic word in the b_{k}. Add to the natural presentation of A the relations U_{i}^{p_{i}} = β_{i}.

Let P_{0} := U_{1} … U_{r}. We rewrite each of the factors U_{j} beginning with U_{1}. If U_{1} is a power of one of our basis elements, we leave it. If it is not, say it is u_{i}^{q}, then we write q = sp_{i} + ρ where ρ is a non-negative integer less than p_{i}, we move u_{i}^{ρ} to the right in P_{0} to the next place where a power of u_{i} occurs as some U_{j}, and we replace the remaining u_{i}^{sp_{i}} by β_{i}^{s}. (The number of commutator relations necessary to make this last replacement is bounded by a constant.) If there is no subsequent occurrence of a power of u_{i} then we move u_{i}^{ρ} to the end of P_{0}, placing it immediately beyond W_{r}. The result is a product that differs from P_{0} in that we have changed the powers in U_{1} and U_{j} (or, if there is no sutiable U_{j} we accumulated an error term at the end of P_{0}).

We repeat this process, working along the factors of P_{0} from the left, moving the error terms until we eventually obtain a word of the form U′_{1} … U′_{r}U′′, where each U′_{i} is of the form B_{i}^{s_{i}} where B_{i} is a geodesic word in the b_{j} and U′′ is a word of length less than M := m max p_{i}. We then apply the minimum number of relations necessary to replace U′′ by a geodesic word in the b_{j} and apply Lemma 3.1. □

References

[Al] 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.

[BB] N. Brady and M. R. Bridson, On the absence of biautomaticity for graphs of abelian groups, Preprint, 1998.

[BGSS] G. Baumslag, S. Gersten, M. Shapiro and H. Short, Automatic groups and amalgams, J. Pure and Appl. Alg. 76 (1991), 229-316.

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

[Bo] B. H. Bowditch, A short proof that a subquadratic isoperimetric inequality implies a linear one, Mich. J. Math 42 (1995), 103–107.

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

[Br1] M.R. Bridson, Fractional isoperimetric inequalities and subgroup distortion, J. Amer. Math. Soc., to appear.

[Br2] M. R. Bridson, Area versus diameter in van Kampen diagrams, In preparation.

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

[Ge] S. M. Gersten, Isoperimetric and isodiametric functions of finite presentations, Geometric group theory, vol. 1 (G. Niblo and M. Roller, eds.), LMS lecture notes 181, Camb. Univ. Press, 1993.

[Gr1] M. Gromov, Hyperbolic groups, Essays in group theory (S.M. Gersten, ed.), MSRI series vol. 8, Springer Verlag, 1987.

[Gr2] M. Gromov, Asymptotic invariants of infinite groups, Geometric Group Theory, vol. 2 (G. Niblo and M. Roller, eds.), LMS lecture note series, vol. 181, CUP, 1993.

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

[Ly] I. G. Lysenok, On some algorithmic properties of hyperbolic groups, (English tanslation of Izv. 53 (1989)), Math. USSR Izv. 35 (1990), 145–163.

[Ni] G. A. Niblo (ed.), GGT 1991 problem list, Geometric Group Theory, vol. 1 (G.A. Niblo and M. Roller, eds.), LMS lecture note series, vol. 181, CUP, 1993.

[Niv] I. Niven, Irrational Numbers, The Carus Mathematical Monographs, No. 11, MAA, 1967.

[Ol] A. Yu Ol’shanski, Hyperbolicity of groups with subquadratic isoperimetric inequalities, Intl. J. alg. comp. 1 (1991), 281–290.

[Pa] P. Papasoglu, On the sub-quadratic isoperimetric inequality, Geometric group theory (R. Charney, M. Davis, M. Shapiro, eds.), de Gruyter, Berlin-New York, 1995.

[SBR] M. Sapir, J-C. Birget, E. Rips, Dehn functions of finitely presented groups, Preprint 1998.

[Sh] H. Short (ed.), Notes on word hyperbolic groups, Group theory from a geometrical viewpoint (E. Ghys, A. Haefliger, A. Verjovsky, eds.), Proc. ICTP Trieste, World Scientific, Singapore, 1991, pp. 3–64.

[SS] M. Shapiro and M. Stein, Some problems in geometric group theory, Geometric group theory (R. Charney, M. Davis, M. Shapiro, eds.), de Gruyter, Berlin, New York, 1995.

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

Department of Mathematics, University of Oklahoma, Norman, OK 73019