Алгоритми і коди над силовськими 2-підгрупами симетричних груп S2n : дисертація на здобуття наукового ступеня доктора філософії
Loading...
Date
2023
Authors
Ольшевська, Віта
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Дисертація на здобуття наукового ступеня доктора філософії в галузі знань 11 "Математика та статистика" за спеціальністю 113 "Прикладна математика" — Національний університет "Києво-Могилянська академія", Київ, 2023. Дисертаційна робота присвячена побудові і аналізу алгоритмів над силовськими 2-підгрупами симетричних груп та дослідженню властивостей кодів на цих групах. Силовські p-підгрупи є класичними об’єктами в теорії груп, опис таких підгруп допомагає зрозуміти структуру самої групи. Зокрема, словські р-підгрупи симетричної групи досліджувалися професором Л. Калужніним та описані в його працях за допомогою вінцевих добутків циклічних груп. Він запропонував зображати елементи таких груп у вигляді спеціальних таблиць, а саме - впорядкованих наборів многочленів певного вигляду. Ю. Дмитрук у своїй праці описав алгебраїчні структури силовських 2-підгруп симетричних груп. Основою для створення означення та отриманих головних результатів послугували саме статті Л. Калужніна. Елементи силовських підгруп симетричних груп можна розглядати як портери автоморфізмів кореневих дерев, які наведені в роботі В. Некрашевича. Мінімальна система твірних та графи Келлі на силовських р-підгрупах симетричних груп S2n описані А. Слупік та В. Сущанським. Нехай маємо ціле та додатнє число п > 1. Силовську 2-підгрупу симетричної групи S2n позначимо S2n as Syl2(S2n). Група Syl2(S2n) ізоморфна кінцевому добутуку р-циклічних груп, що мають порядок 2, а саме: Sylr2 (S2n ) = Z 2 I . . . I Z2 n разів. Б. Павлик використав поліноміальне представлення елементів групи Syl2(S2n). Він описав дії над Syl2(S2n) на множині мінімальних систем твірних цієї групи. Нижній центральний ряд силовських підгруп симетричних груп Sn було досліджено А. Віером. Оскільки такі структури досить зручні та ефективні в обчисленнях, природним продовженням є дослідження алгоритмічних властивостей та створення алгоритмів для обрахунків у силовських 2-підгрупах симетричних груп, елементи яких представлені саме деревами. Враховуючи характеристику порядку групи, особливої уваги заслуговує випадок, коли р = 2. У дисертаційній роботі дослідження ґрунтується на властивостях бінарних кореневих p-рівневих дерев з мітками. У тому числі розглянуті алгоритми основних групових операцій для таких структур, алгоритми зв’язку між деревами та підстановками з силовських 2-підгруп симетричних груп. Окрім того, для кожного алгоритму доведено коректність та досліджено часову складність.
Використовуючи зв’язок підстановок з бінарними кореневими деревами з мітками, в дисертаційній роботі побудовано алгоритм пошуку кількості рухомих точок підстановок та відстані Хеммінга між елементами групи Syl2(S2n). Логічним продовженням роботи стало дослідження кодів над підстановками із силовських 2-підгруп симетричних груп. Починаючи із 1970-х років коди, побудовані на підстановках, та їх властивості широко досліджуються у різних сферах. Так І. Блейк у своїй роботі коротко розглянув та узагальнив відомі того часу результати про перестановочні масиви. Метою статті Дж. Денеса було показати, як використовувати перестановочне кодування для голосових операцій та паралельних обчислень. П. Камероном було отримано низку результатів про групи перестановок і перестановочні коди та зроблено огляд про відомі результати. Описано декілька відкритих проблем. Під кодом на групі підстановок розуміють множину елементів із групи Sn, де довільна пара із множини має відстань не меншу від заданої. При цьому можуть використовувати як різні підгрупи симетричної групи, так і різні метрики, наприклад, Хеммінга, Улама, Левенштейна тощо. Перестановочні коди використовуються як коди корекції помилок в каналах комунікацій з малою пропускною здатністю. Одним з напрямків є дослідження кодів на алгебраїчних структурах. Р. Бейлі у своїй роботі наводить ефективні алгоритми декодування, коли перестановочні коди є підмножинами з Sn. У дисертації розглядаються властивості кодів, які визначені на підстановках із силовської 2-підгрупи Syl2(S2n). симетричної групи Syl2 з відстанню Хеммінга dH над ними. Для їх дослідження також використано зв’язок групи Syl2(S2n) із групою бінарних кореневих n-рівневих дерев з мітками. Досліджено метричні властивості кодів на підстановках. Також описано властивості відстані Хеммінга на підстановках із силовської 2-підгрупи Syl2(S2n) симетричної групи S2n та побудовано алгоритм пошуку відстані Хеммінга для підстановок групи, що має складність 0 (2 n). Окрім того, досліджено метричні властивості кодів на підстановках із Syl2(S2n) та знайдено розміри і кількість кодів для максимальної та мінімальної ненульової відстані Хеммінга. Таким чином, у дисертаційній роботі містяться наступні нові наукові результати: 1. Запропоновано алгоритми перетворення підстановки із силовської 2-підгрупи симетричної групи у кореневе бінарне n-рівневе дерево з мітками та обернений перехід від дерева з LT2,n до підстановки із Syl2(S2n). Доведено їхню коректність і обчислено часову складність. 2. Запропоновано алгоритм множення підстановок силовської 2-підгрупи симетричної групи, що використовує зображення груп бінарними деревами з мітками, та обчислено його часову складність. Описано алгоритм знаходження оберненого елемента. Доведено його коректність та обчислено часову складність. 3. Описано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп симетричних груп з часовою складністю 0 (2n). Пораховано, що в середньому алгоритм виконує т кроків для групи Syl2(S2n). 4. Запропоновано формулу, за якою можна визначити кількість підстановок із Syl2(S2n), що мають задану, зокрема максимальну, кількість рухомих точок. 5. Наведено алгоритм пошуку відстані Хеммінга для підстановок із силовських 2-підгруп симетричних груп з часовою складністю O(2n). Оцінено, що в середньому алгоритм виконує n кроків для групи Syl2(S2n). 6. Запропоновано рекурсивну формулу для обчислення кількості підстановочних кодів CH over Syl2(S2n) з максимальною відстанню Хеммінга та обчислено кількість таких кодів. Практичне значення отриманих результатів. Результати дисертації мають теоретичний характер. Вони можуть використовуватися в теорії кодування, теорії груп підстановок. Дисертація може бути використана для читання спеціалізованих курсів з теорії алгоритмів та теорії кодування для студентів математичних спеціальностей.
Description
The thesis for obtaining Ph.D. degree in the field 11 "Mathematics and statistics" and the specialty 113 "Applied mathematics"— National University of Kyiv-Mohyla Academy, Kyiv, 2023. The dissertation is dedicated to the construction and analysis of algorithms over Sylow 2-subgroups of symmetric groups and the investigation of properties of codes on these groups. Sylow p-subgroups are classical objects in group theory. Describing such subgroups helps to understand the structure of the group itself. In particular, Sylow p-subgroups of the symmetric group have been studied by Professor L. Kaluzhnin and described in his works using wreath products of cyclic groups. He proposed representing the elements of such groups in the form of special tables, namely, ordered sets of polynomials of a specific form. In his work, Y. Dmitruk described the algebraic structures of the Sylow 2-subgroups of symmetric groups. The basis for creating the definition and obtaining the main results were indeed the articles of L. Kaluzhnin. The elements of the Sylow subgroups of symmetric groups can be represented as portraits of automorphisms of rooted trees, which V. Nekrashevych introduced in his work. The minimal generating system and Cayley graphs on Sylow p-subgroups of symmetric groups Spn are described by A. Slupik and V. Sushchansky. Let n > 1 be an integer positive number. We will denote the Sylow 2-subgroup of the symmetric group S2n as Syl2(S2n). The group Syl2(S2n) is isomorphic to the n times iterated wreath product of cyclic groups of order 2, i.e. Sylr2 (S2n) = Z 2 I . . . I Z2.n разів
B. Pawlik used the polynomial representation of elements in the group Syl2(S2n). He described the action of Syl2(S2n) on a set of minimal generated sets of this group. The lower central series of Sylow subgroups of symmetric groups Sn was studied by A. Weir. Since tree-like data structures are convenient and efficient for calculations, this leads to the natural direction of developing algorithms for computations with Sylow 2-subgroups
of symmetric groups using tree-representation. The basic case p = 2 deserves special attention due to the binary nature of the data involved. The dissertation work is based on the properties of binary rooted labeled n-level trees. This includes the algorithms for basic group operations on such structures, algorithms for the connection between trees and permutations from Sylow 2-subgroups of symmetric groups. In addition, the correctness of each algorithm has been proven, and their time complexity has been investigated. Using the connection between permutations and binary rooted labeled trees, the dissertation work presents an algorithm for finding the number of unfixed points of permutations and the Hamming distance between elements of the group Syl2(S2n). A natural extension of this work is a studying of permutation codes over Sylow 2-subgroups of symmetric groups.
The permutation codes and their properties have been widely researched in variousdomains since the 1970s. I.Blake briefly reviewed and generalized known results about permutation arrays at that time. The goal of J.Denes’s article was to demonstrate the application of permutation coding in voice operations and parallel computing. P. Cameron in his article provided an overview of results related to sets and groups of permutations and their connection with coding theory. Several open problems were also described in the article. A permutation code can be defined as follows: the set of elements from the group Sn with the minimum distance between every pair of them. Different subgroups of the symmetric group can be used, as well as different metrics. In general, there are studied codes with Hamming, Ulam, Levensteins, etc. distances. Permutation codes are used as error-correction codes in communication channels with limited bandwidth. The studying of codes on algebraic structures is one of the possible directions. R.Bailey presents efficient decoding algorithms when permutation codes are subsets from Sn in his work. In the dissertation the properties of permutation codes defined on the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n with Hamming distance dH over them are considered. For this approach representation of permutations from Syl2(S2n) by rooted labeled binary trees is used. Metric properties of permutation codes are studied. The properties of the Hamming distance defined on permutations from the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n are also described. An algorithm for
finding the Hamming distance over elements from Syl2(S2n) with complexity O(2n) is constructed. Additionally, metric properties of the codes that are defined on permutations from Sylow 2-subgroups Syl2(S2n) of symmetric group S2n are studied. The capacity and number of codes for the maximum and the minimum nontrivial Hamming distance over codes are characterized.
Thus, the following new scientific results are included in the thesis. 1. The algorithm of transformation a permutation from the Sylow 2-subgroup of the
symmetric group into a labeled rooted n-level binary tree and the reverse algorithm of transformation a tree from LT2n into a permutation from Syl2(S2n) are proposed. Their correctness are proved and time complexities are calculated. 2. The algorithm of multiplication of permutations from the Sylow 2-subgroup of the symmetric group is proposed. The time complexity is calculated. The representation of groups by labeled binary trees is using for this. The algorithm of finding the inverse element is described. Its correctness is proved and the time complexity is calculated. 3. The algorithm of counting the number of unfixed points of permutations from the Sylow 2-subgroups of symmetric groups is described with a time complexity O(2n). It has also been calculated that this algorithm performs n steps for the group Syl2(S2n) in average. 4. A formula has been proposed by which we can determine the number of permutations in Syl2(S2n) that have a specified, in particular maximum, number of unfixed points. 5. The algorithm for finding the Hamming distance over permutations from the Sylow 2-subgroups of symmetric groups with a time complexity O(2n) is provided. It has
been proved that this algorithm performs n steps for the group Syl2(S2n) in average. 6. A recursive formula has been proposed for calculating the number of permutation codes CH over Syl2(S2n) with the maximum Hamming distance. The number of such codes has been computed. The practical significance o f the results. The results of this dissertation are mainly theoretical. They can be applied in coding theory and the theory of permutation groups. The dissertation can be used for lecturing special courses of algorithm theory and coding theory for students majoring in mathematics.
Keywords
група підстановок, силовські 2-підгрупи симетричних груп, алгоритми, часова складність, дерево, відстань Хеммінга, коди на групах підстановок, дисертація, permutation group, Sylow 2-subgroups of symmetric groups, algorithms, time complexity, tree, Hamming distance, permutation codes
Citation
Ольшевська В. А. Алгоритми і коди над силовськими 2-підгрупами симетричних груп S2n : дисертація на здобуття наукового ступеня доктора філософії / Ольшевська Віта Анатоліївна ; наук. кер.: Олійник Богдана Віталіївна ; Міністерство освіти і науки України, Національний університет "Києво-Могилянська академія". - Київ : [б. в.], 2023. - 138 с.