Stallings automata for free-times-abelian groupsintersections and index

  1. Delgado, Jordi 1
  2. Ventura, Enric 2
  1. 1 Universidad del País Vasco. Departamento de Matemáticas
  2. 2 Universitat Politècnica de Catalunya. Departament de Matemàtiques
Publicacions matematiques

ISSN: 0214-1493

Year of publication: 2022

Volume: 66

Issue: 2

Pages: 789-830

Type: Article

More publications in: Publicacions matematiques


We extend the classical Stallings theory (describing subgroups of free groups as automata) to direct products of free and abelian groups: after introducing enriched automata (i.e., automata with extra abelian labels), we obtain an explicit bijection between subgroups and a certain type of such enriched automata, which—as it happens in the free group—is computable in the finitely generated case. This approach provides a neat geometric description of (even non-(finitely generated)) intersections of finitely generated subgroups within this non-Howson family. In particular, we give a geometric solution to the subgroup intersection problem and the finite index problem, providing recursive bases and transversals, respectively.

Bibliographic References

  • L. Bartholdi and P. V. Silva, Rational subsets of groups, in: “Handbook of Automata Theory. Vol. II—Automata in Mathematics and Selected Applications”, EMS Press, Berlin, 2021, pp. 841–869.
  • B. Baumslag, Intersections of finitely generated subgroups in free products, J. London Math. Soc. 41 (1966), 673–679. DOI: 10.1112/jlms/s1-41.1.673
  • R. G. Burns and S.-M. Kam, On the intersection of double cosets in free groups, with an application to amalgamated products, J. Algebra 210(1) (1998), 165–193. DOI: 10.1006/jabr.1998.7411
  • A. Carvalho, On the dynamics of extensions of free-abelian times free groups endomorphisms to the completion, Preprint (2021). arXiv:2011.05205
  • J. Delgado, Extensions of free groups: algebraic, geometric, and algorithmic aspects, Thesis (Ph.D.)-Universitat Polit`ecnica de Catalunya (2017). Available on
  • J. Delgado, M. Roy, and E. Ventura, Intersection configurations in free times free-abelian groups, Preprint (2021). arXiv:2107.12426
  • J. Delgado, M. Roy, and E. Ventura, On universally quotientable groups, in preparation
  • J. Delgado and P. V. Silva, On the lattice of subgroups of a free group: complements and rank, J. Groups Complex. Cryptol. 12(1) (2020), Paper no. 1, 24 pp.
  • J. Delgado and E. Ventura, Algorithmic problems for free-abelian times free groups, J. Algebra 391 (2013), 256–283. DOI: 10.1016/j.jalgebra.2013.04.033
  • J. Delgado and E. Ventura, A list of applications of Stallings automata, Trans. Comb. 11(3) (2022), 181–235. DOI: 10.22108/toc.2021.130387.1905
  • J. Delgado and E. Ventura, Stallings automata for free extensions, in preparation.
  • J. Delgado and E. Ventura, Stallings automata for free-by-abelian groups, in preparation.
  • J. Delgado, E. Ventura, and A. Zakharov, Intersection problem for Droms RAAGs, Internat. J. Algebra Comput. 28(7) (2018), 1129–1162. DOI: 10.1142/S0218196718500509
  • J. Delgado, E. Ventura, and A. Zakharov, Relative order and spectrum in free and related groups, Preprint (2021). arXiv:2105.03798
  • W. Dicks, Simplified Mineyev, Preprint 2011. Available on∼dicks/SimplifiedMineyev.pdf.
  • J. Friedman, Sheaves on graphs, their homological invariants, and a proof of the Hanna Neumann conjecture: with an appendix by Warren Dicks, Mem. Amer. Math. Soc. 233(1100) (2015), 106 pp. DOI: 10.1090/memo/1100
  • M. Hall, Jr., Subgroups of finite index in free groups, Canad. J. Math. 1 (1949), 187–190. DOI: 10.4153/cjm-1949-017-2
  • A. G. Howson, On the intersection of finitely generated free groups, J. London Math. Soc. 29 (1954), 428–434. DOI: 10.1112/jlms/s1-29.4.428
  • S. V. Ivanov, On the intersection of finitely generated subgroups in free products of groups, Internat. J. Algebra Comput. 9(5) (1999), 521–528. DOI: 10.1142/S021819679900031X
  • S. V. Ivanov, Intersecting free subgroups in free products of groups., Internat. J. Algebra Comput. 11(3) (2001), 281–290. DOI: 10.1142/S0218196701000267
  • A. Jaikin-Zapirain, Approximation by subgroups of finite index and the Hanna Neumann conjecture, Duke Math. J. 166(10) (2017), 1955–1987. DOI: 10.1215/00127094-0000015X
  • I. Kapovich and A. Myasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248(2) (2002), 608–668. DOI: 10.1006/jabr.2001.9033
  • I. Kapovich, R. Weidmann, and A. Miasnikov, Foldings, graphs of groups and the membership problem, Internat. J. Algebra Comput. 15(1) (2005), 95–128. DOI: 10.1142/S021819670500213X
  • O. Kharlampovich, A. Miasnikov, and P. Weil, Stallings graphs for quasiconvex subgroups, J. Algebra 488 (2017), 442–483. DOI: 10.1016/j.jalgebra.2017.05.037
  • S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V topologies and the extension problem for inverse automata, Internat. J. Algebra Comput. 11(4) (2001), 405–445. DOI: 10.1142/S0218196701000498
  • A. Miasnikov, E. Ventura, and P. Weil, Algebraic extensions in free groups, in: “Geometric Group Theory”, Trends Math., Birkh¨auser, Basel, 2007, pp. 225–253. DOI: 10.1007/978-3-7643-8412-8_12
  • I. Mineyev, Submultiplicativity and the Hanna Neumann conjecture, Ann. of Math. (2) 175(1) (2012), 393–414. DOI: 10.4007/annals.2012.175.1.11
  • H. Neumann, On the intersection of finitely generated free groups, Publ. Math. Debrecen 4 (1956), 186–189.
  • D. Puder, Primitive words, free factors and measure preservation, Israel J. Math. 201(1) (2014), 25–73. DOI: 10.1007/s11856-013-0055-2
  • A. Roig, E. Ventura, and P. Weil, On the complexity of the Whitehead minimization problem, Internat. J. Algebra Comput. 17(8) (2007), 1611–1634. DOI: 10.1142/S0218196707004244
  • M. Roy and E. Ventura, Fixed subgroups and computation of auto-fixed closures in free-abelian times free groups, J. Pure Appl. Algebra 224(4) (2020), 106210, 19 pp. DOI: 10.1016/j.jpaa.2019.106210
  • M. Roy and E. Ventura, Degrees of compression and inertia for free-abelian times free groups, J. Algebra 568 (2021), 241–272. DOI: 10.1016/j.jalgebra.2020.09.040
  • J.-P. Serre, “Trees”, Translated from the French by John Stillwell, Springer Verlag, Berlin-New York, 1980.
  • P. V. Silva, X. Soler-Escriva, and E. Ventura ` , Finite automata for Schreier graphs of virtually free groups, J. Group Theory 19(1) (2016), 25–54. DOI: 10.1515/jgth-2015-0028
  • P. V. Silva and P. Weil, On an algorithm to decide whether a free group is a free factor of another, Theor. Inform. Appl. 42(2) (2008), 395–414. DOI: 10.1051/ita:2007040
  • J. R. Stallings, Topology of finite graphs, Invent. Math. 71(3) (1983), 551–565. DOI: 10.1007/BF02095994
  • E. Ventura, On fixed subgroups of maximal rank, Comm. Algebra 25(10) (1997), 3361–3375. DOI: 10.1080/00927879708826057