arXiv:1608.04809v1 [math.GR] 16 Aug 2016

GENERALIZING THE FUTURAMA THEOREM
J. ELDER AND O. VEGA
Abstract. The 2010 episode of Futurama titled The Prisoner of Benda centers around a machine that swaps the brains of any two people who use it.
The problem is, once two people use the machine to swap brains with each
other, they cannot swap back.
In this article, we present a new proof of this theorem and also a generalization of it to what would happen if, instead, the machine swapped cyclically
the brains of p characters, where p is prime.

1. Introduction
In the 2010 Writers Guild Award-winning episode of Futurama, The Prisoner of
Benda [5], Professor Farnsworth and Amy build a machine that can swap the brains
of any two people. The two use the machine to swap brains with each other, but
then discover that once two people have swapped with each other, the machine does
not swap them back. More characters get involved until the group is thoroughly
mixed up, and they start looking for ways to return to their own heads.
Clearly, the problem of undoing what the machine has done may be studied using
permutations; each brain swap can be described by a transposition in Sn , where
n is the number of characters involved in the brain-swapping. Hence, the problem
consists in writing the inverse of a permutation as a product of transpositions that
(1) are all distinct, and (2) were not already used in constructing the original
permutation.
The solution given in the episode relies on involving two additional people; these
two characters were not involved in any of the original swaps, and so have no
restrictions on who they can swap with now. For example, using the additional
people x and y, we have
(1 2)−1 = (x y)(2 x)(1 y)(2 y)(1 x)
Note that the transpositions used in the product above are all distinct, and that
none of them is an element of S2 , which is where the original element (1 2) was
taken from. This can be done in general for any permutation, and leads to the
following theorem.
Theorem 1 (Keeler, 2010). Let n ∈ N, n ≥ 2. The inverse of any permutation in
Sn can be written as a product of distinct transpositions in Sn+2 \ Sn .
2010 Mathematics Subject Classification. Primary 20B30; Secondary 20F05.
Key words and phrases. Permutations, products of cycles, Futurama.
The first author thanks the support of the Division of Graduate Studies at California State
University, Fresno in the form of the Robert & Norma Craig Graduate Scholarship and also for
travel support. She would also like to thank the College of Science and Mathematics at California
State University, Fresno for travel support.
1

Although Ken Keeler (writer and executive producer for Futurama at the time)
never published the proof of his theorem, the proof given in the episode as well as a
write up of the idea may be found in [3]. This was, most probably, the first time in
which a theorem was proved for the purpose to advance the narrative of a TV show,
and thus it was all over the internet [1, 4, 7] and was also mentioned in books, such
as Simon Singh’s The Simpsons and Their Mathematical Secrets [6]. Of course,
this aroused the interest of mathematicians (the authors of this article included),
and so in 2014, Evans, Huang, and Nguyen [2] proved that Keeler’s solution to the
problem is optimal in the sense that it uses the minimal number of cycles and the
minimal number of additional elements. In that article, they also gave necessary
and sufficient conditions on m and n for the identity permutation to be expressible
as a product of m distinct transpositions in Sn .
Although in the title of this article we used The Futurama Theorem, for the
remainder of this work we will refer to Theorem 1 as Keller’s Theorem.
2. Reproving Keeler’s Theorem
We want to reprove Keeler’s Theorem using a different, and possibly less optimal,
method. The goal is to present a method that can be generalized to larger cycles
in Sn . As in Keeler’s proof, we will need additional elements that could not have
been used in the permutation we wish to work with.
As expected, we will first study how to write the inverse of a cycle using ‘new’
transpositions to later putting all this together using that every permutation can
be written as the product of disjoint cycles.
Definition 2. Fix n ∈ N and let x, y ∈ N be such that x, y ≫ n. We consider the
set that we will use to define the elements of Sn+2 to be {1, 2, . . . , n, x, y}.
Throughout this paper, we will consider, without loss of generality, the k-cycle
(1 2 · · · k) instead of a generic k-cycle. We start by setting some notation.
Definition 3. Let m ∈ N such that m is odd and m ≤ n − 2. And let δm ∈ Sn+2
be defined as
m
Y
(i + 1 y)(i + 2 y)(i x)(i + 1 x).
δm =
i=1
i odd

Notice that δm , for any 1 ≤ m, will not contain any repeated transpositions. In
fact, every number 1 ≤ j ≤ m will appear at most twice in the product: once in
(j x) and once in (j y). Also, we can see that (x y) is not in the product.
Lemma 4. Let k ≥ 7 be odd and such that k ≡ 1 (mod 3). If σ is a k-cycle then
σ −1 = δk−2 .
Proof. We write k = 1 + 6t, for t ∈ N. We will prove the result by induction on t.
For t = 1, we get:
(1 2 3 4 5 6 7)−1 = (6 9)(7 9)(5 8)(6 8)(4 9)(5 9)(3 8)(4 8)(2 9)(3 9)(1 8)(2 8) = δ5
We now assume the result for all k-cycles, where k = 1 + 6s and s < t. Now let
σ be a j-cycle, where j = 1 + 6t. We let k = j − 6 and write
(2.1)

(1 2 · · · j)−1 = (j − 6 j − 5 j − 4 j − 3 j − 2 j − 1 j)−1 (1 2 · · · k)−1

From the induction hypothesis, we get
(1 2 · · · k)−1 = δj−8 ,
2

and from the base case we get
(j − 6 j − 5 j − 4 j − 3 j − 2 j − 1 j)−1 =

j−2
Y

(i + 1 y)(i + 2 y)(i x)(i + 1 x).

i=j−6
i odd

Putting all this together in Equation (2.1) yields:


j−2
Y
(1 2 · · · j)−1 = 
(i + 1 y)(i + 2 y)(i x)(i + 1 x) δj−8 = δj−2 ,
i=j−6
i odd

which is what we wanted to obtain.



We will use this lemma to prove all remaining cases. First for k odd.
Lemma 5. Let k be an odd number and σ be a k-cycle.
1. If k ≥ 5 and k ≡ 2 (mod 3), then σ −1 = (x y)(k − 2 x)(k − 1 x)(k x)δk−4 .
2. If k ≥ 3 and k ≡ 0 (mod 3), then σ −1 = (x y)(k x)δk−2 .
Proof. Let k be an odd number and σ be a k-cycle.
1. For k = 5, we see that
(1 2 3 4 5)−1 = (6 7)(3 6)(4 6)(5 6)(2 7)(3 7)(1 6)(2 6)
For k > 5 and k ≡ 2 (mod 3), we write
(1 2 . . . k) = (1 2 . . . k − 4)(k − 4 k − 3 k − 2 k − 1 k)
Since k − 4 is odd and k − 4 ≡ 1 (mod 3) we use Lemma 4 to get the
desired result.
2. For k = 3, we have
(1 2 3)−1 = (4 5)(3 4)(2 5)(3 5)(1 4)(2 4),
and when k > 3 and k ≡ 0 (mod 3), we know that k − 2 ≡ 1 (mod 3), with
k − 2 odd. Hence
(1 2 . . . k) = (1 2 . . . k − 2)(k − 2 k − 1 k).
At this point we use Lemma 4 to get the desired result.



Now we will proceed in a similar manner for the cases where k is even.
Lemma
1. If
2. If
3. If

6. Let k be a positive even number, and σ be a k-cycle.
k ≥ 6 and k ≡ 0 (mod 3), then σ −1 = (k y)(k − 1 x)(k x)δk−3 .
k ≥ 4 and k ≡ 1 (mod 3), then σ −1 = (x y)(k − 1 x)(k x)δk−3 .
k ≥ 8 and k ≡ 2 (mod 3), then
σ −1 = (k − 2 y)(k − 1 y)(k y)(k − 3 x)(k − 2 x)δk−5 .

Proof. Let k be even, and σ be a k-cycle.
1. For k = 6, we see that
(1 2 3 4 5 6)−1 = (6 8)(5 7)(6 7)(4 8)(5 8)(3 7)(4 7)(2 8)(3 8)(1 7)(2 7)
For k > 6, and k ≡ 0 (mod 3), we write
(1 2 . . . k) = (1 2 . . . k − 5)(k − 5 k − 4 k − 3 k − 2 k − 1 k)
Since k − 5 is odd and k − 5 ≡ 1 (mod 3) we can use Lemma 4 to get the
desired result
3

2. For k = 4, we have
(1 2 3 4)−1 = (5 6)(3 5)(4 5)(2 6)(3 6)(1 5)(2 5)
and when k > 4 and k ≡ 1 (mod 3), we know that k − 3 ≡ 1 (mod 3),
k − 4 is odd. Hence
(1 2 . . . k) = (1 2 . . . k − 3)(k − 3 k − 2 k − 1 k)
At this point we use Lemma 4 to get the desired result.
3. For k = 8,
σ −1 = (6 y)(7 y)(k y)(5 x)(6 x)δ3
When k > 8 and k ≡ 2 (mod 3), we write
(1 2 . . . k) = (1 2 . . . k − 7)(k − 7 . . . k − 1 k)
Since k − 7 ≡ 1 (mod 3), we use Lemma 4 to get the desired result.



Remark 7. Lemmas 4, 5, and 6 allow us to write any given k-cycle as a product
of transpositions. Moreover, such products consist of transpositions that are all
distinct from each other, and each one of these 2-cycles is an element in Sn+2 \ Sn .
Finally, given a permutation σ ∈ Sn , we write its inverse as a product of disjoint
cycles, σ −1 = σ1 σ2 · · · σr , and then we write each σi as a product of transpositions
in Sn+2 \ Sn using Lemmas 4, 5, and 6. It is easy to see that the only transposition
that could appear more than once in this product is (x y). In this case, each (x y)
would appear at the beginning of a product representing a σi (see Lemmas 5 and
6), but this situation is easy to fix as if τ is a permutation in Sn+2 \ Sn then the
conjugation (x y)τ (x y) yields a permutation that is equal to τ where all the xs
and the ys have been exchanged. Keeler’s Theorem follows.
3. Products of larger cycles
Now we are interested in learning what would happen if Professor Farnsworth
and Amy had created a machine that swapped several brains in a cyclical way. For
example, the machine would do
Professor −→ Amy −→ Bender −→ Leela −→ Fry −→ Professor
The problem of undoing what the machine does in the example above would be
easy if the machine did not have any ‘issues’ and worked even when a set of five
people sat in the machine for a second time; we could use that (1 2 3 4 5)−1 =
(5 4 3 2 1) or that (1 2 3 4 5)−1 = (1 2 3 4 5)4 to solve the problem. That
would be too easy, there would be no TV network that would broadcast an episode
featuring such a simple problem/solution (the existence of the show Scooby-Doo
may go against this premise). Hence, to make this interesting, we will assume that
the machine does not always work when a set of people who have already sat in the
machine sits in it again. Our restriction will be technical, and so we will phrase it
explicitly in the statement of our results.
So, for the rest of this article, we will assume that we are working with a machine
that swaps cyclically the brains of p people at a time, where p is an odd prime.
Note that now, in terms of permutations, our problem will reside in An , as the
brain-swapping machine yields an odd cycle every time it functions.
We will start our study with what will end up being a special case: p = 3.
4

Products of 3-cycles. It turns out that, in this case, we only need one extra
character to undo the mess created by the machine.
Lemma 8. Let n ∈ N, n > 2, and let σ ∈ An be an odd cycle. Then, σ −1 can be
written as a product of 3-cycles
σ −1 = τ1 τ2 · · · τt
where τi ∈ An+1 \ An , for all i = 1, 2, . . . , t, and τi ∈<
/ τj >, for all i 6= j.
Proof. For k = 3 we get (1 2 3) = (x 3 1)(x 1 2), and for every 3 > k ≤ n, k odd,
and x ≫ n, consider the product
(1 2 · · · k − 1 k) = (x k 1)(x k − 2 k − 1) · · · (x 3 4)(x 1 2).
The result is now immediate, as the inverse of any odd cycle is also an odd cycle,
and the 3-cycles used in the products considered all fix different sets of elements. 
Lemma 9. Let α, β ∈ Sn , n > 2, be two disjoint even cycles. Then, (αβ)−1 can
be written as a product of 3-cycles
(αβ)−1 = τ1 τ2 · · · τt ,
where τi ∈ An+1 \ An , for all i = 1, 2, . . . , t, and τi ∈<
/ τj >, for all i 6= j.
Proof. Let β −1 = (a1 a2 · · · ar ) and α−1 = (b1 b2 · · · bs ) be two disjoint cycles,
where r and s are even. Note that (αβ)−1 = β −1 α−1 ∈ An can be written as
β −1 α−1 = (a1 a2 )(b1 b2 ) (a2 a3 · · · ar )(b2 b3 · · · bs )
= (b2 b1 x)(b1 a2 x)(a2 a1 x)(a1 b1 x) (a2 a3 · · · ar )(b2 b3 · · · bs ).
Note that the last two cycles in the product are odd, and thus we can write them
as a product of 3-cycles, as indicated in Lemma 8. It is easy to see now that (αβ)−1
can be written as claimed.

The previous two lemmas indicate that we should only need one extra person to
undo whatever chaos the 3-brain-swapping machine might have created. We make
this result explicit in the following theorem.
Theorem 10. Let σ ∈ An , n > 2. Then, σ −1 can be written as a product of 3-cycles
σ −1 = τ1 τ2 · · · τt ,
where τi ∈ An+1 \ An , for all i = 1, 2, . . . , t, and τi ∈<
/ τj >, for all i 6= j.
Proof. Given σ ∈ An , we know we can write σ −1 as a product of disjoint cycles.
Moreover, after rearrangement (if needed) we can put all the appearing even cycles
(if any) in pairs. Hence, Lemmas 8 and 9 guarantee the desired factorization of
σ −1 .

Products of p-cycles, p > 5. In order to give an answer to what would happen if
the machine now swapped p brains cyclically, where p is a prime larger than three,
we need to set some notation first.
Fix n, p ∈ N, where p > 3 is prime and n > 2. Then, we define the following
ordered lists of numbers
[x]n,p = x1 x2 . . . xp−3
[x]−1
n,p = xp−3 . . . x2 x1
5

where xi ≫ n, for all i = 1, 2, . . . , p − 3. We will use these lists to write cycles. For
example (1 2 [x]3,7 ) = (1 2 x1 x2 x3 x4 ), where x1 , x2 , x3 , x4 ≫ 3.
Theorem 11. Let n ∈ N and p be a prime such that p > 3 and n > 2. If σ ∈ An ,
then, σ −1 can be written as a product of p-cycles
σ −1 = τ1 τ2 · · · τt ,
where τi ∈ An+(p−3) \ An , for all i = 1, 2, . . . , t, and τi ∈<
/ τj >, for all i 6= j.
Proof. We will first prove that every element σ ∈ An can be written as a product
of p-cycles, then we will prove that the factors used satisfy the conditions claimed
in the theorem.
We know that every element in An can be written as a product of odd cycles
and an even number of even cycles. We will first deal with odd cycles. For k = 3
we can write
(1 2 3) = (1 3 2 [x]−1
n,p )(2 1 3 [x]n,p ),
and so we need p − 3 new elements to write a 3-cycle as a product of p-cycles. For
k > 3 we know that every k-cycle in An can be written as a product of k−1
2 distinct
3-cycles as follows:
(3.1)

(a1 a2 · · · ak ) = (a1 a2 a3 )(a3 a4 a5 ) · · · (ak−2 ak−1 ak ).

So, if σ ∈ An is a k-cycle with k > 3, then we write it as in Equation (3.1). After
that we write each of the 3-cycles in that product as a product of two p-cycles, as
discussed in the case k = 3 above. Hence, we can write σ as a product of p-cycles
by incorporating p − 3 new elements.
For products of two even cycles we let σ = (a1 a2 · · · ar ) and τ = (b1 b2 · · · bs ),
where r and s are even. Note that στ ∈ An can be written as
στ = (a1 a2 )(b1 b2 ) (a2 a3 · · · ar )(b2 b3 · · · bs )
−1
= (b2 b1 a2 [x]n,p
)(a2 a1 b1 [x]n,p ) (a2 a3 · · · ar )(b2 b3 · · · bs )

where the first two cycles need p − 3 new elements to have length p, and all the
other cycles involved are odd, and thus can be written as products of p-cycles.
In order to see that all the p-cycles obtained in the final product describing σ −1
generate distinct subgroups of An+(p−3) we notice that, in the majority of the cases,
a pair of these p-cycles will not ‘move’ the same p elements, and thus the groups
they generate would intersect trivially. Thus, the only case that should be analyzed
is when we get two cycles of the form τ1 = (1 3 2 [x]−1
n,p ) and τ2 = (2 1 3 [x]n,p ).
In this case, if we assumed that these elements generate the same subgroups then
τ2i = τ1 , for some i. However, if we look at τ2i (2) we can see that the only possibility
for τ2i = τ1 to happen would be when i = p − 1, but it is easy to see that τ2p−1 =
τ2−1 6= τ1 . This finishes the proof.

We conclude that as long as the brain-swapping machine Professor Farnsworth
and Amy build swaps a prime number of brains cyclically, they can always fix the
chaos created by incorporating enough extra characters to the mix.
References
[1] Casey Chan, Futurama writer invented a new math theorem just to use in the show (2010)
http://gizmodo.com/5618502/futurama-writer-invented-a-new-math-theorem-just-to-use-in-the-show.
[2] Ron Evans, Lihua Huang, Tuan Nguyen, Keeler’s theorem and products of distinct transpositions, Amer. Math. Monthly 121 (2014) 136–144.
6

[3] Hristo Georgiev, The Futurama theorem explained. The Commutator 2 (2010) 18–20.
[4] Tony Phillips, Math in the Media, Amer. Math. Soc., Original math on Futurama (2010),
http://www.ams.org/news/math-in-the-media/10-2010-media.
[5] Previous Nominees & Winners of the Writers Guild Awards (last accessed on 08/15/16).
http://awards.wga.org/wga-awards/previous-nominees-winners.
[6] Simon Singh, The Simpsons and Their Mathematical Secrets. Bloomsbury, NY, 2013.
[7] The prisoner of Benda. The Infosphere, the Futurama Wiki (last accessed on 08/15/16).
http://theinfosphere.org/The_Prisoner_of_Benda.
Department of Mathematics. Arizona State University. Tempe, AZ 85287.
E-mail address: Jennifer.E.Elder@asu.edu
Department of Mathematics. California State University, Fresno.
93740.
E-mail address: ovega@csufresno.edu

7

Fresno, CA

