Symmetry is everywhere in our natural world. Just take a look at your hands, a butterfly, or a sunflower. It’s easy to pass off the idea of symmetry and symmetric structures as a simple quirk of existence, and to pay it little mind. If this is your view, I can assure you it will no longer be by the end of this series. If we force ourselves to look beyond the grade school applications of symmetry, we find a world rich in connections via many different types of symmetric identities. One of the most interesting is Gauge Symmetry, which lies at the heart of Quantum Electrodynamics, or QED (we’ll get into this a bit later in the series). Several branches of higher level mathematics study symmetry in detail, allowing a host of sciences, from physics to chemistry, to view difficult problems and theories from a different perspective.
The subject matter of the ideas explored in symmetry is complicated, and not well known outside of academia and the theoretical sciences. It is the goal of this series of articles to simplify some of the concepts that underpin the study of symmetry, so that the average hacker can gain a basic (and I mean basic) understanding of this fascinating body of knowledge, and put it to use in future projects. We’ll start things off by taking a look at a machine that has crossed the Hackaday server many times – those nifty Rubik’s Cube solvers. Just how do those things work anyway?
The Rubik’s Cube
When [Erno Rubik] invented his famous puzzle in the late seventies, he quickly found out that trying to solve it via random twists was an impossible task. He was quite right, as there are over 43 quintillion states, or permutations, that can be made on a 3×3 Rubik’s Cube. It’s hard to imagine him not getting a chuckle out of watching a machine solve his invention in a single second. Now, we all know how that thing works. We know how webcams and stepper motors work, and how to tie them to a SBC running some type of solving algorithm. But what about the algorithm itself? What is it doing to solve the puzzle?
One approach is to turn the instructions on the Rubik’s Cube website into source code. Indeed, this is how many of these solvers work. This process works in layers for which you designate by orienting the cube so that the top layer faces up and the bottom layer faces down. The top layer is solved by aligning the middle cubes first (making ‘the cross’), and then the corners. Once the top layer is solved, the middle layer is tackled. And finally the bottom to complete the puzzle. Solving each layer can be done by simply following the directions on the website.
The problem with this approach is it follows Searle’s Chinese Room argument – a thought experiment to show that computers can never be “intelligent.” It consists of a man in a room following directions. One person inputs some questions and the man follows the directions that allow him to answer the questions, even though he doesn’t understand the questions themselves. They are written in Chinese. He outputs his results. The person reads the output and declares the room intelligent. But the man was simply following directions…he has no idea of what he wrote means. With our Rubik’s Cube algorithm, we’re simply following directions without the slightest clue on how or why it works.
Another approach, more appropriate for this article, is to consider the Rubik’s Cube in light of a branch of mathematics called Abstract Algebra, as this algorithm does. This will allow us to exit out of Searle’s room and truly understand what we’re doing.
Now, this is where we enter simplistic mode. Abstract algebra is a graduate level math course, and I will not pretend to understand or explain it on that level. My goal is to give you a basic definition of what it means, so that we can understand a little more about symmetry and symmetric structures.
Let us consider the equation:
Many of us will provide the answer of x = 2/5. This is because we’re making some implicit assumptions, such that 5x means “five multiplied by x” and that the real numbers are allowed answers. From this point out, we’re no longer allowed to make those assumptions.
Let’s generalize the above equation to:
We have to ask ourselves the following questions:
What objects are “a” and “b”? They don’t have to be numbers. They can be anything, including permutations of a Rubik’s Cube.
What is “x” allowed to be?
What does the “•” operation do?
You should be able to see where the ‘abstract’ in abstract algebra comes from. Let’s push this idea further and see what happens when me make up some new rules to answer these questions.
Let us consider a particular set of elements. Elements can be anything…numbers, Rubik’s Cube permutations, Arduinos, anything. A set is just a collection of distinct objects (our elements). A well known example would be the set of integers. Each integer is an element of the set. Think about a box of resistors. The box containing all of the resistors is a set, and each resistor is an element of that set. You get the idea.
Now let us apply some rules, also known as axioms (I use ‘rules’ because it sounds less intimidating), to our set. If a set of elements passes all of our rules, it shall be considered a Group.
Rule 1 – Closure
If a and b are in our group, then a • b is also in the group
Remember that the ‘•’ does not mean multiplication. It’s called a binary operator and it can be anything. An example would be if a and b are permutations of our Rubik’s Cube and the ‘•’ operator means turning the top, side, bottom, etc. In this case, a Rubik’s Cube passes the Closure Rule, because after we perform our binary operation, the resulting permutations exist within our set (the cube itself).
Rule 2 – Associativity
If a, b and x are in our group, then (a • b) • x = a • (b • x)
Only addition and multiplication of real numbers are associative. Subtraction and division are not. Thus when working with groups, instead of subtracting we must add a negative. For division, we multiply by the reciprocal. In abstract algebra, these are known as inverses.
For our Rubik’s Cube, turning a face twice, then once will produce the same result as turning the face once, then twice. Our cube passes the Associativity Rule.
Rule 3 – Identity
There exists an element of our group, that we shall call 'e', such that for any element a of our group, a • e = e • a = a
Now this one looks a bit tricky at first, but it’s simple once you see some examples. It’s also closely related to Rule 4, and might make more sense after reading both Rules 3 and 4. If our set is to be considered a group, there must exist an identity element. This element is neutral, and when the binary operation is performed with any element in the set against the identity element, the result will be the unmodified element. If our binary operator were addition, the identity element would be zero. If our binary operator were multiplication, the identity element would be one.
The Identity Rule is important to identifying symmetry as it looks for some type of invariance within a structure (or group). Invariance meaning parts of the group that do not change even when its elements undergo an operation.
The Identity element for our Rubik’s Cube is basically to do nothing. This will make more sense after reading Rule 4.
Rule 4 – Inverse
For any element a of our group, there is an element a-1 such that a • a-1 = e and a-1 • a = e
As advertised, Rule 4 is related to Rule 3 in that it involves our Identity element. It says that in order for our set to be considered a group, there must exist an inverse for each element in the set, so that when our binary operator is applied to the element and its inverse, the result will be the group’s Identity element.
For our Rubik’s Cube, the inverse is the opposite move of what was made. So if I turn the top face right, the Inverse would be to turn the top face left. This would leave us with an unchanged cube, which is what we would get for our Identity element, because doing the inverse is the same as doing nothing.
Consider the set of integers and let us apply the binary operator of addition. Is the set of integers a group?
Rule 1 – Closure – PASS
Any element in the set of integers added to another element within the set will result in an element within the set.
Rule 2 – Associative – PASS
Addition is associative, so this one’s a no brainer.
Rule 3 – Identity – PASS
Zero is the identity element because any element in the set added to zero does not change.
Rule 4 – Inverse – PASS
Every element in the set has an inverse in its negative value, and when added to the element results in the identity element of zero…i.e 4 + (-4) = 0
It would appear the set of integers is a group. We have also shown that the 42 quintillion permutations of a Rubik’s Cube can be considered a group. It is therefore possible to apply Group Theory to the Rubik’s Cube and solve the puzzle.
Let the concept of these axioms set in and in the next article we’ll show how Group Theory lets us understand symmetry in a new way. Take a look at the short video below for a recap on Group Theory and how it not only applies to a Rubik’s Cube, but to music as well.
Dogschool (this page is old and might crash your browser)