# Variations on Keeler’s Theorem

A. Bartas, D. Lara, B. Leavitt, B. Vessely

###### Abstract.

The 2010 _Futurama_ episode The Prisoner of Benda features a mind swapping
machine that swaps the minds of two people at a time with the restriction that
the same pair of people cannot use the machine more than once. We show that if
a machine swaps $n$ people cyclically with the condition that the same group
of people cannot use the machine again, we can find a way to get everyone
back. We prove our solution is optimal for when $n=3$. We also introduce an
infinite variant of the mind swapping machine.

##  1\. Introduction

###  1.1. Context and Motivation

In _Futurama’s_ acclaimed episode, The Prisoner of Benda, a machine swaps the
minds of two people at once. The episodes features a restriction in which a
pair can only use the machine to swap once. A single person, however, can use
the machine multiple times with different partners. After a mind switching
fiasco, an algorithm is found in the show that gets everyone back into their
original body without knowing the sequence of switches that occurred. The
solution was written up by one of the show’s writers, mathematician Ken
Keeler. This algorithm is often referred to as Keeler’s Theorem.

Keeler reframed the problem in terms of permutations in the following way.
Each brain swap can be described as a transposition in $S_{n}$. The mind
switching fiasco is then a product of transpositions that yields a permutation
that is contained in $S_{n}$. The problem to get everyone back into their
original bodies reduces to finding a way to write the inverse of a permutation
$\sigma\in S_{n}$ as a product of distinct transpositions. Keeler’s solution
uses two external individuals that have not used the machine prior to the mind
switching frenzy. It is important to emphasize that the inverse of any
permutation in $S_{n}$ exists; the significance of Keeler’s result is that the
inverse can be written as a product of distinct transpositions. For example,
suppose that Person $1$ and Person $2$ use the machine. If there were no
restriction, the inverse of $(1\;2)$ is itself. That is, Person $1$ and Person
$2$ would use the machine again to get themselves back into their original
bodies. With the constraint, the inverse of the permutation can be written as
a product of distinct transpositions as

(1.1) $(1\;2)^{-1}=(x\;y)(2\;x)(1\;y)(2\;y)(1\;x).$

In 2016, Elder [4], [3] considered a machine that permutes the minds of $k$
people cyclically. That is, if people $1,2,\cdots,k$ use the machine, then
their minds get permuted as follows:

$1\to 2\to\cdots\to k\to 1.$

This can be expressed as the $k$-cycle $(1\;2\;3\cdots\;k)$. The restriction
that Elder introduced is that once a cycle $\tau$ has occurred, no cycle in
the cyclic subgroup $\langle\tau\rangle$ can occur. Elder showed that there is
a way to return everyone’s mind back to their own body when $k$ is either even
or prime. In fact, Elder’s proof works for all natural numbers $k\geq 2$.

Evans, Huang, and Nguyen [5] explored Keeler’s Theorem from a different
perspective. They refined Keeler’s result by providing a more efficient
algorithm that uses the smallest possible number of switches, with the
restriction that at least one external must be used in each step. In addition,
they also proved that the identity permutation in $S_{n}$ can can be written
as a product of $m$ distinct transpositions for when $m$ is even and when
$6\leq m\leq\binom{n}{2}$.

Our goals are to build upon these results. In our first variation of the
problem, the machine permutes $k$ people cyclically, as in Elder’s variation.
Our work varies from Elder’s in that once a set of $k$ people have used the
machine, that same set cannot use the machine again. However, each individual
can use the machine multiple times. Given any permutation that is obtained
from permuting $n$ people cyclically, we provide an algorithm that gets
everyone back into their original body. To build on the work of Evans, Huang,
and Nguyen, we explore the optimally of our solution for when the machine
permutes $3$ people. Finally, we introduce an infinite variation of the
machine that swaps the minds of an infinite amount of people. Our main
theorems are as follows.

###  1.2. Main Results

We employ a variation similar to that of Elder [4]. A machine swaps $k$ people
cyclically. That is if $a_{1},a_{2},\cdots,a_{k}$ use the machine, then the
machine permutes their minds as

$a_{1}\to a_{2}\to\cdots\to a_{k}\to a_{1}.$

Our restriction is that no set of $k$ people can use the machine more than
once. Additionally, we follow Keeler and Elder’s assumption in that we don’t
know which steps were taken to achieve the original mind scrambling, meaning
we need to introduce external users when try to revert everyone back into
their original bodies. We will refer to these external people as outsiders
throughout the paper. Two of our main theorems under these assumptions are as
follows:

######  Theorem 1.2.

Let $m,n\in\mathbb{N}$, $m\geq 3$, $n\geq m$. Let $H_{m}\subseteq S_{n}$
denote the subgroup generated by all $m$-cycles. If $\sigma\in H_{m}$, then
there exist $\mu_{1},\cdots,\mu_{r}$ such that

  1. (1)

$\mu_{i}\in S_{n+d}\setminus S_{n}$, where $d=\begin{cases}(m-2)&\text{if
}m\text{ is odd}\\\ 3(\frac{m}{2}-1)&\text{if }m\text{ is even}\end{cases}$

  2. (2)

$\sigma^{-1}=\mu_{1}\cdots\mu_{r}$, where $\mu_{i}$ is an $m$-cycle permuting
a distinct set of $m$ elements for all $1\leq i\leq r$.

That is, if a collection of $n$ people have used a mind swap machine of size
$m\geq 3$, we can revert everyone back with the addition of $m-2$ outsiders if
$m$ is odd and $3\left(m/2-1)\right)$ outsiders if $m$ is even.

######  Theorem 1.3.

Let $\sigma\in S_{n}$ be written as a product of $r$ disjoint cycles as
$\sigma=\tau_{1}\cdots\tau_{r}$, where $\tau_{i}$ is a $k_{i}$-cycle with
$k_{i}\geq 2$ and $k_{1}+\cdots+k_{r}=n$. Consider outsider $x$ which
$S_{n+1}$ acts upon. We can write $\sigma^{-1}\in S_{n+1}\setminus S_{n}$ as a
product of ${(n+r)\over 2}$ 3-cycles, each of which contains $x$. Further,
this solution is optimal in that any other construction of $\sigma^{-1}$ must
have at least ${(n+r)\over 2}$ steps.

If $n$ people get scrambled using a machine of size $m=3$, we can group them
up into a $r$ number of disjoint groups where in each group, the individuals
have been permutated cyclically. We prove that we need one and only one
outsider and show that the minimum number of steps required must be by
$\left(\frac{n+r}{2}\right)$. We later consider a variation of the problem
where the machine ”cycles” a countably infinite amount of people. The main
result shown in this variation is,

######  Theorem 1.4.

Let $X$ be a countable infinite set, $\sigma\in S_{fin}(X)$. Then there exist
$f_{1}$ and $f_{2}$, which are forgetful and retentive respectively, such that
$dom(f_{1})\neq dom(f_{2})$ and $\sigma^{-1}=f_{2}\circ f_{1}$.

This was quite surprising as $\sigma$ could have been created using an
arbitrarily large number of swaps and yet its inverse can always be written in
2 steps.

###  1.3. Symmetric Group

In this section, we will present fundamental results about the symmetric group
$S_{n}$. For a more detailed recollection, we refer the interested reader to
standard references such as Dummit and Foote [2].

We denote the group of permutations of $n$ objects by $S_{n}$. A _cycle_ of
length $k$ is a permutation that permutes $k$ objects cyclically. $S_{n}$ is
defined to be the set of bijections on the set $\\{1,2,\cdots,n\\}$, and it
forms a group under function composition. The objects of $S_{n}$ are called
_permutations_. For an example, consider the permutation $\sigma\in S_{4}$
defined as

$\sigma=\begin{pmatrix}1&2&3&4\\\ 4&3&1&2\end{pmatrix}$

where $\sigma$ sends $1$ to $4$, $2$ to $3$, and so on. A convenient
alternative notation for permutations is called cycle notation. We see that
$\sigma$ permutes the objects as

$1\to 4\to 2\to 3\to 1.$

We can then write $\sigma$ in cycle notation as $\sigma=(1\;4\;2\;3)$. Note
that if $\sigma=(1\;4\;2\;3)\in S_{10}$, it still permutes $1\to 4\to 2\to
3\to 1$ cyclically, but all other numbers stay fixed. A cycle $\tau\in S_{n}$
of length $k\leq n$ is a function that permutes $k$ objects cyclically. Two
cycles are _disjoint_ if the numbers moved by one cycle are left fixed by the
other. For example, $(1\;3)(2\;5)$ is a product of two disjoint cycles.

######  Example 1.5.

Let’s compute the product

(1.6) $(1\;5)(1\;2\;3)(1\;4).$

When multiplying permutations, the permutation on the right is evaluated
first. The right most permutation sends $1\to 4$. The second leaves $4$ fixed,
and so does the third. Thus, the permutation sends $1\to 4$. Next, we evaluate
the permutation at $4$. The right most cycle sends $4\to 1$, the second sends
$1\to 2$, and the third leaves $2$ fixed. Continuing this process, we obtain

(1.7) $(1\;5)(1\;2\;3)(1\;4)=(1\;4\;2\;3\;5).$

∎

The example illustrates that when we take a product of non-disjoint cycles, we
obtain a product of disjoint cycles (a product of one cycle, in this example).
This is true for all permutations.

######  Theorem 1.8.

Every permutation of $S_{n}$ can be written uniquely, up to order, as a
product of disjoint cycles.

A _transposition_ is a cycle of length $2$, such as $(1\;2)$. Every
permutation can be written as a product of transpositions. A permutation is
said to be _even_ if it can be written as a product of of an even number of
transpositions and _odd_ if it can be written as a product of an odd number of
transpositions. All permutations are either even or odd but not both.

######  Example 1.9.

$(123)=(13)(12)$

so the cycle $(123)$ is even.

$(1234)=(14)(13)(12)$

so the cycle $(1234)$ is odd. Let $I$ be the identity permutation. Observe

$I=(12)(12)$

so $I$ is even. ∎

From these examples we can observe that a cycle of odd length is an even
permutation and a cycle of even length is an odd permutation. The collection
of all even permutation of $S_{n}$ forms a subgroup called the alternating
group $A_{n}.$ We present several key results about the alternating group.

######  Theorem 1.10.

$A_{n}$ is a subgroup of index $2$ and for $n\geq 3$, $A_{n}$ is generated by
$3$-cycles.

That is, every permutation in $A_{n}$ can be written as a product of three
cycles. For example, consider $(3\;4)(1\;2)\in A_{n}$, then

$(3\;4)(1\;2)=(3\;1\;4)(1\;2\;3).$

Another interesting result is that $A_{n}$ is a normal subgroup of $S_{n}$,
meaning that we can mod out the objects of $S_{n}$ by $A_{n}$. The resulting
equivalence classes forms a subgroup. This is written as $S_{n}/A_{n}$. It
turns out that for $n\geq 5$, we have the following interesting result.

######  Lemma 1.11.

Let $n\geq 5$. Then if $H$ is a non-trivial normal subgroup of $S_{n}$, then
$H=A_{n}$.

###  1.4. Mind Swapping Machines

The mind swapping machines can be completely described in terms of
permutations. Suppose people $a_{1},\cdots,a_{k}$ use the machine. The machine
is ordered in such a way that person $a_{1}$ sits on seat $1$ and so on. The
machine then performs the permutation $(a_{1}\;\cdots\;a_{k})$.

Given a collection of people whose minds have been permuted by some sequence
of uses of the $k$-machine, we can always write that permutation of minds as a
product of $k$-cycles. From fundamental results about the symmetric group, the
resulting permutation is a product of distinct cycles.

The problem of getting everyone’s mind back to their own body is reduced to
finding the inverse of $\tau\in S_{n}$. Every permutation can be written as a
product of disjoint cycles. For example, we can write the permutation $\tau\in
S_{n}$ as a product of disjoint cycles where

$\tau=\tau_{1}\cdots\tau_{k}$

with $\tau_{i}\in S_{n}$ for all $i$. Observe that in order to find the
inverse of $\tau$, we just need to find the inverse of each $\tau_{i}$:

$\tau^{-1}=\tau_{k}^{-1}\cdots\tau_{1}^{-1}.$

Under our restrictions, we will not know which sets of people were cycled in
the machine to create the original permutation. Thus, we again require that
the inverse of each $\tau_{i}$ must contain an outsider in each step.

######  Example 1.12.

Suppose Amy, Bender, and Fry have used the $3$-machine. Regardless of what
order they used the machine, we label people as follows. We start with Amy’s
body. Her body gets the label $a_{1}$. Suppose Amy’s mind got moved to Fry’s
body. Fry’s body is then labeled $a_{2}$. We then look for Fry’s mind and in
this case, the only possibility is that it must be in Bender’s body. We label
Bender as $a_{3}$, thus meaning Bender’s mind is in Amy’s body. The
permutation is then written as

$\tau=(a_{1}\;a_{2}\;a_{3})$

Of course, if the machine allowed the same group of people to use the machine
more than once, we could just the machine two more times to get everyone back.
Since this is not allowed under our restriction, the goal is then to find
outsiders that have not used the machine yet to help revert their minds. That
is, we want to write the inverse of $\tau$ as a product of distinct
$3$-cycles. ∎

##  2\. Keeler’s Result

In the original problem, two people switch minds and realize they cannot
switch back. By the end of the episode in which this mind-switching occurs,
the characters’ minds are all scrambled. Keeler’s original solution uses two
outsiders to get everyone back into their original bodies. We will reprove
this solution in a novel manner. We first note that our solution as proposed
in Theorem 2.1 is not exactly the same as Keeler’s solution [3]. Nevertheless,
our algorithm works similarly to Keeler’s, while allowing for a clearer proof.

We call our two outsiders $x$ and $y$, letting $x=n+1$ and $y=n+2$. We define
$S_{n+2}\setminus S_{n}$ to be the collection of permutations that permute $x$
or $y$.

######  Theorem 2.1.

Given any cycle $\tau_{k}=(a_{1}\cdots a_{k})\in S_{n}$, its inverse can be
expressed as a product of distinct transpositions in $S_{n+2}\setminus S_{n}$
in the following form:

(2.2)
$\tau_{k}^{-1}=(x\;y)\bigg{[}\prod_{\ell=2}^{k}(x\;a_{\ell})\bigg{]}(y\;a_{1})(y\;a_{2})(x\;a_{1}).$

###### Proof.

Let $\tau=(a_{1}\cdots a_{k})\in S_{n}$ be a $k$-cycle. We then define

(2.3) $\overline{\tau}_{k}=\prod_{\ell=2}^{k}(x\;a_{\ell}).$

We claim that

(2.4) $\tau_{k}^{-1}=(x\;y)\overline{\tau}_{k}(y\;a_{1})(y\;a_{2})(x\;a_{1}),$

or equivalently,

(2.5) $\overline{\tau}_{k}=(x\;y)\tau_{k}^{-1}(x\;a_{1})(y\;a_{2})(y\;a_{1}).$

We will prove this using induction on $\overline{\tau}_{k}$. For our base
case, in which two people’s minds are cycled, we have

(2.6) $\tau_{2}=(a_{1}\;a_{2}).$

By inspection, we see that

(2.7) $\tau^{-1}_{2}=(x\;y)(x\;a_{2})(y\;a_{1})(y\;a_{2})(x\;a_{1}).$

We verify that $\overline{\tau}_{2}$ has the desired form by rewriting
$\tau^{-1}_{2}$ as follows:

(2.8) $\tau^{-1}_{2}=(x\;y)\overline{\tau}_{2}(y\;a_{1})(y\;a_{2})(x\;a_{1}),$

thus obtaining our desired form,

(2.9) $\overline{\tau}_{2}=(x\;y)\tau^{-1}_{2}(x\;a_{1})(y\;a_{2})(y\;a_{1}).$

We assume inductively that
$\overline{\tau}_{k}=(x\;y)\tau^{-1}_{k}(x\;a_{1})(y\;a_{2})(y\;a_{1})$ holds
for some $k\geq 2$. Let $\tau_{k+1}=(a_{1}\cdots a_{k})$ be a cycle of length
$k+1$.

(2.10) $\displaystyle\overline{\tau}_{k+1}$
$\displaystyle=\bigg{[}\prod_{\ell=2}^{k+1}(x\;a_{\ell})\bigg{]}$ (2.11)
$\displaystyle=\bigg{[}\prod_{\ell=2}^{k}(x\;a_{\ell})\bigg{]}(x\;a_{k+1})$
(2.12) $\displaystyle=\overline{\tau}_{k}(x\;a_{k+1}).$

By our inductive hypothesis,

(2.13) $\displaystyle\overline{\tau}_{k+1}$
$\displaystyle=(x\;y)\tau_{k}^{-1}(x\;a_{1})(y\;a_{2})(y\;a_{1})(x\;a_{k+1})$
(2.14)
$\displaystyle=(x\;y)\tau_{k}^{-1}(x\;a_{1})(x\;a_{k+1})(y\;a_{2})(y\;a_{1})$
(2.15)
$\displaystyle=(x\;y)\tau_{k}^{-1}(a_{1}\;a_{k+1})(x\;a_{1})(y\;a_{2})(y\;a_{1}).$

We know that $\tau_{k}^{-1}=(a_{k}\;a_{k-1}\cdots a_{1})$, so
$\tau_{k}^{-1}(a_{1}\;a_{k+1})=\tau_{k+1}^{-1}$. Thus, we have

(2.16)
$\overline{\tau}_{k+1}=(x\;y)\tau_{k+1}^{-1}(x\;a_{1})(y\;a_{2})(y\;a_{1}),$

giving us our desired result. ∎

######  Remark 2.17.

The permutation $\tau^{-1}$ can be expressed as a product of $k+3$ distinct
transpositions.

######  Definition 2.18.

Let $\tau=(a_{1}\cdots a_{k})$ be an arbitrary $k$-cycle in $S_{n}$. Then we
define

(2.19)
$\widehat{\tau}:=\overline{\tau}(y\;a_{1})(y\;a_{2})(x\;a_{1})=\bigg{[}\prod_{\ell=2}^{k}(x\;a_{\ell})\bigg{]}(y\;a_{1})(y\;a_{2})(x\;a_{1}).$

######  Remark 2.20.

We note that can use $\widehat{\tau}$ to rewrite the result from Theorem 2.1
more concisely, which will make subsequent abstraction of the problem clearer:
given a $k$-cycle $\tau=(a_{1}\cdots a_{k})\in S_{n}$, its inverse can be
written in $S_{n+2}\setminus S_{n}$ as

$\tau^{-1}=(x\;y)\widehat{\tau}.$

We can rewrite this as $\widehat{\tau}=(x\;y)\tau^{-1}$, allowing us to derive
the following identity:

(2.21) $\widehat{\tau}\tau=(x\;y)\tau^{-1}\tau=(x\;y).$

We now look at the case where we have a general permutation $\sigma\in S_{n}$
which is not necessarily a single cycle.

######  Theorem 2.22.

Given $\sigma\in S_{n}$, $\sigma^{-1}$ can be written as a product of distinct
transpositions in $S_{n+2}\setminus S_{n}$. Specifically, if
$\sigma=\tau_{1}\cdots\tau_{j}$ for disjoint cycles $\tau_{i}\in S_{n}$ with
$1\leq i\leq j$, then $\sigma^{-1}$ can be written in the form

$\sigma^{-1}=\begin{cases}(xy)\widehat{\tau}_{j}\cdots\widehat{\tau}_{1}&\text{if
$j$ is odd}\\\ \widehat{\tau}_{j}\cdots\widehat{\tau}_{1}&\text{if $j$ is
even}.\\\ \end{cases}$

###### Proof.

Let $\sigma\in S_{n}$. Theorem 1.8 tells us that there exists $j\geq 1$ such
that $\sigma$ can be written as a product of $j$ disjoint cycles:

(2.23) $\sigma=\tau_{1}\cdots\tau_{j}=\prod_{i=1}^{j}\tau_{i}.$

We first have the case when $j$ is odd. Consider

(2.24)
$\gamma=(x\;y)\widehat{\tau}_{j}\cdots\widehat{\tau}_{1}=(x\;y)\prod_{i=0}^{j-1}\widehat{\tau}_{j-i}.$

We then have

(2.25) $\displaystyle\gamma\sigma$
$\displaystyle=(x\;y)\prod_{i=0}^{j-1}\widehat{\tau}_{j-i}\;\prod_{i=1}^{j}\tau_{i}$
(2.26)
$\displaystyle=(x\;y)\bigg{[}\prod_{i=0}^{j-2}\widehat{\tau}_{j-i}\bigg{]}\widehat{\tau}_{1}\tau_{1}\bigg{[}\prod_{i=2}^{j}\tau_{i}\bigg{]}$
(2.27)
$\displaystyle=(x\;y)\bigg{[}\prod_{i=0}^{j-2}\widehat{\tau}_{j-i}\bigg{]}(x\;y)\bigg{[}\prod_{i=2}^{j}\tau_{i}\bigg{]}.$

Because $\tau_{i}\in S_{n}$ for all $i\geq 1$, $\tau_{i}$ does not contain the
elements $x\text{ or }y$ at any point. This means that $\tau_{i}\text{ and
}(x\;y)$ are disjoint, so we can commute them:

(2.28)
$\gamma\sigma=(x\;y)\bigg{[}\prod_{i=0}^{j-2}\widehat{\tau}_{j-i}\bigg{]}\bigg{[}\prod_{i=2}^{j}\tau_{i}\bigg{]}(x\;y).$

We then repeat this process, cancelling each $\widehat{\tau}_{i}$ with
$\tau_{i}$ to get $(x\;y)$, then commuting $(x\;y)$ to the far right of the
equation. We will do this $j$ times, once for each $\tau_{i}$, leaving us with

(2.29) $\displaystyle\gamma\sigma$ $\displaystyle=(x\;y)(x\;y)^{j}$ (2.30)
$\displaystyle=(x\;y)^{j+1}$ (2.31)
$\displaystyle=\left((x\;y)^{2}\right)^{(j+1)/2}$ (2.32)
$\displaystyle=(e)^{(j+1)/2}$ (2.33) $\displaystyle=e$

So, for all $j\geq 1$ with $j$ odd, we have shown that
$\gamma=(x\;y)\prod_{i=0}^{j-1}\widehat{\tau}_{j-i}=\sigma^{-1}.$

We now look at the case where $j$ is even. We still have
$\sigma=\tau_{1}\cdots\tau_{j}=\prod_{i=1}^{j}\tau_{i}$. Consider the product

(2.34)
$\theta=\widehat{\tau}_{1}\cdots\widehat{\tau}_{j}=\prod_{i=0}^{j-1}\widehat{\tau}_{j-i}.$

We then have

(2.35) $\displaystyle\theta\sigma$
$\displaystyle=\prod_{i=0}^{j-1}\widehat{\tau}_{j-i}\prod_{i=1}^{j}\tau_{i}$
(2.36)
$\displaystyle=\bigg{[}\prod_{i=0}^{j-2}\widehat{\tau}_{j-i}\bigg{]}\widehat{\tau}_{1}\tau_{1}\bigg{[}\prod_{i=2}^{j}\tau_{i}\bigg{]}$
(2.37)
$\displaystyle=\bigg{[}\prod_{i=0}^{j-2}\widehat{\tau}_{j-i}\bigg{]}(x\;y)\bigg{[}\prod_{i=2}^{j}\tau_{i}\bigg{]}$
(2.38)
$\displaystyle=\bigg{[}\prod_{i=0}^{j-2}\widehat{\tau}_{j-i}\bigg{]}\bigg{[}\prod_{i=2}^{j}\tau_{i}\bigg{]}(x\;y),$

where we’ve used the same logic as in the odd case to commute $(x\;y)$. We
repeat this process $j-1$ more times, once for each $\tau_{i}$ remaining in
the right product. This gives us x

(2.39) $\displaystyle\theta\sigma$ $\displaystyle=(x\;y)^{j}$ (2.40)
$\displaystyle=\left((x\;y)^{2}\right)^{j/2}$ (2.41)
$\displaystyle=\left(e\right)^{j/2}$ (2.42) $\displaystyle=e.$

Thus, we have
$\theta=\prod_{i=0}^{j-1}\widehat{\tau}_{j-i}=\widehat{\tau}_{j}\cdots\widehat{\tau}_{1}=\sigma^{-1}$,
as desired. ∎

##  3\. Machines of Larger Sizes

Now suppose the machine swaps $m$ people at at time, cyclically. That is,

$1\to 2\to 3\to\cdots m\to 1$

To extend the rules from Keeler’s original problem, we will assume that the
same group of people cannot use the machine more than once but that
individually, each person can use the machine multiple times. Reframed in
terms of permutations, we have our main result for this section.

######  Theorem 3.1.

Let $m,n\in\mathbb{N}$, $m\geq 3$, $n\geq m$. Let $H_{m}\subseteq S_{n}$
denote the subgroup generated by all $m$-cycles. If $\sigma\in H_{m}$, then
there exist $\mu_{1},\cdots,\mu_{r}$ such that

  1. (1)

$\mu_{i}\in S_{n+d}\setminus S_{n}$, where $d=\begin{cases}(m-2)&\text{if
}m\text{ is odd}\\\ 3(\frac{m}{2}-1)&\text{if }m\text{ is even}\end{cases}$

  2. (2)

$\sigma^{-1}=\mu_{1}\cdots\mu_{r}$, where $\mu_{i}$ is an $m$-cycle permuting
a distinct set of $m$ elements for all $1\leq i\leq r$.

We will refer to $S_{n}$ as the group that permutes $A=\\{a_{1}\cdots
a_{n}\\}$ and $S_{n+d}$ as the group that permutes $A\cup\\{x_{1}\cdots
x_{d}\\}$. So an $m$-cycle $\mu\in S_{n+d}\setminus S_{n}$ is a permutation
that permutes at least one element in $\\{x_{1}\cdots x_{d}\\}$. The part of
this theorem that distinguishes our problem from Elder’s is (2). As an
example:

$(a_{1}\;a_{2}\;a_{3})^{-1}=(a_{1}\;a_{3}\;a_{2})=(a_{1}\;a_{2}\;a_{3}\;x_{2}\;x_{1})(a_{3}\;a_{1}\;a_{2}\;x_{1}\;x_{2})$

is a perfectly acceptable solution under Elder’s variation as

$\langle(a_{1}\;a_{2}\;a_{3}\;x_{2}\;x_{1})\rangle\neq\langle(a_{3}\;a_{1}\;a_{2}\;x_{1}\;x_{2})\rangle.$

But for our purposes we cannot use both of these cycles, as each cycle
permutes the same 5 elements. It is worthwhile to note that any solution under
our restriction can be used under Elder’s restriction (perhaps not as
optimally). The case in which $\sigma$ is a $3$-cycle is of particular
interest to us. We will prove this case in the following lemma.

######  Lemma 3.2.

Let $m,n\in\mathbb{N}$, $m\geq 3$, $n\geq m$. If $\tau\in S_{n}$ is a
$3$-cycle, then there exist $\mu_{1},\mu_{2}$ where $\mu_{i}\in
S_{n+(m-2)}\setminus S_{n}$ such that

  1. (1)

$\tau^{-1}=\mu_{1}\mu_{2}$

  2. (2)

For all $1\leq i\leq 2$, $\mu_{i}$ is an $m$-cycle permuting a distinct set of
$m$ elements

###### Proof.

Let $\tau=(a_{1}\;a_{2}\;a_{3})$. Then

$\tau^{-1}=(a_{1}\;a_{3}\;x_{1}\cdots x_{m-2})(a_{3}\;a_{2}\;x_{m-2}\cdots
x_{1})$

∎

It is worthwhile noting that in this lemma, the solution does not depend on
the parity of $m$.

######  Lemma 3.3.

Let $m,n\in\mathbb{N}$, $m\geq 3$, $n\geq m$. $H_{m}\subseteq S_{n}$ is a
normal subgroup.

###### Proof.

Let $\tau=(a_{1}\cdots a_{m})\in S_{n}$ be an $m$-cycle and thus a generator
of $H_{m}$. For all $\sigma\in S_{n}$,

$\sigma\tau\sigma^{-1}=(\sigma(a_{1})\cdots\sigma(a_{m})).$

Since $\sigma$ is a bijection, there exists $\tau^{\prime}\in H_{m}$ such that

$\tau^{\prime}=(\sigma^{-1}(a_{1})\cdots\sigma^{-1}(a_{m})).$

Thus, $\sigma\tau^{\prime}\sigma^{-1}=\tau$. It is clear that conjugation
permutes the generators of $H_{m}$, hence $\sigma H_{m}\sigma^{-1}=H_{m}$. ∎

We will prove theorem 3.1 in even and odd sections.

###  3.1. Case 1: $m$ is odd

We will use the following without proof.

######  Lemma 3.4.

Let $m,n\in\mathbb{N}$, $n\geq m\geq 3$. $H_{m}=A_{n}$ if and only if $m$ is
odd.

###### Proof.

$\Rightarrow$ Assume that $m$ is even, and let $\tau$ be an $m$-cycle. We know
that $\tau$ is certainly in $H_{m}$ by definition. Since $\tau$ is a cycle of
even length, it is an odd permutation. Hence $\tau\notin A_{n}$.
$\Leftarrow$ If $m=3$, the result follows from Lemma 1.10. Suppose $m\geq 5$.
From Lemma 3.3 we know $H_{m}$ is normal. Thus the result follows from Lemma
1.11. ∎

This is everything we need to prove the case where the machine switches an odd
number of people. To introduce some notation, we denote the elements permuted
by $S_{n+(m-2)}\setminus S_{n}$ in a list by:

$\displaystyle[x]=x_{1}\ x_{2}\cdots x_{m-2}$
$\displaystyle[x]^{-1}=x_{m-2}\cdots x_{2}\ x_{1}$

So from lemma 3.2 if $\tau=(a_{1}\;a_{2}\;a_{3})\in S_{n}$, then its inverse
in $S_{n+(m-2)}\setminus S_{n}$ under our new notation can be written as

$\tau^{-1}=(a_{1}\;a_{3}\;[x])(a_{3}\;a_{2}\;[x]^{-1})$

######  Theorem 3.5.

Let $m,n\in\mathbb{N}$, with $m$ odd, $n\geq m\geq 3$. If $\sigma\in H_{m}$,
then there exist $\mu_{1},\cdots,\mu_{r}\in S_{n+(m-2)}\setminus S_{n}$ for
some $r\geq 1$ such that

  1. (1)

$\sigma^{-1}=\mu_{r}\cdots\mu_{1}$

  2. (2)

For all $1\leq i\leq r$, $\mu_{i}$ is an $m$-cycle permuting a distinct set of
$m$ elements

###### Proof.

By the previous lemma $H_{m}=A_{n}$ so we need only consider the case for
which $\sigma$ is even. We can write $\sigma$ as a product of disjoint cycles.

$\sigma=\tau_{1}\cdots\tau_{r}$

Let $\tau_{i}$ have length $k_{i}$. If $k_{i}$ is odd for all $i$, then
$\tau_{i}\in A_{n}$ for all $i$. Let

$\tau_{i}=(a_{i,1}\cdots a_{i,k_{i}}).$

Since $k_{1}$ is odd, we can write

$(a_{i,1}\cdots
a_{i,k_{i}})=(a_{i,1}\;a_{i,2}\;a_{i,3})(a_{i,3}\;a_{i,4}\;a_{i,5})\cdots(a_{i,k_{i}-2}\;a_{i,k_{i}-1}\;a_{i,k_{i}}).$

By lemma 3.2, we know we can write the inverses of each of these $3$-cycles as
a product of two $m$-cycles in $S_{n+(m-2)}\setminus S_{n}$. Additionally, any
given $3$-cycle is disjoint from all others with exception to the ones next to
it. Therefore, it is sufficient to check that the inverse of
$(a_{i,1}\;a_{i,2}\;a_{i,3})(a_{i,3}\;a_{i,4}\;a_{i,5})$ written as $m$-cycles
satisfies (2) in Theorem 3.5. We proceed using lemma 3.2

$\displaystyle(a_{i,1}\;a_{i,2}\;a_{i,3})^{-1}=(a_{i,1}\;a_{i,3}\;a_{i,2})=(a_{i,1}\;a_{i,3}\;[x])(a_{i,3}\;a_{i,2}\;[x]^{-1})$
$\displaystyle(a_{i,3}\;a_{i,4}\;a_{i,5})^{-1}=(a_{i,3}\;a_{i,5}\;a_{i,4})=(a_{i,3}\;a_{i,5}\;[x])(a_{i,5}\;a_{i,4}\;[x]^{-1}).$

All $m$-cycles above permute a distinct set of $m$ elements, so we can define

$\mu_{i}=(a_{i,k_{i}-2}\;a_{i,k_{i}}\;[x])(a_{i,k_{i}}\;a_{i,k_{i}-1}\;[x]^{-1})\cdots(a_{i,1}\;a_{i,3}\;[x])(a_{i,3}\;a_{i,2}\;[x]^{-1}).$

Where $\mu_{i}=\tau_{i}^{-1}$ hence

$\sigma^{-1}=\mu_{r}\cdots\mu_{1}.$

Now suppose there exists $i$ such that $k_{i}$ is even. Since $\sigma\in
A_{n}$, there must also exist $j\neq i$ such that $k_{j}$ is even. Let

$\displaystyle\tau_{i}=(a_{1}\cdots a_{k_{i}})=(a_{1}\cdots
a_{k_{i}-1})(a_{k_{i}-1}\;a_{k_{i}})$ $\displaystyle\tau_{j}=(b_{1}\cdots
b_{k_{j}})=(b_{1}\cdots b_{k_{j}-1})(b_{k_{j}-1}\;b_{k_{j}})$

So to fix $\tau_{i}$ and $\tau_{j}$, we show it is possible to fix their
product

$\displaystyle\tau_{i}\tau_{j}$ $\displaystyle=(a_{1}\cdots
a_{k_{i}-1})(a_{k_{i}-1}\;a_{k_{i}})(b_{1}\cdots
b_{k_{j}-1})(b_{k_{j}-1}\;b_{k_{j}})$ $\displaystyle=(a_{1}\cdots
a_{k_{i}-1})(b_{1}\cdots
b_{k_{j}-1})(a_{k_{i}-1}\;a_{k_{i}})(b_{k_{j}-1}\;b_{k_{j}})$

We have shown how to write the inverse for a cycle of odd length. Thus for
this case it is sufficient to show we can write the inverse of
$(a_{k_{i}-1}\;a_{k_{i}})(b_{k_{j}-1}\;b_{k_{j}})$ under our restrictions.

$(a_{k_{i}-1}\;a_{k_{i}})(b_{k_{j}-1}\;b_{k_{j}})=(a_{k_{i}-1}\;a_{k_{i}}\;b_{k_{j}-1})(a_{k_{i}}\;b_{k_{j}-1}\;b_{k_{j}})$

So we have

$((a_{k_{i}-1}\;a_{k_{i}})(b_{k_{j}-1}\;b_{k_{j}}))^{-1}=(a_{k_{i}}\;b_{k_{j}}\;b_{k_{j}-1})(a_{k_{i}-1}\;b_{k_{j}-1}\;a_{k_{i}}).$

And from our previous work,

$\displaystyle(a_{k_{i}}\;b_{k_{j}}\;b_{k_{j}-1})=(a_{k_{i}}\;b_{k_{j}}\;[x])(b_{k_{j}}\;b_{k_{j}-1}\;[x]^{-1})$
$\displaystyle(a_{k_{i}-1}\;b_{k_{j}-1}\;a_{k_{i}})=(a_{k_{i}-1}\;b_{k_{j}-1}\;[x])(b_{k_{j}-1}\;a_{k_{i}}\;[x]^{-1})$

Where each $m$-cycle permutes a distinct set of elements. ∎

###  3.2. Case 2: $m$ is even

######  Lemma 3.6.

Let $m\geq 2$ be an even number and $n\geq m$. Then $H_{m}=S_{n}$.

###### Proof.

We know that $S_{n}$ is generated by transpositions so it is sufficient to
show that all transpositions lie in $H_{m}$. Let $(x\;y)\in S_{n}$. Notice
that one can obtain an $(m-1)$-cycle from the product of two $m$-cycles as
follows:

$(y\;a_{1}\;x\;a_{2}\cdots a_{m-2})(y\;x\;a_{1}\ a_{2}\cdots
a_{m-2})=(y\;a_{2}\;a_{4}\;a_{6}\cdots a_{m-2}\;a_{1}\;a_{3}\cdots a_{m-3}).$

Then we can obtain our transposition by taking the product of this
$(m-1)$-cycle with a certain $m$-cycle:

$\displaystyle(x\;y\;a_{m-3}\cdots a_{3}\;a_{1}\;a_{m-2}\cdots
a_{6}\;a_{4}\;a_{2})(y\;a_{2}\;a_{4}\;a_{6}\cdots a_{m-2}\;a_{1}\;a_{3}\cdots
a_{m-3})$ $\displaystyle=(x\;y)(y\;a_{m-3}\cdots a_{3}\;a_{1}\;a_{m-2}\cdots
a_{6}\;a_{4}\;a_{2})(y\;a_{2}\;a_{4}\;a_{6}\cdots a_{m-2}\;a_{1}\;a_{3}\cdots
a_{m-3})$ $\displaystyle=(x\;y).$

Thus $(x\;y)\in H_{m}$. ∎

######  Lemma 3.7.

Let $m,n\in\mathbb{N}$, with $m$ even, $n\geq m\geq 4$. Let $\sigma\in S_{n}$
be a transposition. Then there exist $\mu_{1},\mu_{2},\mu_{3}\in
S_{n+3(\frac{m}{2}-1)}\setminus S_{n}$

  1. (1)

$\sigma^{-1}=\mu_{1}\mu_{2}\mu_{3}$

  2. (2)

For all $1\leq i\leq 3$, $\mu_{i}$ is an $m$-cycle permuting a distinct set of
$m$ elements

To introduce some notation, we denote the elements permuted by
$S_{n+3(\frac{m}{2}-1)}\setminus S_{n}$ in three groups. We denote them in a
list by

$\displaystyle[w]=x_{1}\ x_{2}\cdots x_{\frac{m}{2}-1}$
$\displaystyle[w]^{-1}=x_{\frac{m}{2}-1}\cdots x_{2}\ x_{1}$
$\displaystyle[y]=y_{1}\ y_{2}\cdots y_{\frac{m}{2}-1}$
$\displaystyle[y]^{-1}=y_{\frac{m}{2}-1}\cdots y_{2}\ y_{1}$
$\displaystyle[z]=z_{1}\ z_{2}\cdots z_{\frac{m}{2}-1}$
$\displaystyle[z]^{-1}=z_{\frac{m}{2}-1}\cdots z_{2}\ z_{1}.$

Notice that $|[w]|+|[y]|+|[z]|=3(\frac{m}{2}-1)$.

###### Proof.

Let $\sigma=(a_{1}\;a_{2})$. Then

$\sigma^{-1}=(a_{1}\ [z]^{-1}\ [y]^{-1}\ a_{2})(a_{1}\ [w]^{-1}\ a_{2}\
[z])([w]\ a_{1}\ [y]\ a_{2})$

∎

######  Theorem 3.8.

Let $m,n\in\mathbb{N}$, with $m$ even, $n\geq m\geq 4$. If $\sigma\in
H_{m}=S_{n}$, then there exist $\mu_{1},\cdots,\mu_{r}$ where $\mu_{i}\in
S_{n+3(\frac{m}{2}-1)}\setminus S_{n}$ such that

  1. (1)

$\sigma^{-1}=\mu_{1}\cdots\mu_{r}$

  2. (2)

For all $1\leq i\leq r$, $\mu_{i}$ is an $m$-cycle permuting a distinct set of
$m$ elements

###### Proof.

Since $\sigma$ can be written as a product of disjoint cycles, it is
sufficient to prove for the case when $\sigma$ is a cycle. Suppose $\sigma$
has odd length. Then $\sigma\in A_{n}$. Thus it can be written as a product of
three cycles and by lemma 3.2, we are done. Suppose $\sigma$ has even length
$\sigma=(a_{1}\;a_{2}\cdots a_{k}).$

$(a_{1}\;a_{2}\cdots a_{k})=(a_{1}\;a_{2}\cdots a_{k-1})(a_{k-1}\;a_{k}).$

$(a_{1}\;a_{2}\cdots a_{k-1})$ is a cycle of odd length and by lemma 3.7, we
can write the inverse of the transposition. ∎

######  Example 3.9.

Let $\sigma=(a_{1}\;a_{2}\;a_{3})(a_{4}\;a_{5}\;a_{6}\;a_{7})\in S_{n}$. Then

$\displaystyle(a_{1}\;a_{2}\;a_{3})^{-1}$
$\displaystyle=(a_{1}\;a_{3}\;[x])(a_{3}\;a_{2}\;[x]^{-1})$
$\displaystyle(a_{4}\;a_{5}\;a_{6}\;a_{7})^{-1}$
$\displaystyle=((a_{4}\;a_{5}\;a_{6})(a_{6}\;a_{7}))^{-1}$
$\displaystyle=(a_{6}\ [z]^{-1}\ [y]^{-1}\ a_{7})(a_{6}\ [w]^{-1}\ a_{7}\
[z])([w]\ a_{6}\ [y]\ a_{7})(a_{4}\;a_{6}\;[x])(a_{6}\;a_{5}\;[x]^{-1})$

∎

##  4\. Optimality for 3-machines

In our context, an optimal solution is defined to have the least possible
number of machine uses. Evans et al. previously explored the problem of
optimizing the solution to Keeler’s Theorem using the 2-machine [5]. Keeler’s
original 2-machine solution has been shown to be optimal only when the number
of disjoint cycles $r$ that make up the original permutation is equal to 1 or
2. Evans et al. found an optimal solution for the case in which $r\geq 3$ [5].
We first expand this question by looking at the optimal solution for
3-machines.

######  Definition 4.1.

For the rest of this section, we define
$\varphi=\\{a_{1},a_{2},\cdots,a_{n}\\}$ to be the set of elements that
$S_{n}$ acts on. Specifically, if $S$ denotes the symmetric group, we have
$S_{n}=S(\varphi)$. ∎

######  Definition 4.2.

We denote the set of $d$ outsiders as $X=\\{x_{1},\cdots x_{d}\\}$. We then
define $\varphi\cup X$ to be the set of elements that $A_{n+d}$ acts on (in
other words $A_{n+d}=A(\varphi\cup X)$). ∎

######  Definition 4.3.

Let $\alpha\in S_{n+1}\setminus S_{n}$ be written as a product of disjoint
cycles $\alpha=\tau_{1}\cdots\tau_{r}$, where each $\tau_{i}$ with $1\leq
i\leq r$ has length $k_{i}\geq 2$. Then,

(4.4) $C(\alpha)=\sum_{i=1}^{r}\sum_{\begin{subarray}{c}a_{j}\in\varphi\\\
\tau_{i}(a_{j})\neq a_{j}\end{subarray}}1.$

In words, $C(\alpha)$ is the number of times that any element from $\varphi$
shows up in a $\tau_{i}$ cycle. ∎

######  Lemma 4.5.

Let $\beta$ be a product of 3-cycles in $S_{n+1}\setminus S_{n}$ such that
each 3-cycle contains $x$. Then the number of 3-cycles composing $\beta$ is
$\frac{C(\beta)}{2}$.

###### Proof.

Every 3-cycle is in $S_{n+1}\setminus S_{n}$ and contains $x$. This means that
exactly 2 elements of any given cycle in $\beta$ must be in $\varphi$. Thus,
$C(\beta)$ is two times the number of cycles, giving the number of cycles as
$C(\beta)/2$. ∎

######  Remark 4.6.

Let $\sigma\in A_{n}$ be written as a product of $r$ disjoint cycles,
$\sigma=\tau_{1}\cdots\tau_{r}$, where $\tau_{i}$ is a $k_{i}$-cycle with
$k_{i}\geq 2$. We will assume for all of this section that
$k_{1}+k_{2}+\cdots+k_{r}=n$. This assumption does not present an isuse,
because if $k_{1}+k_{2}+\cdots+k_{r}=\ell<n$, there are $n-\ell$ objects that
remain unpermuted by $\sigma$ and thus don’t need fixing, while the $\ell$
elements that are permuted can be fixed by mimicking the following arguments
with $n$ replaced by $\ell$ [5].

######  Theorem 4.7.

Let $\sigma\in A_{n}$ be written as a product of $r$ disjoint cycles,
$\sigma=\tau_{1}\cdots\tau_{r}$, where $\tau_{i}$ is a $k_{i}$-cycle with
$k_{i}\geq 2$ and $k_{1}+\cdots+k_{r}=n$. Consider outsider $x$ which
$S_{n+1}$ acts on. We can write $\sigma^{-1}\in S_{n+1}\setminus S_{n}$ as a
product of ${(n+r)\over 2}$ 3-cycles, each of which contains $x$. Further,
this solution is optimal in that any construction of $\sigma^{-1}$ must have
at least ${(n+r)\over 2}$ steps.

###### Proof.

Let $\sigma=\tau_{1}\cdots\tau_{r}$, with each $\tau_{i}$ a disjoint cycle.

We rewrite the equation as
$\sigma=\tau_{1}\cdots\tau_{q}\tau_{q+1}\cdots\tau_{r}$, with
$\tau_{1}\cdots\tau_{q}$ representing cycles of odd length and
$\tau_{q+1}\cdots\tau_{r}$ representing cycles of even length. Even-length
cycles have odd parity, and thus must occur in pairs. Corresponding to an
arbitrary pair of even-length cycles $\tau_{v}=(b_{1}\cdots b_{k_{1}})$ and
$\tau_{w}=(c_{1}\cdots c_{k_{2}})$, we define

$G(\tau_{v},\tau_{w})=(c_{1}\;c_{k_{2}}\;x)\bigg{[}\prod_{\begin{subarray}{c}\ell=2\\\
\text{even}\end{subarray}}^{k_{2}-2}(c_{\ell+1}\;c_{\ell}\;x)\bigg{]}(b_{1}\;b_{k_{1}}\;x)\bigg{[}\prod_{\begin{subarray}{c}\ell=2\\\
\text{even}\end{subarray}}^{k_{1}-2}(b_{\ell+1}\;b_{\ell}\;x)\bigg{]}(c_{k_{2}}\;b_{k_{1}}\;x).$

Corresponding to an arbitrary odd-length cycle $\tau_{u}=(a_{1}\cdots a_{k})$,
we define

$F(\tau_{u})=\bigg{[}\prod_{\begin{subarray}{c}\ell=2\\\
\text{even}\end{subarray}}^{k-1}(a_{\ell+1}\;a_{\ell}\;x)\bigg{]}(a_{2}\;a_{1}\;x).$

Then we set

$\sigma^{-1}=F(\tau_{1})\cdots F(\tau_{q})\cdot G(\tau_{q+1},\tau_{q+2})\cdots
G(\tau_{r-1},\tau_{r}).$

It can be verified that $\sigma^{-1}$ is indeed the inverse of $\sigma$ and
that it is made up of $\frac{(n+r)}{2}$ steps.

We will now prove that if $\sigma^{-1}\in S_{n+1}\setminus S_{n}$ is written
as a product of 3-cycles, it must have at least $\frac{(n+r)}{2}$ elements of
$\varphi$. By Lemma 4.5, we just need to show that $C(\sigma^{-1})\geq n+r$.

We first note that every element of $\varphi$ has had its mind permuted away
from its body. This is true because we know that the lengths of the $\tau_{i}$
cycles sum to $n$ and that all $\tau_{i}$ cycles are disjoint. In order to
return each element’s mind to its body, the element must therefore be permuted
again in the inverse, giving $C(\sigma^{-1})\geq n$.

For the following argument, we also specify that every $\tau_{i}$ cycle is
written with $x$ as the rightmost entry.

We will now show that every cycle $\tau_{i}$ must have one element from
$S_{n}$ that shows up at least twice in $\sigma^{-1}$. Since there are $r$
cycles, this will mean that $C(\sigma^{-1})\geq n+r$.

Observe cycle $\tau_{i}\in\sigma$ for some $1\leq i\leq r$, and let $\gamma$
be the set of elements of $\varphi$ that are permuted by $\tau_{i}$. Next,
find the right most element of $\gamma$ in $\sigma^{-1}$, and call the cycle
that this right-most element lies in $T$.

There are three cases for how $T$ could look, which correspond to the (sum of
binomial coefficients) $\binom{2}{1}+\binom{2}{2}$ ways to have $x$ and at
least one $\gamma$ element in $T$. First, it could look like
$(a_{i,1}\;a_{i,2}\;x)$ for some elements $a_{i,1},a_{i,2}\in\gamma$. It could
also look like $(a_{i,3}\;u\;x)$ for some $u$ in a different $\tau$ cycle and
$a_{i,3}\in\gamma$. Finally, it could look like $(v\;a_{i,4}\;x)$ for some $v$
in a different $\tau$ cycle and $a_{i,4}\in\gamma$.

For our first case where $T=(a_{i,1}\;a_{i,2}\;x)$, we note that $a_{i,1}$
gets whatever mind was in $x$’s body. Because $T$ is the farthest right (and
thus chronologically first) cycle in $\sigma^{-1}$ containing elements of
$\gamma$, $x$ must have its own mind or the mind of an element in
$\varphi\setminus\gamma$. So, $a_{i,1}$ gets a mind that is not from $\gamma$.
This means that $a_{i,1}$ definitely does not have its own mind at this point,
so it must be used again in another 3-cycle in $\sigma^{-1}$ to get its mind
back.

We then look at the case that $T=(a_{i,3}\;u\;x)$. Notice that $a_{i,3}$ gets
the mind that was in $x$’s body. For the same reasoning as before, $a_{i,3}$
must get used again in another $3$-cycle in $\sigma^{-1}$ to get its mind
back.

If $T=(v\;a_{i,4}\;x)$, then $a_{i,4}$ gets the mind that $v$ had. Since $T$
is the farthest right 3-cycle in $\sigma^{-1}$ containing elements of
$\gamma$, $v$’s body must have had $x$’s mind or a mind from
$\varphi\setminus\gamma$. So, $a_{i,4}$ must be used at least twice in
$\sigma^{-1}$.

We have shown that for an arbitrary cycle $\tau_{i}\in\sigma$, at least one
element of $\tau_{i}$ must show up twice in $\sigma^{-1}$. This is true for
all $r$ cycles in $\sigma$, so $C(\sigma^{-1})\geq n+r$. Lemma 4.5 tells us
that $\sigma^{-1}$ must have at least $\frac{(n+r)}{2}$ steps, completing our
proof. ∎

######  Lemma 4.8.

Let $\sigma\in S_{n}$ be written as a product of $r$ disjoint cycles as
$\sigma=\tau_{1}\cdots\tau_{r}$, where $\tau_{i}$ is a $k_{i}$-cycle with
$k_{i}\geq 2$ and $k_{1}+\cdots+k_{r}=n$. For $d\geq 1$, $\sigma^{-1}\in
S_{n+d}\setminus S_{n}$ satisfies $C(\sigma^{-1})\geq n+r$.

###### Proof.

This is a generalization of the argument made in Theorem 4.7, but with any
number of outsiders. For an arbitrary cycle $\tau_{i}\in\sigma$, define
$T\text{ and }\gamma$ as in Theorem 4.7. There are two general cases: there is
an element of $\gamma$ in the far left position of $T$, or not. Assume that
all 3-cycles in $\sigma^{-1}$ are written with any outsiders as far right as
possible.

If there is an element of $\gamma$ in the far left position of $T$, then $T$
looks like $(a_{i,1}\;b\;x_{j,1})$ for $a_{i,1}\in\gamma$, $b$ arbitrary, and
$x_{j,1}\in\\{x_{1},\cdots,x_{d}\\}$. By construction, $x_{j,1}$ does not
contain a mind from $\gamma$. So, $a_{i,1}$ gets a mind from outside of
$\gamma$, which cannot be its own mind. This means $a_{i,1}$ must be used at
least twice in $\sigma^{-1}$, and since this was true for all cycles,
$C(\sigma^{-1})\geq n+r$.

In the case that there is not an element of $\gamma$ in the far left position
of $T$, then $T$ looks like $(c\;a_{i,2}\;x_{j,2})$ for
$c\notin\gamma\cup\\{x_{1},\cdots,x_{d}\\}$, $a_{i,2}\in\gamma$, and
$x_{j,2}\in\\{x_{1},\cdots,x_{r}\\}$. By construction, $c$ cannot contain a
mind from $\gamma$. So, $a_{i,2}$ gets this mind from outside of $\gamma$,
again giving $C(\sigma^{-1})\geq n+r$. ∎

######  Corollary 4.9.

Let $\sigma\in S_{n}$ be written as a product of $r$ disjoint cycles as
$\sigma=\tau_{1}\cdots\tau_{r}$, where $\tau_{i}$ is a $k_{i}$-cycle with
$k_{i}\geq 2$ and $k_{1}+\cdots+k_{r}=n$. Then, $\sigma^{-1}\in
S_{n+d}\setminus S_{n}$ will take at least $\frac{(n+r)}{2}$ steps for all
$d\geq 2$.

###### Proof.

Lemma 4.8 says that $\sigma^{-1}$ must satisfy $C(\sigma^{-1})\geq n+r$. But,
having at least one outsider per 3-cycle (regardless of which outsider it is)
means that there can be at most 2 elements of $\varphi$ in each 3-cycle. This
means $\sigma^{-1}$ must have at least $\frac{(n+r)}{2}$ steps, as desired. ∎

##  5\. An Infinitely Large Machine

Here we present an infinite analogy of the machine. Consider a machine that
takes a set of people enumerated by the natural numbers and that permutes
their minds as follows.

$\displaystyle 1$ $\displaystyle\to 2$ $\displaystyle 2$ $\displaystyle\to 3$
$\displaystyle\vdots$

This can be denoted as a function $f:\mathbb{N}\to\mathbb{N}$ defined as
$f(n)=n+1$.

$\displaystyle f=1\to 2\to 3\cdots$

We extend the rules to this infinite case as follows.

  1. (1)

Each seat must be occupied in order for the machine to work.

  2. (2)

Once a collection of people have used the machine, that same collection cannot
use the machine again.

This case differs since we are not working with bijective functions so there
may be bodies that remain with no machine. Swaps that do this will be called
forgetful. In the example above, no one will occupy body $1$. If the machine
is only able to do forgetful swap, we would have no hope of fixing everyone as
in every swap as someone will always remain mindless. Therefore, we give the
machine another capability, to change direction in which minds are swapped:

$\displaystyle 2$ $\displaystyle\to 1$ $\displaystyle 3$ $\displaystyle\to 2$
$\displaystyle\vdots$

This can be denoted as a function $g:\mathbb{N}\to\mathbb{N}$ defined as
$g(n)=n-1$. Written in one line,

$\displaystyle g=\cdots 3\to 2\to 1$

it is more clear to see why we say the machine can ”change direction”. We will
only use this kind of swapping when the first person (in this case body 1) has
no mind occupying it (else body 1 would end up with two minds occupying it).
We will call this type of swapping retentive, as in no bodies remain mindless.
While the swapping above would solve our original problem, it is not allowed
under our rules as it swaps the same set of people. To summarize, here is an
outline of our rules.

  1. (1)

Each seat must be occupied in order for the machine to work.

  2. (2)

Mindless bodies will remain on the machine.

  3. (3)

Once a collection of people have used the machine, that same collection cannot
use the machine again. Individuals can use the machine many times.

  4. (4)

The machine can do forgetful swaps.

  5. (5)

The machine can do retentive swaps.

We show the following results:

######  Lemma 5.1.

Let $f_{0}:\mathbb{N}\to\mathbb{N}$ defined as $f_{0}(n)=n+1$. Then there
exist $f_{1}$, $f_{2}$, and $f_{3}$ where $f_{1}$, $f_{3}$ are retentive and
$f_{2}$ is forgetful, such that $dom(f_{i})\neq dom(f_{j})$ for all $i\neq j$,
and $f^{-1}_{0}=f_{3}\circ f_{2}\circ f_{1}$.

######  Proposition 5.2.

Given a countably infinite set $X$, any permutation $\sigma\in S_{fin}(X)$ and
its inverse can be written as a composition of forgetful and retentive swaps
each with unique domain.

######  Theorem 5.3.

Let $X$ be a countably infinite set, $\sigma\in S_{fin}(X)$. Then there exist
$f_{1}$ and $f_{2}$, which are forgetful and retentive respectively, such that
$dom(f_{1})\neq dom(f_{2})$ and $\sigma^{-1}=f_{2}\circ f_{1}$.

###  5.1. Finite Disjoint Uses

In this case, we will suppose a countable set of people enumerated by
$\mathbb{N}$ have used the machine. The machine does the swap
$f:\mathbb{N}\to\mathbb{N}$ as $f(n)=n+1$. As in the finite case, we will
introduce an outsider who has not used the machine. Let $z$ denote this
outsider. We can undo $f$ in the following steps.

  * Step 1:

$\displaystyle 2$ $\displaystyle\to 1$ $\displaystyle z$ $\displaystyle\to 2$
$\displaystyle 3$ $\displaystyle\to z$ $\displaystyle 4$ $\displaystyle\to 3$
$\displaystyle 5$ $\displaystyle\to 4$ $\displaystyle\vdots$

  * Step 2:

$\displaystyle z$ $\displaystyle\to 2$ $\displaystyle 2$ $\displaystyle\to 3$
$\displaystyle 3$ $\displaystyle\to 4$ $\displaystyle 4$ $\displaystyle\to 5$
$\displaystyle 5$ $\displaystyle\to 6$ $\displaystyle\vdots$

  * Step 3:

$\displaystyle 3$ $\displaystyle\to z$ $\displaystyle 4$ $\displaystyle\to 3$
$\displaystyle 5$ $\displaystyle\to 4$ $\displaystyle 6$ $\displaystyle\to 5$
$\displaystyle 7$ $\displaystyle\to 6$ $\displaystyle\vdots$

The original swap and map in step 1 can be defined as

(5.4) $\displaystyle f(x)=x+1\qquad f_{1}(x)=\begin{cases}2&\text{ if
$x=z$}\\\ z&\text{ if $x=3$}\\\ x-1&\text{ else}.\end{cases}$

We can analogously define step 2 and step 3. The piecewise functions can be
written more concisely using an extension of cycle notation. For example,

(5.5) $f=(1\;2\;3\;4\cdots)\qquad f_{1}=(\cdots 4\;3\;x\;2\;1).$

In the cycle notation, each person has their mind sent to the person to their
right. Notice that forgetful swaps trail off on the right while retentive ones
trail off on the left. This notation makes the proof of the following lemma
much easier to write:

######  Lemma 5.6.

Let $f_{0}:\mathbb{N}\to\mathbb{N}$ defined as $f_{0}(n)=n+1$. Then there
exist $f_{1}$, $f_{2}$, and $f_{3}$ where $f_{1}$, $f_{3}$ are retentive and
$f_{2}$ is forgetful, such that $dom(f_{i})\neq dom(f_{j})$ for all $i\neq j$,
and $f^{-1}_{0}=f_{3}\circ f_{2}\circ f_{1}$.

###### Proof.

Define

$\displaystyle f_{1}$ $\displaystyle=(\cdots 4\;3\;x\;2\;1)$ $\displaystyle
f_{2}$ $\displaystyle=(x\;2\;3\;4\cdots)$ $\displaystyle f_{3}$
$\displaystyle=(\cdots 5\;4\;3\;x).$

Then $dom(f_{0})=\mathbb{N}$, $dom(f_{1})=\mathbb{N}\cup\\{z\\}$,
$dom(f_{2})=dom(f_{1})\setminus\\{1\\}$, and
$dom(f_{3})=dom(f_{1})\setminus\\{1,2\\}$. By tracing elements, we see that
$f^{-1}_{0}=f_{3}\circ f_{2}\circ f_{1}$. ∎

We can generalize the swap as follows. Let $X$ denote a countably infinite set
of people, defined as $X=\\{a_{1},a_{2},\cdots\\}$, that uses the machine. The
machine does the swap defined by the function $f:X\to X$, $f(a_{n})=a_{n+1}$.
Define

$\widehat{f}=(\cdots
a_{5}\;a_{4}\;a_{3}\;x)(x\;a_{2}\;a_{3}\;a_{4}\cdots)(\cdots
a_{4}\;a_{3}\;x\;a_{2}\;a_{1})$

and from the lemma, it is immediate to show $f^{-1}=\widehat{f}$.

######  Corollary 5.7.

Let $X_{1},\cdots,X_{n}$ be countably infinite, pairwise disjoint subsets of
$X$ where $X_{i}=\\{x_{i,j}\\}_{j\in\mathbb{N}}$. Define $f:X\to X$ by
$f(x)=g_{1}\circ\cdots\circ g_{n}$ where

$g_{i}(x)=(x_{i,1}\;x_{i,2}\;x_{i,3}\cdots)=\begin{cases}x&\text{ if $x\notin
X_{i}$}\\\ x_{i,j+1}&\text{ if $x\in X_{i}$}\end{cases}$

Then $f^{-1}=\widehat{g}_{n}\circ\cdots\circ\widehat{g}_{1}$.

###  5.2. Finitary Permutations

Let $X$ be a countably infinite set, and $S(X)$ the permutation group on $X$.
Let $S_{fin}(X)$ be the subgroup of $S(X)$ consisting of permutations of $X$
which fix all but finitely many elements of $X$. We call $\sigma\in S(X)$ a
finitary permutation if $\sigma\in S_{fin}(X)$. As it turns out, we can obtain
any finitary permutation from swaps using the machine under our restrictions.
We start with cycles.

######  Lemma 5.8.

Let $X$ be a countably infinite set, $a_{1},\cdots,a_{n}\in X$. Then there
exists $f_{1}$ and $f_{2}$, forgetful and retentive respectfully, such that
$dom(f_{1})\neq dom(f_{2})$ and $(a_{1}\;\cdots\;a_{n})=f_{2}\circ f_{1}$.

###### Proof.

Let $f=(a_{1}\;a_{2}\cdots a_{n})$, then

$f=(\cdots a_{n+2}\;a_{n+1}\;a_{n})(a_{1}\;a_{2}\cdots a_{n}\;a_{n+1}\cdots)$

∎

######  Example 5.9.

Let $f=(a_{1}\;a_{2})$ and $z\notin X$. Then the transposition is solved by:

  * Step 1:

$\displaystyle a_{1}$ $\displaystyle\to a_{2}$ $\displaystyle a_{2}$
$\displaystyle\to z$ $\displaystyle z$ $\displaystyle\to a_{3}$ $\displaystyle
a_{3}$ $\displaystyle\to a_{4}$ $\displaystyle a_{4}$ $\displaystyle\to a_{5}$
$\displaystyle\vdots$

  * Step 2:

$\displaystyle z$ $\displaystyle\to a_{1}$ $\displaystyle a_{3}$
$\displaystyle\to z$ $\displaystyle a_{4}$ $\displaystyle\to a_{3}$
$\displaystyle a_{5}$ $\displaystyle\to a_{4}$ $\displaystyle a_{6}$
$\displaystyle\to a_{5}$ $\displaystyle\vdots$

In cycle notation,

$(a_{1}\;a_{2})^{-1}=(a_{1}\;a_{2}\;z\;a_{3}\;a_{4}\cdots)(\cdots
a_{5}\;a_{4}\;a_{3}\ z\ a_{1})$

∎

######  Lemma 5.10.

Let $X$ be a countably infinite set, $a_{1},\cdots,a_{n}\in X$, and $z\notin
X$. Then there exists $f_{1}$ and $f_{2}$, forgetful and retentive
respectfully, such that $z\in dom(f_{1}),dom(f_{2})$, $dom(f_{1})\neq
dom(f_{2})$, and $(a_{1}\;\cdots\;a_{n})^{-1}=f_{2}\circ f_{1}$.

###### Proof.

$(a_{1}\;a_{2}\cdots a_{k})^{-1}=(\cdots a_{k+2}\ a_{k+1}\ z\
a_{1})(a_{1}\;a_{k}\ a_{k-1}\cdots a_{3}\;a_{2}\;z\;a_{k+1}\ a_{k+2}\cdots)$ ∎

Let $\sigma\in S_{fin}(X)$ be the cycle $\sigma=(a_{1}\;a_{2}\cdots a_{k})$
and define

$\sigma^{*}=(\cdots a_{k+2}\ a_{k+1}\ z\ a_{1})(a_{1}\;a_{k}\;a_{k-1}\cdots
a_{3}\;a_{2}\;z\;a_{k+1}\;a_{k+2}\cdots)$

Then from the above lemma, $\sigma^{*}=\sigma^{-1}$.

######  Proposition 5.11.

Given a countably infinite set $X$, any permutation $\sigma\in S_{fin}(X)$ and
its inverse can be written as a composition of forgetful and retentive swaps
each with unique domain.

###### Proof.

Since $\sigma\in S_{fin}(X)$, there exist disjoint cycles
$\tau_{1},\cdots\tau_{m}\in S_{fin}(X)$, such that
$\sigma=\tau_{1}\cdots\tau_{m}$. Then
$\sigma^{-1}=\tau^{*}_{m}\cdots\tau^{*}_{1}$. Then we are done since the fact
that each has a unique domain follows from the cycles being disjoint. ∎

Since each $\tau^{*}_{i}$ uses two swaps on the machine, the total number of
swaps needed to write $\sigma^{-1}$ is $2m$. We can do better. Consider
$\sigma=(a_{1}\;a_{2})(a_{3}\;a_{4}\;a_{5})$. Applying our solution from
before we know
$(a_{1}\;a_{2})^{-1}=(a_{1}\;a_{2}\;z\;a_{3}\;a_{4}\cdots)(\cdots
a_{5}\;a_{4}\;a_{3}\;z\;a_{1})$. Examine the left permutation:
$(a_{1}\;a_{2}\;z\;a_{3}\;a_{4}\;a_{5}\cdots).$ For fixing $(a_{1}\;a_{2})$,
the only part of this permutation that is important is $a_{1}\to a_{2}\to z$.
So we can change it to $(a_{1}\;a_{2}\;z\;a_{5}\;a_{4}\;a_{3}\cdots)$. Notice
this fixes $a_{4}$ and $a_{3}$ along with our intention to fix $a_{2}$. We can
generalize this idea to obtain a much more efficient solution.

######  Example 5.12.

$\sigma=(a_{1}\;a_{2})(a_{3}\;a_{4}\;a_{5})$

Let $z\notin X$. Then the problem is solved by:

  * Step 1:

$\displaystyle a_{1}$ $\displaystyle\to a_{2}$ $\displaystyle a_{2}$
$\displaystyle\to z$ $\displaystyle z$ $\displaystyle\to a_{5}$ $\displaystyle
a_{5}$ $\displaystyle\to a_{4}$ $\displaystyle a_{4}$ $\displaystyle\to a_{3}$
$\displaystyle a_{3}$ $\displaystyle\to a_{6}$ $\displaystyle a_{6}$
$\displaystyle\to a_{7}$ $\displaystyle\vdots$

  * Step 2:

$\displaystyle z$ $\displaystyle\to a_{1}$ $\displaystyle a_{5}$
$\displaystyle\to z$ $\displaystyle a_{6}$ $\displaystyle\to a_{5}$
$\displaystyle a_{7}$ $\displaystyle\to a_{6}$ $\displaystyle\vdots$

In cycle notation: $((a_{1}\;a_{2})(a_{3}\;a_{4}\;a_{5}))^{-1}=(\cdots
a_{7}\;a_{6}\;a_{5}\;z\;a_{1})(a_{1}\;a_{2}\;z\;a_{5}\;a_{4}\;a_{3}\;a_{6}\;a_{7}\cdots)$.
∎

Generalizing this solution allows us to fix any finitary permutation in just 2
steps. We create some notation for an arbitrary cycle:

Let $[a]_{k}:=a_{1}\ \cdots a_{k}$ and $[a]^{-1}_{k}:=a_{k}\ \cdots a_{1}$ we
write

$\displaystyle(a_{1}\cdots a_{k})=([a]_{k})$ $\displaystyle(a_{k}\cdots
a_{1})=([a]^{-1}_{k})$

Note that $([a]_{k})^{-1}=([a]^{-1}_{k})$.

######  Theorem 5.13.

Let $X$ be a countable infinite set, $\sigma\in S_{fin}(X)$. Then there exist
$f_{1}$ and $f_{2}$, which are forgetful and retentive respectively, such that
$dom(f_{1})\neq dom(f_{2})$ and $\sigma^{-1}=f_{2}\circ f_{1}$.

###### Proof.

Let $\sigma=\tau_{1}\cdots\tau_{m}$ be the cycle decomposition. Let
$\tau_{i}=([a_{i}]_{k_{i}})$. Then

$\sigma=([a_{1}]_{k_{1}})([a_{2}]_{k_{2}})\cdots([a_{m}]_{k_{m}})$

. And thus by tracing elements one can see:

$\sigma^{-1}=(b_{3}\ b_{2}\ b_{1}\ a_{m,k_{m}}\cdots a_{2,k_{2}}\ x\
a_{1,k_{1}})([a_{1}]^{-1}_{k_{1}}\ x\
[a_{2}]^{-1}_{k_{2}}[a_{3}]^{-1}_{k_{3}}\cdots[a_{m}]^{-1}_{k_{m}}\ b_{1}\
b_{2}\ b_{3}\cdots)$

where the $b_{j}\in X$ not permuted by any $\tau_{i}$ for any $i$. ∎

##  6\. Future Directions

In our finite case, we only proved optimally for when $n=3$ so a natural
extension is to prove optimally for any $n\in\mathbb{N}$. A noteworthy
observation in the $3$ cycle case, each product in the solution is a distinct
$3$ cycle. As an example, consider the solution for when the machine permutes
$3$ people.

(6.1) $(1\;2\;3)=(3\;1\;x_{1})(2\;3\;x_{1})(1\;2\;x_{1})$

Since each $3$ cycle is distinct, then they correspond to a unique triangle on
the graph with vertices $\\{1,2,3,x_{1}\\}$. If we count all possible distinct
triangles that have at least $x_{1}$ in the graph, this places an lower bound
for the the total number of moves required. It would be interesting to see if
these ideas carry over to more general cases.
In the infinite case we lost a group structure when we considered a machine
that does $n+1$ and $n-1$ on $\mathbb{N}$. It would be interesting to explore
the scenario with a group structure by considering a machine that does $n+1$
and $n-1$ on $\mathbb{Z}$. One could also look at a machine that preforms a
different permutation on a countable set. For a countably infinite set $X$,
one could consider a finite machine that only cycles $m$-people.

## References

  * [1] Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller, and Peter M. Neumann.  Notes on Infinite Permutation Groups.  Number no. 1689 in Lecture Notes in Mathematics. Springer, 1998.
  * [2] David S. Dummit and Richard M. Foote.  Abstract Algebra, 3rd Edition.  Wiley, 7 2003.
  * [3] Jennifer Elder.  Generalizing the futurama theorem.  Master’s thesis, California State University, Fresno, 2016.
  * [4] Jennifer Elder and Oscar Vega.  Generalizing the futurama theorem, 2016.
  * [5] Ron Evans, Lihua Huang, and Tuan Nguyen.  Keeler’s theorem and products of distinct transpositions, 2012.
  * [6] Joseph A. Gallian.  Contemporary Abstract Algebra.  Textbooks in Mathematics. CRC Press, 2021.
  * [7] Futurama Wiki.  The prisoner of benda.  https://futurama.fandom.com/wiki/The_Prisoner_of_Benda”.  Accessed: 2023-07-17.