Finite generating sets of relatively hyperbolic groups and applications to geodesic languages
HTML articles powered by AMS MathViewer
- by Yago Antolín and Laura Ciobanu PDF
- Trans. Amer. Math. Soc. 368 (2016), 7965-8010 Request permission
Abstract:
Given a finitely generated relatively hyperbolic group $G$, we construct a finite generating set $X$ of $G$ such that $(G,X)$ has the ‘falsification by fellow traveler property’ provided that the parabolic subgroups $\{H_\omega \}_{\omega \in \Omega }$ have this property with respect to the generating sets $\{X\cap H_\omega \}_{\omega \in \Omega }$. This implies that groups hyperbolic relative to virtually abelian subgroups, which include all limit groups and groups acting freely on $\mathbb {R}^n$-trees, or geometrically finite hyperbolic groups have generating sets for which the language of geodesics is regular and the complete growth series and complete geodesic series are rational. As an application of our techniques, we prove that if each $H_\omega$ admits a geodesic biautomatic structure over $X\cap H_\omega$, then $G$ has a geodesic biautomatic structure.
Similarly, we construct a finite generating set $X$ of $G$ such that $(G,X)$ has the ‘bounded conjugacy diagrams’ property or the ‘neighboring shorter conjugate’ property if the parabolic subgroups $\{H_\omega \}_{\omega \in \Omega }$ have this property with respect to the generating sets $\{X\cap H_\omega \}_{\omega \in \Omega }$. This implies that a group hyperbolic relative to abelian subgroups has a generating set for which its Cayley graph has bounded conjugacy diagrams, a fact we use to give a cubic time algorithm to solve the conjugacy problem. Another corollary of our results is that groups hyperbolic relative to virtually abelian subgroups have a regular language of conjugacy geodesics.
References
- Martin R. Bridson and André Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999. MR 1744486, DOI 10.1007/978-3-662-12494-9
- Martin R. Bridson and James Howie, Conjugacy of finite subsets in hyperbolic groups, Internat. J. Algebra Comput. 15 (2005), no. 4, 725–756. MR 2160576, DOI 10.1142/S0218196705002529
- B. H. Bowditch, Relatively hyperbolic groups, Internat. J. Algebra Comput. 22 (2012), no. 3, 1250016, 66. MR 2922380, DOI 10.1142/S0218196712500166
- Inna Bumagin, The conjugacy problem for relatively hyperbolic groups, Algebr. Geom. Topol. 4 (2004), 1013–1040. MR 2100689, DOI 10.2140/agt.2004.4.1013
- Inna Bumagin, Time complexity of the conjugacy problem in relatively hyperbolic groups, Internat. J. Algebra Comput. 25 (2015), no. 5, 689–723. MR 3384078, DOI 10.1142/S0218196715500162
- Laura Ciobanu and Susan Hermiller, Conjugacy growth series and languages in groups, Trans. Amer. Math. Soc. 366 (2014), no. 5, 2803–2825. MR 3165656, DOI 10.1090/S0002-9947-2013-06052-7
- L. Ciobanu, S. Hermiller, D. F. Holt and S. Rees, Conjugacy Languages in Groups, preprint, arXiv:1401.7203, Israel Journal of Mathematics, to appear.
- M. Coornaert, T. Delzant, and A. Papadopoulos, Géométrie et théorie des groupes, Lecture Notes in Mathematics, vol. 1441, Springer-Verlag, Berlin, 1990 (French). Les groupes hyperboliques de Gromov. [Gromov hyperbolic groups]; With an English summary. MR 1075994
- François Dahmani, Combination of convergence groups, Geom. Topol. 7 (2003), 933–963. MR 2026551, DOI 10.2140/gt.2003.7.933
- François Dahmani, Finding relative hyperbolic structures, Bull. Lond. Math. Soc. 40 (2008), no. 3, 395–404. MR 2418795, DOI 10.1112/blms/bdn018
- François Dahmani, Existential questions in (relatively) hyperbolic groups, Israel J. Math. 173 (2009), 91–124. MR 2570661, DOI 10.1007/s11856-009-0084-z
- Cornelia Druţu and Mark Sapir, Relatively hyperbolic groups with rapid decay property, Int. Math. Res. Not. 19 (2005), 1181–1194. MR 2147058, DOI 10.1155/IMRN.2005.1181
- Murray J. Elder, Finiteness and the falsification by fellow traveler property, Proceedings of the Conference on Geometric and Combinatorial Group Theory, Part II (Haifa, 2000), 2002, pp. 103–113. MR 1950887, DOI 10.1023/A:1021273013372
- David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694
- David Epstein and Derek Holt, The linearity of the conjugacy problem in word-hyperbolic groups, Internat. J. Algebra Comput. 16 (2006), no. 2, 287–305. MR 2228514, DOI 10.1142/S0218196706002986
- B. Farb, Relatively hyperbolic groups, Geom. Funct. Anal. 8 (1998), no. 5, 810–840. MR 1650094, DOI 10.1007/s000390050075
- Rostislav Grigorchuk and Tatiana Nagnibeda, Complete growth functions of hyperbolic groups, Invent. Math. 130 (1997), no. 1, 159–188. MR 1471889, DOI 10.1007/s002220050181
- M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75–263. MR 919829, DOI 10.1007/978-1-4613-9586-7_{3}
- Vincent Guirardel, Limit groups and groups acting freely on $\Bbb R^n$-trees, Geom. Topol. 8 (2004), 1427–1470. MR 2119301, DOI 10.2140/gt.2004.8.1427
- Susan Hermiller, Derek F. Holt, and Sarah Rees, Star-free geodesic languages for groups, Internat. J. Algebra Comput. 17 (2007), no. 2, 329–345. MR 2310150, DOI 10.1142/S0218196707003603
- Derek F. Holt, Garside groups have the falsification by fellow-traveller property, Groups Geom. Dyn. 4 (2010), no. 4, 777–784. MR 2727663, DOI 10.4171/GGD/105
- Derek F. Holt and Sarah Rees, Artin groups of large type are shortlex automatic with regular geodesics, Proc. Lond. Math. Soc. (3) 104 (2012), no. 3, 486–512. MR 2900234, DOI 10.1112/plms/pdr035
- Olga Kharlampovich, Alexei Myasnikov, and Denis Serbin, Actions, length functions, and non-Archimedean words, Internat. J. Algebra Comput. 23 (2013), no. 2, 325–455. MR 3038860, DOI 10.1142/S0218196713400031
- O. Kharlampovich, A. Myasnikov, and P. Weil, Completion process and quasi-convex subgroups. arXiv: 1408.1917.
- Urs Lang, Injective hulls of certain discrete metric spaces and groups, J. Topol. Anal. 5 (2013), no. 3, 297–331. MR 3096307, DOI 10.1142/S1793525313500118
- B. H. Neumann, Groups with finite classes of conjugate subgroups, Math. Z. 63 (1955), 76–96. MR 72137, DOI 10.1007/BF01187925
- Walter D. Neumann and Michael Shapiro, Automatic structures, rational growth, and geometrically finite hyperbolic groups, Invent. Math. 120 (1995), no. 2, 259–287. MR 1329042, DOI 10.1007/BF01241129
- W. D. Neumann and M. Shapiro, A Short Course in Geometric Group Theory. Notes for the ANU Workshop, January/February 1996.
- Walter D. Neumann and Michael Shapiro, Regular geodesic normal forms in virtually abelian groups, Bull. Austral. Math. Soc. 55 (1997), no. 3, 517–519. MR 1456281, DOI 10.1017/S0004972700034171
- Gen. A. Noskov, Growth of certain non-positively curved cube groups, European J. Combin. 21 (2000), no. 5, 659–666. MR 1771984, DOI 10.1006/eujc.1999.0372
- G. A. Noskov, Bounded shortening in Coxeter complexes and buildings, Mathematical structures and modeling, No. 8 (Russian), Omsk. Gos. Univ., Omsk, 2001, pp. 10–14. MR 1890662
- Z. O’Connor, Conjugacy Search Problem for Relatively Hyperbolic Groups, preprint, arXiv:1211.5561.
- D. Osin, Asymptotic dimension of relatively hyperbolic groups, Int. Math. Res. Not. 35 (2005), 2143–2161. MR 2181790, DOI 10.1155/IMRN.2005.2143
- Denis V. Osin, Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems, Mem. Amer. Math. Soc. 179 (2006), no. 843, vi+100. MR 2182268, DOI 10.1090/memo/0843
- Denis V. Osin, Peripheral fillings of relatively hyperbolic groups, Invent. Math. 167 (2007), no. 2, 295–326. MR 2270456, DOI 10.1007/s00222-006-0012-3
- D. Y. Rebbechi, Algorithmic Properties of Relatively Hyperbolic Groups, PhD Dissertation (2003), Rutgers, Newark.
- H. Short, Groups and combings. Preprint, ENS Lyon, 1990.
- Arto Salomaa and Matti Soittola, Automata-theoretic aspects of formal power series, Texts and Monographs in Computer Science, Springer-Verlag, New York-Heidelberg, 1978. MR 0483721
- Andrew D. Warshall, Deep pockets in lattices and other groups, Trans. Amer. Math. Soc. 362 (2010), no. 2, 577–601. MR 2551498, DOI 10.1090/S0002-9947-09-04954-X
Additional Information
- Yago Antolín
- Affiliation: Department of Mathematics, Vanderbilt University, 1326 Stevenson Center, Nash- ville, Tennessee 37240
- Email: yago.anpi@gmail.com
- Laura Ciobanu
- Affiliation: Institut de Mathématiques, University of Neuchâtel, R. Emile-Argand 11, CH-2000 Neuchâtel, Switzerland
- MR Author ID: 797163
- Email: laura.ciobanu@unine.ch
- Received by editor(s): November 6, 2014
- Received by editor(s) in revised form: February 4, 2015, and March 3, 2015
- Published electronically: March 21, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 7965-8010
- MSC (2010): Primary 20F65, 20F10, 20F67, 68Q45
- DOI: https://doi.org/10.1090/tran/6701
- MathSciNet review: 3546790