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

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

Share

COinS
 

© Copyright 2016 Peter C. Nelson