Looking Out To Sea

Spotting patterns is fantastic. There’s something deeply satisfying about bringing together a collection of unrelated items and saying “they all do X”.

We’re all familiar with the concept of addition, and the fact that you can add zero and it doesn’t change the number you’ve added to:

3 + 1 = 4
 
3 + 0 = 3
0 + 3 = 3
 
x + 0 = x
0 + x = x

In this case, we call the number zero the identity for the addition operator. If we use it alongside addition it returns the same number we started with. The same concept arises in multiplication:

3 * 5 = 15
 
3 * 1 = 3
1 * 3 = 3
 
y * 1 = y
1 * y = y

In the case of multiplication, the identity is the number one, but the concept is the same. We have an operation and a special value, and if we use them together on another value, we end up where we started. This works with matrices — adding or mutiplying by the right value can leave us with the original matrix.

[ x y z ]   [ 1 0 0 ]   [ x y z ]
[ m n o ] * [ 0 1 0 ] = [ m n o ]
[ p q r ]   [ 0 0 1 ]   [ p q r ]

We can generalise this to make the idea explicit. Let’s call the operator “~” because it’s not commonly used in arithmetic, and the letter “i” for the identity. This isn’t supposed to mean anything, I just want to show you an outline, a template for what I mean.

x ~ i = x
i ~ x = x

The joining of i doesn’t affect x in any way. It’s inert, it’s the identity, it’s ineffective. Once you’ve got to this abstract level, it turns out that the values we slot into x and i here don’t actually have to be numbers, and ~ doesn’t have to work on numbers. For example, mathematical functions can be joined together like this, so that x ~ y is “do x then do y on the result”. If we have a function double and a function sin we can join them together in either order:

sin ~ double = 2(sin x)
double ~ sin = sin (2x)

This is called function composition, and it’s how we think about applying one function to the result of another function. And it has an identity which we call id:

sin ~ id = sin x
id ~ sin = sin x
 
double ~ id = 2x
id ~ double = 2x

The identity function returns everything it is given, unchanged. As usual, the id effectively disappears when we compose it with other functions. Of course these examples have all been maths-based so far, but that doesn’t mean we should only think about mathematical things in this way.

If you remember the joke about celery being the perfect dieting food, because it gives you as much energy as you use to eat it, then we can think of celery as our identity value, and ~ as “eat with”:

cake ~ celery ~ celery ~ celery = cake

No matter how much celery you eat it doesn’t make any difference…

This thing that I’ve been describing is called a monoid. It isn’t a thing on its own, it’s just a pattern that’s been noticed over the years by mathematicians. It’s one of the simpler patterns (nearly the simplest) and it doesn’t describe much. But it’s still an interesting foundation.

There are other patterns people have noticed. Sometimes you can join two values together to make the identity value.

-3 + 3 = 0
3 + -3 = 0
 
0.5 * 2 = 1
2 * 0.5 = 1

If you double something then half it, you’ve effectively done nothing. If you add 3 then subtract 3 you’ve done nothing.

-3 + x + 3  = x
0.5 * x * 2 = x

So using our thinking from above, we abstract this into its essentials:

x ~ y = i
y ~ x = i

The values x and y are inverses of each other. Together they reduce to the identity. As interesting as the original notion of a monoid was, this is infinitely more powerful. Let’s look at some examples.

The game of Rubik’s Cube lets you spin coloured facets around a larger cube, with the eventual aim of lining up all the similar colours on the same sides of the cube. It’s vitally important that every action has a “reverse” action, which will undo it. If there were actions that one could do but not undo then you could “break” the game, ie get it into a state such that it could never be solved. In fact, we can even think of the scrambling and solving processes as being inverse of each other:

scramble ~ unscramble = i
unscramble ~ scramble = i

If I give you a solved puzzle, and then you scramble it up, I can follow the reverse of your scrambling process to end up in the solved state again. This pattern, with two values which are the inverse of each other, is called a group. All the permutations of the Rubik’s Cube are said to form a group, and one can move freely from one to another simply by twisting — which is why a Rubik’s Cube is always solvable.

Similarly, sliding tile games are examples of this pattern. The tiles are arranged on a grid, with one missing to allow you to rearrange the tiles by sliding. Each tile can slide into a space left behind by another tile, so we can slowly rearrange the tiles to make a picture. The most famous example is the Fifteen puzzle, which contain the numbers 1–15 and a gap in a 4x4 grid. The numbers are all in sequence, except the 14 and 15 which are reversed. But unlike the Rubik’s Cube, no matter what you do this version of the puzzle cannot be solved (the numbers cannot be moved into the correct order). This is because the starting state and the desired solution are not both in the same group. There is no sequence of moves which can convert the initial state of the puzzle to the final state without lifting tiles out.

In our notation, the equation—

scramble ~ unscramble = i

—doesn’t exist. The initial and final states of the puzzle are living in two separate universes. They are like the two bishops in chess, who perform the same manoeuvres but will never meet, because they started out on different coloured squares. This concept is called “closure” and means that the result of any operation cannot be outside the allowed, “closed”, set. So all legal moves by a bishop on a red square end up on a red square.

These operations which exist with inverses and closure explain some of the properties of the real world. Hundreds of years ago the alchemists wanted to turn turn base metals into gold. But they were held back because all the operations they used (burning, melting, dissolving, etc.) were “closed” within their particular atomic element. They could never change the elements being used, only rearrange them into different molecules.

Elsewhere in chemistry catalysts are used to make reactions more efficient. The catalysts themselves aren’t used up in the reaction, but they are involved in the reaction. But whatever happens to them also gets undone by the time the reaction has finished. The catalyst is added to the mixture, but then removed at the end. It seems like it has done nothing (and in some sense it hasn’t, because it can’t make reactions happen that would never happen otherwise) but its presence there was useful anyway. That’s maybe a confusing example, but it appealed to me. :-)

If you want to learn more about groups and group theory, I really recommend Mario Livio’s book called The Equation That Couldn’t Be Solved. It explains everything in much richer detail and with lots of interesting examples. It also describes the rather tragic lives of the two discoverers of the field, Niels Abel and Evariste Galois. Seek it out.

Creative Commons-licensed photo by CodeFin.

Trackback URI | Comments RSS