Invertibility 101

Operations or actions that mathematicians study, that you do while playing games, and those that happen in real life can be split into invertible (reversible) and non-invertible (non-reversible). In real life, putting your socks on is an invertible operation, since you can take them off. Opening a can is non-invertible, you cannot easily close it and return back to the original state. In games, operations in Rubik's Cube and the 15 Puzzle are invertible. If you rotate a face of the Rubik's Cube, rotating it back bring the Cube to the previous state. Sliding a square into the empty slot of the 15 Puzzle is invertible just by sliding the square back. In Tetris,  2048 and thousands of other games either all or most moves are not invertible. Ringiana and Ringsanity are on the side of the Rubik's Cube and the 15 Puzzle in this divide.

In real life it gets more complicated--is walking a mile invertible? Roughly yes, just walk a mile back. But we spent time and a bit of energy walking that mile, and then going back, and the time spent does not come back, except in occasional novels and movies. In real life invertibility is dampened by lost time, resources and opportunity costs, and requires a more refined approach to define and deal with.

Here I want to discuss invertibility in mathematics and in the Ringiana and Ringsanity games. We say that an operation A is invertible if there is an operation B so that doing A then B does not change the original state. We write AB for the operation of doing A then B (for simplicity I'm reversing common math convention that BA denotes doing A then B). The operation of doing nothing, not changing the original state, is called identity and denoted Id (also denoted I, id, 1, e). We write the invertibility condition, that doing A then B is the same as doing nothing as 

            AB = Id 

It turns out not to be quite enough. We should throw in the dual condition, that first doing B than A in the identity (no change in state) as well: 

 BA = Id  

If both properties hold, we say that A and B are invertible and B is the inverse of A. For example, A can the operation 

Take my socks off 

And B the operation

Put my socks on 

Both compositions AB and BA are identities, returning us to the original state before the operations started. There is an additional complication that, at least conventionally, we cannot apply A to any state, only to the state when we are wearing the socks. Likewise for B, which only applies when the socks are off. This can be drawn, with states shown as boxes and actions as arrows. 

A mathematical structure of this kind is called a groupoid. A groupoid has some states and has actions taking us between the states, with every action invertible. 

An additional and extremely useful simplification happens when the same invertible operation can be applied in any state. In the Rubik's Cube game, A could the operation: 

Rotate the face with the central square red 90 degrees clockwise. 

Its inverse B is the operation 

Rotate the face with the central square red 90 degrees anticlockwise. 

Operations A and B are defined no matter how the pieces of the cube have been arranged, and the two operations are inverses of each other.

We write B=A^-1 to denote that B is the inverse of A. This relation is equivalent to A being the inverse of B: 

A=B^-1

Mathematical notion of a group axiomatizes the structure of a collection of invertible operations. A group can be generated by some invertible operations X, Y, Z, ... such that each can be applied to any state of the system. A group G consist of arbitrary finite products of generators X, Y, Z, ... and their inverses. For instance, XY^-1XZ is in the group G if X, Y, Z are in G. It denotes the composition of first doing X, then the inverse of Y, followed by X, followed by Z. Any group contains the identity Id, which is also XX^-1 for any generator X of the group. 

Puzzle time: Can you figure out what is the inverse Id^-1 of the identity? That is, how does one invert doing nothing? 

 Group theory studies groups, collections of invertible transformations (also called symmetries) that are closed under composition (going from X and Y to XY) and under taking inverses (going from X to X^-1). Group theory a big and key subject in mathematics. Books have been written even about particular groups, including the Rubik's Cube Group. That group can be generated by just six operations, rotating one of the six faces of the cube by 90 degrees clockwise. It's a very large but finite group with 2125922464947725402112000 elements. 

Puzzle time: Why do we include both conditions 

AB = Id    and   BA = Id

in our definition of invertibility of A? Why just requiring 

 AB = Id  

is not enough? Can you think of examples from (a) math, (b) games, (c) real life?  

We next look at invertibility in Ringiana (Android, iPhone) and Ringsanity games.  

Spoiler alert and disclaimer!

It's more fun to play these games on your own first and discover invertibility of basic moves for yourself.

There are eight moves in Ringsanity, and in the previous post we labelled them e1 through e8, starting from the first quadrant and going counterclockwise: 

 

 Move e1 expands the first quadrant clockwise and squishes quadrants III and IV together into III. Its inverse is 

Please reread Spoiler Alert above!

the move that expands quadrant III counterclockwise and squishes quadrants I and IV together into a single quadrant, 

and that move is e6. Move e1 followed by move e6 is the same as doing nothing. Move e6 followed by e1 is the same as doing nothing: 

Our shorthand for writing the move e1 followed by e6 is 

e1e6 or e16. Extending this notation, it's natural for us to write identity as e, and our invertibility formula takes the form 

   e16 = e     or     e16 = Id

Let's not forget the other way, e6 then e1 is identity:

e61 = Id 

Since we write, for instance, e463 to denote move e4, followed by e6, then e3, it might be natural to use e for identity, since that's just means no moves (doing nothing). This turns out to be a good convention for Ringsanity, but not for Ringiana, which admits additional moves. For the most part, we'll stick with Id for identity.

Puzzle time: Pair up the remaining six Ringsanity moves into three pairs of mutually-inverse moves before reading the rest of the post.

The answer is in the table below. In the left column there are moves e1 through e4. The right column lists their inverses. 

The pairs are (e1,e6), (e2,e5), (e3,e8), (e4,e7). 

Each Ringsanity move expands a quadrant into an adjacent quadrant. Peer over the adjacent quadrant--next to it on the other side hides the inverse of the move. e1 expands quadrant I into quadrant IV. The other move that expands into quadrant IV is e6, exactly the inverse of e1. 

Moves e2, e5 both expand into quadrant II:

 

Moves e3, e8 expand into quadrant I: 

 and moves e4, e7--into quadrant III:

 

 In each pair of inverse moves, one expands clockwise, the other counterclockwise. 

Ringiana game has four more moves. Compared to e1-e8, these moves are non-agressive and simply transpose adjacent quadrants. We denote these moves s1, s2, s3, s4, starting from the East move (transpose quadrants I and IV) and going counterclockwise. 

Move s1 (East) transposes arcs I and IV. 

Move s2 (North) transposes arcs I and II. 

Move s3 (West) transposes arcs II and III. 

Move s4 (South) transposes arcs III and IV. 

What is the inverse of s1? It's just s1. Doing s1 twice in a row brings us back to the original state. Likewise for the remaining transpositions: the inverse of s2 is s2, of s3 is s3, of s4 is s4: 

 We have 

  s1s1 =  Id,   s2s2 = Id,   s3s3 = Id,  s4s4 = Id

To summarize, Ringsanity has 8 generating moves, all invertible. They pair up into four mutually-inverse pairs. 

Ringiana has 8 (expand) + 4 (swap) = 12 generating moves, with four mutually-inverse pairs of the Expand-Shrink moves and four Swap moves that are their own inverses.

 

Making sense out of chaos: ordering expand-shrink moves

To understand Ringiana (for Android and iPhone)  and Ringsanity (iPhone)  we are going to develop some notations for moves that occur in these games. The most interesting moves, the expand-shrink moves, are common to both games. Every Ringsanity move is an expand-shrink, while Ringiana also has swap or transposition  moves, which exchange two adjacent arcs. 

We  will call expand-shrink moves ES-moves, for lack of a good verb to describe this novel action. An ES-move expands a quarter of the ring into two, either clockwise or counterclockwise, and shrinks the two quarters into one. 

The two shrinking quarters are located along the ring either clockwise or anticlockwise after the expanding quarter. 

Here is a video with a bunch of ES-moves in Ringsanity 

 In Ringsanity only the outer ring moves, while colors of the inner disk remain static. The goal, recall, is to match the colors of the outer ring with those of the inner disk. In Ringiana for iPhone Sergey Nemirovsky (who did almost all the coding) composed ES-moves with radial shrinking and expansion for fancier animations.

 Nikolay Gromov coded Ringiana for Android in OpenGL with a distinctly 3D appearance. ES-moves are still there, but their animations look different. By the way, fancy programming in OpenGL and for Android is not Nikolay's main work. He is a professor of theoretical physics and writes fancy papers such as Quark-anti-quark potential in 4D SYM.

Having looked at implementations of ES-moves, we return to their classification.  There is a total of 8 moves in Ringsanity:  the ring has four quarters, and each quarter can be expanded clockwise or anticlockwise. A programmer would label these moves 0 through 7. As a mathematician, I start with 1 and will label them 1 through 8, adding prefix e  and denoting the moves e1, e2, e3, ..., e8. 

When a mathematician decides to introduce some order in the two-dimensional plane, she often sets up a coordinate system. Let's do that, placing the center of coordinates at the center of the inner disk. Schematically: 

 Outer ring is shown as a shade of yellow, and inner disk light pink. The four quadrants are I, II, III, IV going anticlockwise starting from the Northeast quadrant. 

The four quadrants perfectly match the four quarters of the outer ring. We follow counterclockwise convention and also start with quadrant I. Moves e1, e2 will denote expanding quadrant I piece clockwise and anticlockwise: 

e1 expands piece I counterclockwise and shrinks pieces III and IV into a single piece that will occupy quadrant III. After expansion, piece I occupies quadrants I and IV. 

e2 expands piece I clockwise and shrinks pieces II and III into a single piece that will occupy quadrant III. Following the expansion, piece I occupies quadrants I and II. 

We proceed counterclockwise. Moves e3 and e4 expand the piece in quadrant II, clockwise and anticlockwise, correspondingly: 

 

We proceed, denoting clockwise and anticlockwise expansions of piece III by e5, e6, and the two expansions of piece IV by e7, e8. Here is the diagram of all the moves, where the arrows indicate direction of expansion, clockwise or anticlockwise: 

Now for some applications. Spoiler alerts--we're going to solve levels 1, 3, and 10 of Ringiana, and in few steps. You might want to pause and crack them on your own first!  

Ringiana level 1 is solved by the e2 move:

Ringiana level 3 takes two moves, e5 followed by e8: 

We write this sequence of moves e5e8 or simply e58.

Ringiana level 10 is done in four moves: 

Can you write them down? They are e6, e2, e4, e8. We write the solution as e6e2e4e8 or, shorter, e6248. Each of these moves expands-shrinks counterclockwise, so they are all "anticlockwise" moves. These are exactly the four anticlockwise moves in Ringiana, e2, e4, e6, e8--carrying even labels. The clockwise moves are e1, e3, e5, e7, exactly those with odd labels. In Ringiana notation, odd=clockwise and even=anticlockwise. 

Can you find other Ringiana and Ringsanity levels that can be solved by only clockwise or only anticlockwise moves? 

Mathematics of Ringiana and Ringsanity III: Improving Infinities with Sets

Previous entry II: Solving x + x = x, first entry I: Moves of self-similarity.

To make sense out of our solution x = ∞ and upgrade it to a statement about the object X with the measurement x, we introduce sets. Rigorous axiomatic treatment of sets is long; instead, we follow our intuition and define a set as a collection of elements. Here is a set of 3 people

   S = { Ann, Bob, Carl }.

We list elements of a set inside parenthesis, separated by a comma. Order does not matter, and we can also write 

S = { Carl, Ann, Bob }.

 Exercise: In how many ways can you order elements of this set S? How many ways are there to list elements of a set of 5 people? Can you find a general formula if there are n elements in a set, for n = 1, 2, 3, 4, ... ? 

The number of elements in a set is called its cardinality (it's ok to use "size" if you think "cardinality" is too long). We write cardinality of S as | S |. For our set S above, | S | = 3. 

The empty set with no elements is allowed and denoted ∅.  Listing its elements does not take much space:

  ∅ = { }

and there is a pleasant formula 

     | ∅ | = 0

saying that the cardinality (size) of the empty set ∅ is zero. We won't go  below zero - there are no sets of size -1, -2, and so on. (To interpret the notion of a set of negative size, one needs to do much more - first linearize the concept of a set, then linearize the notion of the boundary of a shape. Some day we'll get to that story.)

Sets can contain various objects; consider this set T of three fruits T = { apple, melon, strawberry }. Set T has cardinality three, | T | = 3, just like S. Let's write S and T side by side: 

S = {Ann, Bob, Carl}   T = {apple, melon, strawberry} 

S and T have the same number of elements. We can match their elements, for instance, by giving apple to Ann, melon to Bob, and strawberry to Carl. A matching between elements of S and T is called an isomorphism between S and T; we denote isomorphism property by the congruence sign 

    S ≅ T 

and say "S is congruent to T" or  "S and T are isomorphic".  

An isomorphism is also called a bijection between elements of S and T. To each element of S we assign an element of T so that different elements of T are assigned to different elements of S (we don't want Bob and Carl to fight over a single strawberry), and each element of T is assigned to some (and unique) element of S. 

If two sets are isomorphic, S ≅ T, they have the same size: 

| S | = | T |  

  

On a deeper level, if two sets are isomorphic, there are many isomorphisms between them unless the sets are really really small (in which case there is only one isomorphism). For our sets S and T,  we can instead choose an isomorphism that gives melon to Ann, apple to Carl, and strawberry to Bob. And there a few other isomorphisms. By the way, the number of isomorphisms between two sets with n elements each is also the number of ways to order elements of either set (this is just me reminding you about the exercise above). 

There is a difference between saying that two sets are isomorphic and choosing a particular isomorphism between them. Ann, Bob, and Carl, the good inhabitants of S, would surely prefer to choose an isomorphism, any isomorphism, between S and T and start eating, rather than spend time staring at elements of T knowing that an isomorphism between them and the set of fruits exists, and more than one.   

In our more advanced examples and manipulations on sets, we will downplay the emotional side of set theory and for the most part will stick to sets of numbers, sequences and points. 

Mathematicians allow infinite sets. In an earlier post we've encountered the infinite set of natural numbers 

N = { 0, 1, 2, 3, ... } .

If a set T is finite, and we create a bigger set U by adding more elements to T, then sets T and U cannot be isomorphic since U has bigger cardinality that T. Interestingly, that is not the  case with infinite sets. 

Infinite sets are strange - we can add elements to them without changing their size. For instance, let's enlarge natural numbers N by adding -1 and calling the resulting set M: 

M = { -1, 0, 1, 2, ... }. 

M properly contains N. That is, every element of N is also an element of M, and some element of M is not in N. In this sense, M is strictly bigger than N. But actually M and N are isomorphic. To construct an isomorphism, we need to assign elements of M to elements of N in a nice (bijective) way. One such bijection is easy to guess if we put N and M next to each other:  

N = { 0,  1, 2, 3, ... }

M = { -1, 0, 1, 2, ... }.

Simply shift every element of N down by 1, that is, assign -1 to 0, 0 to 1, 1 to 2 and so on. To element n of N we assign element n-1 of M, for n = 0, 1, ... This is a sort of infinite shift, and this neat game can only be played with infinite sets. We do get a bijection between N to M this way, even though M contains all elements of N and an extra element. 

Now we come back to our task from the first post, looking for an object X isomorphic to two copies of itself. Let's take an infinite set as X, and, specifically, the set N of natural numbers. Is there a bijection between N and two copies of N? To construct one, we split N into two infinite sets. Any splitting would do, and to keep it simple split N into sets of even and odd integers: 

Even = { 0, 2, 4, 6, 8, ... }  

Odd = { 1, 3, 5, 7, ... } .  

We can write 

N = Even ∪ Odd

to denote that N is a union of two sets, Even and Odd. 

A brief side trip into difference between the usual union of sets and the disjoint union is needed. The usual union 

  X ∪ Y 

of sets X and Y consists of elements of X and elements of Y. If the same element b appears in both X and Y we list it only once in the union. For instance, 

{ a, b, c }  ∪ { b, c, d, e}  = { a, b, c, d, e}.

b appears in both sets, and then once in the union, ditto for c. An element cannot appear in a set more than one. 

Sometimes, we need to engineer an artificial union of two sets and keep track of both copies of each element that appears in X and Y. It's called the disjoint union of X and Y and denoted 

  X ⨆ Y

To implement the disjoint union, for each b that's in both X and Y we add additional labels to signify that it came from a particular set. Relabel b in X by b₀ and b in Y by b₁ to create two different copies of b and same for c in X and Y. Then, 

for the disjoint union of X and Y as above we get 

{ a, b, c }  ⨆ { b, c, d, e}  = { a, b₀, b_1, c₀, c₁, d, e}.

The size of the disjoint union X ⨆ Y is the sum of sizes of X and Y 

  | X ⨆ Y | = | X | + | Y | ,

a simpler formula when compared to  the more familiar case of just the union of sets, where an additional term, the size of the intersection X ∩ Y, enters the equation: 

| X ∪ Y | = | X | + | Y | - | X ∩ Y | .

Since Even and Odd sets in the decomposition of natural numbers N have no elements in common (no number is both even and odd), we can rewrite the union as the disjoint union 

N = Even  ⨆  Odd

where, recall, 

Even = { 0, 2, 4, 6, 8, ... } 

Odd = { 1, 3, 5, 7, ... }.  

There are many bijections between Even and N and between Odd and N. For a bijection between Even and N we choose the one taking 0 to 0, 2 to 1, 4 to 2, 6 to 3, etc. In general, even number 2n is taken to natural number n. Ditto to get a bijection between Odd and N. Take 1 to 0, 3 to 1, 5 to 2, 7 to 3 and so on. Odd number 2n+1 goes to natural number n, for n = 0, 1, 2, ... These bijections give us isomorphisms between sets

  Even  ≅  N   and  Odd  ≅  N

Combining the decomposition N = Even ⨆ Odd with these isomorphisms, we get an isomorphism between N and two copies of N :

  N  ≅  N ⨆ N   

giving us a desired object X isomorphic to two copies of itself together with a particular isomorphism. What about the measurement x of X  that must equal infinity? That measurement is the cardinality (number of elements) of N. It is indeed infinite, and we write 

| N |  =  ∞ 

Actually, cardinalities of infinite sets constitute a sophisticated hierarchy, but for now we observe that N is an infinite set carrying an appropriate label ∞ for its size. 

To summarize the fruits of today's labor, other than those in the set T, we did find a solution to the equation X = X + X  in the world of infinite sets and isomorphisms between them. The next couple of posts will consider ways to prettify and further improve this answer. 

Mathematics of Ringiana and Ringsanity II: Solving x + x = x

This post continues part I: Moves of self-similarity.

Ringiana (for Android and iPhone), Ringsanity (for iPhone), and the math behind these games are based on the idea of manipulating objects that are identical to two copies of themselves. Imagine an abstract object X that can be identified with the double of itself. For lack of notation and clear notion of doubling an object we are going to be informal and denote the double by X+X. Then we are looking for X such that 

X + X = X 

Imagine that X, however abstract, admits some tangible invariant or measurement, such as size, area, length, or volume. Denote the invariant by x. Presumably, the equation X + X = X should translate into the corresponding property of the invariant 

x + x = x 

Say x is a number, then we are trying to solve the equation

2x = x 

Cracking it is not too hard, but, sadly, gives us a not-too-useful unique solution 

x = 0  

telling us that the measurement is zero. At this point it's ok to give up - our object X will have no useful measurements or nontrivial invariants to show. Or we can become creative and set x to infinity 

x = ∞   

Not trying to be too clever, let's think of infinity as a very large number, or better a sequence of numbers that get bigger and bigger. If we can operate on infinity as on a usual number, adding ∞ and a number should be possible - and the answer is easy to guess: 

  ∞ + 10 = ∞ 

and, more generally,

∞ + n = ∞

for any number n. Making n larger and larger, we should get

  ∞ + ∞  = ∞

and suddenly rejoyce in our Eureka moment -- a nontrivial solution is at hand, for our mysterious measurement x is infinity: 

x =  ∞

Whether infinity can be treated as a legitimate number is a tricky question. Examine the simplest popular number system - integers, usually denoted Z. You can add and subtract integers, with these operations satisfying lots of important properties (axioms). Once you add infinity to Z, the structural beauty of integers breaks down. What is ∞ - ∞, infinity minus infinity? It can potentially be anything. Both infinities in the expression 

∞ -  ∞

can be thought of as limits of large numbers. If I choose the sequence of increasing numbers 1,2,3,4, ... for the first infinity and a faster growing sequence 1,2,4,8,16,...,2048,... for the second, hopefully the difference ∞ - ∞ should correspond to the sequence of differences: 

1 - 1 = 0,  2 - 2 = 0, 3 - 4 = -1, 4 - 8 = -4, ..., 

10 - 2048 = - 2038, ... ,

a sequence of negative numbers which should describe -∞, minus infinity. Do we get that ∞ - ∞ = - ∞ ? Not really, for if we swap the sequences and examine the differences, the numbers will be positive and large, and one can as well say that ∞ - ∞ = ∞. With a tiny amount of extra work you can set up the sequences to get ∞ - ∞ = n, for any number n. The difference of two infinities behaves pretty democratically and can take on any value. This teaches us to treat infinities carefully and don't extend the familiar operations on numbers to them in a cavalier way.

Allowing infinity into our world to get a nontrivial solution to the equation 

 x + x = x 

is not a bad idea, however. Something has to give, and we choose to disallow subtraction from our system. Let's keep addition and multiplication, to at least have something. Without subtraction, we can as well downsize from integers to natural numbers, denoted N. They are 0, 1, 2, 3, 4, ... Due to historical and cultural differences in teaching mathematics, some people consider 0 a natural number and some do not. You do get a richer structure if you include 0, and we follow this convention. 

After adding infinity ∞ to natural numbers N both addition and multiplication can still be defined on this larger system and will share many properties with the corresponding operations on natural numbers. Some other properties will fail, though, and the union of infinity and natural numbers is not a particularly beautiful mathematical structure.   

Luckily, the day can be saved: the union of natural numbers and infinity is a shadow of a better and healthier structure that will be revealed in the next installment of the series. 

 

Mathematics of Ringiana and Ringsanity I: Moves of self-similarity

My background is in math, and I do research in pure mathematics at Columbia University. Recently, as a side gig, I and a couple of friends (Nikolay Gromov and Sergey Nemirovsky) developed two mobile games, Ringiana and Ringsanity. Ringiana is available for both iPhone and android, while Ringsanity you can get for iPhone, with  android version in the works. 

These are puzzle-like games, with easy to describe moves but unusual building blocks. Actually, there are no minimal building blocks in these games. Any object can be split into two objects and any two consecutive objects can be merged into a single one. We chose to keep the number of objects constant and equal to four, to match the number of colors in the Ringiana game. To keep the number of objects the same, every time you split an object, two other objects merge, and every time you merge two objects, one of the remaining objects breaks into two, with the total of four objects at any moment. 

Here's the Youtube tutorial for Ringiana, to show you what these convoluted operations are: 

Secretly, we're hoping you are ready to try the real thing and download the game. And, after managing to invent two nouns to name the games, we are still at a loss for a new verb to describe these simultaneous merge-split moves - suggestions are very welcome! 

The unusual feature of our modest contributions to the overcrowded game sections of mobile app stores is this absence of elementary blocks. Think of the games you've played - they all have characters or elementary objects in the background, like atoms, that cannot be decomposed any further. In Tetris, these are the four-square blocks that drop down and the little squares of the grid, in Pac-Man it's the main character, its chasers or groupies, the background grid pieces, and the food the character consumes. These objects may vanish, may reappear, may perhaps merge in pairs into a different basic object (think 2048 or Triple Town), but they don't have any infinite hierarchical or self-similar structure that we've created for the basic objects of our puzzles. 

Once you learn the moves, the games are easy to play. In Ringiana, you'll quickly see that a target configuration (making each piece monochromatic) can be eventually reached no matter what the starting position is, and the challenge becomes finding a short solution. Well, more carefully speaking, the really hard problem is finding a solution with the minimal number of steps. This problem is a great topic for another blog post, and some day we'll come back to it. Ringiana is not only about math research, of course, and we are also hoping that people can simply enjoy playing it and solving the puzzles without exerting themselves to find the shortest way.

With Ringsanity we've decided to be meaner. There are fewer moves available compared to Ringiana (the really interesting ones stayed, of course), and the target configurations are more varied. Ringsanity is a tougher game than Ringiana, unless you're on a hunt for the shortest solutions, in which case both games should prove hard. 

Friends we've shown the game to often take their time to get used to the merge-split moves, but all eventually master them. The same moves are behind some pretty fundamental yet mostly mysterious and poorly understood mathematical structures that go under the name Thompson groups. Some researchers have apparently been so frustrated by the difficulties these groups represent even to the best and brightest of us that they've taken to calling them vagabond groups and chameleon groups. 


The creators of Ringiana and Ringsanity did not fare any better than those researchers and have not proved any magic theorems uncovering the deep structure of Thompson groups. But we did make the games. We hope that releasing Ringiana and Ringsanity will attract more attention to the math behind Thompson groups and speed up progress in unvagabonding them.

Starting in part II, we delve into Ringianity math.