Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T07:34:15.807Z Has data issue: false hasContentIssue false
  • English
  • Français

Growth in Baumslag–Solitar groups I: subgroups and rationality

Part of: Structure and classification of infinite or finite groups Theory of computing Special aspects of infinite or finite groups

Published online by Cambridge University Press:  01 February 2011

Eric M. Freden ,
Teresa Knudson  and
Jennifer Schofield
Eric M. Freden
Affiliation:
Department of Mathematics, Southern Utah University, Cedar City UT, USA (email: [email protected])
Teresa Knudson
Affiliation:
Mohave Community College, North Mohave Campus, Colorado City AZ, USA (email: [email protected])
Jennifer Schofield
Affiliation:
Department of Mathematics, Brigham Young University, Provo UT, USA (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The computation of growth series for the higher Baumslag–Solitar groups is an open problem first posed by de la Harpe and Grigorchuk. We study the growth of the horocyclic subgroup as the key to the overall growth of these Baumslag–Solitar groups BS(p,q), where 1<p<q. In fact, the overall growth series can be represented as a modified convolution product with one of the factors being based on the series for the horocyclic subgroup. We exhibit two distinct algorithms that compute the growth of the horocyclic subgroup and discuss the time and space complexity of these algorithms. We show that when p divides q, the horocyclic subgroup has a geodesic combing whose words form a context-free (in fact, one-counter) language. A theorem of Chomsky–Schützenberger allows us to compute the growth series for this subgroup, which is rational. When p does not divide q, we show that no geodesic combing for the horocyclic subgroup forms a context-free language, although there is a context-sensitive geodesic combing. We exhibit a specific linearly bounded Turing machine that accepts this language (with quadratic time complexity) in the case of BS(2,3) and outline the Turing machine construction in the general case.

MSC classification

Secondary: 20E07: Subgroup theorems; subgroup growth 20F65: Geometric group theory 20F10: Word problems, other decision problems, connections with logic and automata 68Q45: Formal languages and automata
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 14 , 2011 , pp. 34 - 71
Copyright
Copyright © London Mathematical Society 2011

References

[1]Adams, J. and Freden, E. M., ‘A context-sensitive combing associated with Baumslag–Solitar 2, 7’, Preprint.Google Scholar
[2]Baumslag, G. and Solitar, D., ‘Some two-generator one-relator non-Hopfian groups’, Bull. Amer. Math. Soc. 68 (1962) 199–201.CrossRefGoogle Scholar
[3]Brazil, M., ‘Growth functions for some nonautomatic Baumslag–Solitar groups’, Trans. Amer. Math. Soc. 342 (1994) 137–154.CrossRefGoogle Scholar
[4]Buntrock, G. and Loryś, K., On growing context-sensitive languages, Lecture Notes in Computer Science, 623 (Springer, Berlin, 1992) 77–88.Google Scholar
[5]Cannon, J. W., ‘The combinatorial structure of cocompact discrete hyperbolic groups’, Geom. Dedicata 16 (1984) 123–148.CrossRefGoogle Scholar
[6]Collins, D. J., Edjvet, M. and Gill, C. P., ‘Growth series for the group 〈x,y∣x −1yx=y l〉’, Arch. Math. (Basel) 62 (1994) no. 1, 1–11.CrossRefGoogle Scholar
[7]de la Harpe, P., Topics in geometric group theory (The University of Chicago Press, Chicago, IL, 2000).Google Scholar
[8]Diekert, V. and Laun, J., ‘On computing geodesics in Baumslag–Solitar groups’, arXiv:0907.5114v2 [math.GR].Google Scholar
[9]Edjvet, M. and Johnson, D. L., ‘The growth of certain amalgamated free products and HNN extensions’, J. Aust. Math. Soc. Ser. A 52 (1992) no. 3, 285–298.CrossRefGoogle Scholar
[10]Elder, M., ‘A linear-time algorithm to compute geodesics in solvable Baumslag–Solitar groups’, arXiv:0903.0216v3 [math.GR].Google Scholar
[11]Epstein, D. B. A., Cannon, J. W., Holt, D. F., Levy, S. V. F., Paterson, M. S. and Thurston, W. P., Word processing in groups (Jones-Bartlett, Boston, MA, 1992).CrossRefGoogle Scholar
[12]Farb, B. and Moser, L., ‘A rigidity theorem for the solvable Baumslag–Solitar groups’, Invent. Math. 131 (1998) 419–451.CrossRefGoogle Scholar
[13]Flajolet, P. and Sedgewick, R., Analytic combinatorics (Cambridge University Press, Cambridge, 2008).Google Scholar
[14]Freden, E. M., Adams, J. and Schofield, J., ‘Growth in Baumslag–Solitar groups II: asymptotics’, in preparation.Google Scholar
[15]Freden, E. M. and Schofield, J., ‘The growth of Higman 3’, J. Group Theory 11 (2008) 227–298.CrossRefGoogle Scholar
[16]Gilman, R. H., ‘A shrinking lemma for indexed languages’, Theoret. Comput. Sci. 163 (1996) 277–281.CrossRefGoogle Scholar
[17]Hopcroft, J. E. and Ullman, J. D., Introduction to automata theory, languages, and computation (Addison-Wesley, Reading, MA, 1979).Google Scholar
[18] Source code for some growth computations in Baumslag–Solitar groups,http://antares.cciet.suu.edu/papers.html.Google Scholar
[19]Vijay-Shanker, K., ‘A study of tree adjoining grammars’, PhD Thesis, University of Pennsylvania, 1987.Google Scholar
[20]Vijay-Shanker, K. and Weir, D. J., ‘The equivalence of four extensions of context-free grammars’, Math. Syst. Theory 27 (1994) 511–546.CrossRefGoogle Scholar