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

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,

${\displaystyle \max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }}$

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.

où | | désigne le cardinal, ${\displaystyle A+A=\{a+b~|~a,b\in A\}}$ la somme d'ensembles de A avec lui-même et ${\displaystyle A\cdot A=\{a\cdot b~|~a,b\in A\}.}$

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.