En septembre 2019, des chercheurs, exploitant la puissance combinée d'un demi-million d'ordinateurs personnels dans le monde, pour la première fois trouvé une solution à 42. La percée largement rapportée a incité l'équipe à s'attaquer à un problème encore plus difficile, et à certains égards problème plus universel :trouver la prochaine solution pour 3. Crédits :Christine Daniloff, MIT
Que faites-vous après avoir résolu la réponse à la vie, l'univers, et tout? Si vous êtes les mathématiciens Drew Sutherland et Andy Booker, vous allez pour le problème le plus difficile.
En 2019, Booker, à l'Université de Bristol, et Sutherland, chercheur principal au MIT, ont été les premiers à trouver la réponse à 42. Le nombre a une signification dans la culture pop en tant que réponse fictive à "la question ultime de la vie, l'univers, et tout, " comme Douglas Adams l'a écrit dans son roman "Le guide de l'auto-stoppeur de la galaxie." La question qui engendre 42, du moins dans le roman, est frustrant, hilarant inconnu.
En mathématiques, tout à fait par hasard, il existe une équation polynomiale dont la réponse, 42, avait de la même manière échappé aux mathématiciens pendant des décennies. L'équation x 3 +y 3 +z 3 =k est connu comme le problème de la somme des cubes. Bien qu'apparemment simple, l'équation devient exponentiellement difficile à résoudre lorsqu'elle est présentée comme une "équation diophantienne" - un problème qui stipule que, pour toute valeur de k, les valeurs de x, oui, et z doivent chacun être des nombres entiers.
Lorsque l'équation de la somme des cubes est encadrée de cette manière, pour certaines valeurs de k, les solutions entières pour x, oui, et z peut atteindre des nombres énormes. L'espace numérique dans lequel les mathématiciens doivent rechercher ces nombres est encore plus grand, nécessitant des calculs complexes et massifs.
Au cours des années, les mathématiciens avaient réussi par divers moyens à résoudre l'équation, soit trouver une solution, soit déterminer qu'une solution ne doit pas exister, pour chaque valeur de k comprise entre 1 et 100, sauf pour 42.
En septembre 2019, Booker et Sutherland, exploitant la puissance combinée d'un demi-million d'ordinateurs personnels dans le monde, pour la première fois trouvé une solution à 42. La percée largement rapportée a incité l'équipe à s'attaquer à un problème encore plus difficile, et à certains égards problème plus universel :trouver la prochaine solution pour 3.
Booker et Sutherland ont maintenant publié les solutions pour 42 et 3, ainsi que plusieurs autres nombres supérieurs à 100, cette semaine dans le Actes de l'Académie nationale des sciences .
Relever le gant
Les deux premières solutions de l'équation x 3 +y 3 +z 3 =3 peut être évident pour n'importe quel élève du secondaire en algèbre, où x, oui, et z peut être soit 1, 1, et 1, ou 4, 4, et -5. Trouver une troisième solution, cependant, a déconcerté les théoriciens experts des nombres pendant des décennies, et en 1953, l'énigme a incité le mathématicien pionnier Louis Mordell à poser la question :est-il même possible de savoir s'il existe d'autres solutions pour 3 ?
"C'était un peu comme Mordell jetant le gant, " dit Sutherland. " L'intérêt de résoudre cette question n'est pas tant pour la solution particulière, mais pour mieux comprendre à quel point ces équations sont difficiles à résoudre. C'est une référence par rapport à laquelle nous pouvons nous mesurer."
Au fil des décennies sans nouvelles solutions pour 3, beaucoup ont commencé à croire qu'il n'y en avait pas. Mais peu de temps après avoir trouvé la réponse à 42, méthode de Booker et Sutherland, en un temps étonnamment court, mis en place la solution suivante pour 3:
569936821221962380720 3 + (-569936821113563493509) 3 + (-472715493453327032) 3 =3
La découverte était une réponse directe à la question de Mordell :Oui, il est possible de trouver la solution suivante à 3, et ce qui est plus, voici cette solution. Et peut-être plus universellement, la solution, impliquant gigantesque, des nombres à 21 chiffres qu'il n'était pas possible de trier jusqu'à présent, suggère qu'il existe d'autres solutions, pour 3, et d'autres valeurs de k.
"Il y avait eu de sérieux doutes dans les communautés mathématiques et computationnelles, parce que [la question de Mordell] est très difficile à tester, " Sutherland dit. "Les chiffres deviennent si gros si vite. Vous ne trouverez jamais plus que les premières solutions. Mais ce que je peux dire, c'est ayant trouvé cette seule solution, Je suis convaincu qu'il y en a infiniment d'autres."
Le twist d'une solution
Pour trouver les solutions pour 42 et 3, l'équipe a commencé avec un algorithme existant, ou une torsion de l'équation de la somme des cubes dans une forme qu'ils pensaient être plus gérable à résoudre :
k-z 3 =x 3 + oui 3 =(x + y)(x 2 - xy + y 2 )
Cette approche a été proposée pour la première fois par le mathématicien Roger Heath-Brown, qui a conjecturé qu'il devrait y avoir une infinité de solutions pour tout k convenable. L'équipe a encore modifié l'algorithme en représentant x+y comme un seul paramètre, ré. Ils ont ensuite réduit l'équation en divisant les deux côtés par d et en ne gardant que le reste - une opération en mathématiques appelée « modulo d » - en laissant une représentation simplifiée du problème.
"Vous pouvez maintenant considérer k comme une racine cubique de z, modulo d, " explique Sutherland. " Alors imaginez travailler dans un système d'arithmétique où vous ne vous souciez que du reste modulo d, et nous essayons de calculer une racine cubique de k."
Avec cette version plus élégante de l'équation, les chercheurs n'auraient qu'à rechercher les valeurs de d et z qui garantiraient de trouver les solutions ultimes à x, oui, et z, pour k=3. Mais reste, l'espace des nombres qu'ils devraient parcourir serait infiniment grand.
Donc, les chercheurs ont optimisé l'algorithme en utilisant des techniques mathématiques de « tamisage » pour réduire considérablement l'espace des solutions possibles pour d.
"Cela implique une théorie des nombres assez avancée, utiliser la structure de ce que nous savons sur les champs numériques pour éviter de chercher dans des endroits où nous n'avons pas besoin de chercher, " dit Sutherland.
Une tâche globale
L'équipe a également développé des moyens de diviser efficacement la recherche de l'algorithme en centaines de milliers de flux de traitement parallèles. Si l'algorithme était exécuté sur un seul ordinateur, il aurait fallu des centaines d'années pour trouver une solution à k=3. En divisant le travail en millions de tâches plus petites, chacun s'exécute indépendamment sur un ordinateur séparé, l'équipe pourrait encore accélérer sa recherche.
En septembre 2019, les chercheurs mettent leur plan en jeu via Charity Engine, un projet téléchargeable sous forme d'application gratuite par n'importe quel ordinateur personnel, et qui est conçu pour exploiter toute puissance de calcul domestique disponible pour résoudre collectivement des problèmes mathématiques difficiles. À l'époque, La grille de Charity Engine comprenait plus de 400, 000 ordinateurs dans le monde, et Booker et Sutherland ont pu exécuter leur algorithme sur le réseau pour tester la nouvelle plate-forme logicielle de Charity Engine.
"Pour chaque ordinateur du réseau, on leur dit, « votre travail consiste à rechercher les d dont le facteur premier se situe dans cette plage, sous réserve d'autres conditions, '", explique Sutherland. "Et nous avons dû trouver comment diviser le travail en environ 4 millions de tâches qui prendraient chacune environ trois heures à un ordinateur."
Très rapidement, la grille globale a renvoyé la toute première solution à k=42, et seulement deux semaines plus tard, les chercheurs ont confirmé qu'ils avaient trouvé la troisième solution pour k=3—un jalon qu'ils ont marqué, en partie, en imprimant l'équation sur des t-shirts.
Le fait qu'une troisième solution à k=3 existe suggère que la conjecture originale de Heath-Brown était juste et qu'il y a infiniment plus de solutions au-delà de cette plus récente. Heath-Brown prédit également que l'espace entre les solutions augmentera de façon exponentielle, avec leurs recherches. Par exemple, plutôt que les valeurs à 21 chiffres de la troisième solution, la quatrième solution pour x, oui, et z impliquera probablement des nombres avec un nombre ahurissant de 28 chiffres.
« La quantité de travail que vous devez effectuer pour chaque nouvelle solution est multipliée par plus de 10 millions, donc la prochaine solution pour 3 aura besoin de 10 millions de fois 400, 000 ordinateurs à trouver, et il n'y a aucune garantie que ce soit encore assez, " dit Sutherland. " Je ne sais pas si nous connaîtrons un jour la quatrième solution. Mais je crois que c'est là-bas."
