Orbit-Stabilizer Theorem

October 15, 2019

This is going to be a different sort of post from the ranting-about-math-education kinds that usually I make.

As many of you know, when I'm not doing math (yes, I do take a break sometimes), I write electronic music, some of which makes its way into rhythm games.  Most recently, I wrote a track called Orbit Stabilizer for the Korean dance game Pump It Up XX.

If you didn't figure it out from watching the background animation, there's a mathematical connection to the song.  This isn't the first time I've made references to mathematics in my music:

This time, the reference is to something from a branch of mathematics called group theory, which is part of the deep abstract foundations for algebra.  It was pioneered simultaneously by French mathematician Évariste Galois (who shows up in the background of the Orbit Stabilizer video!) and Norwegian mathematician Niels Henrik Abel.  Both are worth reading up on ― heartbreaking stories of geniuses who died tragically young.

Group theory is, in essence, the study of symmetry.  It can be used to describe everything from the shuffling of cards and the positions of a Rubik's cube to the fundamental laws of physics that govern our universe.  I'm not going to go into an in-depth explanation of group theory ― there are plenty of YouTube videos that do that (including my own).  Rather I'm going to go just far enough to explain what the orbit-stabilizer theorem is.

Imagine you have a square sheet of paper in front of you.

You look away, and then I sneak in and potentially move the paper in some way.  When you look back, the square looks the same as it did before.  What could I have done to the paper?

The set of possible transformations I could have done are called symmetries of the square.  In this case, there are three overall types of such symmetries:

All in all, I have eight possible transformations that would take the square back to itself.  Notice that translations (shifts) aren't included ― if I'd moved the paper a bit to the left, you would have noticed (we assume)!  We're only considering transformations that would leave you completely unable to tell what I did.  To visualize the effects of these transformations better, we can label the square and watch what happens:

These transformations form what mathematicians call a group,  which means that they obey four fundamental laws (axioms):

  1. Combining any two of these transformations ― such as, say, rotating by \(90^\circ\) counterclockwise and then flipping across the horizontal axis ― also takes the square back to itself, and is equivalent to one of the original eight transformations ― in this case, flipping across the "backslash" diagonal axis.  We call this the closure law.
  2. Combining transformations is associative, which means that if I have any transformations \(a\), \(b\), and \(c\), then \((ab)c\) ― that is, doing \(c\) first and then doing whatever \((ab)\) is equivalent to ― gives the same result as \(a(bc)\) ― that is, doing whatever \((bc)\) is equivalent to first and then doing \(a\) afterward.  This is just like how you can move parentheses around when doing addition and multiplication.
  3. The set of transformations includes an identity transformation, which essentially does nothing.  (I say "essentially" because you could also think of a \(360^\circ\) rotation as an identity transformation since it has no overall effect.)
  4. Every transformation has an inverse transformation which "undoes" it.  For example, a rotation of \(90^\circ\) can be undone by a rotation of \(270^\circ\), or a reflection can be undone by doing that same reflection again.

We usually use the letter \(G\) to talk about a group in general.  We'll also use the notation \(|G|\) to talk about the "size" of a group ― so in this case, we have \(|G|=8\).

So we know that these transformations take the square back to itself, but what if we ask what happens to just a single point inside of the square?

Suppose we let \(x\) mark the midpoint of segment \(AB\).  Then we can see where \(x\) lands after each of the transformations:

The set of possible places where \(x\) can land using our transformations is called the orbit of \(x\) under our group, and we denote it as \(\text{orb}(x)\).  Since there are four different places that \(x\) can land ― it can end up on any one of the four midpoints of one of the sides ― we say that \(|\text{orb}(x)|=4\).

Looking a little closer, we can find that there are two particular transformations that do something special.  Focus on the identity transformation and the vertical axis flip.  What happens to \(x\) under these two transformations?  Well, it stays where it is!  The other six transformations, on the other hand, all move \(x\) to a different point of the square.  These two special transformations form what's called the stabilizer of \(x\) under our group, and we denote it as \(\text{stab}(x)\).  The stabilizer forms what's called a subgroup of our original group, because if you limit yourself to only doing those things, you still satisfy the same basic group laws.  Again, we can measure the "size" of the stabilizer, which in this case is \(|\text{stab}(x)|=2\).

Now, look at the three "sizes" we've computed.
\]Those three numbers (\(8\), \(4\), and \(2\)) are just begging to be related to each other!


Is this a coincidence?  Well, you can find out for yourself by picking different places for \(x\) (like, say, a corner point, or the very center, or just some random point in the square), then calculating the sizes of its orbit and its stabilizer.  Or you can even try it for a different shape, like a triangle or a rhombus or a pentagon, which will have a different size group.  You'll notice that you always get that same relationship!

That relationship is called the Orbit-Stabilizer Theorem.

...well, almost.

We actually run into a bit of a problem if our group is infinite.  If that's the case, then multiplying and dividing using infinite numbers can get a bit hairy and make it a bit difficult to show that the relationship is meaningful.  To deal with that case, we usually write the Orbit-Stabilizer Theorem in a slightly different way:

\[|\text{orb}(x)|=[G : \text{stab}(x)]\]

The quantity \([G : \text{stab}(x)]\) is called the index of the stabilizer as a subgroup of \(G\).  Essentially this stands for how many copies of \(\text{stab}(x)\) can fit inside \(G\).  (Technically it's how many "cosets" the stabilizer has, if you want to look that up.)  This is the version of the equation that shows up in the video.

Okay, so that explains what the Orbit-Stabilizer Theorem is.  But, you might be wondering, is it also useful?

Well, one famous result in combinatorics (the study of counting) that makes great use of the Orbit-Stabilizer Theorem is Burnside's Lemma.  Burnside's Lemma can be used to solve problems like counting the number of possible ways that the sides of a cube can be painted with three different colors.  (Painting the top side blue and all the others white is considered the same as, say, painting the front side blue and all the others white, since you can just rotate one to get the other.)  Looking for something more "real-world"?  Burnside's Lemma has applications in chemistry ― like if you need to find out how many different ways certain groups can be placed around a central carbon atom ― as well as other areas such as electronic circuits and even (to bring things full circle) music theory!

Hopefully this gives you an idea of why the Orbit-Stabilizer Theorem is interesting, and why I would name a song after it (besides just being a cool-sounding name).  Feel free to let me know if you have any questions.  And of course, if you play Pump It Up, give the track a shot!

P.S.  If you want to know more about group theory, I would highly recommend this YouTube series by Dr. Matt Salomone at Bridgewater State University.  He has a knack for making these sorts of abstract algebraic topics very accessible with excellent examples and intuitive explanations!