Word length in symmetrized presentations of Thompson’s group F

Thompson's groups F, T and Z were introduced by Richard Thompson in the 1960's in connection with questions in logic. They have since found applications in many areas of mathematics including algebra, logic and topology, and their metric properties with respect to standard generating sets...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автори:	Horak, M., Johnson, A., Stonesifer, A.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут прикладної математики і механіки НАН України 2012
Назва видання:	Algebra and Discrete Mathematics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/152238
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Word length in symmetrized presentations of Thompson’s group F / M. Horak, A. Johnson, A. Stonesifer // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 2. — С. 185–216. — Бібліогр.: 12 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-152238
record_format	dspace
spelling	irk-123456789-1522382019-06-10T01:26:19Z Word length in symmetrized presentations of Thompson’s group F Horak, M. Johnson, A. Stonesifer, A. Thompson's groups F, T and Z were introduced by Richard Thompson in the 1960's in connection with questions in logic. They have since found applications in many areas of mathematics including algebra, logic and topology, and their metric properties with respect to standard generating sets have been studied heavily. In this paper, we introduce a new family of generating sets for F, which we denote as Zn, establish a formula for the word metric with respect to Z₁ and prove that F has dead ends of depth at least 2 with respect to Z₁. 2012 Article Word length in symmetrized presentations of Thompson’s group F / M. Horak, A. Johnson, A. Stonesifer // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 2. — С. 185–216. — Бібліогр.: 12 назв. — англ. 1726-3255 2010 MSC:20F65. http://dspace.nbuv.gov.ua/handle/123456789/152238 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	Thompson's groups F, T and Z were introduced by Richard Thompson in the 1960's in connection with questions in logic. They have since found applications in many areas of mathematics including algebra, logic and topology, and their metric properties with respect to standard generating sets have been studied heavily. In this paper, we introduce a new family of generating sets for F, which we denote as Zn, establish a formula for the word metric with respect to Z₁ and prove that F has dead ends of depth at least 2 with respect to Z₁.
format	Article
author	Horak, M. Johnson, A. Stonesifer, A.
spellingShingle	Horak, M. Johnson, A. Stonesifer, A. Word length in symmetrized presentations of Thompson’s group F Algebra and Discrete Mathematics
author_facet	Horak, M. Johnson, A. Stonesifer, A.
author_sort	Horak, M.
title	Word length in symmetrized presentations of Thompson’s group F
title_short	Word length in symmetrized presentations of Thompson’s group F
title_full	Word length in symmetrized presentations of Thompson’s group F
title_fullStr	Word length in symmetrized presentations of Thompson’s group F
title_full_unstemmed	Word length in symmetrized presentations of Thompson’s group F
title_sort	word length in symmetrized presentations of thompson’s group f
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2012
url	http://dspace.nbuv.gov.ua/handle/123456789/152238
citation_txt	Word length in symmetrized presentations of Thompson’s group F / M. Horak, A. Johnson, A. Stonesifer // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 2. — С. 185–216. — Бібліогр.: 12 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT horakm wordlengthinsymmetrizedpresentationsofthompsonsgroupf AT johnsona wordlengthinsymmetrizedpresentationsofthompsonsgroupf AT stonesifera wordlengthinsymmetrizedpresentationsofthompsonsgroupf
first_indexed	2025-07-13T02:37:30Z
last_indexed	2025-07-13T02:37:30Z
_version_	1837497588944732160
fulltext	Jo ur na l A lg eb ra D is cr et e M at h.Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 14 (2012). Number 2. pp. 185 – 216 c© Journal “Algebra and Discrete Mathematics” Word length in symmetrized presentations of Thompson’s group F 1 Matthew Horak, Alexis Johnson and Amelia Stonesifer Communicated by V. Nekrashevych Abstract. Thompson’s groups F, T and Z were introduced by Richard Thompson in the 1960’s in connection with questions in logic. They have since found applications in many areas of mathemat- ics including algebra, logic and topology, and their metric properties with respect to standard generating sets have been studied heavily. In this paper, we introduce a new family of generating sets for F , which we denote as Zn, establish a formula for the word metric with respect to Z1 and prove that F has dead ends of depth at least 2 with respect to Z1. 1. Introduction A common goal in geometric group theory is to determine which properties a given group possesses with respect to some, none or all finite generating sets. For Thompson’s Group F , few results like this exist, especially for its metric properties such as dead end depth and almost convexity. This is mostly due to the fact that the only generating sets for which a method to calculate the word metric is known are the so-called consecutive generating sets, Xn = {x0, x1, . . . , xn}. With respect to every Xn, F is known to contain dead ends [10], leading to the question of whether or not F has dead ends with respect to every finite generating set. In this paper, we introduce a new family of generating sets, Zn, establish 1This work was supported by NSF REU grant DMS 0453421. 2010 MSC: 20F65. Key words and phrases: Thompson’s group F, dead ends, diagram group. Jo ur na l A lg eb ra D is cr et e M at h. 186 Symmetrized presentations of F a formula for the word metric with respect to Z1, and use our formula to show that F has dead end elements of depth at least 2 with respect to Z1. This result extends the class of generating sets with respect to which F is known to contain dead ends. Thompson’s group F can be viewed as a group of piecewise linear homeomorphisms from the unit interval to itself. In this definition, the generating sets Xn seem slightly asymmetric because each generator xi is the identity on the subinterval [0, 2i −1 2i ]. The generating sets Zn that we introduce “symmetrize” the standard generating sets by adding elements yi that are the identity on intervals [ 1 2i , 1]. 1.1. Word length and dead ends For a finitely generated group G and fixed finite generating set S, the word length, lS(g), of g with respect to S is defined to be 0 if g is the identity and to be the minimal length of an expression in elements of S ∪ S−1 that is equal to g if g is not the identity. Word length depends on the generating set, but if there is a fixed generating set under discussion, we often omit the reference to the generating set and write l(g) for lS(g). Geometrically, l(g) can be viewed as the distance from the identity to g in the Cayley graph of G with respect to S. For a group G and fixed generating set S, the element g ∈ G is called a dead end (with respect to S) if l(gα) ≤ l(g) for all α ∈ S ∪ S−1. Geometrically, no infinite geodesic ray originating at the identity in the Cayley graph can pass through g. More generally, if G is an infinite group, the dead end depth of g with respect to S is defined as, δ(g) = min{l(α) \| l(gα) > l(g)}. Since G is an infinite group, δ(g) exists for every g ∈ G. Geometrically, δ(g) is the distance from g to the complement of the ball of radius l(g) centered at the identity in the Cayley graph of G with respect to S. Note that the element g is a dead end if its dead end depth is at least 2. For a finitely generated infinite group G, the dead end depth of G is, δ(G) = max{δ(g) \| g ∈ G} if the maximum exists and infinity otherwise. Geometrically, δ(G) is the least integer N such for any g ∈ G there is guaranteed to exist a path of length at most N from g to the complement of the ball of radius l(g) centered at the identity. We note that these definitions are consistent Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 187 with the definition of dead end depth in [7], but is inconsistent with the convention in [10] in which the dead end depth is one less than this dead end depth. Among other places, dead ends have found application in the proof in [12] demonstrating a random walk that is biased towards the identity on the lamplighter group but that escapes from the identity faster than a simple random walk. Dead ends also played a role in Bogopol′skĭı’s result that infinite commensurable hyperbolic groups are bi-Lipschitz equivalent [4]. 1.2. Thompson’s group F We now define Thompson’s group F and survey some background results about the metric structure of F . We refer to [6] for a more detailed discussion of the group F . Definition 1.1. Thompson’s group F is the set of piecewise linear orien- tation preserving homeomorphisms from [0,1] to [0,1] with the following properties: 1) Each f ∈ F has only finitely many points of non-differentiability, each of which occurs at a dyadic rational number. 2) The slope of f at every point of differentiability is a power of 2. The binary operation is composition of functions. There are two standard presentations for Thompson’s group F : the infinite presentation, F = 〈xk, k ≥ 0 \| x−1 i xjxi = xj+1 if i < j〉 (1) and the finite presentation, 〈x0, x1 \| [x0x−1 1 , x−1 0 x1x0], [x0x−1 1 , x−2 0 x1x2 0]〉. (2) The generating sets Xn := {x0, x1, . . . xn} are commonly referred to as the standard or standard consecutive generating sets. As piecewise linear homeomorphism of the unit interval, the elements x0 and x1 are given by, x0(t) =        1 2 t, 0 ≤ t ≤ 1 2 t − 1 4 , 1 2 ≤ t ≤ 3 4 2t − 1, 3 4 ≤ t ≤ 1 x1(t) =              t, 0 ≤ t ≤ 1 2 1 2 t + 1 4 , 1 2 ≤ t ≤ 3 4 t − 1 8 , 3 4 ≤ t ≤ 7 8 2t − 1, 7 8 ≤ t ≤ 1. Jo ur na l A lg eb ra D is cr et e M at h. 188 Symmetrized presentations of F Figure 1. Graphs of x0 (left) and x1 (right) The graphs of x0 and x1, are shown in Figure 1. Note x1 is the identity on [0, 1 2 ] and the graph of x1 contains a “copy” of the graph of x0 scaled down by a factor of 1 2 and shifted into the upper right corner. The elements xi are constructed similarly, by defining xi to be the identity on the interval [0, 2i −1 2i ] and then to act as a scaled version of x0 on the interval [2i −1 2i , 1]. This is depicted schematically in Figure 2 for the elements x1, x2 and x3. Figure 2. Progression of elements xi 1.3. Combinatorial models for F A common strategy for studying the geometric and combinatorial properties of F is to find a combinatorial model whose structure faithfully represents the algebraic structure of F but whose elements are easier to manipulate and “compose” or “multiply”. This often takes the form of a set of combinatorial objects that are in 1-to-1 correspondence with the elements of F and a description of how the combinatorial representative Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 189 for an element changes when multiplied by a generator or another element of F . The most common combinatorial model for F is that of tree pair diagrams, for which the reader should consult [6] for a full description. Other models include forest diagrams [2], diagram groups [9] and pipe diagrams [5]. By viewing elements of F geometrically in these ways, researchers have been able to prove that F is not minimally almost convex with respect to any subset of Xn that contains x1 [3, 11], has dead end depth 3 with respect to X1 [7], has dead end depth bounded by n 2 and 4n − 2 with respect to Xn for n ≥ 3 [10] and has Hilbert space compression 1 2 [1]. Except for the Hilbert space compression result, all of the above models and results apply to the standard generating sets, Xn. In this paper, we define and use another model, which we call wave diagrams that are better suited to our more symmetrical generating sets, Zn, which we define in the next subsection. 1.4. Generating set Zn For i ≥ 1, let yi be the element of Thompson’s group F given by, yi(t) =          2t, 0 ≤ t ≤ 1 2i+2 t + 1 2i+2 , 1 2i+2 ≤ t ≤ 1 2i+1 t 2 + 1 2i+1 , 1 2i+1 ≤ t ≤ 1 2i t, 1 2i ≤ t ≤ 1. Informally, the function yi is the identity on the interval, [ 1 2i , 1] and acts as a scaled down version of x−1 0 on the interval [0, 1 2i ]. The graphs of y1, y2 and y3 are depicted schematically in Figure 3 Figure 3. Progression of elements yi Jo ur na l A lg eb ra D is cr et e M at h. 190 Symmetrized presentations of F Definition 1.2. The subset Zn ⊂ F is given by Zn := {x0, x1, y1, x2, y2, ..., xn, yn}. Since the generating set Xn is contained in Zn, it is clear that Zn is a generating set for F . For the remainder of the paper, we focus on determining a formula for calculating the word metric with respect to the generating set Z1 and on using this formula to show that F has dead end depth at least 2 with respect to Z1. We begin by developing a combinatorial model for elements of F for which it is easy to analyze the effect of multiplication by a generator in Zn. 2. Wave diagrams Definition 2.1. A wave diagram or simply a diagram is a planar graph, D, together with a smooth embedding of D in the plane satisfying the following. • D contains infinitely many vertices, all of which lie on a distinguished bi-infinite path in G that is embedded in the x-axis in such a way that the vertices have no accumulation point. This path is called the central line and its edges are called central edges. • All other edges are embedded either above the x-axis, where they are defined as upper edges, or below the x-axis, where they are defined as lower edges. • There are only finitely many upper and lower edges. • All finite regions have three edges. • There is a vertex labeled 1 2 on the top. This vertex cannot be between the two endpoints of an upper edge. There also exists a vertex labeled 1 2 on the bottom that cannot be between two endpoints of a lower edge. The same vertex may be labeled 1 2 on both top and bottom. We will be concerned mainly with the finite portion of a diagram that contains all of the non central edges. This portion of a diagram is referred to as the essential portion. Throughout, our convention will be to denote the vertices along the central line by w0, w1, . . . , wn, starting with w0 as the left-most vertex incident to a non-central edge and ending with wn, the the right-most vertex incident to a non-central edge. In many arguments, we must distinguish the “left” and “right” endpoints of an Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 191 w0 w1 w2 w3 w4 w5 w6 Figure 4. The essential portion of a diagram edge. If e is an edge incident to vertices wi and wj with i < j, then we use e− to refer to wi and e+ to refer to wj . Figure 4 is an example of the essential portion of a diagram shown with the top and bottom 1 2 labels omitted. Throughout this paper, we follow the convention of drawing only the essential portion of a diagram unless the top or bottom 1 2 lies outside of the essential portion, in which case, we draw enough to include both 1 2 labels. In order for diagrams to faithfully model elements of F , we must omit diagrams with dipoles, defined below, which completely characterize the extent to which two diagrams representing the same element can differ. Definition 2.2. A dipole is a subgraph of a diagram D that consists of three vertices adjacent along the central line, wi, wi+1, wi+2, an upper edge u, a lower edge l such that u− = l− = wi, u+ = l+ = w1+2, together with the two central edges connecting wi, wi+1 and wi+2. A dipole is shown in Figure 5. Figure 5. A dipole Definition 2.3. A diagram D is called reduced if it contains no subgraph that is a dipole. For the remainder of the paper, we deal with only reduced diagrams, but for convenience, we will usually omit the word “reduced”. Therefore, all diagrams in the following are assumed to be reduced diagrams unless otherwise stated. Jo ur na l A lg eb ra D is cr et e M at h. 192 Symmetrized presentations of F 2.1. Labeling and reading a wave diagram In this section, we describe a 1-to-1 correspondence between (reduced wave) diagrams and elements of Thompson’s group F . The first step is to use the upper and lower edges and the 1 2 labels to label the remaining vertices with “upper” and “lower” labels. Geometrically, we think of “upper” labels as being written above the x-axis and “lower” labels below the x-axis. Diagrams are labeled in such a way that every vertex receives an upper and a lower label. We must first identify the exposed vertices. Definition 2.4. Vertex wi is exposed from the bottom if there exists no lower edge e such that e− = wa and e+ = wb, with a < i < b. Vertex wi is exposed from the top if there does not exist an upper, non-central edge, e, such that e− = wa and e+ = wb, where a < i < b. Now we may assign top labels. First work to the right from the vertex labeled 1 2 on top, labeling the exposed upper vertices in order: “3 4 , 7 8 , 15 16 ,. . . ". Next, work to the left of the vertex labeled 1 2 on top, label the exposed upper vertices “1 4 , 1 8 , 1 16 , . . . ". To assign upper labels to vertices without an upper label, use the rule that if e is an upper edge in which e− has upper label α and e+ has upper label β then the non-exposed vertex w contained in the region bounded by e has label α+β 2 . Vertices are assigned lower labels by following the same procedure with lower edges starting with the vertex labeled 1 2 on the bottom. Results of this process are demonstrated in figure 6. 1 8 15 32 3 16 7 32 1 4 1 2 9 16 5 8 3 4 1 8 1 4 3 8 1 2 5 8 11 16 3 4 7 8 15 16 Figure 6. Example of labeling a Wave Diagram Notice that the dots along both ends represent the infinite vertices on the left and right of the non-central edges. In future diagrams we will ex- clude these ellipsis for simplicity. Even though there is no vertex infinitely far left or right, we sometimes think of an “ideal vertex" lying infinitely far left and one infinitely far to right labeled “0" and “1" respectively. Two diagrams D1 and D2 are isomorphic if there exists an orientation preserving homeomorphism from R 2 to itself that restricts to a label- Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 193 preserving graph isomorphism between D1 and D2 that takes upper edges to upper edges, lower edges to lower edges, and central edges to central edges. As described below, the set of isomorphism classes of reduced diagrams is in in one-to-one correspondence with F . Therefore, it is convenient to abuse terminology and refer to the “diagram D” when one really means the “isomorphism class of diagram D”. For the remainder of this paper, we adopt to this convention together with the convention that all diagrams under consideration are reduced. Thus the term “diagram” will always mean “isomorphism class of reduced diagram”. Moreover, if D1 and D2 are isomorphic diagrams, then there is a unique diagram isomorphism between D1 and D2, thus one may unambiguously speak of an edge in an isomorphism class of diagrams. Each isomorphism class of diagrams corresponds to a unique element of F , as follows. The top and bottom labels on vertices along the central edge of a wave diagram D determine two subdivisions of the interval [0, 1]. The piecewise linear homeomorphism f corresponding to D maps the subinterval from the bottom labeling of the endpoints of any edge e linearly to the subinterval for the top labeling of the endpoints of the same edge e. Since all of the subintervals have length which is a power of 2 and since there are only finitely many non-central edges in D, f is a piecewise linear homeomorphism of I to itself with only finitely many points of non-differentiability and slopes that are powers of 2 elsewhere. Therefore, f is an element of D. This correspondence is seen to be a bijection between the set of isomorphism classes of reduced diagrams and F . For g ∈ F , we use the notation D(g) to denote the diagram corresponding to g and for diagram D, we use fD to denote the element of F corresponding to D. The most basic of these diagrams, consisting of at most one edge, are the elements of the generating set Zn as in Figure 7. 2.2. Multiplication of wave diagrams Though it is not necessary for what follows, we note that one can define a “composition" of these diagrams so that composition of diagrams corresponds exactly to multiplication of the associated group elements. This is done in a way similar to composition in ordinary diagram groups as defined in [9] by identifying the bottom path of D(f) with the top path of D(g) and performing the appropriate “reduction" to arrive at the diagram for D(fg). Jo ur na l A lg eb ra D is cr et e M at h. 194 Symmetrized presentations of F 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 x0 x1 y1 y −1 1 x −1 1 x −1 0 xn yn ︷︸︸︷︷︸︸︷ n vertices n vertices Figure 7. Elements of Zn While it is not necessary to know how to compose two general diagrams, it is important to establish the rules for constructing D(fxi) and D(fyi) from D(f). Before doing so, we classify several different types of edges. Definition 2.5. Let f ∈ F and let g and h be edges in D(f). Let g− = wi, g+ = wj , h− = wk, and h+ = wm. Edge g is said to be below edge h if and only if one of the following holds: 1) both g and h are lower edges, i ≤ k and j ≥ m as shown in Figure 8; 2) g is a lower edge, h is an upper edge and one of the following is true, as shown in Figure 9: (a) k ≤ i < m (b) k < j ≤ m (c) i ≤ k and j ≥ m; or 3) both g and h are upper edges, i ≥ k and j ≤ m, as shown in Figure 10. Conversely, edge h is said to be above edge g if edge if g is below h. We note that the relation ≺, defined on the set of edges of a diagram by g ≺ h if g is below h, is transitive and antisymmetric, so it defines a partial relation on the set of edges of a diagram Definition 2.6. An edge, e in D(f), is bottom-most if there exists no edge below e. Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 195 i g h k j = m j g h mi = k Figure 8. Examples of Definition 2.5 (1) i j g h k g h m l i = k i g h k m l Figure 9. Examples of Definition 2.5 (2) j g h m i = k Figure 10. Examples of Definition 2.5 (3) Definition 2.7. An edge e is an exposed upper edge if e is an upper edge and there does not exist any non-central edges below e. Edge g in Figure 10 is an exposed upper edge. We now describe the effect on a diagram that multiplication by a generator in F has. Let f belong to F and and let wi be the vertex of D(f) labeled 1 2 on the bottom. For generator α ∈ Z1 ∪ Z−1 1 , construct D(fα) from D(f) as follows. 1) If α = x0 then move the bottom 1 2 label left of wi to the nearest vertex exposed from the bottom. 2) If α = x−1 0 then move the bottom 1 2 label right of wi to the nearest vertex exposed from the bottom. 3) If α = x1, proceed as follows. Jo ur na l A lg eb ra D is cr et e M at h. 196 Symmetrized presentations of F • If there exists at least one lower edge to the right of wi, delete the bottom-most of these edges. • If there does not exist any lower edges to the right of wi, add a bottom-most upper edge that connects wi and wi+1. Then, add a vertex subdividing the old central edge from wi to wi+1 into two new central edges, as seen in Figure 11. Figure 11. Diagram D(f) (left) and D(fα) (right) 4) If α = x−1 1 , proceed as follows. • If there exists an exposed upper edge to the right of wi, delete this edge and the vertex wi+1. Connect wi and wi+2 with a new central edge, as in Figure 12. Figure 12. Diagram D(f) (left) and D(fα) (right) • If there does not exist an exposed upper edge to the right of wi, add a bottom-most lower edge connecting wi to the second nearest exposed vertex to the right of wi. 5) If α = y1, then follow Case (3), but consider edges and vertices to the left of wi. 6) If α = y−1 1 then follow Case (4), but consider edges and vertices to the left of wi. 3. Formula for length with respect to Z1 Before presenting our length formula, we establish some definitions. For our purposes, we explicitly indicate both the vertices and edges that the path traverses. We use vi to represent the vertices and qi to represent the edges in the path. Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 197 Definition 3.1. Let N be the set of non-central edges of the diagram D(f) and let λ = v0q1v1q2v2 · · · qlvl be a path in D(f). The function rλ : N → N ∪ {∞} is a reaching function for λ if the following hold. 1) If rλ(e) = 0 then (a) Edge e is incident to v0, (b) Every non-central edge below e is incident to v0, (c) No qj for j > 0 is a central edge below e and (d) Edge e does not appear as qj for any j > 0. 2) If 0 < rλ(e) < ∞ then (a) Edge e is incident to vrλ(e), (b) If h is a non-central edge below e then either h is incident to vrλ(e) or rλ(h) < rλ(e), (c) No qj for j > rλ(e) is a central edge below e and (d) Edge e does not appear as qj for any j > rλ(e). Frequently we have a path λ together with a fixed reaching function rλ for λ. In this case, we say that λ reaches non-central edge e at vertex vi if rλ(e) = i. We note that this use of the term “reach” depends on the particular reaching function under consideration, so we use this convention only when there is only one such function under consideration. Sometimes, to emphasize rλ we say that λ reaches e with respect to rλ at vertex vi. Definition 3.2. Let f ∈ F . The path λ = v0q1v1q2v2 · · · qlvl is a legal path in D(f) if there is a reaching function rλ for λ such that the following three conditions hold. 1) The vertex v0 is labeled 1 2 on the bottom and vl is labeled 1 2 on top. 2) With respect to rλ, the path λ reaches every non-central edge in D(f). 3) For all 0 ≤ i ≤ l, if h is a non-central edge below qi then rλ(h) < i. When we refer to a legal path, we always implicitly assume that we have fixed a reaching function rλ that reaches every non-central edge in D(f). Thus, the term “legal path” refers to a legal path together with a fixed reaching function. The next two observations, which we use frequently in the proofs below follow quickly from the definition a legal path. Jo ur na l A lg eb ra D is cr et e M at h. 198 Symmetrized presentations of F Observation 3.3. Let e be a non-central edge in the legal path λ. No edge q that occurs in λ before the last occurrence of e in λ can be above e. Observation 3.3 follows from the fact that if e is below q, it must be reached at a vertex in the path occurring before q, and once an edge is reached by λ, it cannot occur again in λ. Observation 3.4. If e is a lower and bottom-most edge that is in the legal path λ and if q is reached at a vertex to the left (respectively right) of e− (respectively e+) then both endpoints of q lie to the left (respectively right) of e− (respectively e+). Observation 3.4 follows from the fact that if edge q has endpoints on opposite sides of one of the endpoints of e then either e is under q or q is under e, neither of which occurs by Observation 3.3 and the fact that e is a bottom-most edge. We have the following formula for determining the word length with respect to Z1 of the element f ∈ F . Theorem 3.5. For every f ∈ F , the word length of f with respect to the generating set Z1 = {x0, x1, y1} is given by the formula lZ1 (f) = E(f) + P (f) where E(f) is the number of non-central edges in D(f), and P (f) is the length of a minimal length legal path in D(f). In some of the following proofs, we define a new path λ′ that reorders the vertices and edges of an original path λ. Often, we use an interval notation to denote this path. To denote the subinterval of λ between vertices vi and vp, we use the notation, [vi, vp]. Now, when [vi, vp] appears in the notation for a new path λ′, every vertex and edge between vi and vp is to appear in λ′, preserving the order from λ. If a bracket is closed, include the corresponding vertex, and if the bracket is open, do not. Lemma 3.6. Let f ∈ F and let λ′ be a minimal length legal path in D(f). No bottom-most lower edge occurs more than twice in λ. Proof. Let λ′ = v0q1v1q2v2 · · · qnvn be a legal path of minimal length in D(f) with reaching function rλ′ . Suppose towards a contradiction that e is a bottom-most lower edge of D(f) such that e = qi = qj = qk with i < j < k. Without loss of generality, assume that and qi, Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 199 qj and qk are the first three times that e appears in λ′. Then λ′ = [v0, vi−1]e[vi, vj−1]e[vj , vk−1]e[vk, vn]. We claim that the shorter path, λ = [v0, vi−1](vj , vk−1]e[vi, vj−1)[vk, vn], is a legal path in f , which contradicts the minimality of λ′. To prove this claim, we construct a reaching function rλ that reaches every non-central edge in D(f). Rename the vertices and edges appearing in λ by λ = s0p1s1p2s2 · · · pn−2sn−2. Note that st = vt if 0 ≤ t ≤ i − 1, and st = vt−2 if t ≥ k − 1 since the paths λ and λ′ agree at their beginnings and endings. Additionally, the same set of vertices appear in λ and λ′ since vi−1 = vj = vk−1 and vi = vj−1 = vk. This is illustrated in Figure 13. Figure 13. Interval Location Let v be the leftmost vertex of D(f) that is incident to a non-central edge and number the vertices to the right of v in order along the central path as w0 = v, w1, w2, w3, · · · . Let a and b be such that λ′ traverse e at qi from wa to wb. Without loss of generality we may assume that b > a. Let h be a non-central edge of D(f). We define rλ as follows: 1) If rλ′(h) ≤ i − 1 then rλ(h) = rλ′(h). 2) If i ≤ rλ′(h) ≤ j − 1 then note that the third segment of λ (together with the vertex vk) is the same as the second segment of λ′. Identify the vertex st in the third segment (including vk) of λ that is in the same position as the vertex vr λ′ (h) in the second segment of λ′. Set rλ(h) = t. 3) If j ≤ rλ′(h) ≤ k − 1 then note that the second segment of λ (together with the vertex vi−1) is the same as the third segment of λ′. Identify the vertex st in the second segment (including vi−1) of λ that is in the same position as the vertex vr λ′ (h) in the third segment of λ′. Set rλ(h) = t. 4) If k ≤ rλ′(h) identify the vertex st in the fourth segment of λ that is in the same position as vertex vλ′(h) in the fourth segment of λ′ and set rλ(h) = t. Jo ur na l A lg eb ra D is cr et e M at h. 200 Symmetrized presentations of F We now prove that λ is a legal path by checking the conditions of Definition 3.2. Definition 3.2 has three parts, (1), (2) and (3). Part (2) requires checking that λ reaches certain edges. This requires checking Definition 3.1, which has many parts, (1a), (1b), (1c), (1d) and (2a), (2b), (2c), (2d). The arguments involved in checking many of the conditions are very similar to each other and involve lengthy case analyses. Therefore, we present the most difficult and representative parts and cases to prove in detail and omit the details for the remaining cases, which are similar to the ones presented in detail. The parts we prove in detail are: Definition 3.2 (1) and the Definition 3.1 (2a), (2b) and (2d) portions of Definition 3.2 (2). 3.2 (1) Since λ′ is a legal path, v0 = s0 is the vertex labeled 1 2 on the bottom and vn = sn−2 is the vertex labeled 1 2 on the top. Since λ also begins at s0 and ends at sn−2, so condition one is satisfied. 3.2 (2) We must show that λ reaches every non-central edge in D(f). Let h be a non-central edge of D(f). The argument proving that λ reaches h in the case that rλ′(h) = 0 is similar to the argument for the case in which rλ′(h) > 0, so we present details of the case that rλ′(h) > 0 and omit the details in the case that rλ′(h) = 0. So, assume that rλ′(h) = l > 0. We must verify that the conditions of Definition 3.1 (2a) – (2d) are satisfied. For convenience of notation, let rλ(h) = N so that sN = vl. 3.1 (2a) Since λ′ reaches h at vl, h is incident to vl in D(f). By definition, rλ(h) is the s-subscript of the occurrence of the vl at which h is reached in λ′. Thus, h is incident to srλ(h). 3.1 (2b) Let m be a non-central edge below h, and let M = rλ(m) and M ′ = rλ′(m), so that sM = vM ′ . We must show that either M < N or that m is incident to sN . Assume that m is not incident to sN . By the construction of rλ, we see that m is not incident to vl. Since λ′ is a legal path, M ′ = rλ′(m) < rλ′(h) = l. We separate the argument into cases that depend on the relative positions of vl and vM ′ . i. If sN and sM are in the same interval of λ then they are in the same interval of λ′ and occur in the same order there as in λ. Since λ′ is a legal path, M ′ < l, so M < N , as required. ii. If sN and sM are in different intervals of λ′, there are again several cases. Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 201 A. If k ≤ l ≤ n, then vl is in the final interval of the path λ′ and so sN is in the final interval of λ. Since λ′ is a legal path, m must be reached at vM ′ in one of the intervals [v0, vi−1], [vi, vj−1], or [vj , vk−1] of λ′. Since these are also the first three of λ and sN is in the last interval of λ, we have M < N . B. If i ≤ l ≤ (j − 1), then vl occurs in the second interval of λ′ and sN occurs in the third interval of λ. Since m is reached before h in λ′ and since vM ′ is in a different interval from vl, we know that vM ′ appears in the first interval of λ′, which is the same as the first interval of λ. Thus sM is in the first interval and sN is in the third interval of λ proving that M < N as required. C. If j ≤ l ≤ (k − 1), we show that vM ′ is in the first interval of λ′. By a similar argument to that of the previous case, we know vM ′ cannot be in the last in- terval of λ′. Thus, we need to show that vM ′ is not in the second interval of λ′. Assume toward contradiction that vM ′ is in the second interval. By Observation 3.4, we know that m is incident to wz and wu with z, u ≥ b. We also know that h is incident to ws and wg with s, g ≤ a. But, we know that s, g ≤ a < b ≤ z, u, so m is not below h and we have a contradiction. D. If 0 ≤ l ≤ (i − 1), this case is argued similar to Case (i). 3.1 (2c) Let m be a central edge below h in D(f). We must show that m does not appear in λ after vertex sN . We let r be an edge in λ occurring after sN . We must show that m 6= r. The argument involves careful case analysis of the relative positions of sN and r in λ and λ′. The details are similar to the details in 3.1 (2b) and (2d), so we omit them. 3.1 (2d) Since N = rλ(h), we must show that h does not occur in λ after vertex sN . To do this let r > N . We show that h 6= pr by considering several cases. i. If sN and pr are in the same interval within λ, then they occur in the same interval of λ′ and therefore pr appears after vl in λ′. Since λ′ is a legal path in D(f), it follows from definition 3.1 (2c) that pr 6= h. Jo ur na l A lg eb ra D is cr et e M at h. 202 Symmetrized presentations of F ii. If sN and pr are not in the same interval within λ, we separate further into cases. A. If k ≤ l ≤ n, then h is reached by a vertex in the final interval of the path λ′. By the definition of rλ, we know therefore that N > l and so r > l. Therefore, pr and sN are in the same interval, and the argument in the previous case shows that h 6= pr. B. If i ≤ l ≤ j − 1, then h is reached by a vertex in the second interval of the path λ′. Since λ′ is a legal path, we know that h 6= qc for any qc in [vj , vk−1] or [vk, vn]. Now, by the definition of rλ, sN appears in the third interval of λ. Since pr appears after sN in λ and not the same interval, we know that pr is within the fourth interval of λ, which is contained within the λ′ interval, [vk, vn]. Therefore, we conclude that h 6= qp. C. If j ≤ l ≤ k − 1, then h is reached by a vertex in the third interval of the path λ′. Thus, h 6= qc for any qc within [vk, vn]. We now show that h 6= qc for qc within [vi, vj−1]. Assume toward contradiction that h = qc for some i < c ≤ j − 1. Thus, h is incident to vc. By Observation 3.3, we conclude that h is incident to some wu, with u ≥ b. Since h is reached by λ′ at vl with j ≤ l ≤ k −1, by Observation 3.4 we know that h must be incident to some ws and wg with s, g ≤ a. Therefore, s, g ≤ a < b ≤ u, and we have a contradiction. Thus, h 6= qc for any edge qc within the second or fourth intervals of λ′. Now, by the definition of rλ, we know that sN occurs within the second interval of λ, so pr occurs in the third or fourth intervals of λ, which are contained in the second and fourth intervals of λ′. Since h is not equal to any qc occurring in these intervals, it follows that h 6= pr. D. If 0 ≤ l ≤ i − 1 then by the definition of rλ, the vertex sN occurs in the first interval of λ. Therefore, pr occurs within the second, third or fourth interval of λ, which are contained in the second, third and fourth intervals of λ. Since h is reached by λ′ at a vertex in the first interval of λ′, definition 3.1 (2c) implies that h 6= qc Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 203 for any qc in the second third or fourth intervals of λ′. Since pr lies in one of these intervals, h 6= pr. 3.2 (3) Let pc be an edge in λ, and m a non-central edge below qc. We must show that λ reaches m before sc. Since λ′ is a legal path, we know that m is reached by λ′ at some vertex in λ′ that occurs before vr λ′ (pc). Again, the argument involves careful case analysis of the relative positions of sc and m in λ and λ′. The details are similar to the details in 3.1 (2b) and (2d), so we omit them. This concludes the proof that λ is a legal path in D(f), contradicting the minimality of λ′. Therefore, no bottom-most edge appears more than twice in a legal path. In the above lemma, we modified paths in a diagram for a single given element f ∈ F . During the proof that φZ1 computes the length function with respect to Z1, we occasionally must use paths in one diagram, D(f) to construct paths in the diagram D(fα) for a generator α ∈ Z1 ∪Z−1 1 . As described in Subsection 2.2, if α ∈ Z1 ∪ Z−1 1 then the diagrams D(f) and D(fα) differ by at most the placement of the 1 2 labels or by at most two edges and one vertex. Although D(f) and D(fα) are formally different diagrams, it will be convenient to abuse notation and refer to a single edge or vertex as “belonging to” both diagrams. We formalize this as follows. If α is the generator x0 or x−1 0 , then ignoring the labeling of the vertices, D(f) and D(fα) are isomorphic by a unique diagram isomorphism that takes the vertex labeled 1 2 in D(fα) to the vertex along the bottom path one to the left or right (depending on whether x0 or x−1 0 was used) of the 1 2 label in D(f) and takes upper edges to upper edges and lower edges to lower edges. If e is an edge of D(f), any reference to “edge e” in D(fα) refers to the image of e under this isomorphism. A similar convention is used for edges of D(fα) and vertices of D(f) and D(fα). If α is the generator x−1 1 and if D(fα) differs from D(f) by the addition of an edge, then there is a unique edge e′ in D(fα) such there is an isomorphism between D(f) and D(fα) \ {e′} that respects the 1 2 labeling and takes upper edges to upper edges and lower edges to lower edges. Moreover, this isomorphism is unique. If e is an edge of D(f), any reference to “edge e” in D(fα) refers to the image of e under this isomorphism. A similar convention is used for edges of D(fα) \ {e′} and vertices of D(f) and D(fα). Jo ur na l A lg eb ra D is cr et e M at h. 204 Symmetrized presentations of F 1 2 1 2 v1 v′ 1 k k′ k1 k2 D(f) D(fα) Figure 14. Multiplication by x−1 1 If α is the generator x−1 1 and if D(fα) differs from D(f) by the deletion of an exposed upper edge in D(f), then the situation is slightly more complicated. In this case, we denote the central edge emanating to the right from the vertex labeled 1 2 in D(fα) by k′. In the diagram D(f) we denote the central edge emanating to the right from 1 2 by k1 and central edge emanating from the right endpoint of k1 by k2. We denote the bottommost upper edge emanating from the vertex 1 2 in D(f) by k. Finally, we denote as v1 and v′ 1 the terminal vertices of k and k′ respectively, as shown in Figure 14. There is a unique graph isomorphism between D(f) \ {k, k1, k2} and D(fα) \ {k′} that preserves the 1 2 labeling, central, upper and lower edges. This isomorphism allows us to refer to edges and vertices as belonging to both D(f) and D(fα) as in the cases for multiplication by x0 and x−1 0 . The conventions for multiplying by the generator x1 are obtained by using the conventions for x−1 1 and reversing the roles of f and fα. The conventions for using this terminology with the generators y1 and y−1 1 are formulated analogously to those for x1 and x−1 1 , with the roles of right and left reversed. The final tool used in the proof of Theorem 3.5 is the following lemma of Fordham [8], which gives sufficient conditions for a function that guarantee that it computes the length of elements with respect to a given generating set. Lemma 3.7 ( [8], Lemma 3.3.1). Given a group G, a generating set X and a function φ : G → {0, 1, 2, . . .}, if φ has the properties: Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 205 1) φ(IdG) = 0; 2) if φ(g) = 0, then g = IdG; 3) if g ∈ G and α or α−1 is an element of X, then φ(g) − 1 ≤ φ(gα); and 4) for any non-identity element g ∈ G, there is at least one α ∈ G with either α or α−1 in X such that φ(gα) = φ(g) − 1, then φ(g) = l(g) for all g ∈ G, where l(g) denotes the word length of g with respect to the generating set X. We now begin the proof of Theorem 3.5. Proof. Let f ∈ F . We define the function φZ1 by φZ1 (f) = E(f) + P (f). To prove that this function computes the word length of f with respect to the generating set Z1, it suffices show that it satisfies the four properties of Lemma 3.7. Property 1 of Lemma 3.7: The diagram for the identity element, id in F contains no non-central edges, and the same vertex is labeled 1 2 on the bottom and the top. Therefore, there exists a legal path with length zero and it follows that φZn (id) = 0. Property 2 of Lemma 3.7: If φZ1 (f) = 0, then E(f) = 0 and P (f) = 0. Thus, f contains no non-central edges and therefore there exists a legal path in f of length zero. It follows from the definition of legal path that the top and bottom 1 2 labels must be located on the same vertex. Thus, f is the identity. Property 3 of Lemma 3.7: Let f ∈ F and α ∈ Z1 ∪Z−1 1 . We must show that φ(f) − 1 ≤ φ(fα). We do this by analyzing the cases, α = x0, α = x−1 0 , α = x1, α = x−1 1 , α = y1, α = y−1 1 separately. This frequently involves checking the conditions Definition 3.2 through careful and lengthly case analysis, as in the proof of Lemma 3.6. Many of the cases involve arguments very similar to each other or the arguments in Lemma 3.6. Therefore, we present the details for only the most difficult and representative cases and omit the details for the remaining cases. For ease of notation, let E(f) = e, P (f) = p, and let v0 be the vertex labeled 1 2 on the bottom in D(f). Case 1: α = x0. Multiplying f on the right by x0 moves the bottom 1 2 label left to the nearest exposed vertex along the bottom along, say, edge g. Since we have not added any edges, E(fα) = e and we must show that P (f) − 1 ≤ p. Assume towards a contradiction that P (fα) < p − 1. Thus, Jo ur na l A lg eb ra D is cr et e M at h. 206 Symmetrized presentations of F there exists a legal path, say λ′ = v′ 0q′ 0v′ 1q′ 1 · · · q′ lv ′ l, of length l, less than p − 1. Fix a reaching function rλ′ for λ′. Consider the path λ = v0q1v1q2 · · · ql+1vl+1 in D(f) defined by q1 = g, qi = q′ i−1 for i > 1, and vi = v′ i−1 for i ≥ 1. Define the function rλ by rλ(e) = rλ′(e) + 1. We show that rλ is a reaching function with respect to which λ is a legal path in D(f) by verifying the conditions of Definition 3.1. Let h be a non-central edge in D(f). Since λ′ is a legal path, rλ′(h) = i < ∞. We now verify the conditions of Definition 3.1 by separately considering the cases i = 0 and i > 0. Case i = 0: We have rλ(h) = 1, so part (2) of Definition 3.1 applies. 3.1 (2a) By definition 3.1 (1a), h is incident to v′ 0 in D(fα). Since v′ 0 = v1, h is incident to v1. (2b) By definition 3.1 (1b), every non-central edge below h is also incident to v′ 0 in D(fα), and thus incident to v1 in D(f). (2c) By definition 3.1(1c), no central edge below h appears as in λ′ q′ j with j > 0. Therefore, no central edge below h appears in λ as qj with j > 1. (2d) By definition 3.1 (1d), h does not appear in λ′ as q′ j for any j > 0. Thus, h does not appear in λ as qj for any j > 1. Case i > 0: In this case, rλ(e) = i + 1 ≥ 1 so part (2) of Definition 3.1 applies again. 3.1 (2a) Since rλ′ is a reaching function for λ′, h is incident to v′ i = vi+1 in D(f). (2b) Let m be a non-central edge below h in D(f). Then m is below h in D(fα), and by definition 3.1 (2b) there are two possible cases. • Edge rλ′(m) ≤ i − 1. In this case, rλ(m) = j + 1 ≤ i < rλ(h). • Edge m is incident to v′ i in D(fα). In this case, m is incident to vi+1 in D(f), as required. (2c) Let m be a central edge below h in D(f). Therefore, m is a central edge below h in D(fα), and by definition 3.1 (2c), we know m 6= q′ j for any j > i. Thus m 6= qj+1 for any j > i. Therefore, m 6= qj for any j > i + 1, as required. (2d) By definition 3.1 (2d), we know that q′ j 6= h for any j > i since λ′ is a legal path in D(fα). Thus, h 6= qj+1 in D(f) for any j + 1 > i + 1 as required. Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 207 We now verify that λ is a legal path with respect to reaching func- tion rλ. 3.2 (1) Since λ′ is a legal path in D(fα), v′ l is the vertex labeled 1 2 on top. Since λ is the path from v0 to vl+1 = v′ l, it is a path from the vertex labeled 1 2 on bottom to the vertex labeled 1 2 on top in D(f). 3.2 (2) Let e be a non-central edge of D(f). Since λ′ is a legal path, rλ′(e) < ∞. So, rλ(e) = rλ′(e) + 1 < ∞, and λ reaches every non-central edge of D(f) with respect to rλ. 3.2 (3) Let m be an edge below qi in D(f). We must show that rλ(m) < i. Since q1 is a bottommost edge, i cannot equal 1. Thus, we may assume that i > 1. Now m is below edge q′ i−1 in D(fα). By definition 3.2 (3), m is reached by λ′ before v′ i−1 in D(fα) for all 0 ≤ i − 1 ≤ l. Therefore, m is reached by λ before vi for all 1 ≤ i ≤ l + 1. Thus, λ is a legal path in D(f) of length l + 1, where l < p − 1. Therefore, we contradict the assumption that the length of a minimal length legal path in D(f) is p. So, φ(fα) ≥ φ(f) − 1. Case 2: α = x−1 0 . Multiplication by α on the right acts similarly to Case 1. The only difference is that v1 and q1 will now lie to the right of v0. Therefore, this case is proved in a similar manner. Case 3: α = x1. There must always exist an edge, k, connecting the vertex v0 to the nearest exposed vertex on the right. Call this vertex v1. We can see that if there exists a lower edge incident to and to the right of v0, then k is a lower edge. Otherwise, k is a central edge. Subcase 1: k is a central edge. Multiplication by α adds an upper edge k′ from v0 to v1 as shown in Figure 15. Now, E(fα) = e + 1, so it suffices to show that P (fα) ≥ p − 2. Assume toward contradiction that P (fα) < p − 2. Then, there exists a legal path, λ′ = v′ 0q′ 1v′ 1q′ 2 · · · q′ lv ′ l with reaching function rλ′ in D(fα) with l < p − 2. Figure 15. Diagrams of D(f) (left) and D(fα) (right) Since there are no edges below k in D(f), there are not any non-central edges below k′ in D(fα). Since λ′ is of minimal length, λ′ does not use Jo ur na l A lg eb ra D is cr et e M at h. 208 Symmetrized presentations of F the central edges below k′, for otherwise both would have to be used in succession and we could use k′ instead and construct a shorter legal path. Therefore we may define path λ in D(f) by λ = v0q1v1q2v2 · · · qlvl in D(f) by vi = v′ i for all 0 ≤ x ≤ l, qj=q′ j if q′ j 6= k′, and qj = k if q′ j = k′. We define the function rλ by rλ(e) = rλ′(e). We claim that λ is a legal path in D(f) with respect to rλ. The details in the proof that rλ is a reaching function for λ and that λ is a legal path with respect to rλ involve case analysis and arguments similar to the arguments in the case of α = x0, so we omit them here. Since the length of λ is equal to p − 2, this contradicts the fact that P (F ) = p, proving that P (fα) ≥ p − 2 as required. Subcase 2: k is a non-central edge. In this case, k is a lower, bottom- most edge connecting v0 and v1. Multiplying by x1 deletes edge k, so E(fα) = e − 1, and it suffices to show that P (fα) ≥ p. We assume toward contradiction that P (fα) < p, so there exists a legal path λ′ = v′ 0q′ 1v′ 1q′ 2 · · · q′ lv ′ l with reaching function rλ′ in D(fα) with l < p. Consider the path λ = v0q1v1q2 · · · qlvl defined by qi = q′ i and vi = v′ i. We claim that λ is a legal path in D(f) with respect to the reaching function rλ′ . Again, the details in the proof that rλ is a reaching function for λ and that λ is a legal path with respect to rλ involve case analysis and arguments similar to the arguments in the case of α = x0, so we omit them here. Since the length of λ is less than p, this contradicts the fact that P (f) = p and proves that P (fα) ≥ p. Case 4: α = y1. Multiplying by α on the right acts similarly to Case 3. The only difference is that v1 is the nearest exposed vertex to the left of v0. Therefore, this case can be proved in a similar manner. Case 5: α = x−1 1 . Subcase 1: There does not exist an exposed upper edge emanating to the right of v0. In this case, multiplication by x−1 1 adds a bottom-most edge, k′, with k′− = v0 and k′+ equal to the second nearest vertex to the right along the bottom path of D(f). There is a unique finite region that is bounded by k′ together with two more edges, k1 and k2. Let k1 be the edge incident to k′− and k2 be the one incident to k′+, and let g be the vertex between k1 and k2 as shown in Figure 16. Now, E(fα) = e + 1, so suffices to show that P (fα) ≥ p − 2. We assume toward contradiction that P (fα) < p − 2, so there exists a legal path λ′ = v′ 0q′ 1v′ 1q′ 2v′ 2 · · · q′ lv ′ l with reaching function rλ′ in D(fα) with length less than p − 2. From Lemma 3.6, we know that k′ appears at most twice in λ′. Consider the following cases: Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 209 Figure 16. Diagrams of D(f) (left) and D(fα) (right) Case A: Edge k′ appears twice in λ′. Let x and y be such that k′ = q′ x and k′ = q′ y with 1 ≤ x < y ≤ l. Define a path λ in D(f) by following λ′, but replacing q′ x by [k′ 1gk′ 2], and q′ y by [k′ 2gk′ 1]. Formally, λ = [v′ 0, v′ x−1][k1gk2][v′ x, v′ y−1][k2gk1][v′ y, v′ l]. Define the function rλ by, rλ(e) =        rλ′(e) if rλ′(e) ≤ x − 1 rλ′(e) + 1 if x < rλ′(e) ≤ y − 1 rλ′(e) + 2 if rλ′(e) ≥ y. We now prove that rλ is a reaching function for λ with respect to which λ is a legal path. For convenience, we rename the vertices and edges in λ by λ = v0p1v1p2 · · · vl+2pl+2. We begin by verifying that rλ satisfies the conditions of Definition 3.1. Let h be a non-central edge in D(f). 3.1 (2a) Edge h is also a non-central edge in D(fα), and by the fact that λ′ is a legal path with respect to rλ′ h is incident to v′ r λ′ (h). By the definition of rλ, we see that h is incident to vrλ(h). (2b) Let m be a non-central edge below h in D(f). Then, m is a non- central edge below h in D(fα). Suppose that m is not incident to vrλ(h) in D(f). By the definition of rλ, m is not incident to v′ r λ′ (h). Therefore, since rλ′ is a reaching function we must have rλ′(m) < rλ′(h). By the definition of rλ, this implies that rλ(m) − rλ′(m) ≤ rλ(h) − rλ′(h) proving that rλ(m) < rλ(h) as required. (2c) Let m be a central edge below h in D(f). Let z be an edge in D(f) appearing in λ after vrλ(h). We must show that m 6= z. Subcase 1: z = q′ a for some a. Since m is a central edge below h in D(fα) and since λ′ is a legal path in D(fα), m cannot appear in λ′ as q′ a for any a > rλ′(h). Thus, z appears in λ′ before rλ′(h), and by the definitions of λ and Jo ur na l A lg eb ra D is cr et e M at h. 210 Symmetrized presentations of F rλ, z appears in λ before rλ(h). Since z appears in λ after vrλ(h), we have m 6= z as required. Subcase 2: z 6= q′ a for any a but z = k1. If k1 is a non-central edge, since we assumed m is a central edge, m 6= z. So, we may assume that k1 is central. Since z 6= q′ a for any a, k1 appears in λ because of the fact that k′ appeared in λ′. Since z appears in λ after vrλ(h), k′ appears in λ′ after v′ r λ′ (h). To prove that m 6= z, we assume toward contradiction that m = z = k1. Therefore, k1 is below h. Since k′ is below k1, k′ is below h in D(fα). Since λ′ is a legal path in D(fα), by definition 3.2 (3), k′ must be reached before v′ r λ′ (h). But, k′ appears in λ′ after v′ r λ′ (h), contradicting condition (2d) of Definition3.1 for rλ′ . Subcase 3: z 6= q′ a for any a but z = k2. The details in this case are nearly the same as those in the case that z = k1, so we omit the repetition here. (2d) Let z be an edge in λ after vrλ(h). We must show that z 6= h. Subcase 1: z = q′ j for some j. By the definition of λ and rλ, edge q′ j appears in λ after vrλ(h) if and only if it appears in λ′ after rλ′ . Thus, z = q′ j appears in λ′ after after vrλ(h) and so j > rλ′(h). Since λ′ is a legal path in D(fα), z = q′ j 6= h as required. Subcase 2: z 6= q′ j for any j but z = k1. If k1 is central, then k1 6= h since h is non-central. Thus, we may assume that k1 is non-central. Assume towards a contradiction that h = z. Thus, we have h = z = k1. Since z 6= q′ j for any j, k1 appears in λ because of the fact that k′ appeared in λ′. Now, k′ cannot appear in λ′ after vr λ′ (h), so k1 cannot appear in λ after rλ(h). Since k1 = z, this contradicts the assumption that z is an edge of λ occurring after rλ(h), proving that h 6= z. Subcase 3: z 6= q′ j for any j but z = k2. The details in this case are nearly the same as those in the case that z = k1, so we omit the repetition here. We now check the conditions of Definition 3.2 to verify that λ is a legal path with respect to rλ. 3.2 (1) This condition is satisfied as usual. Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 211 3.2 (2) Let h be a non-central edge in D(f). Since λ′ is a legal path with respect to rλ′ , it follows that rλ′(e) < ∞. By the definition of rλ, we have therefore that rλ(e) < ∞. 3.2 (3) Consider edge pi in λ and let m be a non-central edge below h in D(f). We must show that rλ(m) < i. Since k1 and k2 are bot- tommost edges in D(f), we may assume that pi 6= k1 and pi 6= k2. Therefore, pi appears in λ′ as, say, q′ j . Now, h is below q′ j in λ′, so rλ′(h) < j. Depending on the relative positions of q′ j , qx and qy in λ′, we may have i = j, i = j + 1 or i = j + 2. But, in any of those cases, rλ(h) is increased over rλ′(h) by the same amount that i is increased over j. Therefore rλ(h) < i, as required. Case B: The edge k appears only once in λ′. The details of this case are similar to the details of the case in which k appears twice, with the single simplifying difference that the edge k must be replaced only once in the path λ to produce the path λ′. We omit the repeated details of the proof here. Case C: Edge k does not appear in λ′. In this case, it is straightforward to verify that λ is a legal path in D(f) with respect to the reaching function rλ′ . Subcase 2: There exists an exposed upper edge, k, emanating to the right from v0. Denote by k1 and k2 the central edges below k. Multiplica- tion by x−1 1 deletes edge k. Then E(fα) = e − 1, and it is sufficient to show that P (fα) ≥ p. We assume toward contradiction that P (fα) < p, so there exists a legal path λ′ = v′ 0q′ 1v′ 1q′ 1 · · · q′ lv ′ l with respect to reach- ing function rλ′ with l < p in D(fα). Define the path λ in D(f) by λ = v0q1v1q2v2 · · · qlvl with vj = v′ j , qj = q′ j if q′ i 6= k′, and qi = k if q′ i = k′ for all 0 ≤ j ≤ l. We claim that λ is a legal path in D(f) with respect to the reaching function rλ′ . Since the length of λ is less than P (f), we have the desired contradiction, proving that P (fα) ≥ p. The details involved in this case are similar to those just presented in Subcase 1, so we omit them here. Case 6: α = y−1 1 . Multiplication by α in this case acts similarly to Case 5. The only difference is that k emanates to the left of v0. The proof that φ(f) − 1 ≤ φ(fα) in this case follows the proof in the case that α = x−1 1 with the roles of “left" and “right" exactly reversed, so we omit the repeated details here. This finishes the proof that φ satisfies Property 3 of Lemma 3.7. Jo ur na l A lg eb ra D is cr et e M at h. 212 Symmetrized presentations of F Property 4 of Lemma 3.7: Let f ∈ F , E(f) = e and P (f) = p. Thus φ(f) = e + p. We must show that there exists an α ∈ Z1 ∪ Z−1 1 such that φ(fα) = φ(f) − 1. Let λ = v0q1v1q2v2...qpvp be a legal path in D(f) of minimal length, and let rλ be a reaching function with respect to which λ is a legal path. Case 1: q1 is a lower or central edge. Subcase A: There exists a non-central edge, g with rλ(g) = 0. If g is an upper edge to the right of v0, take α = x−1 1 . If g is an upper edge to the left of v0, take α = y−1 1 . If g is a lower edge to the right of v0, take α = x1. If g is a lower edge to the left of v0, take α = y1. In any of these cases, multiplying f on the right by the corresponding α results in deletion of edge g. Therefore, E(fα) = e − 1 We claim that λ is a legal path for D(fα) with respect to rλ, which shows that P (fα) ≤ p. This follows from the fact that edge g cannot appear in λ because rλ(e) = 0. But by Property 3, which has been proven, φ(fα) ≥ φ(f) − 1. But, in this case, E(fα) = E(fα) − 1. So, P (fα) ≥ P (f) = p. Therefore, P (fα) = p, and φ(fα) = φ(f) − 1. Subcase B: There does not exist any non-central edge with rλ(e) = 0. If q1 lies to the left of v0, take α = x0. If q1 lies to the right of v0, take α = x−1 0 . In either case, multiplication of f on the right by the corresponding α will move the bottom label of 1 2 from v0 to v1. Thus, E(fα) = e, and we must show that P (fα) = p − 1. We claim that λ′ = v1q2v2...qpvp is legal path for D(fα) with respect to the reaching function rλ′ defined by rλ′(e) = rλ(e) − 1. This follows from the fact that since 0 ≤ rλ′(e) < ∞ for all non central edges e, we have 1 ≤ rλ′(e) < ∞ for all non-central edges. Since all edges are reached by λ′ at a vertex numbered one less than the one at which they were reached by λ, all of the conditions of Definitions 3.1 and 3.2 are easily verified. Thus, P (fα) ≤ p − 1. But by Property 3, and the fact that E(fα) = E(f), we have P (fα) ≥ P (f) − 1. Therefore, P (fα) = p − 1, as required. Case 2: q1 is an upper edge. Subcase A: There exists a non-central edge, g, with rλ(e) = 0. Details of this case are very similar to those of Case 1 Subcase A above, so we omit the repetition. Subcase B: No non-central edge e satisfied rλ(e) = 0. Since q1 is the first edge in the path, every non-central edge below q1 must be reached at v0. Since no edge is reached by λ at v0, q1 must be an exposed upper edge. If q1 lies to the left of v0, set α = y−1 1 . If q1 lies to the right of v0, set α = x−1 1 . In either case, multiplication of f on the right by the corresponding α will delete edge q1 and the vertex Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 213 below q1 that is adjacent to v0 along to the central line, say wa and replace the two central edges incident to wa by a single edge, say q′ 1. Thus, E(fα) = E(f) − 1 and it suffices to show that P (fα) = P (f) = p. Consider the path λ′ = v0q′ 1v1q2 · · · qpvp. We claim that λ′ is a legal path for D(fα) with respect to the reaching function rλ. The details in the proof of this claim are similar to the details in the previous proofs, so we omit them here. This proves that P (fα) ≤ p. Now, Property 3, together with the fact that E(fα) = E(f) − 1 imply that P (fα) = p, as required. Therefore, there exists an α ∈ Z1 ∪ Z−1 1 such that for all f ∈ F , φ(fα) = φ(f) − 1. We have now shown that the formula φZ1 (f) = E(f) + P (f) satisfies all four properties of Fordham’s Lemma 3.7. Thus, φZ1 = lZ1 . 4. Dead ends In this section, we conclude by sketching an argument showing F contains dead end elements with respect to Z1. We claim that the the element g ∈ F whose wave diagram is pictured in Figure 17 is a dead end with respect to Z1. The bold edges and arrows indicate a path λ used in determining l(g). Figure 17. Dead end of depth one It is easy to see that E(g) = 8. Consider the length 10 path λ = (v0e1v1e1v3 . . . v9e10v10) in D(g) starting with e1 and traversing the bold edges in the directions indicated by the arrows. In order not to clutter the diagram too much, we have omitted the vertex and edge names after e5. If we define the function rλ by rλ(e) = i if vi is the first vertex in λ incident to e, then rλ is a reaching function for λ with respect to which λ is a legal path. We provide a short explanation as to why λ is the minimal length legal path for g. Jo ur na l A lg eb ra D is cr et e M at h. 214 Symmetrized presentations of F Suppose towards a contradiction that λ′ = (u0f1u2f2 . . . fkuk) is a legal path in D(g) of length k < 10. The vertex v0 divides the diagram into two halves, the “left” half and the “right” half that are isomorphic by a direction-reversing isomorphism. Since λ′ has length at most 9, one half of D(g) contains 4 or fewer edges from λ′. Without loss of generality, we assume that it is the right half. Since λ′ must reach edge b, we see that the edge e2 must occur twice, once in each direction, in λ′. This leaves only two more edges of λ′ in the right half of D(g). These must be e1 once in each direction, and the above four edges must form a consecutive subpath β = (v0e1v1e2v2e−1 2 v2e−1 1 v0) in λ. Now, the edge e1 cannot be reached by λ′ before the end of β since it occurs as the last edge in β. Therefore, the edge c cannot be reached before the end of β since e1 is below c. However, the rest of λ is to the left of v0, and thus cannot reach c, contradicting the fact that, as a legal path, λ′ reaches every non-central edge of D(g). Therefore, the minimal length of a legal path in D(g) is 10, and so l(g) = 18. To show that g is a dead end element of F with respect to Z1, we consider the effect of multiplying g by elements of Z1 ∪ Z−1 1 . First, we consider multiplication of g by x−1 0 . The diagram of gx−1 0 is pictured in Figure 18. We see that E(gx−1 0 ) = 8 and the path indicated by the bold edges is a legal path of length 9. Therefore, lZ1 (gx−1 0 ) ≤ 17. Figure 18. Diagram for gx−1 0 Next, we consider multiplication of g by x1. The diagram of gx1 is pictured in Figure 19. We see that E(gx1) = 7 and the path indicated by the bold edges is a legal path of length 11. Therefore, lZ1 (gx1) ≤ 18. Next we consider multiplication of g by x−1 1 . The diagram of gx−1 1 is pictured in Figure 20. We see that E(gx−1 1 ) = 9 and the path indicated by the bold edges is a legal path of length 9. Therefore, lZ1 (gx−1 1 ) ≤ 18. By the symmetry of g and the generators x1 and y1, the arguments that y1 and y−1 1 do not increase the length of g are similar to those for Jo ur na l A lg eb ra D is cr et e M at h. M. Horak, A. Johnson, A. Stonesifer 215 Figure 19. Diagram for gx1 Figure 20. Diagram for gx−1 1 x1 and x−1 1 . Therefore, lZ1 (gα1) ≤ 18 for all αi ∈ Z1, showing that g is a dead end and that F has dead end depth at least 2 with respect to Z1. References [1] G. N. Arzhantseva, V. S. Guba, and M. V. Sapir, Metrics on diagram groups and uniform embeddings in a Hilbert space, Comment. Math. Helv. 81 (2006), no. 4, 911–929. MR 2271228 (2007k:20084) [2] James Belk and Kai-Uwe Bux, Thompson’s group F is maximally nonconvex, Geometric methods in group theory, Contemp. Math., vol. 372, Amer. Math. Soc., Providence, RI, 2005, pp. 131–146. MR MR2139683 (2006f:20050) [3] , Thompson’s group F is maximally nonconvex, Geometric methods in group theory, Contemp. Math., vol. 372, Amer. Math. Soc., Providence, RI, 2005, pp. 131–146. MR MR2139683 (2006f:20050) [4] O. V. Bogopol′skĭı, Infinite commensurable hyperbolic groups are bi-Lipschitz equiv- alent, Algebra i Logika 36 (1997), no. 3, 259–272, 357. MR 1485595 (98h:57002) [5] J. W. Cannon and Floyd, What is. . . thompson’s group?, Notices Amer. Math. Soc. 58 (2011), no. 8, 1112–1113. [6] J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson’s groups, Enseign. Math. (2) 42 (1996), no. 3-4, 215–256. MR 1426438 (98g:20058) [7] Sean Cleary and Jennifer Taback, Combinatorial properties of Thompson’s group F , Trans. Amer. Math. Soc. 356 (2004), no. 7, 2825–2849 (electronic). MR 2052598 (2005b:20074) Jo ur na l A lg eb ra D is cr et e M at h. 216 Symmetrized presentations of F [8] S. Blake Fordham, Minimal length elements of Thompson’s group F , Geom. Dedi- cata 99 (2003), 179–220. MR MR1998934 (2004g:20045) [9] Victor Guba and Mark Sapir, Diagram groups, Mem. Amer. Math. Soc. 130 (1997), no. 620, viii+117. MR MR1396957 (98f:20013) [10] Matthew Horak, Melanie Stein, and Jennifer Taback, Computing word length in alternate presentations of Thompson’s group F , Internat. J. Algebra Comput. 19 (2009), no. 8, 963–997. MR 2596882 (2011c:20077) [11] , A note on convexity properties of Thompson’s group F , J. Group Theory (2011), to appear. [12] Russell Lyons, Robin Pemantle, and Yuval Peres, Random walks on the lamplighter group, Ann. Probab. 24 (1996), no. 4, 1993–2006. MR 1415237 (97j:60014) Contact information M. Horak University of Wisconsin-Stout Menomonie, WI 54751 USA E-Mail: horakm@uwstout.edu URL: www.uwstout.edu/faculty /horakm/index.cfm A. Johnson Grand Valley State University Allendale, MI 49401-9403 USA E-Mail: johnsoa1@mail.gvsu.edu A. Stonesifer St. Olaf College Northfield, Minnesota 55057 USA E-Mail: stonesif@stolaf.edu Received by the editors: 05.12.2011 and in final form 07.09.2012.

Word length in symmetrized presentations of Thompson’s group F

Репозитарії

Схожі ресурси