Enumeration Problems in Baumslag-Solitar Groups by Thomas Wong B. Science, University of Queensland, Australia, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Mathematics) The University Of British Columbia (Vancouver) October 2010 c Thomas Wong, 2010 Abstract Geometric group theory refers to the study of finitely generated groups and their properties by exploring the algebraic and topological structure. This thesis will look at various enumeration problems that arises in Baumslag-Solitar groups. Initially, this thesis aims to reproduce and validate some of the work that has been done on the questions of growth, cogrowth and geodesic elements via an enumeration approach. This approach will then be used to explore specific examples of Baumslag-Solitar groups where these questions have not been fully answered. The first part of this thesis will look at the growth of a horocyclic subgroup in Baumslag-Solitar groups. It will then build upon this to develop an algorithm to count the elements of the group in general out to a fixed radius with the intention of further understanding the unresolved cases. The second part of this thesis will use Baumslag-Solitar groups as a basis to develop numerical tests to estimate cogrowth of groups. Since the cogrowth of a group is directly related to the amenability of the group, these numerical tests for cogrowth can be applied to groups such that Thompson’s group F, where the question of amenability is still highly debated. ii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Group Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Baumslag-Solitar Groups and HNN Extensions . . . . . . . . . . 12 2.3 Graph Theory and Matrix Representations . . . . . . . . . . . . . 18 2.4 Generating Function and Complex Variables . . . . . . . . . . . . 19 3 Geodesic Words on Horocycles . . . . . . . . . . . . . . . . . . . . . 23 4 Horocycle Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.1 Special Case: n = 1 and m odd . . . . . . . . . . . . . . . . . . . 36 4.2 Special Case: n = 1 and m even . . . . . . . . . . . . . . . . . . 39 4.3 Special Case: n divides m . . . . . . . . . . . . . . . . . . . . . . 45 4.4 Special Case: n = 2 and m = 3 . . . . . . . . . . . . . . . . . . . 49 Geodesic Words and Growth Rate . . . . . . . . . . . . . . . . . . . 57 5 iii 6 Cogrowth and Amenability . . . . . . . . . . . . . . . . . . . . . . . 68 6.1 Enumeration Approach . . . . . . . . . . . . . . . . . . . . . . . 74 6.2 Eigenvalue Approach . . . . . . . . . . . . . . . . . . . . . . . . 78 6.3 Modified Eigenvalue Approach . . . . . . . . . . . . . . . . . . . 80 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 iv List of Tables 5.1 Estimation of growth rate of Baumslag-Solitar groups . . . . . . . 65 5.2 Estimation of growth rate in a horocycle of BS(2, 3) . . . . . . . . 66 6.1 Enumeration approach without backtracking . . . . . . . . . . . . 76 6.2 Enumeration approach with backtracking . . . . . . . . . . . . . 77 v List of Figures 3.1 Cosets of horocycles of BS(2,3). . . . . . . . . . . . . . . . . . . 25 3.2 Schematic for a geodesic word in a horocycle. . . . . . . . . . . . 28 3.3 Exploration of the coset below. . . . . . . . . . . . . . . . . . . . 31 a22 3.4 A geodesic word for in BS(2, 3). . . . . . . . . . . . . . . . . 33 4.1 Set of exponents that contains Γ(aq ) as a subword. . . . . . . . . 37 4.2 Exploring multiple cosets of BS(1, 6). . . . . . . . . . . . . . . . 40 4.3 Rewritting γ(27k + 11) as γ(12k + 5). . . . . . . . . . . . . . . . 50 4.4 Growth of a horocycle in BS(2, 3). . . . . . . . . . . . . . . . . . 56 5.1 Cutting a geodesic word of Par b−1 aim . . . . . . . . . . . . . . . . 62 5.2 Ratio of sphere sizes. . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 Extrapolation for growth rate. . . . . . . . . . . . . . . . . . . . . 66 5.4 Ratio of sphere sizes for horocycles in BS(2, 3). . . . . . . . . . . 66 5.5 Logarithmic estimation for growth of horocycle in BS(2, 3). . . . 67 6.1 Partitioning words of F2 . . . . . . . . . . . . . . . . . . . . . . . 70 6.2 Amenable groups. . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.3 Non-amenable groups. . . . . . . . . . . . . . . . . . . . . . . . 83 6.4 Extrapolation for amenable groups. . . . . . . . . . . . . . . . . . 83 6.5 Extrapolation for non-amenable groups. . . . . . . . . . . . . . . 84 vi Acknowledgments This thesis represents the destination of a two year journey which extends beyond the realm of academics. I would like to show my appreciation and thanks to those who have made this one of the most fruitful and enjoyable periods of my life. This thesis would not have been possible if not for the precious guidance and support of my supervisor, Dr. Andrew Rechnitzer, whose effort began even before I first arrived in Vancouver. His passion for exploration, combined with a wealth of knowledge and an ever optimistic attitude is a significant source of motivation as I expand my understanding in the field of enumeration. I would also like to thank Andrew for financially supporting my attendance at local and national conferences, and more importantly, the opportunities for me to broaden the scope of my mathematical knowledge. In addition, I would like to express my deepest appreciation for Andrew for going above and beyond his call of duty to provide me with assistance and advice about life in Vancouver. From where to get vegemite to tourist destinations around British Columbia, settling in and finding my feet around this new country has been so much easier because of these small deeds. I would also to say a most sincere thank you to my parents and my brother, Dickson. Their support and encouragement has made my transition to Vancouver less agonising. Their never ending calls and sanity checks has been the perfect remedy during those difficult times. Finally, in a non-exhaustive list: To Shane, Paul, the Chu and Li family and my ultimate team (The PhDs). A big thank you for making these two years so enjoyable and memorable in so many ways. vii Chapter 1 Introduction Enumeration is the field of mathematics that encapsulates a large majority of questions that begin with “How many...”. However, these questions might be difficult or impossible to answer in an ill-defined setting. In geometric group theory, questions about combinatorics and enumerations are asked in the well defined setting of a group and its presentation. A group is a set of objects that obey certain conditions under a binary operation. As an initial example, consider the set Z2 . All the elements in this set can be represented as a pair of integers. That is, every element can be represented in the form (x, y) for some x, y ∈ Z and every such pair (x, y) represents a unique element. Thus the set {(x, y) | x, y ∈ Z} is said to be a set of normal forms for the group Z2 . This set can be turned into a group by attaching the binary operation ‘componentwise addition’ to it. One obvious fact about this group is that the element (0, 0) can be added to any element without changing that element. This point is the identity and it is unique for any group. An alternative but equivalent way to think about the group Z2 is to visualise it as the integer square lattice with the element (0, 0) defined to be the origin. In this setting, every element of the group can be thought of a sequence of single horizontal or vertical steps from the origin. These horizontal and vertical steps (denote them h and v) and their inverses (h−1 and v−1 ) span the whole group and are called generators of the group. Note that the generators for a group does not 1 have to be unique. A sequence of generators is a “word” in the generators. However, not every word of these generators represents unique elements. Consider two examples of words; hh−1 and hvh−1 v−1 . They are both non-trivial words, but it can be checked that they are both equivalent to the identity. The word hh−1 is simply a horizontal step followed by it’s immediate reversal. The condition of taking a step followed by its immediate reversal can occur in any group and hence is a property independent of the group. Subwords with this property can be removed and the sequence still represents the same point. A word which does not contain any such subwords is said to be freely reduced. The word hvh−1 v−1 is equivalent to taking a loop around a unit square in the lattice starting and ending at the origin. Words of this nature is a property specific to the group Z2 . Subwords with this property can be removed and the sequence still represents the same point. In fact, the group Z2 can be fully described by stating the generators and all the loops that it contains. This type of description for a group is known as a presentation for a group and is usually denoted S | R , where S is the set of generators and R represents the set of loops that are specific to the group. In this case, the group Z2 ≡ h, v | hvh−1 v−1 . The set of relations now gives a partition of all the words into equivalence classes and by taking a representative from each class, the set of normal forms can be defined. The relation hvh−1 v−1 ≡ e in the group Z2 can be rewritten as hv = vh. Any occurrences of h can be commuted to the left using that relation and similarly any occurrences of v can be moved to the right. A presentation of the group also admits a natural size function from any word to the natural numbers. The size of a word is simply the length of the sequence in the generators used to produce that word. Given such a presentation for Z2 , it is now natural to ask the following question: Given an element in the group, what is the shortest length sequence in the generators required to construct a word that is equivalent to that element? This number is known as the geodesic length of the element and any word of geodesic length representing the element is called a geodesic word. Since any element in Z2 can be represented as an (x, y) normal form, it suffices to find the geodesic length of these normal forms. In this case, it is clear that the geodesic length of the element (x, y) is |x| + |y|. It is simply the L1 -norm of the vector (x, y). For groups in general, this is a very difficult problem. The next example will illustrate this fact. 2 Consider the group generated by a, b | ban b−1 a−m for n, m ∈ Z. This group is known as the Baumslag-Solitar group with parameters n, m, commonly denoted at BS(n, m). This is the group obtained using two generators subject to one commutation relation. When n = m = 1, this group is just Z2 . Consider the group BS(2, 3), which has the relation ba2 b−1 a−3 ≡ e. Now suppose a normal form is defined as with the previous example where all occurrences of the generator a are pushed to the right and the generator b is pushed to the left. The word a4 b−4 is a geodesic word of length 8 but its normal form after applying the commutation a2 b−1 ≡ b−1 a3 to obtain a4 b−4 ≡ b−1 a6 b−3 ≡ b−2 a9 b−2 ≡ b−2 ab−1 a12 b−1 ≡ b−2 ab−2 a18 , has length 23. By taking a step in b−1 direction, the length of the normal form increases dramatically. The word a4 b−5 is a geodesic word of length 9 and only differs from the previous word by a single generator. However, its normal form b−2 ab−3 a27 has length 33. In general, an arbitrary word is easily converted to its normal form. But unlike Z2 , given a normal form, it is very difficult to find a geodesic word that is equivalent to that normal form. Each normal form can be partitioned into two parts: The suffix, which contains the rightmost exponent of a, and the prefix, which contains everything else. The subgroup which contains all elements with an empty prefix is called a horocyclic subgroup. It is exactly the subgroup generated by the single generator a and this subgroup provides a wealth of interesting enumeration results. In general, finding the geodesic length of an arbitrary word is hard, but this problem simplifies significantly within a horocyclic subgroup since it admits a natural normal form that is of geodesic length. Chapter 3 will develop the machinery to find the geodesic length of any element in this subgroup via the use of this normal form. These results will be applied to various Baumslag-Solitar groups in Chapter 4 to validate the results obtained in independent work by Freden et al. [13]. This machinery will then be applied to the special case of BS(2, 3) to find a previously unseen functional equation satisfied by the generating function for the growth of a horocyclic subgroup. A natural question to follow is whether these ideas can be extend to the set of normal forms for the entire group. That is, does this machinery work for normal forms with an nonempty prefix? Suppose the geodesic lengths of normal forms with a certain prefix are known, what can be said about normal forms with a slightly 3 longer prefix. Recall the previous example. Given that the geodesic length of b−2 ab−2 a18 is known to be 8, can this information be used to show that the geodesic length of b−2 ab−3 a27 is 9? Chapter 5 expands the ideas developed in Chapter 3 to normal forms with nonempty prefixes. As with the previous problem on horocyclic subgroups, a brute force approach is always possible. However, Chapter 5 will conclude with an algorithm that is able to iterate prefixes in turn to reduce the time (spent storing and looking up stored data) and memory (the amount of information stored) required. Thus, the geodesic length provides a natural partition of the elements into spheres of different sizes/geodesic lengths. One possible extension to the previous question is whether it is possible to determine how many elements there are of a fixed geodesic length or of a fixed size. Further, using this information, is it possible to find the generating function for the growth of the group? These questions have attracted interest in the field and partial results have been found over the years. The case where n = m has been solved by Edjvet and Johnson [11] in 1992. In 1994, the generating function has been found by Collins et al. [6] for the case n = 1. More recently, Diekert and Laun [8] managed to find a poly-time algorithm for determining the geodesic length of elements in the case where n divides m. With this in mind, the group BS(2, 3) is now of particular interest since it is the first unresolved group. Although this remains an open problem, Chapter 4 and Chapter 5 provides some enumeration results for the growth problem for both the horocyclic subgroup and the full group for this unresolved case. A large obstacle with enumeration problems in Baumslag-Solitar groups is that the amount of geodesic length representing a particular element varies dramatically depending on the element chosen. Consider a8 as a word in the presentation a, b | ba2 b−1 a−3 . This word has geodesic length 8 and can be written in four different ways a8 ≡ ba4 b−1 a2 ≡ a2 ba4 b−1 ≡ aba4 b−1 a. This makes the enumeration extremely difficult. However, it raises the following question: In how many ways can an element be represented using words of a fixed length k? This question is trivial if k is strictly less than the geodesic length of the element. Since the geodesic length of an element is generally difficult to find, a starting point for this type of question is to deal with the identity element. That is, for a fixed length k, how many words of length k is equivalent to the identity? This is exactly the question of the 4 cogrowth of the group. Questions about cogrowth are of particular interest because a result of Cohen [5] and Grigorchuk [14] states that the cogrowth of a group is tightly linked to the amenability of that group. A group is said to be amenable if it admits a probability measure on the subsets of that group. The amenability of certain groups are still widely open and at times conflicting results have been published. In 2009, two results (Akhmedov [1], Shavgulidze [20]) were published presenting contradicting results to the amenability of the Thompson’s group F. To this day, this problem still remains unresolved. However, the question of amenability in Baumslag-Solitar groups has be completely resolved and its amenability depends on the choice of n and m. Hence, Baumslag-Solitar groups provide a good starting point to develop numerical tests of amenability by studying the cogrowth of these groups. These estimates of cogrowth can then be applied to other groups for which the amenability is uncertain (such as Thompson’s group). Chapter 6 focuses on developing the results and machinery required to estimate the value of the cogrowth exponent and using this information to develop a test of amenability. As a summary, Chapter 2 provides a brief outline of the standard definitions and results from group theory, graph theory and enumeration that will be required by latter chapters. This chapter also provides an overview of HNN extensions and Brittons Lemma, which will be used extensively throughout the thesis. The reader is invited to skip ahead if they are familiar with the material. Chapter 3 begins to develop the necessary tools to find the geodesic lengths of horocyclic subgroups of Baumslag-Solitar groups. Chapter 4 contains the enumeration of some special cases of Baumslag-Solitar groups using the results obtained from Chapter 3. The main algorithm for finding geodesic lengths using an iterative algorithm and all the required results leading up to it will be the main focus of Chapter 5. Finally, Chapter 6 will provide the results associated with cogrowth and amenability of the group and will use Baumslag-Solitar groups as a test case for amenability. 5 Chapter 2 Preliminaries This chapter covers the standard definitions and some basic results from group theory, graph theory and enumeration that will be used in later chapters. This chapter also provides an overview of HNN extensions in Section 2.2 and Britton’s Lemma, which will be used extensively throughout the thesis. The reader is invited to proceed to Chapter 3 if they are already familiar with this content. 2.1 Group Theory This section will provide an overview of the standard definitions and results from group theory that will be made use of in this thesis. More details and results can be found in Dummit and Foote [9]. Definition 2.1. Let Z denote the set of integers. The set of positive integers is denoted Z+ = {z ∈ Z | z > 0}. For any q ∈ Z+ , the multiples of q are denoted qZ = {z ∈ Z | z = kq for some k ∈ Z}. Definition 2.2. Let A and B be nonempty sets. The set A × B is the set of ordered pairs of A and B. That is A × B = {(a, b) | a ∈ A, b ∈ B}. Definition 2.3. A group (G, ·) is a set G with a binary operation · : G × G → G satisfying the following properties: 1. Associativity: ∀a, b, c ∈ G, (a · b) · c = a · (b · c) = a · b · c; 6 2. Identity: ∃e ∈ G such that ∀g ∈ G, e · g = g · e = g; 3. Inverse: ∀g ∈ G, ∃g−1 ∈ G such that g · g¯ = g−1 · g = e. From here forward, a group (G, ·) will be denoted G when the binary operation is understood and causes no confusion. As a convention, given a group G and an element g ∈ G, the element gg is written with g2 with the natural extension to gg · · · g being written as gk for the appropriate value of k. Similarly, the element g−k is the element representing the inverse of gk . For any group, the identity is unique. Moreover, for any element in a group, the inverse of that element is also unique. Definition 2.4. Let G be a group. If two elements x, y ∈ G satisfies xy = yx, then x and y are said to commute. If every pair of elements in G commute, then G is said to be abelian or commutative. Definition 2.5. Let (G, ·) be a group. A subset H ⊆ G is a subgroup of G if H forms a group with respect to the group operation. This is denoted H ≤ G. This is equivalent to saying that H contains the identity element and for any element in H, the inverse of that element (in G) is also in H. Given a nonempty subset H ⊆ G, the following is necessary and sufficient to check whether H is a subgroup of G. Lemma 2.6. Let G be a group and H ⊆ G with H = 0. / If for all x, y ∈ H, the element xy−1 ∈ H. Then H is a subgroup of G (under the same binary operation). Proof. To show that H ≤ G, it suffices to check that H is a group (according to Definition 2.3). Associativity of H is a direct consequence of the assumption that H ⊆ G. To show e ∈ H, pick x = y ∈ H and by assumption xy−1 = xx−1 = e ∈ H. To show H contains all appropriate inverses, pick x = e and for any y ∈ H, the element xy−1 = y−1 ∈ H. Finally, H is closed since the multiplication of any two elements is also contained in H. Hence H forms a group. Definition 2.7. Let G be a group and S ⊆ G. The subgroup generated by S, denoted S ≤ G, is the smallest subgroup in G containing S. 7 Alternatively, the subgroup generated by S can be expressed as: S = H {H≤G|S⊆H} Definition 2.8. Let G be a group and H ≤ G. For a fixed g ∈ G, the set gH = {gh ∈ G | h ∈ H} is called a left coset of H in G. Definition 2.9. Let G be a group and H ≤ G. The set of left cosets of of H in G is denoted G/H = {gH | g ∈ G} Lemma 2.10. Let G be a group and H ≤ G. The set of left cosets of H in G partitions G. Proof. Clearly, any element g ∈ G is in the coset gH. Thus, assume that there exists g1 , g2 ∈ G such that the cosets g1 H ∩ g2 H = 0. / Then there exists h1 , h2 ∈ H such that g1 h1 = g2 h2 . This implies g1 = g2 h2 h−1 1 and hence g1 ∈ g2 H. Thus g1 H ⊆ g2 H. Since g2 = g1 h1 h−1 2 , g2 H ⊆ g1 H by the same argument. Hence, g1 H = g2 H and the conclusion follows. Definition 2.11. Let H ≤ G be a subgroup of a group G. A subset S ⊆ G is called transversal for the cosets H in G if G= sH s∈S and for all s, s ∈ S with s = s , the cosets sH = s H. Definition 2.12. Let G be a group and u, v ∈ G. The element vuv−1 is called the conjugate of u by v. Two elements u, v ∈ G are said to be conjugates in G if there exists w ∈ G such that u = wvw−1 . Definition 2.13. Let G be a group and N ≤ G. The subgroup N is a normal subgroup of G if for all g ∈ G and n ∈ N, the element gng−1 ∈ N. A normal subgroup N of G is denoted N G. Lemma 2.14. Let G be a group and N G. The set G/N forms a group. 8 Proof. Let g1 N, g2 N ∈ G/N. By Lemma 2.6, it suffices to show that the element g1 N(g2 N)−1 ∈ G/N. First, it needs to be shown that (g2 N)−1 = g−1 2 N. For any fixed g2 ∈ G and any n ∈ N, the element (g2 n)−1 = n−1 g−1 2 . But by normality of N, there exists n ∈ N −1 −1 −1 −1 such that g2 n−1 g−1 2 = n . Hence n g2 = g2 n ∈ g2 N. Since the cosets partition G, the proves the equality. Thus, g1 N(g2 N)−1 = g1 Ng−1 2 N. For any fixed g1 , g2 ∈ G and for any n ∈ N, −1 consider g1 ng−1 2 N. By normality of n, there exist n ∈ N such that g2 ng2 = n . This implies that g1 g−1 2 n N. Finally, since g1 , g2 ∈ G and N ≤ G, there exists g ∈ G such that g1 g−1 2 n N = g N ∈ G/N. Hence G/N ≤ G. Example 2.15. For a fixed positive integer q, the set of integers modulo q, (usually denoted Zq ) can be thought of as the set of remainders when any integer is divided by q. From an algebraic point of view, the set Zq ≡ Z/qZ. That is, Let G = Z with addition as the binary operation and N = qZ. The multiples of q (qZ)form a normal subgroup in Z since for any z ∈ Z, z + qZ + (−z) = qZ. Thus Z/qZ forms a group and it’s elements is of the form z + qZ (I.e. some multiple of q plus some left over z). It is clear that this coincides with the initial understanding of Zq . Definition 2.16. Let G, H be groups. A homomorphism is a function f : G → H such that f (xy) = f (x) f (y) for all x, y ∈ G. A homomorphism between groups is a way of relating the structure and properties of one group to the other. If there exist an homomorphism in the reverse direction, then the groups are said to be isomorphic. Informally, two groups are isomorphic if they are structurally identical. Definition 2.17. Two groups G and H are isomorphic (there exists an isomorphism between them) if there exists a function f : G → H such that both f and f −1 are homomorphisms. If G is isomorphic to H, then it is denoted G ∼ = H. Isomorphisms play a very important role in algebra and group theory. It allows more complicated and abstract groups to be described in terms of simpler and well understood ones. The remainder of this section will aim towards building a way of describing groups using what is known as a presentation for the group. A 9 presentations consists of a set of generators on which words can be built and a set of relations that define the “loops” in the group. That is, they describe the set of words that are equivalent to the identity. Definition 2.18. Let S be a set. A word w on S is a finite sequence of concatenated elements from S. A word w of length n has the form w = s0 s1 . . . sn where si ∈ S for 0 ≤ i ≤ n. The length of a word is denoted l(w) = n. Definition 2.19. Let S be a set. The set S−1 = {s−1 | s ∈ S} where s−1 is the formal inverse of s. Definition 2.20. Let S be an set. The set F(S) is the set of all finite words on S and S−1 . Definition 2.21. A word w ∈ F(S) is said to be freely reduced if it does not contain subsequences of the form ss−1 or s−1 s for any s ∈ S. Informally, a word is freely reduced if it contains no immediate inverse pairs. The process of removing such inverse pairs is referred to as a free reduction. That is, every word is equivalent to a unique freely reduced word by a sequence of free reductions. Lemma 2.22. For any non-empty set S, the set of freely reduced words in F(S) together with the concatenation operation forms a group. Proof. Clearly, the set F(S) is closed under concatenation. That is the concatenation of any two finite words is another finite word. Next, the concatenation of a sequence of words is independent of the order in which concatenation occurs. Hence F(S) is associative. The identity element is the empty word and for −1 −1 −1 any word w = s0 s1 . . . sn , the word w−1 = s−1 n sn−1 . . . s1 s0 is the inverse of w as ww−1 ≡ w−1 w ≡ e. Thus F(s) forms a group. The group F(S) is the called the free group generated by S ∪ S−1 or when S ⊆ G is a subset of a group G, then F(S) is call the free group generated by S since it necessarily contains S−1 . Definition 2.23. Let S be a set and R ⊆ F(S). The group S | R is the group F(S) subject to the conditions that all words x ∈ R are defined to be equivalent to the 10 identity. The set S is the set of generators and the set R is the set of relations (or relators). The following is a standard algebra result relating a group to its presentation. More details can be found in section 6.3 of Dummit and Foote [9]. Theorem 2.24. Let S be a set and G be a group. Further, let φ : S → G be a set map. Then φ can be extended to a unqiue group homomorphism Φ : F(S) → G such that Φ |S = φ . Definition 2.25. Let X,Y be groups and f : X → Y be a homomorphism. The kernel of f , denoted ker( f ) = {x ∈ X | f (x) = eY } where eY denotes the identity element in Y . Definition 2.26. Let G be a group and S ⊆ G. The normal closure of S in G is the smallest normal subgroup N G such that S ⊆ N. Definition 2.27. Let G be a group and S ⊆ G such that S = G. A presentation for G is a pair S | R where R ⊆ F(S) is a set of words such that the normal closure of R equals the kernel of the homomorphism Φ : S → G. Every group G can be expressed in the form S | R for some S and R by Definition 2.27. Similarly, every compatible pair of S and R (by Definition 2.23) defines a group. From here onwards, the notation g ∈ G will be used denote the elements of the group and the notation w ∈ S | R will be used to denote the word in the presentation of the group. In order to avoid any confusion, the following convention will be used. Definition 2.28. Let G be a group and S | R be a presentation of the group. A word in S | R refers to an element F(S) subject to the relations in R. A word w in S | R is said to be equivalent to the element g in G if Φ(w) → g. Definition 2.29. Let u, v ∈ S | R be words in the presentation of G and let Φ be as defined in Theorem 2.24. 1. The words u and v are equivalent, denoted u ≡ v, if Φ(u) = Φ(v). 2. The concatenation of u with v, denoted uv, is the word obtained by adjoining v to the end of u. 11 3. A word u is a subword of v if there exists two words (possibly empty), w, w such that v = wuw . Definition 2.30. Let G be a group with presentation S | R . A word w ∈ S | R is a geodesic word if for all words v ∈ S | R such that w ≡ v, l(w) ≤ l(v). The geodesic length of a word w, denoted γ(w), is the length of a word v such that v ≡ w and v is a geodesic word. If w ∈ S | R is an arbitrary word, a geodesic word for w is denoted Γ(w). That is to say, given a word w in a group presentation, the geodesic length γ(w) is equal to l(Γ(w)). The geodesic length of an arbitrary word can be thought of as the length of the shortest word that represents the same element in G. Thus, for any word w, a trivial bound γ(w) ≤ l(w) is obtained. Lemma 2.31. Let G be a group with presentation S | R . Let g ∈ G and γ(g) denote the geodesic length of g in the presentation. Then γ(g) = γ(g−1 ). Proof. Suppose there exists g ∈ G for which the lemma does not hold. Without loss of generality, suppose that γ(g) < γ(g−1 ). Let Γ(g) be a geodesic word for g. then Γ(g)−1 is a word representing g−1 of length γ(g). This contradicts that assumption that γ(g) < γ(g−1 ). Hence such an element cannot exists and γ(g) = γ(g−1 ) for all g ∈ G. Lemma 2.32. Let G be a group with presentation S | R . If w ∈ S | R is a geodesic word, then for all subwords u in w, the word u is a geodesic word. Proof. Assume there exists a subword u of w such that γ(u) < l(u). Then simply replace u with its geodesic word to obtain a shorter word for w. This contradicts the assumption that w is a geodesic word. 2.2 Baumslag-Solitar Groups and HNN Extensions Baumslag-Solitar groups, which is the main object studied in this thesis, were initially introduced in 1962 by Baumslag and Solitar [2]. This family of groups is a special case of HNN extensions. HNN extensions were initially introduced in 12 1949 in a paper by Higman et al. [15]. Given a group G and two isomorphic subgroups H and K, the main motivation for introducing this extension was to show the existence of a larger group containing G within which H and K are conjugates. Baumslag-Solitar groups, as well as any groups obtained through HNN extensions admit a natural normal form through the use of Britton’s Lemma. Hence it is worth taking an brief look at HNN extensions and the consequences that follows from it. Definition 2.33. Let G be a group with presentation S | R and H, K ≤ G with an isomorphism φ : H → K. The HNN extension of G with associated subgroups H and K via the isomorphism φ : H → K is the group G G φ φ with presentation: = S, b | R, bab−1 = φ (a) ∀a ∈ H . The additional generator b is referred to as the stable letter. Example 2.34. In this thesis, the group that is used to define Baumslag-Solitar groups is G = a . That is, the group G = {. . . a−3 , a−2 , a−1 , 1, a1 , a2 , a3 , . . .} is the group containing all the powers of a generator a. The subgroups H and K are defined to be H = an and K = am for positive integers n and m. The mapping defined by φ (an ) = am is the default isomorphism. Thus, the group G ban b−1 = am φ = a, b | . For any fixed n, m, this group is a Baumslag-Solitar group, denoted BS(n, m). Definition 2.35. A b-expression is a sequence of the form g0 bε0 g1 bε1 g2 bε2 . . . gk−1 bεk−1 gk (2.1) where each gi ∈ G and ε = ±1. The case where no b appears (k = 0) is a valid bexpression. If at least one b or b−1 appears, then the expression is said to ‘involve’ b. Definition 2.36. Let g0 bδ0 g1 bδ1 g2 bδ2 . . . gl−1 bδl−1 gl be a word in G φ along with Equation 2.1. The two words are said to be b-parallel if k = l and εi = δi for all 0 ≤ i ≤ l − 1. Clearly, every word in G φ is equivalent to a b-expression. Thus, all definitions such as subwords and concatenations of b-expressions are well defined. 13 Definition 2.37. Let w ∈ G φ be a word in the group. A pinch (or a b-reduction) in the word w is a subword u of the form u = bhb−1 for h ∈ H or of the form u = b−1 kb for k ∈ K. Subwords u of that form are called reductions because words of the form bhb−1 = φ (h) and b−1 kb = φ −1 (k) and making these replacements reduces the number of b and b−1 by one each. Definition 2.38. A b-expression where there are no possible pinches or reductions is said to be b-reduced. Examples can be constructed to show that there are non-identical b-reduced words that represent the same element in G φ. Hence simply being b-reduced is not a strong enough condition to ensure uniqueness. Let G be a group and H ⊂ G. Recall from Definition 2.11 that a transversal Y for the left (or right) cosets of H is a set Y that contains exactly one representative from each of the left (or right) cosets of H. In this setting of HNN Extension, the condition that the identity is used as the representative of the coset H is enforced. Definition 2.39. Let TH be a transversal for the subgroup H and TK be a transversal for K. A normal form for words in G φ is defined to be: g0 bε0 g1 bε1 g2 bε2 . . . gk−1 bεk−1 gk where if εi = 1, then gi ∈ TK and if εi = −1, then gi ∈ TH . Finally, if gi = e then εi−1 = −εi . The last condition forbids the existence of inverse pairs of b symbols appearing on either side of the trivial representative e. By construction, the set of normal forms are all b-reduced. Now, to show that every b-reduced word can be represented by such a normal form, let w be a b-reduced word of the form described in Equation 2.1. Starting with i = 0 and moving to the right, for each i, if εi = 1, then gi b ≡ gi kb ≡ gi bφ −1 (k) for the unique gi ∈ TK and k ∈ K. Similarly, if εi = −1, then gi b−1 ≡ gi hb−1 ≡ gi b−1 φ (h) for the unique gi ∈ TH and h ∈ H. By construction, the resulting word will be in the set of normal forms. Further, this process does not introduce any additional b-reductions, the normal form is b-parallel to the original b-reduced word. 14 Example 2.40. Consider the group BS(2, 3) with the isomorphism φ : a2 → a3 . Let w = a3 b−1 ab−1 aba6 b−1 be a word in the corresponding presentation. This word can be converted into a normal form as follows. 1. Start by defining the transversal for Ha2 = {e, a} and Ha3 = {e, a, a−1 }. 2. Remove any pinches from w. Thus, w = a3 b−1 ab−1 aba6 b−1 ≡ a3 b−1 ab−1 a10 . 3. Starting at i = 0, rewrite a3 b−1 ≡ ab−1 a3 to get w ≡ ab−1 a4 b−1 a10 . 4. Repeat this process for i = 1, rewrite a4 b−1 ≡ b−1 a6 to get w ≡ ab−2 a16 . Thus, the word w can be converted to its normal form ab−2 a16 . To summarise the above procedure: Lemma 2.41. Let G φ be an HNN extension. Let TH and TK be transversals for H and K respectively. Then for any word w in G φ: 1. The word w is equivalent to a b-expression in G φ; 2. Any b-expression for w can be converted to a b-reduced expression which is equivalent to w in G φ; 3. Any b-reduced expression for w can be converted into a normal form which is b-parallel to the given expression and is equivalent to w in G φ. The following is Britton’s Lemma (Britton [3]). The lemma and its corollary are of particular importance as it will be used extensively to show that the elements in Baumslag-Solitar groups are in one to one correspondence with the normal forms described above. It is also the backbone for a large majority of results related to Baumslag-Solitar groups. Lemma 2.42. (Britton’s Lemma) Let G φ be as defined in Definition 2.33 and w = g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 gi where g j ∈ G and ε j ∈ {1, −1} for all j. If w ≡ e ∈ G φ, then either: 1. i = 0 and g0 = e; or 2. for some j = 1, 2, . . . , n − 1 one of the following holds: 15 (a) ε j−1 = 1, ε j = −1 and g j ∈ H; (b) ε j−1 = −1, ε j = 1 and g j ∈ K. Proof. Consider the contrapositive of the statement, if a word is nontrivial and does not contain any pinches, then it cannot be equivalent to the identity. The previous lemma establishes the existence of a normal form for each word in G φ. Thus, let Ω denote the set of all normal forms. The elements of G form a right action, denoted θ , on the permutation group S(Ω). Let g ∈ G and w ∈ Ω, w · g = (g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 gi ) · g = g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 (gi g). Clearly, θ is a homomorphism from G to S(Ω). Similarly, with b, a permutation ψ(b) is described by: ε0 ε1 εi−1 g0 b g1 b . . . gi−1 b tK bh if εi−1 = 1 (g0 bε0 g1 bε1 . . . gi−1 bεi−1 gi )·b = g0 bε0 g1 bε1 . . . gi−1 bεi−1 tK bh if εi−1 = −1 and tK = 1 g0 bε0 g1 bε1 . . . bεi−2 gi−1 h if εi−1 = −1 and tK = 1 where gi = tK k with tK ∈ TK , k ∈ K and h = φ −1 (k). Similarly, for b−1 , a permutation ψ(b−1 ) can be defined: ε0 ε1 εi−1 −1 g0 b g1 b . . . gi−1 b tH b k if εi−1 = −1 (g0 bε0 g1 bε1 . . . gi−1 bεi−1 gi )·b−1 = g0 bε0 g1 bε1 . . . gi−1 bεi−1 tH b−1 k if εi−1 = 1 and tH = 1 g0 bε0 g1 bε1 . . . bεi−2 gi−1 k if εi−1 = 1 and tH = 1 where gi = tH h with tH ∈ TH , h ∈ H and k = φ (h). It can be checked that ψ(b) ◦ ψ(b−1 ) and ψ(b−1 ) ◦ ψ(b) are both the identity maps. Further, the homomorphisms θ and ψ extend to a homomorphism θ ψ : G b → S(Ω). It can be checked that θ ψ maps relations in G Hence for any non-trivial normal form g0 bε0 g φ to the identity. ε ε ε 1 2 i−1 gi , its action on 1 b g2 b . . . gi−1 b the trivial word (1)(g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 gi ) = g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 gi 16 is not equal to the trivial word in G φ and hence cannot be the identity permutation. This shows that a b-reduced word involving b cannot be the equal to the trivial word in G φ. Corollary 2.43. Let w be as defined in Lemma 2.42. If 1. n = 0 and g0 = e in G, or 2. n ≥ 0 and w does not have a subword of the form bhb−1 for some h ∈ H or a subword of the form b−1 kb for some k ∈ K, then w = e in G φ. Proof. This is contrapositive of Lemma 2.42 Finally, it has to be shown that this normal form is unique. That is, each element in G φ can be unique represented by a normal form. Lemma 2.44. Every element in G φ is equal to a unique expression of the form w = g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 gi where 1. if εi = −1, then gi ∈ TH ; 2. if εi = 1, then gi ∈ TK and 3. if gi = 1, then εi = −εi−1 . Proof. Lemma 2.41 shows the existence of a normal form for each element in G φ. Thus let w and w = g0 bε0 g1 bε1 g2 bε2 . . . gi−1 bεi−1 gi be two normal forms that represent the same element in G φ. Then the word (w )−1 a ≡ e. By Britton’s Lemma, there must exist a pinch somewhere. Since both w and w are b-reduced words, the only possible pinch that could occur is where the two words meet. More explicitly, the pinch occurs over the subword b−ε0 (g0 )−1 g0 bε0 . This implies ε0 = ε0 and by the construction of TH and TK , this shows that g0 = g0 . By removing this pinch and repeating the argument, this shows that w = w and hence uniqueness is shown. 17 2.3 Graph Theory and Matrix Representations This section provides a basic overview of the definitions in graph theory that will be used in later sections. In particular, the Cayley graph of a group will be used to develop an eigenvalue approach to estimate the cogrowth of a group in Chapter 6. Definition 2.45. A graph G = (V, E) is an ordered pair, where the vertex set V is a nonempty set given by V = {v1 , v2 , . . . , vn } and the edge set E is given by E = {e1 , e2 , . . . , em }. Each edge is an unordered set containing two, possibly equal, vertices called its endpoints. The size of a graph, |G|, refers to the size of the vertex set: |G| = |V |. Definition 2.46. If x and y are the endpoints of an edge in a graph, then x and y are said to be adjacent to each other. This is denoted x ∼ y. Similarly, two edges in a graph are adjacent to each other if they share a common endpoint. Definition 2.47. A directed graph or digraph G = (V, E) is an ordered pair, where the vertex set V is a nonempty set given by V = {v1 , v2 , . . . , vn } and the edge set E is given by E = {e1 , e2 , . . . , em }. Each edge consists of an ordered pair of vertices. An edge with tail vertex u going to a head vertex at v is denoted (u, v). The size of a graph, |G|, refers to the size of the vertex set: |G| = |V |. A walk in a graph G from vertex x to vertex y is a sequence of adjacent edges from x to y: {x, x1 }, {x1 , x2 }, . . . {xn−1 , y}, and is often denoted x0 x1 x2 . . . xn−1 xn , where x = x0 and y = xn . The length of the walk is the number of edges transversed. The vertices x and y are called the terminal vertices and all other vertices within the walk are called internal vertices. A path between two vertices x and y in a graph is a walk from vertex x to vertex y in which all internal vertices are unique. A directed path in a directed graph can be defined in an analogous way. Definition 2.48. A directed graph is said to be strongly connected if there exists a directed path between any two vertices. A strongly connected graph is also known as an irreducible graph. Definition 2.49. A strongly connected graph is said to be periodic with parameter d if and only if the vertex set V can be partitioned into V0 ,V1 , . . .Vd−1 in such a way that all edges with their tail in Vi has their head in Vi+1 18 (mod d) . The largest possible d is called the period. If no decomposition exists with d ≥ 2, then the graph is said to be aperiodic. For notation, let A be a matrix. Denote [A]k,l to be the entry in row k and column l in the matrix A. Definition 2.50. Let G = (V, E) be a digraph of finite size and vertices labelled 1, . . . , |V |. The adjacency matrix A is a |V |×|V | matrix such that the entry [A]k,l = 1 if and only if the pair (k, l) ∈ E. An adjacency matrix of a graph G inherits the properties of G, such as aperiodicity and strongly connectedness. A group G and its representation S | R can be encoded into a graph as follows: Definition 2.51. Let G be a group with a presentation S | R . The Cayley graph G = (G, E) is an ordered pair where the vertices are the elements of the group and E is the set of unordered pairs {g1 , g2 } with g1 , g2 ∈ G and there exists s ∈ S ∪ S−1 such that g1 = sg2 . Further, denote g1 ∼ g2 if {g1 , g2 } ∈ E. A Cayley graph is an equivalent representation of a group. A word in the presentation is equivalent to a walk in the Cayley graph. This means the graph theoretic results presented here will play an important role in the later chapters. 2.4 Generating Function and Complex Variables Generating functions are the primary mathematical object used when storing and analysing information about growth and cogrowth of the group. This section will build up towards the final result of showing that the number of paths in a “nice” graph grows independently of its endpoints. Definition 2.52. A combinatorial class A is a finite or countable set with a size function such that: 1. the size of any element is a non-negative integer; 2. the number of element of any given size is finite. 19 Alternatively, a combinatorial class can be defined as a pair (A , | · |) such that A is countable and | · | : A → N such that the inverse image of any non-negative number is finite. If A is a combinatorial class, the size of an element a ∈ A is denoted |a|A or simply |a| when there is no confusion about the class. For a combinatorial class A , the number of elements of size n is denoted An or an . Definition 2.53. Let A be a combinatorial class. The counting sequence of A is the sequence of integers {an }n≥0 . Definition 2.54. The ordinary generating function of a combinatorial class A is the formal power series ∞ A(z) = ∑ an zn . n=0 Definition 2.55. Given a power series f (z) = ∑ fn zn , the coefficient of zn is denoted [zn ] f (z). That is ∞ [zn ] f (z) = [zn ] ∑ f n zn = fn . n=0 An idea that will be used extensively in later chapters is the concept of a multivariable generating function. Definition 2.56. Let { fn,k }n≥0,k≥0 be a sequence of numbers depending on two integer valued indices n and k. The bivariate generating function of such a sequence { fn,k } is defined as: f (z, u) = ∑ fn,k zn uk n,k For a combinatorial class F , the number fn,k is the number of objects φ ∈ F such that |φ |F = n and some other parameter χ(φ ) = k. Thus, as for the single variable case, the variable z is conjugate to the size of the object and the variable u is conjugate to the parameter χ. The following is a summary of the results that will be required in this thesis. More details can be found in Flajolet and Sedgewick [12], which provides a wealth of information and results related to the asymptotic behaviour of generating functions. 20 Theorem 2.57. (Pringsheim’s Theorem)(Flajolet and Sedgewick [12], page 240.) If f (z) is representable at the origin by a series expansion that has non-negative coefficients and radius of convergence R, then the point z = R is a singularity of f (z). Definition 2.58. (Flajolet and Sedgewick [12], page 243.) A number sequence {an }n≥0 is said to be of exponential order K n , denoted an K n , if and only if lim sup |an |1/n = K. This gives and upper and lower bound on the sequence {an }. Given ε > 0, 1. the number |an | exceeds (K − ε)n infinitely often, and 2. the number |an | is dominated by (K + ε)n except for finitely many values of n. Theorem 2.59. (Flajolet and Sedgewick [12], page 240.) If f (z) is analytic at 0 and R is the modulus of a singularity nearest to the origin, then the coefficient fn = [zn ] f (z) satisfies: fn 1 R n . Theorem 2.60. (Flajolet and Sedgewick [12], page 343.) Consider the matrix F(z) = (I − zA)−1 , where A is the adjacency matrix of a digraph G. If A is irreducible, then all entries [F]k,l (z) of F(z) have the same radius of convergence ρ given by ρ = (λ ∗ )−1 where λ ∗ is the largest eigenvalue of A. Further, the point ρ = (λ ∗ )−1 is a pole of each [F]k,l (z). If F is irreducible and aperiodic, then ρ = (λ ∗ )−1 is the unique dominant singularity of each [F]k,l (z) and [zn ][F]k,l (z) = φk,l (λ ∗ )n + O(Λn ), for computable constants φk,l > 0 and 0 ≤ Λ ≤ λ ∗ . This is equivalent to saying that for any k, l in a irreducible and aperiodic graph, the coefficient [zn ][F]k,l (z) λ ∗. Theorem 2.59 states that the coefficients f j grow like µ j (some sub exponential terms) for some constant µ. Theorem 4.9 (page 256) in Flajolet and Sedgewick 21 [12] shows that coefficents of a rational generating function is of the form [z j ] f (z) = f j ∼ Aµ j jθ asymptotically. Indeed, a more general class of generating functions (Theorem 6.1, page 381 Flajolet and Sedgewick [12]) also have coefficients of this asymptotic form. Further, many of the solved cases of Baumslag-Solitar groups have rational generating functions. The ubiquity of this asymptotic form suggests that it is a good starting point for analysing coefficients in settings where the generating function is not well understood. More complicated asymptotic forms do appear and Flajolet and Sedgewick [12] provides more details regarding the validity and accuracy of such forms. The parameter µ is referred to as the growth of the class. Chapter 5 will provide more details about the importance of this parameter. For now, suppose that a sequence { f j } j≥0 is given and the aim is to extract the value of µ. First, consider the ratio S j+1 /Sn against 1/ j. Whilst it is difficult to prove that the ratio converges, it is frequently observed to do so. Thus assuming convergence, S j+1 Aµ j+1 ( j + 1)θ ∼ Sj Aµ j jθ µ 1+ 1 j θ µ 1+ θ +... j which implies that as j → ∞, the ratio will approach µ. A plot of the ratio verses 1 j will be linear and give a y-intecept of µ. Hence this plot can be used to estimate the value of µ. The second approach looks at value log(S j )/ j against log( j)/ j. For sequences statisfying certain conditions, the following is guaranteed to converge by Fekete’s Lemma (Lemma 5.17). log(S j ) log(Aµ j jθ ) log(A) log( j) ∼ ∼ +θ + log(µ). j j j j In this case, as j → ∞, the limit log(A) j → 0 and will give the value log(µ). 22 log( j) j → 0. Hence, the y-intercept Chapter 3 Geodesic Words on Horocycles This chapter investigates Baumslag-Solitar groups and aims to develop the results related to the growth of a horocyclic subgroup within a Baumslag-Solitar group. It builds towards computing geodesic lengths in a horocycle using Theorem 3.19, where it can be done iteratively. The results here will be used in Chapter 4 to enumerate over the geodesic lengths to obtain generating functions for the growth of the group. These results will also be expanded to the entire set of normal forms in Chapter 5 to produce an algorithm that will allow the iteration over all normal forms in the group to a given geodesic length. Definition 3.1. Baumslag-Solitar groups, BS(n, m), is the the family of groups with presentation a, b | ban b−1 = am with n ≥ 1 and m ≥ 1. In the case where n = m, assume n < m without loss of generality. Baumslag-Solitar groups are a special type of HNN extension. It is the group extension of the free group G = a with subgroups H = an and K = an via the isomorphism Φ(an ) = am . Note that the choice of H and K could have been reversed and the same extension would result. Hence BS(n, m) ≡ BS(m, n). Definition 3.2. Two words w, w , are said to be equivalent in BS(n, m) if w(w )−1 ≡ e. That is, two words are equivalent if they represent the same element in BS(n, m). Recall from Definition 2.30 that a word w is a geodesic word for an element of BS(n, m) if the length of the word is the minimal over all words w such that 23 w ≡ w. For Baumslag-Solitar groups, the geodesic word for an element, denoted Γ(w), does not have to be unique. For example, a6 ≡ ba4 b−1 in BS(2, 3) and are both of geodesic length. The following results, leading up to Theorem 3.9, is part of the “folklore” of Baumslag-Solitar groups. It can be found in various forms in Diekert and Laun [8] and Collins et al. [6]. Lemma 3.3. Let q, r ∈ Z, then words of the form u = aq ∈ BS(n, m) commutes with words of the form v = bar b−1 ∈ BS(n, m) if: 1. q ∈ mZ; or 2. r ∈ nZ. Proof. 1. Write q = km for some k ∈ Z. Then uv ≡ bakn+r b−1 ≡ vu. 2. Write r = kn for some k ∈ Z. Then uv ≡ akm+q ≡ vu. The following results deal with a specific subgroup in BS(n, m). Namely, the subgroup of elements aq for q ∈ Z. By Lemma 2.31, the geodesic length γ(aq ) = γ(a−q ). Thus, without loss of generality, assume that q ≥ 0. When it causes minimal ambiguities, the notation l(q), Γ(q) and γ(q) will be used to represent l(aq ), Γ(aq ) and γ(aq ) respectively. This subgroup generated by a is referred to as a horocycle in Baumslag-Solitar groups. Whilst the term ‘horocycle’ takes a more general definition in different fields of mathematics, in the setting of Baumslag-Solitar groups, the definition simply reduces down to the subgroup a . Horocyclic subgroups admit some natural geometry. Figure 3.1 shows a section of a horocycle of the BS(2, 3) and its cosets in the Cayley graph. Whilst this is an infinite lattice, Theorem 3.9 is show that any element in the horocycle can be represented as a geodesic word on this particular infinite sublattice. Multiplying a word by a or a−1 will keep it on the same horocycle and multiplying by b or b−1 will move it up or down a coset. The relation ban b−1 a−m is exactly the smallest loop in the BS(n, m) lattice. This is commonly referred to as a “brick”. A noteworthy observation is that m steps in a coset converts to n steps in the coset above. Hence, it is sometimes advantageous to move up one (or several cosets) when trying to find geodesic words for larger exponents. 24 Figure 3.1: Cosets of horocycles of BS(2,3). Lemma 3.4. For any q ∈ Z and any geodesic word Γ(aq ), there must be exactly the same number of b’s as b−1 ’s. Proof. The word Γ(aq )a−q ≡ e and hence by Britton’s Lemma, it is either trivial or must contain a pinch. If it is not trivial, a pinch can be removed from it and hence reducing the number of b’s and b−1 by one each. This process can be repeated until the trivial word remains. Hence proving the lemma. Lemma 3.5. Let q > 0. If the subwords u = baq1 b−1 or v = b−1 aq2 b appear in any Γ(q), then q1 ∈ nZ and q2 ∈ mZ. Proof. The words aq and a−q are both in BS(n, m) and the word Γ(q)a−q ≡ e. By Lemma 2.42, the word Γ(q)a−q must be trivial after free reductions or at least one of the subwords u = baq1 b−1 or v = b−1 aq2 b must appear in Γ(q) with q1 ∈ nZ and q2 ∈ mZ. Lemma 3.6. Let q > 0. The subword v = b−1 aq2 b does not appear at all in any Γ(q). Proof. Lemma 3.5 states that if the subword does appear in any Γ(q), it must be the case that q2 ∈ mZ. Thus v = b−1 aq2 b = b−1 akm b ≡ akn for some k ∈ Z. But the initial assumption is that n ≤ m, hence l(b−1 akm b) > l(akn ). Contradicting the assumption that Γ(q) is geodesic. A direct consequence of this lemma is that subwords of the form bain b−1 ar ba jn b−1 do not appear at all. Lemma 3.7. If a geodesic word Γ(aq ) involves b, then all the b’s occur on the left of all the b−1 ’s. 25 Proof. Note that is suffices to show that if a subword b−1 vb appears in a geodesic word, then v = ar for some r ∈ Z. Since Lemma 3.5 then states r ∈ mZ and then Lemma 3.6 forbids all such words. Thus, suppose that v = ar , then v must be a word that involves b and hence there exists a strictly smaller subword of v of the form b−1 v b for some v . Now if v = ar for some r ∈ Z, then this lemma is proved. Otherwise, this argument can be repeated (ie, find a subword of v of the form b−1 v b). This argument will terminate when there exists a v(k) that does not involve b and hence is equal to ar . This process is guaranteed to terminate since Γ(aq ) is of finite length. This proves the lemma. Lemma 3.8. If a geodesic word Γ(aq ) contains a subword bub−1 , then it contains a subword bain b−1 . Proof. This proof uses the same argument as the proof of the previous lemma. Assume u = ar , then the word bub−1 must contain a strictly smaller subword bu b−1 . This argument can be repeated until u does not involve b and hence u = ar for some r. Lemma 3.5 then gives the desired result. Theorem 3.9. Let q ∈ Z. A geodesic word Γ(aq ) is of the form: Γ(aq ) = bk ar b−1 ar1 b−1 ar2 b−1 . . . b−1 ark for some r ∈ nZ. Further, the restriction |r j | ≤ m − 1 holds for all j = 0, 1, . . . , k. Proof. The case where Γ(aq ) does not involve b is simply when k = 0 and r = q. If Γ(aq ) involves b, then Lemma 3.6, Lemma 3.7 forbids the existence of any b−1 occurring to the left of any b. Hence all pinches that occur must occur within each other. That is, they must be embedded. Finally, Lemma 3.8 gives that r ∈ nZ. Thus, every geodesic word can be written as: Γ(aq ) = ar−k b . . . ar−2 bar−1 bar b−1 ar1 b−1 ar2 b−1 . . . b−1 ark . Since r ∈ nZ, Lemma 3.3 gives ar−1 bar b−1 ar1 ≡ bar b−1 ar1 +r−1 . For each 2 < i ≤ k, a similar argument holds. If u ≡ as for some s ∈ nZ then Lemma 3.3 can be applied to give ar−i bub−1 ari ≡ bub−1 ari +r−i . Thus, without loss of generality, assume that u is b-reduced. The required condition is a direct result of Britton’s 26 Lemma. The word Γ(aq )a−q ≡ e and the only possible pinch is over bub−1 . Hence u satisfies the conditions of Lemma 3.3. Finally, observe that these these commutations do not increase the length of word and hence they remain geodesic. Thus, the geodesic word Γ(aq ) can be written as the form described in the theorem. Now suppose that there exists r j > m − 1 for j > 0. Then r j = im + r j for some integer i and |r j | < m − 1. The subword ar j−1 b−1 ar j ≡ ar j−1 +in b−1 ar j which is of shorter length. The case for −r j > m − 1 follows identically. In the case where j = 0, the exact same argument works with r in place of r j−1 . This theorem is only a summary of all the previous lemmas. Whilst it does not provide any exact numerical results, it is useful to keep in mind for this chapter. This structural result will play a fundamental role in the proof of Theorem 3.19, where the geodesic length of elements in a horocycle are determined explicitly. From the lattice point of view, any element can be represented as a geodesic word that starts at the identity, goes up k cosets and then slowly makes its way back down to the original horocycle. A schematic for a geodesic word in a horocycle is provided in Figure 3.2. Whilst Lemma 3.6 states that it is never advantageous to search the coset below for geodesic words, Theorem 3.19 will show that knowledge of the current coset can be used to explore the coset below to find geodesic length of words with higher exponents. At this point, it is worth nothing that the subword obtained by truncating the bottom row (i.e. bk−1 ar b−1 ar1 b−1 ar2 b−1 . . . b−1 ark−1 ) is also a geodesic word in the horocycle for a strictly smaller exponent. This suggests that geodesic words of larger exponents can be obtained by building off geodesic words of smaller exponents iteratively. With this is mind, consider the special case where n = m. The geodesic lengths of all words in the horocycle can be easily resolved. Lemma 3.10. Assume n = m, then aq is a geodesic word and γ(q) = q for all q ∈ Z. Proof. To show that aq is a geodesic word and that γ(q) = q, it suffices to show that any geodesic word for aq cannot contain any b or b−1 . Suppose a geodesic word for aq does contain b or b−1 , then by Lemma 3.5 and Lemma 3.6, it must contain a subword of the form baq1 b−1 for some q1 ∈ nZ. However, the group relation gives baq1 b−1 ≡ aq1 with l(baq1 b−1 ) > l(aq1 ). 27 Figure 3.2: Schematic for a geodesic word in a horocycle. Thus, for the remainder of this section, assume that n = m. Further, without loss of generality, assume that n < m. Due to the nature of the group, the geodesic length of smaller exponents behave differently to those of larger exponents. However, it is possible to define exactly where that boundary occurs. This motivates the following definition. Definition 3.11. Let q ∈ N. Define “small values” of q to be S(n, m), where S(n, m) = {q ∈ N | q < 2m} if m − n = 1 {q ∈ N | q < 21 (m + n + 2)} if m − n ≥ 2 Consequently, “large values” of q is defined to be L(n, m) = N\S. For small values of q, the geodesic length becomes quite straight forward. Lemma 3.12. Let n, m ∈ N with n < m. For all q ∈ S(n, m), the geodesic length γ(q) = q. Proof. This can be seen by an exhaustive search. Clearly, w = aq is a word of the required form and the only way that it can be shortened is to replace some subword using the relation. It can be seen that any such replacement is not favorable for q ∈ S(n, m). 28 Lemma 3.13. Let n, m ∈ N with n < m. For all values q ∈ L(n, m) with q = mi for some i ∈ Z, a geodesic word Γ(q) can be represented as Γ(q) = Γ(mi) ≡ bub−1 for some subword u ≡ ani . Proof. Lemma 3.5 and Lemma 3.6 show that for any geodesic word Γ(mi), the generator b−1 cannot appear before any generator b. Thus, any geodesic word Γ(mi) can be represented as Γ(mi) ≡ ar1 bub−1 ar2 where u is a subword encapsulating all but the leftmost b and the rightmost b−1 . Note that u ≡ akn for some k by Lemma 3.5. By Lemma 3.3, the word w ≡ bub−1 ar1 +r2 . Since bub−1 ≡ ami for some i ∈ Z, it can be concluded that r1 + r2 ∈ mZ. If r1 + r2 = 0, then ar1 +r2 can be replaced with some bu b−1 creating a shorter word, contracting the assumption that Γ(mi) is geodesic. Thus r1 + r2 = 0 and more importantly r1 = r2 = 0 by the minimality of Γ(mi). Hence Γ(q) is of the form as stated in the lemma. Lemma 3.14. Let n, m ∈ N with n < m. For all values q ∈ L(n, m) with q = mi for some i ∈ Z, the minimal length γ(mi) = γ(ni) + 2. Proof. By the definition of a geodesic word and Lemma 3.13, Γ(mi) ≤ l(bub−1 ) ≤ l(b) + Γ(ni) + l(b−1 ). This gives one side of the inequality. To show the reverse inequality, the geodesic Γ(mi) ≡ bub−1 for some u ≡ ani . Hence u ≡ b−1 Γ(mi)b. Thus giving γ(ni) ≤ l(b−1 wb) = γ(mi)−2. The final equality comes from the fact that Γ(mi) is a geodesic word and has the form described in Lemma 3.13. Hence γ(ni) ≤ γ(mi) − 2, or γ(mi) ≥ γ(ni) + 2, as required. Lemma 3.15. Let w be an arbitrary word in a presentation S | R and g be a generator in S ∪ S−1 . Then |γ(w) − γ(wg)| ≤ 1. Proof. Suppose without loss of generality that γ(w) − γ(wg) > 1, then Γ(wg)g−1 is a word for w of length strictly shorter than γ(w). This contradicts the definition of γ(w). The exact argument follows to show that γ(wg) − γ(w) > 1 also leads to a contradiction. By applying the above lemma to a horocyclic subgroup, the following corollary is obtained. Corollary 3.16. For any q, r ∈ Z, the inequality |γ(q) − γ(q + r)| ≤ r 29 Proof. This is the result of the previous lemma applied r times to a horocyclic subgroup. Lemma 3.17. Let w be an arbitrary word in a, b | ban b−1 = am not equivalent to the identity and S be the set of generators. Then γ(w) = 1 + min g∈(S∪S−1 ) γ(wg). Proof. Let w be an arbitrary word not equivalent to the identity. The word w is a word of finite length and hence must have a finite geodesic length. Thus, the geodesic word can be written as Γ(w) = w1 w2 . . . wk , where k = γ(w). By Lemma 2.32, the subword w(wk )−1 is also geodesic and of length γ(w) − 1. Hence, pick g = (wk )−1 to show that γ(w) = 1 + γ(wg). Lemma 3.15 shows that a lower value cannot be achieved. Lemma 3.18. Let n, m ∈ N with n < m. For all values q ∈ L(n, m), write q = im + r with 0 ≤ r < m. Then: γ(q) = 2 + min{γ(n(i + 1)) + (m − r), γ(ni) + r} Proof. First consider the case r = 0. It must be shown that γ(im) = 2+min{γ(n(i+ 1)) + m, γ(ni)}. By Corollary 3.16, the difference |γ(in) − γ(in + n)| ≤ n < m. Thus, it suffices to show that for r = 0 that γ(im) = 2 + γ(ni), but this is exactly Lemma 3.14. Now consider the case when r = 0. The word aq can be rewritten as aq ≡ bain b−1 ar or aq ≡ ba(i+1)n b−1 a−(m−r) . Hence γ(q) ≤ γ((i + 1)n) + γ(−r) and γ(q) ≤ γ(in) + γ(m − r). Thus, this provides an upper bound for the geodesic length γ(q) ≤ 2 + min{γ(n(i + 1)) + (m − r), γ(ni) + r}. To show that a better value cannot be achieved, it suffices to show that any geodesic for aq is in the form of bub−1 ar or bu b−1 a−(m−r) for some subword u. But Theorem 3.9 provides the exact result needed. Further, the word Γ(aq )a−q ≡ e and hence by Britton’s Lemma, the word u is exactly equivalent to ain in the first case or the word u is exactly equivalent to a(i+1)n in the second. Hence, pick u ≡ Γ(ain ) or u ≡ Γ(a(i+1)n ) as appropriate. This proves the lemma. 30 Figure 3.3: Exploration of the coset below. Theorem 3.19. Let n, m ∈ N and q ∈ Z. If n = m then γ(q) = q. When n < m, q γ(q) = 2 + min {γ(n(i + 1)) + (m − r), γ(ni) + r} if q ∈ S(n, m) if q ∈ L(n, m) Proof. This theorem is a summary of Lemma 3.12, Lemma 3.14 and Lemma 3.18. Figure 3.3 provides a diagrammatic explanation of Theorem 3.19. The knowledge of geodesic lengths of ain and ain+n can be used to to find the geodesic lengths of aim and aim+m in the coset below. The values between im and im + m can then be found by considering both paths back to the identity. This gives an iterative method of finding geodesic length of words with high exponents. Example 3.20. Consider the group BS(2, 3). The set S(2, 3) = {1, 2, . . . , 8} and for all q ∈ S(2, 3), the geodesic length γ(q) = q. An example of a geodesic word for each q would simply be aq . For the next few values of q, apply Theorem 3.19. 31 γ(9) = 2 + min{γ(6), γ(8) + 3} = 8 γ(10) = 2 + min{γ(6) + 1, γ(8) + 2} = 9 γ(11) = 2 + min{γ(6) + 2, γ(8) + 1} = 10 γ(12) = 2 + min{γ(8), γ(10) + 3} = 10 γ(13) = 2 + min{γ(8) + 1, γ(10) + 2} = 11 γ(14) = 2 + min{γ(8) + 2, γ(10) + 1} = 12 γ(15) = 2 + min{γ(10), γ(12) + 3} = 11 γ(16) = 2 + min{γ(10) + 1, γ(12) + 2} = 12 As a more involved example, consider the exponent q = 31. Theorem 3.19 states that γ(31) = 2 + min{1 + γ(20), 2 + γ(22)}. But γ(20) = 2 + min{2 + γ(12), 1 + γ(14)} and by a similar logic, γ(22) = 2 + min{1 + γ(14), 2 + γ(16)}. Thus, combining all the minimum functions, γ(31) = 4 + min {1 + min{2 + γ(12), 1 + γ(14)}, 2 + min{1 + γ(14), 2 + γ(16)}} = 4 + min {3 + γ(12), 2 + γ(14)}, 3 + γ(14), 4 + γ(16)} . By looking up the table of values that was obtained previously, it can be deduced that γ(31) = 17. A geodesic word could be a31 ≡ b3 a8 b−2 a2 b−1 a. In this example, the minimum functions could be embedded within each other and resolved. However, in an iterative algorithm, the values of γ(20) and γ(22) will be known before the γ(31) is resolved. Hence, only a single minimum function and two look ups are necessary in any case. For completeness, the values γ(20) = 14 and γ(22) = 15 and a geodesic word for a22 is shown in Figure 3.4. 32 Figure 3.4: A geodesic word for a22 in BS(2, 3). 33 Chapter 4 Horocycle Enumeration Given a Baumslag-Solitar group BS(n, m), Theorem 3.19 gives a method to obtain the geodesic length for any element with normal form aq for some q ∈ Z. This chapter will build upon this and deal with the question: how many elements are there of a certain geodesic length for a particular Baumslag-Solitar group. In particular, this chapter will validate some previously known results for some special cases for particular values of n and m by producing function equations that is satisfied by the generating functions for the growth of these horocyclic subgroups. In the cases where those functional equations can be solved, the generating functions for the growth of the horocycles will be written down explicitly. The results in Section 4.1, Section 4.2 and Section 4.3 reproduce the work done by Freden et al. [13]. For the case of BS(2, 3), Freden et al. [13] provides an automata to compute the growth series whilst Section 4.4 provides a functional equation satisfied by the growth series, which has not be published before. + (z,t) be the positive bivariate generating function where z Definition 4.1. Let Hn,m is conjugate the geodesic length of aq in BS(n, m) with q > 0 and t is conjugate to q. That is, + Hn,m (z,t) = ∞ ∑ zγ(q)t q q=1 The subscript n, m will often be omitted when it causes minimal ambiguities. 34 Since γ(q) = γ(−q), the full bivariate generating function can be obtained by H(z,t) = 1 + H + (z,t) + H + (z,t −1 ). This bivariate generating function counts both the exponent of the generator ‘a’ and the geodesic of that exponent. However, it is the generating function that counts the geodesic length of the exponents, H(z, 1), that is of interest. I.e. by “forgetting” the contributions from t. First consider the case where n = m. Lemma 3.10 provides a complete description of what the geodesic lengths are. That is, for all q ∈ Z, the geodesic length γ(q) = |q|. Hence: + Hn,n (z,t) = ∞ zt ∑ zqt q = 1 − zt q=1 Unfortunately, the remaining cases will not be so trivial. This chapter will be divided into four sections. The first two will deal with the case for n = 1. This is a very special condition, since it allows the minimum function stated in Theorem 3.19 to be directly evaluated in all the case where m is odd and in all but one case when m is even. The third section deals with the case where n divides m. This case proves to be more difficult than the previous two. But the same techniques can be applied to it and the generating function can be found. The final section deals with the case n = 2 and m = 3. This case proves to be extremely difficult. Whilst techniques from previous sections can be applied, the resulting functional equation cannot be solved in any obvious way to obtain the generating function. This chapter will conclude by providing a modified brute force algorithm to enumerate the size of sphere of the horocycle for BS(2, 3) to any fixed order, subject to time and memory constraints. Recall that every element can be represented as a geodesic word of the form bub−1 ar for some geodesic word u and r ∈ Z. Further, the geodesic word u ≡ aq for some q ∈ Z. This is equivalent to saying the word described in Figure 3.2 contains words of smaller exponent in the horocycle. These words can be found by simply truncated the bottom rows of the figure. One natural question that arises is whether this process can be reversed? This idea will be central in many of the proofs in this chapter. Suppose a geodesic word equivalent to aq is known, can this 35 knowledge be used to expand to the coset below to find geodesic words of larger exponent in the horocycles? In all the cases studied, the answer is yes. However, there certain situations where finding the geodesic length of exponents in the coset below required exploration of the geodesic length of exponents of the current coset as well as that of one or more of the cosets below the current one. The majority of the proofs in this chapter will involve resolving the minimum function from Theorem 3.19. This will be done by considering the minimum function over a larger modulus (i.e. exploring the coset below). This process is repeated until a suitable modulus is found for which all minimum functions can be resolved. For the special case n = 1, it is worth noting that |γ(mq) − γ(m(q + 1))| ≤ 1 since |γ(q) − γ(q + 1)| ≤ 1. 4.1 Special Case: n = 1 and m odd For this section, assume that m = 2p + 1 for some p ≥ 1 and q = ms ± r for some s ∈ Z with 0 ≤ r ≤ p. Lemma 4.2. Let aq be a word of the group BS(1, m). Then, for s ≥ 2, the geodesic length γ(q) = γ(s) + r + 2. Proof. By Theorem 3.19, the geodesic length γ(q) = γ(ms ± r) = 2 + min{γ((s ± 1)) + (m − r), γ(s) + r} . since n = 1, it can be seen that |γ(ms) − γ(m(s ± 1))| ≤ 1. It will always be the case that γ((s ± 1)) + (m − r) ≥ γ(s) + r. The geodesic length of amq−p , amq−p+1 , . . . , amq+p−1 , amq+p are all determined by the geodesic length of aq . That is, the set of all the elements one layer below aq that contains Γ(aq ) as a subword can be found explicitly for each q. For this case where m is odd, these sets (Figure 4.1) partitions nicely for each q. This can be used to determine the contribution of these elements to the generating function iteratively. In particular, this gives the following mapping for each −p ≤ r ≤ p, zγ(q)t q → zγ(mq+r)t mq+r = zγ(q)t mq z|r|+2t i . 36 Figure 4.1: Set of exponents that contains Γ(aq ) as a subword. Thus, for a fixed value of q, sum over all appropriate values of r to obtain p zγ(q)t q → ∑ zγ(mp+r)t mp+r . r=−p The value of all summands can be determined exactly. Hence p z2 + ∑ zr+2 t r + t −r zγ(q)t q → zγ(q)t mq . r=1 Recall, Definition 3.11 determines the small values of q. The above mapping will hold for all values q ≥ 2. Thus, by summing the above equation for all q ≥ 2, ∞ ∑z q=2 p ∞ γ(q) q t → ∑ z γ(q) mq t q=2 z + ∑ zi+2 t i + t −i 2 . i=1 In terms of H + (z,t), this is equivalent to p H + (z,t) − zt → H + (z,t m ) − zt m z2 + ∑ zi+2 t i + t −i , i=1 which holds for all q ≥ 2m − p. Thus to obtain the full bivariate generating function, simply add in the correct values for small q’s. That is, ∑2m−p−1 zγ( j)t j . j=0 Combining these pieces of information, the following is obtained. 37 p H + (z,t) − zt = H + (z,t m ) − zt m z2 + ∑ zi+2 t i + t −i i=1 m−p+1 + ∑ p−1 z j t j + z3t 2p+1 + j=1 ∑ z3+ j t 2p+1+ j + t 2p+1− j + z3+pt 3p+1 . j=1 By rearranging the equation and resolving the summations, the generating function H + (z, 1) for the general case can be obtained. Theorem 4.3. In the case where n = 1 and m = 2p + 1 for some integer p, the generating function for the group of the horocyclic subgroup is given by: + H1,2p+1 (z, 1) = z+ z p+2 −z2 z−1 3 p (z −z) + z3 + 2z z−1 + z3+p p+3 3) 1 − z2 + 2(z z−1−z , which can be further simplified to give: + H1,2p+1 (z, 1) = z + z p+4 − z p+2 − z p+3 1 − (z + z3 + z2 − 2z p+3 ) The following example gives the generating function for horocyles for the first few values of p. Example 4.4. By setting t = 1, the generating function of the growth series for the subgroup {aq } is obtained. The generating function for the growth series for the first few values of p are as follows. + H1,3 (z, 1) = z + + H1,5 (z, 1) = z + z2 1 + z + z2 z 1 + z − z3 = 1 − z2 (1 + 2z) 1 − z2 − 2z3 z2 1 + 2z + 2z2 + z3 z 1 + z2 − z3 = 1 − z2 (1 + 2z + 2z2 ) 1 − z − 2z3 2 + H1,7 (z, 1) = z + z2 1 + z + z2 z 1 + z + z2 + z3 − z5 = 1 − z2 (1 + 2z + 2z2 + 2z3 ) (z2 + 1)(1 − 2z2 − 2z3 ) 38 + H1,9 (z, 1) = z + 4.2 z2 1 + z + z2 (1 + z) 1 + z2 z(1 + z2 + z4 − z5 ) = 1 − z2 (1 + 2z + 2z2 + 2z3 + 2z4 ) 1 − z − 2z3 − 2z5 Special Case: n = 1 and m even For this section, assume that m = 2p for some p ≥ 1, q = ms ± r for some s ∈ Z and r ≤ p. As an initial example to motivate this section, consider the group BS(1, 6). Example 4.5. Consider the group BS(1, 6). For every q ∈ Z, express q = 6s ± r for some r ≤ 3. In the case where r = 3, express q = 6s + 3 for some s ∈ Z. Then for large enough values of s, γ(6s) = 2 + γ(s) γ(6s ± 1) = 3 + γ(s) γ(6s ± 2) = 4 + γ(s) γ(6s + 3) = 5 + min{γ(s), γ(s + 1)} To resolve the min function, consider 6s + 3 as an element modulo 36. That is, every q = 6s + 3 = 36k ± r, where r ∈ {3, 9, 15}. Thus γ(36k ± 3) = 3 + min{γ(36k), γ(36k ± 6)} = 5 + min{γ(6k), γ(6k ± 1)} = 5 + min{2 + γ(k), 3 + γ(k)} and hence γ(36k ± 3) = 7 + γ(k). By a similar logic, γ(36k ± 9) = 3 + min{γ(36k ± 6), γ(36k ± 12)} = 5 + min{γ(6k ± 1), γ(6k ± 2)} = 5 + min{3 + γ(k), 4 + γ(k)} 39 and γ(36k ± 9) = 8 + γ(k). Finally, to resolve γ(36k ± 15), γ(36k ± 15) = 3 + min{γ(36k ± 12), γ(36k ± 18)} = 5 + min{γ(6k ± 2), γ(6k ± 3)} = 5 + min {4 + γ(k), 3 + min{γ(6k), γ(6(k + 1))}} = 8 + min{1 + γ(k), γ(6k), γ(6(k + 1))} = 9 + min{γ(k), 1 + γ(k), 1 + γ(k + 1)} Since the difference between γ(k) and γ(k + 1) is at most one, the geodesic length γ(36k ± 15) = 9 + γ(k). The above example shows that for almost all the cases, the minimum function can be explicitly resolved. In the remaining case, the modulus was increased and the minimum functions of the resulting cases can be resolved as well. This is almost identical to the case in the previous section. The unresolved minimum function for the case 6s + 3 can be resolved by looking at the coset below. Figure 4.2 illustrates that if a certain residue cannot be resolved explicitly, consider that residue modulo a higher modulus. This process is described in more details below. Figure 4.2: Exploring multiple cosets of BS(1, 6). 40 Lemma 4.6. Let aq be a word of the group BS(1, m), with 0 ≤ r ≤ p − 1. Then, for large enough values of q, the geodesic length γ(q) = γ(s) + r + 2. For the case when r = p, then γ(q) = 2 + p + min{γ(s), γ(s + 1)}. Proof. The proof is identical to the the proof of Lemma 4.2 except for the case where r = p. In this case, the minimum function of Theorem 3.19 is remains unresolved. Similar to the odd case, the geodesic length of any large fixed q determines the geodesic length of mq − p + 1, mq − p + 2, . . . , mq + p − 2, mq + p − 1. At the level of generating functions, this is equivalent to saying p zγ(q)t q → ∑ zγ(mp+i)t mp+i . i=−p The same approach accounts for all values of q except for the case where q ≡ p (mod m). For that particular case, consider those values of q (mod m2 ) ≡ ±p, ±3p, . . . , ±(2p − 1)p. First, consider the positive case of q (mod m2 ) > 0. The negative case works identically. Suppose that q = km2 + (2 j + 1)p for some 0 ≤ j ≤ p − 1 and k ∈ Z, then applying Theorem 3.19 gives γ(q) = 2 + p + min{γ(2p(2kp + j)), γ(2p(2kp + j − 1))} = 4 + p + min{γ(2kp + j), γ(2kp + j + 1)} As with the example, this minimum function can be resolved when j = p − 1. This is due to the fact γ(2kp + j) = γ(2pk) + j for all j = p − 1. Hence, γ(2kp + j) < γ(2kp + j + 1) and the geodesic length γ(q) = 4 + p + γ(2kp + j) = 6 + p + j + γ(k) is obtained. In the remaining case where j = p − 1, 41 γ(q) = 4 + p + min{γ(2kp + p − 1), γ((2k + 1)p)} = 6 + p + min{p − 1 + γ(k), p + γ(k), p + γ(k + 1)} = 6 + p + min{p − 1 + γ(k), p + γ(k + 1)} = 6 + 2p − 1 + min{γ(k), 1 + γ(k + 1)} = 6 + 2p − 1 + γ(k) The final line of the equality coming from that fact that |γ(k) − γ(k + 1)| ≤ 1. Thus, to summarise: Lemma 4.7. Suppose for a sufficiently large value k ∈ Z, the geodesic length of γ(k) in BS(1, 2p) is known. Then the following geodesic lengths can be found: if q = mk ± r, for 0 ≤ r < p 2 + r + γ(k) γ(q) = 6 + p + j + γ(k) if q = m2 k ± (2 j + 1)p, for 0 ≤ j ≤ p − 1 Thus each known geodesic length of k determines the geodesic length of mk ±r for 0 ≤ r < p, and q = m2 k ± (2 j + 1)p for 0 ≤ j ≤ p − 1. This is analogous to the case when m is odd. At the level of generating functions, this is equivalent to: p−1 zγ(k)t k → p−1 z2+|r|+γ(k)t mk+r + ∑ r=−(p−1) 2 +(2 j+1)p z6+p+| j|+γ(k)t km ∑ . j=−(p−1) Rearranging, this becomes p−1 γ(k) k z t γ(k) mk → z t 2 z + ∑ z2+r t −r + t r r=0 +zγ(k)t m 2k p−1 ∑ z6+p+ j t (2 j+1)p + t −(2 j+1)p . j=1 By the same argument as the previous section, this functional equation holds 42 for k ≥ 2. Hence, p−1 + H1,m (z,t) − zt → + H1,m (z,t m ) − zt z2 + ∑ z2+r t −r + t r r=0 2 + + H1,m z,t m 2 − zt m p−1 ∑ z6+p+ j t (2 j+1)p + t −(2 j+1)p . j=1 To obtain the full bivariate generating function for the growth series, the correction factors must be added for small values of k that are not satisfied by the function equation. + Theorem 4.8. The bivariate generating function H1,2p (z,t) satisfies the functional equation p−1 + H1,2p (z,t) − zt = + H1,2p (z,t 2p ) − zt 2 z + ∑ z2+r t −r + t r r=0 2 + + H1,2p z,t (2p) p−1 − zt ∑ z6+p+ j t (2 j+1)p + t −(2 j+1)p . j=1 with the correction factor ∑ j∈J zγ( j)t j , where J = {1, 2, . . . , 3p}∪{p, 3p, 5p, . . . , (6p− 1)p} for small values of q. As the above results show, the bivariate generating function for the even case is somewhat more complicated than the odd case. This additional complexity is due to the addition work required to resolve the minimum function. As for the previous case, the generating function H + (z, 1) is of particular interest. The following example is a continuation of the Example 4.5 and will apply to above theory to the case n = 1 and m = 6. Although the exact same process will work for any m = 2p. Example 4.9. Combining all the results from Example 4.5, it can be seen that each zγ(k)t k in the generating function is mapped to the following, zγ(k)t k → z2+γ(k)t 6k + z3+γ(k)t 6k t + t −1 + z4+γ(k)t 6k t 2 + t −2 +z7+γ(k)t 36k t 3 + t −3 + z8+γ(k)t 36k t 9 + t −9 + z9+γ(k)t 36k t 15 + t −15 . 43 By factoring, it can be seen that zγ(k)t k → zγ(k)t 6k z2 1 + z t + t −1 + z2 t 2 + t −2 + zγ(k)t 36k z7 t 3 + t −3 + z8 t 9 + t −9 + z9 t 15 + t −15 . Since, this holds for all k ≥ 2, simply sum both sides. + H1,6 (z,t) − zt → + H1,6 (z,t 6 ) − zt 6 z2 + z3 t + t −1 + z4 t 2 + t −2 z7 t 3 + t −3 + z8 t 9 + t −9 + z9 t 15 + t −15 + (z,t 36 ) − zt 36 + H1,6 The full generating function can be obtained by adding back in the small terms k = 1. that is, q = 1, . . . 9, 15, 21, 27, 33, 39, 45, 51. By defining the correction term to be C(z,t) = z2t 2 + z3 t 3 + t 6 + z4 t 4 + t 5 + t 7 + z5t 8 + z6t 9 + z7t 15 + z8 t 21 + t 33 + t 39 + z9 t 27 + t 45 + z10t 51 , the full generating function for the horocycle of BS(1, 6) satisfies, + + H1,6 (z,t) − zt = C(z,t) + H1,6 (z,t 6 ) − zt 6 + + H1,6 (z,t 36 ) − zt 36 z2 + z3 t + t −1 + z4 t 2 + t −2 z7 t 3 + t −3 + z8 t 9 + t −9 + z9 t 15 + t −15 Finally, to complete the example, substitute t = 1 and rearrange for H + (z, 1). Thus + H1,6 (z, 1) − z = C(z, 1) 1 − (z2 + 2z3 + 2z4 + 2z7 + 2z8 + 2z9 ) , which simplifies to: + H1,6 (z, 1) = z + z2 + 2z3 + 3z4 + z5 + z6 + z7 + 3z8 + 2z9 + z10 . 1 − (z2 + 2z3 + 2z4 + 2z7 + 2z8 + 2z9 ) 44 . . 4.3 Special Case: n divides m First, note that this one case encapsulates both previous cases. For this section, assume that m = dn for some d ≥ 2. Then |γ(km) − γ((k + 1)m)| = |γ(kn) − γ((k + 1)n)| ≤ n. By Theorem 3.19, for any q = km ± r for 0 ≤ r ≤ m/2, the geodesic γ(q) = min{γ(km) + r, γ((k ± 1)m) + (m − r)}. Hence, the min function can be resolved for q = mk ± r if m − 2r ≥ n. For the cases where m − 2r < n, the idea from the previous section can be exploited to resolve the min functions. That is, by considering the unresolved cases as a residue, modulus of a higher order. This idea will be illustrated in the following example. Consider the group BS(2, 6), Theorem 3.19 implies that γ(6k) = γ(2k) + 2. For the case r = 1, the geodesic length γ(6k ± 1) = min{γ(6k) + 1, γ(6(k ± 1)) + 5}, which can be resolved to give γ(6k ± 1) = γ(2k) + 3. Note that this is consistent with the condition that m − 2r ≥ n. To illustrate that this is a necessary condition for the min function to be resolvable, consider the case r = 2 (I.e. m − 2r = n). The geodesic γ(6k ± 2) = min{γ(6k) + 2, γ(6(k ± 1)) + 4} = min{γ(2k) + 4, γ(2(k ± 1)) + 6} = 4 + min{γ(2k), γ(2(k ± 1)) + 2} = 4 + γ(2k). For the case r = 3, where m − 2r < n, γ(6k + 3) = min{γ(6k) + 3, γ(6(k + 1)) + 3} = min{γ(2k) + 5, γ(2(k + 1)) + 5} = 5 + min{γ(2k), γ(2(k + 1))}, which is unresolvable. However, Lemma 4.10. Let k ∈ Z. The geodesic length γ(6k + 3) = 4 + γ(2k + 1). Proof. The above calculation shows that γ(6k + 3) = 5 + min{γ(2k), γ(2(k + 1))}. Hence it suffice to show that γ(2k + 1) = 1 + min{γ(2k), γ(2(k + 1))}. To see 45 this, write the integers 2k + 1 as 6 j ± 1 or 6 j + 3 for some j ∈ Z. For the case 2k + 1 = 6 j + 1, the geodesic γ(2k + 1) = γ(6 j + 1) = 1 + γ(6 j) = 1 + γ(2k) from a previous calculation. By noting that γ(2(k + 1)) = γ(6 j + 2) = 2 + γ(6 j) > γ(6 j) > γ(2k), this gives the desired result for the case where 2k + 1 = 2 j + 1. The case where 2k + 1 = 6 j − 1 for some j proceeds similar with the observation that γ(2k + 1) = γ(6 j − 1) = 1 + γ(6 j) = 1 + γ(2(k + 1)) and that γ(2k) = γ(6 j − 2) = 2 + γ(6 j) > γ(6 j) > γ(2(k + 1)), which also gives the desired result. The final case where 2k + 1 = 6 j + 3 for some j ∈ Z can be resolved in a similar way. First, note that γ(6 j + 2) = 2 + γ(6 j) and γ(6 j + 4) = 2 + γ(6( j + 1)). By a previous calculation, γ(6 j + 3) = 46 3 + min{γ(6 j), γ(6( j + 1))}. This can be rewritten as: γ(2k + 1) = γ(6 j + 3) = 3 + min{γ(6 j), γ(6( j + 1))} = 1 + min{2 + γ(6 j), 2 + γ(6( j + 1))} = 1 + min{γ(6 j + 2), γ(6 j + 4)} = 1 + min{γ(2k), γ(2(k + 1))}, which is in the desired form. Hence the geodesic length γ(2k +1) = 1+min{γ(2k), γ(2(k + 1))} and the lemma holds. The techniques from the previous sections can be applied. At the level of generating functions, the following is obtained zγ(2k)t 2k → z2+γ(2k)t 6k + z4+γ(2k)t 6k (t 2 + t −2 ) zγ(2k)t 2k → z3+γ(2k)t 6k (t + t −1 ) zγ(2k+1)t 2k+1 → z4+γ(2k+1)t 6k+3 This motivates the definitions Ho (z,t) = ∑k≥0 zγ(2k+1)t 2k+1 and He (z,t) = ∑k≥1 zγ(2k)t 2k . The function Ho (z,t) is the generating function for odd exponents and He (z,t) is the generating function for the even exponents. Using these, the above can be rewritten as: He (z,t) = A(z,t) + z2 + z4 (t 2 + t −2 ) He (z,t 3 ) Ho (z,t) = B(z,t) + z3 (t + t −1 )He (z,t) + z4 Ho (z,t 3 ), where the functions A(z,t) and B(z,t) are the correction terms for small values. By making the substitution t = 1, this system of functional equations can be rearranged and He (z, 1) can be solved to give: He (z, 1) = A(z, 1) 1 − (z2 + 2z4 ) 47 and using that Ho (z, 1) can be solved to give, Ho (z, 1) = B(z, 1)(1 − z2 − 2z4 ) + 2z3 A(z, 1) 1 − (z2 + 3z4 ) + z6 + 2z8 The correction terms for small values can be computed either by hand or via the use of a computation software. The resulting correction terms are as follows. A(z, 1) = 1 − z4 − z6 B(z, 1) = z − z3 − z5 . + Finally, by combining all the information and the observation that H2,6 (z, 1) = Ho (z, 1) + He (z, 1), the full generating function for a horocycle can be obtained. + H2,6 (z, 1) = 1 + z − 2z4 − 2z5 − z6 + z7 + z8 + z10 (z − 1)(z + 1)(2z2 − 1)(z2 + 1)2 After simplification, this becomes: Theorem 4.11. The generating function for the growth of the horocycle in BS(2, 6) is given by + H2,6 (z, 1) = 1 − z8 − 2z6 − z5 − z4 + z3 + z2 + z . (1 − 2z2 )(z2 + 1)2 The ideas in this section can be generalised to any n, m where n divides m. That is, consider partitioning the generating function as follows. Definition 4.12. Let q, r ∈ Z, the function Fr mod q (z,t) is defined to be Fr mod q (z,t) = ∑ zγ(qk+r)t qk+r k≥0 except for the case when r = 0, where the summation is taken over k ≥ 1. The functions Fr mod n (z, 1) for 0 ≤ r ≤ n − 1 forms a set of linear functional equations which can then be solved and correction terms for each can be manually computed or found with the aid of a computer. All such functions Fr mod q (z, 1) can be combined to form the complete generating function for the growth of the horocycle. 48 4.4 Special Case: n = 2 and m = 3 This is the smallest unresolved case. That is, the smallest case where n = 1 and n does not divide m. By Theorem 3.19, for all k ∈ Z, the geodesic length γ(3k) = γ(2k) + 2, γ(3k ± 1) = min{3 + γ(2k), 4 + γ(2k ± 2)}. Since the min function cannot be resolved, the ideas from Section 4.2 are applied. The residues ±1 (mod 3) are equivalent to ±1, ±2, ±4 (mod 9). Lemma 4.13. The following equalities hold. 1. The geodesic length γ(9k ± 1) = 5 + γ(4k) = 3 + γ(6k), 2. the geodesic length γ(9k ± 4) = 3 + γ(6k ± 2). Proof. 1. By applying Theorem 3.19, and the fact that |γ(q) − γ(q + r)| ≤ r for all q, r ∈ Z, γ(9k ± 1) = min{1 + γ(9k), 2 + γ(9k ± 3)} = min{3 + γ(6k), 4 + γ(6k ± 2)} = min{5 + γ(4k), 5 + γ(6k ± 3), 6 + γ(6k)} = min{5 + γ(4k), 7 + γ(4k ± 2)} = 5 + γ(4k) 2. By comparing the LHS and RHS, a similar argument holds for the case 9k ± 4. First, consider the LHS . LHS = γ(9k ± 4) = min{1 + γ(9k ± 3), 2 + γ(9k ± 6)} = min{3 + γ(6k ± 2), 4 + γ(6k ± 4)} = min{5 + γ(6k), 4 + γ(6k ± 3), 5 + γ(6k ± 3), 6 + γ(6k ± 6)} = min{7 + γ(4k), 6 + γ(4k ± 2), 8 + γ(4k ± 4)} = min{7 + γ(4k), 6 + γ(4k ± 2)} 49 Similarly, for the RHS, the geodesic length γ(6k ± 2) = min{2 + γ(6k), 1 + γ(6k ± 3)} = min{4 + γ(4k), 3 + γ(4k ± 2)}. Hence, γ(9k ± 4) = γ(6k ± 2) + 3. A similar method fails for the case of 9k ± 2 as γ(9k ± 2) cannot be rewritten as a function of γ(6k + j) for any j. Thus, two of the three cases for modulus 9 can be rewritten. By increasing the modulus, the same ideas can be applied to the third remaining case. That is, rewrite the integers 9k ± 2 as integers modulo 27. Every integer of the form 9k ± 2 can be written as ±2, ±7, ±11 (mod 27). Lemma 4.14. For k ≥ 1, the following equalities hold: 1. γ(27k ± 2) = 5 + γ(12k ± 1), 2. γ(27k ± 11) = 5 + γ(12k ± 5). Proof. This proof follows by a similar argument to that of the previous lemma. Figure 4.3: Rewritting γ(27k + 11) as γ(12k + 5). Figure 4.3 provides a graphical explanation for these lemmas. There are two equidistant minimal distant words between 27k + 11 and 12k + 5 two layers up. Hence finding the shortest word to a27k+11 reduces down to the task of finding the shortest word to a12k+5 . As with the previous case, this method is unable to rewrite γ(27k ± 7) as a function of γ(12k + j) for any j. Thus, this argument is repeated by considering integers of the form ±7 (mod 27) as intergers ±7, ±20, ±34 (mod 81). Here, it can be seen that all remaining residues are able to be rewritten. 50 Lemma 4.15. For k ≥ 1, the following equalities hold: 1. γ(81k ± 7) = 6 + γ(36k ± 2), 2. γ(81k ± 20) = 6 + γ(36k ± 10), 3. γ(81k ± 34) = 6 + γ(36k ± 16). Proof. This proof is similar to that of the previous two lemmas. Lemma 4.16. For any k ≥ 2, the above lemmas can be summarised at the level of generating functions as the following list of mappings: zγ(2k)t 2k → z2+γ(2k)t 3k , zγ(6k)t 6k → z3+γ(6k)t 9k t + t −1 , zγ(6k+2)t 6k+2 → z3+γ(6k+2)t 9k+4 , zγ(6k−2)t 6k−2 → z3+γ(6k−2)t 9k−4 , zγ(12k+1)t 12k+1 → z5+γ(12k+1)t 27k+2 , zγ(12k−1)t 12k−1 → z5+γ(12k−1)t 27k−2 , zγ(12k+5)t 12k+5 → z5+γ(12k+5)t 27k+11 , zγ(12k−5)t 12k−5 → z5+γ(12k−5)t 27k−11 , zγ(36k+2)t 36k+2 → z6+γ(36k+2)t 81k+7 , zγ(36k−2)t 36k−2 → z6+γ(36k−2)t 81k−7 , zγ(36k+10)t 36k+10 → z6+γ(36k+10)t 81k+20 , zγ(36k−10)t 36k−10 → z6+γ(36k−10)t 81k−20 , zγ(36k+16)t 36k+16 → z6+γ(36k+16)t 81k+34 , zγ(36k−16)t 36k−16 → z6+γ(36k−16)t 81k−34 . By construction, every value q ∈ Z+ is covered by exactly one of the above + maps. Hence, the generating function H2,3 (z,t) can be obtained by summing over 51 all k ≥ 2 for each of the terms on right hand side and then summing over all resulting sums plus some correction terms, denoted C(z,t), for small exponents. Thus + H2,3 (z,t) = C(z,t) + z2 ∑ zγ(2k)t 3k + z3 ∑ zγ(6k)t 9k t + t −1 k≥2 +z 3 +z 5 +z 5 ∑z k≥2 γ(6k+2) 9k+4 t 3 +z k≥2 ∑ zγ(6k−2)t 9k−4 k≥2 γ(12k+1) 27k+2 ∑z t + z5 ∑ zγ(12k−1)t 27k−2 k≥2 k≥2 γ(12k+5) 27k+11 ∑z t 5 +z k≥2 ∑ zγ(12k−5)t 27k−11 k≥2 + z6 ∑ zγ(36k+2)t 81k+7 + z6 ∑ zγ(36k−2)t 81k−7 k≥2 +z 6 +z 6 k≥2 γ(36k+10) 81k+20 ∑z t + z6 ∑ zγ(36k−10)t 81k−20 k≥2 k≥2 γ(36k+16) 81k+34 ∑z t k≥2 6 +z ∑ zγ(36k−16)t 81k−34 k≥2 Further, the correction terms can be either computed by hand or via to aid of a computer software. The correction term C(z,t) is given by C(z,t) =zt + z2t 2 + z3t 3 + z4 (t 4 − t 3 ) + z5t 5 + z7 (t 7 − t 5 ) +z8t 8 − z9t 8 + z10t 11 + z14t 20 + z18t 34 . Recall Definition 4.12 and let H + (z,t) be the as defined in Definition 4.1, then Fr mod p (z,t) can be written as the sum of: Fr mod p (z,t) = 1 ω −r H + (z, ωt) p ω∑ p =1 where the sum is taken over all ω ∈ C for which ω is the appropriate root of 52 + unity. Hence, the generating function H2,3 (z,t) can be rewritten as: z2 z3 F0 mod 2 (z,t 3/2 ) + t + t −1 F0 mod 6 (z,t 3/2 ) 2 6 z3 z3 + tF2 mod 6 (z,t 3/2 ) + t −1 F−2 mod 6 (z,t 3/2 ) 6 6 z5 z5 −1/4 F1 mod 12 (z,t 9/4 ) + t 1/4 F−1 mod 12 (z,t 9/4 ) + t 12 12 5 z z5 + t −1/4 F5 mod 12 (z,t 9/4 ) + t 1/4 F−5 mod 12 (z,t 9/4 ) 12 12 6 6 z z + t 5/2 F2 mod 36 (z,t 9/4 ) + t −5/2 F−2 mod 36 (z,t 9/4 ) 36 36 z6 z6 + t −5/2 F10 mod 36 (z,t 9/4 ) + t 5/2 F−10 mod 36 (z,t 9/4 ) 36 36 6 6 z z + t −2 F16 mod 36 (z,t 9/4 ) + t 2 F−16 mod 36 (z,t 9/4 ) 36 36 + H2,3 (z,t) = C(z,t) + + By further rewriting, this can be expressed in terms of H2,3 (z,t). For conve+ nience, simply denote H2,3 (z,t) as H + (z,t). 53 H + (z,t) = C(z,t) + + + + z3t 6 ∑ z3 t + t −1 z2 H + (z,t 3/2 ) + H + (z, −t 3/2 ) + 2 6 ω −2 H + (z, ωt 3/2 ) + ω 6 =1 5 −1/4 zt 12 z5t −1/4 12 ∑ z3t −1 6 ω −1 H + (z, ωt 9/4 ) + ω 12 =1 ∑ ω −5 H + (z, ωt 9/4 ) + ω 12 =1 ∑ ω 6 =1 z5t 1/4 12 z5t 1/4 12 ∑ H + (z, ωt 3/2 ) ω 6 =1 ω 2 H + (z, ωt 3/2 ) ∑ ωH + (z, ωt 9/4 ) ∑ ω 5 H + (z, ωt 9/4 ) ω 12 =1 ω 12 =1 + z6t −5/2 z6t 5/2 ω −2 H + (z, ωt 9/4 ) + ω 2 H + (z, ωt 9/4 ) ∑ 36 ω 36 =1 36 ω ∑ 36 =1 + z6t −5/2 z6t 5/2 −10 + 9/4 ω H (z, ωt ) + ω 10 H + (z, ωt 9/4 ) ∑ 36 ω∑ 36 36 =1 ω 36 =1 + z6t −2 z6 t 2 ω −16 H + (z, ωt 9/4 ) + ω 16 H + (z, ωt 9/4 ) ∑ 36 ω 36 =1 36 ω ∑ 36 =1 Which becomes, z2 H + (z,t 3/2 ) + H + (z, −t 3/2 ) 2 ω2 z3 1 t + t+ + 2 + H + (z, ωt 3/2 ) ∑ 6 ω 6 =1 t ω t H + (z,t) = C(z,t) + (4.1) + z5 1 1 + t 1/4 ω + 1/4 5 + t 1/4 ω 5 H + (z, ωt 9/4 ) ∑ 1/4 12 ω 12 =1 t ω t ω + z6 t 5/2 ω 2 1 1 + 5/2 + 5/2 10 + t 5/2 ω 10 + 2 16 + t 2 ω 16 H + (z, ωt 9/4 ) ∑ 2 36 ω 36 =1 ω t ω t t ω Since the generating function H + (z, 1) is of particular interest, substitute t = 1 into the above equation and rearrange to factor all terms containing H + (z, 1). 54 1− z2 2z3 z5 z6 − − − 2 3 3 6 z2 + H (z, −1) 2 z3 1 + 2 + 2 + ω 2 H + (z, ω) ∑ 6 ω 6 =1 ω H + (z, 1) = C(z, 1) + ω=1 + z5 1 1 + ω + 5 + ω 5 H + (z, ω) 12 ω ∑ ω ω 12 =1 ω=1 + z6 ∑ 36 ω 36 =1 1 1 1 + ω 2 + 10 + ω 10 + 16 + ω 16 H + (z, ω) 2 ω ω ω ω=1 Unlike the previous section, the solution to this functional equation does not appear to have a nice solution. By substituting t = 1, it can be seen that resulting functional equation contains many roots of unity. Suppose the functional equation H + (z,t) is evaluated at these roots of unity, the terms t 3/2 and t 9/4 will introduce new roots of unity. Since this happens for any primitive root ω, it is not clear that this functional equation can be expressed as the sum over a finite set of roots of unity from which the equation can then be solved. However, the process of developing this functional equation also lead to an algorithm for computing the size of the spheres of a horocycle out to a given radius. Lemma 4.17. For a fixed R ∈ Z+ . The results stated in Lemma 4.16 provides an iterative and deterministic method to calculate the sequence {hr }0≤r≤R where hr = |Sr | with Sr = {zγ(q)t q | γ(q) = r}. Proof. Suppose that for a sufficiently large r ∈ Z, the values h0 , h1 , . . . hr−1 and the corresponding S0 , S1 , . . . Sr−1 are correct. The set Sr can be found using the mappings in Lemma 4.16. In particular the only contributions to Sr comes from the sets Sr−2 , Sr−3 , Sr−5 , Sr−6 . By the first mapping of Lemma 4.16, the elements zr−2t q ∈ Sr−2 contribute to Sr only if q ≡ 0 (mod 2) and for q = 2k, it contributes the element zr t 3k . By considering each of the mapping in turn, the elements of Sr−3 contribute to Sr if the exponent of t is equivalent to 0, ±2 (mod 6). A similar 55 argument follows for the contribution of Sr−5 and Sr−6 to Sr . Hence, the set Sr and the value of hr can be computed for all r up to R. Thus, it is possible to build an automata to compute the terms of H + (z, 1). This algorithm allows building spheres one at a time rather than one integer at a time. The results obtained using this algorithm are correct for each sphere built and is not subjected to the potential of error large integers with small geodesic lengths. Just for completeness, Figure 4.4 shows the algorithm implemented for a horocycle in the group BS(2, 3) up to sphere 116. The chapter studied similar questions to those that have been previously looked at by Freden et al. [13] and the results produced by Freden et al. [13] have been successfully duplicated. Further, a new result is presented using the ideas in this chapter; the function equation (Equation 4.1) satisfied by the generating function for a horocycle in BS(2, 3) is previously unseen. Figure 4.4: Growth of a horocycle in BS(2, 3). 56 Chapter 5 Geodesic Words and Growth Rate The results regarding the horocycles of a Baumslag-Solitar group will be used as a basis to generate the elements of the entire group out to a fixed geodesic length. Using this information, estimates of the growth exponent can be made. One simple method of obtaining these estimates would simply be to iterate over all words up to a fixed length in the generators using a brute force algorithm. However, this is time and memory consuming since it requires storing all previously seen normal forms and their geodesic lengths. This chapter will initially build upon the results obtained in Chapter 3 before concluding with an algorithm that will iterate over prefixes and normal forms which will speed up the time and decrease the amount of memory required. Definition 5.1. Let G = S | R be a group presentation. For n ∈ N, define Sn = {g ∈ G | γ(g) = n}. The set Sn contains all the words of geodesic length n. It is referred to as the sphere of radius n. Definition 5.2. The growth series is defined to be ∞ G(z) = ∑ S jz j. j=0 57 Definition 5.3. The growth rate (or growth exponent) of a presentation µ is defined to be µ = lim (Sk )1/k , k→∞ Through the use of Lemma 2.42, Baumslag-Solitar groups admits natural normal form via the use of transversals. The following results are used to construct an isomorphism between the element g ∈ G and the normal forms in the presentation by defining a standard transversal. This normal form can be partitioned into two parts. The first part (prefix) consists of a sequence of elements from a finite alphabet Σ and the second part (suffix) consists of a power of the generator a. Using this information, it is possible to develop an iterative algorithm that will allow the geodesic lengths of these normal forms to be computed. This information can then be used to estimate the growth rate. Definition 5.4. Let m ∈ Z+ . A full set of residues for Z/mZ is a set M ⊂ Z such that two things hold: 1. ∀z ∈ Z, ∃x ∈ M such that z ≡ x (mod m); 2. ∀x, y ∈ M with x = y. x ≡ y (mod m). Definition 5.5. For m ∈ Z+ , The set M = {x ∈ Z | (−m + 1)/2 ≤ x ≤ m/2 } forms a full set of residues in Z/mZ. Define MM ⊂BS(n, m) be the set of words such that MM = {aq ∈BS(n, m) | q ∈ M}. That is, the set MM forms a transversal in BS(n, m). The above choice of MM will be the default choice for transversals. When there is no confusion, the set MM will simply be written as M . For the purpose of finding geodesic words, shorter words will be preferable over longer words. Lemma 5.6. Given m ∈ Z+ , for all w ∈ M , the geodesic length γ(w) = l(w) (with respect to the group BS(n, m), with n < m). Proof. By construction, for all w = aq ∈ M , q ∈ S(n, m). Hence by Lemma 3.12, the geodesic length γ(w) = l(w). That is to say that all words in the transversal are alway of geodesic length. 58 Definition 5.7. Let n, m ∈ Z+ and N , M be the transversals in BS(n, m). Define Σ(n,m) to be: Σ(n,m) = {Nb−1 | N ∈ N } ∪ {Mb | M ∈ M } Furthermore, let P ∈ Σ∗(n,m) be a word in Σ(n,m) subject to the restriction that ‘b’ does not follow any element from the set {Nb−1 | N ∈ N } and ‘b−1 ’ does not follow any element from the set {Mb | M ∈ M }. Denote P(n, m) ⊂ Σ∗(n,m) to be the set of words P such that the restriction holds. Whilst the sets Σ∗(n,m) and P(n, m) are dependent on n and m, the choice of n and m will be be fixed for any Baumslag-Solitar group and hence will simply be denoted as Σ∗ and P when the group is clear. Example 5.8. Consider the case of BS(4, 7). The set N = {−1, 0, 1, 2} and M = {−3. − 2, −1, 0, 1, 2, 3}. Hence, the transversals are N = {a−1 , 1, a, a2 }, M = {a−3 , a−2 , a−1 , 1, a, a2 , a3 } and the alphabet for the prefix will be Σ(4,7) = {a−1 b−1 , b−1 , ab−1 , a2 b−1 } ∪ {a−3 b, a−2 b, a−1 b, b, ab, a2 b, a3 b}. The set P is the set of prefixes from which a normal form can be constructed for each element in the group BS(n, m). The claim is each word can be expressed as a unique normal form that is an element from P followed by a word of the form aq for some q ∈ Z. That is, every word w is an ordered pair w = (P, aq ) for some P ∈ P and q ∈ Z. Definition 5.9. Define the set W = P × a . For a word w = (P, aq ), the projection of w onto P is P and the projection of w onto a is aq . Further, let P ∈ P and denote WP to be the set of words w ∈ W such that the projection of w onto P is P. Lemma 5.10. For any fixed n, m ∈ Z+ , the set W is a set of normal forms for elements in BS(n, m). That is, there is a every element of BS(n, m) can be uniquely represented as an element in W Proof. By construction, the sets N and M are exactly the transversals needed to define a normal form for words in the presentation a, b | ban b−1 = am as defined in Lemma 2.41. Hence, W is exactly the set of all normal forms. Further, Lemma 2.42 59 shows that these normal forms are unique and W is in one to one correspondence to the elements of the group BS(n, m). The reader is reminded of Definition 2.30 for the meaning of γ and Γ. Definition 5.11. Let w ∈ W = P × a . The geodesic length of w is denoted γ(w) = γ(P|aq ). Often, this will simply be denoted γ(P|q). Lemma 5.12. The function γ is a subadditive function. Proof. Let w1 , w2 ∈ W. Then clearly, the word Γ(w1 )Γ(w2 ) is a word for w1 w2 and hence it’s geodesic length is at most γ(w1 ) + γ(w2 ). Thus γ(w1 w2 ) ≤ γ(w1 ) + γ(w2 ). Lemma 5.13. Let i ∈ Z. Then γ(b−1 |im) = 1 + γ(in). Proof. The word Γ(in)b−1 ≡ Γ(b−1 |im) and hence is a candidate for a geodesic word. To show that a lower value cannot be achieved, Theorem 3.19 says that the geodesic word Γ(im) ≡ bΓ(in)b−1 which contains Γ(in)b−1 as a subword of length 1 + γ(in). Lemma 5.14. Let i ∈ Z. Then γ(b|in) = 1 + γ(in). Proof. As with the proof of the previous lemma, the word Γ(im) ≡ bΓ(in)b−1 with bΓ(in) being a subword. Hence bΓ(in) is a geodesic word of length 1 + γ(in). This process can be generalised to an arbitrary prefix. Lemma 5.15. Let P ∈ P and r ∈ N with the condition that r = 0 if P ends with a ‘b’. The geodesic length γ(Par b−1 aim ) = γ(Pain+r ) + 1. Proof. Consider Γ(Par b−1 aim ) = g1 g2 . . . gk as a sequence of right multiplication by a single generator at each step where k = γ(Par b−1 aim ). Starting at i = 0 and incrementing: 1. If gi ∈ {a, a−1 }, then the normal form of g1 g2 . . . gi−1 and the normal form of g1 g2 . . . gi must have the same prefix. 60 2. If gi ∈ {b, b−1 }, then the normal form of g1 g2 . . . gi−1 and the normal form of g1 g2 . . . gi can differ by one element in Σ. More specifically, multiplying by a generator b or b−1 increases or decreases the length of the prefix by one; it will either append an element of Σ to the prefix or it will remove the rightmost element of the prefix. Hence, there exists a (smallest) value k ∈ {0, 1, . . . , k} such that the prefix of the normal form of g1 g2 . . . gk is exactly P. By splitting the word at this point, it can be seen that Γ(Par b−1 aim ) = Γ(P|aq )Γ(b−1 |aim−q ) for some q and q (Figure 5.1). Observe that q ≡ r (mod n) or else the normal form Par b−1 aim will not be obtained by combining the two geodesic words. Hence, this can be rewritten as Γ(Par b−1 aim ) = Γ(P|ar+sn )Γ(b−1 |aim−sm ). Since the existence of k and hence s is guaranteed, the geodesic word can be found by minimising over all such words. That is: γ(Par b−1 aim ) = min γ(Par+sn ) + γ(b−1 a(i−s)m ) s∈Z By Lemma 5.13, γ(b−1 a(i−s)m ) = 1 + γ((i − s)n). Hence, γ(Par+sn ) + γ(b−1 a(i−s)m ) = γ(Par+sn ) + γ((i − s)n) + 1 ≥ γ(Par+sn ) + 1, which is independent of s. This lower bound is exactly the case s = i, and hence γ(Par b−1 aim ) = γ(Pain+r ) + 1. Lemma 5.16. Let P ∈ P and r ∈ N with the condition that r = 0 if P ends with a b−1 . Suppose that for all q ≡ r (mod n) the geodesic length γ(w) for w ≡ Paq ∈ WP is known. Then the geodesic length γ(Par bain ) = mink∈Z {γ(P|r + mk) + γ(b|(i − k)n)}. Proof. This proof follows in a similar manner as that of Lemma 5.15. However, a lower bound independent of s could not be found and so the additional assumption is required. 61 Figure 5.1: Cutting a geodesic word of Par b−1 aim . Note that in theory, Lemma 5.16 requires the knowledge of the geodesic length for all words in WP . In practice, only knowledge of the geodesic length of a finite subset of WP is required. Pick any k ∈ Z, the value γ(Par bain ) ≤ M where M = γ(P|r + mk) + γ(b|(i − k)n). Any value of k for which γ(b|(i − k )n) > M can be ignored since it is worse than the initial guess of k. This leaves a finite set of integers that needs to to checked. Lemma 5.15 and Lemma 5.16 gives a natural algorithm to generate all words of BS(n, m) up to and including a fixed geodesic length R. Let σ ∈ Σ(n,m) and P ∈ P. Suppose that for a fixed P, the geodesic length γ(Paq ) is known up to radius R. Depending on the nature of σ , Lemma 5.15 and Lemma 5.16 provides a method of determining all words of the form w ≡ Pσ akm (in the case that σ ends in b−1 ) or w ≡ Pσ akn (in the case that σ ends in b) for all k ∈ Z. Further, since only words with geodesic length of R or less is considered and both Lemma 5.15 and Lemma 5.16 increase the geodesic length by at least one, only words in WP with geodesic length ≤ R needs to be considered. Finally, to complete the iteration step, simply apply the same logic as the proof 62 of Theorem 3.19 to find the geodesic length of words that are not in mZ or nZ (in the case of σ ending with b−1 and b respectively). That is, suppose σ ends with b, then for all q = nk + r for some k ∈ Z and 0 ≤ r ≤ n − 1, the geodesic length γ(Pσ aq ) = min{γ(Pσ akn ) + γ(r), γ(Pσ a(k+1)n ) + γ(n − r)}. A similar logic is applied for the case of σ ending in b−1 . Starting with W0/ , the geodesic length of words in that set is exactly the the result of Theorem 3.19 (I.e. words with an empty prefix). Then, to obtain all elements g ∈BS(n, m) with γ(g) ≤ R, simply iterate over all prefixes in P that consists of R or less elements from Σ(n,m) . This algorithm iterates over all normal form and hence all elements (within the radius) exactly once. It only requires remembering a single prefix P and a horocycle of elements WP up to a given geodesic length. Further, since there are fewer normal forms than words, less time is required to iterate over them. Since, the function γ is a subadditive function. One method of approximating the growth exponent is through the use of Fekete’s Lemma. Schrijver [19] provides more details about Fekete’s Lemma. Lemma 5.17. (Fekete’s Lemmma) Let {a0 , a1 , . . .} be a subadditive sequence. The limit limn→∞ ann exists and is equal to inf ann . A variation of Lemma 5.17 is applicable to this situation. Corollary 5.18. Let {b0 , b1 , . . .} be a submultiplicitive sequence. That is, for all 1 1 n, m ∈ Z+ , bn+m ≤ bn bm . The limit limn→∞ bn n exists and is equal to inf bn n . Proof. This is a direct application of Fekete’s Lemma on the sequence an = log(bn ). + It can be seen that {Si }∞ i=0 is submultiplicitive. For every k, l ∈ Z , every element of Sk+l can be represented as a concatenation of an element in Sk and an element in Sl . Thus the inequality Sk+l ≤ Sk Sl holds. But the reverse implication may not be true. That is, given two words of geodesic lengths k and l, their concatenation may not be a word of geodesic length 1 k +l. Fekete’s Lemma gives a non-trivial upper bound on the limit µ = limk→∞ bk k . Table 5.1 is a summary of the results. It charts the size of S j for small values of j over the various Baumslag-Solitar groups. The final rows are an estimate of 63 the growth rate µ based on several different methods of analysis of the numerical results obtained. For groups where the generating function for the growth has been found, the value µExact is the value of µ obtained through analysis of the singularities of that generating function. This is not applicable for groups where the generating function for the growth of the group has not been found yet. The values µRatio and µLog are the estimates of µ obtained by extrapolating the data obtained via the two methods described in Section 2.4. The value µRatio is obtained through comparison of the ratio of the sizes of successive sphere and the value µLog is obtained through comparing the limit of the sequence (S j )1/ j . Finally, the value of µBound = (S j )1/ j for the largest known j is given. This is a rigorous upper bound for the exact value of µ. The discussion in Section 2.4 can now be applied by making the assumption that S j ∼ Aµ j jθ for some values of A, µ and θ . In this case, the sequence is submultiplicative and hence Lemma 5.17 states that the limit must exist. Figure 5.2 and Figure 5.3 shows the extrapolations. Figure 5.2: Ratio of sphere sizes. For completeness, these estimates were applied to the data obtained for a horocycle in BS(2, 3). In this case, there is no obvious reason why the size of the spheres have to be submultiplicitive. Because for k, l > 8, a geodesic word for 64 j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 µExact µBound µRatio µLog BS(1, 2) 1 4 12 26 50 98 184 336 606 1086 1914 3350 5846 10134 17506 30126 51726 88598 151490 1.696 1.940 1.655 1.580 BS(1, 3) 1 4 12 30 70 158 346 742 1566 3270 6762 13886 28366 57678 116890 236246 476414 959126 1928266 2.000 2.234 1.944 1.881 BS(2, 2) 1 4 12 30 70 158 350 766 1662 3582 7678 16382 34814 73726 155646 327678 688126 1441790 3014654 2.000 2.290 2.040 1.979 BS(2, 3) 1 4 12 36 94 242 620 1578 3988 10060 25324 63572 159312 398956 997434 2490686 6214972 15494062 38595072 2.639 2.409 2.401 BS(3, 5) 1 4 12 36 108 314 906 2608 7488 21446 61358 175396 500820 1429070 4075394 11615210 2.958 2.818 2.782 Table 5.1: Estimation of growth rate of Baumslag-Solitar groups an element in Sk+l cannot be partitioned into two geodesic words with one for an element in Sk and the other for an element in Sl . Hence, the result µBound is no longer rigorous. However, estimates using µLog and µRatio using the theory from Section 2.4 still holds. Figure 5.4 and Figure 5.5 shows the plots and extrapolations used to obtain the estimates. The final estimates obtained are summarised in Table 5.2. 65 Figure 5.3: Extrapolation for growth rate. µRatio µLog Horocycle in BS(2, 3) 1.1672 1.1725 Table 5.2: Estimation of growth rate in a horocycle of BS(2, 3) Figure 5.4: Ratio of sphere sizes for horocycles in BS(2, 3). 66 Figure 5.5: Logarithmic estimation for growth of horocycle in BS(2, 3). 67 Chapter 6 Cogrowth and Amenability As the previous chapter suggests, the growth problem for the group BS(2, 3) is extremely difficult. Part of the difficulty comes from the fact that there are usually multiple geodesic words representing the same group element. Hence, a natural question to ask is how many words are there in the presentation that represents a particular group element; in particular, the identity element. In other words, is it possible to count the number of words that are equivalent to the identity. This is known as the cogrowth problem for a group. This chapter aims to construct a numerical approach to studying the asymptotic behaviour of the cogrowth series of the group. Numerical approach to this problem have attracted interest in the field. The methods developed in this chapter will aim to improve on the results found by Dykema et al. [10]. The cogrowth series is of particular interest because of the tight connections between the cogrowth of a group and its amenability. In addition to BaumslagSolitar groups, data from an amenable group Z2 , a non-amenable group F2 and an undecided group Thompson’s group F (made available by Rechnitzer [18]) have been used to further test and validate the methods developed here. The definition and results related to Thompson’s group is beyond the scope of this thesis. The reader to referred to Cannon et al. [4] for more information about Thompson’s group. The cogrowth of a presentation refers to the rate at which the number of words equivalent to the identity grows with respect to the length of the words. In a more 68 formal setting: Definition 6.1. Let G = S | R be a group presentation. For n ∈ N, the number of freely reduced words equivalent to the identity of length n is denoted Cn . That is Cn = {w ∈ S | R | w ≡ e, l(w) = n, w is freely reduced }. Further, define the sets R j to be exactly the same as for C j except with the freely conditioned removed. Definition 6.2. The cogrowth series C(z) is defined to be ∞ C(z) = ∑ C jz j. j=0 Equivalently, the return series R(z) is defined to be ∞ R(z) = ∑ R jz j. j=0 That is, R j is the number of words of length j equal to the identity. Kouksov [16] provides a method of converting between R(z) and C(z). Lemma 6.3. (Kouksov [16]) Let R(z) and C(z) be as defined above and k be the number of generators in the presentation. Then, C(z) = z 1 − z2 R 2 1 + (2k − 1)z 1 + (2k − 1)z2 , and R(z) = 1 − k + k 1 − 4(2k − 1)z2 C 1 − 4k2 z2 1− 1 − 4(2k − 1)z2 2(2k − 1)z . Definition 6.4. The cogrowth (or cogrowth exponent) of a presentation α is defined to be α = lim sup (C j )1/ j , j→∞ For convenience, the value αR are defined in exactly the same manner, except on the sequence of R j instead of C j . The value αR is known as the return exponent. As an initial example, consider the free-group on two generators, denoted F2 . 69 Example 6.5. The aim of this example is to construct the generating function for the cogrowth of the free group on two generators. First note that for any non-trivial word in the free group, there is exactly one generator that shortens the geodesic length by 1 and three generators that increase the geodesic length by 1. Since the trivial word is an exception to this general rule, begin by omitting that point and partition the free group into four disjoint subsets using the first letter of the word (Figure 6.1). I.e words that begin with x, x−1 , y and y−1 . Note that each of these four subsets are isomorphic to each other under suitable permutations of the generators. Hence denote g ∈ {x, y, x−1 , y−1 } to be an arbitrary generator. Figure 6.1: Partitioning words of F2 . Thus, starting at g, the number of words that leave and come back to g can be obtained. Let z be conjugate to the length of the word w and s be conjugate to the length of the freely reduced word minus the initial generator (i.e. γ(g−1 w)). The bivariate generating function f (z, s) = ∑n,k cn,k zn sk will count the number of words that are of length n and distance k away from g. As mentioned before, there are exactly three generators that can be postmultiplied to each word to increase its geodesic length and one generator that will decrease it. Further, in the case where the word is equivalent to g, there are exactly three generators that will increase its 70 geodesic length and none that will decrease it. Hence: f (z, s) = 1 + 3zs f (z, s) + zs−1 ( f (z, s) − f (z, 0)) . By rearranging, it can be seen that: (s − 3zs2 − z) f (z, s) = s − z f (z, 0). The coefficient of f (z, s) can be factored in terms of s to produce two roots r+ and r− where: √ 1 ± 1 − 12z2 r± = . 6z This can then be rearranged to give: f (z, s) = s − z f (z, 0) . −3z(s − r+ )(s − r− ) The function f (z, s) is known to have a series expansion. However, the term 1 s−r− does not have a combintorial series expansion (one with positive coefficients on positive exponents of s) and therefore must cancel exactly with some part of the numerator. Thus q(z)(s − r− ) = s − z f (z, 0) for some q(z). By comparing the coefficients of s, it can be seen that q(z) = 1 and hence f (z, 0) = r− /z. This gives √ 1 − 1 − 12z2 f (z, 0) = 6z2 This is exactly the generating function for the number of words that leaves a generator g and ends back at generator g. To complete the example, note that any word that is equivalent to the trivial word is either the trivial word or a sequence of subwords that leaves the trivial word and then comes back. Hence, the full generating function for the cogrowth of the free group R(z) can be found by: R(z) = 1 + 4z2 f (z, 0) + 4z2 2 f 2 (z, 0) + . . . + 4z2 k f k (z, 0) + . . . = 1 1 − 4z2 f (z, 0) The last equality coming from the fact that the summation forms a geometric 71 series. Hence, √ 1 − 2 1 − 12z2 R(z) = (4z − 1)(4z + 1) Theorem 2.57 says that if the radius of convergence of R(z) is 1/4 then the point z = ±1/4 is a singularity of the function. However, a quick check shows that limz→±1/4 R(z) = 3/2 and hence, this function has its dominant singularity at √ √ z = 1/ 12. By Theorem 2.59, the values R j ( 12) j . On a seemingly unrelated topic, the amenability of a group refers to the exists of a probability measure on a group. More formally: Definition 6.6. Let G be a group and P(G) denote the powerset of G. The group G is said to be amenable if there exists a measure µ : P(G) → [0, 1] such that: 1. The measure µ is a probability measure (µ(G) = 1). 2. The measure is finitely addtive. That is, for any finite sequence of disjoint subsets S1 , S2 . . . Sn of G, n µ(∪nj=1 S j ) = ∑ µ(S j ). j=1 3. The measure is left invariant. For any subset A ⊂ G and g ∈ G, µ(A) = µ(gA). The relationship between the cogrowth series of a group and its amenability is summarised in the following theorem due to Cohen [5] and Grigorchuk [14]. Theorem 6.7. Let S | R be a presentation for the G with a cogrowth α. The group G is amenable if and only if α = 2|S| − 1. Lemma 6.8. Let S | R be a presentation for the G. The group G is amenable if and only if αR = 2|S|. Proof. Theorem 6.7 gives the condition that a group G is amenable if and only α = 2|S| − 1. 72 For any group, the value of αR is bounded above by 2|S| since there are 2|S| possible paths leaving from every node. Hence it suffices to show that a group is amenable if and only if αR ≥ 2|S|. The condition α = 2|S| − 1 is equivalent to C(z) having a dominant singularity at zc = 1 2|S|−1 . The function 1−z2 1+(2k−1)z2 contains no singularities on the interval [0, zc ]. Hence, by Lemma 6.3, the dominant singularity of C(z) must come from R z 1+(2k−1)z2 . Further, the function tion on [0, zc ] which evaluates to of R(z) occurs at z = 1 2|S| . 1 2|S| z 1+(2k−1)z2 is an monotonic increasing func- at z = zc . Hence, the dominant singularity This is equivalent to saying that αR = 2|S|. Hence, an amenable group implies αR = 2|S|. To show the reverse implication, suppose that a group is not amenable. Then α < 2|S| − 1, which implies that the dominant singularity zc of C(z) is strictly big1 2|S|−1 . z By applying the same logic as above, the function 1+(2k−1)z 2 is 1 monotonically increasing and without singularities on [0, √ ) and in particu- ger than 2|S|−1 lar, the interval contains the value 1 2|S|−1 + ε. Hence, the function R(z) is analytic 1 up to an including z = 2|S| , which implies the dominant 1 ]. Thus, showing that αR ≥ outside of the interval [0, 2|S| singularity of R(z) occurs 2|S|. This proves the lemma. Corollary 6.9. If T < α is an lower bound on the cogrowth exponent, then T = T 2 +2k−1 T is an lower bound on the return cogrowth exponent. That is T < αR . Proof. If α > T , then the dominant singularity zc > 1/T . Lemma 6.3 gives the required transformations. The proof of Lemma 6.8 showed that the transformation is monotonic on the interval [0, zc ] and hence zr = zc 1/T T < = 2 2 2 1 + (2k − 1)(zc ) 1 + (2k − 1)(1/T ) T + 2k − 1 Finally, since α = 1/zr , this gives the desired result. Thus, the amenability of a group can be determined by studying the cogrowth exponent or the return exponent. Baumslag-Solitar groups provides a wealth of examples of both amenable and non-amenable groups. A quick lemma is required before the main result can be stated. 73 Lemma 6.10. For n ≥ 2 and m ≥ 2, the Baumslag-Solitar group BS(n, m) contains the free group on two generators as a subgroup. Proof. Consider the subgroup generated by b and aba−1 . It can be shown that this subgroup is isomorphic to the free group on two generators. First note that a word in this subgroup must either be of the form bk for some k ∈ Z or a word of the form abk1 a−1 bk2 a . . . abkq a−1 for some k1 , k2 , . . . , kq ∈ Z. Suppose there are two words w1 and w2 representing the same element in the subgroup, then w1 (w2 )−1 ≡ e. Now by Brittons lemma (Lemma 2.42), the word w1 = w2 or there must exists a pinch in the word. However, the assumption n, m ≥ 2 forbids the existence of any pinches. Hence, the words w1 = w2 and BS(n, m) contains a the free group on two generators as a subgroup. By a result of Woess [22], any group that contains F2 as a subgroup is nonamenable. Hence, any Baumslag-Solitar group BS(n, m) with n, m ≥ 2 is nonamenable. Woess [22] also states that any solvable group must be amenable. This can be combined with a result from de La Harpe [7] which shows that all BaumslagSolitar groups BS(1, m) are solvable. This is summaried in the following theorem. Theorem 6.11. Let n, m ∈ Z. Baumslag-Solitar groups BS(n, m) is amenable if and only if n = 1 or m = 1. Definition 6.4 gives a direct approach to estimate the cogrowth constant. 6.1 Enumeration Approach This approach approximates the value of α by directly computing the values of C j . First, fix n, m ∈ Z+ and consider the set of normal forms W for the group BS(n, m) as defined by Lemma 5.10. Given a normal form w ∈ W and a generator s ∈ S∪S−1 , the word ws can be converted back to a normal form using Lemma 5.10. An equivalent restatement of Definition 6.1 is to define C j to be the number of freely reduced words of length j which has a trivial normal form. The value C j can be approached directly simply by applying the search algorithm over all freely reduced words of length j. That is, iterate over all words with no immediate inverse pairs. In combination with Lemma 6.3, this gives a direct 74 conversion to the values R j . The advantage of using R j is that the sequence {R j } is supermultiplicitive. That is, for all k, l ∈ Z+ , the inequality Rk+l ≥ Rk Rl holds. This can be seen using the fact that not every word equivalent to the identity can be partitioned into two subwords both equivalent to the identity. Whilst the sequence C j appears to be supermultiplicitive, it is not immediately obvious. This is because the concatenation of two freely reduced words might not be a freely reduced word. Thus, an alternative version of Lemma 5.17 and Corollary 5.18 holds. 1 Lemma 6.12. Let {b0 , b1 , . . .} be a supermultiplicitive sequence. The limit limn→∞ bn n 1 exists and is equal to sup bn n . The results are summarised below in Table 6.1, with the size of C j for small values of j and various groups. This data is then transformed through Lemma 6.3 to Table 6.2. These values will then be used to estimate a lower bound ((αR )lb )for αR . Lemma 6.8 says that a group is amenable if the value αR = 4. Whilst it can be seen that the lower bound obtained for amenable groups are slightly higher than the non-amenable groups, the difference between the two appears minimal. This could be due to the small lengths explored. However, increasing this parameter is computational expensive. The next section will explore a different technique for estimating cogrowth that will provide more data points and hence a better extrapolation towards the cogrowth exponent. 75 j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 BS(1, 2) 1 0 0 0 0 10 0 20 64 96 338 736 2052 5208 13336 36330 92636 248816 665196 1771756 4776094 12848924 34765448 BS(1, 3) 1 0 0 0 0 0 12 0 40 0 264 0 1604 0 9748 0 61720 0 412072 0 2750960 0 18725784 BS(2, 2) 1 0 0 0 0 0 12 0 40 0 224 0 1236 0 7252 0 41192 0 247272 0 1491136 0 9119452 BS(2, 3) 1 0 0 0 0 0 0 14 0 28 60 84 240 564 1090 2760 6492 13496 33728 75768 174760 411234 958364 BS(3, 5) 1 0 0 0 0 0 0 0 0 0 20 0 64 0 280 0 1048 0 4660 0 17964 0 77508 Z2 1 0 0 0 8 0 40 0 312 0 2240 0 17280 0 134568 0 1071000 0 8627872 0 70302888 0 577920200 Table 6.1: Enumeration approach without backtracking 76 77 j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 (αR )lb BS(1, 2) 1 0 4 0 28 10 232 210 2156 3276 21994 46222 242176 626782 2832722 8377900 34699180 111709482 439970596 1494580546 5724071978 20119664376 75931952650 3.12294 BS(1, 3) 1 0 4 0 28 0 244 0 2396 0 25364 0 282868 0 3278888 0 39162396 0 479080108 0 5976762108 0 75795813900 3.12269 BS(2, 2) 1 0 4 0 28 0 244 0 2396 0 25324 0 281140 0 3232352 0 38151196 0 459594316 0 5628197948 0 69859456440 3.11114 BS(2, 3) 1 0 4 0 28 0 232 14 2092 378 19924 6930 197632 108420 2025566 1563330 21339692 21510440 230232382 287613716 2536536668 3776400194 28471353310 2.98676 BS(3, 5) 1 0 4 0 28 0 232 0 2092 0 19884 0 196096 0 1988396 0 20609676 0 217483108 0 2329674508 0 25276624828 2.97064 Table 6.2: Enumeration approach with backtracking Z2 1 0 4 0 36 0 400 0 4900 0 63504 0 853776 0 11778624 0 165636900 0 2363904400 0 34134779536 0 497634306624 3.40155 F2 1 0 4 0 28 0 232 0 2092 0 19864 0 195352 0 1970896 0 20275660 0 211823800 0 2240795848 0 23951289520 2.96338 6.2 Eigenvalue Approach An alternative approach to determine the cogrowth α is to make use of linear algebra. Recall, that Cayley graph (Definition 2.51) is a graph theoretical representation of a group. The Cayley graph admits a distance metric where the distance d(g1 , g2 ) is equal to the length of the shortest path connecting g1 and g2 . By fixing g2 = e, the distance function reduces to the geodesic length. That is for all g ∈ G, d(g, e) = γ(g). The vertices in the graph can be labelled as elements from N such that the vertex labels increase as the distance from the identity increases. That is, there exists a mapping β : G → N ∪ {0} such that for all g1 , g2 ∈ G, if d(g1 , e) < d(g2 , e) then β (g1 ) < β (g2 ). The identity node will be labelled 0 for convenience. Note that the mapping function β is not unique. Elements of the same sphere can be reordered. By reordering the labels, the results obtained at small values could change dramatically. However, at large values, the fluctuations caused by relabelling will be minimal. Further, there exists a subsequence of numbers for which the result obtained is independent of relabeling. That sequence is given j by a j = ∑i=0 |S j | where S j is the size of sphere j. This is because the Cayley graph containing a j nodes will consist of all elements of geodesic length up to and including j. In the case of Baumslag-Solitar groups, the group is infinite and hence the Cayley graph would also be infinite. Thus, let Gk = (Gk , Ek ) be the subgraph generated by the set of vertices Gk = {g ∈ G | β (g) ≤ k} and Ek = {{g1 , g2 } ∈ E | g1 , g2 ∈ Gk }. It is clear that as k tends to infinity, the subgraphs Gk approaches G in the sense that every vertex in G is only excluded from a finite number of graphs in the sequence {G1 , G2 , . . .}. Since all graphs Gi in the sequence is of finite size, normal linear algebra technique can be applied. Each graph Gi can be converted into an adjacency matrix of size i. The Perron-Frobenius Theorem for non-negative matrices states the eigenvalue of largest magnitude (the dominant eigenvalue) will be unique and positive (denote that eigenvalue λ ∗ ). Details can be found in Meyer [17] and Flajolet and Sedgewick 78 [12]. From a graph theoretic point of view, for q ∈ Z+ and an adjacency matrix A, the q-th power of A, gives the number of paths of length q between pairs of nodes. That is, the entry [Aq ]k,l is the number of paths from node k to node l of exactly length q. In particular the entry [A j ]0,0 denotes the number of paths of length j starting and finishing at the identity, which is exactly what is required to determine the cogrowth. Or more precisely, a lower bound for the cogrowth. Theorem 2.60 may be applied if it can be shown that the adjacency matrices are irreducible and aperiodic. Irreducibility in Cayley graphs is obvious to see. Each node represents an normal form in the generators and hence there exists a finite path between every node and the identity. Thus, there exists a path between any two nodes. Aperiodicity is obvious for Baumslag-Solitar groups where n + m is odd. That is, the group contains the cycle ban b−1 a−m of odd length and the cycle ba2n b−1 a−2m which is of even length. Hence the Cayley graph of that group cannot be of period d > 1 and therefore must have period 1. The case where n + m = 2k for some integer k requires more work since it does not contain any odd cycles. Thus, consider the two-step adjacency matrix A2 . This matrix contains the cycle ban b−1 a−m which is of length 2(k + 1) and the cycle ba2n b−1 a−2m of length 2(2k + 1). A quick application of the Euclidean algorithm shows that the greatest common divisor of k + 1 and 2k + 1 is 1. While the adjacency matrix A is not aperiodic for the case where n + m is even, the adjacency matrix A2 is and the resulting dominant eigenvalue will simply be (λ ∗ )2 . Thus: Lemma 6.13. The adjacency matrices of Cayley graphs are irreducible. In the case where n + m is odd, it is also aperiodic. In the case where n + m is even, the adjacency matrix A2 is aperiodic with dominant eigenvalue (λ ∗ )2 . Thus by Theorem 2.60, the sequence [A j ]0,0 (λ ∗ ) j . For any finite matrix A, the value R j ≥ [A j ]0,0 and hence λ ∗ is a lower bound for the cogrowth αR . Lemma 6.14. Let G be a group and A be the adjacency matrix of the Cayley graph of G. Further, let {Ai }i≥1 be the sequence of i × i adjacency matrices generated using the first i nodes of the Cayley graph. Then the value αR is bounded below by the dominant eigenvalue of these finite matrix Ai . 79 The sparse nature of the the adjacency matrix Ai means that the the power method would be efficient in extrapolating the dominant eigenvalue. Stewart [21] provides more details regarding the power method. 6.3 Modified Eigenvalue Approach Similar to the previous approach, the values C j can be obtained directly. Given a group G and its corresponding Cayley graph. The adjacency matrix A can be thought of as a set of ordered pairs, A = {(g, h) ∈ G × G | g ∼ h}. That is, the matrix A is the transfer matrix between all possible states. In order to compute the values C j directly, more information is required. In addition to adjacency between different states, information about the generator that links them is also important. Definition 6.15. Let G be a finite group with presentation S | R and let S = S ∪ S−1 . Define the modified adjacency matrix M = (g, s) × (h,t) ∈ (G × S ) × (G × S ) | t = s−1 and hg−1 = t . This is almost identical to the definition of A. The additional information records the last generator multiplied to reach the node. It can be seen that M can be reduced back down to A simply by “forgetting” that piece of information. That is: A = (g, h) ∈ G × G | ∃s,t ∈ S such that (g, s) × (h,t) ∈ (G × S ) × (G × S ) From a linear algebra point of view, the modified adjacency matrix for a finite group can be defined equivalently as a |G||S| × |G||S| matrix containing all possible ordered pairs (g, s) where g ∈ G and s ∈ S. The entry [M](g,s)×(h,t) = 1 if and only if t = s−1 and hg−1 = t. Thus, given an infinite group such as BS(n, m) and its corresponding infinite Cayley graph G , the same truncations can be made as in the previous section to generate a sequence of finite Cayley graphs that converge towards G . Those truncated subgraphs can then be converted into a sequence of modified adjacency matrices {M1 , M2 , M3 , . . .}. 80 Further, the set G × S can be partitioned into ∪s∈S Gs , where Gs = {(g, s) ∈ G × S | g ∈ G}. Thus, any vector v of compatible size can be partitioned in to a set of vectors ∑s∈S vs where vs consists of all the entries in Gs . Using the same logic, the matrix M can also be partitioned accordingly. The sparse nature of the modified adjacency matrix suggests that the power method would be an efficient way for finding the dominant eigenvalue. Computationally, suppose that for g, h ∈ G, there exists t ∈ S such that h = gt. Then the number of paths ending at state (h,t) is equal to the sum of the number of paths leaving from the set of states ∪s∈S , s=t −1 (g, s). That is, the next iteration of vt is given by: vt = M ∑ s∈S s=t −1 vs . Thus, the eigenvalue estimates obtained from the power method iteration becomes: M λ = ∑ s∈S s=t −1 vs · ∑ s∈S s=t −1 ∑ s∈S s=t −1 vs · ∑ s∈S s=t −1 vs . vs Since the vectors and matrix can be partitioned, this can be further simplified to give: [(Mvs ) · vs ] ∑ λ = s∈S s=t −1 ∑ [vs · vs ] . s∈S s=t −1 Where · represents the dot product of two vectors. Thus, the power method can be used to determine the value of the dominant eigenvalue to within any desired 81 accuracy. By an identical reasoning to Lemma 6.13, it can be seen that the modified adjacency matrices are irreducible. In the case of n+m being odd, the matrix is also aperiodic. In the case where n + m is even, the matrix squared (M2 ) is aperiodic. Thus Theorem 2.60 applies and by a similar argument as Lemma 6.14, it can be seen that for any finite modified adjacency matrix, the inequaliy lim j→∞ (C j )1/ j ≥ λ ∗ holds. This method of estimating the cogrowth exponent was applied to several groups for up to 10 million nodes. Figure 6.2 shows the groups that are amenable superimposed with the Thompson’s group and Figure 6.3 shows the plots for the nonamenable groups superimposed with the Thompson’s group. Since the number of elements grows exponentially with the geodesic length, the Log scale for the x-axis appears to be a natural choice. Indeed, if the eigenvalues were plotted against the number of nodes, the resulting plot would not capture all the essential information the data provides. Figure 6.2: Amenable groups. The same plot with a slightly altered x-axis provides a better picture of the behavior of the group as the number of nodes tends to infinity. If q is the number of nodes used, then as q → ∞, the limit 1/ log(q) → 0. Hence, the data can be extrapolated to 0 to give an estimation of the cogrowth exponent. Figure 6.4 and Figure 6.5 82 Figure 6.3: Non-amenable groups. represents the information in this modified manner. Using this modified eigenvalue method, a lower bound of α > 2.42579 is obtained for BS(2, 3). Through Corollary 6.9, this is equivalent to a lower bound of αR > 3.6625 for BS(2, 3). This improves the bound of 3.536 obtained by Dykema et al. [10]. Figure 6.4: Extrapolation for amenable groups. It can be seen that for all groups in Figure 6.4, as x → 0, the curves clearly approach 3, this agrees with Theorem 6.7. The results for Figure 6.5 also appears 83 Figure 6.5: Extrapolation for non-amenable groups. to agree with the Theorem 6.7. However, data for Thompson’s group appears inconclusive as it is not clear that it approaches 3 from Figure 6.4, but it does appear to have a slight upwards inflection and it also appears to converge to a limit that is greater than all non-amenable groups that was examined. This is an indication that Thompson’s group behaves differently to Baumslag-Solitar groups and that there are additional properties of Thompson’s group for which these plots are not sufficiently sensitive to detect. 84 Bibliography [1] A. Akhmedov. A new metric criterion for non-amenability III: Non-amenability of R. Thompson’s group F. Arxiv preprint arXiv:0902.3849, 2009. → pages 5 [2] G. Baumslag and D. Solitar. Some two-generator one-relator non-Hopfian groups. Bull. Amer. Math. Soc, 68(199-201):116, 1962. → pages 12 [3] J. Britton. The word problem. Annals of Mathematics, pages 16–32, 1963. → pages 15 [4] J. W. Cannon, W. J. Floyd, and W. R. Parry. Introductory notes on richard thompsons groups. Enseign. Math. (2), 42(3-4):215–256, 1996. → pages 68 [5] J. M. Cohen. Cogrowth and amenability of discrete groups. Journal of Functional Analysis, 48(3):301 – 309, 1982. ISSN 0022-1236. → pages 5, 72 [6] D. Collins, M. Edjvet, and C. Gill. Growth series for the group x, y | x−1 yx = yl . Archiv der Mathematik, 62(1):1–11, 1994. → pages 4, 24 [7] P. de La Harpe. Topics in geometric group theory. University of Chicago Press, 2000. → pages 74 [8] V. Diekert and J. Laun. On computing geodesics in Baumslag-Solitar groups. Arxiv preprint arXiv:0907.5114, 2009. → pages 4, 24 [9] D. Dummit and R. Foote. Abstract Algebra. John Wile & Sons. Inc., New York,, 1999. → pages 6, 11 [10] K. Dykema, D. Redelmeier, M. Moslehian, R. Rajic, M. Anshelevich, T. Masuda, R. Dumitru, C. Peligrad, M. Rordam, and A. Sierakowski. Lower bounds for the spectral radii of adjacency operators on Baumslag-Solitar groups. Arxiv preprint arXiv:1006.0556, 2010. → pages 68, 83 85 [11] M. Edjvet and D. Johnson. The Growth of Certain Amalgamated Free Products and HNN-Extensions. Journal of the Australian Mathematical Society: Pure mathematics and statistics, page 285, 1992. → pages 4 [12] P. Flajolet and R. Sedgewick. Analytic combinatorics. Cambridge Univ Pr, 2009. → pages 20, 21, 22, 79 [13] E. Freden, T. Knudson, and J. Schofield. Growth in Baumslag-Solitar groups I: subgroups and rationality. LMS Journal of Computation and Mathematics. URL http://antares.sc.suu.edu/bsgrowth1.ps. → pages 3, 34, 56 [14] R. Grigorchuk. Symmetrical random walks on discrete groups. Multicomponent random systems. Adv. Probab. Related Topics, 6, 1980. → pages 5, 72 [15] G. Higman, B. Neumann, and H. Neuman. Embedding theorems for groups. Journal of the London Mathematical Society, 1(4):247, 1949. → pages 13 [16] D. Kouksov. On rationality of the cogrowth series. Proceedings of the American Mathematical Society, 126(10):2845–2847, 1998. → pages 69 [17] C. D. Meyer, editor. Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. ISBN 0-89871-454-0. → pages 78 [18] A. Rechnitzer. Personal Communication, 2010. → pages 68 [19] A. Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer Verlag, 2003. → pages 63 [20] E. Shavgulidze. About amenability of subgroups of the group of diffeomorphisms of the interval. Arxiv preprint arXiv:0906.0107, 2009. → pages 5 [21] G. Stewart. Matrix Algorithms: Eigensystems. Society for Industrial Mathematics, 2001. → pages 80 [22] W. Woess. Random walks on infinite graphs and groups–a survey on selected topics. Bulletin of the London Mathematical Society, 26(1):1, 1994. → pages 74 86
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Enumeration problems in Baumslag-Solitar groups
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Enumeration problems in Baumslag-Solitar groups Wong, Thomas 2010
pdf
Page Metadata
Item Metadata
Title | Enumeration problems in Baumslag-Solitar groups |
Creator |
Wong, Thomas |
Publisher | University of British Columbia |
Date Issued | 2010 |
Description | Geometric group theory refers to the study of finitely generated groups and their properties by exploring the algebraic and topological structure. This thesis will look at various enumeration problems that arises in Baumslag-Solitar groups. Initially, this thesis aims to reproduce and validate some of the work that has been done on the questions of growth, cogrowth and geodesic elements via an enumeration approach. This approach will then be used to explore specific examples of Baumslag-Solitar groups where these questions have not been fully answered. The first part of this thesis will look at the growth of a horocyclic subgroup in Baumslag-Solitar groups. It will then build upon this to develop an algorithm to count the elements of the group in general out to a fixed radius with the intention of further understanding the unresolved cases. The second part of this thesis will use Baumslag-Solitar groups as a basis to develop numerical tests to estimate cogrowth of groups. Since the cogrowth of a group is directly related to the amenability of the group, these numerical tests for cogrowth can be applied to groups such that Thompson's group F, where the question of amenability is still highly debated. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-10-07 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0071347 |
URI | http://hdl.handle.net/2429/29028 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2010-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2010_fall_wong_thomas.pdf [ 1.54MB ]
- Metadata
- JSON: 24-1.0071347.json
- JSON-LD: 24-1.0071347-ld.json
- RDF/XML (Pretty): 24-1.0071347-rdf.xml
- RDF/JSON: 24-1.0071347-rdf.json
- Turtle: 24-1.0071347-turtle.txt
- N-Triples: 24-1.0071347-rdf-ntriples.txt
- Original Record: 24-1.0071347-source.json
- Full Text
- 24-1.0071347-fulltext.txt
- Citation
- 24-1.0071347.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0071347/manifest