The geometry of profinite graphs with applications to free groups and finite monoids

Auinger, K.; Steinberg, B.

doi:10.1090/S0002-9947-03-03358-0

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