Significance and Applications

There are numerous connections that we could make between the Rubik's cube and other fields, but here, we will only discuss one for the sake of time.

First, one particularly interesting application is a connection between minimizing the number of steps to solve a Rubik's cube and cipher cracking. Optimization is a common interest in mathematics, so it's no surprise that many mathematicians have been interested in how to minimize the number of moves needed to solve a scrambled cube.

A video by Polylog explores how a technique called "Meet in the Middle" can be used to both in finding how to solve a Rubik's cube in the minimum possible number of steps and to decrypt ciphers. In the "Meet in the Middle" technique for Rubik's Cubes, one begins with both the scrambled cube and the solved cube and at each step looks at all possible cubes that could result from applying one move to the cube. Eventually, in one of the steps, you will find a cube state that is common to both the possible outcomes from the solved cube and the scrambled cube. From here, one can simply look at the steps taken to get from the scrambled cube to the intermediate state and then look at the reverse of the steps taken from the solved cube to the intermediate state. This gives a continuous path from the scrambled cube to the solved cube.

The motivation for beginning from both the scrambled cube and the solved cube and meeting in the middle rather than simply starting from one side and searching all possible outcomes until reaching the other state is that it dramatically reduces the computational load. For each subsequent step, the number of possible outcomes grows exponentially, roughly by a factor of 10. Since other papers have shown that a scrambled cube can require up to 20 moves as the minimum distance from the scrambled to solved state, this means that our computer would potentially have to search up to 1020 possibilities. This is not possible for most computers today. On the other hand, searching from both sides reduces it to only 2 x 1010 which is much more feasible for modern computers.

Now, for how this relates to ciphers. A common cipher that has used to be standard in computer encryption involved applying a secret key to the original text which produced an encrypted text of apparent gibberish which could be sent safely. Then, upon receiving the text, the secret key could be applied again to decrypt the text producing the original document. However, with advances in computing, if somebody could get ahold of an original and encrypted version of a text, it became possible for computers to uncover the secret key through brute force testing of all possible keys. Once they had the key, they could easily decipher all future intercepted encrypted texts. So, how to solve this problem?

Well, they ended up simply having 3 separate keys applied sequentially to each text to encrypt and then decrypt it. However, why use 3? Why couldn't they just use 2 keys? It's because using the "Meet in the Middle" technique, 2 ciphers would be no more secure than one. Somebody could simply start from both the original and encrypted text producing all possible intermediate texts, and once they find an intermediate text common to both, they know that they've found their pair of secret keys.

This is an excellent example of how mathematical discoveries frequently have unexpected applications in other fields. People sometimes wonder what the "point" is of many mathematical ideas that don't have obvious connections to the "real" world. Well, one response is what's the point of art or music? We place value on many things simply because we find enjoyment in the creation and beauty in the sharing of them. For many mathematicians, that's how math is.

However, for those who don't consider that a "good enough" reason, it's worth noting that many important mathematical discoveries later applied in other fields were found by mathematicians who, at the time, had no clear application. They were simply enjoying the math. In addition to the encryption connections to mathematics of a Rubik's cube just discussed, there are many other examples of unexpected applications of mathematics, sometimes many years after they were initially discovered. For example, imaginary numbers were first introduced during the 16th century when there was a great fascination with finding the roots of polynomials. Hundreds of years later, we've found that imaginary numbers are also highly important for modeling waves and have become particularly useful in electrical engineering.

All this to say, while applications of mathematics can certainly be important, sometimes, focusing on mathematics for its own sake gives rise to unexpected applications later on down the road.