Le problème qui suit vient d'une suite de réflexions sur le thème des deux dernières entrées, mais peu importe : la question est compréhensible et intéressante en elle-même, elle me semble même très jolie, et elle ne dépend pas de la lecture des entrées en question — je ne vais d'ailleurs quasiment pas expliquer comment je suis arrivé à ce problème (seulement en note en bas).
Je suppose que j'ai 2m symboles, pour un certain
entier m≥1, que je
noterai X1,X2,X3,…,Xm
et X1′,X2′,X3′,…,Xm′ ;
la correspondance entre Xi
et Xi′ est essentielle, et je dirai
que Xi′ est le symbole
complémentaire de Xi et
réciproquement. Je m'intéresse à des cycles de longueur
2m sur ces symboles faisant intervenir chaque symbole une
et une seule fois (le terme cycle
signifie qu'on identifie deux
suites qui s'obtiennent l'un à partir de l'autre par une permutation
cyclique, par
exemple X1,X2,X1′,X2′
s'identifie
à X2,X1′,X2′,X1).
Il existe bien sûr (2m)!/(2m) =
(2m−1)! tels cycles.
On va définir sur les cycles des opérations qui porteront le nom de chiasme de Whitehead (le terme est de moi). Pour définir un chiasme de Whitehead, on commence par choisir un des symboles Z (qui peut être un Xi ou un Xi′) qu'on appellera la base du chiasme ; puis on considère la suite des symboles strictement comprise entre Z et le symbole complémentaire Z′ (c'est-à-dire Xi′ ou Xi si Z vaut Xi ou Xi′ respectivement) qui le suit dans le cycle ; on découpe ce segment de façon quelconque en deux segments consécutifs (non vides si on veut que le chiasme soit non-trivial) et on échange ceux-ci. Voici un exemple : X1,X2,X3,X4,X1′,X2′,X3′,X4′ peut devenir X1,X2,X4,X1′,X3,X2′,X3′,X4′ par un chiasme de Whitehead si on choisit pour base Z=X2 et qu'on découpe le segment X3,X4,X1′ en X3 et X4,X1′ ; en prenant pour base Z=X4′ (et en se souvenant que tout est cylique !), le même cycle X1,X2,X3,X4,X1′,X2′,X3′,X4′ peut devenir X3,X1,X2,X4,X1′,X2′,X3′,X4′.
Remarquons que tout symbole Z peut servir à définir un chiasme de Whitehead (fût-il trivial), puisqu'on peut toujours lire cycliquement jusqu'à tomber jusqu'au symbole complémentaire Z′ qui suit ; si ce dernier survient k symboles plus loin, on pourra faire k−2 chiasmes de Whitehead non triviaux ; et comme le Z′ est lui-même suivi d'un Z (le même qu'au départ) 2m−k symboles plus loin, on peut faire finalement 2m−4 chiasmes de Whitehead non triviaux partant de Z ou Z′ (du moins si ceux-ci ne sont pas immédiatement adjacents, i.e., k≠1,2m−1). Au final, on peut donc faire exactement m(2m−4) chiasmes de Whitehead non-triviaux sur n'importe quel cycle (n'ayant nulle part deux symboles complémentaire adjacents).
Ma question est la suivante : comment peut-on détecter si deux cycles peuvent se déduire l'un de l'autre par une suite de chiasmes de Whitehead, et le cas échéant, comment les produire ? (Il est évident que le problème est décidable puisqu'il est, après tout, fini, mais je demande quelque chose de plus utilisable que l'énumération exhaustive.) Une variante de cette question autorise aussi d'effectuer une permutation des symboles préservant la complémentarité (cf. ci-dessous).
Un point de vue possible, qui simplifie peut-être le problème, ou au contraire le complique, je ne sais pas, consiste à se limiter aux cycles ayant la propriété suivante. Donné un cycle, je peux considérer la fonction qui à un symbole U associe le complémentaire V′ du symbole V qui suit immédiatement U dans le cycle (autrement dit, la fonction composée du cycle considérée interprétée comme une permutation cyclique, et de la fonction « symbole complémentaire ») ; si cette fonction est elle-même un 2m-cycle (c'est-à-dire, si, en partant d'un symbole quelconque et en appliquant successivement cette fonction, on retombe sur le symbole en 2m étapes et pas avant), je dirai que le cycle de départ est parfait, et que l'autre cycle obtenu par cette construction est son dual de Whitehead. Il est clair que le dual de Whitehead est alors lui-même parfait et que son dual est le cycle de départ. Par exemple, le cycle X1,X2,X1′,X2′ est parfait et son dual est X1,X2′,X1′,X2 (i.e., dans ce cas particulier, le cycle inversé), tandis que X1,X2,X3,X1′,X2′,X3′ n'est pas pas parfaite (on tombe sur deux 3-cycle X1,X2′,X3 et X2,X3′,X1′). En fait, si m est impair, aucun cycle (de longueur 2m) n'est jamais parfait (en effet, un 2m-cycle est une permutation impaire, et la fonction « symbole complémentaire » l'est aussi si m est impair, donc la composée ne peut pas être un 2m-cycle). Notons d'ailleurs qu'un cycle parfait ne peut jamais avoir deux symboles complémentaires adjacents.
Il est facile de se convaincre que l'effet d'un chiasme de Whitehead sur le dual d'un cycle parfait est de déplacer le symbole de base d'un endroit à un autre sans changer aucun autre symbole — et notamment, un cycle parfait demeure parfait après application d'un chiasme de Whitehead (ou de façon plus générale, le nombre de cycles du dual ne changerait pas sous l'effet d'un chiasme de Whitehead si on prenait la peine de définir de façon évidente le dual d'un cycle imparfait). On peut se limiter à regarder l'effet des chiasmes de Whitehead sur les cycles parfaits. Ou, si on préfère, sur leur dual (l'effet du chiasme est alors très simple puisqu'on ne déplace qu'un symbole, mais la difficulté est qu'on ne peut pas le déplacer n'importe où).
Si j'ai bien réussi à dérouler[#] et à reformuler une série de résultats autour de la théorie des surfaces qui débutent par un théorème de Whitehead de 1936 (le neveu, pas l'oncle), on peut toujours passer d'un cycle parfait à un autre par une suite de chiasmes de Whitehead, quitte à effectuer, de plus, une permutation des variables préservant la complémentarité (c'est-à-dire qu'on peut renommer Xi en Xj ou Xj′, mais on doit alors renommer Xi′ en Xj′ ou Xj respectivement). Ce que je ne sais pas, c'est par exemple comment produire concrètement une telle suite d'opérations, ou quelle liberté on a dans le processus, ou comment détecter si on a vraiment besoin d'une permutation des variables. Ou si on a vraiment besoin de ces résultats assez compliqués (dont il s'agit d'un cas extrêmement spécial et particulier). En fait, à peu près tout est obscur pour moi dans cette histoire, à commencer par le meilleur point de vue à adopter (entre un cycle et son cycle dual, savoir s'il faut les voir comme des mots du groupe libre ou des permutations, etc.). Il faut peut-être que je me plonge dans les détails de la démonstration de la classification des surfaces topologiques pour y voir plus clair.
En attendant, ceci ferait peut-être un casse-tête amusant, que je pourrais essayer de programmer en JavaScript : quitte à tracer le cycle comme autant de points sur un cercle, entre lesquels on relierait les symboles complémentaires (c'est la seule donnée qui survit si on s'autorise, comme je le suggère ci-dessus, une permutation des variables préservant la complémentarité), essayer de transformer une configuration donnée en une autre par des chiasmes de Whitehead. Ceux-ci se voient assez bien graphiquement (comme illustré par les figures en SVG ci-contre à gauche : en rouge, la base d'un chiasme, qui échange les segments vert et bleu ; à droite, une cible possible à atteindre).
Bref, si quelqu'un a quelque chose à dire sur le sujet, ça m'intéresse. (Ou même sur les données d'un appariement sur 2m points cycliquement ordonnés, c'est-à-dire d'un 2m-cycle et d'une involution sans point fixe.)
[#] Plutôt pour m'en souvenir moi-même qu'à l'intention de mes lecteurs, je note ici rapidement le raisonnement. Si on note la suite cyclique des symboles donnée par le dual d'un cycle parfait comme je l'ai défini, on obtient un mot cyclique dans le groupe libre sur autant de générateurs ; l'algorithme de Whitehead (voir notamment Lyndon & Schupp, Combinatorial Group Theory (1977), proposition 4.19 et la discussion précédente) assure que deux mots cycliques sont transformables l'un en l'autre par un automorphisme du groupe libre exactement quand ils le sont par des transformations de Whitehead (n'allongeant pas le mot) qui, sur le cycle dual, se voient comme les chiasmes de Whitehead que j'ai définis. Mais d'autre part les cycles parfaits définissent des surfaces orientables (à un trou) de genre m/2, cf. l'article de Marc Culler auquel je faisais référence dans la dernière entrée.