Вільні групи та напівтрупи автоматних перетворень

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Вільні групи та напівтрупи автоматних перетворень

Автореферат

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

Загальна характеристика роботи

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

Існування зображення вільної групи рангу 2 підстановками нескінченного степеня гарантується теоремою Келі про зображення груп підстановками. Разом з тим, в кількох роботах останніх років будуються її високо транзитивні підстановкові зображення (група підстановок нескінченного степеня називається високо транзитивною, якщо вона є k-транзитивною для кожного натурального k).

Cеред інших зображень вільної групи слід виділити її зображення елементарними функціями над полями нульової характеристики відносно суперпозиції. А саме, перетворення дійсного або комплексного поля і , де q>1 - фіксоване непарне натуральне число у випадку поля i довільне натуральне у випадку , породжують вільну групу.

Один з фундаментальних результатів про вільні групи, відомий під назвою альтернатива Тітса вперше доводиться в оригінальній роботі у такому формулюванні:

Над полем характеристики 0 довільна лінійна група або містить неабелеву вільну підгрупу, або в неї є розв'язна підгрупа скінченного індексу.

Цей результат був певним поштовхом у напрямку дослідження не просто окремих зображень вільної групи, а поведінки множини вільних підгруп серед усіх підгруп тієї чи іншої групи. З'явилася серія результатів, у яких стверджується, що в тому чи іншому розумінні, «більшість» підгруп даної групи є вільними. В якому сенсі вживається тут слово «більшість»?

Поперше, «більшість» може розглядатися в розумінні міри. А саме, на даній групі вводиться деяка міра, вона розповсюджується на kтий () декартів степінь цієї групи і доводиться, що множина тих елементів цього степеня, компоненти котрих породжують не вільну групу, має міру 0. Так, Д. Епштейн довів, що відносно міри Хаара «більшість» скінченно породжених підгруп зв'язної, скінченновимірної нерозв'язної групи Лі вільні.

Подруге, - в категорному розумінні. На групі вводиться метрика, відносно якої групова операція є неперервною, а одержаний метричний простір - повним. Повним простором тоді є і довільний скінченний його степінь. Тепер розглядається множина тих кортежів цього степеня, компоненти яких вільну групу не породжують і доводиться, що така множина є множиною першої категорії (у розумінні Бера), тобто її можна отримати, як зліченне об'єднання ніде не щільних множин. За теоремою Бера про , доповнення цієї множини є щільним і тому можна говорити про «всюдисущість» вільних груп серед скінченно породжених підгруп даної групи.

Зокрема, Д.Діксон розглянув у симетричній групі підстановок нескінченного степеня S() метрику, відносно якої дві різні підстановки знаходяться на відстані тоді й лише тоді, коли m - найменше таке натуральне число, що його образи або прообрази відносно цих підстановок є різними. Тоді, у розумінні категорії, «більшість» скінченно породжених підгруп S() є вільними. Більше того, в цій же роботі доведено, що вільні підгрупи є всюдисущими і серед високо транзитивних підгруп симетричної групи нескінченного степеня.

Нарешті, М. Бхатачаржи показала, що «більшість» скінченно породжених підгруп вінцевих добутків за нескінченними послідовностями нетривіальних груп є вільними як у категорному розумінні, так і в розумінні міри.

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

Групи автоматних підстановок є об'єктом численних досліджень останніх років. Використовуючи зв'язок цих груп з вінцевими добутками за нескінченними послідовностями груп підстановок та групами автоморфізмів регулярних кореневих дерев, різними авторами будувались приклади нескінченних скінченно породжених періодичних груп, приклади груп проміжного росту та аменабельні неелементарні групи як підгрупи групи автоматних підстановок над деяким алфавітом. Разом з тим, досліджень будови самих груп автоматних підстановок було мало, а будова напівгрупи автоматних перетворень не вивчалась взагалі.

Мета роботи. Метою дисеpтаційної pоботи є

розвинути технічний апарат обчислень в напівгрупах автоматних перетворень та групах скінчено автоматних підстановок і описати відношення Гріна в напівгрупі всіх автоматних перетворень над скінченним алфавітом;

навести загальні конструкції вільних піднапівгруп у напівгрупі автоматних перетворень, виявити, що в категорному розумінні «більшість» k-породжених () піднапівгруп цієї напівгрупи є вільними і побудувати конкретні приклади вільних напівгруп автоматних перетворень;

знайти явні зображення вільної групи рангу 2 автоматними підстановками над двоелементним алфавітом;

вказати явне занурення вільного добутку довільного скінченного числа циклічних груп другого порядку і вільної групи рангу 2 в групу скінченно автоматних підстановок над двоелементним алфавітом і, як наслідок, розв'язати проблему С.Сідкі про зображуваність групи скінченно автоматними підстановками над триелементним алфавітом.

Методи дослідження. У дисеpтаційній pоботі викоpистовуються методи теоpії гpуп та напівгруп, зокpема комбінаторної теоpії гpуп та напівгруп, а також топологічні методи.

Наукова новизна. В дисертаційній роботі отримано такі нові результати:

доведено, що більшість (у категорному розумінні Бера) скінченно породжених піднапівгруп напівгрупи автоматних перетворень над скінченним алфавітом є вільними;

в цій напівгрупі описано відношення Гріна;

знайдено загальні конструкції вільних напівгруп автоматних перетворень і побудовано континуальну родину таких напівгруп;

наведено ряд зображень неабелевої вільної групи автоматними підстановками над двоелементним алфавітом, котрі не є скінченно автоматними;

вказано зображення вільної групи рангу 2 скінченно автоматними підстановками над алфавітом із двох елементів.

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

Апробація роботи. Результати, отpимані в дисеpтації, доповідалися: на семінаpі «Теоpія гpуп та напівгpуп» у Київському Унівеpситеті імені Таpаса Шевченка; на Київському алгебраїчному семінарі; на Всеукраїнській науковій конференції «Розробка та застосування математичних методів в науково-технічних дослідженнях» (Львів, 1995); на П'ятій Міжнаpодній конфеpенції імені академіка М. Кpавчука (Київ, 1996), а також на міжнаpодній конфеpенції «Groups and Group Rings VI» (Wisla, 1998).

Публікації. Основні pезультати дисеpтації опубліковано в 4 наукових статтях, а також в 3 тезах доповідей наукових конференцій, список яких подано в кінці автореферату.

Особистий внесок дисертанта. Всі pезультати дисеpтації отpимані автоpом самостійно.

Структура і об'єм роботи. Дисеpтаційна pобота складається зі вступу, трьох pозділів, висновків і списку літеpатуpи, викладених на 111 стоpінках машинописного тексту. Список літеpатуpи містить 38 найменувань.

Зміст роботи

сідкі напівгрупа автоматний підстановка

У вступі зроблено короткий огляд літератури за темою дисертації, викладено основні результати роботи.

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

У параграфі 1.1 наведено означення автомата над скінченним алфавітом . Автоматом над називається четвірка , в якій:

Q - непорожня, не більш ніж зліченна множина, елементи якої називаються внутрішніми станами автомата;

- деякий виділений внутрішній стан автомата, ініціальний стан;

- функція переходів;

- функція виходів.

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

В параграфі 1.2 вводяться до розгляду основні об'єкти дослідження в дисертаційній роботі. Це, насамперед, напівгрупа AT() автоматних перетворень над алфавітом (відносно суперпозиції). В цій напівгрупі виділяються піднапівгрупа FAT() скінченно автоматних перетворень, а також підгрупи AP() автоматних і FAP() скінченно автоматних підстановок (бієктивних перетворень) над . Зазначається, що кожна з цих напівгруп чи груп діє на множинах скінченних і нескінченних слів над алфавітом .

Параграф 1.3 присвячено вінцевим добуткам за нескінченними послідовностями напівгруп перетворень і встановленню зв'язку між ними та напівгрупою автоматних перетворень над деяким алфавітом. А саме, вiнцевим добутком за нескiнченною послiдовнiстю напiвгруп перетворень , називається напiвгрупа всiх тих перетворень s множини

,

у яких для довiльної послiдовностi

значення kтої координати її образу

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

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

, .

Гомоморфізмами, які визначають такий зворотний спектр, є природні проектування.

Для довільного натурального k вінцеві добутки

та

подібні як напівгрупи перетворень.

Якщо k-тий множник вінцевого добутку одержано як перетин деякої родини напівгруп, то сам вінцевий добуток є перетином вінцевих добутків, у яких k-ті множники пробігають цю родину напівгруп, а всі інші збігаються з множниками початкового вінцевого добутку.

Якщо k-тий множник вінцевого добутку породжується деякою родиною напівгруп, перші k-1 множників діють на скінченних множинах і всі напівгрупи містять одиницю, то сам вінцевий добуток породжується вінцевими добутками, у яких k-ті множники пробігають цю ж саму родину напівгруп, а всі інші збігаються з множниками початкового вінцевого добутку.

Вінцевий добуток за послідовністю напівгруп перетворень , транзитивно діє на множині M тоді й лише тоді, коли кожен з множників є транзитивною напівгрупою.

Доводиться

Теорема 1.19. Напiвгрупа iзоморфна як напiвгрупа перетворень вiнцевому добутку за послiдовнiстю симетричних напiвгруп степеня n=:

),

де .

Звідси одержано

Наслідок 1.21. Напівгрупа автоматних перетворень є піднапівгрупою в напівгрупі автоматних перетворень (n>1).

Відношення Гріна L, R, H, D, J в напівгрупі AT() вивчаються в параграфі 1.4. Символом ranF позначається область значень автоматного перетворення , а класами еквівалентності на множині є повні прообрази слів із ranF. Основний результат цього параграфа формулюється таким чином.

Теорема 1.27. Нехай F, GAT(). Тоді

1. F L G ranF=ranG;

2. F R G ;

3. F H G ranF=ranG і ;

4. F D G існує така H AP(), що ran(FH)=ranG;

5. J = D.

Зауважимо, що ця теорема є природним узагальненням опису відношень Гріна в симетричній напівгрупі.

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

У параграфі 2.1 ми вводимо на напівгрупі AT() природну метрику, за якою відстань між двома різними автоматними перетвореннями рівна тоді й лише тоді, коли m - довжина найкоротшого слова, на якому ці перетворення діють по-різному. У лемі 2.1 встановлюється, що одержаний метричний простір буде повним, а напівгрупова операція - неперервним відображенням у визначеній метриці. Повним буде і kтий () декартів степінь цього простору.

В параграфі 2.2 розглядається множина F тих елементів простору AT(), компоненти яких породжують вільну напівгрупу рангу k. Основними результатами параграфа є такі дві теореми, які дозволяють стверджувати, що в категорному розумінні «більшість» k-породжених піднапівгруп напівгрупи AT() є вільними напівгрупами рангу k.

Теорема 2.5. Пiдмножина F щiльна в AT.

Теорема 2.6. Пiдмножина ATF є множиною першої категорії в AT.

В параграфі 2.3 будується континуальна родина вільних піднапівгруп у напівгрупі AT (p - просте число). Алфавіт у цьому випадку ототожнюється із полем Z і розглядається підгрупа тих автоматних підстановок, які можна задавати за допомогою нескінченних таблиць

таких, що

Z, ZJ,

де J- iдеал в Z, породжений многочленами

.

Розглядається довільна послідовність

a Z.

Теорема 2.9 встановлює, що при p>2 таблиці

породжують вільну піднапівгрупу рангу 2 в напівгрупі AT.

В теоремі 2.10 доведено, що таблицями

породжується вільна піднапівгрупа рангу 2 в напівгрупі AT.

Ці дві теореми дозволяють сформулювати

Наслідок 2.11. Кожна з напівгруп (p - просте) містить континуум багато попарно різних вільних піднапівгруп рангу 2.

Вивчено питання скінченної автоматності побудованих напівгруп. Встановлються (твердження 2.13), що ці напівгрупи будуть скінченно автоматними в тому і лише тому разі, коли послідовність a є майже періодичною, тобто періодичною, починаючи з деякого місця.

В теоремі 2.14 будуються нові серії вільних піднапівгруп напівгрупи AT.

Третій розділ присвячено дослідженню вільних груп автоматних підстановок. Розглядається група AP автоматних підстановок над алфавітом Z.

У параграфі 3.1 будується серія 2-породжених підгруп цієї групи. Доводиться (теореми 3.2, 3.3), що кожна із побудованих груп є вільною групою рангу 2. У твердженні 3.4 встановлюється, що всі вони не є групами скінченно автоматних підстановок.

Основним результатом параграфа 3.2 є

Теорема 3.7. Нехай k 2. Група FAP містить підгрупу, ізоморфну вільному добутку k екземплярів циклічної групи C другого порядку.

Для доведення явно вказується k скінченно автоматних підстановок над двоелементним алфавітом, які в групі FAP мають порядок 2 і таких, що група, ними породжена, розкладається у вільний добуток k своїх циклічних підгруп другого порядку.

В параграфі 3.3 будуються скінченні автомати, які породжують вільний добуток C*C*C у групі FAP. Кількість внутрішніх станів цих автоматів рівна відповідно 10, 10 і 8. Автоматні підстановки, визначені цими автоматами, задаються такими таблицями:

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

Розглядаються таблиці

і доводиться

Теорема 3.9. Cкінченно автоматні підстановки G i G вільно породжують вільну підгрупу рангу 2 у групі скінченно автоматних підстановок над двоелементним алфавітом.

Зазначимо, що це є перший приклад вільної неабелевої групи скінчено автоматних підстановок над двоелементним алфавітом, який супроводжується повним доведенням. У роботі С.В. Альошина також будувався приклад такої групи, проте повне доведення автором досі не опубліковане, а спроби інших математиків завершити його не дали жодних результатів.

Далі наводиться

Лема 3.13. Нехай G - група Припустимо, що H є підгрупою групи скінчено автоматних підстановок над n-елементним алфавітом. Тоді група G є підгрупою групи .

За допомогою цієї леми, користуючись теоремою 3.9, ми доводимо

Теорему 3.14. Група ізоморфно занурюється у групу FAP скінчено автоматних підстановок над триелементним алфавітом.

Ця теорема дає позитивну відповідь на проблему С.Сідкі про існування такого занурення. Зазначимо, що ізоморфно занурити групу у групу FAP скінчено автоматних підстановок над двоелементним алфавітом неможливо, бо вона містить елементи порядку 3, а в групі FAP елементів третього порядку немає.

Наприкінці параграфа будується приклад вільної абелевої підгрупи рангу 2 в групі FAP скінчено автоматних підстановок над двоелементним алфавітом, твірні якої задаються автоматами.

Визначені цими автоматами автоматні підстановки задаються такими таблицями відповідно:

.

Висновки

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

Показано, що вільних піднапівгруп «більшість» (у розумінні категорії Бера) серед скінченно породжених піднапівгруп цієї напівгрупи. Також розвинуто техніку обчислень у вінцевих добутках напівгруп перетворень та груп підстановок, завдяки чому побудовано континуальну родину вільних піднапівгруп напівгрупи автоматних перетворень, вказано серію вільних підгруп цієї напівгрупи. Користуючись мовами скінченних автоматів та вінцевих добутків напівгруп за нескінченними послідовностями напівгруп перетворень, побудовано скінченно автоматні над двоелементним алфавітом групи, ізоморфні вільним добуткам скінченної кількості циклічних груп другого порядку, а також вільній групі рангу 2.

Застосовані в дисертаційній роботі методи і побудовані приклади можна буде використовувати для подальшого дослідження напівгруп автоматних перетворень і груп автоматних підстановок, а також вільних груп та напівгруп.

Автор висловлює щиру подяку своєму науковому керівнику професору Сущанському Віталію Івановичу за постійну увагу і підтримку в роботі.

Роботи автоpа за темою дисеpтації

Олiйник А.C. Вiльнi напiвгрупи скiнченно автоматних перетворень // Всеукраїнська наукова конференцiя «Розробка та застосування математичних методiв в науково-технiчних дослiдженнях». - Львiв. - 1995. - Тези доповідей. с. 39.

Олiйник А.C. Зображення вільних напівгруп квазідіагональними автоматними підстановками // П'ята Міжнаpодна конфеpенція імені академіка М. Кpавчука. - Київ. - 1996. - Тези доповідей. с. 307.

Олійник А. Відношення Гріна в напівгрупах автоматних перетворень // Вісник Київського ун-ту. Серія фіз.-мат. - 1997. - вип. 4. - с. 9197.

Олийнык А.С. О свободных полугруппах автоматных преобразований // Матем. заметки. - 1998. - 63. - с. 248259.

Олійник А.С. Вільні групи автоматних підстановок // Доп. НАН України. - 1998. - №7. - с. 4044.

Olijnyk A. Free products of and finite automata // Abstr. Int. Conf. Group and Group Rings VI. - Wisla. - 1998. - p. 28.

Olijnyk A. Free products of as groups of finitely automatic permutations // Вопросы алгебры. - 1999. - вып. 14. - с. 158165.

Размещено на Allbest.ru