Содержание к диссертации
Введение
Глава 1. Уравнения в нильпотентных группах малой ступени 11
1.1 Уравнения с одной неизвестной в конечно определённых нильпотентных группах ступени 3 11
1.2 Уравнения с одной неизвестной в конечно определённых нильпотентных группах ступени 30
Глава 2. Уравнения в свободных шшпотентных группах 35
2.1 Уравнения в свободных нильпотентных группах ступени cv3 35
2.2 Некоторые технические леммы 44
2.3 Уравнения с одной неизвестной в свободных нильпотентных группах 61
Литература 80
- Уравнения с одной неизвестной в конечно определённых нильпотентных группах ступени
- Уравнения с одной неизвестной в конечно определённых нильпотентных группах ступени
- Некоторые технические леммы
- Уравнения с одной неизвестной в свободных нильпотентных группах
Введение к работе
Первые работы, посвященные алгоритгжческим проблемам для конечно-определённых нильпотентных групп, принадлежат А.И.Мальцеву и Р.Линдону. Ими построен алгоритм для распознавания равенства слов в конечно-определённых нильпотентных группах (см. 5} и [201 ). В дальнейшем, с помощью финитной апроксимируемости А.И.Мальцевым был построен алгоритм для распознавания вхождения в конечно-порождённые подгруппы конечно-определённых нильпотентных групп (см. 16] ). Блэкберн в работе \Ї5"І доказал финитную аіфоксішируемость относительно сопряжённости конечно-определённых нильпотентных групп. Это позволило ему построить алгоритм для распознавания сопряжённости в конечно-определённых нильпотентных группах. Недавно доказано, что в классе всех конечно-определённых нильпотентных групп положительно решается алгоритмическая проблема распознавания изоморфизма групп (см [161, [173 ). Многие алгоритмические проблемы получили положительное решение и в классах групп, являвдихся естественными обобщениями класса конечно-определённых нильпотентных групп (см.,например, [3] ).
Небезуспешными оказались и попытки отыскания алгоритмически неразрешимых проблем, связанных с конечно-определёнными нильпотентными группами. Так, А.И. Мальцевым в работе [73 была доказана алгоритмическая неразрешимость элементарной теории каждой неабелевои свободной нильпотентнои группы. В последствии, Ю.Л. Ершовым был даже найден необходимый и достаточный критерий алгоритмической неразрешимости элементарной теории конечно-определённой нильпотентнои группы. А именно, он показал, что элементарная теория конечно-определённой нильпотентнои группы разрешима тогда и только тогда, когда эта группа почти абелева (см. [23 ).
Однако, долгое время не удавалось найти никаких более простых алгоритмически неразрешимых проблем для конечно-определённых нильпотентных групп. Большое влияние на исследования в этой области оказало отрицательное решение Ю.В.Матвеевичем в 1970 году десятой проблемы Гильберта (см. 183 и [91 ). Появилась возможность применить восходящий к Мальцеву и Блэкберну ме.тод моделирования диофантовых уравнений в нильпотентных группах.
В Ї977 году В.А. Романькову удалось разыскать на этом пути естественную алгоритмически неразрешимую теоретико-групповую проблему. Оказалось, что для свободных нильпотентных групп счётного ранга и ступени > 9 алгоритмическая проблема распознавания эндоморфной сводимости элементов имеет отрицательное решение. Эта проблема состоит в построении алгоритма, который по двум произвольным элементам ^ и Ь, группы G- распознаёт наличие эндоморфизма ш & -». Gr » переводящего элемент g, в элемент К, .
Непосредственным следствием из этого результата является следующая теорема.
Теорема (В.А. Романьков, Ї977 г.). Для каждой свободной нильпотентнои группы счётного ранга и ступени с ^ 9 невозможен алгоритм, распознающий разрешимость уравнений.
В дальнейшем В.Г. Дурнев изучал вопросы распознавания разрешимости систем уравнений в свободных нильпотентных группах. Использовав метод моделирования систем диофанто-вых уравнений, он доказал (см. [1] ), что для каждой неабелевои свободной нильпотентнои группы невозможен алгоритм, распознающий разрешимость систем уравнений. В.Г. Дурнев также отметил, что из его результата вытекает алгоритмическая неразрешимость УУ,Э.. .В - фрагмента позитив-ной теории неабелевои свободной нильпотентнои группы. Здесь Ть -достаточно большое натуральное число. Этот результат несколько уточняет теорему Мальцева о неразрешимости элементарной теории свободной нильпотентнои группы.
Естественный путь отыскания более простых алгоритмически неразрешимых проблем для конечно-определённых нильпотентных групп состоит в рассмотрении каких-либо специальных классов уравнений в этих группах. Данная работа посвящена изучешпо проблем распознавания разрешимости уравнений с одной неизвестной в конечно-определённых нильпотентных группах. Работа состоит из двух глав. В первой главе исследуются вопросы распознавания разрешимости уравнении с одной неизвестной в конечно-определённых нильпотентных группах малых ступеней. Вторая глава посвящена изучению проблем распознавания разрешимости уравнений в свободных нильпотентных группах.
Уравнения с одной неизвестной в конечно определённых нильпотентных группах ступени
Теорема I. Существует конечно-определенная нильпотент-ная группа Q- ступени 3, для которой невозможен алгоритм, распознающий разрешимость уравнений с одной неизвестной. Доказательство теоремы Ї разбивается на несколько этапов. На первом этапе мы строїш некоторое вспомогательное семейство W \. й оіє S систем диофантовых уравнений, обладающее рядом специальных свойств. В частности, будет невозможен алгоритм, который распознаёт разрешимость систем диофантовых уравнений из \ в целых числах. На втором этапе, используя семейство \., мы построим группу С;. На следующем этапе по каждой системе диофантовых уравнений ei є ЇЛ мы определим некоторое уравнение с одной неизвестной W CXV у В группе Go И наконец, на последнем, четвертом этапе мы покажем, что система разрешима в целых числах тогда и только тогда, когда уравнение W GO = \. имеет решение в группе Gr . На этом доказательство теоремы I завершится. Пусть Р ( 1 эса,...., - полином с целыми коэффициентами, такой, что невозможен алгоритм, который по целому числу tL распознаёт наличие у уравнения целочисленного решения. Существование такого полинома дока зано Ю.В. Матиясевичем (см. 18} и \9] ). Построим по поли ному I? Сх«_, х у ) систему диофантовых уравнений состоит только из уравнений следующих четырех типов: Теперь, вводя новые переменные с достаточно большими номерами и новые равенства типа (с), можно добиться того, что в разные уравнения типов (а) и (в) входят неизвестные с различными номерами. Кроме того, можно считать, что неизвестные ...х упорядочены таким образом, что если в систему диофантовых уравнений входят уравнение 43- к. или уравнение осІ+Х±- асі , то 1& \с Далее, можно добиться того, что каждая переменная х , і і,...лл. не входит одновременно в равенства типа (с) и типа (д). Действительно, если некоторая переменная х-и входит в равенство х = Z. , г. с Z типа (д) и, одновременно, входит в некоторое равенство 4= 4 типа (с), то последнее равенство следует выкинуть и добавить к системе р равенство х; = Е типа (д).
После конечного числа таких операций мы придем к системе, в которой ни одна неизвестная не входит одновременно в равенства типа (с) и (д). Очевидно, можно считать, что если в системе Ъ имеется некоторое равенство ос L = х , то Uj .(Это условие не является ограничением). Кроме того, немного изменяя систему & , можно добиться того, что каждая неизвестная входит не более чем в два уравнения типа (с), причем, если она входит именно "в два уравнения, то в одно уравнение эта переменная входит справа, а во второе слева. (Например, если у нас имеется три равенства sXs, хз. аі? и я xu » то следует перейти к системе из равенств х.3 - 5, х5 = х , х? s ос .) К, наконец, можно считать, что каждая переменная xt входит только в одно уравнение типа (д). (Если какая-либо переменная входит в два таких уравнения, то либо одно уравнение лишнее, либо система Ь несовместна). Таким образом, можно считать, что система tx4,...j«.vt,i обладает следующими свойствами: I. Система состоит только из уравнений следующих четырех типов: П. Если в систему входят два различных уравнения Ev Ш. Каждая неизвестная ос , l = i,...,u. входит не более чем в два уравнения типа С, причем, если она входит именно в два таких уравнения, то в одно из них она входит справа, а во второе слева. 17.
Каждая переменная ос- , Cri,... входит не более чем в одно уравнение типа Д, причем, если она входит в уравнение типа Д, то уже не входит ни в одно уравнение типа С. Пусть теперь система А C j...... Л , ы с "Zi получается из системы $(х41...,х добавлением равенства oct= ot и (возможно) путем проведения описанных ранее преобразований, избавляющих полученную систему от одновременного вхождения переменных в равенства типа С и Д. Заметим, что каждая полученная система і ± будет обладать свойствами I - ІУ. Действительно, выполнимость свойств I - Ш не зависит от добавления в систему некоторого количества дополнительных равенств типа Д. Покажем, что выполнено свойство ІУ. Во-первых, отметим, что переменная ос± не может входить в равенства типа Д. Действительно, иначе существовал бы тривиальный алгоритм для распознавания по числу . разрешимости в целых числах уравнения (« ., ,...,06, о Если неизвестная хА не входит к тому же в равенства типа С, то, очевидно, добавление к системе S равенства хА= oL , к є Ж не нарушит выполнимости свойства ІУ. Если же неизвестная acL входит в какое-либо уравнение типа С, то система $Л получается, очевидно, из системы $ путем добавления некоторого количества равенств вида х , где 1 таково, что неизвестная ос в исходной системе р входаїла в равенства типа С, а тем самым, не входила в равенства типа Д.
Уравнения с одной неизвестной в конечно определённых нильпотентных группах ступени
Очевидно, что для любой конечно-определённой абелевой группы существует алгоритм, распознающий разрешимость уравнений. В этом параграфе будет доказано, что для любой конечно-определённой нильпотентной группы ступени 2 существует алгоритм, распознающий разрешимость уравнений с одной неизвестной. Существование такого алгоритма означает, что теорема і даёт точную оценку на минимальную ступень нильпотентности такую, что существуют конечно-определённые ниль-потентные группы данной ступени, для которых невозможен алгоритм, распознающий разрешимость уравнений с одной неизвестной. Пусть дана некоторая нильпотентная группа G- ступени 2: ft, - некоторое конечное множество определяющих соотношений. Опишем, как действует алгоритм, распознающий разрешимость уравнений с одной неизвестной в группе Gr. Предположим, что нам дано некоторое уравнение WQ -V1. Приведём вначале его к виду: ГДЄ »4» «Чи ЛІ»««-» 4v»fa.i «..уу-1НекотРые целые числа, ар- целое неотрицательное число. Очевидно, что это всегда можно сделать. Необходимым условием разрешимости этого уравнения в группе G- , является условие а4... 4, Ua CGT} . Проверить выполнимость этого условия можно эффективно. Если это окажется так, то переписав элемент (Х ... а в образующих to A ,...,LV vv- » мы придём к уравнению Заметим, что если у уравнения (9) имеется какое-либо решение G , то любой элемент смежного класса $"йаС( ) тоже будет решением этого уравнения. Поэтому достаточно определить наличие у уравнения (9) решений вида где осд,..., ос Z . Для таких значений X имеем: некоторые линейные функции с целыми коэфициентами. Коэфи-циенты этих функций легко находятся по целым числам N 4 ,. Таким образом, наша задача свелась к следующей: имеется некоторая конечно-определённая абелева группа А , в которой отмечены элементы &0 , 0 ,..., и даны некоторые линейные функции с целыми коэфициентами \. 1L- 1L , L = і ,...,wu . Требуется определить, существует ли такой ВеКТОр 2e"Z , ЧТО В нашем случае А - %±CG , t0 = Laz,a !".. ta_ ,a 1 ,Yl №«.,... ) \= Л-Л .Ч-Й Легко видеть, что подобная задача сводится к вопросу о разрешимости в целых числах некоторой системы линейных диойантовых уравнений. Пусть теперь р о и пусть
Положим . Ъ дз . Это целочисленная k v\, матрица. Предположим, что уравнение (7) имеет некоторое решение "X. в группе Gr. Пусть Элемент aA ...a группы Ct/ t(Q} будет решением уравнения X = 0. ...0- в этой группе. Поэтому вектор ос С 4.,..., ос будет удовлетворять равенству где KC A»." О , а ч. - некоторый вектор из , . Но тогда этот вектор ч будет являться решением сравнения Мц - (УПО О) . Следовательно, при некотором cLc вектор и можно представить в виде u«4 + od , где ч е "Z, -некоторое такое решение сравнения ґ\и c.-cL(w\o Lo) t j которого все координаты расположены в промежутке от 0 до p-i.. Подобных решений конечное число. Все их можно эффективно выписать. Обозначим их через » $1Ь" Итак, при некотором d.t и некотором Uti,... имеем равенство: Пусть ос = "о - Л х - целочисленный вектор. Это следует из того, что вектор является решением срав нения Ц -сСО оА-р) . сЛ Из равенство (10) вытекает, что аЛ ...ак = av... а в группе Ос / ъ х С Gr} . Следовательно, В таком случае, при некоторых целых чилах 2Д д,..., г , элемент "X. представляется в виде . Итак, доказано, что если уравнение (7) имеет какое-либо решение в группе Gc , то оно имеет решение следующего специального вида: Следовательно, уравнение (7) шлеет решение вида (її) в группе G- тогда и только тогда, когда существуют такие целые числа гг1 , ...,гич_ , что Таким образом, задача о разрешимости уравнения (7) в группе Q- сводится к задаче об извлечении корня -ой степени из некоторого элемента абелевой группы #_ ( . Эта задача, очевидно, тлеет алгоритмическое решение.
Некоторые технические леммы
В зависимости от того, какой из квадратов т. или C rv. ближе к числу W полагаем Ї = m либо і = m +1. Один из этих квадратов обязательно расположен блике к числу У, нежели другой вследствие того, что расстояние между двумя последовательными квадратами - число нечётное. Следовательно, Вернёмся к доказательству нашей леммы. Предположим, а. что. Возьмём в качестве ш\ л 3. - ближайший квадрат к числу (u -iHV4- - а\ ) Умеем: Лемма 2. Невозможен алгоритм, который по произвольному полиному p(x1,...,xu) , имеющему целые коэфи-циенты и степень $4= a,- 10s, распознаёт наличие таких целых чисел осА ,..., хЧ , что выполнены следующие равенства: Доказательство. Каждое натуральное число, и только натуральное число, можно представить в виде суммы трёх треугольных чисел. Поэтому второе уравнение системы (14) разрешимо в целых числах относительно г.,. , гг , z5 тогда и только тогда, когда целые числа осд_,...,ос1ч, ,. .., удовлетворяют неравенству: Или Но в силу леммы I, последнее неравенство разрешимо в целых числах относительно ,..., тогда и только тогда, когда ос О ,..., ocV4 О . Следовательно, система диофантовых уравнении (14) разрешима в целых числах тогда и только тогда, когда существуют такие целые положительные числа сс ,...,«:ц , что имеет место равенство: Известно (см. \18 \ и [19Q ), что существует универсальный для 4L, полином, имеющий 14 свободных переменных и степень 4 3--10 . Поэтому невозможен алгоритм, который по произвольному полиному тлеющему целые коэфициенты и степень 4 1-Ю , распознаёт наличие таких целых чисел х1,..., хїчє2і" \ что выполнено равенство 8(хХі...л х1ч -0 . Перед тем, как перейти к доказательству остальных лемм, мы введём ряд необходимых определений. Пусть "F = о,, t - абсолютно свободная группа ранга 2 на образующих о. и b . - свободная нилыютентная группа ранга 2 и ступени сь5-\о. Пусть t)v Dt -.. - последовательность всех базисных коммутаторов группы ТГ , начинающаяся с коммутатора C .ct ,&Д] , старшего коммутатора среди коммутаторов веса 4.
Начало этой последовательности имеет вид: В последовательности с01 , Ъг , Ъг ,... имеется один базисный коммутатор веса 4, 6 базисных коммутаторов веса 5, 9 базисных коммутаторов веса 6, Ї8 базисных комілутаторов веса 7 и 30 базисных коммутаторов веса 8. Всего в этой последовательности имеется 64 базисных коммутатора, вес которых не превышает 8. Пусть СА од_ - все те коммутаторы из последовательности Т ± , Т ,... , которые: а) Не превосходят коммутатора [Л.а.Ч .з! . б)
Отличны от коммутаторов (двух старших комму- таторов среди коммутаторов веса 6) и (четырёх старших коммутаторов среди коммутаторов веса 7). В последовательности С t , С..., С имеется один базисный коммутатор веса 4, 6 базисных коммутаторов веса 5, 7 базисных кошлутаторов веса 6, 14 базисных коммутаторов веса 7 и 3 базисных коммутатора веса 8. Определил следующую последовательность слов в алфавите Под весом слова L OO (обозначается ) будем понжіать вес коммутатора Ц 00 , рассматриваемого как элемент свободной группы на образующих аД и "X. . Имеют место следующие леммы. Лемма 3. Пусть o U ui , D - базисный коммутатор, 1 Ь\$8 , С ЯЬ . Тогда Ь С&) - базисный коммутатор веса iL Misl -і. . Кроме того, если шлеется некоторый базисный коммутатор "Е такой, что \"Е\4% , С "Е , то Доказательство. Будем доказывать эту лемму индукцией по числу V.. При \с = о утверждение лемглы очевидно. Пусть k = i . Тогда «Ь с4= їЛ.а.МЗ и Ъ - базисный комгдутатор, вес которого не выше 8. Следовательно D оканчивается коммутатором, вес которого не превышает 4. Но іЛ,а.ДДі является старшим комглутато- роы среди всех базисных кожяутаторов веса 4. Следовательно СЪ, t a.H.&li - базисный коммутатор. Его вес равен
Уравнения с одной неизвестной в свободных нильпотентных группах
Для доказательства теоремы мы построил по каждому полиному \?сх,,...,ос. л , имеющему целые коэшициенты ж сте-пень не превосходящую числа OL- 3.-10 , некоторое слово Wp С"К) в алфавите {ct, ь ,Х.\ такое, что уравнение шлеет решение в группе "Р тогда и только тогда, когда система диофантовых уравнений (14), построенная по полиному Р , шлеет целочисленное решение. В силу леммы 2, мы получим, что невозможен алгоритм, распознающий разрешимость уравнений с одной неизвесткой в свободной нильпотентной группе G = Л цС?); Любая нильпотентная группа ступени с неабелева. Это вытекает из определения ступени нильпотентности группы и того, что о 1 . Поэтому каждая свободная нильпотентная группа ступени с шлеет ранг не менее двух. А тогда утверждение теоремы 3 для всех подобных групп будет вытекать из невозможности алгоритгла, распознающего разрешимость уравнений с одной неизвестной в группе G- и из замечания, приведённого в конце 2.1 . С этого момента, для некоторого упрощения обозначений, мы будем считать, что ог чт ... 4 1 . В общем же случае следовало бы упорядочить коммутаторы аґ4 ,..., г31 по возрастанию: пґ 4 чґ 4 ... 4 tfj. , ив дальнейшем действовать в соответствии с этим порядком. Это не изменит ничего по существу,а только лишь усложнит обозначения. Слово WpC } будет иметь следующий вид: Слова ЧОХ) и V(X определяются в следующих двух подпунктах. ние базисных коммутаторов по modX . (JF) » содершіт более W al\ a букв і .
Доказательство. Элемент 1А.00 группы V является произведением элементов Ц.ЛХ і - 1,...1 «V По это-му достаточно доказать, что каждый базисный коммутатор, входящий в разложение какого-либо элемента IL (X) , содержит более \1д \ 8 букв & . А для этого достаточно од. доказать, что каждый коммутатор ІЛ.СХ , рассматриваемый как коммутатор в алфавите а , і ,Х j содержит более \UM\ t g букв % . То есть, что "b U X") ЦАЧ" Согласно лемме 10, слово R у Р содершіт не ме-нее 5,-1 буїш Ъ . Но при \с і Следовательно, в этом случае слово A 0 содершіт не ме-нее 3. -1 букв Ь . Но тогда любой базисный комглута-тор, входящий в разложение любого элемента вида Л,. 0 ), X ы видно, что коммутатор ЧГ.» , который, согласно лешле 9, совпадает с коммутатором v , входит в коммутатор игъ четыре раза. Поэтому имеет смысл следующее определение.
Пусть L= 2.1 Л& » V= It 2, 3, 4. Определим слово А- GO как результат подстановки в коммутатор т ъ1 вместо W левых вхождений подкоммутатора of слова А. (XV Если XeF , X=( \..C o UatV), хд у2, то согласно леммам 7 и 9 шлеш: Пусть многочлен u(xij...1oo " шлеет вид: Тогда можно считать, что второе уравнение системы диофан-товых уравнений (14) имеет вид: Представим многочлен СЦос. ,..,, . в ввде суммы одночленов: Кроме того, в калодыи одночлен входит не более одной неизвестной из множества ц »«»«»oc ai\ а каіКДая из неизвестных эсг9, хао, х вообще не входит в те одночлены, в которые входит какая-либо неизвестная, от неё отличная. Слово \АХ будет являться произведением слов V QC) : А каждое слово V-CW строится по одночлену fj.oc "... з 4" следующим образом. . -ь Случай I. В одночлен Р{ ч " аі входит в ненулевой степени неизвестная ос, , к- 27, 28. Слово Случай 2. В одночлен fi -" ъ входит в ненулевой степени неизвестная ос , \с- 30 , ЗІ. В этом слу-чае слово V? (X) будет иметь вид: Случай 3. В одночлен \\ х ... х 1 не ВХОдиТ в не_ нулевой степени ни одна из неизвестных X , Слово VCX) определено. Рассмотрим коммутатор Покажем, что это базисный коммутатор веса с . Действительно, коммутатор \_%,ъ.,Q ,c-wt-ал является базисным коммута-тором. Его вес равен c-wi i.s «лоа , что превьшает веса коммутаторов т ,..., tfi . Учитывая, что заключаем, что базисным является коммутатор
