Choux romanesco, Vache qui rit et intégrales curvilignes

Szemerédi, go !

Après un mois d'hibernation, je me dois de réouvrir le blog pour annoncer quelque chose de très important : il s'est passé quelque chose sur la planète maths ! Le 22 mars dernier, un prix mathématique a été remis, et pas n'importe lequel : le prix Abel. Et pour la deuxième fois, c'est un hongrois qui décroche la récompense suprême : le célèbre Endre Szemerédi !

Endre
Endre Szemerédi, regard langoureux, sourire enjoleur.

Faisons bref : le prix Abel, c'est le prix Nobel des mathématiques (à ne pas confondre avec la médaille Fields, qui est aussi le prix Nobel des mathématiques). Remis par l'académie norvégienne des sciences et des lettres, elle récompense ce qui se fait de mieux en matière de mathématiciens vivants. Cette année, c'est donc Endre Szemerédi qui a été récompensé, «pour ses contributions fondamentales aux mathématiques discrètes et à la science de l'informatique théorique, et en reconnaissance du retentissement profond et durable de ces contributions sur la théorie additive des nombres et la théorie ergodique». S'il fallait résumer de manière très grossière, on pourrait dire que sans lui, Internet n'existerait pas (mais on va éviter de faire ce genre de raccourcis).

Le domaine de prédilection de Szemerédi, c'est donc les mathématiques discrètes. Par exemple, pour modéliser les mouvements d'un fluide, on va s'intéresser aux pressions ou aux vitesse de tout points en fonction du temps pour en déduire des équations dans le meilleur des cas différentielles : ça, c'est le travail des mathématiques continues. Le travail de Szemerédi est donc l'exact opposé.

Le théorème de Szemerédi
Avant de parler du théorème, rappelons qu'une progression arithmétique, c'est une suite où chaque pas (la "raison") est de la même longueur. Par exemple, 4; 7; 10; 13; 16; 19; 22 est une suite arithmétique de longueur 7 et de raison 3.

L'œuvre la plus célèbre de Szemerédi restera donc avant tout sa démonstration en 1975 de la conjecture d'Erdős–Turán, énoncée 40 ans plus tôt : toute suite d'entiers de densité non nulle contient une progression arithmétique arbitrairement longue ! Quand on sait à quel point ses prédécesseurs ont galéré sur le cas des progressions arithmétiques de longueur 3 (Roth, 1956) et de longueur 4 (Szemerédi, 1969), il mérite le respect. Trente ans plus tard, ce théorème deviendra le théorème de Green-Tao ("La suite des nombres premiers contient des suites arithmétiques arbitrairement longues.")

Le théorème de Szemerédi, comme celui de Green-Tao, reste un cas particulier d'une conjecture à 3000$ (la conjecture d'Erdõs) : si la série des inverses d'une suite entière positive diverge, alors elle admet une progression arithmétique arbitrairement longue.

Mais au fait, que dit exactement ce théorème ?
Pour le comprendre, prenons une proportion p (par exemple, 40%) et un nombre k (par exemple, 3). Le théorème énonce donc que si l'on prend au moins 40% des nombres entre 1 et N (N étant un nombre assez grand qui dépend de p et de k), on pourra y trouver une progression arithmétique de 3 termes (une suite où la différence entre deux termes consécutifs est constante). 

Le nombre N, dans ce cas-là, est 42. Si vous prenez 17 nombres entre 1 et 42, vous serez certain d'y trouver une suite arithmétique de 3 termes ! La preuve en image :

1, 2, 4, 6, 9, 14, 15, 17, 18, 20, 21, 25, 31, 32, 36, 40, 42
(en cherchant un peu, vous ne tarderez pas à en trouver d'autres) 

Ce théorème fonctionne pour n'importe quelle proportion p (aussi petite soit-elle), et pour n'importe quelle longueur k (aussi grande soit-elle). Ainsi, en ne gardant que 1% de la totalité des nombres entiers, on peut quand même y trouver des suites arithmétiques de longueur 200.

Le même théorème (démontré également par Szemerédi) existe en deux dimensions : pour une proportion p donnée, on peut trouver une grille assez grande contenant p points dans lequel il existe un "coin" (trois points de coordonnées (x,y), (x+h,y) et (x,y+h)).

Au cours de sa démonstration, Szemerédi démontrera un lemme sur le moment anecdotique, mais qui deviendra finalement encore plus célèbre que le théorème en lui-même : le lemme de régularité. Ce lemme/théorème deviendra  central en théorie des graphes, ce qui n'est pas rien.

Le théorème de Ramsey
Si vous réunissez un nombre suffisamment grand de personnes dans un même endroit, alors
- soit il y aura un groupe de s personnes où chacun connaît tous les autres
- soit il y aura un groupe de t personnes où personne ne se connaît.
C'est ce qu'énonce le théorème de Ramsey (bien qu'il ait plutôt parlé de sous-graphes complets monochromatiques d'un graphe complet coloré)

Le nombre de personnes à réunir dépend évidemment de s et de t. Par exemple, dans le cas s=t=3, il faut réunir au moins 6 personnes :

Graphes
A gauche, une réunion de 5 personnes, à droite, une réunion de 6 personnes
Deux personnes sont reliées en vert si elles se connaissent, en rouge sinon.
A gauche, il n'y a pas de triangle vert (pas de groupes de 3 où tout le monde se connaît), ni de triangle rouge (un groupe de 3 où personne ne connaît personne).
A droite, on trouvera toujours un triangle vert ou un triangle rouge. Ici, trois personnes se connaissent. 

Le nombre minimal de personnes a réunir pour qu'il existe un groupe de 4 personnes dans lequel chacun se connaît ou bien personne ne se connaît (cas s=t=4) est 18. Pour s=t=5, ce nombre minimal est quelque part entre 43 et 49, et il semble très difficile d'en avoir une estimation plus précise.

Szemerédi, avec l'aide de Ajtai and Komlós, s'est attelé à chercher une bonne estimation de ce nombre dans le cas s=3 et t quelconque. Leurs conclusions ont plutôt satisfait la communauté.

Le problème des ragots
Bon, on ne va pas s'amuser à lister tous les travaux de Szemerédi, puisqu'il a écrit plus de 200 papiers, qui ont donné des choses très précieuses, comme le théorème de Szemerédi–Trotter, le théorème de Erdős–Szemerédi, le lemme de Balog–Szemerédi–Gowers ou le réseau de tri de Ajtai–Komlós–Szemerédi. Mais j'aimerais parler d'un important papier co-écrit par Szemerédi intitulé "A cure for telephone disease".

Notre prix Abel s'est donc intéressé au problème suivant :
Considérons n femmes, chacune au courant d'un scoop d'envergure mondiale. Lorsque deux femmes se téléphonent, elles se partagent l'ensemble des ragots dont elles ont la connaissance. Combien faudra-t-il au minimum de coups de fil pour que chacune soit au courant de tous les potins ?

Ainsi, si n=1, il faudra 0 coup de téléphone ;
si n=2, il faudra 1 coup de téléphone ;
si n=3, il faudra 3 coups de téléphone ;
si n=4, il faudra 4 coups de téléphone ;
si n=5, il faudra 6 coups de téléphone ;

Regots
La stratégie la plus efficace pour que 9 femmes se partagent 9 ragots (chaque arête du graphe correspond à un coup de téléphone, le nombre correspond à l'ordre dans lequel il faut les effectuer).

Ils n'ont pas tardé à déterminer la solution tant attendue : au delà de 4 femmes, il faudra 2n-4 coups de téléphone (au minimum) !


Sources :
Site officiel du prix Abel, avec un max d'informations sur Szemerédi
A cure for telephone disease - Hajnal, Milner et Szemerédi  

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : ,

Commentaires sur Szemerédi, go !

    Petite coquille

    Très intéressant comme d'habitude.
    Il y a par contre une petite coquille dans l'illustration du théorème de Ramsey. Tu écris « à gauche il y a forcément un triangle vert ou un triangle rouge » tu voulais écrire « à droite », non ?

    Posté par judu, 25 mars 2012 à 11:25 | | Répondre
  • Encore plus de ragots

    Salut, très intéressant.
    Sur le probleme des ragots il me semble avoir buté sur une question à l'époque:
    Mettons qu'à chaque pas de temps on puisse avoir autant de coup de téléphone simultanés qu'on désire du moment qu'ils ne font intervenir que des couples disjoints d'interlocuteur.
    Combien faut il de pas de temps pour que tout le monde soit au courant de tout?

    Posté par Clydevil, 28 mars 2012 à 14:56 | | Répondre
  • Et bien entendu, ce sont des femmes qui sont associées à la diffusion des ragots...
    Bravo, belle mentalité d'asocial.

    Posté par lecteur, 14 novembre 2012 à 16:39 | | Répondre
  • lecteur > Il faut savoir s'amuser des clichés ! (Cela dit, je n'ai fait que reprendre l'énoncé de Szemerédi !)

    Posté par El Jj, 14 novembre 2012 à 18:46 | | Répondre
  • Bonsoir,
    y'a un truc qui me chagrine dans le texte : "en ne gardant que 1% de la totalité des nombres entiers"...
    N'étant pas un super mathématicien, je me trompe peut-être : toujours est-il qu'il me semble que le nombre de nombres entiers est infini, par conséquent 1% de ce nombre est aussi infini, non ?
    On a donc autant de chance de trouver "des suites arithmétiques de longueur 200" en prenant en compte la totalité des nombres entiers qu'en n'en prenant que 1%.
    J'en conviens, ça mériterait sûrement une démonstration que je suis absolument incapable de développer...

    Ceci dit, le prix Abel ou la médaille Fields, ce serait plus "ce qu'aurait été le prix Nobel de mathématique s'il avait existé" que "c'est le prix Nobel de mathématiques", mais c'est seulement un façon de présenter les choses (pour éviter que Nobel se retourne dans sa tombe)

    Posté par Djoe l'indien, 04 avril 2014 à 20:33 | | Répondre
  • @Djoe l'indien > Effectivement, 1% des nombres entiers reste toujours infini. Mais pour y trouver une suite arithmétique de raison 200, il faudra aller chercher très loin. Ce que dit le théorème, c'est que ce "très loin" ne dépend que du choix de la proportion et de la raison, et pas de la façon dont on a choisi ce 1% des nombres entiers. Et ça, c'est loin d'être évident.

    Pour cette affaire de prix Nobel des mathématiques, c'est plus une blague qu'autre chose. Dès qu'un prix prestigieux est remis dans un domaine qui n'est pas récompensé par le Nobel, on parle de "prix Nobel de ...". (voir cet article : http://eljjdx.canalblog.com/archives/2012/12/30/25773585.html )

    Posté par El Jj, 05 avril 2014 à 11:24 | | Répondre
Nouveau commentaire
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.