arXiv:1602.03957v3 [] 20 Mar 2016

COMPUTATIONAL ENUMERATION OF INDEPENDENT
GENERATING SETS OF FINITE SYMMETRIC GROUPS
ATTILA EGRI-NAGY1 AND VOLKER GEBHARDT2

Abstract. We developed computer algebra tools for enumerating conjugacy
classes of independent subsets and generating sets of symmetric groups up to
n = 7, and carried out an initial analysis of the obtained results.

1. Introduction
Generating sets are an efficient way of defining algebraic structures, thus it is
natural to require them to be as concise as possible. This minimality condition can
be formulated as independence, that none of the generators can be constructed by
the remaining elements of the generating set.
Symmetric groups Sn , the group of all permutations of degree n, are central
objects in mathematics since all groups can be represented as a subgroup of some
permutation group. Asymptotically, any pair (x, y), x, y ∈ Sn will generate the
alternating group or the symmetric group, with probability 43 [4]. Except n = 4,
we can always construct a permutation that will generate Sn together with a given
permutation [8, 10]. In Sn , the maximal size of an independent set is n − 1 and in
that case it is a generating set for Sn [11]. These maximal independent generating
sets can be explicitly constructed [2].
2. Basic definitions and notation
The set {1, 2, . . . , n} is denoted by n. The power set of a set A is denoted by
P(A).
A generating set of a group G is a subset A ⊆ G such that every element of G
can be expressed as a combination of elements of A, denoted by hAi = G. Here
we do not include the inverses of the generators tacitly, so we generate the group
as a semigroup. Alternatively, we say that hAi, the subgroup generated by A, is
the intersection of all subgroups of G containing A. We consider generating sets
essentially the same if they are conjugate.
Definition 2.1. Let A and B subsets of G. Then A is conjugate to B in G, denoted
by A ∼ B iff there exists g ∈ G such that A = g −1 Bg.
In Sn conjugacy corresponds to simultaneous relabelling of the points of the permutations.
Similar to linear independence in vector spaces, we can define independence for
sets of permutations.
Definition 2.2 (Independent set of permutations). Let A be a set of permutations.
It is independent if a ∈
/ hA \ {a}i for all a ∈ A.
1

2

A. EGRI-NAGY, V. GEBHARDT

A set of permutations may or may not be independent, depending on the actual
algebraic structure it is the subset of. The set {()} containing the identity only is
not independent in Sn considered as a group, since by the group axioms the empty
set generates the trivial group. However, in Sn as a semigroup, it is independent.
In this paper we consider independent sets in Sn as a semigroup.
Removing elements from an independent set keeps the set independent.
Fact 2.3. Any nonempty subset of an independent set is an independent set.
On the contrary, adding elements and keeping the set independent is difficult, even
when we use information from the underlying permutation representation. Let A be
a independent set of permutations acting on n − 1, and b a permutation such that
b∈
/ Stabn . Then A ∪ {b} is not guaranteed to be independent. For example, adding
(14) to {(12), (23)} yields an independent set, but adding (14) to {(12), (123)} does
not since {(123), (14)} already generates S4 thus (12) becomes redundant.
Definition 2.4. Let I(G) denote the set of independent subsets of a group G.
An independent set A ⊆ G is maximal if there is no B ∈ I(G) such that A ⊂ B.
The set of all maximal independent sets of G is denoted by Imax (G). The set of
independent generating sets of G is denoted by Ihi (G).
By definition, P(G) ⊇ I(G) ⊇ Imax (G) ⊇ Ihi (G), since an independent generating set of G is necessarily maximal. Here we study Ihi (Sn ), the independent
generating sets of the symmetric group.
3. The folklore
There are a few standard generating sets for the symmetric group. For a concise
overview and wider context see [3].
Proposition 3.1 (All transpositions). The set of all transpositions (ij), where
i 6= j and i, j ∈ n, generate Sn .
Proof. A general element of Sn is a product of disjoint cycles, therefore it is enough
to show that an arbitrary cycle can be built using transpositions. Let (i1 i2 . . . ik )
be a general cycle, then
(i1 i2 . . . ik ) = (ik−1 ik )(ik−2 ik−1 ) · · · (i2 i3 )(i1 i2 ).

There are
ating set.


n
2

=

n(n−1)
2

transpositions in Sn , hence it is not an independent gener-

Proposition 3.2 (Base point transpositions). Let i be a chosen base point and
the set of transpositions of the form (ik) with k ∈ n, k 6= i called the base point
transpositions. This set of n − 1 transpositions generates Sn .
Proof. Without loss of generality we can fix the base point to be 1. We can express
a general transposition by base point transpositions.
(1j)(1i)(1j) = (ij),
therefore by Proposition 3.1 we can generate Sn .



Proposition 3.3 (Transposition chain). The generating set {(12), (2, 3), . . . , (n −
1, n)}, the chain of transpositions generates Sn .

INDEPENDENT GENERATING SETS OF SYMMETRIC GROUPS

3

n
1 2
3
4
5
6
7
|I(Sn )|
1 3 16 413 25346 6825268 750102585
|I(Sn )/ ∼|
1 3
6
31
258
10294
155305
|Ihi (Sn )/ ∼| 1 1
2
14
178
8621
126515
Table 1. The number of independent sets, their conjugacy classes,
and also independent generating sets up to conjugation in Sn as a
semigroup.

Proof. By using the transpositions in the chain we can generate base point transpositions (Proposition 3.2): (1i) = (12)(23) · · · (i−2 i−1)(i−1 i)(i−2 i−1) · · · (12). 
Proposition 3.4 (Transposition and a full cycle). A full cycle on n points (i1 i2 . . . in )
and a transposition of consecutive points (ij ij+1 ) in the cycle generates Sn .
Proof. The transposition can be conjugated by the cycle to produce a transposition
chain.

These generator sets are very ‘regular’ in a sense and thus easier to study, but by
no means all the types of generating sets. Therefore a more systematic enumeration
is needed.
4. Algorithmic Enumeration
For n ≤ 3 we can easily find all independent generating sets of Sn by pen and
paper calculations. For the trivial group S1 , the only semigroup generating set is the
singleton set containing the identity (while the only independent group generating
set is the empty set). For S2 ∼
= Z2 , the only independent generating set is {(12)}.
For S3 , we have Ihi (S3 )/ ∼ = {{(12), (23)}, {(12), (123)}}, the familiar transposition
chain, and the transposition and a full cycle generating sets.
We can use brute force enumeration for S4 and S5 to get the independent sets
by simply enumerating all subsets of size n − 1 and check them for for independence. The size of the search space is 12950 and ≈199.8 million. For S6 the brute
force algorithm would need to check ≈191 trillion cases, therefore we need a better
approach.
A customized depth-first graph search algorithm gives us all the independent sets
in the low degree cases. The nodes are sets of permutations and edges correspond
to adding a new element to a set. In other words, the search algorithm traverses
the Hasse-diagram of the subset lattice. The search tree can be cut at dependent
sets, since those can never be made independent by adding more elements.
Elements of a conjugacy class of subsets can be calculated easily if we have
a representative element, therefore it is enough and more efficient to collect only
representative subsets. For choosing a representative element of a conjugacy class,
we take its minimal element in lexicographic order. As further optimization, a
pre-calculated lookup table is used to decide which elements of Sn may produce
the representative for a given subset, so we do not need to conjugate by all the n!
permutations in Sn .
Alternatively, the method of canonical construction paths [9] can also be used
to speed up the search. We say that the canonical way of extending a set is to add
a new maximal element (in lexicographic order) and reject any other extensions.

4

A. EGRI-NAGY, V. GEBHARDT

n
1 2 3 4
5
6
7
#dead ends 1 1 1 4 19 278 17591
Table 2. Number of dead end independent sets in symmetric groups.

This method does not require us to check a newly constructed subset against the
database of already visited subsets. However, in some cases it is faster to decide
independence for a subset than checking the canonicity of its construction.
5. Preliminary Analysis of Results
By analyzing the results of the enumeration we can make the following observations:
(1) There are dead ends, maximal (by inclusion) independent sets in Sn , so all
possible extensions lead to dependent sets, but they do not generate Sn .
(2) The proportion of two-element independent generating sets is decreasing as
n increases.
(3) With the comprehensive enumeration we can define the minimum and maximum diameters for Sn .
(4) Most independent generating sets have no symmetries.
Of course, these observations should be understood with the condition ‘in the low
degree cases’.
5.1. Dead Ends. All independent generating sets of Sn are maximal independent
sets, since simply there exists no other permutation not generated already. However,
the converse is not true. Maximality of an independent set does not guarantee
that it will generate the symmetric group. A trivial example of such a set is the
singleton {()} generating the trivial group. Since any added finite permutation
would generate the identity, there is no way to make this independent set bigger.
Non-trivial examples were discovered by the analysis of the search-tree.
Fact 5.1. There exists n ∈ N such that Imax (Sn ) ) Ihi (Sn ), i.e. not all maximal
independent sets of permutations generate the symmetric group.
Proof. The smallest value is n = 4:
h(1, 3), (1, 2, 3, 4)i = D4 ,
h(1, 2)(3, 4), (1, 2, 3, 4)i = D4 ,
h(1, 2)(3, 4), (1, 3)(2, 4)i = Z2 × Z2 .
For example, in the first two cases, any permutation p ∈ S4 \ D4 generates S4 with
the 4-cycle (1, 2, 3, 4), forcing the other generator to be redundant.

The number of dead ends is growing monotonically, see Table 2.
5.2. Size distribution of independent sets. Asymptotically most pairs of permutations generate the symmetric group [4], and this may suggest that most independent generating sets would be of size 2. However results show, at least at
beginning, that the proportion of of the two-element generating sets is decreasing
from n = 3, see Table 3. For n = 8 we can enumerate the distinct 2-element generating sets, and it is also a relatively small number. The above percentages are

INDEPENDENT GENERATING SETS OF SYMMETRIC GROUPS

5

2
3
4
5
6
S3
2 (100%)
S4
5 (35.71%)
9
S5
31 (17.41%)
138
9
S6
163 (1.89%)
6355
2059
44
S7 1576 (1.01%) 67078 54398 3415 48
S8
21912
Table 3. Size distribution of independent generating sets of Sn .
Percentages indicate the proportion of 2-element generating sets.

n
1 2 3 4
5
6
minS (diamS (Sn )) 0 1 2 4
5
7
maxS (diamS (Sn )) 0 1 3 7 14 18
Table 4. Minimal and maximal diameter values of
generating sets of symmetric groups.

7
8
34
independent

1

Z2 Z2 × Z2 Z3 D4 D6
S3 S4 S5 S6
1
Ihi (S3 )/ ∼
1
1
Ihi (S4 )/ ∼
8
5
1
Ihi (S5 )/ ∼
150
25
1
1
1
Ihi (S6 )/ ∼
7931
645
11
6
4
20
2
2
Ihi (S7 )/ ∼ 121426 4846
78
7
7
7 134
8
1
1
Table 5. Symmetry groups of independent generating sets of symmetric groups. It is a special property of a set of group elements
to have nontrivial symmetries.
Ihi (S2 )/ ∼

for conjugacy class representatives, but the size distribution of the total number of
independent generating sets have similar ratios.
5.3. Speed of Generating Sets. We can for instance measure the ‘speed’ of
generating sets, i.e. how quickly they can build the elements of the group. A
generating S for a group G is slow if diamS (G) is maximal across all generating
set. Slow implies independent, since adding a generator only shorten words.
For n = 2 the only generating set is {(12)}, therefore it is slow. For n = 3,
diam{(12),(23)} (S3 ) = 3, while diam{(123),(23)} (S3 ) = 2, so the transposition chain is
the slow one. For n = 4 and n = 5 we have unique slow generating sets:{(123), (34)}
and {(1243), (2, 3)(4, 5)}. For n = 6, {(23)(456), (12)(34)(56)} and {(56), (123456)},
so the full cycle and the transposition generating set is slower than the transposition
chain.
5.4. Symmetries of independent generating sets. Most independent generating sets have no symmetries, i.e. their normalizers are trivial (Table 5).

6

A. EGRI-NAGY, V. GEBHARDT

6. Combinatorial Approach: Incremental generating sets
For chasing a recursive counting formula of independent generating sets of Sn ,
we need a systematic method to build these objects. This can be achieved for a
special class of generating sets. We look at how to build a generating set for Sn if
we have one for Sn−1 .
Lemma 6.1. Let A be a generating set for Sn−1 naturally acting on n − 1, then
hA ∪ {g}i = Sn for any g ∈ Sn naturally acting on n such that g ∈
/ Stabn .
Proof. Let g be a transposition of the form (in), i ∈ n − 1. Then by taking transpositions (ik), k ∈ n − 1 \ {i} from Sn−1 we have a basepoint generating set for
Sn .
For an arbitrary cycle, let g = (i1 . . . ik n). Then g(ik . . . i1 ) = (ik n), i.e. we multiply
g by an element of Sn−1 , and we get a transposition of the form of the previous
case. For the general case, g consists of several cycles. Let g = pq where p is the
cycle containing n and q is the product of some disjoint cycles of n − 1. Then since
q −1 ∈ Sn−1 we can generate p = gq −1 , thus we have a single cycle containing n. 
Definition 6.2 (Incremental generating set). Let A ∈ ISn , then A is incremental
if ∃a ∈ A such that hA \ {a}i ∼
= Sn−1 .
Definition 6.3 (Strongly incremental generating set). Let A ∈ ISn , then A is
strongly incremental if ∀a ∈ A such that hA \ {a}i ∼
= Sn−1 .
The base point generating set, {(1, 2), (1, 3), . . . , (1, n)}, has this property recursively on all of its subsets.
symmetric groups
#incremental

S1
0

S2
1

S3
2

S4
9

S5
92

S6
6907

So if we know |ISn−1 | then we get independent generating sets by adding elements
of Sn \ Stabn . Unfortunately not all of them are independent, since the added
element may interfere with the irreducubility of the smaller generating set.
7. Conclusions
The computational enumeration was done by the SubSemi [5] and BioGAP [6]
(for calculating minimal and maximal diameters) packages for the Gap computer
algebra system [7]. The SubSemi package uses multiplication table representations,
therefore it is capable of calculating independent subsets of semigroups as well, not
just groups.
For checking the results, the number of independent subsets of symmetric groups
was also enumerated independently using the Magma computer algebra system [1].
By a different graph search algorithm and using the permutation group representation directly, the values of |I(Sn )| were calculated up to n = 6. Then, using the set
of conjugacy class representatives I(Sn )/ ∼ constructed by SubSemi, we enumerated
the conjugacy classes, and by summing their cardinalities we got the same values
of |I(Sn )|, but by a different method.
These software tools produced huge amount of data, which in turn yielded interesting observations and raised new combinatorial questions providing novel directions for further theoretical work.

INDEPENDENT GENERATING SETS OF SYMMETRIC GROUPS

7

Acknowledgement. Most of this work was carried out at the Centre for Research
in Mathematics, Western Sydney University, and greatly benefited from discussions
with Andrew R. Francis.
References
[1] Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user
language. J. Symbolic Comput., 24(3-4):235–265, 1997. Computational algebra and number
theory (London, 1993).
[2] Peter J. Cameron and Philippe Cara. Independent generating sets and geometries for symmetric groups. Journal of Algebra, 258(2):641 – 650, 2002.
[3] Keith Conrad. Generating sets. www.math.uconn.edu/~ kconrad/blurbs/grouptheory/genset.pdf.
[4] John D. Dixon. The probability of generating the symmetric group. Mathematische
Zeitschrift, 110(3):199–205, 1969.
[5] James East, Attila Egri-Nagy, and James D. Mitchell. SubSemi – software package for
enumerating subsemigroups, v0.77, 2016. github.com/gap-packages/subsemi.
[6] Attila Egri-Nagy, Andrew R. Francis, and Volker Gebhardt. Bacterial genomics and computational group theory: The BioGAP package for GAP. In Hoon Hong and Chee Yap, editors,
Mathematical Software – ICMS 2014, volume 8592 of Lecture Notes in Computer Science,
pages 67–74. Springer Berlin Heidelberg, 2014. https://github.com/gap-packages/biogap.
[7] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.8.2, 2016.
[8] Thilo Zieschang I. M. Isaacs. Generating symmetric groups. The American Mathematical
Monthly, 102(8):734–739, 1995.
[9] Brendan D McKay. Isomorph-free exhaustive generation. Journal of Algorithms, 26(2):306 –
324, 1998.
[10] Sophie Piccard. Sur les bases du groupe symétrique et du groupe alternant. Mathematische
Annalen, 116:752–767, 1939.
[11] Julius Whiston. Maximal independent generating sets of the symmetric group. Journal of
Algebra, 232(1):255–268, 2000.

Appendix A. Independent generating sets of S4 up to conjugation
The ‘well-known’ generating sets are highlighted.
Ihi (S4 )/ ∼

= {{(3, 4), (2, 3), (1, 2)},

{(3, 4), (2, 3), (1, 2)(3, 4)},

{(3, 4), (2, 3), (1, 3)}, {(3, 4), (2, 3), (1, 3)(2, 4)},
{(3, 4), (2, 3, 4), (1, 2)(3, 4)},
{(3, 4), (2, 3, 4), (1, 3, 4)},
{(3, 4), (2, 3, 4), (1, 3)(2, 4)},
{(3, 4), (2, 3, 4), (1, 4, 3)},
{(3, 4), (2, 3, 4), (1, 4)(2, 3)}, {(3, 4), (1, 2, 3)},
{(3, 4), (1, 2, 3, 4)}, {(2, 3, 4), (1, 2, 3, 4)},
{(2, 3, 4), (1, 2, 4, 3)},

{(1, 2, 3, 4), (1, 2, 4, 3)}}

1 Akita

International University, Yuwa, Akita-city 010-1292, Japan
E-mail address: attila@egri-nagy.hu
2 Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, Western Sydney University, Locked Bag 1797, Penrith, NSW 2751, Australia
E-mail address: v.gebhardt@westernsydney.edu.au

