Проблемы распознавания разрешимости уравнений в нильпотентных группах

Первые работы, посвященные алгоритмическим проблемам для конечно-определённых нильпотентных групп, принадлежат А. И. Мальцеву и Р.Линдону. Ими построен алгоритм для распознавания равенства слов в конечно-определённых нильпотентных группах (см. ?5} и [201). В дальнейшем, с помощью финитной алроксимируемости А. И. Мальцевым был построен алгоритм для распознавания вхождения в конечно-порождённые подгруппы конечно-определённых нильпотентных групп (см. 16]). Блэкберн в работе 15″ i доказал финитную апроксимируемость относительно сопряжённости конечно-определённых нильпотентных групп. Это позволило ему построить алгоритм для распознавания сопряжённости в конечно-определённых нильпотентных группах. Недавно доказано, что в классе всех конечно-определённых нильпотентных групп положительно решается алгоритмическая проблема распознавания изоморфизма групп (см [161, tI7]). Многие алгоритмические проблемы получили положительное решение и в классах групп, являвдихся естественными обобщениями класса конечно-определённых нильпотентных групп (см., например, [3]).

Небезуспешными оказались и попытки отыскания алгоритмически неразрешимых проблем, связанных с конечно-определёнными нильпотентньши группами. Так, А. И. Мальцевым в работе [7] была доказана алгоритмическая неразрешимость элементарной теории каждой неабелевой свободной нильпотентной группы. В последствии, Ю. Л. Ершовым был даже найден необходимый и достаточный критерий алгоритмической неразрешимости элементарной теории конечно-определённой нильпотентной группы. А именно, он показал, что элементарная теория конечно-определённой нильпотентной группы разрешима тогда и только тогда, когда эта группа почти абелева (см. [2]).

Однако, долгое время не удавалось найти никаких более простых алгоритмически неразрешимых проблем для конечно-определённых нильпотентных групп. Большое влияние на исследования в этой области оказало отрицательное решение Ю.В.Ма-тиясевичем в 1970 году десятой проблемы Гильберта (см. 183 и [91). Появилась возможность применить восходящий к Мальцеву и Блэкберну ме. тод моделирования диофантовых уравнений в нильпотентных группах.

В 1977 году В. А. Романькову удалось разыскать на этом пути естественную алгоритмически неразрешимую теоретико-групповую проблему. Оказалось, что для свободных нильпотентных групп счётного ранга и ступени > 9 алгоритмическая проблема распознавания эндоморфной сводимости элементов имеет отрицательное решение. Эта проблема состоит в построении алгоритма, который по двум произвольным элементам ^ и К группы Gраспознаёт наличие эндоморфизма (? • &^, переводящего элемент g, в элемент К, .

Непосредственным следствием из этого результата является следующая теорема.

Теорема (В.А. Романьков, 1977 г.). Для каждой свободной нильпотентной группы счётного ранга и ступени с ь 9 невозможен алгоритм, распознающий разрешимость уравнений.

В дальнейшем В. Г. Дурнев изучал вопросы распознавания разрешимости систем уравнений в свободных нильпотентных группах. Использовав метод моделирования систем диофанто-вых уравнений, он доказал (см. [1]), что для каждой неабе-левой свободной нильпотентной группы невозможен алгоритм, распознающий разрешимость систем уравнений. В. Г. Дурнев также отметил, что из его результата вытекает алгоритмическая неразрешимость VVJB. .В — фрашента позитив.

Yt ной теории неабелевой свободной нильпотентной группы. Здесь Ть — достаточно большое натуральное число. Этот результат несколько уточняет теорему Мальцева о неразрешимости элементарной теории свободной нильпотентной группы.

Естественный путь отыскания более простых алгоритмически неразрешимых проблем для конечно-определённых нильпотентных групп состоит в рассмотрении каких-либо специальных классов уравнений в этих группах. Данная работа посвящена изучению проблем распознавания разрешимости уравнений с одной неизвестной в конечно-определённых нильпотентных группах. Работа состоит из двух глав. В первой главе исследуются вопросы распознавания разрешимости уравнений с одной неизвестной в конечно-определённых нильпотентных группах малых ступеней. Вторая глава посвящена изучению проблем распознавания разрешилости уравнений в свободных нильпотентных группах.