Keeler’s Theorem (Futurama Theorem) and Products of Distinct Transpositions

In the television show Futurama, episode “The Prisoner of Benda,” Dr. Farnsworth created a machine that swaps the minds of two individuals. Unfortunately, they discover that the machine cannot be used on the same pair of bodies again.

The question is, given a collection of jumbled up minds and bodies, how can you get them all back to normal? Well, they have to come up with some equation to prove that, with enough people switching, eventually everyone will end up in their rightful form.

It was first mentioned in an interview that head writer and executive producer David X. Cohen gave to the American Physical Society:

“In an APS News exclusive, Cohen reveals for the first time that in the 10th episode of the upcoming season, tentatively entitled “The Prisoner of Benda,” a theorem based on group theory was specifically written (and proven!) by staffer/PhD mathematician Ken Keeler to explain a plot twist. Cohen can’t help but chuckle at the irony: his television-writing rule is that entertainment trumps science, but in this special case, a mathematical theorem was penned for the sake of entertainment.”

This theorem is now known as Keeler’s Theorem, or the “Futurama Theorem”.

The Futurama Theorem proves that no matter the size of the collection or how many mind swaps have been made, all minds can be restored to their original bodies using only two extra “clean” bodies (individuals who haven’t swapped minds with anyone) are needed, since a collection of just two people with swapped minds could never get back to normal.

If you want to know more about the details on group theory (group, the symmetric group, permutation diagrams, transpositions, cycle notation, products of disjoint cycles, products of distinct transpositions, etc.) read the talk given by Dana C. Ernst about the Futurama Theorem. He has blogged twice on this talk:
1. Talk about the Futurama Theorem
2. Another talk about the Futurama Theorem

and he has given the talk three times:
1. November 3, 2011 Gordon Talk
2. December 7, 2011 PSU Talk
3. February 28, 2012 UNO Talk

I personally like the first talk. He mentions:

“The slides for the second talk are very similar to the first set, but there are a few differences:

• The second talk is shorter. I trimmed a few things from the first talk that were not completely necessary.
• I’ve improved the wording in a few spots.
• In the second talk, multiplication of permutations is right to left.”

Talks 2 and 3 are almost identical.

If you read the talk, you will understand the proof that appeared in the show,

which uses nothing other than basic facts about group theory and permutations. Furthermore, you will understand applying the algorithm to the arrangement of minds in Futurama requires 13 moves. However, since Fry and Zoiberg only swapped with each other and since there is only one other cycle, we could use Fry and Zoiberg as and , respectively in the algorithm and thus it only requires 9 moves.

Below are the implementations of the 13 move algorithm in Sage and WolframAlpha. (Note, Sage and WolframAlpha will multiply cycles left to right):

S_11 = SymmetricGroup(11)
c7 = S_11("(1,2,3,4,5,6,7)")
c1 = S_11("(8,9)")
t1 = S_11("(8,10)")
t2 = S_11("(9,11)")
t3 = S_11("(9,10)")
t4 = S_11("(8,11)")
t5 = S_11("(10,1)")
t6 = S_11("(11,7)")
t7 = S_11("(11,6)")
t8 = S_11("(11,5)")
t9 = S_11("(11,4)")
t10 = S_11("(11,3)")
t11 = S_11("(11,2)")
t12 = S_11("(11,1)")
t13 = S_11("(10,7)")

c1*t1*t2*t3*t4*c7*t5*t6*t7*t8*t9*t10*t11*t12*t13


Click here to view the Futurama permutation in WolframAlpha

Click here to view the 13 move algorithm for the Futurama permutation solution in WolframAlpha

Here are some questions posed by Dana C. Ernst:
1. Can we do better (i.e., fewer moves to fix the cycles)?
2. Under what circumstances do we not need to introduce two “clean” people?
3. Would only using one “clean” person ever be useful?
4. Could you use fewer moves if you allowed more than two “clean” people?

We now know the answer to some these questions. Students from the University of California, San Diego have improved the result, giving a better algorithm for finding the minimum number of switches to put everyone’s head back in the right places, give optimal solutions for two particular situations, and give necessary and sufficient conditions for it being possible to represent the identity permutation as distinct transpositions in .

Here is the paper submitted on April 26, 2012.