Неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени $l\geq 2$ достаточно большого ранга

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Дается ответ на вопрос М. Лори и Б. Стейнберга о разрешимости проблемы вхождения в подмоноиды конечно порожденной нильпотентной группы. А именно, строится конечно порожденный подмоноид свободной нильпотентной группы ступени $2$ достаточно большого ранга $r$, проблема вхождения в который алгоритмически неразрешима. Отсюда следует существование подмоноида с аналогичным свойством в любой свободной нильпотентной группе ступени $l \geq 2$ ранга $r$. Доказательство основывается на неразрешимости десятой проблемы Гильберта.Библиография: 28 наименований.

Об авторах

Виталий Анатольевич Романьков

Омский филиал Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Email: romankov48@mail.ru
доктор физико-математических наук, профессор

Список литературы

  1. A. Myasnikov, V. Shpilrain, A. Ushakov, Group-based cryptography, Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag, Basel, 2008, xvi+183 pp.
  2. 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.
  3. В. А. Романьков, Алгебраическая криптология, Изд-во Омского гос. ун-та, Омск, 2020, 261 с.
  4. С. И. Адян, В. Г. Дурнев, “Алгоритмические проблемы для групп и полугрупп”, УМН, 55:2(332) (2000), 3–94
  5. Г. А. Носков, В. Н. Ремесленников, В. А. Романьков, “Бесконечные группы”, Итоги науки и техн. Сер. Алгебра. Топол. Геом., 17, ВИНИТИ, М., 1979, 65–157
  6. В. Н. Ремесленников, В. А. Романьков, “Теоретико-модельные и алгоритмические вопросы теории групп”, Итоги науки и техн. Сер. Алгебра. Топол. Геом., 21, ВИНИТИ, М., 1983, 3–79
  7. В. А. Романьков, “Об алгоримических проблемах теории групп”, Вестн. Омского ун-та, 2017, № 2, 18–27
  8. 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
  9. А. И. Мальцев, “О гомоморфизмах на конечные группы”, Уч. зап. Ивановского гос. пед. ин-та, 18:5 (1958), 49–60
  10. 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.
  11. 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
  12. V. A. Roman'kov, “On the occurence problem for rational subsets of a group”, Комбинаторные и вычислительные методы в математике, Cб. науч. тр., ОмГУ, Омск, 1999, 235–242
  13. B. А. Романьков, Рациональные подмножества в группах, Изд-во Омского гос. ун-та, Омск, 2014, 176 с.
  14. 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
  15. 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
  16. M. Benois, “Parties rationnelles du groupe libre”, C. R. Acad. Sci. Paris Ser. A, 269 (1969), 1188–1190
  17. S. Eilenberg, M. P. Schützenberger, “Rational sets in commutative monoids”, J. Algebra, 13:2 (1969), 173–191
  18. М. Ю. Недбай, “Проблема вхождения в рациональные подмножества конечно порожденных абелевых групп”, Вестн. Омского ун-та, 1999, № 3, 37–41
  19. Z. Grunschlag, Algorithms in geometric group theory, PhD thesis, Univ. of California, Berkeley, 1999, 127 pp.
  20. М. Ю. Недбай, “Проблема вхождения в рациональные подмножества свободного произведения групп”, Вестн. Омского ун-та, 2000, № 2, 17–18
  21. M. Lohrey, B. Steinberg, “Tilings and submonoids of metabelian groups”, Theory Comput. Syst., 48:2 (2011), 411–427
  22. Ю. В. Матиясевич, “Диофантово представление перечислимых предикатов”, Изв. АН СССР. Сер. матем., 35:1 (1971), 3–30
  23. 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
  24. Y. Matijasevič, J. Robinson, “Reduction of an arbitrary Diophantine equation to one in 13 unknowns”, Acta Arith., 27 (1975), 521–553
  25. J. P. Jones, “Undecidable Diophantine equations”, Bull. Amer. Math. Soc. (N.S.), 3:2 (1980), 859–862
  26. T. Skolem, Diophantische Gleichungen, Ergeb. Math. Grenzgeb., 5, Springer, Berlin, 1938, 130 pp.
  27. В. А. Романьков, “Две проблемы о разрешимых и нильпотентных группах”, Алгебра и логика, 59:6 (2020), 719–733
  28. 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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Романьков В.А., 2023

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).