Astuces mathématiques pour apprivoiser le demi-fond | Quanta Magazine

Jusqu'à présent cette année, Quanta a fait la chronique de trois avancées majeures dans la théorie de Ramsey, l'étude de la façon d'éviter de créer des modèles mathématiques. Le premier résultat mettre un nouveau plafond sur la taille d'un ensemble d'entiers sans contenir trois nombres régulièrement espacés, comme {2, 4, 6} ou {21, 31, 41}. Le seconde et de troisième de même mettre de nouvelles bornes sur la taille des réseaux sans grappes de points qui sont soit tous connectés, soit tous isolés les uns des autres.

Les preuves traitent de ce qui se passe lorsque les nombres impliqués deviennent infiniment grands. Paradoxalement, cela peut parfois être plus facile que de gérer des quantités embêtantes du monde réel.

Par exemple, considérez deux questions sur une fraction avec un très grand dénominateur. Vous pourriez vous demander quelle est l'expansion décimale de, disons, 1/42503312127361. Ou vous pouvez demander si ce nombre se rapproche de zéro à mesure que le dénominateur augmente. La première question est une question spécifique sur une quantité du monde réel, et elle est plus difficile à calculer que la seconde, qui demande comment la quantité 1/n changera "asymptotiquement" comme n grandit. (Il se rapproche de plus en plus de 0.)

"C'est un problème qui afflige toute la théorie de Ramsey", a déclaré Guillaume Gasarch, informaticien à l'Université du Maryland. "La théorie de Ramsey est connue pour avoir des résultats asymptotiquement très bons." Mais analyser des nombres inférieurs à l'infini nécessite une boîte à outils mathématique entièrement différente.

Gasarch a étudié des questions de la théorie de Ramsey impliquant des nombres finis qui sont trop grands pour que le problème puisse être résolu par la force brute. Dans un projet, il a pris en charge la version finie de la première des percées de cette année — un article de février de Sandre Kelley, étudiant diplômé de l'Université de l'Illinois, Urbana-Champaign, et Raghu Meka de l'Université de Californie à Los Angeles. Kelley et Meka ont trouvé une nouvelle limite supérieure sur le nombre d'entiers entre 1 et N vous pouvez mettre dans un ensemble tout en évitant les progressions à trois termes ou les modèles de nombres régulièrement espacés.

Bien que le résultat de Kelley et Meka s'applique même si N est relativement petit, il ne donne pas de borne particulièrement utile dans ce cas. Pour de très petites valeurs de N, il vaut mieux s'en tenir à des méthodes très simples. Si N est, disons, 5, il suffit de regarder tous les ensembles de nombres possibles entre 1 et N, et choisissez le plus grand sans progression : {1, 2, 4, 5}.

Mais le nombre de réponses possibles augmente très rapidement et rend trop difficile l'emploi d'une stratégie aussi simple. Il y a plus d'un million d'ensembles composés de nombres entre 1 et 1. Il y a plus de 20⁶⁰ en utilisant des nombres compris entre 1 et 200. Trouver le meilleur ensemble sans progression pour ces cas nécessite une forte dose de puissance de calcul, même avec des stratégies d'amélioration de l'efficacité. "Vous devez être en mesure d'extraire beaucoup de performances des choses", a déclaré James Glen, informaticien à l'université de Yale. En 2008, Gasarch, Glenn et Clyde Kruskal de l'Université du Maryland écrit un programme pour trouver les plus grands ensembles sans progression jusqu'à un N de 187. (Les travaux précédents avaient obtenu les réponses jusqu'à 150, ainsi que pour 157.) Malgré une liste d'astuces, leur programme a pris des mois pour se terminer, a déclaré Glenn.

Pour réduire leur charge de calcul, l'équipe a utilisé des tests simples qui ont empêché leur programme de poursuivre des recherches sans issue et ont divisé leurs ensembles en parties plus petites qu'ils ont analysées séparément.

Gasarch, Glenn et Kruskal ont également essayé plusieurs autres stratégies. Une idée prometteuse s'appuyait sur le hasard. Un moyen simple de créer un ensemble sans progression consiste à mettre 1 dans votre ensemble, puis à toujours ajouter le nombre suivant qui ne crée pas de progression arithmétique. Suivez cette procédure jusqu'à ce que vous atteigniez le chiffre 10, et vous obtiendrez l'ensemble {1, 2, 4, 5, 10}. Mais il s'avère que ce n'est pas la meilleure stratégie en général. "Et si nous ne commencions pas à 1 ?" dit Gasarch. "Si vous commencez à un endroit au hasard, vous faites mieux." Les chercheurs ne savent pas pourquoi le hasard est si utile, a-t-il ajouté.

Calculer les versions finies des deux autres nouveaux résultats de la théorie de Ramsey est encore plus frustrant que de déterminer la taille des ensembles sans progression. Ces résultats concernent des réseaux mathématiques (appelés graphes) constitués de nœuds reliés par des lignes appelées arêtes. Le nombre de Ramsey r(s, t) est le plus petit nombre de nœuds qu'un graphe doit avoir avant qu'il ne devienne impossible d'éviter d'inclure soit un groupe de s nœuds connectés ou t les déconnectés. Le nombre de Ramsey est un tel casse-tête à calculer que même r(5, 5) est inconnu — c'est quelque part entre 43 et 48.

En 1981, Brendan McKay, aujourd'hui informaticien à l'Australian National University, a écrit un logiciel appelé nauty, destiné à simplifier le calcul des nombres de Ramsey. Nauty garantit que les chercheurs ne perdent pas de temps à vérifier deux graphiques qui ne sont que des versions inversées ou tournées l'une de l'autre. « Si quelqu'un se trouve dans la zone et n'utilise pas nauty, le jeu est terminé. Vous devez l'utiliser », a déclaré Stanisław Radziszowski, mathématicien au Rochester Institute of Technology. Pourtant, la quantité de calculs impliqués est presque incompréhensible. En 2013, Radziszowski et Jean Goedgebeur Prouvé cela r(3, 10) vaut au plus 42. "Il a fallu, je pense, près de 50 années CPU", a déclaré Goedgebeur, informaticien à l'Université KU Leuven en Belgique.

Si vous ne pouvez pas calculer un nombre de Ramsey exact, vous pouvez essayer de réduire sa valeur avec des exemples. Si vous trouviez un graphe à 45 nœuds sans cinq nœuds tous connectés et sans cinq nœuds tous déconnectés, cela prouverait que r(5, 5) est supérieur à 45. Les mathématiciens qui étudiaient les nombres de Ramsey avaient l'habitude de penser que trouver ces exemples, appelés graphes de Ramsey, serait simple, a déclaré Radziszowski. Mais ce n'était pas le cas. "Il y avait cette attente que des constructions mathématiques agréables et cool donneraient les meilleures constructions possibles, et nous avons juste besoin de plus de personnes pour y travailler", a-t-il déclaré. "Mon sentiment est de plus en plus que c'est chaotique."

Le hasard est à la fois un obstacle à la compréhension et un outil utile. Geoffrey Exo, informaticien à l'Indiana State University, a passé des années à affiner des méthodes aléatoires pour générer des graphes de Ramsey. Dans un papier 2015 annonçant des dizaines de nouveaux graphiques Ramsey battant des records, Exoo et Milos Tatarevic ont généré des graphiques aléatoires, puis les ont progressivement modifiés en supprimant ou en ajoutant des arêtes qui réduisaient le nombre de clusters indésirables jusqu'à ce qu'ils trouvent un graphique Ramsey. Cependant, les techniques d'Exoo sont autant un art qu'autre chose, a déclaré Radziszowski. Ils l'obligent parfois à combiner plusieurs méthodes ou à faire preuve de discernement quant au type de graphiques avec lequel commencer. "Beaucoup de gens essaient, et ils ne peuvent pas le faire", a déclaré Radziszowski.

Les techniques développées pour générer des graphiques de Ramsey pourraient être plus largement utiles un jour, a déclaré Goedgebeur, qui a travaillé sur produire d'autres types de graphiques, tels que des graphiques représentant des composés chimiques. "Il n'est pas improbable que ces techniques puissent également être transférées et ajustées pour aider à générer plus efficacement d'autres classes de graphiques (et vice versa)", a-t-il écrit dans un e-mail.

Pour Radziszowski, cependant, la raison d'étudier les petits nombres de Ramsey est beaucoup plus simple. "Parce que c'est ouvert, parce que personne ne sait quelle est la réponse", a-t-il déclaré. « Les cas triviaux que nous traitons à la main ; un peu plus grand, vous avez besoin d'un ordinateur, et un peu plus grand, même l'ordinateur n'est pas assez bon. Et c'est ainsi que le défi émerge.