Keeler's Theorem: Body Swap Machine and Affine Transpositions

With n bodies, the number of unique pairs is n(n-1)/2. Each pair can be used at most once. That is the total budget of swaps available:

With n=2, one swap exhausts the only pair. The two people are stuck in each other's bodies with no way back. That is the inciting incident of the episode — and the k=2 base case of the theorem.

Keeler proved (on the show's blackboard) that introducing just two fresh people who have never swapped with anyone is always enough to fix everyone, no matter how tangled the swaps have become.

Keeler (2010, blackboard in "The Prisoner of Benda"):

For n >= 2, the inverse of any pi in S_n is a product of distinct transpositions in S_n+2 \ S_n.

The repair transpositions each move x or y. Distinctness from the history that produced pi is therefore structural: history edges lie in Sym2 [n], repair edges each touch {x,y}. No bookkeeping over the history is required.

This is an affine resource discipline: each edge of Sym2 beta is a consumable resource, used at most once across the entire trace (history ++ repair).

The transform codec pipeline operates on the same structure. Each codec step is a function; an involution (like rot13) is a transposition in function space. The "reverse pipeline" is the inverse permutation. Both are symmetric group actions with a no-reuse constraint on transpositions.

A browser-based body swap simulator at /tools/body-swap/:

The tool lets you build a permutation by clicking pairs, watch the cycle structure change, then run Keeler's repair step-by-step with two fresh Globetrotters. Each pair dims after use – the affine constraint is visible.

ClojureScript + shadow-cljs, matching the transform tool's build:

The repair procedure for a single k-cycle (c_0 c_1 ... c_{k-1}):

(defn repair-cycle
  "Keeler's blackboard formula for one cycle.
   Returns a sequence of swaps using fresh bodies :x and :y."
  [cycle]
  (let [k (count cycle)]
    (concat
      ;; swap x with each element except the last
      (map (fn [c] #{:x c}) (butlast cycle))
      ;; swap y with the last, then x with the last, then y with the first
      [#{:y (last cycle)}
       #{:x (last cycle)}
       #{:y (first cycle)}])))

(defn repair-permutation
  "Apply Keeler's theorem: decompose into cycles, repair each.
   Each cycle repair transposes x<->y. If odd number of cycles,
   x and y end up swapped -- add a final [x y] to fix."
  [perm x y]
  (let [cycles (perm->cycles perm)
        swaps (vec (mapcat #(repair-cycle % x y) cycles))
        after (apply-swaps perm swaps)]
    (if (= (get after x x) y)
      (conj swaps [x y])  ;; parity correction
      swaps)))

Each cycle repair leaves x and y transposed (always, regardless of cycle length). After repairing all cycles: odd count of nontrivial cycles means x and y are swapped, even means they are fixed. The final [x y] swap corrects the parity.

Fresh bodies x : inr false=, y : inr true=. A repair swap Equiv.swap (inr b) (inl a) is syntactically disjoint from any history swap Equiv.swap (inl a) (inl a').