The geometry of profinite graphs with applications to free groups and finite monoids
HTML articles powered by AMS MathViewer
- by K. Auinger and B. Steinberg PDF
- Trans. Amer. Math. Soc. 356 (2004), 805-851 Request permission
Abstract:
We initiate the study of the class of profinite graphs $\Gamma$ defined by the following geometric property: for any two vertices $v$ and $w$ of $\Gamma$, there is a (unique) smallest connected profinite subgraph of $\Gamma$ containing them; such graphs are called tree-like. Profinite trees in the sense of Gildenhuys and Ribes are tree-like, but the converse is not true. A profinite group is then said to be dendral if it has a tree-like Cayley graph with respect to some generating set; a Bass-Serre type characterization of dendral groups is provided. Also, such groups (including free profinite groups) are shown to enjoy a certain small cancellation condition. We define a pseudovariety of groups $\mathbf {H}$ to be arboreous if all finitely generated free pro-$\mathbf {H}$ groups are dendral (with respect to a free generating set). Our motivation for studying such pseudovarieties of groups is to answer several open questions in the theory of profinite topologies and the theory of finite monoids. We prove, for arboreous pseudovarieties $\mathbf {H}$, a pro-$\mathbf {H}$ analog of the Ribes and Zalesskiĭ product theorem for the profinite topology on a free group. Also, arboreous pseudovarieties are characterized as precisely the solutions $\mathbf {H}$ to the much studied pseudovariety equation $\mathbf {J}\ast \mathbf {H}= \mathbf {J} \text {\textcircled {$m$}} \mathbf {H}$.References
- Jorge Almeida, Finite semigroups and universal algebra, Series in Algebra, vol. 3, World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Translated from the 1992 Portuguese original and revised by the author. MR 1331143
- Jorge Almeida, Hyperdecidable pseudovarieties and the calculation of semidirect products, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 241–261. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1722629, DOI 10.1142/S0218196799000163
- Jorge Almeida and Benjamin Steinberg, On the decidability of iterated semidirect products with applications to complexity, Proc. London Math. Soc. (3) 80 (2000), no. 1, 50–74. MR 1719180, DOI 10.1112/S0024611500012144
- Jorge Almeida and Benjamin Steinberg, Syntactic and global semigroup theory: a synthesis approach, Algorithmic problems in groups and semigroups (Lincoln, NE, 1998) Trends Math., Birkhäuser Boston, Boston, MA, 2000, pp. 1–23. MR 1750489
- Jorge Almeida and Pascal Weil, Reduced factorizations in free profinite groups and join decompositions of pseudovarieties, Internat. J. Algebra Comput. 4 (1994), no. 3, 375–403. MR 1297147, DOI 10.1142/S0218196794000051
- J. Almeida and P. Weil, Relatively free profinite monoids: an introduction and examples, Semigroups, formal languages and groups (York, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 466, Kluwer Acad. Publ., Dordrecht, 1995, pp. 73–117. MR 1630619
- Zh. Almeĭda and P. Veĭl′, Free profinite semigroups over semidirect products, Izv. Vyssh. Uchebn. Zaved. Mat. 1 (1995), 3–31 (Russian); English transl., Russian Math. (Iz. VUZ) 39 (1995), no. 1, 1–27. MR 1391317
- C. J. Ash, Inevitable graphs: a proof of the type $\textrm {II}$ conjecture and some related decision procedures, Internat. J. Algebra Comput. 1 (1991), no. 1, 127–146. MR 1112302, DOI 10.1142/S0218196791000079
- Karl Auinger, Semigroups with central idempotents, Algorithmic problems in groups and semigroups (Lincoln, NE, 1998) Trends Math., Birkhäuser Boston, Boston, MA, 2000, pp. 25–33. MR 1750490
- K. Auinger, Join decompositions of pseudovarieties involving semigroups with commuting idempotents, J. Pure Appl. Algebra 170 (2002), no. 2-3, 115–129. MR 1904840, DOI 10.1016/S0022-4049(01)00081-0
- K. Auinger, T. E. Hall, N. R. Reilly, and S. Zhang, Congruences on the lattice of pseudovarieties of finite semigroups, Internat. J. Algebra Comput. 7 (1997), no. 4, 433–455. MR 1459621, DOI 10.1142/S0218196797000198
- A. H. Clifford and G. B. Preston, The algebraic theory of semigroups. Vol. I, Mathematical Surveys, No. 7, American Mathematical Society, Providence, R.I., 1961. MR 0132791
- Manuel Delgado, Stuart Margolis, and Benjamin Steinberg, Combinatorial group theory, inverse monoids, automata, and global semigroup theory, Internat. J. Algebra Comput. 12 (2002), no. 1-2, 179–211. International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory (Lincoln, NE, 2000). MR 1902365, DOI 10.1142/S0218196702000924
- Leo F. Epstein, A function related to the series for $e^{e^x}$, J. Math. Phys. Mass. Inst. Tech. 18 (1939), 153–173. MR 58, DOI 10.1002/sapm1939181153
- Gillian Z. Elston, Semigroup expansions using the derived category, kernel, and Malcev products, J. Pure Appl. Algebra 136 (1999), no. 3, 231–265. MR 1675804, DOI 10.1016/S0022-4049(97)00172-2
- Rita Gitik and Eliyahu Rips, On separability properties of groups, Internat. J. Algebra Comput. 5 (1995), no. 6, 703–717. MR 1365198, DOI 10.1142/S0218196795000288
- Dion Gildenhuys and Luis Ribes, Profinite groups and Boolean graphs, J. Pure Appl. Algebra 12 (1978), no. 1, 21–47. MR 488811, DOI 10.1016/0022-4049(78)90019-1
- Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
- Bernhard Herwig and Daniel Lascar, Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (2000), no. 5, 1985–2021. MR 1621745, DOI 10.1090/S0002-9947-99-02374-0
- Karsten Henckell, Stuart W. Margolis, Jean-Eric Pin, and John Rhodes, Ash’s type $\textrm {II}$ theorem, profinite topology and Mal′cev products. I, Internat. J. Algebra Comput. 1 (1991), no. 4, 411–436. MR 1154442, DOI 10.1142/S0218196791000298
- Peter M. Higgins, Techniques of semigroup theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. With a foreword by G. B. Preston. MR 1167445
- John M. Howie, Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1455373
- Kenneth Krohn and John Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965), 450–464. MR 188316, DOI 10.1090/S0002-9947-1965-0188316-1
- Kenneth Krohn and John Rhodes, Complexity of finite semigroups, Ann. of Math. (2) 88 (1968), 128–160. MR 236294, DOI 10.2307/1970558
- Mark V. Lawson, Inverse semigroups, World Scientific Publishing Co., Inc., River Edge, NJ, 1998. The theory of partial symmetries. MR 1694900, DOI 10.1142/9789812816689
- Stuart W. Margolis and John C. Meakin, $E$-unitary inverse monoids and the Cayley graph of a group presentation, J. Pure Appl. Algebra 58 (1989), no. 1, 45–76. MR 996174, DOI 10.1016/0022-4049(89)90052-2
- Stuart W. Margolis and John C. Meakin, Free inverse monoids and graph immersions, Internat. J. Algebra Comput. 3 (1993), no. 1, 79–99. MR 1214007, DOI 10.1142/S021819679300007X
- S. W. Margolis and J.-E. Pin, Varieties of finite monoids and topology for the free monoid, pp 113–130 in: Proceedings of the 1984 Marquette Conference on Semigroups, K. Byleen, P. Jones and F. Pastijn, eds., Marquette University, Milwaukee, 1984.
- S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-$\mathbf V$ topologies and the extension problem for inverse automata, Internat. J. Algebra Comput. 11 (2001), no. 4, 405–445 (English, with English and French summaries). MR 1850210, DOI 10.1142/S0218196701000498
- D. B. McAlister, Groups, semilattices and inverse semigroups. I, II, Trans. Amer. Math. Soc. 192 (1974), 227–244; ibid. 196 (1974), 351–370. MR 357660, DOI 10.1090/S0002-9947-1974-0357660-2
- J. McCammond and J. Rhodes, Geometric semigroup theory, Internat. J. Algebra Comput. (to appear).
- W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. (3) 29 (1974), 385–404. MR 360881, DOI 10.1112/plms/s3-29.3.385
- Hanna Neumann, Varieties of groups, Springer-Verlag New York, Inc., New York, 1967. MR 0215899, DOI 10.1007/978-3-642-88599-0
- G. A. Niblo, Separability properties of free groups and surface groups, J. Pure Appl. Algebra 78 (1992), no. 1, 77–84. MR 1154898, DOI 10.1016/0022-4049(92)90019-C
- Jean-Eric Pin, $\textbf {BG}=\textbf {PG}$: a success story, Semigroups, formal languages and groups (York, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 466, Kluwer Acad. Publ., Dordrecht, 1995, pp. 33–47. MR 1630617
- Jean-Eric Pin and Christophe Reutenauer, A conjecture on the Hall topology for the free group, Bull. London Math. Soc. 23 (1991), no. 4, 356–362. MR 1125861, DOI 10.1112/blms/23.4.356
- John Rhode and Benjamin Steinberg, Pointlike sets, hyperdecidability and the identity problem for finite semigroups, Internat. J. Algebra Comput. 9 (1999), no. 3-4, 475–481. Dedicated to the memory of Marcel-Paul Schützenberger. MR 1723478, DOI 10.1142/S021819679900028X
- John Rhodes and Benjamin Steinberg, Profinite semigroups, varieties, expansions and the structure of relatively free profinite semigroups, Internat. J. Algebra Comput. 11 (2001), no. 6, 627–672. MR 1880372, DOI 10.1142/S0218196701000784
- Luis Ribes and Pavel A. Zalesskii, On the profinite topology on a free group, Bull. London Math. Soc. 25 (1993), no. 1, 37–43. MR 1190361, DOI 10.1112/blms/25.1.37
- Luis Ribes and Pavel A. Zalesskii, The pro-$p$ topology of a free group and algorithmic problems in semigroups, Internat. J. Algebra Comput. 4 (1994), no. 3, 359–374. MR 1297146, DOI 10.1142/S021819679400004X
- Luis Ribes and Pavel Zalesskii, Pro-$p$ trees and applications, New horizons in pro-$p$ groups, Progr. Math., vol. 184, Birkhäuser Boston, Boston, MA, 2000, pp. 75–119. MR 1765118
- Luis Ribes and Pavel Zalesskii, Profinite groups, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 40, Springer-Verlag, Berlin, 2000. MR 1775104, DOI 10.1007/978-3-662-04097-3
- L. Ribes and P. A. Zalesskiĭ, Profinite Trees, Springer (to appear).
- Jean-Pierre Serre, Trees, Springer-Verlag, Berlin-New York, 1980. Translated from the French by John Stillwell. MR 607504, DOI 10.1007/978-3-642-61856-7
- John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
- Benjamin Steinberg, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra Comput. 8 (1998), no. 2, 203–234. With an addendum by the author. MR 1620343, DOI 10.1142/S0218196798000119
- Benjamin Steinberg, On algorithmic problems for joins of pseudovarieties, Semigroup Forum 62 (2001), no. 1, 1–40. MR 1832252, DOI 10.1007/PL00020979
- Benjamin Steinberg, Inevitable graphs and profinite topologies: some solutions to algorithmic problems in monoid and automata theory, stemming from group theory, Internat. J. Algebra Comput. 11 (2001), no. 1, 25–71. MR 1818661, DOI 10.1142/S0218196701000462
- Benjamin Steinberg, A delay theorem for pointlikes, Semigroup Forum 63 (2001), no. 3, 281–304. MR 1851812, DOI 10.1007/s002330010051
- Benjamin Steinberg, Finite state automata: a geometric approach, Trans. Amer. Math. Soc. 353 (2001), no. 9, 3409–3464. MR 1837243, DOI 10.1090/S0002-9947-01-02774-X
- Benjamin Steinberg, Polynomial closure and topology, Internat. J. Algebra Comput. 10 (2000), no. 5, 603–624. MR 1781850, DOI 10.1142/S0218196700000285
- Benjamin Steinberg, Inverse automata and profinite topologies on a free group, J. Pure Appl. Algebra 167 (2002), no. 2-3, 341–359. MR 1874549, DOI 10.1016/S0022-4049(01)00030-5
- B. Steinberg, $\rm PG=BG$: redux, Semigroups (Braga, 1999) World Sci. Publ., River Edge, NJ, 2000, pp. 181–190. MR 1895418
- B. Steinberg, The uniform word problem for groups and finite Rees quotients of $E$-unitary inverse semigroups, J. Algebra 266 (2003), 1–13.
- J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63 (1990), no. 1, 81–112. MR 1037695, DOI 10.1016/0022-4049(90)90057-O
- Bret Tilson, Categories as algebra: an essential ingredient in the theory of monoids, J. Pure Appl. Algebra 48 (1987), no. 1-2, 83–198. MR 915990, DOI 10.1016/0022-4049(87)90108-3
- Pascal Weil, Computing closures of finitely generated subgroups of the free group, Algorithmic problems in groups and semigroups (Lincoln, NE, 1998) Trends Math., Birkhäuser Boston, Boston, MA, 2000, pp. 289–307. MR 1750503
- P. A. Zalesskiĭ, Geometric characterization of free constructions of profinite groups, Sibirsk. Mat. Zh. 30 (1989), no. 2, 73–84, 226 (Russian); English transl., Siberian Math. J. 30 (1989), no. 2, 227–235. MR 997469, DOI 10.1007/BF00971377
- P. A. Zalesskiĭ and O. V. Mel′nikov, Subgroups of profinite groups acting on trees, Mat. Sb. (N.S.) 135(177) (1988), no. 4, 419–439, 559 (Russian); English transl., Math. USSR-Sb. 63 (1989), no. 2, 405–424. MR 942131, DOI 10.1070/SM1989v063n02ABEH003282
Additional Information
- K. Auinger
- Affiliation: Institut für Mathematik, Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria
- Email: karl.auinger@univie.ac.at
- B. Steinberg
- Affiliation: School of Mathematics and Statistics, Carleton University, Herzberg Laboratories, Ottawa, Ontario, Canada K1S 5B6
- MR Author ID: 633258
- Email: bsteinbg@math.carleton.ca
- Received by editor(s): September 28, 2002
- Received by editor(s) in revised form: March 13, 2003
- Published electronically: August 21, 2003
- Additional Notes: The authors gratefully acknowledge support from INTAS project 99–1224 Combinatorial and geometric theory of groups and semigroups and its applications to computer science. The second author was supported in part by NSF-NATO postdoctoral fellowship DGE-9972697, as well as by Praxis XXI scholarship BPD 16306 98, FCT through the Centro de Matemática da Universidade do Porto, and by the FCT and POCTI approved project POCTI/32817/MAT/2000 in participation with the European Community Fund FEDER. He was at the University of Porto when this work was performed.
- © Copyright 2003 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 356 (2004), 805-851
- MSC (2000): Primary 20E18, 20E08, 20M07, 20M18
- DOI: https://doi.org/10.1090/S0002-9947-03-03358-0
- MathSciNet review: 2022720