Free and fragmenting filling length

FREE AND FRAGMENTING FILLING LENGTH M. R. BRIDSON AND T. R. RILEY A. The filling length of an edge-circuit ηin the Cayley 2-complex of a finite presentation of a group is the minimal integer length Lsuch that there is a combinatorial null-homotopy of ηdown to a base point through loops of length at most L. We introduce similar notions in which the null-homotopy is not required to fix a base point, and in which the contracting loop is allowed to bifurcate. We exhibit a group in which the resulting filling invariants exhibit dramatically different behaviour to the standard notion of filling length. We also define the corresponding filling invariants for Riemannian manifolds and translate our results to this setting. 1. I Consider a vertical cylinder C⊆R3of height hand diameter d≪h. Let Sbe the surface formed by the curved portion of Cand the disc capping offits top. Topologically, Sis a closed 2-disc. The loop ∂Scan be homotoped in Sto a constant loop through loops of length at most πdby lifting it up the cylinder and then contracting it across the top of C. However, if we insist on keeping a basepoint on ∂Sfixed in the course of the null-homotopy then we will encounter far longer loops, some of length at least 2h. In this article we will bring to light similar contrasts between basepoint-fixed and basepoint-free null-homotopies for loops in the Cayley 2-complex Cay2(P) of a finite presentation Pof a group Γ. Words wthat represent 1 in Γ(null-homotopic words) correspond to edge-circuits ηwin Cay2(P). The filling length FL(w) of w was defined by Gromov [13] and in a combinatorial context is the minimal length Lsuch that there is a base point fixing, combinatorial null-homotopyof ηwthrough loops of length at most L. (A closely related notion called LNCH was considered by Gersten in [9].) We define FFL(w), the free filling length of w, likewise but without holding a base point fixed, and FFFL(w), the fragmenting free filling length of w, by also allowing the contracting loops to bifurcate. Detailed definitions are given in Section 2. Date: December 1, 2005. 2000 Mathematics Subject Classification. 2000 Mathematics Subject Classification: 20F65, 20F10, 53C23. Key words and phrases. filling length, null-homotopy, van Kampen diagram. 1 2 M. R. BRIDSON AND T. R. RILEY Our first goal is to construct a finite presentation in which FL(w) and FFL(w) differ dramatically for an infinite sequence of null-homotopic words of increasing length. [Our notational conventions are [a,b]=a−1b−1ab,ab=b−1ab and a−b= b−1a−1b. For f,g:N→N, we write fgwhen there exists C>0 such that for all nwe have f(n)≤Cg(Cn +C)+Cn +C, which gives an equivalence relation expressing qualitative agreement of the growths of fand g: write f≃gif and only if fgand gf.] Theorem A. Let Γbe the group with aspherical presentation Q:=ha,b,t,T, τ |aba−2,[t,a],[τ, at],[T,t],[τ, T]i. For n ∈Ndefine wn:=[T,a−bnτabn].Then wnis null-homotopic in Q, has length ℓ(wn)=8n+8, and FFL(wn)≃n, but FL(wn)≃2n. We assume the reader is familiar with van Kampen diagrams ([4] is a recent survey); they can be thought of as combinatorial homotopy discs for loops in the Cayley 2-complex of a presentation. We show that there are van Kampen diagrams ˆ ∆nfor wnthat, owing to geometry like that in our cylinder example, have FFL(ˆ ∆n)nand FL(ˆ ∆n)≃2n. Indeed, we will show that every van Kampen diagram ∆for wnhas intrinsic diameter 2n. (The intrinsic diameter of ∆is the maximal distance between two vertices as measured in combinatorial metric on ∆(1)) ; it will then follow that FL(wn)2n. The area Area(w) and intrinsic diameter IDiam(w) of ware the minimal Aand D, respectively, such that there is a van Kampen diagram for wwith A2-cells or with intrinsic diameter D. For M =Area,IDiam,FL,FFL or FFFL define filling functions M : N→Nfor finitely presented groups: M(n) :=maxM(w)|wnull-homotopic and ℓ(w)≤n. (The argument of M determines its meaning; the potential for ambiguity is tolerated as it spares us from a terminology over-load.) In the case M =Area, the function is the Dehn function. In spite of Theorem A, the filling functions FL and FFL for Qare ≃-equivalent: we will see in Section 3 that any van Kampen diagram for w′ n:= [T,a−bnτabnτabnτ−1a−bn] has two peaks and the savings that can be made by escaping the base point are no longer significant. On the other hand, if we allow our loops to bifurcate then they can pass over peaks independently. So FFFL exhibits markedly different behaviour. Theorem B. The filling functions IDiam,FL,FFL,FFFL : N→Nfor Qsatisfy IDiam(n)≃FL(n)≃FFL(n)≃Area(n)≃2n FFFL(n)≃n. FREE AND FRAGMENTING FILLING LENGTH 3 We remark that Γhas the properties IDiam(n)≃Area(n) and FL(n)≃Area(n), which are unusual in non-hyperbolicgroups. In contrast, if Area(n)≃nαfor some α≥2 then IDiam(n)nα−1– see [11]. Theorems A and B are proved in Section 3, modulo a number of auxiliary propositions postponed to Section 4. The remainder of this article is dedicated to establishing the credentials of FL, FFL and FFFL for inclusion in the pantheon of filling invariants, to relating them to other filling functions, and to interpretthem in terms of algorithmic complexity. As explained in [11], FL can be thought of as a space-complexity measure in that FL(w) is the minimal Lsuch that wcan be converted to the empty word through a sequence of words of length at most L, each obtained from the previous by free reduction, free expansion, or applying a relator. We will show in Section 2 that FFL and FFFL can be interpreted in a similar way: if we also allow conjugation we get FFL(w) and if we additionally include the move that replaces a word w=uv by a pair of words u,v, we get FFFL(w). This point of view is useful for calculations and allows us to prove that, as for FL, given a finite presentation, Area(n) is at most an exponential of FFFL. This and other relationships are spelt out in the following theorem, which shows, in particular, that Qof Theorem A provides an example of Area(n) outgrowing FFFL(n) as extremely as is possible. Theorem C. Let Pbe a finite presentation. There is a constant C, depending only on P, such that for all n ∈Nthe Dehn, filling length, free filling length, and fragmenting free filling length functions Area,FFL,FFFL : N→Nof Psatisfy Area(n)≤CFFFL(n) FFFL(n)≤FFL(n)≤FL(n)≤CArea(n)+n. In Section 5 we prove that FL(n), FFL(n) and FFFL(n) are all quasi-isometry invariants (and, in particular, are all group invariants – c.f. [12, Theorem 8.1]) of finitely presented groups, up to ≃-equivalence. Theorem D. If Pand P′are finite presentations of quasi-isometric groups then FLP≃FLP′,FFLP≃FFLP′,and FFFLP≃FFFLP′. In Section 6 we define analogous filling invariants FLX(n), FFLX(n) and FFFLX(n) describing the geometry of null-homotopies for rectifiable loops in arbitrary metric spaces X, and we prove: Theorem E. Supposea group Γwith finite presentation P=hA | Ri acts properly and cocompactly by isometries on a simply connected geodesic metric space X for which there exist µ, L>0such that every loop of length less than µadmits a based null-homotopy of filling length less than L. Then FLP≃FLX,FFLP≃FFLXand FFFLP≃FFFLX. 4 M. R. BRIDSON AND T. R. RILEY As the universal cover of any closed connected Riemmian manifold satisfies these conditions and (as is well known)every finitely presentable group is the fundamental groups of such a manifold, we can use Theorem E and its analogues for Area and IDiam (proved in [4, 6]) to obtain the following results from Theorem A and B. Corollary F. There exists a closed connected smooth Riemannian manifold M such that IDiame M(n)≃FLe M(n)≃FFLe M(n)≃Areae M(n)≃2n FFFLe M(n)≃n. Moreover, there is an infinte sequence of loops cnin e M such that ℓ(cn)→ ∞, FFLe M(cn)≃n, and FLe M(cn)≃2n. (Strictly speaking, the final part is not a direct corollary of the prior results, but it follows from the methods of Section 6: the wnof Theorem A can be used to construct word-like loops cnwith ℓ(cn)≃ℓ(wn); van Kampen diagrams witnessing to the upper bounds FFL(wn)nand FL(wn)2ncan be carried to fillings of cn showing FFLe M(cn)nand FLe M(cn)2n; and every null-homotopy of cnin e M has filling length 2nbecause the filling-disc corresponding to a null-homotopy induces a van Kampen diagram filling for wnwith ≃filling length.) Natural questions that remain open include the following. Open problem 1.1. Does there exist a finite presentation for which FL(n); FFL(n)? Open problem 1.2. Does there exist a finite presentation for which IDiam(n); FL(n)? In reference to the first of these problemswe note that for a finitely presentation hA | Ri of a group G, the presentation hA ∪ {t} | Ri for G∗Zsatisfies FL(n)≃ FFL(n) for the following reason. If wnis a word over Pwith FL(wn)=FL(n) then FFL([wn,t]) ≥2+ℓ(wn)+FL(wn) since any diagram for [wn,t] is a diagram for wn joined to a diagram for wn−1by a t-edge, and the most efficient way to shell such a diagram (from the point-of-view of FFL) is to shell the wndiagram, then collapse the t-edge, and then shell the wn−1diagram. The second problemwas posed by Gromov[13, §5C]. A negativeanswer would imply that the double exponential upper bound [7, 8] on the Dehn (i.e. area) function in terms of IDiam(n) could be improved to a single exponential using the single exponential upper bound [11, 13] for Area(n) in terms of FL(n). Acknowledgement. The second author is grateful for support from NSF grant 0404767 and for the hospitality of the Centre de Recerca Matem`atica in Barcelona during the writing of this article. FREE AND FRAGMENTING FILLING LENGTH 5 2. T     Let ∆be a diagram; that is, a finite, planar, contractible, combinatorial 2- complex; i.e. a van Kampen diagram bereft of any group theoretic decorations. Before discussing filling length, we recall and develop a combinatorial notion of a null-homotopy of ∆from [11] called a shelling. Definition 2.1. Ashelling S=(∆i) of ∆is a sequence of diagrams ∆ = ∆0,∆1, . . . , ∆m, in which each ∆i+1is obtained from ∆iby one of the shelling moves defined below and depicted in Figure 1. •1-cell collapse. Remove a pair (e1,e0) where e1is a 1-cell with e0∈∂e1 and e1is attached to the rest of ∆ionly by one of its end vertices ,e0. (We call such an e1aspike.) •1-cell expansion. Cut along some 1-cell e1in ∆ithat has a vertex e0in ∂∆i, in such a way that e0and e1are doubled. •2-cell collapse. Remove a pair (e2,e1) where e2is a 2-cell which has some edge e1∈(∂e2∩∂∆i). The effect on the boundary circuit is to replace e1 with ∂e2re1. We say that the shelling Sis full when ∆mis a single vertex. A full shelling to a base vertex ⋆= ∆mon ∂∆is a full shelling in which ⋆is preserved throughout the sequence (∆i). In particular, in every 1-cell collapse e0,⋆, and in every 1-cell expansion on ∆iwhere e0=⋆a choice is made as to which of the two copies of e0is to be ⋆in ∆i+1. We define a full fragmenting shelling Sof ∆by adapting the definition of a full shelling to allow each ∆ito be a disjoint union of finitely many diagrams, insisting that ∆mbe a set of vertices; we also allow one extra type of move: •Fragmentation. ∆i+1is the disjoint union of ∆′ iand ∆′′ i, where ∆i= ∆′ i∪∆′′ i and ∆′ i∩∆′′ iis a single vertex. 1-cell 1-cell 2-cell fragmentation collapse collapse expansion F 1. Shelling moves. 6 M. R. BRIDSON AND T. R. RILEY For a shelling S, define ℓ(S) :=maxiℓ(∂∆i), where ℓ(∂∆i) denotes the sum of the lengths of the boundary circuits of the components of ∆i. Then the filling length FL(∆, ⋆), the free filling length FFL(∆), and the fragmented free filling length FFFL(∆) are the minimum of ℓ(S) as Sranges over all full shellings to ⋆, full shellings, and all full fragmenting free shellings of ∆, respectively. This notation emphasizes the fact that FL(∆, ⋆) is defined with respect to a base vertex ⋆∈∂∆but FFL(∆) and FFFL(∆) are not. Let P=hA | Ri be a finite presentation of a group Γ. Define the filling length FL(w) of a null-homotopic word win a presentation P=hA | Ri by FL(w) :=minFL(∆, ⋆)|∆a van Kampen diagram for w, and FFL(w) and FFFL(w) likewise. A sequence S=w0,...,wmof null-homotopic words is a null-sequence if each wi+1is obtained from wiby one of the following moves: •Free reduction. Remove a subword aa−1or a−1afrom wi, where a∈ A. •Free expansion. This is the inverse of a free reduction. •Application of a relator. Replace a subword uof wiby a word vsuch that a cyclic conjugate of uv−1is in R±1. We define two more moves: •Cyclic conjugation. Replace wiby a cyclic permutation. •Fragmentation. Replace a word w=uv by a pair of words u,v. (In effect, insert a letter into wthat represents a blank space.) To employ the fragmentation move we must generalise our definition of a nullsequence so that each wiis a finite sequence of words, and when we perform any of the operations listed above we execute it on one of the words in wi. The following reassuring lemma is straight forward to prove. The “if” part is well known (indeed, freely reducing, freely expanding, and apply relators suffices). The “only if” part can be proved by an easy induction on the number of fragmentation moves used. Lemma 2.2. A word w over Prepresents the identity if and only if it can be reduced to a sequence of empty words by free reductions, free expansions, applying relators, cyclically conjugating, and fragmenting. For a null-sequenceS, define ℓ(S) :=maxiℓ(wi) where, if fragmentationmoves are employed, ℓ(wi) is the sum of the lengths of words in the sequence wi. Proposition1 in[11]says thatfor allnull-homotopicwordsw, we haveFL(w)=minSℓ(S), quantifying over null-sequences Sfor wthat employ free reductions,free expansions and applications of relators. We add the following. FREE AND FRAGMENTING FILLING LENGTH 7 Proposition2.3. Quantifyingover all null-sequencesSfor a null-homotopicword w, where free reduction,free expansion,applications of relators, and cyclic conjugation are allowed, we have FFL(w)=minSℓ(S).If, additionally, we allow fragmentations we get FFFL(w)=minSℓ(S). Proof. The proof in [11] that minSℓ(S)≤FL(w) is straightforward because the words around the boundary of the van Kampen diagrams in the course of a full shelling form a null-sequence. Each word in the sequence of boundary words in the course of a free shelling of a van Kampen diagram is only defined up to cyclic conjugation, as a base-vertexis not kept fixed during the shelling. It is then easy to see that minSℓ(S)≤FFL(w), quantifying over all all null-sequences Sfor wthat use free reduction,free expansion,applications of relators, and cyclic conjugation. Introducingfragmentation moves into the shelling, produces fragmentations in the corresponding null-sequence. And we see minSℓ(S)≤FFFL(w). The reverse bounds require more care. Given a null-sequence Sfor winvolving applications of relations and free expansions and reductions, we seek to construct a van Kampen diagram with a shelling during which the lengths of the boundary circuit remain at most ℓ(S). This can be done by starting with an edge-loop labelled by w, and filling it in by attaching a 2-cell on every application of a relator, by attaching a 1-cell on every free expansion, by folding together two adjacent 1- cells on every free reduction. However it is possible that the resulting complexwill not be planar: 2-spheres or other cycles may be pinched off(for example, when an inverse pair aa−1is inserted and then removed). Removing these cycles gives a van Kampen diagram ∆with FL(∆)≤ℓ(w). This is explained carefully in [11]. If Salso uses cyclic conjugation moves then no extra complications are added to the construction of ∆. If Salso uses fragmentations then the corresponding move in the course of the construction of ∆is to identify two vertices so that an inner boundary circuit is changed from a topological circle to a figure-eight.  Remark 2.4. (Filling length and space complexity.) Envisaging a null-sequence to be the course of a calculation on a Turing tape, we see that FL(w) is the nondeterministic space complexity of the following approach to solving the word problem for P: write won the tape and then exhaustively apply relators and perform free reductions and free expansions. A sequence of moves that converts w into the empty word amounts to a proof that wrepresents 1 in Pand FL(w) is the minimal upper bound on the number of places on the tape that have to be used in the calculation (see [10] for more details). If we allow cyclic conjugation then the non-deterministic space complexity is FFL(w). If we also including fragmentation then the non-deterministic space complexity is FFFL(w) plus the maximum number of blank spaces separating the words; that is, between FFFL(w) and 2FFFL(w). 8 M. R. BRIDSON AND T. R. RILEY The following inequalities are easy FFFL(w)≤FFL(w)≤FL(w)≤KArea(w)+ℓ(w),(1) IDiam(w)≤FL(w),(2) where Kis a constant depending only on P. (See [11] or [13].) Similar inequalities, for example IDiam(n)≤FL(n) for all n, relate the corresponding filling functions (defined in Section 1). It is well known [11, 13] that there is a constantC, that depends only on P, such that the Dehn function Area : N→Nof Psatisfies Area(n)≤CFL(n) for all n. This is essentially the bound Time-Space bound of algorithmic complexity: the number of different words of length FL(n) on an alphabet of size C is CFL(n), and as wadmits a null-sequence that does not include repeated words, CFL(n)is an upper bound on the number of times relations are applied in the nullsequence and hence on Area(w). The same proof applies to FFFL and so with (1) gives Theorem C. 3. P  T A B Proof of Theorem A. We exploit a technique due to the first author in [3] to show that the intrinsic diameter IDiam(wn) of wn=[T,a−bnτabn] is at least 2n. ∆ ΣΣ u0 µ u u uv bn bn bnbn bn bn bn bn bn bn bn bn aa a a a a TT τ τ τ τ F 2. A van Kampen diagram ∆for wnwith a subdiagram Σ. Suppose π:∆→Cay2(Q) is a van Kampen diagram for wn. Figure 2 is a schematic depiction of ∆and Figure 3 shows an explicit example when n=3. We seek an edge-path µin ∆, along which reads a word in which the exponent sum of the letters tis 2n. A T-corridor through ∆connects the two letters Tin wn. Along each side of this corridor we read a word uin nt±1, τ±1o⋆. Let Σbe a subdiagram FREE AND FRAGMENTING FILLING LENGTH 9 of ∆with boundary made up of one side of the T-corridor and a portion of ∂∆ labelled a−bnτabn. A τ-corridor in Σjoins the τin a−bnτabnto some edge-labelled τ in u. Let u0be the prefix of usuch that the letter immediately following u0is this τ, and then let µbe the edge-path along the side of the τ-corridor running from the vertex at the end of a−bnto the vertex at the end of u0. Let v∈n(at)±1o⋆be the word along µ. Then u0=abnvin Q. Killing T,tand τ, retracts Qonto the subpresentation ha,b|ab=a2i. So v=abnin ha,b|ab=a2i, where v∈na±1o⋆is vwith all letters t±1removed. It follows that the exponent sum of the letters in vis 2nand hence that µhas the asserted property. Killing all generators other than tdefines a retraction φof Qonto htiZthat is distance decreasing with respect to word metrics. But the image of φ◦π:∆→Z has diameter at least 2non account of µ. So IDiam(wn)≥2n, as claimed. It is easy to check that the van Kampen diagram ˆ ∆nfor wnconstructed below admits a shelling down to their base vertex that realises the bound FL(wn)2n. So, as IDiam(wn)≤FL(wn), we deduce that IDiam(wn)≃FL(wn)≃2n. The bound FFL(wn)nfollows from Proposition 4.4. None-the-less we will sketch a proof since the salient ideas, developing the cylinder example from Section 1, appear here more transparently than in the more general contexts of Section 4. The van Kampen diagram ˆ ∆3for w3is depicted in Figure 3. The analogous construction of the diagram ˆ ∆nfor wnshould be clear. Within ˆ ∆nthere are four triangular subdiagrams over the subpresentation ha,t|[a,t]i, in which strings of a-edges run vertically (in the sense of Figure 3). Cut along each of these strings (except those of length 2nat the left and right sides of the diagrams) and insert back-to-back copies of the ha,b|ab=a2i-diagrams Ωkthat shortcut akto a word ukof length ∼log2kn. These shortcut diagrams Ωkare constructed in Proposition 4.1 and the way they are inserted is shown (in a more general context) in Figure 8. Call the resulting diagram ∆n. For 0 ≤k≤2nlet ˆρkbe the edge-paths in ˆ ∆n, forming concentric squares in Figure 3, labelled by akTa−kτ−1akT−1a−kτ. Next, for 0 ≤k≤2ndefine ρkto be the edge-path in ∆nthat is obtained from ˆρkby replacing each subword a±kby its shortcut uk±1. (In particular ρ2n=∂∆n.) Note that for all k, the length of ρkis n. We now briefly describe a full shelling of ∆nthat realises the bound FFL(wn) n. In the course of this shelling we encounter the subdiagrams of ∆nthat have ρkas their boundary loops. The following lemma concerning the diagrams Ωkof Proposition 4.1 is the key to shelling the subdiagram bounded by ρk+1down to that bounded by ρk. The length of the boundary loop is kept within nsince log2k≤n. Lemma 3.1. Let Πbe the van Kampen diagram comprising a copy of Ωk+1and a copy Ωkjoined to each side of a t-corridor along sides labelled ak+1. Let ⋆be a 16 M. R. BRIDSON AND T. R. RILEY such that ℓT(w)=ℓτ(w)=2and the occurrences of T±1and τ±1alternate in w. Then FFL(w)≤Cℓ(w)where C >0depends only on Q. Proof. In any van Kampen diagram ∆for wthere is one T-corridor and one τcorridor. The condition that the occurrences of T±1and τ±1in walternate is equivalent to saying that these corridors cross at least once in ∆. Take ∆to be a minimal area diagram. We argue that the two corridors cross exactly once. The words along the sides of the Tand τ-corridors are of the form α1tǫ1α2tǫ2...tǫp−1αpand β1(at)µ1β2(at)µ2...(at)µq−1βq, where ǫi, µi=±1 and αi∈ nt±1o⋆and βi∈n(at)±1o⋆for all i. Further, the αiand βimust be reduced because otherwise ∆would not be a reduced diagram and hence not be of minimal area. Suppose, for a contradiction,that the Tandτ-corridorscrossmorethanonce. Then there is a subdiagram between the two corridors with boundary word w0=uv where u∈nt±1o⋆and v∈n(at)±1o⋆. Killing all the generators other than tretracts Qonto hti=Zand so ℓt(w0)=0. It follows that ℓa(w0)=0 because killing t,τ and Tretracts Qonto the subpresentation Pin which ahas infinite order. So νis not freely reduced and we have a contradiction. An additional feature of a minimal area diagram is that it contains no Tor τ-annulus. This can be proved by a similar method to the above. Conclude that ∆consists of a T-corridor, a τ-corridor and four subdiagrams of the form where Proposition4.3 applies. Producea newvan Kampen diagram ∆′for wby replacing the four subdiagrams that minimise the length Lof Proposition 4.3. A shelling of ∆′realising the asserted bound is obtained byrunning shellings of the four subdiagramsand the two corridorsconcurrentlyin the obviousway so that the diagram is eventually shelled to the [τ, T]-2-cell, and then to a single vertex.  Proposition 4.5. Suppose w is a null-homotopic word in Q(defined above) and ℓT(w)=2. Then FFFL(w)≤Cℓ(w)where C >0depends only on Q. Proof. Let ∆be a reduced van Kampen diagram for w. We will use the layout of the τ-corridors and the one T-corridor in ∆as a template for the construction of another van Kampen diagram ∆2for wthat will admit a shelling realising the asserted bound. Suppose Cis a τ-corridor in ∆that does not cross the T-corridor. The word wC along the sides of Cis in {(at)}⋆and is reduced because ∆is a reduced diagram, and so must be (at)kfor some k∈Z. Killing all defining generators other than t retracts Qonto hti. So k≤ℓ(λ), where λis a portion of the boundary circuit of ∆ connecting the end points of a side of C. If follows that if we remove any number of τ-corridors that do not cross the T-corridor from ∆, then the length of the boundary circuit of each connected component is at most 2ℓ(w). Suppose we remove all of the τ-corridors that do not cross the T-corridor from ∆. Define ∆0to be the connected component that contains the T-corridor. All of FREE AND FRAGMENTING FILLING LENGTH 17 the other connected components have boundary words that are null-homotopic in Q0=ha,b,t|aba−2,[t,a]i, which is both a retract and a subpresentation of Q. Obtain ∆1from ∆by replacing all these subdiagrams by Q0-diagrams of minimal FFL. Repeating the followinggives a shelling of ∆1downto ∆0in the course ofwhich the boundarycircuit has length at mostC0ℓ(w), whereC0is a constant that depends only on Q. Choose a τ-corridorCin ∆1such that, of the tow componentswe get by removingC, that which does not contain the T-corridor contains no τ-corridor. Cut along one side of Cusing 1-cell expansion moves, and one fragmentation move. Next use 1-cell collapse and 2-cell collapse moves to remove the 2-cells along C. By the remarks above, both connected components have boundary circuits of length at most 2ℓ(w). Collapse the component that does not contain the T-corridor down to a single vertex using a minimal FFL shelling, in the course of which the boundary circuit has length at most a constant times 2ℓ(w) by Proposition 4.2. (In fact, a shelling down to ∆0within the required bound, can be achieved without the fragmentation move if care is taken over base points.) It remains to show that the word w0around ∂∆0admits a van Kampen diagram with a full, fragmenting, free shelling in which the sum of the lengths of the boundaries of the components are at most a constant times ℓ(w0). For then we can take ∆2to be ∆1with ∆0replaced by this diagram. First suppose ℓτ(w0)=0. Then w0is null-homotopic in the retract Q1:= ha,b,t,T|aba−2,[t,a],[T,t]i, and the length of the T-corridor in any reduced Q1-diagram ∆′ 0for w0is at most ℓ(w0)/2 on account of the retraction onto hti. Assume that the two components of ∆′ 0we get on removing the T-corridor are Q0-diagrams of minimal FFL. Then we can collapse ∆′ 0by shelling each of these componentsand the T-corridor in turn, and using Proposition 4.2 it is easy to check that the length of the boundary circuit remains at most a constant times ℓ(w0). Next suppose ℓτ(w0)=2. Then Proposition 4.4 applies and gives us the result we need. τ τ τ τ τ τ τ τ τ τ τ ττε τε τε τε w1 w1 w1 w1 w1T TT T F 9. Shelling away one τ-corridor. 18 M. R. BRIDSON AND T. R. RILEY Finally, suppose ℓτ(w0)>2. Then there is a subword τεw1τ−εin w0, where ε= ±1, ℓτ(w1)=0 and ℓT(w1)=1. As τεw1τ−ε=w1in Q, there is a Q-van Kampen diagramfor w0that wecan shell by cutting along an edge-pathlabelled by w1to cut the diagram into two, as shown in Figure 9, and the shelling the two components. One of these components is a diagram for τεw1τ−εw1−1, and this we shell first as per Proposition 4.4. The remaining component has boundary length ℓ(w0)−2 and includes two fewer letters τ±1, and so by continuing inductively we can find a shelling for which FFFL is at most a constant times ℓ(w0).  Proposition 4.6. Suppose w is a null-homotopic word in Q2:=ha,b,t, τ |aba−2,[t,a],[τ, at]i. Then FL(w)≤Cℓ(w)where C >0depends only on Q2. Proof. The method used in the proof of Proposition 4.4, to reduce to the case where all the τ-corridors cross the T-corridor, gives this result.  Proposition 4.7. Suppose w is a null-homotopic word in Q. Then FFFL(w)≤ Cℓ(w)where C >0depends only on Q. Proof. The cases where ℓT(w)=0 and ℓT(w)=2 are dealt with by Propositions 4.6 and 4.4, respectively. For the case ℓT(w)>2 we take a similar approach to that used in the proof of Proposition 4.4 to control FFFL(w0). There isasubwordTεw1T−εinw, whereε=±1andTεw1T−ε=w1in Q. So we can find a Q-van Kampen diagram for wthat can be severed into two components, one of which is a diagram for Tεw1T−εw1−1, and the other of which is a diagram for a word of length ℓ(w)−2 that has two fewer letters T±1. The former of these two components can be shelled as per Proposition 4.4. Continuing inductively we see that the other component can be taken to be a diagram that admits a shelling in which the boundary circuit has length at most a constant times ℓ(w).  5. Q-  In this section we prove Theorem D. Our approach is to monitor how filling length, in its three guises, behaves in the standard proof that finite presentability is a quasi-isometry invariant [5, page 143]. As careful quantified versions of this proofare well established ([1], addressing Area, is the first in print), our exposition here will be brief. We have quasi-isometric groups Γand Γ′with finite presentations P=hA | Ri and P′=hA′| R′i, respectively. So there is a quasi-isoemtry f: (Γ,dA)→ (Γ′,dA′) with quasi-inverse g: (Γ′,dA′)→(Γ,dA). We begin by showing FLP≃FLP′. Suppose ρ′is an edge-circuit in the Cayley graph of P′, visiting vertices v0,v1,...,vn=v0in order. Consider a circuit ρin the Cayley graph Cay1(P) FREE AND FRAGMENTING FILLING LENGTH 19 of Pobtained by joining the successive vertices of g(v0),g(v1),...,g(vn) by geodesics. Note that ℓ(ρ) is at most a constant times ℓ(ρ′). Fill ρwith a van Kampen diagram ∆over Padmitting a shelling Sof filling length FLP(ℓ(ρ)) and use fto map ∆(0) to P′. Then join f(a) to f(b) by a geodesic whenever aand bare the end points of an edge in ∆. The result is a combinatorial map π′ 0:∆′ 0(1) →Cay1(P′) filling a loop ρ′ 0, where ∆′ 0is obtained from ∆by subdividing each of its edges into edge-paths of length at most some constant. Interpolate between ρ′and ρ′ 0by joining vito f(g(vi)) for every i, to build a map π′ 1:∆′ 1(1) →Cay1(P′) where ∆′ 1is obtained from ∆′ 0by attaching an annulus Aof n2-cells around the boundary. A shelling S′ 1of ∆′ 1down to the base vertex with ℓ(S′ 1) at most a constant times (1+FLP(ℓ(ρ))) is obtained by first shelling away A, to leave just a stalk from v0to f(g(v0)), and then running a shelling of ∆′ 0modelled on S: where Sdemands the collapse of a 1-cell in ∆collapse all the 1-cells in the corresponding edge-path in ∆′ 0.However, whilst the words around the 2-cells of ∆′ 1are null-homotopic they may fail to be in R′, so ∆′ 1may not be a van Kampen diagram over P′. To rectify this we will replace the 2-cells of∆′ 1byvan KampendiagramsoverP′, eachofarea at most some uniform constant. A concern here is that van Kampen diagrams can be singular 2-discs and so gluing them in place of 2-cells may destroy planarity. This is dealt with by replacing the 2-cells of ∆′ 1one at a time; on each occasion, if the 2-cell e2to be replaced has non-embeddedboundary circuit then we discard all the edgesinside the simple edge-circuitσin ∂e2such that no edge of ∂e2is outside σ, and then we fill σ. The result is a van Kampen diagram ∆′ 2for ρ′over P′. We obtain a shelling S′ 2for ∆′ 2by altering S′ 1: each time we discarded some connected component of the set of edges inside some σwe contract it (more strictly, its preimage) and all the 2-cells it encloses to a single vertex in every one of the diagrams comprising the shelling, and each time we fill some 2-cell e2with a van Kampen diagram Dwe shell out all of Dwhen we had been due to performa 2-cell collapse move on e2. [This could fail to give a shelling when a 2-cell collapse move in S′ 1 removes a pair (e2,e1), where e1is one of the now contracted edges – but then a 1- cell expansion followed by a 2-cell collapse producing the same effect can be used instead.] The difference between ℓ(S′ 1) and ℓ(S′ 2) is then at most some additive constant. Deduce that FLP′FLP. Interchanging Pand P′we have FLPFLP′ and so FLP≃FLP′. The proof that FFLP≃FFLP′is essentially the same, except we consider free shellings, we discard the stalk between v0and f(g(v0)), and we replace FLP(ℓ(ρ)) by FFLP(ℓ(ρ)). To show FFFLP≃FFFLP′we additionally allow free and fragmenting shellings and we use FFFLP(ℓ(ρ)) in place of FLP(ℓ(ρ)); no further technical concerns arise. 20 M. R. BRIDSON AND T. R. RILEY 6. R     Suppose c: [0,1] →Xis a loop in a metric space X. Abased null-homotopy H of cis a continuous map H: [0,1]2→Xfor which H(0,t)=H(1,t)=c(0) for all tand, defining Ht: [0,1] →Xby Ht(s)=H(s,t), we have H0=cand H1(t)=c(0) for all t. Afree null-homotopy H of cis a continuous map H: [0,1]2→Xsuch that H(0,t)=H(1,t) for all t, and H0and H1are cand a constant function, respectively. Let Sbe the set of subspaces Sof [0,1]2that have [0,1] × {0} ⊂ Sand are the union of a finite family of solid closed triangles ∆i=[(ai,0),(bi,0),(ci,di)] with ci∈[ai,bi] and di∈(0,1]. The fibres Stof the projection mapping points in Sto their second co-ordinate are disjoint unions Fkt i=1It,i× {t}of closed intervals It,i. At finitely many critical t-values τi, intervals comprising the fibres bifurcate or collapse to a point. Afree and fragmenting null-homotopy H of cis a continuous map H:S→X for some S∈ S where, defining Htto be the restriction of Hto St, we find that H0=c, that H1is constant on I1,ifor all i, and that Ht(x)=Ht(y) for all t, whenever xand yare the end points of some It,i. We define ℓ(Ht) to be the sum of the lengths of the ktloops in Xdefined by Ht. Note that taking Sto be a single triangle reduces to the case of a free null-homotopy. In each of the three settings above define ℓ(H) :=supt∈[0,1] ℓ(Ht), and then FL(c)=inf ℓ(H)|based null-homotopies Hof c FFL(c)=inf ℓ(H)|free null-homotopies Hof c FFFL(c)=inf ℓ(H)|free and fragmenting null-homotopies Hof c. For M =FL,FFL or FFFL, define MX: [0,∞)→[0,∞) by MX(l)=supM(c)|null-homotopicloops cwith ℓ(c)≤l. The following lemma gives sufficient conditions for FLX, FFLXand FFFLXto be well-defined – conditions enjoyed by the universal cover of any closed connected Riemannian manifold, for example. Lemma 6.1. Suppose X is the universal cover of a compact geodesic space Y for which there exist µ, L>0such that every loop of length less than µadmits a based null-homotopy of filling length less than L. Then FLX,FFLXand FFFLXare well-defined functions [0,∞)→[0,∞). Proof. The proof of Lemma 2.2 in [6] can readily be adapted to this context. In brief, we first show that every rectifiable loop cin Xadmits a based null-homotopy with finite filling length – apply a compactness argument to an arbitrary based null-homotopy for cto partition cinto finitely many loops of length at most µ; by hypothesis each such loop has finite filling length and it follows that chas finite filling length. FREE AND FRAGMENTING FILLING LENGTH 21 Next suppose chas length land assume (by shrinking µif necessary) that balls of radius µin Ylift to X. Cover Ywith a maximal collection of disjoint balls of radius µ/10 >0; let Λ⊂Xbe the set of lifts of their centres. Subdivide cinto m≤1+10ℓ/µ arcs with end-points vi, each of length at most µ/10; each vilies within µ/5 of some ui∈Λ; form a piece-wise geodesic loop c′approximating c by connecting-up these ui. Loops made up of the portion of cfrom vito vi+1and geodesics [ui,ui+1], [ui,vi] and [ui+1,vi+1] have length at most µ, and so homotopy discs for these loops together form a collar between cand c′. By passing across these discs one at a time, it is possible to homotop cacross the collar to a loop made up of c′and a stalk of length µ/5 from c(0) to a u0, encountering loops only of length at most a constant (depending on Land µ) times len route. Modulo the action of π1Y, there are only finitely many such piecewise geodesic loops such as c′and, by our earlier argument, each one admits a filling of finite filling length. It follows that FLX, and hence FFLXand FFFLX, are well-defined functions.  Proof of Theorem E. Fix a basepoint p∈X. Define a quasi-isometry Φmapping the Cayley graph of P=hA | Ri to Xby choosing a geodesic from pto its translate a·pfor each a∈ A, and then extending equivariantly. Let Ψbe a quasi-isometry from Xto Γsending x∈Xto some γsuch that γ.pis a point of Γ.pclosest to x. A path in Xis called word-like (following [4]) if it is the image in Xof an edgepath in the Cayley graph. For each r∈ R, let crdenote the word-like loop in X, based at pthat is the image of an edge-circuit in the Cayley graph labelled r. Map the Cayley 2-complex of Pto Xby choosing a disc-filling arising from a based null-homotopy of finite filling length for each cr. We will show first that FLXFLP, FFLXFFLPand FFFLXFFFLP. As in the proof of Lemma 6.1, a collar between an arbitrary rectifiable loop cin X and a word-like loop c′, can be used to show there is no change in the ≃classes of FLX, FFLXor FFFLXif one takes the suprema in their definitions to be over fillings of word-like loops only: for FLXone notes that ccan be homotoped across the collar to a loop based at c(0) that is obtained from c′by attaching a stalk from c(0) to c′(0), and one need pass through loops of length no more than Cℓ(c)+C en route, where Cis a constant independent of c; for FFLXand FFFLX, the stalk is abandoned and the homotopy is between cand c′. One gets an upper bound on the filling length of a word-like loop cin Xby taking the image in Xof a minimal filling length van Kampen diagram ∆. The progress of the boundarycircuit in the course of a shelling of ∆dictates a sequence of stages in a null-homotopy of c. Using Lemma 6.1, we can interpolate between these stages in a way that increases the length of the curve by no more than an additive constant, and so we get FLXFLP. The proof that FFLXFFLPand FFFLXFFFLPcan be completed likewise. 22 M. R. BRIDSON AND T. R. RILEY Now we address FLPFLX. Consider a word-like loop c: [0,1] →X corresponding to a null-homotopic word wover Pof length n. Fix a constant λ > maxa∈A dX(p,a.p). Then ℓ(c)≤λn. Let H: [0,1]2→Xbe a based nullhomotopy of cwith filling length at most 1 +FLX(λn). By uniform continuity, there exists ε > 0 such that ε−1∈Zand dX(H(a),H(b)) ≤1 for all a,b∈[0,1]2 with dE2(a,b)≤ε. Subdivide [0,1]2into ε−1rectangles separated by the lines t=tjwhere tj=jε and j=0,1,...,ε−1. For all such t=tj, take 0 =st,0<st,1< . . . < st,kt=1 in such a way that for all i, the restriction of Htto [st,i,st,i+1] is an arc of length at most λand kt≤1+ℓ(Ht)/λ. Mark the points st,0,...,st,ktonto each of the lines t=tj. Then, for all j=0,1,...,ε−1−1 and all i=1,2,...,ktj−1, join (st,i,tj) to (st,i′,tj+1) by a straight-line segment where (st,i′,tj+1) is the first marked point reached from by (st,i,tj+1) by increasing the s-co-ordinate. Note that (3) d(Htj(st,i),Htj+1(st,i′)) ≤1+λ. In the same way, for all j=1,...,ε−1and for all i=1,...,ktj−1 such that (st,i,tj) is not the terminal vertex of one of the edges we just connected, join (st,i,tj) to some (xt,i′,tj−1) for which (4) d(Htj(st,i),Htj−1(st,i′)) ≤1+λ, so as to produce a diagram ∆in which every 2-cell has boundary circuit of combinatorial length at most 4. Orient every edge eof ∆arbitrarily and define ge:= Ψ(Ht′(s′))Ψ(Ht(s))−1 when the initial andterminal pointsof eare(s,t) and (s′,t′), respectively. It follows from (3) and (4) that gehas word length |ge|at most some constant Kwith respect to A. Subdivide einto a path of |ge|edges; give each of these new edges an orientation and a labelling by a letter in Aso that one reads a word representing ge along the path. Make all the choices in the construction above in such a way that wlabels the line t=0 and all the other edges in ∂∆are labelled by e. The shelling (∆i) of ∆which strips away the rectangles from left to right, shelling each in turn from top to bottom, has max iℓ(∆i)≤K(1 +FLX(λn)) +4K. Let wibe the word one reads aroundthe boundary circuit of ∆i. Each 2-cell in each ∆ihas boundary circuit labelled by a null-homotopic word that may not be in R, but has length at most 4K. So it is possibleto interpolatebetween the wito produce a null-sequence (see Section 2) with respect to Pfor w=w0in which every word has length at most K(1 +FLX(λn)) +4Kplus a constant. Thus FLPFLX, as required. FREE AND FRAGMENTING FILLING LENGTH 23 That FFLPFFLXcan be proved in the same way. The argument needs to be developed further to show that FFFLPFFFLX. Given the word-like loop c, one takes a free and fragmenting null-homotopy H:S→Xof cwith ℓ(H) at most FFFLX(ℓ(c)) +1and with the property that whenever loops of length less than some prior fixed constant appear, those loops are contracted to points before any further bifurcations occur. This implies that for all t, the number of connected componentsktin the fibre St=Fkt i=1It,i×{t}is at most a constant times (1+ℓ(Ht)). For the construction of ∆we inscribe Swith the arcs of its intersection with the lines t=tjand with the additional lines t=τi, where τiare the critical t-values of H. Using Htand Ψas before, we subdivide the fibre Stinto edges and label each of its ktconnected components by a null-homotopic word – this works as before, except we additionally insist that the end points of the closed intervals It,i comprising Stbe included amongst the si– this may add ktto the total length the words along St, but the argument given above ensures that this additional cost is no more than a constant times (1 +ℓ(Ht)).  R [1] J. M. Alonso. In´egaliti´es isop´erim´etriques et quasi-isom´etries. C.R. Acad. Sci. Paris Ser. 1 Math., 311:761–764, 1990. [2] G. Baumslag, S. M. Gersten, M. Shapiro, and H. Short. Automatic groups and amalgams. J. Pure Appl. Algebra, 76(3):229–316, 1991. [3] M. R. Bridson. Asymptotic cones and polynomial isoperimetric inequalities. Topology, 38(3):543–554, 1999. [4] M. R. Bridson. The geometry of the word problem. In M. R. Bridson and S. Salamon, editors, Invitations to Geometry and Topology, pages 33–94. O.U.P., 2002. [5] M. R. Bridson and A. Haefliger. Metric Spaces of Non-positive Curvature. Number 319 in Grundlehren der mathematischen Wissenschaften. Springer Verlag, 1999. [6] M. R. Bridson and T. R. Riley. Extrinsic versus intrinsic diameter for Riemannian filling-discs and van Kampen diagrams. preprint, 2005. [7] D. E. Cohen. Isoperimetric and isodiametric inequalities for group presentations. Int. J. of Alg. and Comp., 1(3):315–320, 1991. [8] S. M. Gersten. The double exponential theorem for isoperimetric and isodiametric functions. Int. J. of Alg. and Comp., 1(3):321–327, 1991. [9] S. M. Gersten. Asynchronously automatic groups. In Charney, Davis, and Shapiro, editors, Geometric group theory, pages 121–133. de Gruyter, 1995. [10] S. M. Gersten, D. F. Holt, and T. R. Riley. Isoperimetric functions for nilpotent groups. GAFA, 13:795–814, 2003. [11] S. M. Gersten and T. R. Riley. Filling length in finitely presentable groups. Geom. Dedicata, 92:41–58, 2002. [12] S. M. Gersten and T. R. Riley. Some duality conjectures for finite graphs and their group theoretic consequences. To appear in Proc. Edin. Math. Soc., http://www.math.utah.edu/∼gersten/grouptheory.htm/,2003. [13] M. Gromov. Asymptotic invariants of infinite groups. In G. Niblo and M. Roller, editors, Geometric group theory II, number 182 in LMS lecture notes. Camb. Univ. Press, 1993. 24 M. R. BRIDSON AND T. R. RILEY M R. B Mathematics, Huxley Building, Imperial College, London, SW7 2AZ, UK [email protected], http://www.ma.ic.ac.uk/∼mbrids/ T R. R Mathematics Department, 310 Malott Hall, Cornell Univ., Ithaca, NY 14853-4201, USA tim.ril[email protected]ell.edu, http://www.math.cornell.edu/∼riley/