Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n
Loading...
Date
2021
Authors
Ольшевська, Віта
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
У статті запропоновано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп Syl2(S2n) симетричних груп S2n, n є N. Для побудови цього алгоритму використано ізоморфізм між групою Syl2(S2n) та групою бінарних кореневих дерев з мітками. Також обчислено складність запропонованого алгоритму та його середню кількість кроків для силовської 2-підгрупи симетричної групи S2n. Обраховано кількість підстановок із Syl2(S2n), що мають максимальну кількість рухомих точок.
The Symmetric permutation group S2n is a classical algebraic object that is also used in Computer science, Coding theory, Statistics, etc. In particular, the coding theory considers codes defined on the symmetric group Sn or its subgroups. The research of permutation codes has been started from 1970s. These codes can be obtained with using different distances: Hamming, Ulam, Cailey, Levenshtein. The finding distance on permutations depends on their number of fixed or unfixed points. Therefore, it is natural to count the number of unfixed points in a certain group of permutations. In this paper, we consider the number of unfixed points of permutations that are elements of the Sylow 2-subgroup Syl2(S2n) of symmetric groups S2n. Leo Kaluzhnin used tables to represent the elements of these groups [8]. Volodymyr Nekrashevych represented permutations by their portraits [9]. We use algorithms that describe the connection between the permutation group Syl2(S2n) and the group of labeled, binary rooted trees [10]. An algorithm for finding the number of unfixed points for permutations of the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n is proposed in the article. An isomorphism between the group Syl2(S2n) and a group of labeled, binary root trees was used to construct this algorithm. It is proved, that the algorithm of searching the number of unfixed point for permutations of the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n has complexity O(2n). In addition, the average number of steps of the algorithm for the Sylow 2-subgroup of the symmetric group S2n is found. The result for small n (n = 2, 3, 4) was verified with a program, that is written in the language of the computer algebra Sage. At the end of the article we find the number of permutations from Syl2(S2n) that have a maximum number of unfixed points. The number of such permutations in the symmetric group S2n is well known. Obviously that this number is smaller for the Sylow 2-subgroup of the symmetric group Syl2(S2n). In this case, we calculate the maximum number of unfixed points using a recursive formula.
The Symmetric permutation group S2n is a classical algebraic object that is also used in Computer science, Coding theory, Statistics, etc. In particular, the coding theory considers codes defined on the symmetric group Sn or its subgroups. The research of permutation codes has been started from 1970s. These codes can be obtained with using different distances: Hamming, Ulam, Cailey, Levenshtein. The finding distance on permutations depends on their number of fixed or unfixed points. Therefore, it is natural to count the number of unfixed points in a certain group of permutations. In this paper, we consider the number of unfixed points of permutations that are elements of the Sylow 2-subgroup Syl2(S2n) of symmetric groups S2n. Leo Kaluzhnin used tables to represent the elements of these groups [8]. Volodymyr Nekrashevych represented permutations by their portraits [9]. We use algorithms that describe the connection between the permutation group Syl2(S2n) and the group of labeled, binary rooted trees [10]. An algorithm for finding the number of unfixed points for permutations of the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n is proposed in the article. An isomorphism between the group Syl2(S2n) and a group of labeled, binary root trees was used to construct this algorithm. It is proved, that the algorithm of searching the number of unfixed point for permutations of the Sylow 2-subgroup Syl2(S2n) of the symmetric group S2n has complexity O(2n). In addition, the average number of steps of the algorithm for the Sylow 2-subgroup of the symmetric group S2n is found. The result for small n (n = 2, 3, 4) was verified with a program, that is written in the language of the computer algebra Sage. At the end of the article we find the number of permutations from Syl2(S2n) that have a maximum number of unfixed points. The number of such permutations in the symmetric group S2n is well known. Obviously that this number is smaller for the Sylow 2-subgroup of the symmetric group Syl2(S2n). In this case, we calculate the maximum number of unfixed points using a recursive formula.
Description
Keywords
рухомі точки, симетричні групи, силовські підгрупи, алгоритм, складність алгоритму, стаття, unfixed points, symmetric groups, sylow subgroups, algorithm, complexity
Citation
Ольшевська В. А. Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n / Ольшевська В. А. // Могилянський математичний журнал. - 2021. - Т. 4. - С. 34-40. - https://doi.org/10.18523/2617-70804202134-40