Unsolvability of the submonoid membership problem for a free nilpotent group of class $l\geq 2$ of a sufficiently large rank
- 作者: Roman'kov V.A.1
-
隶属关系:
- Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
- 期: 卷 87, 编号 4 (2023)
- 页面: 166-185
- 栏目: Articles
- URL: https://journals.rcsi.science/1607-0046/article/view/133924
- DOI: https://doi.org/10.4213/im9342
- ID: 133924
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
The paper gives an answer to the question of M. Lohrey and B. Steinberg about the solvability of the submonoid membership problem for a finitely generated nilpotent group. Namely, a finitely generated submonoid of a free nilpotent group of class $2$ of a sufficiently large rank $r$ is constructed, the membership problem for which is algorithmically unsolvable. This implies the existence of a submonoid with a similar property in any free nilpotent group of class $l \geq 2$ of rank $r$. The proof is based on the undecidability of Hilbert's 10th problem.
作者简介
Vitalii Roman'kov
Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Email: romankov48@mail.ru
Doctor of physico-mathematical sciences, Professor
参考
- A. Myasnikov, V. Shpilrain, A. Ushakov, Group-based cryptography, Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag, Basel, 2008, xvi+183 pp.
- A. Myasnikov, V. Shpilrain, A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, Math. Surveys Monogr., 177, Amer. Math. Soc., Providence, RI, 2011, xiv+385 pp.
- В. А. Романьков, Алгебраическая криптология, Изд-во Омского гос. ун-та, Омск, 2020, 261 с.
- С. И. Адян, В. Г. Дурнев, “Алгоритмические проблемы для групп и полугрупп”, УМН, 55:2(332) (2000), 3–94
- Г. А. Носков, В. Н. Ремесленников, В. А. Романьков, “Бесконечные группы”, Итоги науки и техн. Сер. Алгебра. Топол. Геом., 17, ВИНИТИ, М., 1979, 65–157
- В. Н. Ремесленников, В. А. Романьков, “Теоретико-модельные и алгоритмические вопросы теории групп”, Итоги науки и техн. Сер. Алгебра. Топол. Геом., 21, ВИНИТИ, М., 1983, 3–79
- В. А. Романьков, “Об алгоримических проблемах теории групп”, Вестн. Омского ун-та, 2017, № 2, 18–27
- Ch. F. Miller, III, “Decision problems in algebraic classes of groups (a survey)”, Word problems: decision problems and the Burnside problem in group theory, Dedicated to H. Neumann (Univ. California, Irvine, CA, 1969), Stud. Logic Found. Math., 71, North-Holland, Amsterdam, 1973, 507–523
- А. И. Мальцев, “О гомоморфизмах на конечные группы”, Уч. зап. Ивановского гос. пед. ин-та, 18:5 (1958), 49–60
- F. Bassino, I. Kapovich, M. Lohrey, A. Miasnikov, C. Nicaud, A. Nikolaev, I. Rivin, V. Shpilrain, A. Ushakov, P. Weil, Complexity and randomness in group theory. GAGTA book 1, De Gruyter, Berlin, 2020, xii+374 pp.
- M. Lohrey, “The rational subset membership problem for groups: a survey”, Groups St. Andrews 2013, London Math. Soc. Lecture Note Ser., 422, Cambridge Univ. Press, Cambridge, 2015, 368–389
- V. A. Roman'kov, “On the occurence problem for rational subsets of a group”, Комбинаторные и вычислительные методы в математике, Cб. науч. тр., ОмГУ, Омск, 1999, 235–242
- B. А. Романьков, Рациональные подмножества в группах, Изд-во Омского гос. ун-та, Омск, 2014, 176 с.
- R. H. Gilman, “Formal languages and infinite groups”, Geometric and computational perspectives on infinite groups (Minneapolis, MN, New Brunswick, NJ, 1994), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Amer. Math. Soc., Providence, RI, 1996, 27–51
- V. A. Roman'kov, “Polycyclic, metabelian or soluble of type $(mathrm{FP})_{infty}$ groups with Boolean algebra of rational sets and biautomatic soluble groups are virtually abelian”, Glasg. Math. J., 60:1 (2018), 209–218
- M. Benois, “Parties rationnelles du groupe libre”, C. R. Acad. Sci. Paris Ser. A, 269 (1969), 1188–1190
- S. Eilenberg, M. P. Schützenberger, “Rational sets in commutative monoids”, J. Algebra, 13:2 (1969), 173–191
- М. Ю. Недбай, “Проблема вхождения в рациональные подмножества конечно порожденных абелевых групп”, Вестн. Омского ун-та, 1999, № 3, 37–41
- Z. Grunschlag, Algorithms in geometric group theory, PhD thesis, Univ. of California, Berkeley, 1999, 127 pp.
- М. Ю. Недбай, “Проблема вхождения в рациональные подмножества свободного произведения групп”, Вестн. Омского ун-та, 2000, № 2, 17–18
- M. Lohrey, B. Steinberg, “Tilings and submonoids of metabelian groups”, Theory Comput. Syst., 48:2 (2011), 411–427
- Ю. В. Матиясевич, “Диофантово представление перечислимых предикатов”, Изв. АН СССР. Сер. матем., 35:1 (1971), 3–30
- Yu. V. Matijasevič, “Some purely mathematical results inspired by mathematical logic”, Logic, foundations of mathematics and computability theory, Proc. 5th internat. congr. logic, methodology and philos. of sci., Part I (Univ. Western Ontario, London, ON, 1975), Univ. Western Ontario Ser. Philos. Sci., 9, Reidel, Dordrecht, 1977, 121–127
- Y. Matijasevič, J. Robinson, “Reduction of an arbitrary Diophantine equation to one in 13 unknowns”, Acta Arith., 27 (1975), 521–553
- J. P. Jones, “Undecidable Diophantine equations”, Bull. Amer. Math. Soc. (N.S.), 3:2 (1980), 859–862
- T. Skolem, Diophantische Gleichungen, Ergeb. Math. Grenzgeb., 5, Springer, Berlin, 1938, 130 pp.
- В. А. Романьков, “Две проблемы о разрешимых и нильпотентных группах”, Алгебра и логика, 59:6 (2020), 719–733
- V. A. Roman'kov, “Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two”, Сиб. электрон. матем. изв., 19:1 (2022), 387–403
补充文件
