Київський національний університет імені Тараса Шевченка

СІКОРА Віра Степанівна

УДК 512.54

Мінімальні системи твірних скінченних

гіпероктаедральних, мономіальних, Метасиметричних та автоматних груп підстановок

01.01.06 – алгебра і теорія чисел

Автореферат дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ – 2000

Дисертацією є рукопис.

Робота виконана в Київському національному університеті імені Тараса Шевченка.

Науковий керівник: доктор фізико-математичних наук, професор

СУЩАНСЬКИЙ Віталій Іванович, Київський національний університет

імені Тараса Шевченка, завідувач кафедри алгебри і математичної логіки, м.Київ.

Офіційні опоненти: доктор фізико-математичних наук, професор

ЛИМАН Федір Миколайович, Сумський державний педагогічний

університет ім. А.С.Макаренка, завідувач кафедри математики, м. Суми.

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

БОДНАРЧУК Юрій Вікторович, Національний університет “

Києво-Могилянська академія”, завідувач кафедри математики, м. Київ.

Провідна установа: Львівський національний університет ім. І.Франка, кафедра алгебри і топології, Міністерство освіти і науки України, м.Львів.

Захист відбудеться "1" лютого 2001 року о 14 год. на засіданні спеціалізованої вченої ради Д 26.001.18 при Київському національному університеті імені Тараса Шевченка за адресою: 03127, м.Київ–127, проспект академіка Глушкова, 6, механіко-математичний факультет.

З дисертацією можна ознайомитися у науковій бібліотеці Київського національного університету імені Тараса Шевченка (вул. Володимирська, 64).

Автореферат розісланий "28" грудня 2001 року.

Вчений секретар

спеціалізованої вченої ради Петравчук А.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальнiсть теми.

Задача дослiдження "економних" (зокрема, незвiдних) систем твiрних у довiльних групах є класичною для теорiї груп i розглядалася у роботах рiзних авторiв ще з самого початку становлення цiєї теорiї. Насамперед це пов'язано з тим, що у багатьох випадках iнформацiя про систему твiрних групи є вирiшальною при розв'язуваннi рiзних задач, а "економнiсть" системи твiрних дозволяє зменшити кiлькiсть потрiбних перевiрок. Якщо група є скiнченно породженою, то її незвiднi системи твiрних можуть складатися з рiзної кiлькостi елементiв. А тому для таких груп природним є питання про побудову та дослiдження систем твiрних з мiнiмальним можливим числом елементiв. Це число є важливим iнварiантом групи i дослiджувалося у роботах рiзних авторiв, зокрема Р. Стейнберга, М.Ашбахера, Р.Гуралнiка, К.Бузашi, Л.Ковача, Л. дi Мартiно, М.Тамбурiнi, I.М.Айзекса, Тхiло Цiчанга та iнших.

Одним з найважливiших результатiв, який отримано в цьому напрямку, є теорема Р.Стейнберга про 2-породжуванiсть простих груп лiєвого типу. На основi цiєї теореми М.Ашбахер та Р.Гуралнiк довели, що кожна скiнченна проста група є 2-породженою. Це твердження стало основою для багатьох дослiджень, в яких будуються конкретнi 2-елементнi системи твiрних у рiзних простих (зокрема, лiнiйних) групах, дослiджуються розклади елементiв групи за такими твiрними.

При переходi до вивчення цього питання для непростих груп природно розглядати спочатку розширення кiлькох простих груп або їх прямих добуткiв. У зв'язку з цим виникає задача дослiдження мiнiмальних (за кiлькiстю елементiв) систем твiрних у вiнцевих добутках. Ряд результатiв про найменше можливе число твiрних у таких добутках отримано в роботах К.Бузачi, Л.Ковача та iн. Майже очевидно, що це число не перевищує суми вiдповiдних iнварiантiв для вiнцевих спiвмножникiв, однак ця оцiнка не є точною, причому в загальному випадку встановити точну оцiнку не вдається. А тому природно виникає задача побудови мiнiмальних (за кiлькiстю елементiв) систем твiрних у вiнцевих добутках тих чи iнших конкретних груп. Одними з найбiльш уживаних таких вiнцевих добуткiв є метасиметричнi групи, тобто вiнцевi добутки скiнченних симетричних груп та близькi до них. Вони часто виникають у дослiдженнях з дискретної математики як групи симетрiй рiзних дискретних структур (графiв, дискретних метричних просторiв, впорядкованих множин тощо), використовуються при класифiкацiї бульових функцiй та функцiй багатозначної логiки, у теорiї перелiку, в теорiї автоматiв i автоматних вiдображень.

Зокрема, група автоматних пiдстановок над фiксованим алфавiтом та її природним чином iндукованi дiї є iзоморфними, як групи пiдстановок, вiнцевим добуткам симетричних груп. На основi цього i здiйснювалися першi дослiдження груп автоматних пiдстановок, в яких, зокрема, розглядалося питання про їх незвiднi системи твiрних (роботи Я.Хорейса, Б.Чаканя, Ф.Гечега, В.П.Заровного,).

Вагомий внесок у розвиток нового роздiду теорiї груп, тісно пов'язаного з теорiєю автоматiв, внесли українськi вченi В.М. Глушков, Л.А. Калужнiн, А.А. Летiчевський, А.В. Анiсiмов, В.I. Сущанський та iншi.

Усе вищенаведене свiдчить про те, що дослiдження систем твiрних вiнцевих добуткiв симетричних та близьких до них груп є актуальною задачею. Розгляду цiєї задачi i присвячена дана дисертацiйна робота.

Зв'язок роботи з науковими програмами, планами, темами.

Тематика дисертацiї знаходиться в руслi основних дослiджень кафедри алгебри та математичної логiки Київського нацiонального унiверситету iм. Тараса Шевченка, якi ведуться в рамках науково-дослiдної теми "Теорiя алгебраїчних систем та їх зображень i її застосування" (номер держреєстрацiї 0197U003160).

Мета i задачi дослiдження.

Метою дисертацiйної роботи є побудова мiнiмальних (за кiлькiстю елементiв) систем твiрних вiнцевих добуткiв симетричних та близьких до них груп i оцiнка дiаметрiв їх графiв Келi, що вiдповiдають таким системам твiрних.

Для досягнення мети необхiдно оцiнити кiлькiсть елементiв у мiнiмальних системах твiрних розглядуваних груп, сконструювати конкретнi такi системи та оцiнити довжини розкладiв елементiв групи за кожною з побудованих систем твiрних.

Наукова новизна одержаних результатiв.

У дисертацiї отримано такi результати:–

доведено, що гiпероктаедральнi, "дуальнi" до них та повнi мономiальнi групи даної вимiрностi n над скiнченним полем є 2-породженими; знайдено конкретнi двохелементнi системи твiрних для цих груп; оцінено зверху діаметри графів Келі цих груп для побудованих систем твірних;–

встановлено, що мiнiмальнi (за потужнiстю) системи твiрних метасиметричних груп скiнченного рангу складаються з r елементiв (); оцiнено дiаметр графа Келi довiльних таких груп при ;–

встановлено, що iндукованi групи автоматних пiдстановок на словах даної довжини є точно r-породженими;–

наведено коректне доведення нескiнченної породжуваностi основних груп автоматних пiдстановок.

Усi отриманi науковi результати є новими. При побудовах мiнiмальних систем твiрних використовувались певнi двохелементнi системи твiрних симетричних груп. Верхнi оцiнки дiаметрiв графiв Келi дослiджуваних груп будувалися з використанням тотожностей, якими характеризуються розклади довiльних елементiв симетричної групи на добуток твiрних, та оцiнок довжин таких розкладiв.

Практичне значення одержаних результатiв.

Результати диcертацiї мають теоретичний характер. Вони можуть бути використанi для вивчення будови груп, близьких до вiнцевих добуткiв симетричних чи циклiчних груп i знайти своє застосування в подальших дослiдженнях груп автоморфiзмiв графiв, груп симетрiй булевих функцiй i функцiй багатозначної логiки, їх iнварiантiв, iзометрiй ультраметричних просторiв берiвського типу.

Особистий внесок здобувача.

Усi результати дисертацiйної роботи одержано самостiйно або за особистою участю автора. Результати спiльної статтi [5] викладено в четвертому роздiлi. З них теореми 4.1 і 4.3 належать дисертанту, а доведення теорем 4.2 і 4.5 отримано при рівному вкладі співавторів.

Апробацiя результатiв дисертацiї.

Результати, якi викладенi в дисертацiї, доповiдалися:

на II Мiжнароднiй алгебраїчнiй конференцiї в Українi, присвяченiй пам'ятi проф. Л.А.Калужнiна (Київ – Вiнниця, 1999 р.);

на конференцiї молодих математикiв "Сучасна алгебра та її застосування", присвяченiй 40-рiччю кафедри алгебри та математичної логiки Київського нацiонального унiверситету iм. Тараса Шевченка (Київ, 1999 р.);

на VIII Мiжнароднiй науковiй конференцiї iм. академіка М.Кравчука (Київ, 2000 р.);

на науковому семiнарi математичного факультету Чернiвецького національного унiверситету iм. Ю.Федьковича (Чернiвцi, 1999 p.);

на наукових семiнарах кафедри алгебри i геометрiї математичного факультету Чернiвецького національного унiверситету iм. Ю.Федьковича (Чернiвцi, 1999 – 2000 рр.);

на алгебраїчному семiнарi Київського нацiонального унiверситету iм. Тараса Шевченка (Київ, 2000 р.).

Публiкацiї.

Основнi результати дисертацiї опублiковано в 7 наукових роботах [1–7]. З них 5 статей у фахових виданнях з перелiку N1, затвердженого ВАК України, та двi тези доповiдей на мiжнародних наукових конференцiях.

Структура та обсяг дисертацiї.

Дисертацiя складається з вступу, чотирьох роздiлiв, висновкiв та списку використаних джерел, який мiстить 59 найменувань. Повний обсяг роботи становить 140 сторiнок, з них 133 сторiнки основного змiсту та 7 сторiнoк використаних джерел.

ОСНОВНИЙ ЗМIСТ РОБОТИ

Перший роздiл дисертацiї носить допомiжний характер i мiстить основнi означення та властивостi груп, якi розглядаються у роботi.

У пiдроздiлi 1.1 обговорюються незвiднi системи твiрних (для скорочення називатимемо такi системи базами) симетричних груп. Сформульовано твердження, якi можна використовувати для їх розпiзнавання. Наведено приклади рiзних систем твiрних та оцiнено зверху мiнiмальну можливу довжину розкладу довiльної пiдстановки на добуток елементiв таких систем.

Для системи твiрних символом позначено довжину мiнiмального можливого розкладу пiдстановки на добуток елементiв iз i покладено

для довiльного натурального . Зафiксовано спецiальнi системи твiрних групи

якi будуть iстотно використовуватися при побудовах мiнiмальних баз вiнцевих добуткiв. Доведено, що та не перевищують для довiльного (теорема 1.1).

У пiдроздiлi 1.2 дано означення вiнцевого добутку за довiльною (скiнченною чи нi) послiдовнiстю груп пiдстановок; розглянуто поняття вiнцевого степеня, фiнiтарного вiнцевого добутку, обмеженого та фiнiтарного вiнцевого степенiв. Наведено деякi відомі їх властивостi. Зокрема, визначено природну метрику на довiльному нескiнченно iтерованому вiнцевому добутку груп пiдстановок.

Пiдроздiл 1.3 мiстить означення метасиметричних груп – (скiнченно або нескiнченно) iтерованих вiнцевих добуткiв симетричних груп , . Наводяться основнi властивостi таких груп, вказано деякi їх застосування.

У пiдроздiлi 1.4 подано означення iнiцiальних автоматiв Мiлi над скiнченним алфавiтом та пов'язаних з ними понять: сильно зв'язаного автомата, пiдстановкового автомата, автоматного перетворення, рiвносильних автоматiв тощо. Описано зв'язок мiж автоматними пiдстановками та автоморфiзмами вiдповiдних кореневих дерев.

У другому роздiлi будуються мiнiмальнi (за кiлькiстю елементiв) бази гiпероктаедральних, "дуальних" до них, мономiальних та метасиметричних (рангу 2) груп.

Зокрема, у пiдроздiлi 2.1 розглядаються означення гiпероктаедральної групи , яка вводиться як група перестановок i змiн напрямiв векторiв ортонормованої бази евклiдового простору вимiрностi . Група має також природну реалiзацiю як група симетрiй -вимiрного куба. Як абстрактна група, вона iзоморфна вiнцевому добутку wr симетричної групи з адитивною групою кiльця лишкiв за модулем 2.

Основнi властивостi гiпероктаедральних груп пiдсумовано у вiдомiй роботi М.Бакi, де, зокрема, побудовано деякi їх трьохелементнi бази. У цьму напрямку ми доводимо таке твердження.

Теорема 2.1. Для довiльного натурального гiпероктаедральна група має базу, яка складається з двох елементiв.

Зокрема, двохелементними базами групи wr , iзоморфної , будуть, наприклад, пари

при непарному чи при парному .

Теорема 2.2. Вiнцевий добуток wr породжується двома пiдстановками.

Далі групу wr називаємо "дуальною" до гіпероктаедральної групи . Отримано, що для мiнiмальними базами будуть пари

при непарному або при парному .

У пiдроздiлi 2.2 розглядаються мономiальнi групи вимiрностi над скiнченним полем ( – просте). Кожен елемент такої групи однозначно визначається деякою пiдстановкою на множинi та вектором . Мають мiсце такi твердження.

Теорема 2.3. Мономiальна група , де – просте, породжується двома мономiальними матрицями:

(i)

якщо непарне;

(ii)

якщо парне, де є твiрним, а 1 – нейтральним елементами циклiчної групи .

Теорема 2.4. Мономiальна група , де , , породжується двома мономiальними матрицями вигляду:

(j)

якщо непарне;

(jj)

якщо парне, де є твiрним, а 1 – нейтральним елементами циклiчної групи .

Пiдроздiл 2.3 присвячено доведенню такого твердження.

Теорема 2.5. Група wr для довiльних натуральних чисел , є 2-породженою, тобто мiстить незвiдну систему твiрних, яка складається з двох елементiв.

А саме, якщо – непарнi, то

якщо – непарне, – парне, то

якщо – парне, – непарне, то

якщо ж – парнi, то

утворюють незвiднi системи твiрних групи wr .

Наведено приклад двохелементної системи твiрних вiнцевого добутку wr, вiдмiнної вiд побудованої при доведеннi теореми 2.5.

У третьому роздiлi отримано полiномiальнi оцiнки для дiаметрiв графiв Келi груп з попереднього роздiлу вiдносно побудованих там двохелементних систем твiрних.

Зокрема, у пiдроздiлi 3.1 доведено такi твердження.

Теорема 3.1. Дiаметр графа Келi гiпероктаедральної групи вiдносно двохелементних систем твiрних (побудованих при доведеннi теореми 2.1) не перевищує для довiльного натурального .

Теорема 3.2. Дiаметр графа Келi групи wr вiдносно двохелементних систем твiрних (побудованих при доведеннi теореми 2.2) не перевищує для довiльного натурального .

Наступний пiдроздiл 3.2 присвячено знаходженню верхнiх оцiнок дiаметрiв графiв Келi мономiальної групи вiдносно систем твiрних, побудованих у теоремах 2.3 та 2.4. А саме, доведено таке твердження.

Теорема 3.3. Дiаметр графа Келi мономiальної групи , вимiрностi над скiнченним полем , , , вiдносно двохелементних систем твiрних не перевищує числа для довiльних натуральних чисел та простого .

У пiдроздiлi 3.3 доведена

Теорема 3.4. Дiаметр графа Келi метасиметричної групи wr вiдносно двохелементних систем твiрних (побудованих при доведеннi теореми 2.5) не перевищує для довiльних цiлих .

Четвертий роздiл дисертацiї присвячено дослiдженню мiнiмальних (за кiлькiстю елементiв) незвiдних систем твiрних метасиметричних груп скiнченного та нескiнченного рангу i груп автоматних пiдстановок над даним скiнченним алфавiтом.

Позначимо – вiдповiдно групи автоматних, скiнченно автоматних та фiнiтарних автоматних пiдстановок над деяким алфавiтом – множину всiх слiв у алфавiтi ; – пiдмножину , яка складається iз слiв довжини точно . При довiльному пiдмножина є iнварiантною вiдносно перетворень iз , тобто можна розглядати групу дiй . Позначимо ядро цiєї дiї i визначимо такi фактор-групи:

У пiдроздiлi 4.1, який має допомiжний характер, наведено ряд вiдомих тверджень про основнi автоматнi групи. Показано (лема 4.3), що для довiльного мають мiсце рiвностi Аналогiчно (леми 4.5, 4.6), для довiльного , охарактеризовано:

а) групу пiдстановок , , як -ий вiнцевий степiнь симетричної групи ;

б) групу пiдстановок , , як вiнцевий добуток нескiнченної послiдовностi симетричних груп степеня в його iнтранзитивнiй реалiзацiї;

в) групу, як обмежений вiнцевий степiнь в його iнтранзитивнiй реалiзацiї;

г) групу, як фiнiтарний вiнцевий добуток i скрiзь щiльну пiдгрупу метричної групи .

У пiдроздiлi 4.2 розглядаємо спочатку системи твiрних групи , якi складаються тільки з координатних таблиць. Для цього в симетричнiй групi фiксовано деяку систему твiрних i будуються таблицi вигляду

(1)

в яких

(2)

де – одиничний елемент групи , – фiксований кортеж,

Теорема 4.1. Система елементiв, визначених формулами (1) та (2), є системою твiрних групи при довiльному виборi кортежiв . Ця система буде незвiдною тодi i тiльки тодi, коли система буде незвiдною.

Наступне твердження використовується при доведеннi теорем 4.3 та 4.4.

Теорема 4.2. Комутант мiстить тi i тiльки тi таблицi , для яких виконується спiввiдношення

де символом позначено добуток всiх значень координатної функцiї , взятих у певному порядку.

Теорема 4.3. Кожна мiнiмальна (за кiлькiстю елементiв) система твiрних групи для довiльного мiстить рiвно елементiв.

Це твердження без змiн узагальнюється на випадок метасиметричних груп :

Теорема 4.4. Кожна мiнiмальна (за кiлькiстю елементiв) система твiрних метасиметричної групи довiльного скiнченного рангу мiстить рiвно елементiв.

У пiдроздiлi 4.3 розглянуто застосування отриманих для метасиметричних груп результатiв до основних груп автоматних пiдстановок.

А саме, дано коректне доведення нескiнченної породжуваностi в алгебраїчному сенсi для фiнiтарної групи автоматних пiдстановок , групи скiнченно автоматних пiдстановок та нескiнченної породжуваностi в топологiчному сенсi групи всiх автоматних пiдстановок (теорема 4.5), чим виправлено помилки в ранiше опублiкованих доведеннях iнших авторiв8,

Побудовано цiлi серiї незвiдних систем твiрних фiнiтарної групи, якi мiстять всi ранiше вiдомi такi бази. А саме, нехай – база групи , i для довiльного натурального фiксовано деякий набiр , який складається з не обов'язково рiзних кортежiв довжини над алфавiтом . Для кожного кортежа i пiдстановки будується деякий автомат , який визначає пiдстановку множини , що включається до системи твiрних.

Теорема 4.6. Система автоматних пiдстановок, визначених автоматами вигляду

є незвiдною системою твiрних групи всiх фiнiтарних автоматних перетворень i системою твiрних групи (або ) в топологiчному розумiннi.

ВИСНОВКИ

У дисертацiйнiй роботi вивчаються мiнiмальнi (за кiлькiстю елементiв) системи твiрних гiпероктаедральних, мономiальних, та метасиметричних груп. Побудовано конкретнi мiнiмальнi системи твiрних в таких групах. Отримано верхнi оцiнки для дiаметрiв графiв Келi цих груп щодо побудованих систем твiрних.

Одержанi результати застосовано до дослiдження систем твiрних метасиметричних груп скiнченного рангу та груп автоматних пiдстановок, якi дiють на множинi слiв довжини над даним алфавiтом або на множинi всiх слiв над цим алфавiтом. А саме, встановлено, що метасиметричнi групи скiнченного рангу та iндукованi групи автоматних пiдстановок на множинi слiв довжини над даним скiнченним алфавiтом мають мiнiмальнi (за кiлькiстю елементiв) cистеми твiрних, якi мiстять рiвно елементiв. Описано процедуру побудови таких систем твiрних. На пiдставi цього вперше подано коректне доведення нескiнченної породжуваностi основних груп автоматних пiдстановок. Отриманi результати застосовуються при дослiдженнi незвiдних (в алгебраїчному або топологiчному розумiннi) систем твiрних основних груп автоматних пiдстановок.

Автор висловлює щиру подяку науковому керiвнику доктору фiзико-математичних наук, професору Сущанському В.I. за постiйну увагу, консультацiї та корисне обговорення результатiв.

ПУБЛIКАЦIЇ АВТОРА ЗА ТЕМОЮ ДИСЕРТАЦIЇ

Сiкора В.С. Двохелементнi бази гiпероктаедральних груп // Вiсн. Київськ. ун-ту. Серiя: Фiзико-математичнi науки.– 1999.– N1.– С.87-93.

Ciкора В.С. Розклади елементiв мономiальних груп над скiнченними полями за мiнiмальними базами // Вiсн. Київськ. ун-ту. Серiя: Фiзико-математичнi науки.– 1999.– N3.– С.71-79.

Ciкора В.С. Дiаметр графа Келi гiпероктаедральних та мономiальних груп // Вiсн. Київськ ун-ту. Серiя: Фiзико-математичнi науки.– 2000.– N2.– С. 119-123.

Ciкора В.С. Дiаметр графа Келi вiнцевого добутку двох симетричних груп для двохелементної системи твiрних // Наук. вiсн. Чернiвецького ун-ту: Зб. наук. праць. Математика.– Чернiвцi: ЧДУ, 2000.– Вип.76.– С.99-105.

Cикора В.С., Сущанский В.И. Системы порождающих групп автоматных подстановок // Кибернетика и системный анализ.– 2000.– N3.– С. 121-133.

Sikora V.S. On generators of the wreath products on symmetric groups // Матерiали II-ої мiжнар. алгебр. конф. в Українi, присвяченої пам'ятi професора Л.А.Калужнiна (1914–1990).– Вiнниця, 1999.– С.45-46.

Ciкора В.С. Дiаметр графа Келi вiнцевого добутку симетричних груп // Матерiали VIII-ї Мiжнар. наук. конф. iм. академiка М.Кравчука.– К.: НТУУ (КПI).– 2000.– С.360.

АНОТАЦIЯ

Ciкора В.С. Мiнiмальнi системи твiрних скiнченних гiпероктаедральних, мономiальних, метасиметричних та автоматних груп пiдстановок.– Рукопис.

Дисертацiя на здобуття наукового ступеня кандидата фiзико-математичних наук за спецiальнiстю 01.01.06 – алгебра i теорiя чисел. – Київський нацiональний унiверситет iменi Тараса Шевченка, Київ, 2000.

У роботi побудовано мiнiмальнi (за кiлькiстю елементiв) системи твiрних гiпероктаедральних, мономiальних, та метасиметричних груп. Встановлено, що гiпероктаедральнi, мономiальнi та метасиметричнi рангу 2 групи є 2-породженими. Отримано верхнi оцiнки для дiаметрiв графiв Келi цих груп вiдносно побудованих двохелементних систем твiрних. Доведено, що метасиметричнi групи довiльного скiнченного рангу , є -породженими, причому – найменше можливе таке число.

Одержанi результати застосовано до дослiдження систем твiрних груп автоматних пiдстановок, якi дiють на множинi слiв фiксованої довжини або на множинi всiх слiв над даним алфавiтом. Дано коректне доведення нескiнченної породжуваностi основних груп автоматних пiдстановок, якi дiють на множинi всiх слiв над даним алфавiтом, чим виправлено помилки в ранiше опублiкованих доведеннях iнших авторiв.

Ключовi слова: незвiдна система твiрних, гiпероктаедральна група, мономiальна група, метасиметрична група, граф Келi групи, група автоматних пiдстановок.

АННОТАЦИЯ

Cикора В.С. Минимальные системы образующих конечных гипероктаэдральных, мономиальных, метасимметрических и автоматных групп подстановок.– Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.06 – алгебра и теория чисел. – Киевский национальный университет имени Тараса Шевченко, Киев, 2000.

В диссертации исследуются минимальные (по числу элементов) системы образующих гипероктаэдральных (при натуральных ), "дуальных" к ним групп wr , , мономиальных групп над конечным полем F ( – простое) метасимметрических ранга r групп

(при натуральных ), сплетенной степени

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

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

Установлено, что при любых натуральных и любом простом мономиальная группа над полем F, состоящем из элементов, является 2-порожденной группой. Построено конкретные двухэлементные системы образующих группы , вид которых зависит от четности или нечетности чисел n и-1, т.е. принадлежащие к одному из четырех типов.

Доказано, что минимальные (по количеству элементов) системы образующих метасимметрических групп ранга r ( – натуральные числа) состоят в точности из r элементов. Доказательство этой теоремы осуществляется индукцией по r. Cлучай r=2, являющийся базой индукции, требует отдельного рассмотрения. В этом случае построенные в работе системы образующих сплетения также принадлежат к одному из четырех типов, определяемых четностью или нечетностью чисел .

Получены оценки сверху для диаметров графов Кэли гипероктаэдральных, "дуальных" к ним, мономиальных и метасимметрических ранга 2 групп относительно построенных минимальных систем образующих. Эти оценки являются полиномиальными относительно степеней сплетаемых групп или порядка соответствующих матриц и числа элементов поля F в случае мономиальных групп, причем суммарная степень возникающих при этом полиномов не превышает 11.

Поскольку группа всех автоматных подстановок, определяемых автоматами Мили над конечным алфавитом X, |X| = n, при действии на множестве слов длины r изоморфна r-ой сплетенной степени симметрической группы , т.е. то полученные результаты о системах образующих для метасимметрических групп используются в работе при исследовании неприводимых систем порождающих основных автоматных групп. А именно, группа также имеет минимальную (по числу элементов) систему порождающих, которая состоит ровно из r элементов.

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

Построены новые классы неприводимых систем образующих финитарной группы автоматных подстановок F(x) над конечным алфавитом X, которые включают в себя все ранее известные типы таких систем порождающих.

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

ABSTRACT

Sikora V.S. Minimal systems of generators of finite hyperoctahedral, monomial, metasymmetric groups and groups of automatic permutations.– Manuscript.

Dissertation for the Degree of Philosophy Doctor (Ph.D.) in speciality 01.01.06 – algebra and number theory.--- Kiev National Taras Shevchenko University, Kiev, 2000.

The minimal (in number of elements) systems of generators of finite hyperoctahedral, monomial and metasymmetric groups are studied. It is proved that all hyperoctahedral and monomial groups are 2-generated, while the minimal number of generators of the metasymmetric groups of rank is exactly r. In all cases, explicit systems of generators are constructed. The upper estimates are given for the diameters of Cayley graphs of all these groups with respect to the constructed minimal systems of generators.

The obtained results are applied to the investigation of systems of generators for the automatic permutation groups acting on the set of all words in the finite alphabet or on the set of all words of fixed length such an alphabet. A correct proof is given that the basic groups of automatic permutations, which act on the sets of the all words, are not finitely generated (the preceding publications on this topic had gaps).

Key words: the irreducible system of generators, hyperoctahedral group, monomial group, metasymmetric group, Cayley's graph of group, the group of automatic permutations.