(added Sep. 2014: An updated version of this article will appear in the College Math Journal.)

We have an appetite for information, and especially for pattern, information that falls into meaningful arrays from which we can make rich inferences. Information can be costly to obtain and analyze, but because it offers an invaluable basis for action, nature evolves senses and minds to gather and process information appropriate to particular modes of life. Like other species, humans can assimilate information through the rapid processing that specialized pattern recognition allows, but unlike other species we also seek, shape, and share information in an open-ended way. Since pattern makes data swiftly intelligible, we actively pursue patterns…

Brian Boyd
(On the Origin of Stories, [B])

Introduction

The Rubik’s cube was a world-wide obsession in the early 1980, when Tomas Rokicki, a high school junior in Texas, got his first one. Around the same time, Tom began losing his sense of hearing.

During the 1980s there were Rubik’s cube solving contests (some even televised) but no one knew the smallest number of moves needed to solve the cube. This mysterious quantity, “God’s number,” was the number of moves needed to solve the cube in its most scrambled state. Although David Singmaster, cubologist extraordinaire, guessed it might be in the low 20s, no one had a serious conjecture as to what God’s number would actually be. The cube solving contest winners relied on knowing various solving strategies and very fast finger movement.

During that era, hearing aids were very primitive and no one knew how to restore hearing to those who were totally deaf. In the 1970s-1980s, hearing aids were so-called “in the ear” transistor devices. By the time Tom got his first one in the 1980s, they were small earbuds which fit inside the ear, but not reaching into the ear canal [T]. Unfortunately, the device was useless unless you had at least some hearing ability.

We do know, thanks to Tom Rokicki’s recent work, the value of God’s number (explained below). This was a very difficult problem to solve. Also, we do know, due to decades of work by many researchers, how to restore hearing to the totally deaf [W]. Thanks to two double cochlear implant surgeries, that Tom’s hearing is almost fully restored. Digitizing human hearing is a very difficult problem to solve.

The Rubik’s cube

The Rubik’s cube, or simply the cube for short, was unleashed on the world in the
mid 1970’s. It became a sensation world-wide but is still remains a popular mechanical puzzle for people of all ages. For the sake of orientation, here is a short description. Image a cube sitting on a table. This cube has six faces: up, down, left, right, front and back. Color each of the six faces with a different color. Now cut up the cube into 27 subcubes of equal size using slices parallel to the faces. In the mid 1970s, Erno Rubik, a Hungarian professor of architecture and design at a university in Budapest, did just this but also figured out an ingenious internal mechanism for connecting the 26 external subcubes in a way that allows them to be rotated around a center. This mechanism allows each face to be rotated by or or , clockwise or counterclockwise. The effect of this is that the centers of the faces do not change. If you imagine the front face of the cube as always facing you and that you are holding the cube with your right hand on the right face, the the total number of different positions that the cube could be scrambled is

or about 43 billion billion positions (see [J]). In the sense of Brian Boyd’s quotation, the Rubik’s cube is full of “patterns.”

Imagine having to search through this. How does it compare with finding a needle in a haystack? A straw of hay is about 1 gram. For a 200 pound haystack, that works out to about straws in a haystack. In other words, finding a needle in a haystack is (“ten thousand billion”) times easier. How does it compare to the gross domestic product of the United States economy? This number is over one million times the size of the United States GDP. How does it compare to the distance to the moon in the sky? If you stacked sheets of paper on top of each other until their thickness grew to the moon, the number of sheets you uses would be over a million times smaller than this number . How does it compare to searching the largest publically known database that arose in commerce or government? The largest such database is at the World Data Centre for Climate [F], weighing in at about petabytes, or . Imagine having to search through this. The “Rubik’s cube database” is over times larger. This number of cube positions is a very big number. This is what Tom is trying to search through.

I do not recall who gave me the cube, but I do remember quite clearly trying to solve it, and being surprised at how difficult it was. For months I tried to solve it, on and off, and just could not restore it; I could get two layers, but the last layer was just too difficult. Finally, I started keeping a notebook on the cube, and looked for some sequences (algorithms, I now know they are called) that would affect only a small portion of the cube, leaving the rest alone. At one point I had all the algorithms I needed except the one that permuted three corners. With a bit more work I finally figured out those pesky corners, and had a full solution. It took me about six months from originally getting the cube until this point! I did top corners first, then bottom corners, then top and bottom edges, and finally middle edges.

– Tom Rokicki

Since the late 1970’s, mathematicians and computer scientists have been wondering how many moves do you need to make to solve the Rubik’s cube, in the worst case scenario. There are two ways to measure the number of moves you make while manipulating the cube. One is called the quarter-turn metric. In this measurement, each quarter turn of any face of the cube, whether clockwise or counterclockwise, is called one move. The other is the face-turn metric. In this measurement, each turn of any face of the cube, whether by or or in either direction, is called one move. The use of the word “metric” is designed to suggest distance. How far from the solved position of the cube can you get? Starting from the solved position, how many moves would you have to make to scramble the cube into a position which is further from that solved position than any other? The answer depends on which metric you use. The exact answer is known as God’s number in the face-turn metric (resp., in the quarter-turn metric, if you prefer that measurement).

The determination of God’s number was the Mount Everest of mathematical questions
connected with the Rubik’s cube. With over possible positions, one might think that God’s number could be very large.

Hearing loss

The human ear is a complicated organ. In rough terms, here is how the hair cells in the inner ear contribute to hearing. Sound is basically a vibration of the molecules of the air created by small differences in air pressure. Different sound frequencies create different pressure differences. Deep inside the ear, in an area called the cochlea, is a surface called the basilar membrane of the inner ear. In very rough terms, you can think of this surface as like your skin with hair on it. When it experiences a sound, the hair on it will vibrate. Remarkably, different frequencies will cause hair in different locations on this surface to vibrate. It is as though a high-pitched frequency would vibrate the hair on your legs and not your arms, but a low-pitched frequency would vibrate the hair on your arms and not your legs. This “frequency-to-place” mapping is the way the ear sorts out different frequencies, enabling our brain to process that sound. In a normal ear, high-frequency sounds are registered by the hair cells located at the shallower end of the cochlea, but low frequency sounds are registered by the hair cells further inside. When these hair cells vibrate, they create a tiny electrical impulse which the nerve cells in the basilar membrane pass to the brain. The brain interprets this activity to determine which sound frequency is being heard.

If you lack hair cells, then this process completely breaks down and you cannot distinguish frequencies. The most beautiful music is merely noise.

Tom’s hearing

As Michael Chorost explains in his book Rebuilt [Ch], some teenagers in the 1980s developed hearing problems due to the fact that, in the United States, there was a Rubella outbreak in the 1960s. One of the consequences of this virus
was that some pregnant women exposed to Rubella gave birth to babies who were more likely to gradually lose cochlear hair cells starting in the 1980s during their teenage years. However, other illnesses can cause hearing loss and the cause of Tom’s hearing problems is not known.

Tom graduated from Wolfe City High School in 1981, got a bachelors degree in electrical engineering from Texas A+M University in 1985, and a Ph.D. at Stanford University in Computer Science in 1993. While this was going on, Tom was becoming deaf. Here is how he describes it:

I am post-lingually progressively deafened. I started losing my hearing in high school (no cause is known), and in college it became a huge problem. A very good friend’s parents noticed how deaf I was and sprung for hearing aids for me (I was working my way through school at the time; no way I could afford them) and they helped a lot but school was still a challenge. Once I started working full-time I could afford more and better hearing aids, but as the aids got better my hearing got worse, until I reached a point that hearing aids weren’t really helping much at all.

Recent progress on God’s number

As long ago as the early 1980’s it was known that every position the cube could be solved in moves or less [C20]. Here is a table of progress since then.

For years, Tom Rokicki has been working on lowering the upper bound for the face turn metric of the Rubik’s cube. His main work (finished in March 2008) is described in [TR], using a mathematical field known as group theory and prodigious programming skills. In Tom’s own words:

In December of 2003 I decided to solve the “edges-with-centers” space (the entire space of Rubik’s cube, ignoring all the corners). I wrote all of the code in C++ using a new set of classes for representing positions, sequences, and symmetry. The program itself required only 1.3GB of RAM, and I posted the results to the Yahoo newsgroup speedsolving in January 2004. This was the largest such complete implicit graph search performed to date at that time, I believe, with 980 billion states (before symmetry and antisymmetry reductions).

In November of 2005, I got an email from Silviu Radu that he had used the “edges-with-­centers” results I had posted to lower the upper bound on God’s number in the quarter turn metric to 38. This email started a collaboration that, in the end, led to all the rest of the work. My debt to Silviu is profound.

Many others were also working on this problem, but Rokicki’s progress in early 2008 was so significant that Rubik’s cube aficiadados started to think Rokicki was about to make a first ascent on their own Mount Everest. In fact, it was soon afterwards that Sony’s John Welborn contacted Tom out of the blue and offered CPU time on the “farm” of computers which Sony Imageworks uses to render animated movies, such as “Spiderman 3.” As a result of this generous offer by Sony, Tom was able to extend the same method used in the -move upper bound to show, in the face turn metric, every position can be solved in moves.

Then Google called. They donated time on a supercomputer to rule out the cases . This meant God’s numbr was . On the other hand, the “superflip” position is known to take face moves exactly (Michael Reid established this in 1995), so is best possible. In other words, God’s number in the face turn algorithm is . What Tom did was great but, with a little help from some friends, an amazing milestone was achieved.

Cochlear implants

What a cochlear implant tries to do is generate tiny electrical impulses in the nerve cells of the basilar membrane by attaching small electrical wires to different locations where hair cells should be. Even though the cochlear implant is very small, it cannot match mother nature. In a normal human ear, there are about hair cells. There is no way to surgically implant electrical nodes in the small area of the human skull where the inner ear is located. However, even 25 electrodes, which is the current state of the art, can transform a deaf person’s life from noise (or silence) to meaningful sound. The implanted electrodes get “mapped” or “programmed” to nerve cells of the basilar membrane by an audiologist working closely with the patient. For some patients, the process of installing and mapping a functioning “bionic ear” goes fairly smoothly. For others, it can be a very frustrating experience.

How does the cochlear implant distinguish the frequencies which are then passed to the implanted electrodes? Sound waves can be “decomposed” into more basics sounds called fundamental harmonics. As a rough analogy, think of the sound from a piano chord, which can be decomposed into the sounds of its individual keys. Each of the individual piano keys makes a more fundamental, pure sound. Play them simultaneously, as you do when playing a piano chord, and you get a more complicated sound. Now, try to reverse this process. Listen to the sound of a complicated chord. How do you tell what the individual notes are? Assuming you are not a musician who knows the chords by heart, this question of decomposing a chord into individual key notes is a complicated one. Abstractly, the process of decomposing sound into fundamental harmonics uses the mathematics of Fourier analysis, a method physicists and mathematicians have known since the 1800s. However, mathematics and engineering are not the same. Implementing these procedures in a tiny hardware device which is small enough to allow it to be surgically implanted in your skull behind your ear is still a very difficult, but actively researched, problem. Many engineers and scientists are developing new techniques, with improvements in hearing devices being discovered every year.

At some point Tom’s hearing got so bad that hearing aids no longer helped. Here is how Tom described what happened next.

I went in, and they said I might be a candidate for cochlear implants; I got implanted, and now I am hearing so much better! (If not normally.) It is hard to put into words how much better I hear now; it is like someone turned on the lights after I had spent years stumbling in the dark. Absolutely and truly a miracle in my life.

Tom Rokicki had his first surgery for a cochlear left-side implant in March 2008, just before he published his move upper bound for God’s number, in the face-turn metric. His surgery in March 2011, about 8 months after establishing the move result, was for the right side. It was so successful, that he listens to audio books in the car on the way to work in the morning. As Tom says, miraculous.

Today

The question remains – how many moves do you need to make to solve the Rubik’s cube in the worst case scenario, in the quarter turn metric? In this case, there is a position which is known to require quarter turn moves, namely, the “superflip with 4 spot” position (the position of the Rubik’s cube where the corners are correct, and all edges are correctly placed but “flipped,” and 4 of the 6 corners are permuted) also established in 1995 by Michael Reid. In the quarter turn metric, the answer is unknown at this time.

Will the improvements in implants ever make Tom’s hearing as good as a normal person? Time will tell.

[B] Brian Boyd, On the Origin of Stories: Evolution, Cognition, an Fiction, Harvard Univ. Press, Cambridge MA, 2009.

[C20] Cube 20 website http://cube20.org/

[Ch] Michael Chorost, Rebuilt: My Journey Back to the Hearing World, Mariner Books, 2006

[F] Article on large databases:
http://www.focus.com/fyi/10-largest-databases-in-the-world/

[J] David Joyner, Adventures in Group Theory, 2nd ed., Johns Hopkins Univ. Press, 2008.

[TR] Tomas Rokicki’s website http://tomas.rokicki.com/

[T] Bernard Becker Medical Library, Washington University School of Medicine, Timeline of Hearing Devices and Early Deaf Education,
http://beckerexhibits.wustl.edu/did/timeline/

[W] Wikipedia article on Cochlear implants:
http://en.wikipedia.org/wiki/Cochlear_implant#History

[W2] Wikipedia articles on the Rubik’s cube:
http://en.wikipedia.org/wiki/Rubiks_Cube
http://en.wikipedia.org/wiki/Gods_algorithm
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubiks_Cube

Many thanks to Tom Rokicki for his many very helpful correspondences!