Algorithmically complex residually finite groups. (English) Zbl 1423.20022
Summary: We construct the first examples of algorithmically complex finitely presented residually finite groups and the first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn functions, and arbitrarily large depth functions. The groups are solvable of class 3.
MSC:
| 20E26 | Residual properties and generalizations; residually finite groups |
| 20F05 | Generators, relations, and presentations of groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F16 | Solvable groups, supersolvable groups |
References:
| [1] | Agol, I.: The virtual Hacken conjecture (with an appendix by I. Agol, D. Groves and J. Manning), arXiv:1204.2810, (2012) · Zbl 0423.20038 |
| [2] | Baumslag, G.: A non-cyclic one-relator group all of whose finite factor groups are cyclic. J. Aust. Math. Soc. 10, 497-498 (1969) · Zbl 0214.27402 · doi:10.1017/S1446788700007783 |
| [3] | Baumslag, G.: Subgroups of finitely presented metabelian groups. J. Aust. Math. Soc. Ser. A 16(1), 98-110 (1973) · Zbl 0287.20027 · doi:10.1017/S1446788700013987 |
| [4] | Baumslag, G., Miller III, C.F., Short, H.: Isoperimetric inequalities and the homology of groups. Invent. Math. 113(3), 531-560 (1993) · Zbl 0829.20053 · doi:10.1007/BF01244317 |
| [5] | Baumslag, G., Roseblade, J.E.: Subgroups of direct products of free groups. J. Lond. Math. Soc. 30, 44-52 (1984) · Zbl 0559.20018 · doi:10.1112/jlms/s2-30.1.44 |
| [6] | Borisov, A., Sapir, M.: Polynomial maps over finite fields and residual finiteness of mapping tori of group endomorphisms. Invent. Math. 160(2), 341-356 (2005) · Zbl 1083.14023 · doi:10.1007/s00222-004-0411-2 |
| [7] | Borisov, A., Sapir, M.: Polynomial maps over p-adics and residual properties of mapping tori of group endomorphisms. Int. Math. Res. Not. IMRN 16, 3002-3015 (2009) · Zbl 1183.20031 |
| [8] | Birget, J.-C.: Infinite string rewriting systems and complexity. J. Symb. Comput. 25(6), 759-793 (1998) · Zbl 0983.68089 · doi:10.1006/jsco.1997.0198 |
| [9] | Bou-Rabee, K.: Quantifying residual finiteness. J. Algebra 323, 729-737 (2010) · Zbl 1222.20020 · doi:10.1016/j.jalgebra.2009.10.008 |
| [10] | Brady, N., Dison, W., Riley, T.: Hyperbolic hydra. Groups Geom. Dyn. 7(4), 961-976 (2013) · Zbl 1318.20041 · doi:10.4171/GGD/212 |
| [11] | Bridson, M., Haefliger, A.: Metric Spaces of Non-Positive Curvature. Springer, Berlin (1999) · Zbl 0988.53001 · doi:10.1007/978-3-662-12494-9 |
| [12] | Cohen, D.E.: Combinatorial Group Theory: A Topological Approach. London Mathematical Society Student Texts, 14. Cambridge University Press, Cambridge (1989) · Zbl 0697.20001 |
| [13] | Davis, M.D.: A note on universal Turing machines. Automata studies, Annals of Mathematics Studies, no. 34, pp. 167-175. Princeton University Press, Princeton (1956) · Zbl 0104.02101 |
| [14] | Dison, W., Riley, T.: Hydra groups. Comment. Math. Helv. 88(3), 507-540 (2013) · Zbl 1305.20052 · doi:10.4171/CMH/294 |
| [15] | Dyson, V.H.: A family of groups with nice word problems. Collection of articles dedicated to the memory of Hanna Neumann, VIII. J. Aust. Math. Soc. 17, 414-425 (1974) · Zbl 0304.02018 · doi:10.1017/S144678870001805X |
| [16] | Ershov, M.: Golod-Shafarevich groups: a survey. Int. J. Algebra Comput. 22(5), 1230001 (2012) · Zbl 1286.20033 · doi:10.1142/S0218196712300010 |
| [17] | Farb, B.: The extrinsic geometry of subgroups and the generalized word problem. Proc. Lond. Math. Soc. 68(3), 577-593 (1994) · Zbl 0816.20032 · doi:10.1112/plms/s3-68.3.577 |
| [18] | Gersten, S.M.: Dehn functions and l1-norms of finite presentations. Algorithms and Classification in Combinatorial Group Theory, pp. 195-225. Springer, Berlin (1992) · Zbl 0789.68074 |
| [19] | Gersten, S.M.: Isoperimetric and isodiametric functions of finite presentations. Geometric Group Theory, vol. 1 (Sussex, 1991), pp. 79-96, London Math. Soc. Lecture Note Ser., 181, Cambridge University Press, Cambridge (1993) · Zbl 0829.20054 |
| [20] | Gersten, S.M., Riley, T.R.: Some duality conjectures for finite graphs and their group theoretic consequences. Proc. Edinb. Math. Soc. 48(2), 389-421 (2005) · Zbl 1089.20017 · doi:10.1017/S0013091503000890 |
| [21] | Grigorchuk, R.: Groups with intermediate growth functions and their applications, Doctor’s Thesis (Russian), Moscow Steklov Mathematical Institute (1985) · Zbl 0816.20032 |
| [22] | Golubov, E.A.: Finite separability in semigroups. Dokl. Akad. Nauk SSSR 189, 20-22 (1969) · Zbl 0209.32403 |
| [23] | Gurevich, Y.S.: The problem of equality of words for certain classes of semigroups. Algebra i Log. Sem. 5(5), 25-35 (1966) · Zbl 0178.32501 |
| [24] | Higman, G.: Subgroups of finitely presented groups. Proc. R. Soc. Ser. A 262, 455-475 (1961) · Zbl 0104.02101 · doi:10.1098/rspa.1961.0132 |
| [25] | Hsu, T., Wise, D.: Cubulating graphs of free groups with cyclic edge groups. Amer. J. Math. 132(5), 1153-1188 (2010) · Zbl 1244.20040 · doi:10.1353/ajm.2010.0004 |
| [26] | Kassabov, M., Matucci, F.: Bounding the residual finiteness of free groups. Preprint, arXiv · Zbl 1230.20045 |
| [27] | Kassabov, M., Nikolov, N.: Generation of polycyclic groups. J. Group Theory 12(4), 567-577 (2009) · Zbl 1180.20028 · doi:10.1515/JGT.2008.098 |
| [28] | Kharlampovich, O.G.: Finitely presented solvable group with unsolvable word problem. Sov. Math. Izvest. 45(4), 852-873 (1981) · Zbl 0485.20023 |
| [29] | Kharlampovich, O.G.: The word problem for groups and Lie algebras, Doctor’s Thesis (Russian), Moscow Steklov Mathematical Institute (1990) · Zbl 0702.20024 |
| [30] | Kharlampovich, O.G.: The universal theory of the class of finite nilpotent groups is undecidable. Mat. Zametki 33(4), 499-516 (1983) · Zbl 0516.20018 |
| [31] | Kharlampovich, O.G., Sapir, M.V.: A non-residually finite, relatively finitely presented group in the variety \[\mathfrak{N}_2\mathfrak{A}\] N2A. Combinatorial and Geometric Group Theory (Edinburgh, 1993), pp. 184-189, London Math. Soc. Lecture Note Ser., 204, Cambridge Universiy Press, Cambridge (1995) · Zbl 0843.20019 |
| [32] | Kharlampovich, O., Sapir, M.: Algorithmic problem in varieties. Int. J. Algebra Comput. 5(4-5), 379-602 (1995) · Zbl 0837.08002 · doi:10.1142/S0218196795000227 |
| [33] | Kourovskaja tetrad’ (Unsolved Problems in Group Theory), 5th edn. Novosibirsk, (1976) |
| [34] | Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. Assoc. Comput. Mach. 24, 522-526 (1977) · Zbl 0359.68049 · doi:10.1145/322017.322031 |
| [35] | Malcev, A.I.: Algorithms and Recursive Functions. Nauka, Moscow (1965) |
| [36] | Malcev, A.I.: On Homomorphisms onto finite groups (Russian). Uchen. Zap. Ivanovskogo Gos. Ped. Inst. 18 (1958), pp. 49-60. English translation in: Amer. Math. Soc. Transl. Ser. 2, 119, pp. 67-79 (1983) · Zbl 1293.20041 |
| [37] | McKenzie, R., Thompson, R.J.: An elementary construction of unsolvable word problems in group theory. Word problems: decision problems and the Burnside problem in group theory (Conf., Univ. California, Irvine, Calif. 1969; dedicated to Hanna Neumann), Studies in Logic and the Foundations of Math., 71, p. 457478. Amsterdam (1973) · Zbl 0286.02047 |
| [38] | Meskin, S.: A finitely generated residually finite group with an unsolvable word problem. Proc. Am. Math. Soc. 43(1), 8-10 (1974) · Zbl 0261.20020 · doi:10.1090/S0002-9939-1974-0335645-5 |
| [39] | Madlener, K., Otto, F.: Pseudonatural algorithms for the word problem for finitely presented monoids and groups. J. Symb. Comput. 1(4), 383-418 (1985) · Zbl 0591.20038 · doi:10.1016/S0747-7171(85)80022-5 |
| [40] | McKinsey, J.: The decision problem for some classes of sentences without quantifiers. J. Symb. Log. 8, 61-76 (1973) · Zbl 0063.03864 · doi:10.2307/2268172 |
| [41] | Miasnikov, A., Ushakov, A., Won, D.: The word problem in Baumslag group is polynomial time decidable. J. Algebra 345, 324-342 (2011) · Zbl 1248.20038 · doi:10.1016/j.jalgebra.2011.07.024 |
| [42] | Mikhailova, K.A.: The occurrence problem for direct products of groups. Dokl. Akad. Nauk SSSR 119, 1103-1105 (1958) · Zbl 0084.25302 |
| [43] | Neumann, H.: Varieties of Groups. Springer, Berlin (1967) · Zbl 0149.26704 · doi:10.1007/978-3-642-88599-0 |
| [44] | Nikolov, N., Segal, D.: Finite index subgroups in pro-finite groups. C. R. Math. Acad. Sci. Paris 337(5), 303-308 (2003) · Zbl 1033.20029 · doi:10.1016/S1631-073X(03)00349-2 |
| [45] | Ollivier, Y., Wise, D.T.: Cubulating random groups at density less than 1/6. Trans. Am. Math. Soc. 363(9), 4701-4733 (2011) · Zbl 1277.20048 · doi:10.1090/S0002-9947-2011-05197-4 |
| [46] | Olshanskii, AYu.: Almost every group is hyperbolic. Int. J. Algebra Comput. 2(1), 1-17 (1992) · Zbl 0779.20016 · doi:10.1142/S0218196792000025 |
| [47] | Olshanskii, A., Sapir, M.: Length and area functions on groups and quasi-isometric Higman embeddings. Int. J. Algebra Comput. 11, 137-170 (2001) · Zbl 1025.20030 · doi:10.1142/S0218196701000401 |
| [48] | Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Publishing Company, Reading (1994) · Zbl 0833.68049 |
| [49] | Pueschel, K.: Hydra group doubles are not residually finite, arXiv:1507.02554 · Zbl 1352.20032 |
| [50] | Platonov, A.N.: An isoperametric function of the Baumslag-Gersten group. Vestnik Moskov. Univ. Ser. I Mat. Mekh. 2004, no. 3, pp. 12-17, translation in Moscow Univ. Math. Bull. 59 (2004), no. 3, p. 1217 (2005) · Zbl 1084.20022 |
| [51] | Remeslennikov, V.: Studies on infinite solvable and finitely approximable groups. Mat. Zametki 17(5), 819-824 (1975) |
| [52] | Remak, R.: Uber der Zerlegung der endlichen Gruppen in direkte unzerlegbare Faktoren. J. Reine Angew. Math. 139, 293308 (1911) · JFM 42.0156.01 |
| [53] | Rips, E.: Subgroups of small cancellation groups. Bull. Lond. Math. Soc. 14, 45-47 (1982) · Zbl 0481.20020 · doi:10.1112/blms/14.1.45 |
| [54] | Rotman, J.J.: An Introduction to the Theory of Groups, 4th edn. Graduate Texts in Mathematics, 148. Springer, New York (1995) · Zbl 0810.20001 |
| [55] | Sapir, M.: Algorithmic problems in varieties of semigroups. Algebra i Logika 27(4), 440-463 (1988) · Zbl 0683.20048 · doi:10.1007/BF01978400 |
| [56] | Sapir, M.: Weak word problem for finite semigroups. Monoids and Semigroups with Applications (Berkeley, CA, 1989), pp. 206-219. World Science Publisher, River Edge (1991) · Zbl 0795.20047 |
| [57] | Sapir, M.: Asymptotic invariants, complexity of groups and related problems. Bull. Math. Sci. 1(2), 277-364 (2011) · Zbl 1293.20041 · doi:10.1007/s13373-011-0008-1 |
| [58] | Sapir, M.: Minsky machines and algorithmic problems, accepted in Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday, LNCS. Springer, Berlin (2015) · Zbl 1465.03077 |
| [59] | Sapir, M., Birget, J.C., Rips, E.: Isoperimetric and isodiametric functions of groups. Ann. Math. 156(2), 345-466 (2002) · Zbl 1026.20021 · doi:10.2307/3597195 |
| [60] | Slobodskoi, A.M.: Undecidability of the universal theory of finite groups. Algebra Log. 20(2), 207-230 (1981) · Zbl 0519.03006 · doi:10.1007/BF01735740 |
| [61] | Waack, St: On the parallel complexity of linear groups. RAIRO Inform. Theor. Appl. 25, 323-354 (1991) · Zbl 0789.68074 · doi:10.1051/ita/1991250403231 |
| [62] | Wehrfritz, B.A.F.: On finitely generated soluble linear groups. Math. Z. 170(2), 155-167 (1980) · Zbl 0423.20038 · doi:10.1007/BF01214771 |
| [63] | Wise, D.T.: The structure of groups with a quasiconvex hierarhy. Preprint (2011) · Zbl 0423.20038 |
| [64] | Wise, D.T.: A residually finite version of Rips’s construction. Bull. Lond. Math. Soc. 35(1), 23-29 (2003) · Zbl 1027.20014 · doi:10.1112/S0024609302001406 |
| [65] | Zel’manov, E.I.: The solution of the restricted Burnside problem for groups of odd exponent. Izv. Akad. Nauk. SSSR. Ser. Mat., 54(1), 42-59 (1990). Transl. in Math. USSR-Izv. 36(1), 41-60 (1991) · Zbl 0709.20020 |
| [66] | Zel’manov, E.I.: The solution of the restricted Burnside problem for 2-groups. Mat. Sb. 182(4), 568-592 (1991) · Zbl 0752.20017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
