The unbounded dead-end depth propertie is not a group invariant

THE UNBOUNDED DEAD-END DEPTH PROPERTY IS NOT A GROUP INVARIANT TIM R. RILEY AND ANDREW D. WARSHALL Abstract. The dead-end depth of an element gof a group with finite generating set Ais the distance from gto the complement of the radius dA(1, g) closed ball, in the word metric dA. We exhibit a finitely presented group Kwith two finite generating sets Aand B such that dead-end depth is unbounded on Kwith respect to Abut is bounded above by two with respect to B. 1. Introduction Suppose Gis a group with finite generating set Aand associated word metric dA. The dead-end depth (or, more concisely, the depth) of g∈G with respect to Ais the distance between gand the complement of the ball of radius dA(1, g) centered at 1 in G. (If the ball is all of Gthen the depth of gis infinite.) An element gof depth greater than one is called a dead end because a geodesic from 1 to gin the Cayley graph cannot be continued to a group element beyond g. In general, depth depends on the generating set. For example, all elements of Z=haihave depth 1 in (Z,{a}), but the depth of ain (Z,a2, a3) is 2. This article addresses how radical the dependence can be. Cleary & Taback [5, 6] showed depth to be unbounded in the lamplighter group Z2oZand similar wreath products, with respect to certain finite generating sets – for instance {a, t}, where Z2oZis presented by ha, t | a2; [ati, a],∀i∈Zi. (Independently, Erschler observed that Z2oZprovides an example resolving the closely related Question 8.4 of Bowditch in [1].) This prompted the question (asked by Taback, lecturing at CUNY in April 2004, and subsequently in print by Cleary and the first author in [4]) whether the property of depth being unbounded is a group invariant, that is, is independent of the finite generating set. Indeed, there was speculation on whether the property might be a quasi-isometry invariant. We answer these Date: 31 March 2005, revised 9 September 2005. 1 2 TIM R. RILEY AND ANDREW D. WARSHALL questions negatively. (We denote the commutator a−1b−1ab by [a, b] and the conjugates b−1ab and b−1a−1bby aband a−b, respectively.) Theorem 1. The group Kwith finite presentation ha, s, t, u |a2,[a, at],[s, t],[s, u],[t, u], a−saat, a−uati has unbounded dead-end depth with respect to the generating set A={a, s, t, u, as, at, au, sa, ta, ua, asa, ata, aua } but dead-end depth bounded above by 2with respect to B=A ∪ {tu, atu, tau, tua, atau, atua, taua, ataua, ut−1, aut−1, tat−1, t−1at, atat−1, at−1at }. Dead ends and depth have been studied in a variety of settings. In addition to those already mentioned these include SL2(Z) and hx, y|x3 ,y3 ,(xy)ki (see [2]), Thompson’s group F(see [8]), and presentations satisfying the C0(1/6) small cancellation condition (see [3]). Also IV.A.13,14 of [7] contain a discussion of (non-) dead ends under the name “extension property for geodesic segments.” Dead ends and depth (not so-termed in [9]) are the key to a striking result of Lyons, Pemantle & Peres [9]: they show that random walks on the lamplighter group biased suitably towards the identity (“homesick” random walks) move outward from the identity faster than simple random walks. The point is that the homesick random walk will escape dead ends faster than a simple random walk. In general, it seems hard to understand the behaviour of depth in a group as the finite generating set varies. Even depth in Zis not entirely straightforward. For any given finite generating set, depth is bounded – indeed, Bogopol’ski˘ı showed this to be the case to be the case in all infinite hyperbolic groups [2]. However, as we will show in Section 6, depth in Zis not uniformly bounded as the generating set varies: Proposition 2. For all k∈N, there exists a finite generating set Afor Z for which there is a group element of depth greater than kin (Z,A). En route to Theorem 1 we will prove an analogous result for a group that is finitely generated but not finitely presentable: Theorem 3. The group Hpresented by ha, t, u |a2,[t, u], a−uat;∀i∈Z,[a, ati]i THE UNBOUNDED DEAD-END DEPTH PROPERTY 3 has unbounded depth with respect to the generating set C={a, t, u, at, ta, ata, au, ua, aua } but depth bounded above by 2with respect to D=C ∪ {tu, atu, tau, tua, atau, atua, taua, ataua, ut−1, aut−1, tat−1, t−1at, atat−1, at−1at }. The construction of His similar to that of Z2oZ: specifically, H= Li∈ZZ2o Z2,where aigenerates the i-th copy of Z2in the direct sum, Z2=ht, ui, and the actions of uand tare given by ait=aiu=ai+1. Defining a:= a0we find ai=ati, and the presentation given in Theorem 3 can be obtained by simplifying h(ai)i∈Z, t, u |[t, u] ; ∀i, j ∈Z,[ai, aj], aitai+1 −1, aiuai+1 −1, ai2i. (Identifying tand uretracts Honto Z2oZand so gives a way of obtaining a presentation of Z2oZfrom a presentation for Hthat shows Hnot to be finitely presentable because Z2oZis not finitely presentable.) The group G of [4] presented by ha, s, t |a2,[a, at],[s, t], a−saati was the first example of a finitely presentable group with unbounded deadend depth with respect to some finite generating set, specifically {a, s, t, at, ta, ata, as, sa, asa}. The group Kof Theorem 1 is related to G similarly to how His related to the lamplighter group. This article is organised as follows. Sections 2 and 4 describe lamplighter models that aid understanding of the geometries of Hand K, and Sections 3 and 5 contain proofs of Theorems 3 and 1, respectively. The brief Section 6 contains a proof of Proposition 2 on depth in Z. Acknowledgement. We thank Joshua Zelinsky for his assistance with Proposition 2 and an anonymous referee for a careful reading. 2. A lamplighter model for H Cannon’s lamplighter model is a well-known aid to understanding Z2oZ. It involves a lamplighter moving along a Z-indexed string of lamps and toggling them between on and off. We will describe a similar model for H. We will give a faithful transitive left action of Hon Pfin(Z)×Z2, where Pfin(S) denotes the collection of finite subsets of a set S. Killing adefines a retraction L:H→→ ht, ui∼ =Z2that gives the location L(g) = (q, r) of a lamplighter among the Z2-lattice points of the plane after the left action of gon (∅,0). (Here, qand rare the t- and u-coordinates, respectively, of the 4 TIM R. RILEY AND ANDREW D. WARSHALL lamplighter and 0:= (0,0).) In contrast to the lamplighter model for Z2oZ, we conceive the lamps to be infinitely long bulbs (like a long fluorescent tube). These are Z-indexed and the i-th lamp runs along the entire length of the line x+y=ias illustrated in Figure 1. Defining actions of t,uand aon Pfin(Z)×Z2as follows extends to an action in which an element of Hrepresented by a word won {t, u, a}acts by the composition of the actions of the letters of w, beginning with the right-most. (The reader can check that the defining relations act trivially and so this action is well-defined.) The actions of tand uare to move the lamplighter one unit in the t- and u-directions, respectively. When (q, r) is the location of the lamplighter the action of ais to toggle the (q+r)-st lamp between on and off. In other words, atoggles the lamp running through the lamplighter’s position. We define I:H→→ Pfin(Z) by, given g∈H, setting I(g) to be the set of lamps illuminated after ghas acted on (∅,0), and we see that L(g) is then the location of the lamplighter. * t u Figure 1. Diagonal strip-lights in the lamp-lighting model for H. Of the lamps shown, numbers −7,−5,−4,−3,−1,1,3,5,6 (those with white stripes) are illuminated, and the lamplighter is at (−2,3). Checking that the action is transitive is straightforward and is left to the reader. To show the action is faithful we suppose g∈Hsatisfies g(∅,0) = (∅,0) and we check that g= 1 in H. Let wbe a word representing g. Reading wfrom right to left determines a path followed by the lamplighter THE UNBOUNDED DEAD-END DEPTH PROPERTY 5 in the grid, starting and finishing at 0and in the course of which lamps are toggled between on and off. The relation at=auimplies that a=aut−1 and a=atu−1. These relations can be used to alter wto another word w0 that also represents gin Hand that determines a path in the grid in the course of which lamps are only toggled on and off when the lamplighter is on the t-axis. (For example, if wis uatu−1at−1then w0can be taken to be uu−1tat−1utu−1at−1.) The relation [t, u] = 1 together with free reduction can then be used to alter w0to another word w00 that represents gand that determines a path in which the lamplighter does not leave the t-axis. (In our example, this would give us w00 =ta2t−1.) Identifying tand udefines a retraction of Honto the lamplighter group, under which gis mapped to an element also represented by w00. So g= 1 in Hbecause the action of the lamplighter group Z2oZin Cannon’s model is faithful. 3. Proof of Theorem 3 The following proposition establishes that depth is unbounded on (H, C). For, suppose we take gn∈Hwith I(gn) = {−n, n}and L(gn) = 0. Then dC(1, gn) = 4nand, with respect to C, the distance from gnto the complement of the radius 4nclosed ball about 1 is at least n+ 1 since the lamplighter has either to toggle a light outside {−n,...,n}or to end up outside {−n,...,n}and so in either case must travel outside Dn. Proposition 4. Define Dn:= (q, r)∈Z2| |q|+|r| ≤ n. If g∈Hsatisfies L(g)∈Dnand I(g)⊆ {−n,...,n}then dC(1, g)≤4n. If, in addition, L(g) = 0and {−n, n} ⊆ I(g), then dC(1, g) = 4n. Proof. The salient feature of Cis that, when the lamplighter moves in the grid from a vertex v1to an adjacent vertex v2, one or both of the lights at v1and v2can be toggled between on and off with no additional cost to word length. So, for g∈Hr{a}, we find dC(1, g) is the length of the shortest path in the grid that starts at (0,0), visits all of the lights that have to be illuminated, and finishes at L(g). Assume g∈Hr{a}with (q, r) := L(g)∈Dnand I(g)⊆ {−n, . . . , n}. Define v1:= n+q−r 2,n−q+r 2, v2:= −n+q−r 2,−n−q+r 2, the points of intersection of the line x−y=q−rwith the lines x+y=n and x+y=−n, respectively. Either both v1and v2are in Z2, or both are in (1/2+Z)2. In the latter case redefine v1and v2by adding (1/2,−1/2) to both. Then (in either case) there is a grid path from v1to v2of length 2n 6 TIM R. RILEY AND ANDREW D. WARSHALL that passes through (q, r). Assume (q, r) is closer to v1than v2along this path; otherwise interchanging v1and v2in the following gives the required result. There are grid paths of length nfrom 0to v2, of length 2nfrom v2to v1, and of length at most nfrom v1to (q, r). Concatenating gives a path of length at most 4nin the course of which every light in {−n, . . . , n} is visited. So dC(1, g)≤4n. If, in addition, L(g) = 0and {−n, n} ⊆ I(g) then the lamplighter must visit lamp −nand then lamp n, or vice versa, and then return to 0. Grid paths of length n, 2nand n, respectively, are both necessary and sufficient for these three components of the journey. So dC(1, g) = 4nas required.  We will show that depth is identically 1 in (H, D) except at a. The depth at ais 2 because all group elements at distance 1 from it are either other elements of Dor the identity, while these other elements of Dthemselves have depth 1, as we will show. This will prove Theorem 3. We begin by defining a D-path in R2to be a concatenation of straight-line segments each of which connects a point in Z2to a point in (1/2 + Z)2, has length √2/2, and (so) has slope ±1. Define the length of a D-path to be the number of such constituent line segments. The following lemma is straightforward. Lemma 5. For (q, r)∈Z2the length of the shortest D-path from 0to (q, r)is |q+r|+|q−r|, that is the `1-norm of (q, r)with respect to the basis {(1/2,1/2),(−1/2,1/2)}. Our next lemma relates D-paths and the word metric dD. Lemma 6. For g∈Hr{a}, the distance dD(1, g)is half the length of the shortest D-path from (0,0) to L(g)that visits all the lamps in I(g). Proof. Let µbe a minimal length D-path from 0to (q, r) that, en route, toggles some of the lamps it visits in such a way as to illuminate the pattern I(g). Choose some of the vertices at the start or end of segments in µto be distinguished, with the selection being made in such a way that toggling all the lamps incident with distinguished vertices lights the pattern I(g). The lamplighter in the grid model for Hcannot follow µbecause of being constrained to move between points in Z2. However, µhas even length as the points at the ends of segments are alternately in Z2and (1/2 + Z)2. Consider µtwo segments at a time. A pair of adjacent segments combine to give a path between two Z2points (that may include some of the distinguished vertices). Well, a generator in Dr{a}acts to move the lamplighter between two Z2points and possibly toggle some lamps between the initial and the final location of the lamplighter. The construction of Dis such that elements of D±1ra±1are in correspondence with certain pairs of THE UNBOUNDED DEAD-END DEPTH PROPERTY 7 adjacent length-√2/2 diagonal line-segments along which some vertices are distinguished. There are 16 ways to construct a path of two joined diagonal segments, 10 of which are depicted in Figure 2; the remaining 6 are the inverses of the paths in the first four rows. Corresponding elements of D are shown in the figure, and the locations of the letters adictate where the incident lamp is to be toggled. The two cases in row seven cannot occur in µbecause µis of minimal length. For the same reason, the cases in rows five and six can only occur when the lamp incident with the midpoint of the square is to be toggled. Only two words occur in the fourth row, one with an aand one without, as the corresponding D-path is incident with only one lamp. So we can produce a word won the alphabet D±1such that the length of wis half that of µ, that, read right to left, describes a grid path from 0 to (q, r) and along which lamps are toggled to illuminate the configuration I(g). In the same manner, given a geodesic word won D±1representing some g∈Hr{a}, we can produce a D-path of length twice that of wfrom 0to (q, r) that, en route, switches on the lamps I(g). (There will be no generators ain was they could be absorbed into an adjacent generator, reducing word length.)  (3) tu, atu, tau, tua, atau, atua, taua, ataua (1) t, ta, at, ata (2) u, ua, au, aua , , , (4) ut−1, aut−1 (6) tat−1, atat−1 (5) t−1at, at−1at Figure 2. Generators in Dand the corresponding D-paths. The two lemmas combine to give: 8 TIM R. RILEY AND ANDREW D. WARSHALL Proposition 7. Suppose g∈Hr{a}. Let (q, r) := L(g). Then dD(1, g)is half the length of the shortest D-path that starts at (0,0), travels along the line x=yvisiting all lamps in I(g), then arrives at ((q+r)/2,(q+r)/2) (the point of intersection of the lines x=yand x+y=q+r)and finally travels along x+y=q+rto (q, r). So, given g∈Hr{a}, either dD(1,(ut−1)g) = dD(1, g) + 1 or dD(1,(tu−1)g) = dD(1, g) + 1. This completes the proof of Theorem 3. 4. A lamplighter model for K In Section 2 we gave a lamplighter model for Hthat amounted to a left action on Pfin(Z)×Z2. Similarly, Khas a lamplighter model: a left action on Pfin(Z)×Z3that will be given by two maps, I:K→→ Pfin(Z) and L:K→→ Z3, such that g(∅,0) = (I(g),L(g)). This action will be faithful and transitive, or, equivalently, I ×L will be bijective. Define L:K→→ hs, t, ui∼ =Z3to be the retraction given by killing a. This defines the location L(g) = (p, q, r) of the lamplighter among the Z3- lattice points of R3after the action of g∈Kon (∅,0), where p,qand rare the s-, t- and u-coordinates. The definition of I:K→→ Pfin(Z) involves the group Gpresented by ha, s, t |a2,[a, at],[s, t], a−saati and related to Kas discussed in Section 1. The following lamplighter model for Gwas given in [4]. Envisage a Z-indexed set of lamps that are arranged along the q-axis in the p, q-plane in which the p-axis is skewed so as to make an angle π/3 with the q-axis — see Figure 3 (reproduced from [4]). Regard an element of Pfin(Z)×Z2as a pair consisting of a finite set of lamps (illuminated lamps) together with a lattice point (lamplighter position). Define a (faithful, transitive) left action of Gon Pfin(Z)×Z2by letting sand tmove the lamplighter a distance 1 in the p- and q-directions, respectively, and by letting a“press a button” at the location of the lamplighter that toggles the lights at the locations of the 1s in a modulo 2 Pascal’s triangle, suspended from (or growing up from, when below the q-axis) the location of the lamplighter, as illustrated in Figure 3. Identifying tand udefines a retraction Φ : K→→ G. For g∈K, define I(g) to be the Pfin(Z) component of the image of (∅,0) under the action of Φ(g). The map I ×L :K→ Pfin(Z)×Z3is easily checked to be surjective. To show it is injective, suppose g∈Ksatisfies (I ×L)(g) = (∅,0); the action defined above of Gon Pfin(Z)×Z2is faithful [4] and so g∈Ker Φ. But Ker Φ is the normal closure of htu−1iin K. Since tu−1is in the center of K, it generates its own normal closure, and so KerL∩Ker Φ = {1}. Hence g= 1. THE UNBOUNDED DEAD-END DEPTH PROPERTY 9 * * 1 1 1 1 1 1111 1 1 1111 0 000 00 * 0 0 0 1 1 1 1 ppp q qq Figure 3. An example of the action of a. The left diagram shows g(∅,0) and the right diagram shows ag(∅,0), where g=s6at−2at−1at−3at−1at−1at4. Along the taxis, open circles indicate illuminated lamps and filled-in circles indicate lamps which are off. 16 TIM R. RILEY AND ANDREW D. WARSHALL we exchange x0and x1– in other words we push ξacross the parallelogram with x0as its lower side and x1as its left side, replacing those two sides with the right and top. We leave it for the reader to check that in every case V can be altered, selecting new vertices on the other side of the parallelogram, illuminating the same bulbs – perhaps the easiest way to do this is push ξ across the parallelogram one unit-sided rhombus at a time, working from bottom to top, checking that at each stage vertices can be moved across in a way that maintains the same configuration of illuminated lights. Suppose next that ξ0and ξ2are not both in the plane q=r. The only way this can happen is for ξ2to be the first segment of the portion of µ outside the plane q=r. In this case interchange ξ1and ξ2, translating any vertices of Von ξ1on the way. Since motion perpendicular to the plane q=rdoes not affect which lights are toggled by the buttons, the new path will represent the same group element. Repeating this process eventually renders (µ, V) word-like and it changes neither Dnor V. If the interchange in the paragraph above was implemented then the vertical path moved is µ3, the diagonal segment that now precedes it is µ2, and the remaining initial and terminal portions of µare µ1and µ4. Otherwise, µ2and µ3are taken to be of zero-length and µ1is the maximal length initial path of µlying in the plane q=rand µ4is the remainder. Let wbe the word now obtained from (µ, V). The length of wis V+D/2, which is at most the length of w0. So wis a geodesic. Moreover, all vertices of Vare on µ1,µ2and µ3, as required.  We can now conclude our proof. Suppose g∈Kr{a}. Consider g0∈K with I(g0) = I(g) and L(g0) located so that the line through L(g) and L(g0) is perpendicular to the plane q=rand L(g0) is a distance √2 further from that plane than is L(g). Then g0is at distance greater than 1/√2 from the plane q=rand so, by Lemma 14, some geodesic word w0for g0comes from a decorated B-path (µ0,V0) whose last two segments form the diagonal from L(g) to L(g0), and vertices of V0lie beyond L(g). So deleting these last two segments gives a decorated B-path (µ, V0) yielding a word wrepresenting g, which is a subword of w0by construction. Since dB(g, g0) = 1, our proof is complete. 6. Dead-end depth in Z In this section we prove Proposition 2. Writing r∈ {0,1,...,n(n+ 1) −1}as an +bfor some 0 ≤a≤nand 0≤b < n, we have r= (a−b)n+b(n+ 1) = (a−b+n+ 1)n+ (b−n)(n+ 1). THE UNBOUNDED DEAD-END DEPTH PROPERTY 17 Thus if ddenotes the word metric on (Z,{n, n + 1}) then d(0, r)≤min {|a−b|+|b|,|a−b+n+ 1|+|b−n|}, which is at most nbecause if a+n≥2bthen |a−b|+|b| ≤ nand if a+n < 2bthen |a−b+n+ 1|+|b−n|= (a−b+n+1)+(n−b) = a−2b+2n+1 < n+1, and so |a−b+n+ 1|+|b−n| ≤ n. Thus max {d(0, r)|r= 0,1,...,n(n+ 1) −1} ≤ n. It is enough to show that this maximum is attained at a positive integer < n+1, because then any point of Zfurther from 0 will be at least n(n+1)−n= n2away in the standard metric on Z, and hence at least n2/(n+ 1) > n −1 away in d. If nis even, we set n= 2m; the maximum will be attained at msince if m=a(2m) + b(2m+ 1) then m=b(mod 2m), m =−a(mod 2m+ 1) and so |a|,|b| ≥ m. If nis odd, we set n= 2m−1; the maximum will again be attained at msince if m=a(2m) + b(2m−1) we have m=−b(mod 2m), m =a(mod 2m−1), and so |b| ≥ mand |a| ≥ m−1. In both cases |a|+|b| ≥ nand m < n + 1. This completes the proof. We remark that Proposition 2 also holds for groups Gsuch that G/N ∼ =Z for some finite NEGand for groups Z o Hwhere His finitely generated. Whether it holds for other groups (even a rank 2 free group) remains open. References [1] M. Bestvina. Questions in geometric group theory. http://www.math.utah.edu/∼bestvina/. [2] O. V. Bogopol0ski˘ı. Infinite commensurable hyperbolic groups are bi-Lipschitz equivalent. Algebra i Logika, 36(3):259–272, 357, 1997. [3] C.Champetier. Propri´et´es statistiques des groups de pr´esentation finie. Adv. in Math., 116:197–262, 1995. [4] S. Cleary and T. R. Riley. A finitely presented group with unbounded dead end depth. To appear in Proc. AMS, arXiv:math.GR/0406443, 2004. [5] S. Cleary and J. Taback. Dead end words in lamplighter groups and other wreath products. Quart. J. Math. Oxford, to appear, 2003. [6] S. Cleary and J. Taback. Metric properties of the lamplighter group as an automata group. To appear in Contemporary Mathematics, arXiv:math.GR/0312331, 2003. [7] P. de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000. 18 TIM R. RILEY AND ANDREW D. WARSHALL [8] S. B. Fordham. Minimal length elements in Thompson’s group F. PhD thesis, Brigham Young University, 1995. [9] R. Lyons, R. Pemantle, and Y. Peres. Random walks on the lamplighter group. Ann. Probab., 24(4):1993–2006, 1996. T.R.Riley, Mathematics Department, 310 Malott Hall, Cornell University, Ithaca, NY 14853-4201, USA [email protected] A.D.Warshall, Mathematics Department, 10 Hillhouse Avenue, P.O. Box 208283, New Haven, CT 06520-8283, USA [email protected]