Théorème d'Erdős-Szemerédi
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.
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