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

На правах рукописи

Меньшов Антон Владимирович

АСИМПТОТИЧЕСКИЕ СВОЙСТВА РАЦИОНАЛЬНЫХ МНОЖЕСТВ И СИСТЕМ УРАВНЕНИЙ В СВОБОДНЫХ АБЕЛЕВЫХ ГРУППАХ И РАЗРЕШИМОСТЬ РЕГУЛЯРНЫХ УРАВНЕНИЙ В КЛАССЕ НИЛЬПОТЕНТНЫХ

01.01.06 — математическая логика, алгебра и теория чисел

ГРУПП

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

3 (ЧАР 2015

0мск-2015

005559908

005559908

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф. М. Достоевского».

Научный руководитель:

доктор физико-математических наук, профессор Романьков Виталий Анатольевич.

Официальные оппоненты: Будкин Александр Иванович,

доктор физико-математических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Алтайский государственный университет», заведующий кафедрой Дудкин Федор Анатольевич,

кандидат физико-математических наук, Федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, старший научный сотрудник

Ведущая организация:

Федеральное государственное бюджетное учреждение пауки Институт математики и механики им. Н. Н. Красовского Уральского отделения Российской академии наук

Защита состоится 8 мая 2015 года в 14:00 на заседании диссертационного совета Д 003.015.02 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: пр. Академика Коптюга 4, г. Новосибирск,

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук и на сайте www.math.nsc.ru.

630090.

Автореферат разослан «■/¿г» февраля 2015

Учёный секретарь диссертационного с с----

кандидат физико-математических нау! доцент

г.

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

Актуальность работы.

Регулярные языки и конечные автоматы являются классическими объектами в теории формальных языков. Их изучение восходит к 40-м годам XX века, когда в работе МакКаллока. и Питтса [37] конечные автоматы использовались для моделирования нейронных сетей. С тех пор регулярные языки и конечные автоматы активно изучались. Среди ранних результатов, безусловно, стоит отметить теорему Клини, устанавливающую эквивалентность регулярных языков и конечных автоматов [33].

Рациональные множества в группах (более обобщенно — в моноидах) естественным образом обобщают регулярные языки в свободных моноидах. Изучение рациональных множеств в группах началось с работ Беноис для свободных групп [12], Эйленберга и Шютценбергера для абелевых групп [20] и Анисимова [9,10]. Эта область и по сей день является предметом многочисленных исследований. В первой главе диссертации исследуются асимптотические свойства рациональных множеств свободных абелевых групп. Такое направление исследований развивается в данной области многими авторами, например, Гилманом, Лори, Мяснпковым, Ремесленниковым, Стайнбергом и другими. Интерес к нему обусловлен проблемами сложности и случайного выбора, чрезвычайно важными для приложений. В [14,22] исследовались асимптотические свойства рациональных множеств в свободных группах.

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

Уравнения в группах составляют одну из наиболее разрабатываемых областей в современной теории групп. Первым результатом о разрешимости уравнений над группами следует, пожалуй, считать известную теорему Магнуса о свободе (см., например, [3]). Начало систематическому изучению уравнений над группами положил Нейман. Относительно результатов в данной области и ее исторического развития см., например, обзор [38]. Также краткий очерк истории вопроса можно

/ ' '

найти в [3].

Напомним, что уравнением от к неизвестных над группой О называется выражение вида и(х1,... .и^) = 1, где и(х1,... ,Хк) € Сх = С * Р(Х) — групповое слово от неизвестных из X — {а?!,..., Хк} и элементов группы С?, Р(Х) — свободная группа с базисом X. Будем называть Сх пространством всех уравнений с неизвестными из Л" над группой О.

Если Н — ббльшая группа, т. е. группа содержащая О в качестве фиксированной подгруппы, то уравнение над О также рассматривается как уравнение над Н. Уравнение называется разрешимым в группе С (или просто разрешимым), если существуют элементы }ц...., /¿д. 6 С, для которых «(/11,. .-,Нк) = 1- Уравнение называется разрешимым над группой С. если существует ббльшая группа Н, в которой это уравнение разрешимо.

Идея генеричности в теории конечных групп идет от работ Эрдеша и Турана [21], а также Диксона [18]. В настоящее время это предмет многочисленных исследований. В геометрической теории групп генери-ческий подход инициирован Громовым [27-29]. Он связан со случайными блужданиями на группах.

В последнее время генерический подход все более концентрируется на конкретных группах. Укажем, например, работы [31,32] о группах с одним соотношением, работы [2,7] по усредненным функциям Дена.

Не так много известно о генерических свойствах уравнений над группами. Так как разрешимость является одной из центральных проблем при рассмотрении уравнений, то можно сформулировать следующий вопрос: какова вероятность того, что случайное уравнение из Сх разрешимо над (■?? При этом можно наложить ограничения на разрешимость уравнений в самой группе С или некоторой фиксированной надгруппе Н. Обозначим 8ЛТя(С\ к) С Сх — множество всех уравнений из разрешимых в некоторой надгруппе Н, содержащей С. Различные подходы к измерению множеств в бесконечных группах рассматривались в [15]. В дискретных группах одним из общепринятых способов является вычисление асимптотической плотности. Так Гил-ман, Мясников и Романьков исследовали асимптотическую плотность разрешимых уравнении в свободных абелевых и конечно порожденных

нилыютентных группах [26] п в свободных группах [25]. В [11] рассматривалась асимптотическая плотность разрешимых однородных уравнений в фундаментальных группах компактных поверхностей. Вопрос о разрешимости случайных уравнений из Gx допускает следующее обобщение: какова вероятность того, что случайная система из п уравнений из Gx разрешима над G?

Разрешимость случайных систем линейных и нелинейных уравнений над конечными полями рассматривалась в работах Балакина, Кол-чина и Сачкова. В частности, в [1] Балакин исследовал разрешимость случайных систем линейных уравнений над простым конечным полем Fp порядка р. Во второй главе диссертации исследуется разрешимость случайных систем уравнений над свободными абелевыми группами конечного ранга.

Уравнение от одной неизвестной вида и.(х) = 1 над группой G называется регулярным, если сумма показателей степеней неизвестной х в слове и(х) (экспонента) не равна нулю, унимодулярным, если экспонента равна ±1 и сингулярным, если экспонента равна нулю.

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

Гипотеза (Кервера-Лауденбаха для уравнения). Произвольное регулярное уравнение от одной неизвестной jшзрешимо над любой группой.

Пусть щ{х\,...,Xk) — 1, i = l....,m — система из т уравнений над группой G от неизвестных х\,...,Хк- Обозначим через оц сумму показателей степеней, с которыми неизвестная ж, входит в запись слова щ. Система уравнений называется независимой, если матрица (cr;j) имеет ранг т. Система называется р-независимой (р — простое), если матрица системы (гт^) имеет ранг rn (mod р).

Указанная выше гипотеза допускает следующее обобщение:

Гипотеза (Кервера-Лауденбаха для систем уравнений). Произвольная независимая система уравнений разрешима над любой группой.

В общем случае гипотезы Кервера-Лауденбаха. остаются открытыми. Из полученных результатов отметим следующие. В серии работ Бродского [16] и [17]. Хови [30], Герстена [23], Крстпча [35] доказано, что любая независимая система, уравнений разрешима над произвольной локально индикабельной группой. Более того, любая р-независимая система уравнений разрешима над произвольной локально р-индикабельной группой для любого простого р. Напомним, что группа называется локально индикабельной, если любая ее конечно порожденная подгруппа допускает бесконечный циклический гомоморфный образ, и локально р-индикабелъной (р - простое), если любая ее конечно порожденная подгруппа допускает циклический гомоморфный образ порядка р. Относительно других результатов см. обзор [38].

Приведем еще одну известную гипотезу близкую по тематике к гипотезам Кервера-Лауденбаха.

Гипотеза (Левин). Произвольное уравнение разрешимо над любой группой без кручения.

Клячко доказал в [34], что любое унимодулярное уравнение от одной переменной разрешимо над произвольной группой без кручения. В общем случае эта гипотеза также открыта.

Пусть С — некоторый класс групп. Уравнение над группой С € С называется разрешимым в классе С, если существует группа Н € С, содержащая группу С, в которой оно имеет решение.

Так как указанные выше гипотезы Кервера-Лауденбаха остаются открытыми в общем случае, имеет смысл рассматривать вопросы разрешимости регулярных уравнении от одной неизвестной и систем независимых уравнений в классах групп. Для них можно формулировать аналоги различных гипотез и доказывать утверждения, которые естественно называть относительными. Так в [38] Романьковым был сформулирован вопрос 2.15 о разрешимости регулярных уравнений в классе нилыютентных групп, который стал предметом исследования третьей главы данной работы. Попутно отметим, что проблема разрешимости уравнений достаточно простого вида в свободных нилыютентных группах алгоритмически неразрешима (см. [4-6]).

Выполнимость для классов Т всех конечных и ЫЦ7 всех локально финитно аппроксимируемых групп для обеих относительных гипотез

Кервера-Лауденбаха следует из замечательной теоремы Герстенхабера и Ротхауза:

Теорема (Герстенхабер-Ротхауз [24]). Произвольная независимая система уравнений над компактной связной группой Ли разрешима над этой группой.

Отсюда вытекает, что любая независимая система уравнений над конечной группой (над локально финитно аппроксимируемой группой) имеет решение в конечной (соответственно, локально финитно аппроксимируемой [39]) группе, содержащей данную группу. В частности, любое регулярное уравнение от одной неизвестной над конечной (локально финитно аппроксимируемой) группой имеет решение в большей конечной (локально финитно аппроксимируемой) группе.

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

Целью диссертационной работы является:

1. Изучение асимптотических свойств рациональных множеств в свободных абелевых группах.

2. Изучение разрешимости случайных систем уравнений над свободными абелевыми группами.

3. Исследование разрешимости регулярных уравнений в различных классах нилыютентных групп.

Научная новизна. Все основные результаты диссертации являются новыми.

Выносимые на защиту положения. На защиту выносятся следующие основные результаты диссертации:

1. Доказано, что любое рациональное множество в свободной абеле-вой группе II1 конечного ранга п имеет асимптотическую плотность. Получен эффективный способ вычисления асимптотической плотности для свободных коммутативных моноидов в группе Ъп, позволяющий вычислять асимптотическую плотность рациональных множеств, представленных в полупростом виде.

2. Пусть ЗАТ(йт. к, п) и SATqr,^(Zm,k,n) обозначают множества всех систем из п уравнений с к неизвестными над свободной абеле-вой группой Ът ранга т, разрешимых соответственно в Ът и О'". Доказано, что асимптотическая плотность р(8АТ<(2">(2тД',п)) множества БАТ^т (2т, к. п) равна 1 при п < к и 0 при п > к. Для множества 8АТ(Ет, к, п) при п < к получены оценки для нижней и верхней асимптотических плотностей, показано, что они лежат

в интервале от (П?=а.—п+1 СО')) Д° (^сЙг) ' где ~~ ДЗета-функция Римана. При п < к установлена связь между асимптотической плотностью множества БАТ(2т, к, п) и суммами обратных наибольших делителей по матрицам полного ранга. Доказано, что р(БАТ(Жт, к, п)) = 0 при п > к.

3. Доказано, что вопрос о разрешимости регулярных уравнений в классе Лг конечно порожденных нильпотентных групп сводится к рассмотрению аналогичных вопросов для классов Мц нильпотентных групп без кручения и }7Р конечных р-групп для различных простых чисел р. Установлено, что для доказательства р-разрешимости (т. е. разрешимости в классе регулярных уравнений достаточно доказать их р-разрешимость над унитреуголь-ными группами над простым конечным нолем ¥р.

4. Доказана р-разрешимость любых регулярных уравнений над р-группой Гейзенберга 1ТТз и некоторых регулярных уравнений над произвольными унитреугольными группами иТп(Ер).

Третий и четвертый из основных результатов получены в неразделимом соавторстве с В. А. Романьковым при равном участии обеих сторон, остальные результаты получены автором самостоятельно.

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

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях и семинарах:

1. Омский алгебраический семинар (ОФ ИМ им. С. Л. Соболева СО РАН, г. Омск. 2012, 2013, 2014 гг.).

2. Конференция с международным участием «Алгебра, алгоритмы и вычисления на суперкомпьютерах» (ОФ ИМ им. С. Л. Соболева СО РАН и Омский государственный университет им. Ф. М. Достоевского, г. Омск. 2012 г.).

3. Международная конференция «Мальцевские чтения» (ИМ им. С. Л. Соболева СО РАН, г. Новосибирск, 2012, 2014 гг.).

4. 10-ая международная летняя школа «Пограничные вопросы теории моделей и универсальной алгебры» (ИМ им. С. Л. Соболева СО РАН, г. Новосибирск, 2013 г.).

5. Международная школа-конференция «Математические проблемы информатики» (Омский государственный технический университет, Омский государственный университет им. Ф. М. Достоевского и ОФ ИМ им. С. Л. Соболева СО РАН, г. Омск, 2013 г.).

6. Семинар «Алгебра и логика» (ИМ им. С. Л. Соболева СО РАН и Новосибирский государственный университет, г. Новосибирск, 2014 г.).

Публикации. Результаты автора по теме диссертации опубликованы в работах [40-48], из них [42.44-46] входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть

опубликованы основные результаты диссертаций на соискание ученых степеней доктора и кандидата наук. Работы [45,46] выполнены совместно с В. А. Романьковым при равном участии обеих сторон.

Объем и структура работы. Диссертация состоит из оглавления, введения, трех глав (разбитых на параграфы), заключения и списка литературы. Полный объем диссертации составляет 84 страницы. Список литературы содержит 62 наименования. Основные результаты каждой главы сформулированны во введении.

Все утверждения (леммы, предложения, теоремы, следствия) пронумерованы тремя числами: первое является номером главы, второе — номером параграфа в главе, третье — порядковым номером утверждения в данном параграфе. Формулы занумерованы двумя числами: первое соответствует номеру главы, а второе — порядковому номеру формулы в данной главе.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

В главе 1 исследуется асимптотическая плотность рациональных множеств в свободной абелевой группе Z" конечного ранга п относительно естественной стратификации группы Zn шарами, соответствующими норме || • ||р Евклидова пространства Rn, где 1 < р < оо.

В параграфе 1.1 вводится понятие асимптотической плотности, даются способы ее определения в свободных абелевых группах.

Будем называть асимптотическую плотность рр инвариантной, если . для любого М С Z" с асимптотической плотностью рр{М) = р и для любого V е Ъп существует pp(v + М) — р.

Лемма 1.1.2. Асимптотическая плотность рр является инвариантной для любого 1 < р < ос.

В параграфе 1.2 приводятся необходимые определения и известные результаты из [20] о рациональных множествах в коммутативных моноидах, в частности, в свободных абелевых группах.

В параграфе 1.3 получены основные результаты главы 1.

Лемма 1.3.1. Пусть В* С Z" — свободный коммутативный моноид с базисом {bi,.... b}.}, тогда для любого 1 < р < оо существует рр(В*) и рр(В*) > 0 тогда и только тогда, когда к = п.

В лемме 1.3.1 также получен эффективный способ вычисления этой асимптотической плотности.

Теорема 1.3.2. Для любого 1 < р < оо и любого рационального подмножества R С Z" существует pp(R). Eaiu R дано в виде полупростого

множемпва R = [J^=1(ai + В*). 7по pp(R) = J2i=i Рр(В*)-

Также, приводится пример 1.3.3. демонстрирующий, что для разных р-норм соответствующие асимптотические плотности могут не совпадать.

Результаты главы 1 опубликованы в [42].

Глава 2 посвящена исследованию разрешимости случайных систем уравнений над свободными абелевыми группами. Пусть SAT(Zm, к, п)

и SATQm(Zm,A;,n) обозначают множества всех систем из п уравнений с к неизвестными над свободной абелевой группой Zra ранга т, разрешимых соответственно в '£'" и Qm (Q — рациональные числа). Исследуется асимптотическая плотность указанных множеств в группе от-

носительно естественной стратификации ее шарами, соответствующими норме || • ||ос. Евклидова пространства Шп(-к+т\

В параграфе 2.1 приводятся необходимые сведения об уравнениях над группами, которые конкретизируются в параграфе 2.2 для свободных абелевых групп.

В параграфе 2.3 вычислена асимптотическая плотность множества SATqm (Zm, к, п.). Напомним, что множество называется генериче-скгш, если его асимптотическая плотность равна 1 и несущественным, если его плотность равна 0.

Теорема 2.3.2. Множество SATq>n(Zrn Д\п) является генерическим при п < к и несущественным при п > к.

Вычислена, асимптотическая плотность множества SAT(Zm,fc,n) для случая, когда количество уравнений п превосходит количество неизвестных к.

Следствие 2.3.3. При п > к множество SAT(Zm, к, п) является несущественным.

В параграфе 2.4 излагаются известные комбинаторные результаты о количестве целочисленных точек в расширениях целочисленных и рациональных многогранников. Основы изучения этого вопроса были заложены в 1960-х годах французским математиком Юджином Эр-хартом. Данные результаты оказываются полезными при вычислении асимптотических плотностей некоторых множеств в свободных абелевых группах. Основным результатом данного параграфа является неравенство на коэффициенты квазиполиномов Эрхарта, аналогичное неравенству [13, теорема 6] для полиномов Эрхарта.

Теорема 2.4.6. Пусть V — d-мерный рациональный многогранник в со знаменагпе.аем р и квазиполиномом Эрхарта Lv(t) = cat4 + crf_i(i)id_1 + • ■ • + ci(£)f + 1, тогда

|cr(f)| < \s{d + l,r + l)|crf

для г = 1.... ,(1 — 1, Ъ^, где обозначают числа Стирлинга

первого рода.

В параграфе 2.5 исследуется асимптотическая плотность множества 8АТ(27П, к, п). Приводятся некоторые известные критерии разрешимости систем линейных днофантовых уравнений в целых числах. Устанавливается связь между асимптотической плотностью множества ЗАТ(йт, /о, н.) и суммами обратных наибольших делителей по матрицам полного ранга.

Обозначим при п < к

ГтЛп(г) = 9тп-= 22 ^с<1(А) т,

гапк (А)=п

где gcd(Л) — наибольший общий делитель миноров порядка п матрицы А размера п х к и В11к{Ъ) - {(а^) <Е Ъпк \ \ < г}.

Теорема 2.5.6. Существует р(БАТ(Ъ'п, к, п)) = р тогда и только тогда. когда существует

РтЛп(г)

11111 —:-г—.— = О.

г-юо (2 г)пк

При п = к и т = 1

Г1л!-Лг> = Ц ТЩЩ'

гапк(Л)=п

Исходя из теоремы 2.5.6 и асимптотики для целочисленных матриц с заданным значением определителя [19, пример 1.6] выдвинута следующая гипотеза.

Гипотеза 2.5.7. „,„,(/•) - 0(гп2~п 1п(г)) и р{$кТ{Ът, п, п)) = 0.

С использованием результатов [26, 36] получены нетривиальные оценки для нижней и верхней асимптотических плотностей множества

ОС ^

ЭАТ(Ът,к,п). Далее ((з) = У"--дзета-функция Римана.

п=1 п8

Теорема 2.5.10. Справедливы следующие оценки:

(V ( П СО') ) < р(8АТ(2"\ к, п)) при к > п > 1.

(

3—к—п+1

(2) р{БКТ(Ът,к,п)) <

при к > п> 1.

Результаты главы 2 опубликованы в [44].

В главе 3 исследуется разрешимость регулярных уравнений в различных классах нилыютентных групп.

В параграфе 3.1 приводятся результаты о разрешимости уравнений в некоторых классах нильпотентных групп, необходимые в дальнейших построениях.

Определение 3.1.3. Пусть О — конечная р-группа, ]> — простое число. Уравнение называется р-разрелиимъш над С, если существует конечная />-группа Н > С. в которой это уравнение имеет решение.

Направление исследования разрешимости регулярных уравнений в классе нильпотентных групп установлено в следующем предложении.

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

1. Любое регулярное уравнение от одной неизвестной разрешимо в классе всех конечно порожденных нильпотентных групп без кру-

2. Любое регулярное уравнение над конечной р-группой (р простое) р-разрешимо.

Разрешимость регулярных уравнений в классе нильпотентных групп без кручения следует из теоремы Шмелькина о разрешимости невырожденных систем уравнений в делимых нильпотентных группах.

чения.

Теорема 3.1.7 (Шмелькин [8]). Произвольное регулярное уравнение от одной неизвестной над нгтьп-отентной группой без кручения N имеет решение в се мальцевском пополнении N

В параграфе 3.2 содержатся некоторые сведения об уравнениях над конечными р-группами, приводятся два способа присоединения корней, не выводящие за пределы класса конечных /;-групп: центральные произведения и сплетения. Отмечается, что любая конечная р-грушщ С изоморфна некоторой подгруппе группы унитреугольных матриц иТп(Рр) над простым конечным полем порядка р, где п = |С|. Таким образом, для доказательства утверждения 2) предложения 3.1.6 достаточно исследовать р-разрешимость регулярных уравнений над унитре-угольными группами.

В параграфе 3.3 исследуется р-разрешимость регулярных уравнений над р- группой Гейзенберга иТз(Ер).

Лемма 3.3.2. Пусть V — произвольная группа, порожденная элементами х, VI,..., г'т. Тогда любой элемент V € V может быть записан в виде

V = хг(х, q)sw, (3.4)

где г 6 Ъ, д, в <Е §р(иь..., г>т), т £ .

Теорема 3.3.4. Пусть регулярное уравнение вида и(х) = 1 над группой Ц/Г-Л(¥р). р — нечетное простое число, записано в форме (3.4) и (<7, з) ф 1. Тогда такое уравнение р-разрешимо над группой иТз(¥р).

Также приводится пример 3.3.1 который показывает, что сохранение ступени нильпотентности при переходе к группе, в которой разрешимо рассматриваемое уравнение, обеспечивается только для класса Л/"(/-

В параграфе 3.4 приводятся способы присоединения корней, специфичные для унитреугольных групп, описываются возникающие при этом вложения.

Лемма 3.4.2. Пусть ¥р — простое конечное поле порядка р. Уравнение над группой иТп(¥р) вида

хр*г = М 7),

где нод{р,г) = 1. з € Ъ+, = 1 г < j. 7 € 1Рр. разрешимо в

некоторой надгруппе, изоморфной 11Тт{¥р), где т = п + р3 — 1.

Теорема 3.4.6. Пусть — простое конечное поле порядка р. Уравнение над группой иТп(¥р) вида

хч = а,

где о = р", « б Ъ^, разрешимо в некоторой надгруппе, изоморфной иТт(¥р), где т = (п - 1)д + 1.

В параграфе 3.5 исследуется разрешимость регулярных уравнений над унитреугольными группами над простым конечным полем.

Теорема 3.5.3. Пусть над группой 11Тп(¥р) дано регулярное уравнение д\Х€1д2Х€2 ...дкХ€к = 1 с экспонентной д = р3. в е Обозначим а = .(/1.72 ■ •. у к- Если выполнено одно из следующих условий:

1- «¡.1+1 ф 0 для г = 2,.... п — 1.

Йг.г+1 ф 0 для г = 1____,п — 2,

5. а — центральный элемент в группе иТп(¥р),

то уравнение разреишмо в некоторой надгруппе, изоморфной 11Тт(¥р), где т — (п — 1 )д + 1.

Следствие 3.5.4. Любое регулярное уравнение экспоненты д = р3, в € , над иТз(¥р) разрешимо в некоторой надгруппе, изоморфной иТт{¥р), гдет = 2д+1.

Лемма 3.5.5. Если произвольное регулярное уравнение экспоненты (] = //, 5 £ Ъ+, над р-группой С4 разрешимо в большей р-группе Н такой, что \Н\ < /с{д), где /с — некоторая функция от экспоненты уравнения д, зависящая от группы С, то любое регулярное уравнение над С р-разрегиимо.

Из следствия 3.5.4 и леммы 3.5.5 получаем следующий результат:

Теорема 3.5.6. Произвольное регулярное уравнение над группой иТз(¥р) р-разрешимо.

Отметим, что теоремы 3.5.3 и 3.5.6 не являются следствиями теоремы Герстенхабера-Ротхауза и, что более важно, известные доказательства последней не могут быть адаптированы каким-то достаточно понятным способом для получения такого следствия. К тому же, доказательство теоремы 3.5.3 проводится конструктивным способом, в то время, как конструктивных построений для теоремы Герстенхабера-Ротхауза до снх пор не найдено.

Результаты главы 3 получены в неразделимом соавторстве с В. А. Романьковым при равном участии обеих сторон и опубликованы в [45, 46].

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

Список литературы завершает изложение работы.

Благодарности. Автор выражает глубокую благодарность своему научному руководителю профессору Виталию Анатольевичу Романько-ву за постановку задач и поддержку в работе.

Литература

[1] Балакин Г. В. Системы случайных уравнений над конечным полем // Тр. по дискр. матем. — 1998. — № 2. — С. 21-37.

[2] Кукина Е., Романьков В. А. Субквадратичностъ усредненной функции Дена для свободных абелевых групп // Сиб. мат. журн. — 2003. — Т. 44, Л» 4. — С. 772-778.

[3] Магнус В., Каррас А., Солитэр Д. Комбинаторная теория групп. — Москва: Наука, 1974. — 456 с.

[4] Репин Н. Н. Проблема разрешимости уравнений с одной неизвестной в нильпотентных группах //' Изв. АН СССР Сер. Матем. - 1984. - Т. 48, № 6. — С. 1295-1313.

[5] Романьков В. А. О неразрешимости проблемы эндоморфной сводимости в свободных нильпотентных группах и в свободных кольцах /7 Алгебра и Логика, — 1977. — Т. 16, № 4. — С. 457471.

[6] Романьков В. А. Об уравнениях в свободных метабелевых группах // Сиб. мат. журн. - 1979. — Т. 20, № 3. — С. 671-673.

[7] Романьков В. А. Об асимптотическом росте усредненной функции Дена для нильпотентных групп // Алгебра и логика. — 2007. - Т. 46, № 1, С. 60-74.

[8] Шмелькин А. Л. О полных нгыьпотетппых группах // Алгебра и Логика. - 1967. — Т. 6, № 2. - С. 111-114.

[9] Anisimov A. W. Group languages // Kibernetica. - 1971. — N. 4. — P. 18-24.

[10] Anisimov A. W., Seifert F. D. Zur algebraischen Charakteristik der durch kontext.-freie Sprachen definierten Gruppen jj Elektron. Informationsverarbeit. Kybernetik. — 1975. — N. 11. — P. 695-702.

Antolin Y., Ciobanu L., Viles N. On the asymptotics of visible elements and homogeneous equations in surface groups // Groups Geom. Dyn. — 2012. - V. 6. - P. 619-638.

Benois M. Parties rationnelles du groupe libre /7 C.. R. Acad. Sci. Paris. - 1969. - N. 269. - P. 1188-1190.

Betke U. McMullen P. Lattice points in lattice polytopes /'/ Monatsh. Math. - 1985. - V. 99, N. 4. - P. 253-265.

Borovik A. V., Myasnikov A. G., Remeslennikov V. A. Multiplicative measures on free groups fj Int. J. Algebra Comp. — 2003. — № 13. — P. 705-731.

Borovik A. V., Myasnikov A. G., Shpilrain V. Measuring sets in infinite groups // Contemporary Math. — 2002. — V. 298. — P. 21-42.

Brodskii S. D. Equations over groups and groups with a single defining relation /,/ Russian Math. Surveys. - 1980. - N. 35. — P. 165.

Brodskii S. D. Equations over groups and groups with, a single defining relator /7 Sib. Math. J. - 1984. - N. 25. - P. 235-251.

Dixon J. The probability of generating the symmetric group // Math. Z. — 1969. - V. 110, N. 3. — P. 199-205.

Duke W., Rudnick Z., Sarnak P. Density of integer points on affine homogeneous varieties // Duke Math. .J. — 1993. — V. 71, N. 1. — P. 143-179.

Eilenberg S., Schutzenberger M. P. Rational sets in commutative monoids // J. of Algebra. — 1969. — V. 13. — P. 173-191.

Erdos P., Turan P. On some problems of statistical group theory If/Z. Wahrscheinlichkeitstheorie venv. Geb. — 1965. — V. 4. — P. 175-186.

Frenkel E. V., Myasnikov A. G., Remeslennikov V. N. Regular sets and counting in free groups // Combinatorial and Geometric Group Theory. Basel: Birkliauser, 2010. — P. 93-118.

[23] Gersten S. M. Reducible diagrams and equations over groups // Essays in Group Theory. MSRI publ. New York; Berlin: Springer-Verl., 1987. - V. 8. - P. 15-73.

[24] Gerstenhaber M., Rothaus O. S. The solution of sets of equations in groups H Proc. N. A. S. — 1962. — V. 48, N. 9. — P. 1531-1533.

[25] Gilman R., Myasnikov A., Roman'kov V. Random equations in free groups /7 Groups. Complexity, Cryptology. — 2011. — V. 3. — P. 257284.

[26] Gilman R., Myasnikov A., Roman'kov V. Random equations in nilpotent groups // J. of Algebra, — 2012. — V. 352. — P. 192-214.

[27] Gromov M. Hyperbolic Groups j/ Essays in Group Theory. MSRI publ. New York; Berlin: Springer-Verl., 1987. - V. 8. - P. 75-263.

[28] Gromov M. Asymptotic invariants of infinite groups j j Geometric group theory (Sussex, 1991). Cambridge: Cambridge Univ. Press, 1993. - V. 2. - P. 1-295.

[29] Gromov M. Random walks in random groups // Geom. Funet. Analysis. - 2003. — V. 13. - P. 73-146.

[30] Howie J. On locally indicable groups i/ Math. Z. — 1982. — N. 180. — P. 445-461.

[31] Kapovich I., Scliupp P. Genericity, the Arzhantseva-Olshanskii method and the isomorphism problem for one-relator groups / / Math. Ann. - 2005. - V. 331, N. 1. - P. 1-19.

[32] Kapovich I., Schupp P. Delzant's T-ivariant, one-relator groups and Kolmogorov complexity // Comment. Math. Helv. — 2005. — V. 80. — P. 911-933.

[33] Kleeue S. C. Representation of events in nerve nets and finite automata // Automata Studies. — 1956. — N. 34. — P. 3-41.

[34] Klyachko A. Funny property of sphere and equations over groups // Comm. Algebra. - 1993. — N. 21. — N. 2555-2575.

[35] Krstic S. .Systems of equations over locally p-indicable groups // Invent. Math. — 1985. — N. 81. — P. 373-378.

[36] Maze G., Rosenthal J., Wagner U. Natural density of rectangular unimodular integer matrices // Linear Algebra Appl. — 2011. — V. 434, N. 5. - P. 1319-1324.

[37] McCulloch W. S., Pitts W. .4 logical calculus of the ideas immanent in nervous activity // Bull. Math. Biophysics. — 1943. — N. 5. — P. 115-133.

[38] Romairkov V. A. Equations over groups // Groups, Complexity, Crypt ology. — 2012. — N. 4. — P. 191-239.

[39] Rothaus S. O. On the non-triviality of some group extensions given by generators and relators // Ann. Math. — 1977. — V. 106, N. 3. — P. 599-612.

Публикации автора по теме диссертации

[40] Меньшов А. В. Асимптотическая пяотность рациональных множеств в Z" // Алгебра, алгоритмы и вычисления на суперкомпьютерах: тр. Междунар. конф., Россия, Омск — 2012. — С. 39-40.

[41] Menshov А. V. Asymptotic density of rational sets in Zn // Мальцев-ские чтения: тр. Междунар. конф., Россия, Новосибирск — 2012. — С. 97.

[42] Меньшов А . В. Асгшптотическая плотность рациона/итых множеств в Z" // Вестник Омского Университета. — 2013. — № 2. — С. 37-40.

[43] Меньшов А. В. Случайные системы уравнений в свободных абе-левых группах // Математические проблемы информатики: тр. Междунар. конф., Россия, Омск — 2013. — С. 35-36.

[44] Меньшов А. В. Случайные системы у1мвнений в свободных абеле-вых группах // Сибирский Математический Журнал. — 2014. — Т. 55, № 3. - С. 540-552.

[45] Меньшов А. В., Романьков В. А. О р-разрешилюсти некоторых регулярных уравнений надр-груттой Гейзенберга UT-.s(Zp) // Вестник Омского Университета. — 2014. — № 3. — С. 11-14.

[46] Меньшов А. В., Романьков В. А. Разрешимость регулярных уравнений в классе, нильпотентных групп // Вестник Омского Университета. — 2014. — № 4. — С. 19-22.

[47] Menshov А. V. Asymptotic density of rational sets in free abelian groups // arXiv.org, Cornell University Library, 2014. — 6 pp. URL: http://arxiv.org/pclf/1401.6558.pdf (дата обращения: 18.08.2014).

[48] Menshov A. V. On systems of equations in free abelian groups Ц arXiv.org, Cornell University Library, 2014. — 15 pp. URL: http: //arxiv.org/pdf/1401.7092.pdf (дата обращения: 18.08.2014).

Меньшов Антон Владимирович

АСИМПТОТИЧЕСКИЕ СВОЙСТВА РАЦИОНАЛЬНЫХ МНОЖЕСТВ И СИСТЕМ УРАВНЕНИЙ В СВОБОДНЫХ АБЕЛЕВЫХ ГРУППАХ И РАЗРЕШИМОСТЬ РЕГУЛЯРНЫХ УРАВНЕНИЙ В КЛАССЕ НИЛЬПОТЕНТНЫХ ГРУПП

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 4 февраля 2015 года. Формат 60x84 1/16. Усл. печ. л. 1,5. Тираж 110 экз. Заказ № 20.

Отпечатано в отделе полиграфии Омского государственного университета 644077, Омск, пр. Мира, 55