Le nombre 15 décrit la limite secrète d'une grille infinie

En tant qu'étudiant de premier cycle à l'Université du Chili, Bernardo Subercaseaux avait une mauvaise opinion de l'utilisation des ordinateurs pour faire des maths. Cela semblait contraire à une véritable découverte intellectuelle.

"Il y a un instinct ou une réaction instinctive contre l'utilisation d'ordinateurs pour résoudre vos problèmes, comme si cela allait à l'encontre de la beauté ou de l'élégance idéale d'un argument fantastique", a-t-il déclaré.

Mais en 2020, Subercaseaux est tombé amoureux et, comme cela arrive souvent, ses priorités ont changé. L'objet de son obsession était une question qu'il a vue sur un forum en ligne. Il a scanné la plupart des problèmes et les a oubliés, mais celui-ci a attiré son attention. Il a glissé vers la droite.

"La première chose que j'ai faite a été d'aimer la publication dans le groupe Facebook, en espérant recevoir une notification plus tard lorsque quelqu'un d'autre publiera une solution", a-t-il déclaré.

La question était de remplir une grille infinie avec des nombres. Ce n'était pas, comme il s'est avéré, le genre de problème que l'on résout sur une alouette. Pour ce faire, Subercaseaux a dû quitter le Chili pour suivre des études supérieures à l'Université Carnegie Mellon.

Là, en août 2021, il fait une rencontre fortuite avec Marijn Heule, un informaticien qui utilise une énorme puissance de calcul pour résoudre des questions mathématiques difficiles. Subercaseaux a demandé à Heule s'il voulait tenter le problème, donnant le coup d'envoi d'une collaboration qui a abouti en janvier à une preuve qui peut se résumer à un seul chiffre : 15.

Toutes les manières possibles

En 2002, Wayne Godard de l'Université de Clemson et certains mathématiciens partageant les mêmes idées crachaient des problèmes de combinatoire, essayant de trouver de nouveaux rebondissements sur les questions fondamentales du domaine concernant la coloration des cartes compte tenu de certaines contraintes.

Finalement, ils ont atterri sur un problème qui commence par une grille, comme une feuille de papier millimétré qui dure indéfiniment. Le but est de le remplir de chiffres. Il n'y a qu'une seule contrainte : la distance entre chaque occurrence d'un même nombre doit être supérieure au nombre lui-même. (La distance est mesurée en additionnant la séparation verticale et horizontale, une métrique connue sous le nom de distance «taxicab» pour la façon dont elle ressemble à se déplacer dans des rues urbaines quadrillées.) Une paire de 1 ne peut pas occuper des cellules adjacentes, qui ont une distance en taxi de 1, mais ils peuvent être placés dans des cellules directement diagonales, qui ont une distance de 2.

Initialement, Goddard et ses collaborateurs voulaient savoir s'il était même possible de remplir une grille infinie avec un ensemble fini de nombres. Mais au moment où lui et ses quatre collaborateurs publié ce problème de "coloration d'emballage" dans la revue Ars Combinatoria en 2008, ils avaient prouvé qu'il pouvait être résolu à l'aide de 22 nombres. Ils savaient également qu'il n'y avait aucun moyen de le résoudre avec seulement cinq chiffres. Cela signifiait que la réponse réelle au problème - le nombre minimum de nombres nécessaires - se situait quelque part entre les deux.

Les chercheurs n'ont pas rempli une grille infinie. Ils n'avaient pas à le faire. Au lieu de cela, il suffit de prendre un petit sous-ensemble de la grille - disons un carré de 10 sur 10 - remplissez-le avec des nombres, puis montrez que des copies du sous-ensemble rempli peuvent être placées les unes à côté des autres, comme vous couvririez un sol avec des copies d'une tuile.

Lorsque Subercaseaux a appris le problème pour la première fois, il a commencé à chercher des carreaux à l'aide d'un stylo et de papier. Il dessinait des grilles de nombres, les barrait, réessayait. Il s'est vite lassé de cette approche et a demandé à un ami de concevoir un outil Web qui ressemblait au jeu Minesweeper et lui permettait de tester des combinaisons plus rapidement. Après quelques semaines de travail supplémentaires, il s'était convaincu qu'il n'y avait aucun moyen d'emballer une grille avec huit chiffres, mais il ne pouvait pas aller plus loin que cela - il y avait tout simplement trop de formes potentielles que les tuiles pouvaient prendre, et trop de différentes manières de les remplir de chiffres.

Le problème, comme cela deviendrait clair plus tard, est qu'il est beaucoup plus difficile de montrer que la grille ne peut pas être couverte par un certain ensemble de nombres que de montrer qu'elle le peut. "Il ne s'agit pas seulement de montrer qu'une façon ne fonctionne pas, cela montre que toutes les façons possibles ne fonctionnent pas", a déclaré Goddard.

Après que Subercaseaux ait commencé à CMU et ait convaincu Heule de travailler avec lui, ils ont rapidement trouvé un moyen de couvrir la grille avec 15 numéros. Ils ont également pu exclure la possibilité de résoudre le problème avec seulement 12 numéros. Mais leur sentiment de triomphe a été de courte durée, car ils ont réalisé qu'ils n'avaient fait que reproduire des résultats qui existaient depuis longtemps : dès 2017, les chercheurs savaient que la réponse n'était ni inférieure à 13 ni supérieure à 15. .

Pour un étudiant diplômé de première année qui avait amené un professeur renommé à travailler sur son problème de compagnie, c'était une découverte troublante. "J'étais horrifié. J'avais essentiellement travaillé pendant plusieurs mois sur un problème sans m'en rendre compte, et pire encore, j'avais fait Marijn y perdre son temps!" Subercaseaux écrit dans un article de blog récapitulant leur travail.

Heule, cependant, a trouvé la découverte des résultats passés revigorante. Cela a démontré que d'autres chercheurs trouvaient le problème suffisamment important pour y travailler, et lui a confirmé que le seul résultat qui valait la peine d'être obtenu était de résoudre complètement le problème.

"Une fois que nous avons compris qu'il y avait eu 20 ans de travail sur le problème, cela a complètement changé la donne", a-t-il déclaré.

Éviter le vulgaire

Au fil des ans, Heule avait fait carrière en trouvant des moyens efficaces de rechercher parmi de vastes combinaisons possibles. Son approche s'appelle la résolution SAT - abréviation de « satisfiabilité ». Il s'agit de construire une longue formule, appelée formule booléenne, qui peut avoir deux résultats possibles : 0 ou 1. Si le résultat est 1, la formule est vraie et le problème est résolu.

Pour le problème de coloration de l'emballage, chaque variable de la formule peut représenter si une cellule donnée est occupée par un nombre donné. Un ordinateur cherche des moyens d'assigner des variables afin de satisfaire la formule. Si l'ordinateur peut le faire, vous savez qu'il est possible d'emballer la grille dans les conditions que vous avez définies.

Malheureusement, un simple encodage du problème de coloration de l'emballage sous forme de formule booléenne pourrait s'étendre à plusieurs millions de termes - un ordinateur, ou même une flotte d'ordinateurs, pourrait fonctionner sans fin pour tester toutes les différentes façons d'attribuer des variables en son sein.

"Essayer de faire cette force brute prendrait jusqu'à ce que l'univers se termine si vous le faisiez naïvement", a déclaré Goddard. "Vous avez donc besoin de quelques simplifications intéressantes pour le ramener à quelque chose qui est même possible."

De plus, chaque fois que vous ajoutez un nombre au problème de coloration de l'emballage, cela devient environ 100 fois plus difficile, en raison de la multiplication des combinaisons possibles. Cela signifie que si une banque d'ordinateurs travaillant en parallèle pouvait exclure 12 en une seule journée de calcul, il lui faudrait 100 jours de temps de calcul pour exclure 13.

Heule et Subercaseaux considéraient la mise à l'échelle d'une approche informatique par force brute comme vulgaire, d'une certaine manière. "Nous avions plusieurs idées prometteuses, nous avons donc adopté l'état d'esprit suivant :" Essayons d'optimiser notre approche jusqu'à ce que nous puissions résoudre ce problème en moins de 48 heures de calcul sur le cluster "", a déclaré Subercaseaux.

Pour ce faire, ils devaient trouver des moyens de limiter le nombre de combinaisons que le cluster informatique devait essayer.

"[Ils] veulent non seulement le résoudre, mais le résoudre de manière impressionnante", a déclaré Alexandre Soifer de l'Université du Colorado, Colorado Springs.

Heule et Subercaseaux ont reconnu que de nombreuses combinaisons sont essentiellement les mêmes. Si vous essayez de remplir une tuile en forme de losange avec huit nombres différents, peu importe si le premier nombre que vous placez est un en haut et un à droite du carré central, ou un en bas et un à gauche de la place centrale. Les deux emplacements sont symétriques l'un par rapport à l'autre et contraignent votre prochain mouvement exactement de la même manière, il n'y a donc aucune raison de les vérifier tous les deux.

Heule et Subercaseaux ont ajouté des règles qui permettaient à l'ordinateur de traiter les combinaisons symétriques comme équivalentes, réduisant le temps total de recherche d'un facteur huit. Ils ont également utilisé une technique que Heule avait développée dans des travaux antérieurs appelée cube et conquérir, ce qui leur a permis de tester davantage de combinaisons en parallèle les unes avec les autres. Si vous savez qu'une cellule donnée doit contenir 3, 5 ou 7, vous pouvez diviser le problème et tester chacune des trois possibilités simultanément sur différents ensembles d'ordinateurs.

En janvier 2022, ces améliorations ont permis à Heule et Subercaseaux d'exclure 13 comme réponse au problème de coloration de l'emballage dans une expérience qui nécessitait moins de deux jours de temps de calcul. Cela leur laissait deux réponses possibles : 14 ou 15.

Un gros plus

Pour exclure 14 - et résoudre le problème - Heule et Subercaseaux ont dû trouver des moyens supplémentaires d'accélérer la recherche informatique.

Au départ, ils avaient écrit une formule booléenne qui attribuait des variables à chaque cellule individuelle de la grille. Mais en septembre 2022, ils ont réalisé qu'ils n'avaient pas besoin de procéder cellule par cellule. Au lieu de cela, ils ont découvert qu'il était plus efficace de considérer de petites régions composées de cinq cellules sous la forme d'un signe plus.

Ils ont réécrit leur formule booléenne afin que plusieurs variables représentent des questions telles que : y a-t-il un 7 quelque part dans cette région en forme de plus ? L'ordinateur n'avait pas besoin d'identifier exactement où dans la région le 7 pouvait se trouver. Il avait juste besoin de déterminer s'il était là ou non - une question qui nécessite beaucoup moins de ressources de calcul pour répondre.

"Avoir des variables qui ne parlent que d'avantages au lieu d'emplacements spécifiques s'est avéré bien meilleur que d'en parler dans des cellules spécifiques", a déclaré Heule.

Aidés par l'efficacité de la recherche plus, Heule et Subercaseaux ont exclu 14 dans une expérience informatique en novembre 2022 qui a fini par prendre moins de temps à s'exécuter que celle qu'ils avaient utilisée pour exclure 13. Ils ont passé les quatre mois suivants à vérifier que la conclusion de l'ordinateur était correcte - presque autant de temps qu'ils avaient passé à permettre à l'ordinateur d'arriver à cette conclusion en premier lieu.

"C'était gratifiant de penser que ce que nous avions engendré comme une sorte de question secondaire dans un journal aléatoire avait amené des groupes de personnes à passer, en fin de compte, des mois de leur temps à essayer de trouver comment le résoudre", Goddard a dit.

Pour Subercaseaux, ce fut le premier véritable triomphe de sa carrière de chercheur. Et même si ce n'était peut-être pas le type de découverte qu'il avait idéalisé lorsqu'il envisageait pour la première fois de travailler en mathématiques, il a découvert qu'en fin de compte, cela avait ses propres récompenses intellectuelles.

"Ce n'est pas comprendre le formulaire où vous me donnez un tableau noir et je peux vous montrer pourquoi c'est 15", a-t-il déclaré. «Mais nous avons compris comment fonctionnent les contraintes du problème, à quel point il est préférable d'avoir un 6 ici ou un 7 là-bas. Nous avons acquis beaucoup de compréhension intuitive.