ECONOMICAL GENERATING SETS FOR THE SYMMETRIC AND ALTERNATING GROUPS CONSISTING OF CYCLES OF A FIXED LENGTH

The symmetric group S_n and the alternating group A_n are groups of permutations on the set {0, 1, 2, …, n - 1} whose elements can be represented as products of disjoint cycles (the representation is unique up to the order of the cycles). In this paper, we show that whenever n ≥ k ≥ 2, the collection of all k-cycles generates S_n if k is even, and generates A_n if k is odd. Furthermore, we algorithmically construct generating sets for these groups of smallest possible size consisting exclusively of k-cycles, thereby strengthening results in [O. Ben-Shimol, The minimal number of cyclic generators of the symmetric and alternating groups, Commun. Algebra35(10) (2007) 3034–3037]. In so doing, our results find importance in the context of theoretical computer science, where efficient generating sets play an important role.