Transcript A,B

Cycles, Transpositions, and
Bob Gardner
ETSU Abstract Algebra Club Advisor
Spring 2015
Futurama is an animated series about a pizza delivery
boy, Philip J. Fry, who time-travels from New Year’s
Eve 1999 to New Year’s Eve 2999. The show follows
the underachieving Fry as he deals with talking
robots, one eyed mutants, and various space aliens.
The show aired from March 28, 1999 to September 4,
2013 on the Fox network (1999 to 2003) and Comedy
Central (2008 to 2013),for a total of 140 shows. The
show was created by Matt Groening, of The Simpsons
fame.
Futurama has always been big on math and science
related jokes. In fact, several of the writers have
undergraduate and graduate degrees in
mathematics, computer science, physics, and
chemistry.
Dr. Sarah Greenwald of Appalachian State
University has a webpage devoted to the
mathematical content of Futurama:
http://mathsci.appstate.edu/~sjg/futurama/
Writer Ken Keeler has a Ph.D. in applied math from Harvard
University. He wrote the script for “The Prisoner of Benda”
which first aired on Comedy Central on August 19, 2010.
The plot concerns a body switching machine which allows two
bodies to switch brains, but once a pair of bodies has
switched brains then the same pair of bodies cannot switch
again (due to the cerebral immune response). After several
uses of the machine, the posed-problem is to return the
brains to the correct bodies. Keeler proved a theorem about
permutation groups and it is used in the show.
The Regular Characters
Fry (F)
Amy (A)
Leela (L)
Hermes (H)
Zoiberg (Z)
Bender (B)
Professor Farnsworth (P)
Characters Relevant to “The Prisoner of Benda”
Emperor Nikolai (E)
Sweet Clyde (S)
Washbucket (W)
Bubblegum Tate (T)
1. Groups
2. Permutation Notation
3. Permutation Groups
4. Transpositions
5. The Inversion Theorem
Definition. A binary operation  on a set is a rule that
assigns to each ordered pair of elements of the set an
element of the set. The element associated with ordered
pair (a,b) is denoted a  b.
Example. Consider the set M2
of all 2 2 matrices. A binary
operation on M2 is matrix
multiplication. Notice that
this binary operation is not
commutative.
Leela (L)
Definition. A group is a set G together with a binary
operation  on G such that:
• The binary operation  is associative a  (b  c)  (a  b)  c,
• There is an element e in G such that a  e  e  a  a
for all a  G , and
• For each a  G there is an element a  G with the
property that a  a  a  a  e.
Note. Element e is called
the identity element of the
group and element a is
called the inverse of
element a.
Amy (A)
Example. Here is an example of a “multiplication
table” of a group with binary operation * and set
G={0,1,2,3,4}.
G={a,b,c,d,e}.
Professor
Farnsworth (P)
+
*
a
0
b
1
2c
d
3
4e
a
0
a
0
b
1
2c
3d
4e
b
1
b
1
2c
d
3
4e
a
0
2c
2c
d
3
4e
a
0
b
1
d
3
d
3
4e
0a
1b
2c
4e
4e
a
0
b
1
2c
d
3
Zoiberg (Z)
Definition. A permutation of a set A is a one-to-one
and onto function from set A to itself.
Example. If A={1,2,3,4,5}, then a
permutation is function s where:
s(1)=4, s(2)=2, s(3)=5, s(4)=3,
s(5)=1. This can be represented with
permutation notation as:
 1 2 3 4 5
.
s  
 4 2 5 3 1
Bender (B)
Example. Another permutation on set
A={1,2,3,4,5} is
1 2 3 4 5
.
  
3 5 4 2 1
We can multiply two permutations to get the
permutation product as follows:
 1 2 3 4 5  1 2 3 4 5 
s  


 4 2 5 3 1  3 5 4 2 1 
1 2 3 4 5
 
.
5 1 3 2 4
Fry (F)
Example. We can write the previous permutation as
a “product of cycles”:
1 2 3 4 5
s  
  (1,5,4,2 (3.
5 1 3 2 4
Theorem. Every permutation of
a finite set is a product of disjoint
cycles.
Hermes (H)
Example. When taking products of cycles, we read
from right to left:
1 2 3 4 5 6
( 2 , 1 , 5 ( 1 , 4 , 5 , 6   
.
4 1 3 2 6 5 
Amy (A)
Example. Consider the two permutations on {1,2,3}:
 1 2 3

  
 2 3 1
and
1 2 3
.
  
3 1 2
1
The product of these permutations is:
 1 2 3  1 2 3  1 2 3 

  
.
  
 2 3 1  3 1 2  1 2 3 
1
1
For this reason,  is called the inverse of  .
Bender (B)
Note. In fact, the permutations of a set form a
group where the binary operation is permutation
product.
Definition. The group of all permutations of a set
of size n is called the symmetric group on n letters,
denoted Sn.
Note. Two important subgroups of Sn are the
dihedral group Dn and the alternating group An.
Definition. A cycle of length two is a transposition.
Theorem. Any permutation of a finite set of at least two
elements is a product of transpositions.
Now, pause this video and watch “The Prisoner
of Benda.” This can be found on Netflix and
Amazon video on demand. Watch for the seven
main characters (Fry, Leela, Amy, Professor
Farnsworth, Zoiberg, Hermes, and Bender),
along with the other four characters:
Washbucket (W)
Emperor Nikolai (E)
Sweet Clyde (S)
Bubblegum Tate (T)
Note. We will represent a body switch with a
transposition. The first body switch is between the
Professor and Amy. We denote this as:
(P, A
or
P, A .
After the First Three Body Switches…
P
…the permutation is (P, L ( A, B (P, A  
B
A B L
.
L A P
Let’s explore some
permutations and their
inverses…
Suppose we start with this population…
YELLOW
RED
GREEN
BLUE
...and permute the red and blue disks:
YELLOW
RED
GREEN
BLUE
We can…
YELLOW
GREEN
(G,B)
(G,R)
(Y,R)
(Y,B)
RED
BLUE
Finally, we interchange Y and G
YELLOW
GREEN
(Y,G)
RED
BLUE
Suppose we start with this population…
YELLOW
RED
GREEN
BLUE
BLACK
Let’s mix things up to create a 3-cycle:
YELLOW
GREEN
(R,Bc)
(R,B)
RED
BLUE
BLACK
(RED,BLUE,BLACK)
Let’s mix things up to create a 3-cycle:
YELLOW
GREEN
(G,Bc)
(G,R)
(Y,G)
(Y,B)
(G,B)
(Y,R)
RED
BLUE
BLACK
In The Prisoner of Benda, the initial transpositions are:
Body 1
Body 2
Transposition
Professor
Amy
(P,A)
Amy
Bender
(A,B)
Professor
Leela
(P,L)
Amy
Washbucket
(A,W)
Fry
Zoiberg
(F,Z)
Washbucket
Emperor
(W,E)
Hermes
Leela
(H,L)
This yields the resulting permutation:
(H , L(W , E (F , Z (A,W (P, L(A, B(P, A
P A
 
B H
B
E
L W
P A
F E
Z W
H
L
Z
.
F
Note. The problem is to find an inverse of the permutation
P A

B H
B
E
L W
P A
F E
Z W
H Z

L F
which does not repeat any of the previous transpositions (or
repeat any new transpositions). Notice that this transposition
can be written as the disjoint cycles:
(P, B, E,W , A, H , L(Z , F .
Futurama gives the following transpositions (in order)
which produce the inverse of the above permutation:
Body 1
Body 2
Transposition
Fry
Sweet Clyde
(F,S)
Zoiberg
Bubblegum Tate
(Z,T)
Sweet Clyde
Zoiberg
(S,Z)
Bubblegum Tate
Fry
(T,F)
Professor
Sweet Clyde
(P,S)
Washbucket
Bubblegum Tate
(W,T)
Sweet Clyde
Leela
(S,L)
Bubblegum Tate
Emperor
(T,E)
Hermes
Sweet Clyde
(H,S)
Bender
Bubblegum Tate
(B,T)
Sweet Clyde
Amy
(S,A)
Bubblegum Tate
Professor
(T,P)
Washbucket
Sweet Clyde
(W,S)
The transpositions give the permutation:
(W , S (T , P(S, A(B, T (H , S (T , E (S, L(W , T (P, S (T , F (S, Z (Z , T (F , S 
F
 
Z
S
S
Z T
F T
P W
L E
L
H
E
B
H
A
B A
,
P W
which equals the product of disjoint cycles:
(F , Z (S (T (P, L, H , A,W , E, B.
We can take the permutation product to get:
P A

B H
F

Z
F
 
F
S
S
B L W
E P A
Z T
F T
S
S
Z T
Z T
P W
L E
P W
P W
F E
Z W
L
H
E
B
L E
L E
H
L
H
A
H
H
Z

F
B A

P W
B
B
A
.
A
This verifies that Futurama’s second permutation is
the inverse of the first permutation.
In terms of cycles, we have:
(P, B, E,W , A, H , L(Z , F 
(F , Z (S (T (P, L, H , A,W , E, B
 (P(B(E (W ( A(H (L(Z (F (S (T .
Sweet Clyde’s Inversion
Theorem. Any permutation
on a set of n individuals
created in the body
switching machine can be
restored by introducing at
most two extra individuals
and adhering to the cerebral
immune response rule (i.e.
no repeated transpositions).
Here is Futurama’s proof of Sweet Clyde’s
Inversion Theorem:
Recall that:
Theorem. Every permutation of
a finite set is a product of
disjoint cycles.
So if we can show the theorem
for a k-cycle, then this is
sufficient for the proof.
First, let p be a k-cycle:
 1 2 3  k 1 k 
.
p  (1,2,3,, k   
1
2 3 4 k
Introduce two new elements, x and y. We perform a
sequence of transpositions. Consider
s  (x,1( y,2( y,3( y, k  2( y, k  1( y, k (x,2( y,1
k
x
 1 2 3  k 1
 
 k 1 2  k  2 k 1 y
y
.
x
(this is a special case of Sweet Clyde’s proof, and we
use a slightly different notation).
We now see that whatever permutation p did,
permutation s undoes:
k
x
1 2 3  k 1
sp  
k 1 2  k  2 k 1 y
1 2 3  k  1 k
 
1 2 3  k  1 k
y  1 2 3k  1 k 


x  2 3 4 k
1
x
y
y

x
or
sp  (x,1( y,2( y,3( y, k  2( y, k  1( y, k (x,2( y,1(1,2,3,k 
 (1,1(2,2(k 1, k 1(k , k (x, y .
Notice that x and y are interchanged, but all other
elements are fixed.
So for each cycle in the permutation, x and y are
interchanged. If the permutation consists of an
even number of cycles, then x and y will be fixed.
If there are an odd number of cycles in the
permutation, then at the end, apply the permutation
(x,y).
Q
E
D
UPDATE!
This presentation was first given in September of 2010 (about a month after
“The Prisoner of Benda” first aired) to the TN Beta chapter of Kappa Mu
Epsilon. See:
http://faculty.etsu.edu/gardnerr/KME/Fall2010.html
UPDATE!
This episode has gotten some additional publicity in:
Simon Singh, The Simpsons and Their Mathematical
Secrets, NY: Bloomsbury (2013). See Chapter 17,
“The Futurama Theorem,” and Appendix 6.
Simon Singh argues that Fry and Zoiberg can replace
Sweet Clyde and Bubblegum Tate to give an inverse
consisting of only 9 transpositions instead of the 13 in
the show:
Body 1
Body 2
Transposition
Professor
Fry
(P,F)
Washbucket
Zoiberg
(W,Z)
Fry
Leela
(F,L)
Zoiberg
Emperor
(Z,E)
Hermes
Fry
(H,F)
Bender
Zoiberg
(B,Z)
Fry
Amy
(F,A)
Zoiberg
Professor
(Z,P)
Washbucket
Fry
(W,F)
This means that the solution given in “The Prisoner
of Benda” is not optimal in the sense of minimizing
the number of new individuals who must be introduced in order to invert the permutation.
UPDATE!
In 2014, Ron Evans, Lihua Huang, and Tuan Nguyen of the University of
California, San Diego published: “Keeler’s Theorem and Products of Distinct
Transpositions,” The American Mathematical Monthly, 121(2) 136-144 (2014).
See also: http://arxiv.org/pdf/1204.6086.pdf
In this paper, the authors give an algorithm using the smallest possible number of
switches (tanspositions) to invert the given permutation.
Oh yeah… the gratuitous cartoon nudity…
References
1. Fraleigh, John B., A First Course in Abstract Algebra,
Seventh Edition, Pearson Education (2002).
2. Internet: The images in this presentation were shamelessly
“borrowed” from the internet. Wikipedia and Google’s image
search were of particular use.
3. Details on the proof are online at:
http://theinfosphere.org/The_Prisoner_of_Benda