La réponse à la vie, à l’univers et à tout
Une équipe dirigée par Andrew Sutherland du MIT et Andrew Booker de l’Université de Bristol a résolu la dernière pièce d’une célèbre énigme mathématique vieille de 65 ans en donnant la réponse au nombre le plus insaisissable de tous : 42.
Le nombre 42 est particulièrement significatif pour les fans du roman de science-fiction « Le guide du routard de la galaxie » de Douglas Adams, car ce nombre est la réponse donnée par un superordinateur à « la question ultime de la vie, de l’univers et de tout ».
Booker voulait aussi connaître la réponse à 42. C’est-à-dire, y a-t-il trois cubes dont la somme est 42 ?
Cette énigme de la somme de trois cubes, posée pour la première fois en 1954 à l’université de Cambridge et connue sous le nom d’équation diophantienne x3+y3+z3=k, mettait les mathématiciens au défi de trouver des solutions pour les nombres de 1 à 100. Avec des nombres plus petits, ce type d’équation est plus facile à résoudre : par exemple, 29 peut être écrit sous la forme 33 + 13 + 13, tandis que 32 est insoluble. Toutes ont finalement été résolues, ou prouvées insolubles, à l’aide de diverses techniques et de superordinateurs, sauf deux nombres : 33 et 42.
Booker a conçu un algorithme ingénieux et a passé des semaines sur le superordinateur de son université lorsqu’il a récemment trouvé une solution pour 33. Mais lorsqu’il s’est tourné vers la solution de 42, Booker a constaté que le calcul nécessaire était d’un ordre de grandeur supérieur et pourrait dépasser les capacités de son superordinateur. Booker dit avoir reçu de nombreuses offres d’aide pour trouver la réponse, mais il s’est plutôt tourné vers son ami Andrew « Drew » Sutherland, chercheur principal au département de mathématiques. « C’est un expert mondial de ce genre de choses », dit Booker.
Sutherland, dont la spécialité comprend les calculs massivement parallèles, a battu en 2017 le record du plus grand cluster Compute Engine, avec 580 000 cœurs sur des machines virtuelles préemptibles, le plus grand cluster de calcul haute performance connu à fonctionner dans le cloud public.
Comme d’autres théoriciens des nombres computationnels qui travaillent en géométrie arithmétique, il était au courant du problème de la « somme de trois cubes ». Et les deux hommes avaient déjà travaillé ensemble auparavant, participant à la construction de la base de données des fonctions L et des formes modulaires (LMFDB), un atlas en ligne d’objets mathématiques liés à ce que l’on appelle le programme de Langlands. « J’étais ravi quand Andy m’a demandé de le rejoindre sur ce projet », dit Sutherland.
Booker et Sutherland ont discuté de la stratégie algorithmique à utiliser dans la recherche d’une solution à 42. Comme Booker l’avait trouvé avec sa solution à 33, ils savaient qu’ils n’avaient pas à recourir à l’essai de toutes les possibilités pour x, y et z.
« Il y a un seul paramètre entier, d, qui détermine un ensemble relativement petit de possibilités pour x, y et z telles que la valeur absolue de z est inférieure à une limite de recherche choisie B », dit Sutherland. « On énumère ensuite les valeurs de d et on vérifie chacune des possibilités x, y, z associées à d. Dans la tentative de craquer 33, la limite de recherche B était 1016, mais cette B s’est avérée trop petite pour craquer 42 ; nous avons plutôt utilisé B = 1017 (1017 est 100 millions de milliards).
Au contraire, la principale différence entre la recherche de 33 et la recherche de 42 serait la taille de la recherche et la plate-forme informatique utilisée. Grâce à une offre généreuse de la société Charity Engine, basée au Royaume-Uni, Booker et Sutherland ont pu exploiter la puissance de calcul de plus de 400 000 ordinateurs personnels de volontaires, répartis dans le monde entier, à chacun desquels a été attribué un éventail de valeurs pour d. Le calcul sur chaque PC s’exécute en arrière-plan afin que le propriétaire puisse toujours utiliser son PC pour d’autres tâches.
Sutherland est également un fan de Douglas Adams, le projet était donc irrésistible.
La méthode d’utilisation de Charity Engine est similaire à une partie de l’intrigue autour du nombre 42 dans le roman « Hitchhiker » : Après que la réponse de Deep Thought, 42, s’avère insatisfaisante pour les scientifiques, qui ne connaissent pas la question à laquelle il est censé répondre, le superordinateur décide de calculer la Question Ultime en construisant un superordinateur alimenté par la Terre… autrement dit, en employant une plateforme mondiale de calcul massivement parallèle.
« C’est une autre raison pour laquelle j’ai vraiment aimé exécuter ce calcul sur Charity Engine – nous avons réellement utilisé un ordinateur à l’échelle planétaire pour régler une question ouverte de longue date dont la réponse est 42. »
Ils ont exécuté un certain nombre de calculs à une capacité inférieure pour tester à la fois leur code et le réseau Charity Engine. Ils ont ensuite utilisé un certain nombre d’optimisations et d’adaptations pour rendre le code mieux adapté à un calcul massivement distribué, par rapport à un calcul exécuté sur un seul superordinateur, dit Sutherland.
Pourquoi le superordinateur de Bristol n’a-t-il pas pu résoudre ce problème ?
« Eh bien, n’importe quel ordinateur *peut* résoudre le problème, à condition que vous soyez prêt à attendre suffisamment longtemps, mais avec environ un demi-million de PC travaillant sur le problème en parallèle (chacun avec plusieurs cœurs), nous avons été en mesure de terminer le calcul beaucoup plus rapidement que nous aurions pu utiliser la machine de Bristol (ou n’importe laquelle des machines ici au MIT) », dit Sutherland.
L’utilisation du réseau Charity Engine est également plus économe en énergie. « Dans la plupart des cas, nous utilisons des ressources informatiques qui seraient autrement gaspillées », explique Sutherland. « Lorsque vous êtes assis devant votre ordinateur en train de lire un courriel ou de travailler sur une feuille de calcul, vous n’utilisez qu’une infime partie des ressources CPU disponibles, et l’application Charity Engine, qui est basée sur l’infrastructure ouverte de Berkeley pour le calcul en réseau (BOINC), en tire parti. Par conséquent, l’empreinte carbone de ce calcul – liée à l’électricité que nos calculs ont fait consommer aux PC du réseau au-delà de ce qu’ils auraient utilisé, de toute façon – est inférieure à ce qu’elle aurait été si nous avions utilisé un superordinateur. »
Sutherland et Booker ont effectué les calculs sur plusieurs mois, mais l’exécution finale réussie a été réalisée en quelques semaines seulement. Lorsque le courriel de Charity Engine est arrivé, il fournissait la première solution de x3+y3+z3=42:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
« Lorsque j’ai appris la nouvelle, c’était définitivement un moment de fist-pump », dit Sutherland. « Avec ces calculs à grande échelle, vous versez beaucoup de temps et d’énergie dans l’optimisation de la mise en œuvre, le réglage des paramètres, puis les tests et les retests du code pendant des semaines et des mois, sans jamais vraiment savoir si tous ces efforts vont payer, alors c’est extrêmement satisfaisant quand c’est le cas. »
Booker et Sutherland disent qu’il reste 10 autres nombres, de 101 à 1000, à résoudre, le prochain étant 114.
Mais tous deux sont plus intéressés par une énigme plus simple mais plus difficile à calculer : savoir s’il y a plus de réponses pour la somme de trois cubes pour 3.
« Il y a quatre solutions très faciles qui étaient connues du mathématicien Louis J. Mordell, qui a écrit de façon célèbre en 1953 : » Je ne sais rien des solutions entières de x3 + y3 + z3 = 3 au-delà de l’existence des quatre triples (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4) ; et il doit être très difficile en effet de trouver quoi que ce soit sur d’autres solutions. Cette citation a suscité un grand intérêt pour le problème de la somme de trois cubes, et le cas k=3 en particulier. Bien qu’il existe une conjecture selon laquelle il devrait y avoir une infinité de solutions, malgré plus de 65 ans de recherche, nous ne connaissons que les solutions faciles qui étaient déjà connues de Mordell. Il serait très excitant de trouver une autre solution pour k=3. »