Théorème de Keeler

Le théorème de Keeler, ou théorème de Futurama, est un théorème mathématique d'algèbre générale de la théorie des groupes. Il est développé en 2010 par le mathématicien et scénariste Ken Keeler pour un épisode de la série Futurama.

Ce théorème démontre que dans un groupe fini, peu importe le nombre de permutations effectuées entre les éléments, il est possible de revenir à la configuration initiale en ajoutant deux nouveaux éléments, en sachant qu'une permutation ne peut être effectuée qu'une fois.

Contexte

Le Prisonnier de Benda

Dans le dixième épisode de la sixième saison de Futurama intitulé Le Prisonnier de Benda, le Professeur Farnsworth et Amy Wong construisent une machine pour échanger les corps ; d'autres personnages échangent également leurs corps entre eux. Cependant, ils se rendent compte que la machine ne peut pas échanger plus de deux fois la même paire de corps. Avec l'aide d'habitants de la planète des Globetrotters, les personnages peuvent revenir dans leurs corps d'origine^[1],[2].

Résolution du problème

Alors qu'ils écrivaient l'épisode, les auteurs se sont rendu compte qu'ils avaient également créé un problème mathématique. Le lendemain, Ken Keeler, titulaire d'un doctorat en mathématiques^[3] et scénariste principal du Prisonnier de Benda, est arrivé avec le théorème permettant de résoudre l'intrigue^[4]. Pour Keeler, faire apparaître la preuve complète à l'écran est un moyen de populariser les mathématiques au sein des jeunes^[1].

Énoncé

L'énoncé du théorème n'a jamais été mathématiquement formulé par l'épisode, contrairement à sa preuve. Aussi, il peut exister plusieurs définitions.

Il peut se définir comme suit :

« Soit ${\displaystyle A}$ un ensemble fini et soient ${\displaystyle x,y}$ deux éléments qui n'appartiennent pas à ${\displaystyle A}$. Toute permutation de ${\displaystyle A}$ peut être réduite à l'identité par une séquence de transpositions de ${\displaystyle A\cup \{x,y\}}$ dont chacune contient soit ${\displaystyle x}$ soit ${\displaystyle y}$^[5]. »

Il peut également être écrit comme :

« Soit ${\displaystyle \pi \in S_{n}}$. Alors il existe ${\displaystyle \sigma \in S_{n+2}}$ produit de transpositions distinctes de ${\displaystyle S_{n+2}-S_{n}}$ tel que ${\displaystyle \pi \circ \sigma =id}$^[6]. »

Preuve

La preuve de l'énoncé est donnée dans son intégralité dans l'épisode^[5]. Toute permutation pouvant être décomposée en permuations ciculaires 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 <a,b>}$ 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 =(<x,1><x,2>\dots <x,i>)(<y,i+1><y,i+2>\dots <y,k>)(<x,i+1>)(<y,i>)}$.

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 <x,y>}$.

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 <x,y>}$.

Applications

Amélioration

En 2012, Lihua Huang et al. développent un algorithme plus optimal 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})}$^[7],[8].

Généralisation

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érieur^[9].

Notes et références

1. (en) Reece Goodall, « Futurama and Keeler’s Theorem », sur The Boar, 8 juillet 2018 (consulté le 14 juin 2024).
2. (en) Alex Kasman, « Futurama (Episode: The Prisoner of Benda) (2011) », sur Mathematical Fiction (consulté le 14 juin 2024).
3. (en) Casey Chan, « Futurama Writer Invented A New Math Theorem Just To Use In The Show », sur Gizmodo, 21 août 2010 (consulté le 17 juin 2024).
4. (en) « Futurama’s Resident Physics Nerd on Math Jokes and Richard Nixon », sur Wired, 9 juillet 2014 (consulté le 17 juin 2024).
5. (es) « El Teorema de Keeler, pertmutaciones y Futurama », sur Blog de la asignatura Álgebra Básica de la Universidad de Sevilla, 17 novembre 2014 (consulté le 15 juin 2024).
6. « Deux (deux ?) minutes pour Futurama », 21 janvier 2015 (consulté le 17 juin 2024)
7. (en) Lihua Huang, Ron Evans et Tuan Nguyen Keeler's theorem and products of distinct transpositions (rapport), 2012, 12 p. (DOI 10.48550/arXiv.1204.6086, arXiv 1204.6086v2, lire en ligne).
8. (en) Yohanssen Pratama « A survey on keeler’s theorem and application of symmetric group for swapping game » (rapport), Journal of Physics Conference Series, n^o 795,‎ janvier 2017 (DOI 10.1088/1742-6596/795/1/012048, lire en ligne).
9. (en) Jennifer Elder et Oscar Vega Generalizing the Futurama Theorem (rapport), 2016, 7 p. (DOI 10.48550/arXiv.1608.04809, arXiv arXiv:1608.04809, lire en ligne).

• Portail de l’algèbre