Introduction
A la mi-octobre, Justin Gilmer a volé de Californie à New York pour assister au mariage d'un ami. Alors qu'il était sur la côte Est, il a rendu visite à son ancien conseiller, Michel Saks, mathématicien à l'Université Rutgers, où Gilmer avait obtenu son doctorat sept ans plus tôt.
Saks et Gilmer se sont rencontrés pendant le déjeuner, mais ils n'ont pas parlé de maths. En fait, Gilmer n'avait pas pensé sérieusement aux mathématiques depuis qu'il avait terminé à Rutgers en 2015. C'est à ce moment-là qu'il avait décidé qu'il ne voulait pas faire carrière dans le milieu universitaire et avait plutôt commencé à apprendre à programmer. Alors que lui et Saks mangeaient, Gilmer a parlé à son ancien mentor de son travail chez Google, où il travaille sur l'apprentissage automatique et l'intelligence artificielle.
Il faisait beau le jour où Gilmer a rendu visite à Rutgers. Alors qu'il se promenait, il se souvenait qu'en 2013, il avait passé la majeure partie de l'année à parcourir les mêmes sentiers du campus, en pensant à un problème appelé la conjecture syndicale fermée. Cela avait été une fixation, bien qu'infructueuse : malgré tous ses efforts, Gilmer n'avait réussi qu'à apprendre par lui-même pourquoi le problème apparemment simple des ensembles de nombres était si difficile à résoudre.
« Je pense que beaucoup de gens réfléchissent au problème jusqu'à ce qu'ils soient convaincus qu'ils comprennent pourquoi c'est difficile. J'y ai probablement passé plus de temps que la plupart des gens », a déclaré Gilmer.
Après sa visite d'octobre, quelque chose d'inattendu s'est produit : il a eu une nouvelle idée. Gilmer a commencé à réfléchir à des moyens d'appliquer des techniques de la théorie de l'information pour résoudre la conjecture d'union fermée. Il a poursuivi l'idée pendant un mois, s'attendant à tout moment à ce qu'elle échoue. Mais au lieu de cela, le chemin vers une preuve ne cessait de s'ouvrir. Enfin, le 16 novembre, il a publié un résultat unique en son genre cela permet aux mathématiciens de prouver la conjecture complète.
Le document a déclenché une vague de travaux de suivi. Les mathématiciens de l'Université d'Oxford, du Massachusetts Institute of Technology et de l'Institute for Advanced Study, entre autres institutions, se sont rapidement appuyés sur les nouvelles méthodes de Gilmer. Mais avant de le faire, ils ont posé leur propre question : qui est ce type ?
À moitié plein
La conjecture d'union fermée concerne des collections de nombres appelés ensembles, tels que {1, 2} et {2, 3, 4}. Vous pouvez effectuer des opérations sur des ensembles, notamment en prenant leur union, c'est-à-dire en les combinant. Par exemple, l'union de {1, 2} et {2, 3, 4} est {1, 2, 3, 4}.
Une collection, ou une famille, d'ensembles est considérée comme "fermée par l'union" si l'union de deux ensembles quelconques de la famille est égale à tout ensemble existant dans la famille. Par exemple, considérons cette famille de quatre ensembles :
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Combinez n'importe quelle paire et vous obtenez un ensemble qui est déjà dans la famille, ce qui rend l'union familiale fermée.
Les mathématiciens ont discuté des versions de la conjecture syndicale fermée dès les années 1960, mais elle a reçu sa première déclaration formelle en 1979, dans un article de Peter Frankl, un mathématicien hongrois qui a émigré au Japon dans les années 1980 et qui compte parmi ses activités les spectacles de rue.
Frankl a supposé que si une famille d'ensembles est fermée par une union, elle doit avoir au moins un élément (ou nombre) qui apparaît dans au moins la moitié des ensembles. C'était un seuil naturel pour deux raisons.
Premièrement, il existe des exemples facilement disponibles de familles à union fermée dans lesquelles tous les éléments apparaissent dans exactement 50% des ensembles. Comme tous les ensembles différents que vous pouvez faire à partir des chiffres de 1 à 10, par exemple. Il existe 1,024 10 ensembles de ce type, qui forment une famille à union fermée, et chacun des 512 éléments apparaît dans XNUMX d'entre eux. Et deuxièmement, au moment où Frankl a fait la conjecture, personne n'avait jamais produit d'exemple de famille à union fermée dans laquelle la conjecture ne tenait pas.
Donc 50% semblait être la bonne prédiction.
Cela ne voulait pas dire que c'était facile à prouver. Dans les années qui ont suivi l'article de Frankl, il y a eu peu de résultats. Avant les travaux de Gilmer, ces articles ne réussissaient qu'à établir des seuils qui variaient avec le nombre d'ensembles dans la famille (au lieu d'être le même seuil de 50% pour les familles d'ensembles de toutes tailles).
"On dirait que cela devrait être facile, et cela ressemble à beaucoup de problèmes faciles, mais il a résisté aux attaques", a déclaré Est-ce que Sawin de l'Université de Columbia.
L'absence de progrès reflétait à la fois la nature délicate du problème et le fait que de nombreux mathématiciens préféraient ne pas y penser ; ils craignaient de perdre des années de leur carrière à poursuivre un problème séduisant impossible à résoudre. Gilmer se souvient d'un jour de 2013 où il s'est rendu au bureau de Saks et a évoqué la conjecture de la fermeture du syndicat. Son conseiller – qui dans le passé avait lui-même lutté avec le problème – l'a presque jeté hors de la pièce.
"Mike a dit : 'Justin, tu vas me faire repenser à ce problème et je ne veux pas faire ça'", a déclaré Gilmer.
Un aperçu de l'incertitude
Après sa visite à Rutgers, Gilmer tourna le problème dans son esprit, essayant de comprendre pourquoi c'était si difficile. Il s'est inspiré d'un fait fondamental : si vous avez une famille de 100 ensembles, il existe 4,950 4,950 façons différentes d'en choisir deux et de prendre leur union. Puis il s'est demandé : comment est-il possible que 100 XNUMX unions différentes se retrouvent sur seulement XNUMX ensembles si aucun élément n'apparaît dans ces unions avec au moins une certaine fréquence ?
Même à ce moment-là, il était en route vers une preuve, bien qu'il ne le sache pas encore. Les techniques de la théorie de l'information, qui fournissent une manière rigoureuse de penser à quoi s'attendre lorsque vous tirez une paire d'objets au hasard, l'y conduiraient.
La théorie de l'information s'est développée dans la première moitié du XXe siècle, notamment avec l'article de Claude Shannon de 20, "Une théorie mathématique de la communication.” Le document a fourni un moyen précis de calculer la quantité d'informations nécessaires pour envoyer un message, en fonction de la quantité d'incertitude autour de ce que le message dirait exactement. Ce lien - entre information et incertitude - était la perspicacité remarquable et fondamentale de Shannon.
Pour prendre un exemple de jouet, imaginez que je lance une pièce cinq fois et que je vous envoie la séquence résultante. S'il s'agit d'une pièce normale, il faut cinq bits d'information pour la transmettre. Mais s'il s'agit d'une pièce chargée - disons, 99% de chances d'atterrir sur face - cela prend beaucoup moins. Par exemple, nous pourrions convenir à l'avance que je vous enverrai un 1 (un seul élément d'information) si la pièce chargée atterrit face cinq fois, ce qui est très probable. Il y a plus de surprise dans le résultat d'un tirage équitable que d'un tirage biaisé, et donc plus d'informations.
Le même raisonnement s'applique aux informations contenues dans les ensembles de nombres. Si j'ai une famille d'ensembles fermés par union - disons les 1,024 1 ensembles composés des nombres 10 à 50 - je pourrais choisir deux ensembles au hasard. Ensuite je pourrais vous communiquer les éléments de chaque set. La quantité d'informations nécessaires pour envoyer ce message reflète le degré d'incertitude autour de ces éléments : il y a 1 % de chances, par exemple, que le premier élément du premier ensemble soit un 1 (car 50 apparaît dans la moitié des ensembles dans la famille), tout comme il y a XNUMX % de chances que le premier résultat d'une séquence de lancers équitables soit face.
La théorie de l'information apparaît souvent en combinatoire , un domaine des mathématiques concerné par le comptage d'objets, ce que Gilmer avait étudié en tant qu'étudiant diplômé. Mais alors qu'il rentrait chez lui en Californie, il s'inquiétait que la façon dont il pensait relier la théorie de l'information à la conjecture de l'union fermée était la perspicacité naïve d'un amateur : des mathématiciens en activité avaient sûrement déjà rencontré cet objet brillant et l'avaient reconnu comme de l'or du fou. .
"Pour être honnête, je suis un peu surpris que personne n'y ait pensé avant", a déclaré Gilmer. "Mais peut-être que je ne devrais pas être surpris, car j'y avais moi-même réfléchi pendant un an, et je connaissais la théorie de l'information."
Plus probable qu'improbable
Gilmer a travaillé sur le problème la nuit, après avoir terminé son travail chez Google, et les week-ends tout au long de la seconde moitié d'octobre et début novembre. Il a été encouragé par des idées qu'un groupe de mathématiciens avait explorées des années plus tôt dans un collaboration ouverte sur le blog d'un éminent mathématicien nommé Tim Gowers. Il a également travaillé avec un manuel à ses côtés afin de pouvoir rechercher des formules qu'il avait oubliées.
"On pourrait penser que quelqu'un qui arrive avec un bon résultat ne devrait pas avoir à consulter le chapitre 2 de Éléments de théorie de l'information, mais je l'ai fait », a déclaré Gilmer.
La stratégie de Gilmer était d'imaginer une famille à union fermée dans laquelle aucun élément n'apparaissait même dans 1% de tous les ensembles - un contre-exemple qui, s'il existait vraiment, falsifierait la conjecture de Frankl.
Supposons que vous choisissiez au hasard deux ensembles, A et B, dans cette famille et que vous considériez les éléments qui pourraient se trouver dans ces ensembles, un à la fois. Demandez maintenant : Quelles sont les chances que l'ensemble A contienne le chiffre 1 ? Et l'ensemble B ? Étant donné que chaque élément a un peu moins de 1% de chances d'apparaître dans un ensemble donné, vous ne vous attendriez pas à ce que A ou B contienne 1. Ce qui signifie qu'il y a peu de surprise - et peu d'informations acquises - si vous apprenez que ni l'un ni l'autre en fait Est-ce que.
Ensuite, pensez à la probabilité que l'union de A et B contienne 1. C'est encore peu probable, mais c'est plus probable que les chances qu'il apparaisse dans l'un ou l'autre des ensembles individuels. C'est la somme de la probabilité qu'il apparaisse dans A et de la probabilité qu'il apparaisse dans B moins la probabilité qu'il apparaisse dans les deux. Donc, peut-être un peu moins de 2 %.
C'est encore bas, mais c'est plus proche d'une proposition 50-50. Cela signifie qu'il faut plus d'informations pour partager le résultat. En d'autres termes, s'il existe une famille à union fermée dans laquelle aucun élément n'apparaît dans au moins 1% de tous les ensembles, il y a plus d'informations dans l'union de deux ensembles que dans l'un ou l'autre des ensembles eux-mêmes.
"L'idée de révéler les choses élément par élément et de regarder la quantité d'informations que vous apprenez est extrêmement intelligente. C'est l'idée principale de la preuve », a déclaré Ryan Alweiss de l'Université de Princeton.
À ce stade, Gilmer commençait à se rapprocher de la conjecture de Frankl. C'est parce qu'il est facile de démontrer que dans une famille fermée, l'union de deux ensembles contient nécessairement moins d'informations que les ensembles eux-mêmes — pas plus.
Pour comprendre pourquoi, pensez à cette famille fermée par union contenant les 1,024 1 ensembles différents que vous pouvez créer à partir des nombres 10 à 1,024. Si vous choisissez deux de ces ensembles au hasard, vous obtiendrez en moyenne des ensembles contenant cinq éléments. (Sur ces 252 120 ensembles, XNUMX contiennent cinq éléments, ce qui en fait la taille d'ensemble la plus courante.) Vous êtes également susceptible de vous retrouver avec une union contenant environ sept éléments. Mais il n'y a que XNUMX façons différentes de créer des ensembles contenant sept éléments.
Le fait est qu'il y a plus d'incertitude sur le contenu de deux ensembles choisis au hasard que sur leur union. L'union tend vers des ensembles plus grands avec plus d'éléments, pour lesquels il y a moins de possibilités. Lorsque vous prenez l'union de deux ensembles dans une famille à union fermée, vous savez en quelque sorte ce que vous allez obtenir - comme lorsque vous lancez une pièce biaisée - ce qui signifie que l'union contient moins d'informations que les ensembles qui la composent.
Avec cela, Gilmer avait une preuve. Il savait que si aucun élément n'apparaissait dans même 1% des ensembles, le syndicat était obligé de contenir plus d'informations. Mais le syndicat doit contenir moins d'informations. Par conséquent, il doit y avoir au moins un élément qui apparaît dans au moins 1 % des ensembles.
La poussée à 50
Lorsque Gilmer a publié sa preuve le 16 novembre, il a inclus une note indiquant qu'il pensait qu'il était possible d'utiliser sa méthode pour se rapprocher encore plus d'une preuve de la conjecture complète, élevant potentiellement le seuil à 38 %.
Cinq jours plus tard, trois différent groupes des mathématiciens ont publié des articles à quelques heures d'intervalle qui s'appuyaient sur le travail de Gilmer pour faire exactement cela. Supplémentaire papiers suivi, mais le sursaut initial semble avoir poussé les méthodes de Gilmer aussi loin qu'elles le peuvent ; arriver à 50% nécessitera probablement de nouvelles idées supplémentaires.
Pourtant, pour certains des auteurs des articles de suivi, atteindre 38% était relativement simple, et ils se sont demandé pourquoi Gilmer ne l'avait pas fait lui-même. L'explication la plus simple s'est avérée être la bonne : après plus d'une demi-décennie sans mathématiques, Gilmer ne savait tout simplement pas comment effectuer une partie du travail d'analyse technique nécessaire pour réussir.
"J'étais un peu rouillé, et pour être honnête, j'étais coincé", a déclaré Gilmer. "Mais j'étais impatient de voir où la communauté l'emmènerait."
Pourtant, Gilmer pense que les mêmes circonstances qui l'ont laissé hors de la pratique ont probablement rendu sa preuve possible en premier lieu.
"C'est la seule façon dont je peux expliquer pourquoi j'ai pensé au problème pendant un an à l'université et n'ai fait aucun progrès, j'ai abandonné les mathématiques pendant six ans, puis je suis revenu au problème et j'ai fait cette percée", a-t-il déclaré. "Je ne sais pas comment l'expliquer autrement que d'être dans l'apprentissage automatique a biaisé ma pensée."
Correction: 3 janvier 2023
Le titre original faisait référence à Gilmer comme un "ingénieur Google". En fait, il est chercheur.
