Sunday, August 22, 2010

I'm Afraid We Need to Use (gasp) Math!!!


The most recent episode of Futurama, "The Prisoner of Benda" was one of the most mathematically intense episodes. Written by Ken Keeler, who has Erdős number 4 for his paper "Short encodings of planar graphs and maps" co-written with fellow Futurama writer Jeff Westbrook.

Since the math got a bit complicated, I thought I would provide this handy little guide to what exactly was going in mathematically and what concepts were used.

As you could probably tell from the moment Professor Farnsworth said "Mind-Switcher", this is an episode about group theory, specifically the theory of the symmetric group.

So, for those of you who have no idea what group theory is, allow me to elaborate. A group is an abstract algebraic structure with a binary operation. This means you take two things and combine them to get one. For instance, addition takes two numbers and returns their sum, while multiplication takes two things and returns their product. To be a group, this operation has to be associative, meaning

(a + b) + c = a + (b + c)
(ab)c = a(bc)


Addition and multiplication are associative, but subtraction isn't. For example

(3 - 2) - 1 = 1 - 1 = 0
3 - (2 - 1) = 3 - 1 = 2


A group also has an identity, meaning a term that fixes everything. The additive identity is 0 and the multiplicative identity is 1, because

a + 0 = 0 + a = a
a1 = 1a = a


Finally, a group has inverses. If you combine something with its inverse you will get the identity. The additive inverse of a is -a and the multiplicative inverse of a is 1/a, because

a + (-a) = (-a) + a = 0
a(1/a) = (1/a)a = 1


So, the integers are a group under addition. The positive real numbers are a group under multiplication, but the real numbers as a whole aren't because you can't divide by 0.

The symmetric group is a group whose elements aren't numbers, but permutations of a set. The binary operation, rather than addition or multiplication is composition. If you perform one permutation and then another, you will get a third permutation. It's not hard to check that composition of permutations is associative. The identity permutation is the permutation that fixes everything, and the inverse of a permutation is the permutation that sends everything in the opposite direction.

In the case of this Futurama episode, these are permutations on the characters. It has nine elements. To make the equations simpler, I will refer to them by the first two letters of their most well-known name. They are:

Am = Amy Wong

Be = Bender Bending Rodríguez

Fa = Professor Hubert J. Farnsworth

Fr = Philip J. Fry

He = Hermes Conrad

Le = Turanga Leela

Ni = Nikolai, Playboy Ruler of the Robo-Hungarian Empire

Wa = The Wash Bucket

Zo = Dr. John A. Zoidberg

The issue in the episode was as follows: Farnsworth invents a Mind-Switcher, which can switch two people's minds. However due to the cerebral immune response (AKA random technobabble), the same pair of bodies can't switch minds twice. So after the characters get their minds permuted in a convoluted fashion (as so often happens when one has unfettered access to a Mind-Switcher), how can they return their minds to their regular bodies if the same pair of bodies can't switch twice?

Before looking at that, let's clarify some notation. We have the nine people being permuted. But we need notation for the permutations themselves. The way these would be written would be as follows. If you are only permuting two objects, a and b, you write (a,b). So, if Fry and Leela switched minds, that would be denoted (Fr,Le). It could also be denoted (Le,Fr). If Bender and Zoidberg switched minds, that would be (Be,Zo) or (Zo,Be).

For a more complicated cycle, you would write (a,b,c) to mean the mind in a's body goes into b's body, the mind in b's body goes into c's body and the mind in c's body goes to a's body. So, if Amy's mind went into Hermes, and Hermes' mind went into Nikolai and NIkolai's mind went into Amy, that would be (Am,He,Ni). This is equivalent to (He,Ni,Am) and (Ni,Am,He), but not (Am,Ni,He). That last one would mean that Amy's mind went into Nikolai, Nikolai's mind went into Hermes and Hermes' mind went into Amy. This would be the inverse permutation.

You can get larger cycles with similar notation. If n terms are in the cycle, it's called an n-cycle. so (a,b) is a 2-cycle and (a,g,e,c,y,s) is a 6-cycle. The identity permutation is denoted 1.

Note that (a,b,c) means the mind in a's body goes to b's body, which is not the same as saying a's mind goes to b's body. If a's mind had been previously switched, then (a,b,c) would send a's new mind to b's body.

Now, when composing two permutations, you write them one after another: but be careful!!! Unlike, addition or multiplication, composition of permutations is not commutative. This means the order in which you compose them matters. If Fry and Leela Switch minds and then Fry and Bender switch minds, you get (Be,Fr,Le). But if Fry and Bender switch minds and then Fry and Leela switch minds, you get (Be,Le,Fr).

To account for this problem, we will use what is known as Isaacs' Notation, named after UW-Madison Professor I. Martin Isaacs. This means, when you see two permutations in a row, you do the left one first, then the right one. This means

(Fr,Le)(Fr,Be) = (Be,Fr,Le)
(Fr,Be)(Fr,Le) = (Be,Le,Fr)


It should be noted that Isaacs' notation is not what most mathematicians use. This is because algebra was invented by Arabs and they write everything backwards. I am using Isaacs' notation for two reasons:

1) It's easier for non-mathematicians to follow, since the order of operations is the order in which people read.
2) I go to UW-Madison.

One more notational thing. Not all permutations are cyclic, but all permutations are a disjoint union of cycles, and disjoint cycles commute. This means (a,b,c)(d,e) = (d,e)(a,b,c). When you want to write a permutation that is a disjoint union of multiple cycles, one typically writes the cycles one after another. So if Fry and Leela switched minds and Bender and Zoidberg switched minds, you can just leave that as (Fr,Le)(Be,Zo) or (Be,Zo)(Fr,Le), whichever you find most aesthetically pleasing.

A few rules to make computation easier. If you have an n-cycle followed by a 2-cycle where one term in the 2-cycle appears in the n-cycle, you can just insert the other term in the 2-cycle before it. For example

(a,b,c,d,e)(c,f) = (a,b,f,c,d,e)

If you do the 2-cycle first, you put the extra term afterwards, so

(c,f)(a,b,c,d,e) = (a,b,c,f,d,e)

If both terms in the 2-cycle appear in the n-cycle then it will split the n-cycle. If the 2-cycle is after the n-cycle, you start with one term in the 2-cycle follow through with the n-cycle until just before the next term and jump back. In the other order, you start just after a term in the 2-cycle and follow through until you get to the next term.

(a,b,c,d,e,f,g)(c,f) = (a,b,f,g)(c,d,e)
(c,f)(a,b,c,d,e,f,g) = (a,b,c,g)(d,e,f)


Now, onto the events of the episode (yay):

First Amy and Farnsworth switch minds.

(Am,Fa)

Then Amy (with Farnsworth's mind) and Bender Switch minds.

(Am,Fa)(Am,Be) = (Am,Fa,Be)

Then Farnsworth (with Amy's mind) and Leela switch minds.

(Am,Fa,Be)(Fa,Le) = (Am,Le,Fa,Be)

Then Amy (with Bender's mind) and the wash bucket switch minds.

(Am,Le,Fa,Be)(Am,Wa) = (Am,Le,Fa,Be,Wa)

Then Fry and Zoidberg switch minds.

(Am,Le,Fa,Be,Wa)(Fr,Zo)

Up until this last switch, both Fry and Zoidberg had their own minds. This means we now no longer have a single cycle, but a disjoint union of a 5-cycle and a 2-cycle.

Then the wash bucket (with Bender's mind) and Nikolai switch minds.

(Am,Le,Fa,Be,Wa)(Fr,Zo)(Ni,Wa) = (Am,Le,Fa,Be,Ni,Wa)(Fr,Zo)

Then Leela (with Amy's mind) and Hermes Switch minds.

(Am,Le,Fa,Be,Ni,Wa)(Fr,Zo)(He,Le) = (Am,He,Le,Fa,Be,Ni,Wa)(Fr,Zo)

At this point, the entire main cast, as well as two new characters, have been jumbled up royally. We now have a permutation, consisting of a 7-cycle and a 2-cycle. As can be expected in this situation, various whacky shenanigans ensue culminating in an epic swordfight at the UN.

So, our permutation is (Am,He,Le,Fa,Be,Ni,Wa)(Fr,Zo), meaning Amy's mind is in Hermes' body, whose mind is in Leela's body, whose mind is in Farnsworth's body, whose mind is in Benders body, whose mind is in Nikolai's body, whose mind is in the wash bucket's body, whose mind is in Amy's body. Also, Fry and Zoidberg have their minds in each other's body.

But now they have to get back into their own bodies. But you can't repeat the same switches that occurred before. How can this be done? Fortunately the Harlem Globetrotters arrive to the rescue.

They introduce a theorem which states that any permutation can be inverted without repeating 2-cycles provided there are two fixed elements. Or in the words of "Sweet" Clyde Dixon "Basically no matter how permuted your minds are, they can be restored usin' at most two extra playas."

This theorem is known, in the Futurama universe as "Dixon's Inversion Theorem" because, in Futurama continuity, the theorem was first proved by Harlem Globetrotter "Sweet" Clyde Dixon in the year 3010. In real life, however, it was proved by Ken Keeler in the year 2010. In fact he proved it for the sole purpose of using it in this episode of Futurama.

Before explaining the proof, let's introduce the two extra playas who come to restore order. They are

Bu = Ethan "Bubblegum" Tate

Sw = "Sweet" Clyde Dixon

To get the proof of Dixon's Inversion Theorem, let's first prove it in the case of a cycle. If your permutation is (a1,a2,...,an), then your goal is to get the permutation (an,an-1,...,a1). So pick some term in the permutation ak and let x and y be the two other terms. We have the following

(x,ak)(x,ak-1)...(x,a1) = (x,ak,ak-1,...,a1)

This is part of our cycle, with an extra x thrown in. Similarly,

(y,an)(y,an-1)...(y,ak+1) = (y,an,an-1,...,ak+1)

These are disjoint cycles, so they commute, but if you apply (x,an) and (y,ak), you get

(y,an,an-1,...,ak+1)(x,ak,ak-2,...,a1)(y,ak)(x,an) = (y,an,an-1,...,ak+1,ak,ak-2,...,a1,x)(x,an) = (an,an-1,...,a1)(x,y)

This is almost the permutation we want, except x and y are switched. However, to get this permutation we never directly switched x and y, so we can directly switch them back.

Now, if you have a disjoint union of cycles, you can apply all but the final (x,y) separately to each cycle. Each time you do this, you'll invert that cycle and switch the x and the y. If your permutation is a disjoint union of an even number of cycles, you're done and if it's a disjoint union of an odd number of cycles, you can switch apply a final (x,y) switch. Q.E.D.

Dixon's Inversion Theorem is applied in the episode via a rapid-fire montage of the following body switches

Fry (with Zoidberg's mind) switches with "Sweet" Clyde.

(Fr,Sw)

Zoidberg (with Fry's mind) switches with "Bubblegum" Tate.

(Fr,Sw)(Bu,Zo)

"Sweet" Clyde (with Zoidberg's mind) switches with Zoidberg (with "Bubblegum" Tate's mind).

(Fr,Sw)(Bu,Zo)(Sw,Zo) = (Fr,Sw)(Bu,Sw,Zo)=(Bu,Sw,Fr,Zo)

"Bubblegum" Tate (with Fry's mind) switches with Fry (with "Sweet" Clyde's mind).

(Bu,Sw,Fr,Zo)(Bu,Fr) = (Bu,Sw)(Fr,Zo)

Farnsworth (with Leela's mind) switches with "Sweet" Clyde (with "Bubblegum" Tate's mind).

(Bu,Sw)(Fr,Zo)(Fa,Sw) = (Bu,Fa,Sw)(Fr,Zo)

The wash bucket (with Nikolai's mind) switches with "Bubblegum" Tate (with "Sweet" Clyde's mind).

(Bu,Fa,Sw)(Fr,Zo)(Bu,Wa) = (Bu,Fa,Sw,Wa)(Fr,Zo)

"Sweet" Clyde (with Leela's mind) switches with Leela (with Hermes' mind).

(Bu,Fa,Sw,Wa)(Fr,Zo)(Le,Sw) = (Bu,Fa,Le,Sw,Wa)(Fr,Zo)

"Bubblegum" Tate (with Nikolai's mind) switches with Nikolai (with Bender's mind).

(Bu,Fa,Le,Sw,Wa)(Fr,Zo)(Bu,Ni) = (Bu,Fa,Le,Sw,Wa,Ni)(Fr,Zo)

Hermes (with Amy's mind) switches with "Sweet" Clyde (with Hermes's mind).

(Bu,Fa,Le,Sw,Wa,Ni)(Fr,Zo)(He,Sw) = (Bu,Fa,Le,He,Sw,Wa,Ni)(Fr,Zo)

Bender (with Farnsworth's mind) switches with "Bubblegum" Tate (with Bender's mind).

(Bu,Fa,Le,He,Sw,Wa,Ni)(Fr,Zo)(Be,Bu) = (Be,Bu,Fa,Le,He,Sw,Wa,Ni)(Fr,Zo)

"Sweet" Clyde (with Amy's mind) switches with Amy (with the wash bucket's mind).

(Be,Bu,Fa,Le,He,Sw,Wa,Ni)(Fr,Zo)(Am,Sw) = (Am,Sw,Wa,Ni,Be,Bu,Fa,Le,He)(Fr,Zo)

"Bubblegum" Tate (with Farnsworth's mind) switches with Farnsworth (with "Bubblegum" Tate's mind).

(Am,Sw,Wa,Ni,Be,Bu,Fa,Le,He)(Fr,Zo)(Bu,Fa) = (Am,Sw,Wa,Ni,Be,Fa,Le,He)(Fr,Zo)

And finally, the wash bucket (with "Sweet" Clyde's mind) switches with "Sweet" Clyde (with the wash bucket's mind).

(Am,Sw,Wa,Ni,Be,Fa,Le,He)(Fr,Zo)(Sw,Wa) = (Am,Wa,Ni,Be,Fa,Le,He)(Fr,Zo)

This permutation is the inverse of the permutation the characters got into. As such they all end up back in their own bodies.

To see how this corresponds to the method described in the proof, remember our permutation is(Am,He,Le,Fa,Be,Ni,Wa)(Fr,Zo). Sw is our x and Bu is our y.

They take care of the 2-cycle first, with Fr being both a1 and ak. This is done almost exactly as described in the proof, and is undone, while switching Sw and Bu. For the 7-cycle, Am is a1 and Fa is ak. If we had followed the proof exactly this would have meant our final batch of switches would be

(Sw,Fr)(Bu,Zo)(Bu,Fr)(Sw,Zo)(Sw,Fa)(Sw,Le)(Sw,He)(Sw,Am)(Bu,Wa)(Bu,Ni)(Bu,Be)(Bu,Fa)(Sw,Wa)

These are the same switches that they did in the episode, but in a different order. However, if you have two switches, where all four people involved are different, then you can switch the order of the switches, so that's actually equivalent to the one they did in the episode. In the episode, they found a way to make it alternate between switches with "Sweet" Clyde and switches with "Bubblegum" Tate. This, I assume, was done for aesthetic reasons.

So that's basically it. If you are wondering if Dixon's Inversion Theorem can be strengthened so that you only need one more person, you can't do that. That's why simply introducing Bender to the mix after Amy and Farnsworths switched was insufficient to get them back into their original bodies. In fact Farnsworth said as much in the episode, so if you were wondering that you obviously haven't watched the episode. And if you haven't watched the episode why did you read this whole thing?

Ah well, here you go.

2 comments:

  1. Gah! I read through and only understand half of the post. Forgive my weak math skills. The saddest part was getting to the episode and seeing it was removed.

    ReplyDelete
  2. I love the maths in this show.
    The maths works but I have a couple of niggles with Clyde's write-up. I'd like someone to tell me if it's me.
    One thing that bugs me is that the proof states l-to-r (which I read as left-to-right). This makes sigma = pi*, whereas it should be the inverse. Reading right-to-left works.
    More trivially when it says I = 1...k, it should say I = 1...k-1.
    Also using I as a variable is a bit confusing, it looks exactly the same as 1.
    I'm going to write this up on Math Factor but won't do half as good a job. Thanks,
    Love the Farnsworth line 'Who says pure math isn't relevant to the real world!'

    Good work, keep it up,
    Steve

    ReplyDelete