Complements in the symmetric group

Posted on 2016/07/26 by wdjoyner

About 20 years ago I was asked a question of Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$ , respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$ . Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is,
as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a “ $k$ -tuple of complementary subgroups” (defined below) for which the answer to the analogous question is ”yes.”

This post is a very short summary of a paper I wrote (still unpublished) which can be downloaded here.

Complements in the symmetric group

Posted on 2014/04/12 by wdjoyner

Almost 20 years ago I was asked a question by Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$ , respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$ . Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is, as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a ” $k$ -tuple of complementary subgroups” for which the answer to the analogous question is ”yes.”

This post is a very short summary of part of a paper I wrote (still unpublished) which can be downloaded here. This post explains the ”no” part of the answer. For the more technical ”yes” part of the answer, see the more complete pdf version.

Notation: If $X$ is any finite set then

$|X|$ denotes the number of elements in $X$ .
$S_X$ denotes the symmetric group on $X$ .
$S_n$ denotes the symmetric group on $\{1,2,...,n\}$ .
$A_n$ denotes its alternating subgroup of even permutations.
$C_n$ denotes the cyclic subgroup of $S_n$ generated by the $n$ -cycle $(1,2,...,n)$ .
$M_{10}$ denotes ”the Mathieu group of degree $10$” and order $720=10!/7!$, which we define as the subgroup of $S_{10}$ generated by $(2,6,10,7)(3,9,4,5)$ and $(1,5)(3,8)(4,10)(7,9)$ .
$M_{11}$ denotes the Mathieu group of degree $11$ and order $7920=11!/7!$ generated by $(1,2,3,4,5,6,7,8,9,10,11)$ and $(3,7,11,8)(4,10,5,6)$ .
$M_{12}$ denotes the Mathieu group of degree $12$ and order $95040=12!/7!$ generated by $(2,3,5,9,8,10,6,11,4,7,12)$ and $(1,12)(2,11)(3,10)(4,9)(5,8)(6,7)$ .
For any prime power $q$ , ${\Bbb F}_q$ denotes the finite field with $q$ elements.
$AGL_n({{\Bbb F}}_q)$ denotes the affine group of transformations on ${\Bbb F}_q^n$ of the form $\vec{v}\longmapsto A\vec{v}+\vec{a}$ , where $A\in GL_n({{\Bbb F}}_q)$ and $\vec{a} \in {\Bbb F}_q^n$ .

If $G$ is a finite group and $G_1,G_2$ are subgroups then we say $G_2$ is the complement of $G_1$ when

$G_1\cap G_2=\{1\}$ , the identity of $G$ ,
and
$G=G_1\cdot G_2=\{g_1g_2\ |\ g_1\in G_1,\ g_2\in G_2\}$ .

Let $X$ denote a finite set. If $G$ is a subgroup of $S_X$ and $x\in X$ then we let $G_x$ denote the stabilizer of $x$ in $G$ :
$G_x=\{ g\in G\ |\ g(x)=x\}.$

Let $G$ be a permutation group acting on a finite set $X$ (so $G$ is a subgroup of the symmetric
group of $X$ , $S_X$ ). Let $k\geq 1$ be an integer and let
$X^{(k)}=\{{\rm distinct\ }k{\rm -tuples\ in\ }X\} =\{(x_1,x_2,...,x_k)\ |\ x_i\not= x_j,\ 1\leq i \textless j\leq k\}.$
We say $G$ acts $k$ -transitively on $X$ if $G$ acts transitively on $X^{(k)}$ via the ”diagonal” action
$g:(x_1,x_2,...,x_k)\longmapsto (g(x_1),g(x_2),...,g(x_k)).$

If $G$ acts transitively on $X$ and $G_x=1$ for some (hence all) $x\in X$ then we say $G$ acts regularly on $X$ . If $G$ acts $k$ -transitively on $X$ and acts regularly on $X^{(k)}$ then we say $G$ acts sharply $k$ -transitively on $X$ .

The classification of $k$ -transitive groups, for $k\geq 4$ , is to Jordan: A sharply $k$ -transitive group, $k\geq 4$ , must be one of the following.

$k \geq 6$ : $S_k$ , $S_{k+1}$ and $A_{k+2}$ only.
$k = 5$ : $S_5$ , $S_6$ , $A_7$ and the Mathieu group $M_{12}$ .
$k = 4$ : $S_4$ , $S_5$ , $A_6$ and the Mathieu group $M_{11}$ .

We give a table which indicates, for small values of $n$ , which $S_m$ have a complement in $S_n$ .

$n$	$m$	complement of $S_m$ in $S_n$
$4$	$2$	$A_4$
$4$	$3$	$C_4$
$5$	$2$	$A_5$
$5$	$3$	$\langle (1,2,3,4,5),(2,3,5,4)\rangle \cong AGL_1({{\Bbb F}}_5)$
		size $20$
$5$	$4$	$C_5$
$6$	$2$	$A_6$
$6$	$3$	$\langle (2,3,4,5,6),(3,4,6,5)\rangle \cong PGL_2({{\Bbb F}}_5)$
		size $120$
$6$	$5$	$C_6$
$7$	$2$	$A_7$
$7$	$5$	$\langle (1,2,6,5,3,7),(1,4,3,2,5,6)\rangle \cong AGL_1({{\Bbb F}}_7)$
		size $42$
$7$	$6$	$C_7$
$8$	$2$	$A_8$
$8$	$5$	$\langle (1,5,8,6,7,4),(1,5,8,7)(2,3,4,6)\rangle \cong PGL_2({{\Bbb F}}_7)$
		size $336$
$8$	$6$	$AGL_1({{\Bbb F}}_8)$
		size $56$
$8$	$7$	$C_8$
$9$	$2$	$A_9$
$9$	$6$	$PGL_2({{\Bbb F}}_8)$
		size $504$
$9$	$7$	$AGL_1({{\Bbb F}}_9)$
		size $72$
$9$	$8$	$C_9$
$10$	$2$	$A_{10}$
$10$	$7$	$M_{10}$
		size $720$
		( $PGL_2({{\Bbb F}}_9)$ is another)
$10$	$9$	$C_{10}$
$11$	$2$	$A_{11}$
$11$	$7$	$M_{11}$
		size $7920$
$11$	$9$	$AGL_1({{\Bbb F}}_{11})$
		size $110$
$11$	$10$	$C_{11}$
$12$	$2$	$A_{12}$
$12$	$7$	$M_{12}$
		size $95040$
$12$	$9$	$PGL_2({{\Bbb F}}_{11})$
		$=\langle (1,2,3,4,5,6,7,8,9,10,11), (1,2,4,8,5,10,9,7,3,6),$
		$(1,10)(2,5)(3,7)(4,8)(6,9)(11,12)\rangle$
		size $1320$
$12$	$11$	$C_{12}$

Proposition: $S_m$ has a complement in $S_n$ if and only if there is an subgroup $H$ of $S_n$ such that

$H$ acts $(n-m)$ -transitively on $\{1,2,...,n\}$ ,
$|H|=n(n-1)...(m+1)=n!/m!$ .

Example: $S_{10}$ has not one but two non-isomorphic subgroups, $M_{10}$ and $PGL_2({{\Bbb F}}_9)$ , of order $720=10!/7!$ , each of which acts $3$ -transitively on $\{1,2,...,10\}$ . Thus $S_7$ has two non-isomorphic complements in $S_{10}$ .

The statement below is the main result.

Theorem: The following statements hold.

If $n>2$ is not a prime power or a prime power plus $1$ then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ and $m=n-1$ .
If $n>12$ is a prime power and not a prime power plus $1$ then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ , $m=n-2$ and $m=n-1$ .
If $n>12$ is a prime power plus $1$ but not a prime power then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ , $m=n-3$ and $m=n-1$ .
If $n>12$ is both a prime power plus $1$ and a prime power then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ , $m=n-3$ , $m=n-2$ and $m=n-1$ .
If $n\leq 12$ , see the above table.

The man who found God’s number

Posted on 2012/07/06 by wdjoyner

(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 $90^o$ or $180^o$ or $270^o$ , 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 $N$ of different positions that the cube could be scrambled is

$N = 8!\cdot 12!\cdot 2^{10}3^7=43252003274489856000 \cong 4.3\times 10^{19},$
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 $100000=10^4$ straws in a haystack. In other words, finding a needle in a haystack is $10^{14}$ (“ten thousand billion”) times easier. How does it compare to the gross domestic product of the United States economy? This number $N$ 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 $N$ . 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 $6$ petabytes, or $6\times 10^{15}$ . Imagine having to search through this. The “Rubik’s cube database” is over $1000$ 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 $90^o$ or $180^o$ or $270^o$ 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 $4.3\times 10^{19}$ 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 $52$ moves or less [C20]. Here is a table of progress since then.

	Lower	Upper
Date	bound	bound	Notes and Links
July, 1981	18	52	Morwen Thistlethwaite
Dec., 1990	18	42	Hans Kloosterman
May, 1992	18	39	Michael Reid
May, 1992	18	37	Dik Winter (just one day later!)
Jan., 1995	18	29	Reid (analyzing
			Kociemba’s two-phase algorithm).
Jan., 1995	20	29	Reid: the “superflip” position
			(This is the position of the Rubik’s cube where the centers and corners are correct, and all edges are correctly placed but “flipped.”) requires 20 moves.
April, 2006	20	27	Silviu Radu
May, 2007	20	26	Dan Kunkle and Gene Cooperman
March, 2008	20	25	Tomas Rokicki
Aug., 2008	20	22	Rokicki and John Welborn
July, 2010	20	20	Rokicki, Herbert Kociemba, Morley Davidson,
			and John Dethridge determine God’s number!

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 $25$ -move upper bound to show, in the face turn metric, every position can be solved in $\leq 22$ moves.

Then Google called. They donated time on a supercomputer to rule out the cases $N=21,22$ . This meant God’s numbr was $\leq 20$ . On the other hand, the “superflip” position is known to take $20$ face moves exactly (Michael Reid established this in 1995), so $20$ is best possible. In other words, God’s number in the face turn algorithm is $20$ . 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 $20000$ hair cells. There is no way to surgically implant $20000$ 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 $25$ move upper bound for God’s number, in the face-turn metric. His surgery in March 2011, about 8 months after establishing the $20$ 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 $26$ 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!

God’s number for the Rubik’s cube in the face turn metric

Posted on 2010/08/29 by wdjoyner

This is an update to the older post.

The story is described well at cube20.org but the bottom line is that Tom Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge have established that every cube position can be solved in 20 face moves or less. The superflip is known to take 20 moves exactly (in 1995, Michael Reid established this), so 20 is best possible – or God’s number in the face turn algorithm. Google (and, earlier, Sony) contributed computer resources to do the needed massive computations. Congradulations to everyone who worked on this!

This would make a great documentary I think!

new Rubik’s cube bound of Tom Rokicki

Posted on 2008/09/10 by wdjoyner

For some time, Tom Rokicki has been working on lowing the upper bound for the face-turn metric of the Rubik’s cube. His main work (finished in Feb or March 2008) is described in http://tomas.rokicki.com/rubik25.pdf. More recently, John Welborn came up out of the blue and offered Tom CPU time on the “farm” of computers which Sony Imageworks uses to render animated movies. As a result of this generous offer, Tom was able to extend the same method used in the 25-move upper bound to show: in the face turn metric, every position can be solved in <=N moves, where N=20,21,22 (which one, we don’t know yet).

Recently, New Scientist ran a short article on Tom’s result. Here is the link, though the full article requires a subscription: http://www.newscientist.com/channel/fundamentals/mg19926681.800-cracking-the-hardest-mystery-of-the-rubiks-cube.html .

Please see Herbert Kociemba’s cube
performance page for more info.

Yet Another Mathblog

Tag Archives: Rubik’s cube

Complements in the symmetric group

Complements in the symmetric group

God’s number for the Rubik’s cube in the face turn metric

new Rubik’s cube bound of Tom Rokicki