Logspace and compressed-word computations in nilpotent groups

Macdonald, Jeremy; Myasnikov, Alexei; Nikolaev, Andrey; Vassileva, Svetla

doi:10.1090/tran/8623

Logspace and compressed-word computations in nilpotent groups
HTML articles powered by AMS MathViewer

by Jeremy Macdonald, Alexei Myasnikov, Andrey Nikolaev and Svetla Vassileva PDF

Trans. Amer. Math. Soc. 375 (2022), 5425-5459 Request permission

Abstract:

For finitely generated nilpotent groups, we employ Mal’cev coordinates to solve several classical algorithmic problems efficiently. Computation of normal forms, the membership problem, the conjugacy problem, and computation of presentations for subgroups are solved using only logarithmic space and quasilinear time. Logarithmic space presentation-uniform versions of these algorithms are provided. Compressed-word versions of the same problems, in which each input word is provided as a straight-line program, are solved in polynomial time.

References

Gilbert Baumslag, Frank B. Cannonito, Derek J. Robinson, and Dan Segal, The algorithmic theory of polycyclic-by-finite groups, J. Algebra 142 (1991), no. 1, 118–149. MR 1125209, DOI 10.1016/0021-8693(91)90221-S
Norman Blackburn, Conjugacy in nilpotent groups, Proc. Amer. Math. Soc. 16 (1965), 143–148. MR 172925, DOI 10.1090/S0002-9939-1965-0172925-5
Khalid Bou-Rabee and Daniel Studenmund, Full residual finiteness growths of nilpotent groups, Israel J. Math. 214 (2016), no. 1, 209–233. MR 3540612, DOI 10.1007/s11856-016-1358-x
Inna Bumagin, Time complexity of the conjugacy problem in relatively hyperbolic groups, Internat. J. Algebra Comput. 25 (2015), no. 5, 689–723. MR 3384078, DOI 10.1142/S0218196715500162
Volker Diekert, Jonathan Kausch, and Markus Lohrey, Logspace computations in graph groups and Coxeter groups, LATIN 2012: theoretical informatics, Lecture Notes in Comput. Sci., vol. 7256, Springer, Heidelberg, 2012, pp. 243–254. MR 2979050, DOI 10.1007/978-3-642-29344-3_{2}1
Murray Elder, Gillian Elston, and Gretchen Ostheimer, On groups that have normal forms computable in logspace, J. Algebra 381 (2013), 260–281. MR 3030521, DOI 10.1016/j.jalgebra.2013.01.036
Edward Formanek, Conjugate separability in polycyclic groups, J. Algebra 42 (1976), no. 1, 1–10. MR 419608, DOI 10.1016/0021-8693(76)90021-1
Mikhael Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53–73. MR 623534
Fritz Grunewald and Daniel Segal, Some general algorithms. II. Nilpotent groups, Ann. of Math. (2) 112 (1980), no. 3, 585–617. MR 595207, DOI 10.2307/1971092
Philip Hall, The Edmonton notes on nilpotent groups, Queen Mary College Mathematics Notes, Queen Mary College, Mathematics Department, London, 1969. MR 0283083
Niko Haubold, Markus Lohrey, and Christian Mathissen, Compressed decision problems for graph products and applications to (outer) automorphism groups, Internat. J. Algebra Comput. 22 (2012), no. 8, 1240007, 53. MR 3010821, DOI 10.1142/S0218196712400073
Derek Holt, Markus Lohrey, and Saul Schleimer, Compressed decision problems in hyperbolic groups, 36th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 126, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, pp. Art. No. 37, 16. MR 3927752
Derek F. Holt and Sarah Rees, Solving the word problem in real time, J. London Math. Soc. (2) 63 (2001), no. 3, 623–639. MR 1825979, DOI 10.1017/S0024610701002083
Artur Jeż, Compressed membership for NFA (DFA) with compressed labels is in NP (P), 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 14, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2012, pp. 136–147. MR 2909309
M. I. Kargapolov and Ju. I. Merzljakov, Fundamentals of the theory of groups, Graduate Texts in Mathematics, vol. 62, Springer-Verlag, New York-Berlin, 1979. Translated from the second Russian edition by Robert G. Burns. MR 551207
M. I. Kargapolov, V. N. Remeslennikov, N. S. Romanovskiĭ, V. A. Roman′kov, and V. A. Čurkin, Algorithmic questions for $\sigma$-powered groups, Algebra i Logika 8 (1969), 643–659. MR 0283060
Daniel König and Markus Lohrey, Evaluating matrix circuits, Computing and combinatorics, Lecture Notes in Comput. Sci., vol. 9198, Springer, Cham, 2015, pp. 235–248. MR 3447256, DOI 10.1007/978-3-319-21398-9_{1}9
C. R. Leedham-Green and Leonard H. Soicher, Symbolic collection using Deep Thought, LMS J. Comput. Math. 1 (1998), 9–24. MR 1635719, DOI 10.1112/S1461157000000127
Richard J. Lipton and Yechezkel Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach. 24 (1977), no. 3, 522–526. MR 445901, DOI 10.1145/322017.322031
M. Lohrey and S. Schleimer, Efficient computation in groups via compression, Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007. Proceedings, Lecture Notes in Computer Science, vol. 4649, Springer Berlin / Heidelberg, 2007, pp. 249–258.
Markus Lohrey, Word problems on compressed words, Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 3142, Springer, Berlin, 2004, pp. 906–918. MR 2161070, DOI 10.1007/978-3-540-27836-8_{7}6
Markus Lohrey, Algorithms on SLP-compressed strings: a survey, Groups Complex. Cryptol. 4 (2012), no. 2, 241–299. MR 3043435, DOI 10.1515/gcc-2012-0016
Jeremy Macdonald, Compressed words and automorphisms in fully residually free groups, Internat. J. Algebra Comput. 20 (2010), no. 3, 343–355. MR 2658415, DOI 10.1142/S021819671000542X
Klaus Madlener and Friedrich Otto, Pseudonatural algorithms for the word problem for finitely presented monoids and groups, J. Symbolic Comput. 1 (1985), no. 4, 383–418. MR 849044, DOI 10.1016/S0747-7171(85)80022-5
Bohdan S. Majewski and George Havas, The complexity of greatest common divisor computations, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 184–193. MR 1322722, DOI 10.1007/3-540-58691-1_{5}6
A. I. Mal’cev, On homomorphisms onto finite groups, Transl., Ser. 2, Am. Math. Soc. 119 (1983), 67–79, Translation from Uch. Zap. Ivanov. Gos. Pedagog Inst. 18, 49–60 (1958).
A. G. Miasnikov and M. Sohrabi, Elementary bilinearization and coordinatization of finitely generated nilpotent groups, arXiv:1311.1391v3 [math.GR], 2016.
A. Włodzimierz Mostowski, Computational algorithms for deciding some problems for nilpotent groups, Fund. Math. 59 (1966), 137–152. MR 224694, DOI 10.4064/fm-59-2-137-152
Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov, The Post correspondence problem in groups, J. Group Theory 17 (2014), no. 6, 991–1008. MR 3276224, DOI 10.1515/jgth-2014-0022
Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov, Non-commutative lattice problems, J. Group Theory 19 (2016), no. 3, 455–475. MR 3510838, DOI 10.1515/jgth-2016-0506
Werner Nickel, Matrix representations for torsion-free nilpotent groups by Deep Thought, J. Algebra 300 (2006), no. 1, 376–383. MR 2228654, DOI 10.1016/j.jalgebra.2006.03.002
Wojciech Plandowski, Testing equivalence of morphisms on context-free languages, Algorithms—ESA ’94 (Utrecht), Lecture Notes in Comput. Sci., vol. 855, Springer, Berlin, 1994, pp. 460–470. MR 1328862, DOI 10.1007/BFb0049431
V. N. Remeslennikov, Conjugacy in polycyclic groups, Algebra i Logika 8 (1969), 712–725 (Russian). MR 0280593
Saul Schleimer, Polynomial-time word problems, Comment. Math. Helv. 83 (2008), no. 4, 741–765. MR 2442962, DOI 10.4171/CMH/142
Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. MR 1267733, DOI 10.1017/CBO9780511574702
Svetla Vassileva, Space and time complexity of algorithmic problems in groups, Ph.D. thesis, McGill University, Montreal, August 2013.