Théorème d'Erdős-Szemerédi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
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.

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[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Szemerédi theorem » (voir la liste des auteurs).

  1. (en) P. Erdős et E. Szemerédi, « On sums and products of integers », dans P. Erdős, L. Alpár, G. Halász (hu) et A. Sárközy, Studies in Pure Mathematics : To the Memory of Paul Turán, Birkhäuser, (lire en ligne), p. 213-218
  2. (en) Terence Tao, « The sum-product phenomenon in arbitrary rings », Discrete Math., vol. 4, no 2,‎ , p. 59-82, arXiv:0806.2497
  3. (en) Jozsef Solymosi, « Bounding multiplicative energy by the sumset », Advan. Math., vol. 222, no 2,‎ , p. 402-408, preprint arXiv:0806.1040