Théorème d'Erdős-Szemerédi
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Confusion_colour.svg/20px-Confusion_colour.svg.png)
Ne doit pas être confondu avec la conjecture d'Erdős-Turán démontrée par Szemerédi ou d'autres théorèmes portant le nom d'Erdős.
En combinatoire arithmétique, le théorème d'Erdős-Szemerédi[1] assure qu'il existe des constantes strictement positives c et ε telles que pour tout ensemble fini A de réels,
où | | désigne le cardinal, la somme d'ensembles de A avec lui-même et
Il peut arriver que A soit de taille comparable à A + A (si A est en progression arithmétique) ou à A ∙ A (si A est en progression géométrique). Le théorème de Erdős-Szemerédi peut donc s'interpréter informellement en disant qu'un « gros » ensemble ne peut « se comporter » simultanément comme une progression arithmétique et une progression géométrique ; on peut aussi dire que la droite réelle ne contient pas d'ensemble qui « ressemble à » un sous-anneau fini. C'est le premier exemple de ce qu'on appelle maintenant le « phénomène somme-produit », dont on sait qu'il a lieu pour beaucoup d'anneaux et de corps, y compris des corps finis[2].
Erdős et Szemerédi ont conjecturé qu'ε peut être choisi arbitrairement proche de 1. En 2009, le meilleur résultat dans cette direction est celui de Solymosi[3] : ε peut être choisi arbitrairement proche de 1/3.
Notes et références
- ↑ (en) P. Erdős et E. Szemerédi, « On sums and products of integers », dans P. Erdős, L. Alpár, G. Halász et A. Sárközy, Studies in Pure Mathematics : To the Memory of Paul Turán, Birkhäuser, (lire en ligne), p. 213-218
- ↑ (en) Terence Tao, « The sum-product phenomenon in arbitrary rings », Discrete Math., vol. 4, no 2, , p. 59-82, arXiv:0806.2497
- ↑ (en) Jozsef Solymosi, « Bounding multiplicative energy by the sumset », Advan. Math., vol. 222, no 2, , p. 402-408, preprint arXiv:0806.1040
Portail des mathématiques