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

• Меньшов, Антон Владимирович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Меньшов, Антон Владимирович

Оглавление

Введение

Глава 1. Асимптотическая плотность рациональных множеств свободных

абелевых групп

1.1 Асимптотическая плотность

1.2 Рациональные множества в коммутативных моноидах

1.3 Основной результат

Глава 2. Случайные системы уравнений над свободными абелевыми

группами

2.1 Уравнения над группами

2.2 Уравнения над абелевыми группами

2.3 Системы, разрешимые в <0>ш

2.4 Точки решеток в выпуклых многогранниках и квазиполиномы Эрхарта

2.5 Системы, разрешимые в Z7n

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

групп

3.1 Уравнения над нильпотентными группами

3.2 Уравнения над конечными р-группами, способы присоединения корней и переход к матричным группам

3.3 Регулярные уравнения над иТз(^)

3.4 Присоединение корней к иТп(Ер)

3.5 Регулярные уравнения над иТп(Ер)

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Асимптотические свойства рациональных множеств и систем уравнений в свободных абелевых группах и разрешимость регулярных уравнений в классе нильпотентных групп»

Введение

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

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

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

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

группами положил Нейман. Относительно результатов в данной области и ее исторического развития см., например, обзор [50]. Также краткий очерк истории вопроса можно найти в [4].

Напомним, что уравнением от к неизвестных над группой С называется выражение вида и(х 1,..., = 1, где и(х 1,..., £ Сх = <3 * Р{Х) — групповое слово от неизвестных из X = {ж1,..., и элементов группы С, Р{Х) — свободная группа с базисом X. Будем называть Сх пространством всех уравнений с неизвестными из X над группой (7.

Если Н — большая группа, т. е. группа содержащая С в качестве фиксированной подгруппы, то уравнение над С также рассматривается как уравнение над Н. Уравнение называется разрешимым в группе С? (или просто разрешимым), если существуют элементы ..., £ С, для которых и(1г\,..., Н^) — 1. Уравнение называется разрешимым над группой С, если существует большая группа Н, в которой это уравнение разрешимо.

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

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

Не так много известно о генерических свойствах уравнений над группами. Так как разрешимость является одной из центральных проблем при рассмотрении уравнений, то можно сформулировать следующий вопрос: какова вероятность того, что случайное уравнение из Сх разрешимо над С? При этом можно наложить ограничения на разрешимость уравнений в самой группе С или некоторой фиксированной иадгруппе Н. Обозначим БАТя^, к) С (?х — множество всех уравнений из С?х, разрешимых в некоторой надгруппе Н, содержащей С. Различные подходы к измерению множеств в бесконечных группах

рассматривались в [23]. В дискретных группах одним из общепринятых способов является вычисление асимптотической плотности. Так Гилман, Мясников и Ромаиьков исследовали асимптотическую плотность разрешимых уравнений в свободных абелевых и конечно порожденных нильпотентных группах [34] и в свободных группах [33]. В [16] рассматривалась асимптотическая плотность разрешимых однородных уравнений в фундаментальных группах компактных поверхностей. Вопрос о разрешимости случайных уравнений из Gx допускает следующее обобщение: какова вероятность того, что случайная система из п уравнений из Gx разрешима над G1

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

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

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

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

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

зывается р-независимой (р — простое), если матрица системы (сг^) имеет ранг т (mod р).

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

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

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

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

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

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

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

классах групп. Для них можно формулировать аналоги различных гипотез и доказывать утверждения, которые естественно называть относительными. Так в [50] Романьковым был сформулирован вопрос 2.15 о разрешимости регулярных уравнений в классе нильпотентных групп, который стал предметом исследования третьей главы данной работы. Попутно отметим, что проблема разрешимости уравнений достаточно простого вида в свободных нильпотентных группах алгоритмически неразрешима (см. [7,9,10]).

Выполнимость для классов Т всех конечных и ЬШ-* всех локально финитно аппроксимируемых групп для обеих относительных гипотез Кервера-Лауденбаха следует из замечательной теоремы Герстенхабера и Ротхауза: Теорема (Герстенхабер-Ротхауз [32]). Произвольная независимая система уравнений над компактной связной группой Ли разрешима над этой группой.

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

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

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

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

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

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

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

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

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

2. Пусть 8АТ(Жт, к, те) и 8АТо)т(йт, к, те) обозначают множества всех систем из те уравнений с к неизвестными над свободной абелевой группой I/11 ранга 7П, разрешимых соответственно в И11 и <{])т. Доказано, что асимптотическая плотность р^АТ^т^"1, к, те)) множества 8АТ(^г7г(Жт, к, те) равна 1 при те < к и 0 при п > к. Для множества 8АТ(Жт, к, п) при п < к получены оценки для нижней и верхней асимптотических плотностей, по-

где — дзета-функция Римана. При п < к установлена связь между асимптотической плотностью множества 8АТ(йт, к, п) и суммами обратных наибольших делителей по матрицам полного ранга. Доказано, что р{БАТ{^п, к, те)) = 0 при п > к.

выми.

казано, что они лежат в интервале

3. Доказано, что вопрос о разрешимости регулярных уравнений в классе Л/" конечно порожденных нилытотентных групп сводится к рассмотрению аналогичных вопросов для классов А/^/ нилытотентных групп без кручения и Тр конечных р-групп для различных простых чисел р. Установлено, что для доказательства р-разрешимости (т. е. разрешимости в классе Т^) регулярных уравнений достаточно доказать их р-разрешимость над унит-реугольными группами над простым конечным полем

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

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

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

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

Апробация работы. Основные результаты работы докладывались на

следующих конференциях и семинарах:

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

г. Омск, 2012, 2013, 2014 гг.).

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

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

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

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

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

работах [54-62], из них [56,58-60] входят в перечень ВАК российских рецензируемых научных журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученых степеней доктора и кандидата паук. Работы [59, 60] выполнены совместно с В. А. Романьковым при равном участии обеих сторон.

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

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

и

Содержание диссертации.

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

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

Будем называть асимптотическую плотность рр инвариантной, если для любого М С Zn с асимптотической плотностью рр(М) = р и для любого V £ Zn существует рр(у + М) = р.

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

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

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

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

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

Теорема 1.3.2. Для любого 1 < р < оо и любого рационального подмножества ЙCZ" существует рр(Я). Если Я дано в виде полупростого множества Я = + В1), то Рр(Д) = Рр(В*).

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

Глава 2 посвящепа исследованию разрешимости случайных систем уравнений над свободными абелевыми группами. Пусть 8АТ(ЖТП, к, п) и 8АТ<о)т(Ж"г, к, п) обозначают множества всех систем из п уравнений с к неизвестными над свободной абелевой группой Ът ранга т, разрешимых соответственно в Ът и (О — рациональные числа). Исследуется асимптотическая плотность указанных множеств в группе 1/1(к+т) относительно естественной стратификации ее шарами, соответствующими норме || • Цоо Евклидова пространства жп(к+т\

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

В параграфе 2.3 вычислена асимптотическая плотность множества ЗАТО)/с,п). Напомним, что множество называется генерическим, если его асимптотическая плотность равна 1 и несущественным, если его плотность равна 0.

Теорема 2.3.2. Множество 8АТ<$т(Ът, к: п) является генерическим при п < к и несущественным при п > к.

Вычислена асимптотическая плотность множества 8АТ(йт, к, п) для случая, когда количество уравнений п превосходит количество неизвестных к. Следствие 2.3.3. При п > к множество 8АТ(%т,к,п) является несущественным.

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

Теорема 2.4.6. Пусть V — й-мерный рациональный многогранник в М^ со знаменателем р и квазиполиномом Эрхарта Ь-р(£) = + с(1-\{Ь)1й~1 + ■ ■ ■ + 1, тогда

для г = 1,..., д, — 1; £ Е где обозначают числа Стирлинга первого

рода.

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

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

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

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

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

Лев?* (г),

гапк(/1)=п

При п = к и т — 1

гапк(Л)=га

Гипотеза 2.5.7. ^,п,п(г) = 0{гп2~п 1п(г)) и р($КТ{Ът,щп)) = 0.

С использованием результатов [34, 47] получены нетривиальные оценки для нижней и верхней асимптотических плотностей множества 8АТ(йт, к, п).

ОО 2

Далее ("(в) = У}--дзета-функция Римана.

п=1 па

Теорема 2.5.10. Справедливы следующие оценки: (V ( П Ш) ) < к, п)) при к > п > 1.

(2) р(8АТ(Жш,А;,п)) < прик>п> 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

V = хг(х, д)зт, (3.4)

где gp(vъ • • ■, ги € 73V.

Теорема 3.3.4. Пусть регулярное уравнение вида и(х) = 1 над группой иТз(¥р), р — нечетное простое число, записано в форме (3-4) и (д, з) ^ 1. Тогда такое уравнение р-разрешимо над группой иТ%(¥р).

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

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

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

хР = ^'(т))

где нод(р, г) = 1, в € Ъ+, ¿,.7 = 1,..., п, г < 7 е разрешимо в некоторой надгруппе, изоморфной иТт(¥р), где т = п +р8 — 1.

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

х* = а,

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

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

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

Э1Хе1д2Хе2... дкХ£к = 1 с жспонентой д = р8, в Е . Обозначим а = д\д<2 ... дь-Если выполнено одно из следующих условий:

1. 0 для г = 2,.. ., п — 1,

2. ац+1 ф 0 для г — 1,..., п — 2,

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

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

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

Лемма 3.5.5. Если произвольное регулярное уравнение экспоненты д = рэ, в 6 , над р-группой <2 разрешимо в большей р-группе Н такой, что \Н\ < где /с — некоторая функция от экспоненты уравнения зависящая от группы то любое регулярное уравнение над С р-разрешимо.

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

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

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

Результаты главы 3 опубликованы в [59,60].

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

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

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

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

1.1. Асимптотическая плотность

Стратификацией счетного множества Т называется последовательность {Tr}repj непустых конечных подмножеств Тг таких, что |JrGNTr = Т. Стратификации обычно задаются с помощью функций длины. Функция длины на Т - это отображение I : Т —> N такое, что для каждого г Е N множество {х Е Т | 1(х) = г} конечно. Стратификации по сферам и шарам образованы соответственно сферами Sr = {х Е Т \ 1{х) = г} и шарами Br = {х G Т | 1{х) < г].

Определение 1.1.1. Асимптотической плотностью множества М С Т в соответствии со стратификацией {Тг} называется предел

\мпт\

р(М) = lim рг(М), где рг(М) = 1 г|

г—>оо IТ,

г

если он существует. В противном случае будем использовать пределы р(М) = lim sup pr(M), р(М) = lim inf pr(M),

r—¥oo

r—>oo

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

Множество М называется генерическим, в соответствии со стратификацией {Тг}, если р(М) — 1, и несущественным, если р(М) = 0.

Пусть Zn — свободная абелева группа конечного ранга п. Группу Ъп будем отождествлять со стандартной целочисленной решеткой Евклидова пространства Кп. Считаем, что Мп снабжено р-нормой || • ||р для некоторого 1 < р < оо,

определяемой для элемента х = (rri,..., хп) формулой

Fib =

+ • ■ ■ + |жп|Р)р при 1 < р < оо max{|a;i|,..., \хп\] при р = оо

Эта норма порождает функцию длины 1р '. zn —> N с шарами

В1Г{1) = В^г Г)%п = {ие%п\ Ц'уЦр < г},

где Врг = {х Е Мп | ||ж||р < г} — шар радиуса г в!" относительно нормы || ■ ||р. Для соответствующие относительные частоты определяются как

РрЛм) =

\MDB¡¡r(Z)\ \МПВ.

■п

■р,Г I

\B-r(Z)\ \B»X(Z)\ •

P,rK

Соответствующие плотности будем обозначать рр,~рр, р^.

Список литературы диссертационного исследования кандидат наук Меньшов, Антон Владимирович, 2014 год

Литература

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

2. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. — Москва: Наука, 1982. - 288 с.

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

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

5. Мальцев А. И. Нилъпотентные группы без кручения // Изв. АН СССР Сер. матем. - 1949. - Т. 13, № 3. - С. 201-212.

6. Нейман X. Многообразия групп. — Москва: Мир, 1969. — 264 с.

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

8. Романьков В. А. Теоремы вложения для нилъпотентных групп // Сиб. мат. журн. - 1972. - Т. 13, № 4. - С. 859-867.

9. Романьков В. А. О неразрешимости проблемы эндоморфпой сводимости в свободных нилъпотентных группах и в свободных кольцах // Алгебра и Логика. - 1977. - Т. 16, № 4. - С. 457-471.

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

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

12. Стенли Р. Перечислительная комбинаторика. — Москва: Мир, 1990. — 440 с.

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

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

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

16. 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.

17. Baumslag G. Wreath products and p-groups // Proc. Cambridge Philos. Soc. — 1959. - V. 55. - P. 224-231.

18. Beck M., De Loera J., Develin M., Pfeifle J., Stanley R. Coefficients and roots of Ehrhart polynomials // Contemporary Math. — 2005. — V. 374. - P. 15-36.

19. Beck M., Robins S. Computing the continuous discretely. — New York: Springer-Verl., 2007. - 227 p.

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

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

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

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

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

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

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

27. 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.

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

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

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

31. 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.

32. Gerstenhaber M., Rothaus O. S. The solution of sets of equations in groups // Proc. N. A. S. - 1962. - V. 48, N. 9. P. 1531-1533.

33. Gilman R., Myasnikov A., Roman'kov V. Random equations in free groups // Groups, Complexity, Cryptology. - 2011. V. 3. — P. 257-284.

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

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

36. Gromov M. Asymptotic invariants of infinite groups // Geometric group theory (Sussex, 1991). Cambridge: Cambridge Univ. Press, 1993. — V. 2. — P. 1-295.

37. Gromov M. Random walks in random groups // Geom. Funct. Analysis. — 2003. - V. 13. - P. 73-146.

38. Howie J. On locally indicable groups // Math. Z. - 1982. - N. 180. - P. 445461.

39. Kapovich I., Schupp P. Genericity, the Arzhantseva-Olshanskii method and the isomorphism problem for one-relator groups // Math. Ann. — 2005.

V. 331, N. 1. - P. 1-19.

40. Kapovich I., Schupp P. Delzant's T-ivariant, one-relator groups and Kolmogorov complexity // Comment. Math. Helv. — 2005. — V. 80. — P. 911933.

41. Katznelson Y. Integral Matrices of Fixed Rank // Proc. Amer. Math. Soc. — 1994. - V. 120, N. 3. - P. 667-675.

42. Kleene S. C. Representation of events in nerve nets and finite automata // Automata Studies. 1956. - N. 34. - P. 3-41.

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

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

45. Lazebnik F. On systems of linear diophantine equations // Math. Mag. — 1996. - V. 69, N. 4. P. 261-266.

46. Levin F. Solution of equations over groups // Bull. Amer. Math. Soc. — 1962. - V. 68, N. 6. P. 603-604.

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

48. McCulloch W. S., Pitts W. A logical calculus of the ideas immanent in nervous activity // Bull. Math. Biophysics. - 1943. - N. 5. - P. 115-133.

49. Neumann B. H. Adjunction of elements to groups //J. London Math. Soc. — 1943. - V. 18. - P. 12-20.

50. Roman'kov V. A. Equations over groups // Groups, Complexity, Cryptology. - 2012. - N. 4. - P. 191-239.

51. Rothaus S. 0. On the non-triviality of some group extensions given by generators and relators // Ann. Math. — 1977. — V. 106, N. 3. — P. 599612.

52. Smith H. J. S. On Systems of Linear Indeterminate Equations and Congruences // Philos. Trans. R. Soc. bond. 1861. V. 151. P. 293 326.

53. Software package LattE: Lattice-Point Enumeration, URL: https://www.rnath.ucdavis.edu/-latte/ (дата обращения: 18.08.2014)

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

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

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

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

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

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

59. Меньшов А. В., Романьков В. А. О р-разрешимости некоторых регулярных уравнений над р-группой Гейзенберга UT^CLp) // Вестник Омского Университета. - 2014. - № 3. - С. 11-14.

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

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

62. 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).