Automata Theory

The smallest known length of an ordered system of generators of a symmetric group

S. A. Kalinchuk^a, Yu. L. Sagalovich<sup>b

a</sup> NetCracker, Moscow
^b A. A. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences

Abstract: We consider a recursive algorithm for constructing an ordered system of generators of a symmetric group of degree $n$. We show that the number of transpositions that form this system is $O(n\log_2^2n)$. This is only by a factor of $\log_2n$ greater in order than the lower bound on the number of transpositions in such a system.

UDC: 621.391.15+512

Received: 16.12.2008
Revised: 22.06.2009

 English version: Problems of Information Transmission, 2009, 45:3, 242–257

Bibliographic databases:

• 
• 
• 
• 
•