Нормальные базисы и символическая динамика

• Автор: Чернятьев, Александр Леонидович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 82 с. : ил.

Содержание
1 Введение
2 Пространство слов и символическая динамика
2.1 Пространство слов
2.2 Рекуррентность и равномерная рекуррентность
2.3 Специальные подслова
2.4 Морфизмы
2.5 Вопросы периодичности
2.6 Графы Рози подслов
2.7 Слова, порождаемые динамическими системами
2.8 Функция рассогласования
2.9 Соответствие между словами и разбиениями множества
2.10 Перекладывания отрезков
2.11 Слова Штурма
2.12 Структура слов Штурма
2.13 Слова Арно-Рози
3 Сбалансированные слова и динамические системы
3.1 Введение и постановка проблемы
3.2 Основные конструкции и определения
3.3 Конечные сбалансированные слова
3.4 Расширение сбалансированных слов
3.5 Слова, порождаемые повороотом окружности
3.6 Сбалансированные слова над алфавитом из п символов
3.7 Основная теорема о непериодических сбалансированных
словах над произвольным алфавитом
3.8 Замечания о периодических сбалансированных словах над
произвольным алфавитом
3.9 Сбалансированные слова и теорема Голода-Шафаревича
4 Слова с минимальной функцией роста
4.1 Постановка задачи
4.2 Свойства слов с минимальной функцией роста
4.3 Частоты подслов в словах медленного роста
4.4 Конструкция динамической системы
4.5 Нормальные базисы граничных аллгебр

5 Перекладывания отрезков и символическая динамика
5.1 Введение и постановка задачи
5.2 Необходимые условия для порождаемости слова перекладыванием отрезков
5.3 Построение динамической системы
5.4 Эквивалентность множества р.р слов, порождаемых кусочно-
непрерывным преобразованием, множеству слов, порождаемых перекладыванием отрезков

1 Введение.
Актуальность темы.
Комбинаторика слое находит свое применение в самых разных разделах математики. Например, в алгебре при изучении базисов и нормальных форм, в алгебраической топологии, в символической динамике. Ряд проблем, относящихся к комбинаторике слов находится на стыке алгебры и теории динамических систем. Многие проблемы комбинаторики слов представляют самостоятельный интерес.
Комбинаторика слов широко используется в задачах комбинаторной теории групп, в теории алгебр Ли, в вопросах бернсайдовского типа и в задачах, связанных с мономиальными алгебрами. Комбинаторная техника, относящаяся к теории групп, развивалась в работах М. Дэна, Е. С. Голода и И. Р. Шафаревича, П. С. Новикова, С. И. Адяна, А. И. Костри-кина, Е. И. Зельманова, И. Рипса, М. Громова, А. Ю. Ольшанского, М. В. Сапира и др.
Е. С. Голод и И. Р. Шафаревич [11], [12] построили конечно порожденную бесконечную периодическую группу (с неограниченной экспонентой) на основе рассмотрения нормальных форм алгебр и оценки функий роста. П. С. Новиков и С. И. Адян [1] провели детальное исследование свойств периодичности, находящее свое применение в самых разных разделах математики. Ими были впервые построены примеры бесконечных конечно порожденных периодических групп ограниченой экспоненты (т.е. решена проблема Бернсайда), получены наилучшие из известных оценок на экспоненту для таких групп (см. обзор [2]). В дальнейшем был исследован случай четной экспоненты (см. [24], [58]).
В основе замечательных работ М. Громова и А. К). Ольшанского также лежит техника диаграмм Ван-Кампена, возникшая в комбинаторной топологии. Подробнее (а также литературу по этой теме) см. в монографии [27].
Комбинаторные соображения, возникшие в символической динамике (автоматные группы), нашли свое применение в работах С. В. Алешина [3, 4, 5] и и Р. И. Григорчука [13], [14], [15] при решении проблемы Мил-нора - посторении групп промежуточного роста (при этом группы Григорчука периодичны). Впервые автоматные полугруппы были построены в работах С. В. Алешина. (Изложение примера С. В. Алешина - см. в книге [16]) Автоматные конструкции активно используются в самых разных ситуациях (см. [9], [31], [29], [21]). Возникают они и в данной работе

подслово w такое, что и = aw и v = bw. Так как и, v имеют по два разных продолжения, то в W встретятся подслова аша и bwb, значит W не сбалансированно.
Теперь докажем импликацию <=. Предположим , что W не сбалансированно. Тогда по предложению 2.28, найдется такое подслово и = wdwx wn, что аиа и bub - также подслова W. Предположим также, что и имеет минимальную длину из всех слов с таким свойством.
Отметим, что из этого предположения следует, что если пара слов одинаковой длины щ,щ не сбалансирована, то слова имеют длину, не меньше, чем н + 3. Действительно, из доказательства предложения 2.28, следует, что минимальная длина такого и не больше наименьшей длины не сбалансированной пары уменьшенной на 2. Поэтому любая не сбалансированная пара имеет длину не меньше |м| + 2 = п + 3.
Заметим, что по предложению 2.28 и не пусто, иначе в слове W встретились бы слова аа и ЬЪ. По этой же причине, wо = wn, w = гцг_1 и более обще, гщ- = wn-k, то есть и-палипдром.
Теперь, мы знаем, что различных слов длины п+1 ровно п + 2. Слово и может быть расширено двумя путями как влево, так и вправо. Соответственно, ровно одно из слов аи или Ьи (мы предположим, что аи) может быть расширено вправо двумя путями. Следовательно, аиа, aub и bub - подслова W. а Ьиа - не является подсловом. Пусть ?' - первый момент, когда подслово bub встречается в W. Докажем следующее
Предложение 2.30 Слово аи не является подсловом слова
V = W7Wi+1 Wi+2n+‘i-
Доказательство. Длина v равна 2п + 4, длина bub равна п + 3 и длина аи равна п + 2, следовательно, в предложении в точности утверждается, что первый символ вхождения аи не может встречаться в bub. Предположим противное, то есть что начало аи перекрывается с bub. Ясно, что перекрытие происходит не в первой позиции bub, если перекрытие происходит позиции Wk, то это означает, что aw о = уд wnb и
это означает, что гщ. = а и wn-k — Ъ, что противоречит тому, что и -палиндром. □
Завершение доказательства Теоремы
Понятно, ЧТО В слове V = WiWi+1 Wi+2n+3 встречается ровно п + 3 подслова длины п + 2. Но из предложения следует, что среди них нет подслова аи, следовательно, какое-то подслово встречается как минимум