Un mathématicien a résolu un problème vieux de 30 ans à la frontière entre les mathématiques et l'informatique. Il a utilisé une preuve innovante et élégante qui a émerveillé ses collègues de sa simplicité.
Hao Huang, professeur adjoint de mathématiques à l'Université Emory d'Atlanta, a prouvé une idée mathématique appelée la conjecture de sensibilité, qui, en termes incroyablement approximatifs, fait une réclamation sur combien vous pouvez changer l'entrée d'une fonction sans changer la sortie (ce est sa sensibilité).
Dans les décennies qui se sont écoulées depuis que les mathématiciens ont proposé pour la première fois la conjecture de sensibilité (sans le prouver), les informaticiens théoriques ont réalisé qu'elle avait d'énormes implications pour déterminer les moyens les plus efficaces de traiter l'information.
Ce qui est remarquable dans la preuve de Huang, selon d'autres experts dans le domaine, ce n'est pas seulement que Huang l'a réussi, mais aussi la manière élégante et simple dont il l'a fait. Sa preuve n'a pas été officiellement révisée par des pairs ni publiée dans aucun journal de mathématiques. Mais peu de temps après que Huang l'ait mis en ligne le 1er juillet, ses collègues l'ont rapidement accepté comme un fait.
"Chaque fois qu'il y a une annonce comme celle-ci", a écrit Scott Aaronson, informaticien théoricien de l'Université du Texas à Austin, "~ 99% du temps, soit la preuve est fausse, soit, en tout cas, c'est trop compliqué pour les étrangers de l'évaluer. rapidement. C'est l'un des 1% de cas restants. Je suis plutôt confiant que la preuve est bonne. Pourquoi? Parce que je l'ai lu et compris. Cela m'a pris environ une demi-heure. "
Ryan O'Donnell, professeur d'informatique qui étudie la théorie des nombres à l'Université Carnegie Mellon de Pittsburgh, a souligné que la preuve de Huang peut être résumée en un seul tweet:
Qu'est-ce que Huang a réellement prouvé?
Par souci de simplicité, imaginez un cube 3D avec des côtés d'une longueur de 1 unité chacun. Si vous placez ce cube dans un système de coordonnées 3D (ce qui signifie qu'il a des mesures dans trois directions), un coin aurait les coordonnées (0,0,0), celui à côté pourrait être (1,0,0), le celui au-dessus pourrait être (0,1,0) et ainsi de suite. Vous pouvez prendre la moitié des coins (quatre coins) sans avoir de paire de voisins: (0,0,0), (1,1,0), (1,0,1) et (0,1,1) aren ' t voisins. Vous pouvez le montrer en regardant le cube, mais nous le savons aussi car tous sont différents de plus d'une coordonnée.
La conjecture de sensibilité consiste à trouver le nombre de voisins que vous avez lorsque vous prenez plus de la moitié des coins d'un cube de dimension supérieure ou d'un hypercube, a déclaré le mathématicien de l'Université hébraïque Gil Kalai. Vous pouvez écrire les coordonnées de l'hypercube sous forme de chaînes de 1 et de 0, où le nombre de dimensions est la longueur de la chaîne, a déclaré Kalai à Live Science. Pour un hypercube 4D, par exemple, il y a 16 points différents, ce qui signifie 16 chaînes différentes de 1 et de 0 qui ont quatre chiffres.
Choisissez maintenant la moitié plus 1 points individuels sur l'hypercube (pour un hypercube 4D, cela signifie choisir neuf - ou 8 + 1 - points différents sur un total de 16).
À partir de ce petit ensemble, trouvez le point avec le plus de voisins - quel est le le minimum nombre de voisins qu'il peut avoir? (Les voisins diffèrent par un seul numéro. Par exemple, 1111 et 1110 sont voisins, car vous n'avez qu'à échanger un chiffre pour transformer le premier en deuxième.)
Huang a prouvé que ce coin doit avoir au moins autant de voisins que la racine carrée du nombre de chiffres - dans ce cas, la racine carrée de 4 - qui est 2.
Pour les dimensions faibles, vous pouvez dire que cela est vrai simplement en vérifiant. Ce n'est pas si difficile de vérifier 16 coordonnées sur le cube (ou "chaînes") pour les voisins, par exemple. Mais chaque fois que vous ajoutez une dimension au cube, le nombre de chaînes double. Le problème devient donc plus difficile à vérifier très rapidement.
L'ensemble de chaînes de 30 chiffres - les coordonnées aux coins d'un cube à 30 dimensions - contient plus d'un milliard de chaînes différentes, ce qui signifie que le cube a plus d'un milliard de coins. Avec des chaînes de 200 chiffres, il y en a plus d'un novemdecillion. C'est un million de milliards de milliards de milliards de milliards de milliards de milliards, ou 1 suivi de 60 zéros.
C'est pourquoi les mathématiciens aiment les preuves: ils montrent que quelque chose est vrai dans tous les cas, pas seulement les plus faciles.
"Si n est égal à un million - cela signifie que nous avons des chaînes de longueur 1 million - alors la conjecture est que si vous prenez 2 ^ 1,000,000-1 et ajoutez 1, alors il y a une chaîne qui a 1000 voisins - la racine carrée d'un million, "Dit Kalai.
La dernière avancée majeure dans la conjecture de sensibilité est survenue en 1988, a déclaré Kalai, lorsque les chercheurs ont prouvé qu'une chaîne doit avoir au moins le logarithme de n voisins. C'est un chiffre bien inférieur; le logarithme de 1 000 000 n'est que de 6. La preuve de Huang vient donc de découvrir qu'au moins 994 autres voisins sont là-bas.
Une preuve élégante et "mystérieuse"
"C'est très mystérieux", a déclaré Kalai à propos des preuves de Huang. «Il utilise des« méthodes spectrales », qui sont des méthodes très importantes dans de nombreux domaines des mathématiques. Mais il utilise des méthodes spectrales d'une manière nouvelle. plus d'applications. "
Essentiellement, Huang a conceptualisé l'hypercube en utilisant des tableaux de nombres dans des lignes et des colonnes (appelées matrices). Huang a trouvé une façon complètement inattendue de manipuler une matrice avec un arrangement inhabituel de -1 et de 1 qui "fait que tout fonctionne comme par magie", a écrit Aaronson sur son blog.
Huang "a pris cette matrice et l'a modifiée de manière très ingénieuse et mystérieuse", a déclaré Kalai. "C'est comme si vous aviez un orchestre et qu'ils jouaient de la musique, et ensuite vous laissez certains des joueurs, je ne sais pas, se tenir sur la tête, et la musique devient complètement différente - quelque chose comme ça."
Cette musique différente s'est avérée être la clé pour prouver la conjecture, a déclaré Kalai. C'est mystérieux, a-t-il dit, car même si les mathématiciens comprennent pourquoi la méthode a fonctionné dans ce cas, ils ne comprennent pas pleinement cette nouvelle "musique" ou dans quels autres cas elle pourrait être utile ou intéressante.
"Pendant 30 ans, il n'y a eu aucun progrès, puis Hao Huang a réglé ce problème, et il a trouvé une preuve très simple que la réponse est la racine carrée de n", A déclaré Kalai." Mais pendant ces 30 années… les gens ont réalisé que cette question est très importante dans la théorie de l'informatique. "
La preuve de Huang est passionnante car elle fait avancer le domaine de l'informatique, a déclaré Kalai. Mais il est également remarquable car il a introduit une nouvelle méthode, et les mathématiciens ne savent toujours pas ce que la nouvelle méthode de Huang pourrait leur permettre d'accomplir.
