Endre Szemerédi : Dans tout chaos, il y a un ordre

Six mois après avoir commencé ses études de médecine, Endre Szemerédi a décidé qu'il ne se faisait pas confiance avec un scalpel — il doutait, a-t-il déclaré plus tard, de sa capacité à « faire un travail comportant une telle responsabilité » — et a abandonné. Il a erré pendant un certain temps, puis s'est inscrit en mathématiques, et a été affecté par un accident administratif à un directeur de thèse qu'il n'avait jamais demandé. Cette erreur de classement l'a conduit à Moscou sous la direction d'Israel Gelfand, l'un des grands mathématiciens du XXe siècle, plutôt que d'Alexander Gelfond, que Szemerédi avait en fait sollicité. C'est l'un des meilleurs accidents du domaine.

De Budapest à Moscou par erreur

Szemerédi est né le 21 août 1940 à Budapest. Après sa brève et abandonnée tentative en médecine, il a obtenu son diplôme de premier cycle à l'université Eötvös Loránd de Budapest avant de poursuivre ses études de master et de doctorat à l'université d'État de Moscou. Là-bas, sous la direction de Gelfand — l'erreur administrative qui l'a envoyé vers le mauvais superviseur — il a entamé la carrière en mathématiques discrètes qui allait finalement lui valoir une reconnaissance proche de la médaille Fields, rarement accordée à la combinatoire : le prix Abel.

Le théorème qui porte son nom

L'accomplissement déterminant de Szemerédi, annoncé en 1975, a résolu une conjecture que Paul Erdős et Pál Turán avaient formulée des décennies plus tôt et qui avait résisté à toutes les tentatives depuis : tout ensemble de nombres naturels de densité supérieure positive — en gros, tout ensemble qui ne s'amenuise pas jusqu'à disparaître par rapport à la droite numérique entière — doit contenir des progressions arithmétiques de toute longueur, quelle que soit leur importance. C'est une affirmation sur l'ordre caché : aussi irrégulier ou dispersé que puisse paraître un ensemble d'entiers suffisamment important, des séquences structurées y sont inévitablement enfouies. Le comité du prix Abel a résumé plus tard l'esprit de son travail en une seule phrase : « dans tout chaos, il y a un ordre ».

Le lemme de régularité

La preuve de ce théorème a produit quelque chose d'encore plus important que le théorème lui-même. En chemin, Szemerédi a introduit ce qu'on appelle aujourd'hui le lemme de régularité de Szemerédi, un résultat structurel montrant que tout graphe suffisamment grand peut être partitionné en un nombre borné de morceaux qui se comportent, au sens statistique précis, de manière presque aléatoire les uns par rapport aux autres. Cela semble être un lemme technique ; il est devenu l'un des outils centraux de la combinatoire moderne, sous-tendant les tests de propriétés, la théorie des limites de graphes et une grande part de la théorie extrémale des graphes développée au cours des décennies suivantes. Des médaillés Fields comme Timothy Gowers et László Lovász ont consacré des conférences entières à retracer ses conséquences — un cas rare où le sous-produit d'une preuve dépasse en influence son théorème original.

Un ensemble de résultats nommés

La carrière de Szemerédi a produit un nombre inhabituellement élevé de résultats qui portent aujourd'hui son nom aux côtés de ses collaborateurs : le théorème de Szemerédi-Trotter en géométrie d'incidence, qui délimite le nombre de fois que des points et des lignes dans le plan peuvent se rencontrer ; le théorème de Hajnal-Szemerédi sur la coloration des graphes ; le théorème d'Erdős-Szemerédi sur les sommes et les produits dans les ensembles finis, un résultat fondamental dans ce qui est devenu le domaine de la combinatoire arithmétique ; et, avec Miklós Ajtai, le théorème des coins (corners theorem). Avec Ajtai et János Komlós, il a établi des bornes influentes sur les nombres de Ramsey et a construit des réseaux de tri à profondeur optimale — une rare excursion des mathématiques pures vers l'informatique théorique qui a aidé à justifier son futur ancrage académique dans un département d'informatique. Avec Ajtai, Václav Chvátal et Monroe Newborn, il a également prouvé l'inégalité du nombre de croisements, une borne fondamentale en dessin de graphes. À travers plus de deux cents articles publiés, le fil conducteur est cohérent : trouver une structure rigide et inévitable à l'intérieur d'objets — ensembles d'entiers, graphes, configurations de points — qui semblent désordonnés en surface.

Une carrière américaine bâtie sur des fondations hongroises

Szemerédi a rejoint l'université Rutgers en 1986 en tant que professeur d'informatique de l'État du New Jersey, poste qu'il occupe toujours en tant qu'émérite, tout en restant affilié de façon permanente à l'Institut de mathématiques Alfréd Rényi à Budapest, foyer institutionnel des mathématiques hongroises depuis le milieu du XXe siècle. Entre-temps, il a occupé des postes de professeur invité à Stanford, McGill, l'université de Caroline du Sud et l'université de Chicago, ainsi qu'un poste de membre à l'Institute for Advanced Study de Princeton — une carrière couvrant la migration mathématique de la guerre froide, de la Hongrie et de la sphère soviétique vers les universités de recherche américaines.

Reconnaissance

Les honneurs se sont accumulés sur cinq décennies : le prix Alfréd Rényi en 1973 et le prix George Pólya en 1975, dans les années qui ont suivi immédiatement la parution de son théorème ; le prix Leroy P. Steele et le prix Rolf Schock en mathématiques, tous deux en 2008 ; son élection à l'Académie nationale des sciences des États-Unis en 2010 ; et, en 2012, le prix Abel lui-même, décerné « pour ses contributions fondamentales aux mathématiques discrètes et à l'informatique théorique, et en reconnaissance de l'impact profond et durable de ces contributions sur la théorie additive des nombres et la théorie ergodique » — une citation qui crédite explicitement son travail pour avoir remodelé des domaines bien au-delà de la combinatoire strictement définie. La Hongrie l'a fait récipiendaire de l'ordre de Saint-Étienne en 2020.

Pourquoi Endre est appelé un génie

L'argument en faveur du génie de Szemerédi est aussi limpide que les mathématiques le permettent : une seule preuve, d'une seule conjecture de longue date, a généré un outil — le lemme de régularité — dont l'influence en aval sur toute une discipline dépasse sans doute celle du théorème qu'il était censé démontrer. Ce type d'impact de second ordre, où la méthode survit et dépasse son objectif initial, est l'un des marqueurs les plus clairs d'un esprit opérant au niveau structurel le plus profond plutôt que se contentant de résoudre le problème devant lui. Le langage même du comité du prix Abel — localiser l'ordre au sein du chaos — n'est pas une hyperbole ; c'est une paraphrase juste de ce que fait réellement le lemme de régularité, et le fait que Gowers et Lovász, eux-mêmes parmi les figures les plus décorées de la discipline, aient construit des conférences majeures autour de l'explication de ses conséquences à d'autres mathématiciens est une forme de reconnaissance par les pairs difficile à fabriquer ou à gonfler.

S'il y a une mise en garde, elle est de l'ordre de l'étroitesse plutôt que de l'exagération : la renommée de Szemerédi repose massivement sur des résultats en mathématiques discrètes et en combinatoire, des domaines qui, pendant une grande partie du XXe siècle, étaient considérés par certaines parties de l'establishment mathématique comme moins prestigieux que l'analyse, la géométrie ou la théorie des nombres dans leurs formes classiques — le prix Abel décerné à un combinatoricien a été perçu à l'époque comme un argument implicite que le domaine méritait une reconnaissance qu'il avait tardé à recevoir. Cela ne diminue pas le travail ; cela signifie que le qualificatif de « génie » ici suit une forme spécifique et technique de perspicacité structurelle plutôt que le genre de renommée universelle attachée aux physiciens ou aux mathématiciens dont les résultats sont célèbres même en dehors de leur domaine.

Héritage

Le lemme de régularité est désormais enseigné comme un matériau standard dans les cours de combinatoire des cycles supérieurs dans le monde entier et reste un moteur actif de nouvelles recherches, y compris dans des domaines — informatique théorique, combinatoire additive, théorie des limites de graphes — qui existaient à peine lorsque Szemerédi l'a écrit pour la première fois en 1975. Toujours actif en tant que chercheur émérite au milieu de ses quatre-vingts ans, il demeure l'un des cas les plus évidents en mathématiques modernes de la méthode d'une seule preuve devenant plus conséquente que le théorème qu'elle était destinée à établir.