In abstract algebra, the symmetric group Sn on a finite set X (containing n elements)
is the set of all possible mappings from X to itself, and whose group operation
is multiplication. In practice, Sn = all possible permutations of set Xs n distinct
elements; thus the magnitude of Sn is n!. We can partition Sn into one or more
parts (also known as blocks or cells) â˘A ¸S that is to say, we can divide Sn into a
union of non-overlapping, non-empty subsets; these blocks form a basis for Sn. We
can also say that they form a subalgebra of Sn if any combination of these parts
via composition produces a linear combination of the blocks formed by the initial
This paper seeks to find out, for any given n, how many of the potential bell
number of ways to partition Sn actually yield a working subalgbera. Once all of the
subalgebras for n = 1; 2; : : : are found, the intention is to try to discern if there are
any mathematical patterns and/or categories that these partitions fall into.
The number of possible ways to partition Sn increases dramatically as n increases,
meaning that even for n = 4 we are already looking at a 15-digit number of possible
ways to divide Sn. This means that checking all possible partitions of Sn via brute
force would be prohibitively inefficient. Instead, this paper will attempt to find
all possible subalgebras via several different approaches, including Monte Carlo
simulations, as well as examining subsets of prohibitively large search spaces.
Nelson, Peter C., "Needles and Haystacks: A Computational Approach to Finding Subalgebras of the Group Algebra of the Symmetric Group" (2016). Senior Independent Study Theses. Paper 7132.
Computer Sciences | Number Theory
Bachelor of Arts
Senior Independent Study Thesis
© Copyright 2016 Peter C. Nelson