×

The word and geodesic problems in free solvable groups. (English) Zbl 1207.20026

The computational complexity of the word problem in free solvable groups \(S_{r,d}\) of rank \(r\) and derived length \(d\) is studied for \(r,d\geq 2\). The procedures obtained are of smaller complexity than those derived from the Magnus embedding. It is shown, among other things, that the word problem in \(S_{r,2}\) has time complexity \(O(rn\log_2n)\); in \(S_{r,d}\) with \(d>2\) this is \(O(n^3rd)\).

MSC:

20F16 Solvable groups, supersolvable groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Jorge Almeida, Semidirect products of pseudovarieties from the universal algebraist’s point of view, J. Pure Appl. Algebra 60 (1989), no. 2, 113 – 128. · Zbl 0687.20053
[2] Zh. Almeĭda and P. Veĭl\(^{\prime}\), 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.
[3] K. Auinger and B. Steinberg, The geometry of profinite graphs with applications to free groups and finite monoids, Trans. Amer. Math. Soc. 356 (2004), no. 2, 805 – 851. · Zbl 1033.20028
[4] K. Auinger and B. Steinberg, A constructive version of the Ribes-Zalesskiĭ product theorem, Math. Z. 250 (2005), no. 2, 287 – 297. · Zbl 1074.20022
[5] K. Auinger and B. Steinberg, Constructing divisions into power groups, Theoret. Comput. Sci. 341 (2005), no. 1-3, 1 – 21. · Zbl 1077.68056
[6] Joan S. Birman, Braids, links, and mapping class groups, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1974. Annals of Mathematics Studies, No. 82. · Zbl 0297.57001
[7] Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. · Zbl 0844.05054
[8] Gary Chartrand and Ortrud R. Oellermann, Applied and algorithmic graph theory, International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1993. · Zbl 0611.05056
[9] David F. Cowan, A class of varieties of inverse semigroups, J. Algebra 141 (1991), no. 1, 115 – 142. · Zbl 0729.20025
[10] Richard H. Crowell and Ralph H. Fox, Introduction to knot theory, Springer-Verlag, New York-Heidelberg, 1977. Reprint of the 1963 original; Graduate Texts in Mathematics, No. 57. · Zbl 0362.55001
[11] CRyptography And Groups (CRAG) C++ Library, Available at http://www.acc.stevens. edu/downloads.php.
[12] Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. · Zbl 1074.05001
[13] Carl Droms, Jacques Lewin, and Herman Servatius, The length of elements in free solvable groups, Proc. Amer. Math. Soc. 119 (1993), no. 1, 27 – 33. · Zbl 0798.20026
[14] Anna Dyubina, Instability of the virtual solvability and the property of being virtually torsion-free for quasi-isometric groups, Internat. Math. Res. Notices 21 (2000), 1097 – 1101. · Zbl 0979.20034
[15] M. Elder, A polynomial-time algorithm to compute geodesic length in BS(1,p), in preparation.
[16] 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. · Zbl 0764.20017
[17] Anna Erschler, On drift and entropy growth for random walks on groups, Ann. Probab. 31 (2003), no. 3, 1193 – 1204. · Zbl 1043.60005
[18] Alex Eskin, David Fisher, and Kevin Whyte, Quasi-isometries and rigidity of solvable groups, Pure Appl. Math. Q. 3 (2007), no. 4, Special Issue: In honor of Grigory Margulis., 927 – 947. · Zbl 1167.22007
[19] Benson Farb and Lee Mosher, A rigidity theorem for the solvable Baumslag-Solitar groups, Invent. Math. 131 (1998), no. 2, 419 – 451. With an appendix by Daryl Cooper. · Zbl 0937.22003
[20] Benson Farb and Lee Mosher, Quasi-isometric rigidity for the solvable Baumslag-Solitar groups. II, Invent. Math. 137 (1999), no. 3, 613 – 649. · Zbl 0931.20035
[21] Ralph H. Fox, Free differential calculus. I. Derivation in the free group ring, Ann. of Math. (2) 57 (1953), 547 – 560. · Zbl 0050.25602
[22] Ralph H. Fox, Free differential calculus. II. The isomorphism problem of groups, Ann. of Math. (2) 59 (1954), 196 – 210. · Zbl 0055.01704
[23] Ralph H. Fox, Free differential calculus. III. Subgroups, Ann. of Math. (2) 64 (1956), 407 – 419. · Zbl 0073.25401
[24] Ralph H. Fox, Free differential calculus. V. The Alexander matrices re-examined, Ann. of Math. (2) 71 (1960), 408 – 422. · Zbl 0142.22305
[25] M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32 (1977), no. 4, 826 – 834. · Zbl 0396.05009
[26] Mikhael Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53 – 73. · Zbl 0474.20018
[27] Mikhael Gromov, Infinite groups as geometric objects, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983) PWN, Warsaw, 1984, pp. 385 – 392. · Zbl 0599.20041
[28] K. W. Gruenberg, Residual properties of infinite soluble groups, Proc. London Math. Soc. (3) 7 (1957), 29 – 62. · Zbl 0077.02901
[29] Narain Gupta, Free group rings, Contemporary Mathematics, vol. 66, American Mathematical Society, Providence, RI, 1987. · Zbl 0641.20022
[30] M. Hanan, On Steiner’s problem with rectilinear distance, SIAM J. Appl. Math. 14 (1966), 255 – 265. · Zbl 0151.33205
[31] Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. · Zbl 1044.55001
[32] V. A. Kaĭmanovich and A. M. Vershik, Random walks on discrete groups: boundary and entropy, Ann. Probab. 11 (1983), no. 3, 457 – 490. · Zbl 0641.60009
[33] M. I. Kargapolov and V. N. Remeslennikov, The conjugacy problem for free solvable groups, Algebra i Logika Sem. 5 (1966), no. 6, 15 – 25 (Russian). · Zbl 0249.20017
[34] Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85 – 103.
[35] O. G. Harlampovič, A finitely presented solvable group with unsolvable word problem, Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852 – 873, 928 (Russian). · Zbl 0485.20023
[36] O. G. Kharlampovich and M. V. Sapir, Algorithmic problems in varieties, Internat. J. Algebra Comput. 5 (1995), no. 4-5, 379 – 602. · Zbl 0837.08002
[37] Wilhelm Magnus, On a theorem of Marshall Hall, Ann. of Math. (2) 40 (1939), 764 – 768. · Zbl 0022.31403
[38] Stuart W. Margolis and John C. Meakin, \?-unitary inverse monoids and the Cayley graph of a group presentation, J. Pure Appl. Algebra 58 (1989), no. 1, 45 – 76. · Zbl 0676.20037
[39] S. W. Margolis, J. C. Meakin, and J. B. Stephen, Free objects in certain varieties of inverse semigroups, Canad. J. Math. 42 (1990), no. 6, 1084 – 1097. · Zbl 0726.20040
[40] Jane Matthews, The conjugacy problem in wreath products and free metabelian groups, Trans. Amer. Math. Soc. 121 (1966), 329 – 339. · Zbl 0136.27602
[41] John Milnor, Growth of finitely generated solvable groups, J. Differential Geometry 2 (1968), 447 – 449. · Zbl 0176.29803
[42] Lee Mosher, Michah Sageev, and Kevin Whyte, Quasi-actions on trees. I. Bounded valence, Ann. of Math. (2) 158 (2003), no. 1, 115 – 164. · Zbl 1038.20016
[43] W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. (3) 29 (1974), 385 – 404. · Zbl 0305.20033
[44] Hanna Neumann, Varieties of groups, Springer-Verlag New York, Inc., New York, 1967. · Zbl 0251.20001
[45] Walter Parry, Growth series of some wreath products, Trans. Amer. Math. Soc. 331 (1992), no. 2, 751 – 759. · Zbl 0793.20034
[46] V. N. Remeslennikov, Certain properties of the Magnus embedding, Algebra i Logika 8 (1969), pp. 72-76.
[47] V. N. Remeslennikov and N. S. Romanovskiĭ, Algorithmic problems for solvable groups, Word problems, II (Conf. on Decision Problems in Algebra, Oxford, 1976), Stud. Logic Foundations Math., vol. 95, North-Holland, Amsterdam-New York, 1980, pp. 337 – 346.
[48] V. N. Remeslennikov and V. G. Sokolov, Certain properties of the Magnus imbedding, Algebra i Logika 9 (1970), 566 – 578 (Russian).
[49] 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. · Zbl 1026.20057
[50] A. L. Shmel\( '\)kin, Wreath products and group varities, Izvestiya AN SSSR, seriya matematika, 29 (1965), pp. 149-176.
[51] I. M. Singer and John A. Thorpe, Lecture notes on elementary topology and geometry, Scott, Foresman and Co., Glenview, Ill., 1967. · Zbl 0163.44302
[52] A. M. Vershik, Geometry and dynamics on the free solvable groups, preprint. Erwin Schroedinger Institute, Vienna, 1999, pp. 1-16.
[53] A. M. Vershik, Dynamic theory of growth in groups: entropy, boundaries, examples, Uspekhi Mat. Nauk 55 (2000), no. 4(334), 59 – 128 (Russian, with Russian summary); English transl., Russian Math. Surveys 55 (2000), no. 4, 667 – 733. · Zbl 0991.37005
[54] A. M. Vershik and S. V. Dobrynin, Geometrical approach to the free solvable groups, Internat. J. Algebra Comput. 15 (2005), no. 5-6, 1243 – 1260. · Zbl 1104.20034
[55] B. A. F. Wehrfritz, Two examples of soluble groups that are not conjugacy separable, J. London Math. Soc. (2) 7 (1973), 312 – 316. · Zbl 0272.20048
[56] B. A. F. Wehrfritz, Another example of a soluble group that is not conjugacy separable, J. London Math. Soc. (2) 14 (1976), no. 2, 381 – 382. · Zbl 0341.20036
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.