Article collection "Mathematical Problems of Cybernetics" №8, Moscow, 1999

Authors:Glukhov M.M., Zubov A.Y.

About lengths of the symmetric and alternating permutation groups via the systems of various generators

Abstract:

In the article a review of the results on the systems of generators of symmetric and alternating permutation groups of finite degrees is presented. In the first part of the review methods allowing to answer the question, whether the given multitude of permutation generates symmetric (Sn) or alternating (An) group, are shown. Well-known as well as specific systems of generators of groups Sn and An, consisting of permutations with the same cycle structure, systems of generators, used in such applications as theory of automata, cryptography etc. are pointed out. The second part of the review is dedicated to estimations of lengths of groups Sn and An, via the various systems of generators. The length of the group coincides with the diameter of the Cayley graph of the group and represents the maximum of the lengths of the shortest representations of group elements via the given generators. For some systems of generators of substitutions groups algorithms allowing to find representations of group elements via the form of products of the given generators (in particular, the shortest) are shown. Along with the published results the authors present particular results known to them from different scientific reports.

Keywords:

system of generations of the group; symmetric and alternating permutation groups; length of the group element and length of the group via the system of generators; diameter of the Cayley graph of the group

Publication language:russian, pages:28 (p. 5-32)

Research direction:

Mathematical problems and theory of numerical methods