Olshevska V. Algorithms and Codes over Sylow 2-Subgroups of Symmetric Groups S2n

Olshevska V. A. Algorithms and Codes over Sylow 2-Subgroups of Symmetric Groups S2n . – Qualifying scientific work on the rights of the manuscript. 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. Sylow p-subgroups of the symmetric group have been studied by Prof. L.Kaluzhnin and described 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. 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 S_(p^n ) are described by A.Slupik and V.Sushchansky. B.Pawlik used the polynomial representation of elements in the group 〖Syl〗_2 (S_(2^n ) ). He described the action of 〖Syl〗_2 (S_(2^n ) ) on a set of minimal generated sets of this group. The lower central series of Sylow subgroups of symmetric groups S_n was studied by A.Weir. Since tree-like data structures are convenient and efficient for calculations, this leads to the developing algorithms for computations with Sylow 2-subgroups of S_(p^n ) 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 S_(2^n ). 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 〖Syl〗_2 (S_(2^n ) ). A natural extension of this work is a studying of permutation codes over Sylow 2-subgroups of S_(2^n ). The permutation codes and their properties have been widely researched in various domains since the 1970s. I.Blake reviewed and generalized known results about permutation arrays at that time. J.Denes demonstrated the application of permutation coding in voice operations and parallel computing. P.Cameron provided an overview of results related to groups of permutations and permutation codes. A permutation code is defined as the set of elements from the group S_n with the minimum distance between every pair of them. Different subgroups of the symmetric group can be used, as well as different metrics (Hamming, Ulam, Levensteins etc.) Permutation codes are used as error-correction codes in communication channels with limited bandwidth. R.Bailey presents efficient decoding algorithms when permutation codes are subsets from S_n in his work. In the dissertation the properties of permutation codes defined on the Sylow 2-subgroup 〖Syl〗_2 (S_(2^n ) ) of the group S_(2^n ) with Hamming distance d_H over them are considered. Metric properties of permutation codes are studied. The properties of the Hamming distance defined on the group 〖Syl〗_2 (S_(2^n ) ) are also described. An algorithm for finding the Hamming distance over group elements is constructed. Keywords: permutation group, Sylow 2-subgroups of symmetric groups, algorithms, time complexity, tree, Hamming distance, permutation codes.