« Une équipe » de mathématiques prouve l'existence d'un lien essentiel entre l'addition et les ensembles | Magazine Quanta

Dans un ensemble de nombres choisis au hasard, l’addition peut devenir folle.

Additionnez chaque paire d'un tel ensemble et vous obtiendrez une nouvelle liste qui contiendra probablement beaucoup plus de chiffres que celle avec laquelle vous avez commencé. Commencez avec 10 nombres aléatoires, et cette nouvelle liste (appelée sumset) contiendra environ 50 éléments. Commencez avec 100 et le total en comptera probablement environ 5,000 1,000 ; 500,000 XNUMX nombres initiaux aléatoires formeront un ensemble de XNUMX XNUMX nombres.

Mais si votre ensemble initial a une structure, l’ensemble peut se retrouver avec moins de nombres que cela. Considérons un autre ensemble de 10 nombres : tous les nombres pairs de 2 à 20. Étant donné que les différentes paires totalisent le même nombre — 10 + 12 sont identiques à 8 + 14 et 6 + 16 — l'ensemble total ne contient que 19 nombres, pas 50. Cette différence devient de plus en plus profonde à mesure que les ensembles s'agrandissent. Une liste structurée de 1,000 2,000 numéros peut contenir un ensemble de seulement XNUMX XNUMX numéros.

Dans les années 1960, un mathématicien nommé Grégory Freiman a commencé à étudier les ensembles avec de petites sommes dans le but de sonder le lien entre l'addition et la structure des ensembles - un lien crucial qui définit le domaine mathématique de la combinatoire additive. Freiman a fait des progrès impressionnants, prouvant qu'un ensemble avec une petite somme doit être contenu dans un ensemble plus grand dont les éléments sont espacés selon un motif très régulier. Mais ensuite, le domaine a stagné. « La preuve originale de Freiman était extraordinairement difficile à comprendre, au point que personne n'était vraiment absolument sûr qu'elle était correcte. Cela n’a donc pas vraiment eu l’impact qu’il aurait pu avoir », a déclaré Timothy Gowers, mathématicien au Collège de France et à l'Université de Cambridge et médaillé Fields. "Mais alors Imre Rouzsa a fait irruption sur la scène.

Dans une série de deux papiers dans les années 1990, Ruzsa a réaffirmé le théorème de Freiman avec un nouvel argument élégant. Quelques années plus tard, Kataline Marton, un mathématicien hongrois influent décédé en 2019, a peaufiné la question de savoir ce qu'implique un petit ensemble sur la structure de l'ensemble original. Elle a remplacé les types d'éléments apparaissant dans l'ensemble et le type de structure que les mathématiciens devraient rechercher, pensant que cela permettrait aux mathématiciens d'extraire encore plus d'informations. La conjecture de Marton a des liens avec les systèmes de preuve, la théorie du codage et la cryptographie, et occupe une place exaltée dans la combinatoire additive.

Sa conjecture "semble vraiment être l'une des choses les plus fondamentales que nous n'avons pas comprises", a déclaré Ben Vert, mathématicien à l'Université d'Oxford. Cela « sous-tend en quelque sorte beaucoup de choses qui me tiennent à cœur ».

Green s'est associé à Gowers, Freddie Manières de l'Université de Californie à San Diego et Terence tao, médaillé Fields à l'Université de Californie à Los Angeles pour former ce que le mathématicien et blogueur israélien Gil Kalaï appelé un "Notre équipe» des mathématiciens. Ils ont prouvé une version de la conjecture dans un article partagé le 9 novembre.

Filets Katz, un mathématicien de l'Université Rice qui n'a pas participé aux travaux, décrit la preuve comme « magnifiquement simple » – et « plus ou moins complètement inattendue ».

Tao a alors lancé un effort pour formaliser la preuve en "Lean", un langage de programmation qui aide les mathématiciens à vérifier les théorèmes. En quelques semaines seulement, cet effort a réussi. Tôt le mardi matin du 5 décembre, Tao a annoncé que Lean avait prouvé la conjecture sans aucun « désolé » – la déclaration standard qui apparaît lorsque l'ordinateur ne peut pas vérifier une certaine étape. Il s’agit de l’utilisation la plus médiatisée d’un tel outils de vérification depuis 2021, et marque un point d'inflexion dans la manière dont les mathématiciens rédigent les preuves dans des termes qu'un ordinateur peut comprendre. Si ces outils deviennent suffisamment faciles à utiliser pour les mathématiciens, ils pourraient peut-être remplacer le processus d'évaluation par les pairs, souvent long et onéreux, a déclaré Gowers.

Les ingrédients de la preuve mijotaient depuis des décennies. Gowers a conçu ses premiers pas au début des années 2000. Mais il a fallu 20 ans pour prouver ce que Kalai appelle « le Saint Graal » du domaine.

Le groupe

Pour comprendre la conjecture de Marton, il est utile de se familiariser avec le concept de groupe, un objet mathématique constitué d'un ensemble et d'une opération. Pensez aux nombres entiers – un ensemble infini de nombres – et à l’opération d’addition. Chaque fois que vous additionnez deux entiers, vous obtenez un autre entier. L'addition obéit également à quelques autres règles d'opérations de groupe, comme l'associativité, qui permet de changer l'ordre des opérations : 3 + (5 + 2) = (3 + 5) + 2.

Au sein d'un groupe, vous pouvez parfois trouver des ensembles plus petits qui satisfont à toutes les propriétés du groupe. Par exemple, si vous ajoutez deux nombres pairs, vous obtiendrez un autre nombre pair. Les nombres pairs constituent un groupe à part entière, ce qui en fait un sous-groupe des nombres entiers. Les nombres impairs, en revanche, ne constituent pas un sous-groupe. Si vous additionnez deux nombres impairs, vous obtenez un nombre pair, qui ne figure pas dans l'ensemble d'origine. Mais vous pouvez obtenir tous les nombres impairs en ajoutant simplement 1 à chaque nombre pair. Un sous-groupe décalé comme celui-ci est appelé un coset. Il ne possède pas toutes les propriétés d’un sous-groupe, mais il conserve la structure de son sous-groupe de plusieurs manières. Par exemple, tout comme les nombres pairs, les nombres impairs sont tous espacés de manière égale.

Marton supposait que si vous aviez un set, nous l'appellerions A constitué d'éléments de groupe dont la somme n'est pas tellement plus grande que A lui-même, alors il existe un sous-groupe — appelez-le G — avec une propriété spéciale. Changement G plusieurs fois pour créer des cosets, et ces cosets, pris ensemble, contiendront l'ensemble original A. De plus, elle a supposé que le nombre de cosets n'augmentait pas beaucoup plus vite que la taille de la somme – elle pensait que cela devrait être lié par un facteur polynomial, par opposition à une croissance exponentielle beaucoup plus rapide.

Cela peut ressembler à une curiosité hautement technique. Mais comme il s'agit d'un test simple, que se passe-t-il lorsque vous ajoutez seulement deux éléments dans l'ensemble ? — pour la structure globale d'un sous-groupe, c'est très important pour les mathématiciens et les informaticiens. La même idée générale apparaît lorsque les informaticiens tentent de chiffrer les messages afin que vous puissiez décoder juste une partie du message à la fois. Il apparaît également dans les preuves probabilistes vérifiables, une forme de preuve que les informaticiens peuvent vérifier en vérifiant seulement quelques éléments d'information isolés. Dans chacun de ces cas, vous travaillez avec seulement quelques points d'une structure - décodant seulement quelques bits d'un long message ou vérifiant une petite partie d'une preuve complexe - et concluez quelque chose sur une structure plus large et de niveau supérieur.

"Vous pouvez soit prétendre que tout constitue un sous-ensemble important d'un groupe", a déclaré Tom Sanders, un ancien élève de Gowers qui est maintenant un collègue de Green à Oxford, ou vous pouvez « obtenir tout ce que vous vouliez de l'existence de nombreuses coïncidences additives. Ces deux perspectives sont utiles.

Rouzsa a publié la conjecture de Marton en 1999, lui donnant tout le crédit. "Elle est parvenue à cette conjecture indépendamment de moi et de Freiman, et probablement avant nous", a-t-il déclaré. "C'est pourquoi, lorsque je lui ai parlé, j'ai décidé d'appeler cela sa conjecture." Pourtant, les mathématiciens l’appellent désormais la conjecture polynomiale de Freiman-Ruzsa, ou PFR.

Des zéros et des uns

Les groupes, comme de nombreux objets mathématiques, prennent de nombreuses formes différentes. Marton suppose que sa conjecture est vraie pour tous les groupes. Cela reste à démontrer. Le nouvel article le prouve pour un type particulier de groupe, qui prend comme éléments des listes de nombres binaires comme (0, 1, 1, 1, 0). Parce que les ordinateurs fonctionnent en binaire, ce groupe est crucial en informatique. Mais cela a également été utile en combinatoire additive. "C'est comme un décor de jouets dans lequel vous pouvez jouer et essayer des choses", a déclaré Sanders. "L'algèbre est bien plus agréable" que de travailler avec des nombres entiers, a-t-il ajouté.

Les listes ont des longueurs fixes et chaque bit peut être 0 ou 1. Vous les additionnez en ajoutant chaque entrée à son homologue dans une autre liste, avec la règle selon laquelle 1 + 1 = 0. Donc (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR est une tentative de comprendre à quoi peut ressembler un ensemble s'il ne s'agit pas vraiment d'un sous-groupe mais s'il possède des fonctionnalités de type groupe.

Pour rendre le PFR précis, imaginez que vous disposez d'un ensemble de listes binaires appelées A. Maintenant, prenez chaque paire d'éléments de A et additionnez-les. Les sommes résultantes constituent la somme de A, appelée A + A. Si les éléments de A sont choisis au hasard, alors la plupart des sommes sont différentes les unes des autres. S'il y a k éléments dans A, ça veut dire qu'il y en aura autour k²/2 éléments dans le total. Quand k est grand - disons, 1,000 XNUMX - k²/2 est beaucoup plus grand que k. Mais si A est un sous-groupe, chaque élément de A + A est en A, ce qui signifie que A + A est de la même taille que A elle-même.

PFR considère des ensembles qui ne sont pas aléatoires, mais ne sont pas non plus des sous-groupes. Dans ces ensembles, le nombre d'éléments dans A + A est un peu petit — disons, 10kOu 100k. "C'est vraiment utile lorsque votre notion de structure est bien plus riche qu'une simple structure algébrique exacte", a déclaré Shachar Lovett, informaticien à l'Université de Californie à San Diego.

Tous les ensembles que connaissaient les mathématiciens et qui obéissaient à cette propriété « sont assez proches des sous-groupes réels », a déclaré Tao. "C'était l'intuition qu'il n'y avait pas d'autres types de faux groupes qui traînaient." Freiman avait prouvé une version de cette affirmation dans son œuvre originale. En 1999, Ruzsa a étendu le théorème de Freiman des entiers à l'établissement de listes binaires. Il a prouvé que lorsque le nombre d'éléments dans A + A est un multiple constant de la taille de A, A est contenu dans un sous-groupe.

Mais le théorème de Ruzsa exigeait que le sous-groupe soit énorme. L'idée de Marton était de postuler que plutôt que d'être contenu dans un sous-groupe géant, A pourrait être contenu dans un nombre polynomial de cosets d'un sous-groupe qui n'est pas plus grand que l'ensemble d'origine A.

"Je connais une vraie idée quand je vois une vraie idée"

Au tournant du millénaire, Gowers est tombé sur les preuves du théorème de Freiman de Ruzsa alors qu'il étudiait un problème différent concernant les ensembles contenant des chaînes de nombres régulièrement espacés. "J'avais besoin de quelque chose comme ça, en quelque sorte obtenir des informations structurelles à partir d'informations beaucoup plus vagues sur un certain ensemble", a déclaré Gowers. "J'ai eu beaucoup de chance que, peu de temps auparavant, Ruzsa ait produit cette preuve absolument magnifique."

Gowers a commencé à élaborer une preuve potentielle de la version polynomiale de la conjecture. Son idée était de commencer avec un ensemble A dont la somme était relativement petite, puis manipuler progressivement A dans un sous-groupe. S'il pouvait prouver que le sous-groupe résultant était similaire à l'ensemble original A, il pouvait facilement conclure que la conjecture était vraie. Gowers a partagé ses idées avec des collègues, mais personne n'a pu les transformer en une preuve complète. Même si la stratégie de Gowers a été couronnée de succès dans certains cas, dans d'autres, les manipulations ont pris du temps. A plus éloigné de la conclusion souhaitée de la conjecture polynomiale de Freiman-Ruzsa.

Finalement, le domaine a évolué. En 2012, Sanders PFR presque prouvé. Mais le nombre de sous-groupes décalés dont il avait besoin était supérieur au niveau polynomial, bien que de peu. "Une fois qu'il a fait cela, cela signifie que c'est devenu une chose moins urgente, mais cela reste un très beau problème pour lequel j'ai une grande affection", a déclaré Gowers.

Mais les idées de Gowers sont restées gravées dans la mémoire et les disques durs de ses collègues. "Il y a là une vraie idée", a déclaré Green, qui avait également été un élève de Gowers. "Je reconnais une vraie idée quand je vois une vraie idée." Cet été, Green, Manners et Tao ont finalement libéré les idées de Gowers de leur purgatoire.

Green, Tao et Manners ont collaboré pendant 37 pages avant de penser à revenir aux idées vieilles de 20 ans de Gowers. Dans un 23 juin papier, ils avaient utilisé avec succès un concept de la théorie des probabilités appelé variables aléatoires pour sonder la structure d'ensembles avec de petites sommes. En effectuant ce changement, le groupe a pu manipuler ses sets avec plus de finesse. "Le traitement des variables aléatoires est en quelque sorte beaucoup moins rigide que le traitement des ensembles", a déclaré Manners. Avec une variable aléatoire, "je peux modifier légèrement l'une des probabilités, et cela pourrait me donner une meilleure variable aléatoire."

En utilisant cette perspective probabiliste, Green, Manners et Tao pourraient passer du travail avec le nombre d’éléments dans un ensemble à une mesure de l’information contenue dans une variable aléatoire, une quantité appelée entropie. L'entropie n'était pas nouvelle dans la combinatoire additive. En fait, Tao avait tenté pour populariser le concept à la fin des années 2000. Mais personne n’avait encore essayé de l’utiliser sur la conjecture polynomiale de Freiman-Ruzsa. Green, Manners et Tao ont découvert que c'était puissant. Mais ils ne parvenaient toujours pas à prouver cette hypothèse.

Tandis que le groupe réfléchissait à ses nouveaux résultats, il réalisa qu'il avait enfin créé un environnement dans lequel les idées dormantes de Gowers pourraient s'épanouir. S’ils mesuraient la taille d’un ensemble en utilisant son entropie plutôt que son nombre d’éléments, les détails techniques pourraient bien mieux fonctionner. "À un moment donné, nous avons réalisé que ces vieilles idées de Tim d'il y a 20 ans étaient en réalité plus susceptibles de fonctionner que celles que nous essayions", a déclaré Tao. « Nous avons donc réintégré Tim dans le projet. Et puis toutes les pièces s’emboîtent étonnamment bien.

Pourtant, il restait de nombreux détails à comprendre avant qu’une preuve ne soit réunie. "C'était un peu stupide que nous soyons tous les quatre incroyablement occupés avec autre chose", a déclaré Manners. "Vous voulez publier cet excellent résultat et le dire au monde entier, mais vous devez encore rédiger vos examens de mi-session." Finalement, le groupe a réussi et le 9 novembre, ils ont publié leur article. Ils ont prouvé que si A + A n'est pas plus grand que k fois la taille de A, puis A ne peut être couvert que par environ k¹² déplacements d'un sous-groupe qui n'est pas plus grand que A. Cela représente un nombre potentiellement énorme de changements. Mais c'est un polynôme, donc il ne croît pas exponentiellement plus vite que k grossit, comme ce serait le cas si k étaient dans l’exposant.

Quelques jours plus tard, Tao a commencé à formaliser la preuve. Il a dirigé le projet de formalisation en collaboration, en utilisant le package de contrôle de version GitHub pour coordonner les contributions de 25 bénévoles à travers le monde. Ils ont utilisé un outil appelé Plan développé par Patrick Massot, mathématicien à l'université Paris-Saclay, pour organiser les efforts de traduction de ce que Tao appelé « L'anglais mathématique » en code informatique. Blueprint peut, entre autres, créer un tracer décrivant les différentes étapes logiques impliquées dans la preuve. Une fois que toutes les bulles étaient recouvertes de ce que Tao a appelé une « jolie nuance de vert », l’équipe avait terminé. Ils ont découvert quelques fautes de frappe très mineures dans le journal – dans un article en ligne. message, Tao a noté que « les parties du projet les plus intéressantes mathématiquement étaient relativement simples à formaliser, mais ce sont les étapes techniques « évidentes » qui ont pris le plus de temps.

Marton est décédée quelques années seulement avant que sa célèbre conjecture ne soit prouvée, mais la preuve lui fait écho. le travail de la vie sur l'entropie et la théorie de l'information. "Tout fonctionne bien mieux lorsque vous le faites dans ce cadre d'entropie que dans le cadre dans lequel j'essayais de le faire", a déclaré Gowers. "Pour moi, cela semble encore un peu magique."

Quanta mène une série d’enquêtes pour mieux servir notre public. Prenez notre enquête auprès des lecteurs de mathématiques et vous serez inscrit pour gagner gratuitement Quanta marchandise.