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

• Автор: Меньшов, Антон Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Омск
• Количество страниц: 84 с.

Оглавление

Введение

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

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

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

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

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

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

группами

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

2.2 Уравнения над абелевыми группами
2.3 Системы, разрешимые в <0>т
2.4 Точки решеток в выпуклых многогранниках и квазиполиномы
Эрхарта
2.5 Системы, разрешимые в
Глава 3. Разрешимость регулярных уравнений в классе нильпотентных
групп
3.1 Уравнения над нильпотентными группами
3.2 Уравнения над конечными ^группами, способы присоединения
корней и переход к матричным группам
3.3 Регулярные уравнения над 11Тз(Жр)
3.4 Присоединение корней к иТ„(Ер)
3.5 Регулярные уравнения над иТ„(¥р)
Заключение
Литература
Введение

Актуальность темы исследования. Регулярные языки и конечные автоматы являются классическими объектами в теории формальных языков. Их изучение восходит к 40-м годам XX века, когда в работе МакКаллока и Питтса [48] конечные автоматы использовались для моделирования нейронных сетей. С тех пор регулярные языки и конечные автоматы активно изучались. Среди ранних результатов, безусловно, стоит отметить теорему Клини, устанавливающую эквивалентность регулярных языков и конечных автоматов [42].
Рациональные множества в группах (более обобщенно — в моноидах) естественным образом обобщают регулярные языки в свободных моноидах. Изучение рациональных множеств в группах началось с работ Бснонс для свободных групп [20], Эйленберга и Шютцепбергера для абелевых групп [28] и Анисимова [14,15]. Эта область и по сей день является предметом многочисленных исследований. В первой главе диссертации исследуются асимптотические свойства рациональных множеств свободных абелевых групп. Такое направление исследований развивается в данной области многими авторами, например, Гилманом, Лори, Мясниковым, Ремесленниковым, Стайнбергом и другими. Интерес к нему обусловлен проблемами сложности и случайного выбора, чрезвычайно важными для приложений. В [22,30] исследовались асимптотические свойства рациональных множеств в свободных группах.
Изучение разрешимости уравнений различного вида присутствует во всех областях современной математики. Чаще всего рассматриваются вопросы о существовании и нахождении решений. При этом также обращается внимание на алгоритмическую сторону вопроса, на возможность описания всех решений.
Уравнения в группах составляют одну из наиболее разрабатываемых областей в современной теории групп. Первым результатом о разрешимости уравнений над группами следует, пожалуй, считать известную теорему Магнуса о свободе (см., например, [4]). Начало систематическому изучению уравнений над

группами положил Нейман. Относительно результатов в данной области и ее исторического развития см., например, обзор [50]. Также краткий очерк истории вопроса можно найти в [4].
Напомним, что уравнением от к неизвестных над группой С называется выражение вида и(х,... ,щ) = 1, где и(х,... , ад.) € = С * Р{Х) —
групповое СЛОВО ОТ неизвестных ИЗ X = {.г-1, . . . , Хи} и элементов группы С, Р(Х) свободная группа с базисом X. Будем называть Сх пространством всех уравнений с неизвестными из X над группой С.
Если Н — большая группа, т. е. группа содержащая С в качестве фиксированной подгруппы, то уравнение над С также рассматривается как уравнение над Н. Уравнение называется разрешимым в группе О (или просто разрешимыел), если существуют элементы , к); € С, для которых и(Ъ,, . . . , кк) =
Уравнение называется разрешимым над группой (3, если существует большая группа Н, в которой это уравнение разрешимо.
Идея генеричности в теории конечных групп идет от работ Эрдеша и Турина [29], а также Диксона [26]. В настоящее время это предмет многочисленных исследований. В геометрической теории групп генерический подход инициирован Громовым [35-37]. Он связан со случайными блужданиями на группах.
В последнее время генерический подход все более концентрируется на конкретных группах. Укажем, например, работы [39,40] о группах с одним соотношением, работы [3,11] по усредненным функциям Дена.
Не так много известно о генерических свойствах уравнений над группами. Так как разрешимость является одной из центральных проблем при рассмотрении уравнений, то можно сформулировать следующий вопрос: какова вероятность того, что случайное уравнение из Сх разрешимо над С? При этом можно наложить ограничения на разрешимость уравнений в самой группе С или некоторой фиксированной падгруппе Н. Обозначим ЭАТя(С, к) С Сх — множество всех уравнений из Сх, разрешимых в некоторой надгруппе Н, содержащей! С. Различные подходы к измерению множеств в бесконечных группах

где А е К*, Ь <5 Мто.
Конусом К, С К”, порожденным векторами Wl,..., называется множество вида
/С — сопе(уь..., шт) = {адлмх 4 Ь Q;тоwm | а; > О, «; € К}.
Если все вершины многогранника V являются точками решетки Л, то будем называть V многогранником решетки А. Многогранники решетки будем называть целочисленными многогранниками.
Рациональным, многогранником будем называть многогранник, все вершины которого имеют рациональные координаты. В этом случае знаменателем V будем называть наименьшее р € 2+, при котором рР является многогранником решетки ЪА.
Классическим вопросом является изучение величины | {£5 П | как функции от I для подмножеств 5 С Евклидова пространства. Для рациональных многогранников основы изучения этого вопроса были заложены в 1960-х годах французским математиком Юджином Эрхартом. Подробное изложение приводимых далее результатов содержится в [19] (см. также [12]).
Обозначим Ь-р{Ь) — {ЬР П 1. Рядом Эрхарта будем называть ряд
ЕЬг-р(г) = Ь-р(Р)гь.
для п е С, к €