Commutative Transformation Semigroups

I expect I have less experience writing than most of the other interns, as when studying maths at undergrad level you rarely need to write in full sentences, so please forgive me for any basic writing errors. What I’ve actually been doing falls into two main categories. The first being writing code for my supervisor’s github page which is accessible online here: http://github.com/james-d-mitchell/libsemigroups-python-bindings, and the second being learning more about semigroups and attempting to find new algorithms which can be of use to making the code more useful. In my opinion the latter of these two is where most of the fun lies.

Over the course of my internship so far I have learned a great deal about mathematics and mathematical research. Unfortunately however in order to explain what I have learned properly to non-mathematicians would require far more space than I have here, so instead I will attempt to explain the basic concepts underlying what I have done. I enjoy studying pure mathematics far more than any of it’s other forms and I believe that mathematics should be learned and studied rigorously and in a “sensible” order. The topic of semigroups is an unusual place to start, in particular most who try to learn about semigroups are already somewhat familiar with the wonders of group theory. Fortunately however as semigroups are so abstract they are relatively easy to define.

I like to define things properly so for my own piece of mind I will give you the rigorous definition of a semigroup. A semigroup is a set X together with a binary operation * satisfying the following conditions:

  1. Closure: for all x,y in X we have (x*y) is in X
  1. Associativity: for all x,y,z in X we have (x*y)*z = x*(y*z)

A semigroup is commutative if it satisfies that: for all x,y in X we have x*y = y*x

A well know example of a commutative semigroup is the set of natural numbers          {1, 2, 3, 4 …} under the binary operation +.

Throughout most of my research I have been working with commutative transformation semigroups. A transformation is a function from a set to itself, it usually doesn’t matter what the set actually contains so for simplicity we tend to use a set of numbers. A commutative transformation semigroup is simply a commutative semigroup in which all elements are transformations, and the binary operation is composition.

As with most things, the best way of understanding this is with a picture:

Here we have three transformations on the set {0, 1, 2, 3, 4, 5, 6}. How the transformations action on each number is shown by an arrow pointing to where each number is sent. If we apply transformation 1 followed by transformation 2 we get transformation 3. For example if we map 4 by transformation 1 we get 1, and if we map 1 by the transformation 2 we get 0, and indeed transformation 3 maps 4 to 0. Notice also that transformations 1 and 2 commute, meaning that if you apply transformation 2 and then transformation 1 we still get transformation 3. This turns out to be a very powerful property which I am attempting to make use of in order the make my code better.

That’s probably enough for now but if you want more I highly encourage you to explore for yourself. Good luck to all of you with your coming research.

Leave a Reply