L’apprentissage automatique aide à s’attaquer aux problèmes mathématiques classiques | Café et théorèmes | Science

Le problème de Hadwiger-Nelson est probablement l’un des plus connus dans le domaine de la géométrie discrète. Il s’agit de la question suivante : quel est le nombre minimum de couleurs nécessaires pour peindre le plan, de telle sorte que toujours, en prenant deux points quelconques, espacés d’une unité entre eux, ils soient toujours peints avec des couleurs différentes ? Même si cette question semble innocente, elle reste sans réponse depuis plus de 70 ans. Cependant, grâce aux outils d’apprentissage automatique, des progrès récents ont été réalisés dans sa compréhension.

Jusqu’à présent, on sait que le nombre de couleurs nécessaires peut être de cinq, six ou sept. Pour étudier le nombre minimum de couleurs nécessaire, il suffit de trouver des configurations spécifiques de points du plan qui ne peuvent pas être peints avec un nombre – appelons-les n – de couleurs et répondant à la propriété indiquée. Ainsi, nous savons que nous avons besoin de plus, au moins n+1 couleurs pour peindre l’ensemble du plan – qui inclut ce dessin spécifique – si nous voulons que la propriété soit vérifiée.

Tout d’abord, il est facile de constater qu’il faut au moins trois couleurs. En effet, en prenant un arrangement aussi simple que les trois sommets d’un triangle équilatéral dont le côté mesure un, il faut déjà trois couleurs pour les colorer, de sorte qu’il n’y a pas deux sommets adjacents de même couleur – sinon, ces points ne rempliraient pas la condition propriété recherchée : ils seraient à distance 1 et auraient la même couleur.

En affinant ce type d’argument, au début des années 60 du siècle dernier, les frères Leo et William Moser ont trouvé une configuration concrète de seulement sept points du plan qui a besoin d’au moins quatre couleurs pour remplir la propriété souhaitée, ce qui montre que le minimum le nombre est quatre. Plus récemment, en 2018, le mathématicien amateur Aubrey de Gray a trouvé une configuration comportant plus de 1 000 points sur le plan dans laquelle il fallait utiliser au moins cinq couleurs pour que la condition souhaitée soit remplie.

En plus, On sait que le nombre de couleurs ne peut pas dépasser septcar nous connaissons des stratégies pour colorer l’avion avec ces couleurs qui atteignent notre objectif. Par exemple, prenez simplement un pavage en nid d’abeille et peignez un hexagone d’une couleur et les six adjacents de couleurs différentes. Comme le diamètre de chaque hexagone est inférieur à ½, deux points quelconques à distance, l’un d’eux tombe toujours dans des hexagones différents et adjacents, donc peints d’une couleur différente.

Mais cela ne résout pas le mystère, il pourrait y avoir une autre coloration, que nous ne connaissons pas encore, qui nécessiterait moins de couleurs tout en remplissant la propriété. La réponse pourrait donc être cinq, six ou sept et, pour le moment, personne ne sait comment résoudre cette énigme.

Pour faire progresser la recherche, une stratégie courante en mathématiques consiste à imposer des contraintes plus faibles et à résoudre le problème qui en résulte. Cela nous permet souvent de trouver des approches pour résoudre la question initiale. Dans notre cas, pour étudier le problème faible de Hadwiger Nelson, nous analysons ce qui se passe si nous permettons à certains des points peints avec la même couleur d’être à une distance différente de l’un. Pour ce faire, nous introduisons la notion de configuration valide d’une coloration du plan de n couleurs, avec des distances (d1, d2, … dn) associées à chaque couleur.

Par exemple, si n=4, les couleurs sont le bleu, le vert, le jaune et l’orange, et les distances 1,5 –associées à la couleur bleue–, 0,2 –au vert–, 1 –au jaune–, 3,7 – à l’orange– , une configuration valide avec ces valeurs est un ensemble de points dans lequel chaque paire de points colorés avec la même couleur est à une distance supérieure à la distance associée à cette couleur. Dans l’exemple, il ne peut pas y avoir deux points bleus espacés de moins de 1,5 ou deux points verts espacés de moins de 0,2.

Ainsi, trouver une configuration valide de six couleurs avec des distances associées (1,1,1,1,1,1) reviendrait à montrer que la réponse au problème de Hadwiger-Nelson est, au plus, six. Trouver une configuration de cinq couleurs et avec des distances (1,1,1,1,1) serait encore mieux, car cela résoudrait complètement le problème. Et, même si elles sont moins ambitieuses, trouver des configurations de ce type permet d’approfondir nos connaissances sur le problème général.

Récemment, une équipe de chercheurs du Zuse Institute Berlin (ZIB) et de la Technische Universität Berlin (TU Berlin) a progressé dans cette direction. Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel et Max Zimmer ont trouvé une configuration valide de six couleurs (1,1,1,1,1,d), où la valeur de d Il est compris entre 0,354 et 0,657. En d’autres termes, les points colorés avec les cinq premières couleurs maintiennent la condition avec une distance unité, tandis que pour la sixième couleur la condition est assouplie : il peut y avoir une paire de points peints avec cette couleur à une distance plus petite, entre 0,354 et 0,657. . Ce résultat améliore les résultats précédents de 1996, élargissant la marge de choix possible pour d.

Mais ce qui est vraiment intéressant, c’est aussi le rôle que l’apprentissage automatique a joué dans l’obtention de ce résultat. Son idée, d’une manière générale, a été de former un réseau de neurones pour trouver des représentations répondant aux conditions souhaitées, en essayant de rendre la valeur de d était autant que possible. Ce type de réseaux neuronaux n’est pas capable de résoudre exactement le problème, mais plutôt d’obtenir des propositions de solutions approximatives, en testant un nombre énorme de combinaisons possibles, ce qui est une tâche irréalisable pour les humains.

Le réseau neuronal fonctionne alors comme un « oracle approximatif » et il incombe aux chercheurs d’interpréter les informations générées et de façonner cette voie d’exploration en une solution possible. Avec ces techniques, les auteurs ont pu obtenir diverses constructions qui améliorent toutes celles connues jusqu’à présent. Par exemple, ils ont construit un pavage périodique (dans l’image) qui utilise six couleurs, dans laquelle la sixième couleur, le rouge, est celle qui répond aux conditions les plus laxistes.

Ce type de techniques informatiques est très prometteur et il est possible qu’à l’avenir elles permettent de traiter d’autres problèmes aujourd’hui inaccessibles, comme, par exemple, l’étude du même problème dans l’espace – plutôt que dans l’espace. avion -, ou le problème de Hadwiger-Nelson dans son intégralité.

Rue Juanjo Il est professeur adjoint au Département de mathématiques de l’Université Université Polytechnique de Catalogne (UPC), membre du Institut de Mathématiques UPC (IMTech) et chercheur affecté à Centre de Recherche Mathématique (CRM).

Agata A. Timón G Longoriacoordinateur du Unité de culture mathématique ICMAT.

Café et théorèmes est une section dédiée aux mathématiques et à l’environnement dans lequel elles sont créées, coordonnée par l’Institut des Sciences Mathématiques (ICMAT), dans laquelle chercheurs et membres du centre décrivent les dernières avancées de cette discipline, partagent des points de rencontre entre les mathématiques et d’autres aspects sociaux. et expressions culturelles et rappelons-nous ceux qui ont marqué leur développement et ont su transformer le café en théorèmes. Le nom évoque la définition du mathématicien hongrois Alfred Rényi : « Un mathématicien est une machine qui transforme le café en théorèmes. »

Édition, traduction et coordination : Agate Timón García-Longoria. Elle est coordinatrice du Unité de Culture Mathématique de l’Institut des Sciences Mathématiques (ICMAT)