ФЕДОРОВА МАРIЯ ВIКТОРIВНА АВТОМАТНI ДIЇ ВIЛЬНИХ ДОБУТКIВ ГРУП : ФЕДОРОВА МАРИЯ Викторовна автоматные ДЕЙСТВИЯ СВОБОДНЫХ ДОБУТКIВ ГРУПП FEDOROVA MARIA VICTORIVNA AUTOMATIC ACTIONS OF FREE PRODUCTS OF GROUPS

Краткое описание

Київський нацiональний унiверситет iменi Тараса Шевченка Мiнiстерство освiти i науки України Київський нацiональний унiверситет iменi Тараса Шевченка Мiнiстерство освiти i науки України Квалiфiкацiйна наукова праця на правах рукопису ФЕДОРОВА МАРIЯ ВIКТОРIВНА УДК 512.54 ДИСЕРТАЦIЯ АВТОМАТНI ДIЇ ВIЛЬНИХ ДОБУТКIВ ГРУП 01.01.06 — алгебра та теорiя чисел Подається на здобуття наукового ступеня кандидата фiзико-математичних наук Дисертацiя мiстить результати власних дослiджень. Використання iдей, результатiв i текстiв iнших авторiв мають посилання на вiдповiдне джерело Науковий керiвник Олiйник Андрiй Степанович, доктор фiзикоматематичних наук, доцент Київ 2018 Змiст Перелiк умовних позначень 4 Анотацiя 6 Вступ 18 1 Необхiднi допомiжнi вiдомостi 24 1.1 Групи та їх дiї . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2 Графи та їх автоморфiзми . . . . . . . . . . . . . . . . . . . . . . 30 1.3 Автомати та графи ними визначенi . . . . . . . . . . . . . . . . 39 Висновки до роздiлу 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2 Скiнченно автоматнi занурення вiльних добуткiв груп 49 2.1 Вiльнi добутки скiнченних груп, заданi скiнченними автоматами 49 2.2 Серiя вiльних добуткiв, заданих скiнченно автоматними пiдстановками . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Висновки до роздiлу 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Графи Шраєра вiльних добуткiв груп 61 3.1 Елементарнi властивостi графiв Шраєра . . . . . . . . . . . . . 62 3.2 Властивостi графiв Шраєра на рiвнях . . . . . . . . . . . . . . . 63 3.3 Шраєрова вкладенiсть та еквiвалентнiсть . . . . . . . . . . . . . 69 3.4 Планарнiсть компонент графа Шраєра . . . . . . . . . . . . . . 72 Висновки до роздiлу 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4 Вiльнi добутки груп, заданi скiнченними автоматами 78 4.1 Конструкцiя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.2 Iзоморфне занурення . . . . . . . . . . . . . . . . . . . . . . . . . 82 2 4.3 Розклад у вiльний добуток . . . . . . . . . . . . . . . . . . . . . 83 4.4 Основна теорема . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Висновки до роздiлу 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5 Вiльнi групи, заданi скiнченними автоматами 88 5.1 Додавальна машина над бiнарним алфавiтом . . . . . . . . . . . 89 5.2 Конструкцiя автоматiв, що задають вiльну групу порядку 2 . . 93 5.3 Основний результат . . . . . . . . . . . . . . . . . . . . . . . . . 104 Висновки до роздiлу 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Висновки 111 Список використаних джерел 113 Додатки 119

Список литературы

Висновки У дисертацiї автором дослiджуються алгебраїчнi та геометричнi властивостi груп, породжених автоматними пiдстановками, та графiв Шраєра, пов’язаних з ними. Зокрема розглядаються вiльнi добутки скiнченної кiлькостi скiнченних груп та вiльнi групи скiнченного рангу. Основними новими теоретичними науковими результатами є наступнi: 1. Побудовано серiю конструкцiй точних занурень вiльних добуткiв скiнченної кiлькостi скiнченних груп, серед яких є група порядку бiльшого за 2, у групи скiнченно автоматних пiдстановок. Зокрема побудовано два автомати над алфавiтом потужностi 9, що задають вiльний добуток двох циклiчних груп порядку 3. 2. Дослiдженi властивостi орбiтальних графiв Шраєра та графiв Шраєра на рiвнях вiльного добутку скiнченної кiлькостi скiнченних груп заданих скiнченно автоматними пiдстановками за [28]. 3. Отримано умови планарностi орбiтальних графiв Шраєра побудованих точних скiнченно автоматних дiй вiльних добуткiв двох циклiчних груп. Зокрема показано, що для вiльного добутку двох скiнченних груп орбiтальнi графи Шраєра є планарними, а у випадку бiльшої кiлькостi множникiв — непланарними графами. 4. Знайдено критерiй планарностi iндуктивної границi графiв. 5. Визначено поняття шраєрової вкладеностi та показаний взаємозв’язок мiж цим поняттям та точнiстю дiї групи. 6. Доведена замкненiсть класу груп, що дiють скiнчено становими автоморфiзмами на регулярних кореневих деревах, вiдносно операцiї вiль111 ного добутку, що дало вiдповiдь на питання з Коурiвського зошита. Тобто вiльний добуток G ∗ H груп G та H, що дiють точно скiнченно становими автоморфiзмами на регулярному кореневому деревi, точно дiє скiнченно становими автоморфiзмами на деякому регулярному кореневому деревi. 7. Отримано нове точне зображення вiльної групи рангу 2 скiнченно автоматними пiдстановками. Для цього розглянуто властивостi автоматiв, вiдомих як додавальнi машини, та їх степенiв. На базi даних автоматiв побудовано новий приклад представлення вiльної групи рангу 2 заданої скiнченно автоматними пiдстановками. Доведення головної теореми є конструктивним, що дозволяє отримати алгоритм побудови за допомогою добутку твiрних W слова ω такого, на яке W дiє нетривiально.