Travaillant le jour et effectuant des recherches la nuit, les chercheurs de Google Brain ont résolu une conjecture qui laisse perplexe la communauté mathématique depuis des décennies.

À la mi-octobre 2022, Justin Gilmer s'est envolé de Californie pour New York pour rendre visite à son ancien mentor Michael Saks, mathématicien à l'université Rutgers, sur la côte Est.

Pendant les souvenirs, ils n'ont pas parlé de mathématiques. En fait, Gilmer n’a pas sérieusement réfléchi aux mathématiques depuis qu’il a obtenu son doctorat à l’Université Rutgers en 2015. À cette époque, il décide de ne pas poursuivre une carrière universitaire et commence à apprendre la programmation en autodidacte. Au cours d'un dîner avec Saks, Gilmer a parlé à son mentor de son travail chez Google : l'apprentissage automatique et l'intelligence artificielle.

En marchant sur le chemin du campus, Gilmer a rappelé qu'en 2013, il avait passé plus d'un an à marcher sur ce chemin, en réfléchissant à un problème appelé « Union Closed Set Conjecture (également connue sous le nom de Frankl Conjecture) ». Cela a toujours été un problème inutile. Malgré tous ses efforts, Gilmer n’a réussi qu’à apprendre par lui-même pourquoi ce problème apparemment simple concernant une collection de nombres était si difficile à résoudre.

Mais après cette visite sept ans plus tard, Gilmer a soudain eu une nouvelle inspiration. Il a commencé à réfléchir à la manière d’appliquer la théorie de l’information pour résoudre et clôturer l’ensemble des conjectures. Après un mois de recherche, la voie de la preuve ne cessait de s'ouvrir. En novembre, il a publié les résultats sur arXiv, annonçant des progrès significatifs dans la preuve de l'ensemble de la conjecture.

Lien papier : https://arxiv.org/pdf/2211.09055.pdf

Cet article a déclenché une vague de recherches de suivi. Des mathématiciens de l'Université d'Oxford, du MIT et de l'Institute for Advanced Study, entre autres, ont rapidement commencé à travailler sur la nouvelle méthode de Gilmer.

Qu'est-ce que la conjecture d'ensemble fermé d'union ?

La conjecture d'ensemble fermé est liée à des ensembles de nombres, tels que {1, 2} et {2, 3, 4}. Vous pouvez effectuer des opérations sur des ensembles, notamment prendre leur union, ce qui les fusionne. Par exemple, l'union de {1, 2} et {2, 3, 4} est {1, 2, 3, 4}.

Un ensemble ou une famille est dit "union fermée" si l'union de deux ensembles quelconques de la famille est égale à n'importe quel ensemble existant dans la famille. Par exemple, considérons cette famille de quatre ensembles : {1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.

En combinant n'importe quelle paire, vous obtiendrez un ensemble qui existe déjà dans la famille, on dit donc que cette famille est un ensemble fermé.

Les mathématiciens ont discuté et clôturé la conjecture d'ensemble dès les années 1960, mais ce n'est qu'en 1979 qu'elle a reçu sa première déclaration formelle, dans un article de Péter Frankl, un mathématicien hongrois, il a immigré au Japon dans les années 1980. En plus des mathématiques, il aime aussi les spectacles de rue.

Frankl a supposé que si une famille d'ensembles est un ensemble fermé par union, alors elle doit avoir au moins un élément (ou un nombre) qui apparaît dans au moins la moitié des ensembles. Il s’agit d’un seuil naturel pour deux raisons.

​

Justin Gilmer

Tout d'abord, dans l'exemple d'une famille d'ensembles prête à l'emploi et fermée, où tous les éléments apparaissent dans exactement 50% des ensembles. Par exemple, vous pouvez utiliser les nombres 1 à 10 pour former tous les différents ensembles, ce qui donne un total de 1 024 ensembles. Ils forment une famille fermée de 512 ensembles dans laquelle apparaît chacun des 10 éléments.

Quand Frankl a proposé cette conjecture, personne n'avait encore proposé d'exemple d'ensemble fermé où la conjecture était invalide. Donc 50 % semble être une prédiction correcte.

Cela ne veut pas dire que c’est facile à prouver. Avant les travaux de Gilmer, de nombreux articles n'avaient réussi qu'à établir des seuils qui variaient en fonction du nombre d'ensembles dans la famille (plutôt qu'un seuil de 50 % qui était le même pour toutes les tailles de familles d'ensembles).

Will Sawin de l'Université de Columbia a déclaré : "On dirait que cela devrait être facile, et cela ressemble à beaucoup de problèmes faciles, mais cela n'a jamais été surmonté

."

Le manque de progrès reflète à la fois la nature insoluble du problème et le fait que de nombreux mathématiciens préfèrent ne pas y penser. Ils craignent de perdre des années de leur carrière à rechercher un problème impossible. Gilmer se souvient d'un jour de 2013, où il s'est rendu au bureau de Saks et a mentionné cela ainsi que la conjecture fermée, et les instructeurs, qui avaient également été aux prises avec le problème, l'ont expulsé de la pièce.

Aperçu de l'incertitude

Après avoir visité Rutgers, Gilmer s'est posé la question dans son esprit, essayant de comprendre pourquoi c'était si difficile. Il s'est rappelé un fait fondamental : si vous avez une famille de 100 combinaisons d'ensembles, il existe 4 950 façons différentes d'en sélectionner deux et de les combiner. Puis il pensa : comment 4 950 combinaisons différentes pourraient-elles correspondre à 100 ensembles si aucun élément n'apparaissait dans ces combinaisons, au moins avec une certaine fréquence ?

À ce stade, il est déjà sur le chemin de la résolution, même s’il ne le sait pas encore.

La théorie de l'information a été développée dans la première moitié du 20e siècle, notamment dans l'article de Claude Shannon de 1948 « Une théorie mathématique de la communication ». Cet article fournit une manière précise de calculer la quantité d'informations requise pour envoyer un message, en fonction du degré d'incertitude entourant ce que le message exprime. Ce lien entre information et incertitude constitue la perspicacité remarquable de Shannon.

La théorie de l'information apparaît fréquemment en combinatoire, un domaine des mathématiques concerné par le comptage d'objets que Gilmer a étudié en tant qu'étudiant diplômé. Mais alors qu'il rentrait chez lui en Californie, il craignait que la manière dont il associait la théorie de l'information à la conjecture de l'ensemble fermé de l'union ne relève de la naïveté d'un amateur.

"Pour être honnête, je suis un peu surpris que personne n'y ait pensé auparavant", a déclaré Gilmer. "Mais peut-être que je ne devrais pas être surpris, car j'y réfléchis moi-même depuis un an et je comprends la théorie de l'information."

Explorer les problèmes

L'étude des mathématiques de Gilmer vient de son amour des mathématiques. Il est principalement occupé par son travail quotidien chez Google en semaine et se consacre à l'étude de problèmes mathématiques pendant son temps libre. Il emporte également avec lui un manuel de mathématiques au travail afin de pouvoir rechercher à tout moment les formules oubliées. Gilmer garde les pieds sur terre mais regarde également les étoiles : il aime lire les blogs du célèbre mathématicien Tim Gowers, qui le inspirent.

Gilmer a dit humblement : "Peut-être pensez-vous que les gens qui résolvent des problèmes mathématiques ne devraient pas consulter le chapitre 2 des "Éléments de la théorie de l'information (Bases de la théorie de l'information), mais je l'ai fait."

La méthode proposée par Gilmer est Considérons une famille d'ensembles fermés dans laquelle la probabilité qu'un élément apparaisse dans tous les ensembles est inférieure à 1 %. Il s’agit d’un contre-exemple qui, s’il était vrai, fausserait la conjecture de Frankl.

Supposons que deux ensembles A et B soient sélectionnés au hasard dans cette famille, demandez : Quelle est la probabilité que l'ensemble A contienne le nombre 1 ? Qu'en est-il de l'ensemble B ? Étant donné que la probabilité que chaque élément apparaisse dans un ensemble donné est légèrement inférieure à 1 %, vous ne devez pas vous attendre à ce que A ou B contienne 1. Cela signifie que nous ne serions pas surpris si aucun des deux ne contenait réellement 1, et que nous n'obtiendrons certainement pas beaucoup d'informations.

Ensuite, considérons la probabilité que l'union de A et B contienne 1. Ceci est encore improbable, mais légèrement supérieur à la probabilité que 1 apparaisse dans l'un ou l'autre ensemble seul, et correspond à la somme de la probabilité que 1 apparaisse dans A et de la probabilité que 1 apparaisse dans B moins la probabilité que 1 apparaisse dans les deux. Ainsi, la probabilité que l’union de A et B contienne 1 est d’environ moins de 2 %.

C'est encore faible, mais plus proche d'une estimation de 50 %, ce qui signifie que plus d'informations sont nécessaires avant que les résultats puissent être partagés. En d’autres termes, s’il existe une famille d’ensembles englobant une union dans laquelle la probabilité qu’un élément apparaisse dans tous les ensembles est inférieure à 1 %, alors l’union des deux ensembles contient plus d’informations que l’un ou l’autre ensemble pris isolément.

"L'idée de prouver la conjecture élément par élément est très intelligente", a commenté Ryan Alweiss de l'Université de Princeton.

Le travail de Gilmer commence à se rapprocher de la supposition de Frankl. En effet, il est facile de montrer que dans une famille d’ensembles fermés par union, l’union de deux ensembles doit contenir moins d’informations que les deux ensembles eux-mêmes, pas plus.

La raison est simple. Prenons comme exemple la famille d'ensembles fermés union contenant 1024 ensembles différents. Les éléments de chaque ensemble sont des nombres de 1 à 10. Si deux de ces ensembles sont choisis au hasard, on obtiendra en moyenne une union de cinq éléments. (Sur les 1 024 ensembles, 252 contiennent cinq éléments, ce qui constitue la taille d'ensemble la plus courante.) Il est également possible que nous obtenions une union d'environ sept éléments. Mais il n’existe que 120 combinaisons différentes pour obtenir une union de sept éléments.

Le fait est que deux ensembles choisis au hasard contiennent des éléments avec plus d'incertitude que leur union. Une union ressemble davantage à un ensemble plus vaste comportant plus d’éléments et moins de possibilités. Lorsque vous effectuez une opération d'union sur deux ensembles dans une famille d'ensembles fermés par union, vous pouvez connaître le résultat de l'union, tout comme si vous jetiez une pièce de monnaie biaisée. Vous pouvez facilement deviner sur quel côté la pièce atterrira. L'union contient moins d'informations. que les deux ensembles eux-mêmes.

Sur cette base, Gilmer estime que la probabilité qu'au moins un élément apparaisse dans l'ensemble est supérieure ou égale à 1%.

Ce que vous perdez, vous gagnez quelque chose

Lorsque Gilmer a publié sa preuve le 16 novembre, il a joint une note - Il pensait que l'utilisation de sa méthode pourrait être plus proche de la preuve de la conjecture complète, et il pourrait être possible de Le seuil est porté à 38%.

Cinq jours plus tard, trois groupes différents de mathématiciens ont publié à quelques heures d'intervalle des articles s'appuyant sur les travaux de Gilmer. L'épidémie semble avoir poussé l'approche de Gilmer à l'extrême, même si pour atteindre 50 pour cent, il faudra peut-être davantage d'idées nouvelles.

Pour certains auteurs d'articles ultérieurs, cependant, ils se demandaient pourquoi Gilmer n'avait pas réalisé lui-même l'étude relativement simple de 38 %. En fait, la raison n'est pas compliquée : après plus de 5 ans d'absence des mathématiques, Gilmer ne savait tout simplement pas comment effectuer le travail d'analyse technique pour atteindre cet objectif.

"Je suis un peu rouillé et honnêtement, je suis coincé", a déclaré Gilmer. "Mais je suis curieux de voir où la communauté mathématique l'emmènera."

Mais Gilmer pense également que les mêmes raisons qui lui ont coûté l'opportunité de le pratiquer sont, en partie, ce qui a rendu sa preuve possible dans le premier. lieu : « C'est la seule explication pour laquelle je n'ai fait aucun progrès dans la réflexion sur ce problème pendant un an à l'école supérieure, puis j'ai fait une percée lorsque je suis revenu sur ce problème après avoir quitté les mathématiques pendant six ans. En plus des changements dans ma réflexion. causé par l’apprentissage automatique, je ne connais pas d’autre explication. »

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!