Théorème de Keeler

La preuve de l'énoncé est donnée dans son intégralité dans l'épisode^[9]. Toute permutation pouvant être décomposée en permutations circulaires disjointes, il est possible de démontrer le théorème pour un k-cycle sans perdre sa généralité.

Soit ${\displaystyle \pi }$ un k-cycle du groupe symétrique ${\displaystyle S_{n}}$ qui s'écrit sous la forme ${\displaystyle \pi ={\begin{pmatrix}1&2&\dots &k&k+1&\dots &n\\2&3&\dots &1&k+1&\dots &n\end{pmatrix}}}$.

On note ${\displaystyle \langle a,b\rangle }$ la transposition des éléments ${\displaystyle a}$ et ${\displaystyle b}$, puis on introduit deux nouveaux éléments ${\displaystyle \{x,y\}}$ tels qu'on obtient ${\displaystyle \pi '={\begin{pmatrix}1&2&\dots &k&k+1&\dots &n&x&y\\2&3&\dots &1&k+1&\dots &n&x&y\end{pmatrix}}}$.

Pour tout ${\displaystyle i}$ allant de ${\displaystyle 1}$ à ${\displaystyle k}$, on pose ${\displaystyle \sigma }$ la série de transpositions : ${\displaystyle \sigma =(\langle x,1\rangle \langle x,2\rangle \dots \langle x,i\rangle )(\langle y,i+1\rangle \langle y,i+2\rangle \dots \langle y,k\rangle )(\langle x,i+1\rangle )(\langle y,i\rangle )}$.

On remarque que chaque transposition de ${\displaystyle \sigma }$ est composée d'un élément de ${\displaystyle S_{n}}$ et d'un élément de ${\displaystyle \{x,y\}}$, donc il n'y a aucune répétition avec les permutations ayant créé ${\displaystyle \pi }$ ni avec la transposition ${\displaystyle \langle x,y\rangle }$.

Ceci permet d'obtenir que ${\displaystyle \pi '\circ \sigma ={\begin{pmatrix}1&2&\dots &k&k+1&\dots &n&x&y\\1&2&\dots &k&k+1&\dots &n&y&x\end{pmatrix}}}$. Autrement dit, ${\displaystyle \sigma }$ inverse le k-cycle ${\displaystyle \pi }$ et intervertit ${\displaystyle x}$ et ${\displaystyle y}$.

Ainsi, toute permutation de ${\displaystyle S_{n}}$ peut être inversée, en la décomposant sous forme d'un ou plusieurs k-cycles. Puis, si besoin, il est possible d'appliquer la transposition ${\displaystyle \langle x,y\rangle }$.

En 2016, Jennifer Elder et Oscar Vega publient Generalizing the Futurama Theorem dans lequel, en plus de donner une autre preuve au théorème de Keeler, généralisent son fonctionnement dans le cas de permutation de p-cycle où p est un nombre premier différent de 2. Dans le cas particulier d'un 3-cycle, il est possible d'inverser la permutation à l'aide d'un seul élément extérieur. Dans les autres cas, il y a toujours la possibilité d'inverser la permutation à l'aide d'éléments extérieurs^[10].

En 2012, Lihua Huang et al. développent un algorithme plus efficace quant à la permutation d'éléments, basé sur l'algorithme de Keeler. Ces deux algorithmes possèdent en fait la même complexité en ${\displaystyle O(t^{2})}$^[11],[12], et en 2014, ils cherchent le nombre minimal de permutations nécessaire. Dans la même étude, ils s'intéressent à l'épisode Transfert de la saison 2 de Stargate SG-1 qui propose un scénario similaire à l'épisode de Futurama^[13]. En 2023, Alexandra Barta et al. trouvent une solution plus efficace pour un 3-cycle^[14].

• Portail de l’algèbre