AUCUN ALGORITHME NE PEUT RECONNAÎTRE CERTAINES FORMES DE DIMENSION 4

Certaines questions n’ont pas de recette. Non parce que personne ne l’a encore trouvée, mais parce qu’il est démontré qu’aucun algorithme — aucune procédure pas à pas, aussi longue soit-elle, sur aucun ordinateur — ne peut y répondre juste à chaque fois. Cameron McA. Gordon, de l’université du Texas à Austin, ajoute deux questions de ce genre sur les formes de dimension 4.

Est-ce la même forme ?

Les mathématiciens appellent ces formes des variétés de dimension 4 : des espaces qui, vus de près, ressemblent partout à l’espace ordinaire à quatre dimensions. Pour les confier à un ordinateur, l’article les suppose construites en morceaux plats recollés (« linéaires par morceaux », ou PL), de sorte que chacune se décrit par une liste finie de données. La question de base devient alors : deux formes de ce genre sont-elles les mêmes, à une déformation continue près ?

En 1958, A. A. Markov a montré que cette question n’a pas d’algorithme. Sa preuve change le problème de formes en problème de groupes : il existe des groupes — des ensembles d’opérations qu’on peut enchaîner et défaire —, définis par un nombre fini de règles, pour lesquels aucun algorithme ne peut décider si une combinaison donnée de leurs éléments, appelée « mot », vaut l’élément neutre, celui qui ne fait rien — le « problème du mot ». À partir d’un tel groupe, on construit des formes qu’un algorithme ne pourrait distinguer qu’en résolvant ce problème impossible.

Le compte à rebours jusqu’à sept

L’argument de Markov fixe même la difficulté sur des formes précises. Prenez S², la surface d’une balle ordinaire, et formez le produit S² × S², une forme de dimension 4. Recollez-en k copies (une « somme connexe », notée #k). Pour un certain k, aucun algorithme ne décide si une forme donnée est #k(S² × S²). Quel k ?

L’article retrace le compte à rebours. Un groupe au problème du mot insoluble à 12 règles, trouvé par Borisov en 1969, a donné 14 copies. Gordon est descendu à 12 en 2022. M. Tancer a trouvé une nouvelle voie, par la classification des formes de dimension 4 due à Freedman, et atteint 9 dans la version « topologique », où les formes n’ont pas à être construites en morceaux plats. Une version antérieure de ce travail atteignait 8. Puis Kegel, Li et Ren ont construit un groupe insoluble bien plus petit — 3 générateurs et 9 règles —, atteignant 7 en version topologique et 9 en version à morceaux plats.

Gordon fait fonctionner la voie de Tancer aussi pour les formes en morceaux plats, et démontre :

Il n’existe aucun algorithme pour décider si une variété de dimension 4 donnée est, morceau pour morceau, la somme connexe de 7 copies de S² × S².

Le cœur de la preuve est un dictionnaire. Pour chaque mot w du groupe de Kegel, Li et Ren, Gordon construit une forme de dimension 4. Si w vaut l’élément neutre, une suite de mouvements permis sur les règles — les mouvements d’Andrews-Curtis, qui réécrivent la description sans changer la forme — montre que la forme est exactement sept copies de S² × S². Sinon, la forme contient des boucles impossibles à resserrer en un point — ce qui n’arrive jamais dans sept copies de S² × S² — et ne peut donc pas être ces sept copies. Un algorithme qui reconnaîtrait #7(S² × S²) résoudrait donc le problème du mot, ce qui est impossible.

Des sphères nouées

La seconde question porte sur les nœuds. Un nœud ordinaire est un cercle emmêlé dans l’espace à trois dimensions, et décider s’il peut être dénoué est possible : il existe un algorithme, dû à Haken. Une dimension plus haut, une sphère de dimension 2 peut être nouée dans un espace à quatre dimensions. En dimensions plus élevées, on sait que le problème correspondant n’a pas d’algorithme. Pour les sphères de dimension 2 dans la sphère de dimension 4, S⁴, personne ne sait.

Gordon démontre que dans #7(S² × S²), aucun algorithme ne peut décider si une sphère de dimension 2 — ou n’importe quelle surface, à deux faces ou à une seule — est dénouée. En chemin, l’article construit une sphère dans cette forme dont l’espace environnant a un groupe au problème du mot insoluble, et, dans 12 copies de S² × S², une sphère dont le groupe contient une copie de tout groupe qu’un ordinateur peut décrire.

Le grand prix : zéro copie

L’article énonce le but sans détour : faire descendre le nombre de copies jusqu’à zéro. Zéro copie, c’est la sphère de dimension 4, S⁴, elle-même. En dimension 5 et au-delà, aucun algorithme ne peut reconnaître la sphère ; en dimensions 2 et 3, on le peut. La dimension 4 reste ouverte — tout comme la question de savoir si l’on peut détecter les sphères nouées dans S⁴. Chaque copie retirée rapproche des deux.