Une percée majeure dans la résolution de l'hypothèse vieille de 60 ans met en lumière la façon dont l'ordre commence à y apparaître avec la croissance des systèmes aléatoires
Une équipe de mathématiciens et d'informaticiens a finalement démontré des progrès dans la résolution, à première vue, d'une tâche simple qui a tourmenté les chercheurs pendant près de six décennies.
Cette tâche, définie par les mathématiciens Pal Erdös et Richard Rado en 1960, concerne la fréquence à laquelle on peut s'attendre à l'apparition de motifs ressemblant à un tournesol dans de grands ensembles d'objets - par exemple, dans un grand nombre de points dispersés sur un plan. Bien que le
nouveau résultat ne résout pas complètement l'hypothèse d'Erdös et Rado, il favorise la compréhension des mathématiciens dans l'apparition de structures étonnamment complexes dans des grappes aléatoires. À cette fin, la tâche a été reformulée en termes de fonction informatique, profitant de la relation croissante entre l'informatique théorique et les mathématiques pures.
«Dans ce travail, une idée mathématique se manifeste d'une nouvelle manière, qui deviendra l'idée principale de notre temps. Le résultat lui-même est incroyable », a déclaré
Gil Kalai de l'Université hébraïque de Jérusalem.
L'hypothèse du tournesol fait référence à des ensembles ou ensembles d'objets. Il est plus facile d'imaginer en utilisant l'exemple d'un ensemble de points sur le plan xy. Tout d'abord, sélectionnez un nombre fixe de points qui seront inclus dans chaque ensemble. Dessinez ensuite des boucles aléatoires de sorte que chaque boucle, ou ensemble, inclue un nombre sélectionné de points. Les boucles peuvent se croiser et certains points peuvent tomber dans plusieurs ensembles, ressemblant à un diagramme de Venn.
Si vous dessinez beaucoup de boucles contenant un grand nombre de points, la plupart se croiseront et ressembleront aux subtilités de la vigne. Mais Erdös et Rado ont prédit qu'une structure raffinée en résulterait également: trois ensembles ou plus se croiseraient, laissant le même sous-ensemble de points à l'intersection, tandis qu'aucun de ces ensembles ne se croiserait avec d'autres ensembles.
Si vous supprimez ce sous-ensemble commun de points, les trois ensembles seront situés autour du vide et seront complètement séparés les uns des autres - comme des pétales autour du milieu sombre du tournesol. Le tournesol le plus simple est considéré comme ayant trois ensembles qui ne se croisent pas avec les autres; ces îles sont appelées ensembles disjoints.
Erdös et Rado ont suggéré qu'à mesure que le nombre de boucles augmente, de tels tournesols apparaîtront inévitablement, soit sous forme d'ensembles disjoints, soit sous forme d'ensembles superposés de la manière indiquée. Cette hypothèse du tournesol fait partie d'un domaine plus général des mathématiques appelé
la théorie de Ramsey, qui étudie comment l'ordre commence à y apparaître avec l'augmentation de la taille des systèmes aléatoires.
"Si vous avez un objet mathématique suffisamment grand, une structure doit y être cachée", a déclaré
Shachar Lovet de l'Université de Californie à San Diego, co-auteur d'un nouveau travail sur
lequel Ryan Alweis de Princeton University a également travaillé et Keven Wu de l'Université de Pékin. et
Jiapeng Zhang de l'Université Harvard.
Erdös et Rado voulaient savoir exactement combien d'ensembles et quelle taille était nécessaire pour garantir un tournesol. Ils ont fait le premier pas modeste vers la résolution du problème en définissant le paramètre w, indiquant le nombre de points dans chacun des ensembles. Ensuite, ils ont prouvé qu'il fallait environ w
w d' ensembles de taille w pour garantir qu'un tournesol composé de trois ensembles y apparaîtrait. Donc, si vous souhaitez utiliser des ensembles de 100 points, vous aurez besoin de 100 à
100 ensembles pour garantir l'apparence d'un tournesol.
En même temps, Erdös et Rado ont suggéré qu'en fait le nombre de jeux garantissant un tournesol est beaucoup moins que w
w - et ressemble plus à une constante en degré w (par exemple, 3
w ou 80
w ou 5 000 000
w ). Cependant, ils n'ont pas pu trouver un moyen de prouver leur supposition.
«Ils ont dit que la tâche semblait extrêmement simple et ont été surpris de ne pas pouvoir progresser», a déclaré M. Alveys.
Et ils n'étaient pas seuls. Dans la période qui a suivi leur premier résultat et ce nouveau travail, qui est apparu 60 ans plus tard, seuls deux mathématiciens ont fait au moins quelques progrès sur cette question - puis ils sont allés progressivement, faisant un pas en 1997 et le
second cette année .
"Tout le monde a déjà essayé toutes les idées avec lesquelles les gens se sentent à l'aise", a déclaré
Anup Rao de l'Université de Washington, qui a publié
des travaux supplémentaires simplifiant les méthodes obtenues dans le nouveau résultat. «Et personne n'a pu améliorer la ligne de base établie par Erds et Rado.»
Mais les nouvelles preuves ont fait une percée majeure.
Quatre chercheurs, dont des mathématiciens et des informaticiens, ont pu le faire en divisant la tâche en deux scénarios différents. Dans la première, plus facile, ils ont examiné ce qui se passerait lorsque les ensembles se croisent de manière significative les uns avec les autres, ce qui permet de comprendre beaucoup plus facilement quand un tournesol devrait y apparaître.
"Lorsque vous avez un ensemble d'éléments qui appartiennent à un ensemble plus important, vous pouvez utiliser cette structure", pour rechercher un tournesol, a déclaré Lovet.
Dans un premier temps, les chercheurs se sont demandé s'il existait un ensemble de points appartenant à une partie suffisamment importante de tous les ensembles du système. Ayant trouvé de tels points, dans leur recherche d'un tournesol, ils se sont limités à la seule partie des ensembles qui contiennent cet ensemble de points. Ensuite, ils ont continué à agir de la même manière, affinant la recherche, y compris de moins en moins d'ensembles de systèmes, qui ont de plus en plus de points communs. Cette taille a continué jusqu'à ce qu'ils trouvent leur tournesol.
Dans un deuxième scénario, plus complexe, ils analysent ce qui se passera si les ensembles ne se croisent pas fortement. Dans ce cas, le moyen le plus probable d'obtenir un tournesol est de prendre trois ensembles disjoints. Cependant, il n'est pas facile de prouver que trois ensembles distincts se cachent dans des ensembles plus légèrement entrecroisés.
C'est là que l'informatique entre en jeu. Deux co-auteurs, Lovet et Zhang, tentent depuis plusieurs années d'analyser le problème du tournesol en utilisant les mêmes outils que les informaticiens utilisent pour étudier les fonctions booléennes. Ces fonctions effectuent des opérations sur une séquence de bits - des uns et des zéros - et produisent un seul bit à la fin, correspondant à la véracité ou non d'une instruction de calcul. Par exemple, une fonction booléenne peut être programmée pour renvoyer 1 si au moins un des bits d'entrée est 1 et 0 si aucun des bits d'entrée n'est 1.
Il y a trois ans, Lovet et Zhang ont réalisé que la même question pouvait être posée quant à savoir s'il y avait trois ensembles disjoints parmi un ensemble d'ensembles peu entrecroisés. Tout d'abord, attribuez une étiquette à chaque point de l'ensemble: 1 s'il n'est contenu que dans cet ensemble et 0 dans un autre cas. Une fonction booléenne renvoie 1 (vrai) si chaque point à l'entrée est 1 - c'est-à-dire que chaque point de l'ensemble existe exclusivement dans cet ensemble, ce qui rend cet ensemble disjoint. Le vrai résultat suggère qu'il existe des conditions appropriées pour trouver un tournesol.
Prouvant strictement cette correspondance, les chercheurs ont utilisé des connaissances approfondies concernant les fonctions booléennes pour attaquer le problème du tournesol, qui manquait auparavant de ressources. Ils ont prouvé que les ensembles (log w)
w sont suffisants pour obtenir un tournesol. Un tel résultat ne suffit pas pour prouver l'hypothèse qu'une certaine constante de degré w suffit pour obtenir un tournesol. Mais c'est un résultat d'un ordre de grandeur meilleur que w
w obtenu par Erdös et Rado, et il coïncide à peu près avec le nombre d'ensembles qu'ils ont prédit.
Après un demi-siècle d'échecs, les nouveaux travaux suggèrent que nous verrons bientôt une solution complète. Il améliore également la compréhension de la façon dont des formes spéciales surviennent inévitablement dans la nature mathématique sauvage du hasard.