Алгоритмические проблемы для многообразий групп тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

'ОД

о

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕЗОЛЮЦИЙ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНЛШНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ кюнв И. В. ЛОМОНОСОВА ЖШ'ЖО-МАТКЛА'ПЖСКуЙ ФАКУЛЬТЕТ

На пели ах рукэпяся .ШОХИН УЛШЛ ИГОРЕВИЧ

УДК 512.54.05 АЛГОШТ^ЧЕСКИЕ ПРОБЛЕМ ДЛЯ ИОГООБРАБКЙ ГРУПП 01.01.05 - катоматнчвсяая логика., алгебра я теория члсол

А В Т О Р £ С ЕРАТ доссэртацпп соискапкз ученой степени кандидата фзз ако-гат&иасичэсгтах паук

HoortBa - 1993

Работа выполнена ка кафэдро высшей алгебры иоханлхо-ма-тематнчоского факультета Московского государственного университета емонл Н. В. Ломоносова.

Научный руководитель - доктор фазкхо-матецаткческих пауп,

профессор А. Л. Сьэлькан. Официалыша оппоненты - доктор фязнко-матаиатячосхнх наук,

профэссор В. К. Сущанскнй; кандидат фнзкко-штозгатачвсгаа наук, доцзкт А. Е. Красильнгков. Ведущая организация - Омский государственный университет.

Задата диссертация состоятся 1993 г. в 16 ч. 05 млн. на еасодании Сшцашшакроаанного сово-та Д.053.05.05 прз Московском государственном университета ни. М. В. Ло?40носовй по адресу: 1198S9, ГСП, Москва, Лопккскав горы, ИТ, кехяниг.о-катематичоскяЁ факультет, аудаторня 14-08.

С диссертацией ыояно 'ознакогаться в би&шотакэ ыэханяко-иатематического факультета !ЯУ (Главное зданий,. 14 атах).

Автореферат разослан

19 ■ ШМАЛ^^Л 1993 г.

Учзннй секретарь Спецзализнрованного совете. Д.053.06.05 пр;; ЩГУ, доктор

фпзихо-матёыатачосЕнх ноу^, профессор В. Е. 4ydapsi:o3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность ts'*'h. Алгоряг-ляческиэ проблемы теоряя групп подвергались ннт-знстьнс'^у кзучеггш) п тачание долгого врзкеня (см., например, обзоры [1, § 7; 2, гл. 1; 3]). Однако этя про-блз?.а псслэдоваллсь в оснозксм для групп, заданных конэчннм число» пороадавоях з опрздзл.ашх ссотнсгюяяЗ (конечно определенных (к. о.) групп), з таг-стэ для протпзолънях конечно порождению: групп. Кои&чно дороддонныэ свободные группы конечно Са-ятруог;?jx глтогос ЗрагпЛ бо многих случаях ко являются к. о., но для них суцостзуе? естественный способ эадшгая конечным числом порозданцях з то:глостб2ян1гс соотношений (т. э. базисом тождеств соотвогстззупгого многообразия). Диссертация большей часты) посвяцона пзучонзв атгорптмичоскях проблем для групп, заданных конечным чдслсм поровджцях з тоздэственннх соотношения (конечно оадаягшх тоддоствгт? (к. я. т.) групп), а тага» для групп, я. о. т. в нэкогорсн многообразен я для конечно базяру-сс (к. б.) многообразий групп. В этом направлении мезнэ от-

1. Г. А. Нссксз, Б. Н. Рэизсленниксв, В. А. Рсманысов. Бесконечно грушн // Итоги: науки а тэта. Алгебра. Топология. Твстття, ■?. 17, с. 65-157. - П.: ВИНИТИ, 1979.

2. В. К. Реиэслйапзкоз, В. А. Ромгнысов. Теоретико-модельные и алгоритмические вопроси теорггя групп // Итога науки и тхя. Алгебра. Топология. Гэокатрия, т. 21, с. 3-79. -ГЛ.: ВИНИТИ, 1S83.

3. Л. А. Еокуть, Г. П. Кукпи. Кзразрешнмнв алгорзтмячэсхяв проблема для полугрупп, групп з г.олац // Итога наукп и тохк. Алгебра. Топология. Гескетрия, т. 25, с. 3-66. -Е.:• ВИНИТИ, 1S07.

метять иэвастшй результат П. Г. Клеймана [4] о существовании 2-порожденной 6 7-ступанио разрешимой к. з. т. группы, в которой проблема равенства неразрешима. Из существования такой группы следует существование тождества, проблема распознавания следствий которого алгоритмически неразрешима. В £4] доказало

I

также существование такого тождества Ы = 1. , что на существует алгоритма, выясняющего по произвольному тождеству, является ли Ы = 1 его следствием. Позднее С. В. Айвазян [53, используя метод Клеймана, построил 4 5-ступвнно разрешимую 2-порсвденную к. з. т. группу с неразрешимой проблемой равенства.

В диссертация изучается следувдив алгоритмические проблемы.

1. Цустъ ! I - некоторый класс конечных заданий групп, а Р - некоторое абстрактное теоретико-групповое свойство. Существует лн алгоряти, опрвделялаий по произвольному заданна из Г1 , обладает ли соответствуюдая группа свойством Р ? Другими словаки, распознаваемо лк свойство Р в классе групп, определявши заданаямя кз П ?

2. Пусть 3 - некоторый класс конечных систем тождеств, а Р - некоторое свойство многообразий групп. Существует ля алгоритм, вняснявдп® по произвольно!! система аз

3 , обладает лк определяемое ой многообразна свойсгвоа ? Другими словами, распознаваемо т свойство в

4. С. Г. Клейман. О тождествах в группах // Тр. ¡Зоек. иат. о-ва, 1982, т. 44, с. 62-108.

5. С. В. Айвазян. Об одной проблош А. К. Мальцева // Сиб. мат. а., 1988, т. 29, В 6, с. 3-11.

класса кногообразнй, определяемых сястеиама из В ?

3. Пусть С - некоторый класс грутш о заданным® коночными иля счетккма системами пороздашлг, а - неко-торкЗ зад сводимости. Какой шгет бнть 1 -степень яаразрала-иостн проблоиа равенства группа аз С ? (Во шош случаях

^-стопэггь проблоии равенства конечно порозденной группа не завзеет от внбора конечной система яорездшестх.)

4. Построить группу, в которой разрешала проблема равенства, по неразрешима проблема тоздествешшх соотноаеняй (т. в. многэство ВС62 тоздеств, нстпнннх в ной, нерекурсивно), обладавшую хоросязаа свойствами.

5. Пусть Г~| - сэкоторцЗ класс конечных заданяЗ груш, з которых разрзаша проблема равенства. Существует ля единый {равномерный) алгерзлн, рэаагаиЗ проблему равенства по произвольному заданно из П ?

6. Пусть I - некоторый класс конечных заданий групп,

а Г - кнозоство всех заданлЗ нз I ' , опродзляззцзп группа с разреапкой проблемой равенства. Какова алгорэтшгчеекая природа Ш10згэс7ва Г ? В частности, входя? лз оно в варар-яш Кгяш - Ростовского (арзфузтическуэ керартга), я эсла вкь дят, то гдэ его шето а этой иерархия?

Сформуляруеи вкратцз некоторые результата по этан проблемам. Через ОС мз обозначаза многообразие всех ^ М-ступенно разрэиннше групп (т. е. П-а степень иногообразяя зсэх абагавых групп № I.

1. Пропзвольно-э карковсков (в частностк, нэтряваадьвое наследственной) свойство нераспозпавазио в классе всех в. о.

групп (теорема Адяна - Рабнна; ои. Пб, теорема 4.1 гл. XV 3). Полицкклнчность, еверхразреиимость, нильпотентность( абелевость, цакличность, конечность, тривиальность распознаваемы в

классе всех раэрзпгшлых к. о., а также к. о. в 01> груш С?]. Тривиальность и периодичность в классе всех к. а. т. групп, а таксе абелевость, нильпотентность к конечность в классе разрешимых к. з. т. групп распознававши

2. Тривиальность и периодичность в классе всех к. б. многообразий групп, а таязад абелевость н кроас-ОЕОсть (поразда-омость конечной грушю§; си. Ё8, е. 231-232]) а классе разроак-мых к. б. многообразий; распознаваема.

3. Степзкьэ ЕзразрзЕк^озхх проблем равенства к. о. группы ыо&эт быть лазбая рокурспыго порвчаелвмая £т;-стейбаь С9, 10]. Для лабого ьсассяства ^А натуральных чесол сукое-

6. Р. Лиадои, П. Щупп. Комбинаторная теория групп, - Ы.: iirp» 1980.

7. G-. Baumsfag,, Г-В. Caruwniio, C.F. Mi tie г III .. Some ищпшИг pxopetiies ot soMle Qiou'ps!J

' MalL 2, Ш1, Ы..Ш, Л 3, S. 2S3-Ж

8. В. А. Бахтурак, А.- Ю. Ольгшнскяй. Тождества // Алгебра-2. Итога науки и техн. Совр. npo&s. шт. Фунд. напрявл., т. 18, с. 117-240. - 13.: ВИШИ, 1988.

9. U. К. Валнев. О слсашостм проблемы тождества ддя конечно опроделаиша групп // Алгебра ж логика, 1969, т. 8, В 1, с. 5-43. . .

ю. Я). J. Collins. Ttuih-iofle debtees and ike Boone noups // Am.'Maik, 1971, v. 94, Л 3, 392-33$.

твувт 2-порождоппая группа С £ (X тзкгл. что М 1-сзсдшло г. проблема равенства тз С- я прсблока равенства п От С-сводима к М .В частности, столень» неразрешимости проблсми рьвокства 2-порождзшюй группы из 01 кс:*«т бнть любзл С-степень £11, 12] я любая насладственпая /12-стапзяь, отличаая ст £ 0 1 Г13.]. Существует рекурсстпо па-рачкелпмая /¿"¿-степень, б которой нэт прсоло;.г:г равенства пикакс! грушш

4. Существует 3-порслденпал (п дояа 2-породдонная) группа кз 01 , в которой разрэпяка проблема равенства, ко неразрешима проблема тождественных соотношений [4].

5. Существует равно^эрниЗ алгоритм, решаи^лй проблему равенства по произвольно^ заданию копачнтсл числом порозэдакцих я опрэделяхщях и тождественных соотношений фипитно аппроксимируемой группы [6, та орана 4.6 гл. IV 3 . Такого алгоритма на существует для всех заданий конечным числом порождающих и

11. 0. В. Белэградек. Об алгебраячеекп замкнутых группах // Алгебра я логика, 1974, т. 13, Я 3, с. 239-255.

12. М. lleaitt. Огирргп mil Voiaescktiehnern, ШйргсШ>п Ц fAalh. Ann., m$, Ы. 219, Л I, S. HZ-5L.

13. 0. В. Еолоградек. Об Н1-стопоп/Тх проблемы тождества слов // Ся<5. кат. а., 1978, т. 19, й S, с. 1232-1236.

14. М. Eitv leKuisiv aufzahlSptet tU-triad, Лег nickt zum, Wortpioiuwi ¿¿п&г ¿гирре qekoil H Z. math. Logic.

md ыЛ Hath, me, и 22, № г, swm

- G -

оцрздояладюс соотношений груш с разрешимой проблемой равенства и даже для некоторого рекурсивно порачислимого множества таких заданий [15].

6. Множество всех заданнй конечным числом пороядаззцнх и опрзделящих соотношений групп с разрешимой проблемой равенства максимально б классе Zj 3 корарзош Клкнз - Ростовского [15].

Цель работы - доказать для конечно поровдзнннх относительно свободных (как правило, к. а. т.) групп аналога некоторых праве дэнзшх визе рэзудьтатоз, касаагнхсл к. о. или конечно порожденных групп.

Метод?; псследованкя. Основнкм методом диссартацяп является метод Ю. Г. Клеймана С4, 16J, который! а свои очередь восходит к идеям работ £17, 18 J.

Научная новизна. Результаты дкссертадкг являйтся нозтш и состоят в следуодем (подробнее - пря наяожэвгв содэрнанЕя

is. W.W. Boone, Н- Royets,jt. Orí a ptoßUm LH. С. WhiUheaé and a ptoßieо г Momo Скигск И Malk. Scanl, Ш, v. ÍS/I2,

16. Ю. Г. Клейман. О некоторых вопросах теоран шюгообраэя£ групп // Изв. № СССР, сор. шт., 1983, т. 47, ß 1, с. 37-74.

17. M.R. Vauqkati - Lee. Uncouniatly many ira-xUiies oi gtoups // Butt. London Math. Soc.,

18. В. А. Романьков. О неразрзшшостн проблем задонорФаоЗ сводимости в свободных нклызотэнтных группах 2 в свободанх кольцах // Алгебра и логика, 1977, г. 16, £ 4, о. 457-471.

работы ).

1. Указано несколько н-эраспоппааае:.тнх свойств в класса 2-норояденпнх разроппяясс к. з. т. трупп п одно нераспознаваемое свойство в классо разрешимых к. tí. многообразий групп.

2. Доказано, что в жсбоЗ (рекурсивно поречислимой) С-стопеип а потривиальной наследственной til -степени содэряатся проблеял равенства некоторой г-псроадогшой разреяшой относительно свободной [к. з. т.) группа.

3. Приведен прилер 2-порахчонноЗ разрешимой к. з. т. группы, в которой разреЕшка проблема равенства, но неразрешима пройдена тожественных соотношений.

4. Доказано отсутствие равномерного алгоритма, решазщэго проблему равенства по произвольному заданию деумя пороэдахсшш п коночным числом тождественных соотношения разрешимой группы, в котороЗ эта проблема разрешима.

5. Для многих естественных классов конечных заданий относительно свободных групп определено место в иерархии Клини -Ростовского шояества всэх заданий из данного класса, опрвде-лясдах грушш с разрешимой проблемой равенства.

Теологическая н практическая ценность. Работа носат теоретический характер. Ее результаты могут быть полезны спзцза-листан по алгоритмической теории групп и многообразий групп.

Апробацяя шботы. Результаты днссортацдл частично докладывались на научно-исследовательской семинаре по алгебре иэха-нако-катематичоского факультета ИГУ.

Публикации. Результаты диссертации опубликованы в двух работах, указаниях в конце автореферата.

Структур* я обьем работа. Диссертация выполнена на 100 страницах машинописного текста и состоит из введения, пятя па-

раграфов, списка литературы, содержащего 27 наименований, и указателя обозначений.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается обзор результатов по исследуемым проблема/л и кратко формулируются основные результаты диссертации.

В $ 1 собраны основные определения, обозначения и факты, постоянно используемые в диссертации. Ын в основном пользуемся терминологией и обозначениями книг С1Э-213. Приведем некоторые обозначения и определения, используемые в автореферате. Через N обозначается множество всех целых неотрицательных чисел. Множество М1 £ N С-сводашо к инатес-гег М2 4

, если существует алгоритм, ставящей

в соответствие каждому С £ [М конечное множество С { —

й N так, что I ё Сс & М2 Для всех

в N . Это определение легко переформулировать на случай, когда М* или являются множествами групповых слов

в некоторых конечных или счетных алфавитах, божество М £ £ {М называется наследственным, если М* М М ^-степень, содержащая наследственное множество (равносильно, состоящая из наследственных множеств), называется наследственной.

19. X. Неймап. Многообразия групп. - ы.: Ыир, 1969.

20. I. Роджерс. Теория рекурсивных функций а эффективная вычислимость. - И.: Мир, 1972.

21. Дж. Шенфглд. Степени неразрешимости. - И.: Наука, 1977.

3 конца § 1 для произвольного многообразия групп ^ , отличного от многообразия всех групп, строятся, следуя работе [16]/, нециклические относительно свободные группы & , /4 .

Э одного и того же конечного или счетного ранга, постоянно встрочащиеся в диссертации. Каждому подмножеству V/ —

$ ^ (Д } , где ^р - ворбальная подгруппа свободной группы счетного ранга, соответствующая . ставится в соответ-

ствие некоторая подгруппа К () группы 5 . При этом если IV - множество всех значений в А некоторой совокупности слов из р , то км

- вербальная подгруппа в 3 • Приведены также некоторые свойства введенных объектов

аз работы С16Д.

В $ 2 изучается связи между поданожэства&ш

н соответствупцилщ подгруппаш КМ , а также между иного ствами вида [М,3)]=[[а, $] I М, Ъ }_, где

, и множествами

м . ш

I ш - образ еО при естественном эпиморфизме г\ —* —» Й ).

§ 3 носит подготовитолышЗ характер. В нем и в последув-ких параграфах мы фиксируем натуральное число £ Ч и полагаем

с = гиъ . ¿2 = Пс

- многообразие всех

нильпотентннх групп класса ^ С • Считаем также, что группы . А . £ имеют ранг 2. В § 3 доказнваются некоторые ьспомогатольныо утверждения о группе

а также определяется некоторые групповые слова, игравшие важную роль в дальнейшем, и доказывается некоторые их свойства (в основном свойства рекурсивности множеств всех их значений в К или /\ ). Некоторые из этих слов или их аналога

встречаются в £4. 16, 181.

В §_4 методом, сходным с методами работ [4, 16, 183, каждому многочлену

степени < I , а такяэ нулевому многочлену эффективно ставятся в соответствие слова ■ ^ Ъ ( 3) ' ^й) ) • а каздоцу I 6 2 - слово от двух перзмэнных. Получены нокоторне свойства множеств всех значений слов ,

^ и , У/ф в Я а А соответственно.

В частности, изучается связи между этими мнохаствамг и шотз-ством всех значений многочлена 0) прн произвольных целочисленных значениях перзнашгах. В конце § 4 определена 2-пороз-денкая разрешимая к. з. т. группа , являтаяся фактор-

группой группы 3 , з доказаны некоторые свойства ее вар-

бальных подгрупп в 1 1 () , ГДЗ

Мс N .

В § 5 приведены доказательства основных результатов диссертации. В этих доказательствах мы используем свойства вышеуказанных вербальных подгрупп группы н известный результат Ю. В. Уатиясевича [22] о том, что для любого рекурсивно поречислпыого множества М ~ НУ существует многочлен с целыми ковффзциентамк степени ^ 6 от нескольких переменных, множество всех неотрицательных значений которого прн произ-

22. Ю. В. Матиясевнч. Диофантозо множество // Пат. энцаклопз-дая, т. 2, с. 161-162. - П.: Сов. энциклопедия, 1979.

вольных целочисленных значениях поремещшх совпадает с М Поэтому ми берем в назюЗ конструкцта / — 6 . Обозначим через Шц класс всех груш из 01 , заданных двумя порох-

дажщгиз и конечным числом тоздеетаэиных соотношений. Слова "задание группы из " будут означать задание такой

грушш именно двумя лороэдашзчи к коночным члслс?л тоядэстбэп-яих соотношений. Приведем оеяовнке результаты диссертации.

1. Следующие свойства алгоритмически нераспознаваекн: а) отсутствие крученая в Ъ1% (теорема 5.1);

• б) тривиальность центра в ^Лц) (п. 1 теорема 5.2^

в) неразложимость в прсиззэданяэ з классе всех к. б.

подшогообразиЗ ОС (п. 2 теоремы 5.2); более того, для

любого шогообразля мнояество всех конечных

сястэи тогдзств, определяющих в IX неразложимое в произвел денно подмногообразие, не рекурсивно перечислимо (замечание 5.3);

г) £

-аппроксшлируемость в и, , где £ -произвольны:! класс групп, содер?Л!Пий все конечные 2-группн и

■г

такой, что любая 2-порохденная группа из

сОС финитно аппроксимируема (равносильно, аппроксишруома пераодически-ми группа?®) (теореиа 5.5); в частности, в качество

оС можно взять классы всех конечных, периодических, нильпотентных групп и всех конечных 2-групп (следствие 5.б).

2. Для любого (рекурсивно пере числимого) мно."гества

М — 1Р/ существует 2-лорозденная относительно свободная

группа

такая, что /I 1-сводемо к

проблема равенства в (г и проблема равенства в С С-сводама к М . Если /Л наслодстванно и непусто, то здесь ыояно заменять С-сводимость на ГСТ-сводимость (теорема 5.7). В частности, в лзбой (рекурсивно перечислимся) С-степени н любой наследственной (рекурсивно порочислимой) -степени, отличной ст {0} , содержится проблема равенства некоторой

2-пороздешюй относительно свободной грушш из

(следствие 5.8).

3. Существует группа из ^ , в которой разрешила

проблема равенства, но кэразрэанма проблема тоздоственних соотношений (п. 1 теоремы 5.9). Ынсязство всех тождеств, истинных в такой группе, на рзкураашо перечислило, поэтому существует к. б. многообразие ~ такое, что (^Р)

порождает многообразие. не обладающее но только конечнгвл, но в рекурсивно перечислимым базисом тождеств (замечание 5.10).

4. Существует рекурсивно пврочлелиша (и даже рэкурсив-ное) множество П заданий групп из такое, что в

кавдой группе, определяемой заданной из Г] , разрешима проблема равенства, но не существует равномерного алгоритма, рз-иавщего эту проблему по произвольному заданию нз I I . В частности, не существует равномерного алгохзгаа, р^аащего проблему равенства по произвольному заданию группы из XX ^ >

в которой эта проблема разрешима (п. 2 теоремы 5.9 и загдзчанзэ 5.12).

5. Пусть \Л - произвольное многообразие групп, содер-

а?

____ п обладахцеа рекурсивно перечислишь базнсои

товдеств, Г - класс всох заданий групп конечншз числом по-

рогдоггчяж л тоядостаанных соотношений в и или двумя порождавшими и конечны:,? числом тоясдеотаенннх соотношагплй в ,

а Г - гаохэство всэх заданий пз Г , опредеяящях груп-

г'

пы с разрешаю! проблемой равенства. Тогда I максимально (полно) в класса иерархия Клики - Уостозского (теорема

5.14). Зто значит, что суг,эсгзу<зт рокурсявш/З продзкат Р на Г * * [И !]\| такой, что лля лэбого у б Г

у6Г'<5=>3 хУ^ЭгР^у.^г), (*;

з лвбсе шсхгэсгго вида [¿6 1М | Л У V Ц- 3 2 Х,!/,?)],

гдз Ы - рекурсивный предикат на

I ? / , .

1-сводпио :г I . Отсюда следует, что в представлении кэльэя обоЗтись тпъ£гли чзсдсм кванторов. 3 частностл, ни

Г . нз Г4 г

но рзкурзнвно перечислило. В доказательств?. таорота 5.14 ии пользуешься общей схедай из [15], основанной на тсораьго Ростовского - Родгерса ([20, теорема XVI гл. 143, согласно которой шо-тэстео всех номеров рекурсивных шшзеств в гздэлезс.2 ¡5ушрации рокурсивао порэчЕслимнх подмао-20 ста [IV максшлшгьно (полно] в класса .

Диссертация выполнена на основе одной неоконченной работы Ю. Г. Клеймана, который любезно предоставил автору оо рукопись, за что автор внраяает ему глубокую признательность. В диссертации указано, что ¡шэнпо азтор позаимствовал из этой работы. Автор виражает глубокул благодарность своему научному руководители Л. I. Шмолькяну за постановку задач, консультации и внимание к тсбота.

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИЙ

1. и. И. Анохин. Нераспознаваэмость некоторых аппрокскмацяон-ных свойств относительно свободных групп // Сиб. пат. *., 1992, т. 33, Я 5, с. 3-14.

2, Ы. И. Анохин. О некоторых алгоритмических проблемах для относительно свободных групп. Москва, 1993, 71 с. ^копись деп. в ВИНИТИ от 11.06.93 » 1630-В93.

Подписано в печать 19.07.93 г. Зак. 599. Тир. 100. В Н И И И И Т