Permutation codes over Sylow 2-subgroups Syl2(S2n) of symmetric groups S2n

Loading...
Thumbnail Image
Date
2021
Authors
Olshevska, Vita
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The permutation code (or the code) is well known object of research starting from 1970s. The code and its properties is used in different algorithmic domains such as error-correction, computer search, etc. It can be de ned as follows: the set of permutations with the minimum distance between every pair of them. The considered distance can be di erent. In general, there are studied codes with Hamming, Ulam, Levensteins, etc. distances. In the paper we considered permutations codes over 2-Sylow subgroups of symmetric groups with Hamming distance over them. For this approach representation of permutations by rooted labeled binary trees is used. This representation was introduced in the previous author's paper. We also study the property of the Hamming distance de ned on permutations from Sylow 2-subgroup Syl2(S2n) of symmetric group S2n and describe an algorithm for nding the Hamming distance over elements from Sylow 2-subgroup of the symmetric group with complexity O(2n). The metric properties of the codes that are de ned on permutations from Sylow 2-subgroup Syl2(S2n) of symmetric group S2n are studied. The capacity and number of codes for the maximum and the minimum nontrivial distance over codes are characterized.
Починаючи із 1970-х років коди, побудовані на підстановках, та їх властивості широко досліджуються у різних сферах. Під кодом на групі підстановок розуміють множину елементів із групи Sn, де довільна пара із множини має відстань не меншу від заданої. При цьому можуть використовувати як різні підгрупи симетричної групи, так і різні метрики, наприклад, Хеммінга, Улама, Левенштейна тощо. У статті розглядаються коди підстановок із силовської 2-підгрупи Syl2(S2n) симетричної групи S2n з відстанню Хеммінга йи над ними. Для їх дослідження використано зв’язок групи Syl2(S2n) із групою бінарних кореневих те-рівневж дерев з мітками LT2,n. Також описано властивості відстані Хеммінга на підстановках із силовської 2-підгрупи Syl2(S2n) симетричної групи S2n та побудовано алгоритм пошуку відстані Хеммінга для підстановок групи, що має складність O(2n). Окрім того, досліджено метричні властивості кодів на підстановках із Syl2(S2n) та знайдено розміри і кількість кодів для максимальної та мінімальної ненульової відстані Хеммінга.
Description
Keywords
permutation codes, Sylow 2-subgroup, symmetric group, Hamming distance, article, коди на підстановках, силовська 2-підгрупа, симетрична група, відстань Хеммінга
Citation
Olshevska V. A., Permutation codes over Sylow 2-subgroups Syl2(S2n) of symmetric groups S2n / V. A. Olshevska // Researches in Mathematics. - 2021. - Vol. 29, No 2. - P. 28-43. - https://doi.org/10.15421/242107