#### Abstract

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

partitioning.

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.

#### Advisor

Visa, Sofia

#### Second Advisor

Moynihan, Mathew

#### Department

Computer Science

#### Recommended Citation

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.

https://openworks.wooster.edu/independentstudy/7132

#### Disciplines

Computer Sciences | Number Theory

#### Keywords

subalgebra of the group algebra of the symmetric set, monte carlo, enumeration, gray code, algorithm

#### Publication Date

2016

#### Degree Granted

Bachelor of Arts

#### Document Type

Senior Independent Study Thesis

© Copyright 2016 Peter C. Nelson