En combinatoria aritmética, el teorema de Szemerédi (denominado así en referencia al matemático húngaro Endre Szemerédi) es un resultado relativo a progresiones aritméticas en subconjuntos de los números enteros.
En 1936, Erdős y Turán conjeturaron[1] que cada conjunto de enteros A con densidad natural positiva contiene k términos en progresión aritmética para cada k. Endre Szemerédi demostró la conjetura en 1975.
Se dice que un subconjunto A de números naturales tiene densidad superior positiva si El teorema de Szemerédi afirma que un subconjunto de los números naturales con densidad superior positiva contiene infinitas progresiones aritméticas de longitud k para todos los números enteros positivos k. Una versión finita equivalente de uso frecuente del teorema establece que para cada número entero positivo k y número real
Usando un enfoque similar al que usó para el caso k= 3, Roth[4] dio una segunda prueba de este teorema en 1972.
El caso general se resolvió en 1975, también por Szemerédi,[5] quien desarrolló una extensión ingeniosa y complicada de su anterior argumento combinatorio para k= 4 (llamado "una obra maestra del razonamiento combinatorio" por Erdős[6]).
[9] Para k pequeño, existen límites más estrechos que en el caso general.
Cuando k= 3, Bourgain,[16][17] Heath-Brown,[18] Szemerédi,[19] y Sanders[20] proporcionaron límites superiores cada vez más pequeños.
Los mejores límites actuales son debido a O'Bryant[11] y Bloom[21] respectivamente.
Hillel Furstenberg y Yitzhak Katznelson demostraron por primera vez una generalización multidimensional del teorema de Szemerédi utilizando la teoría ergódica.
Alexander Leibman y Vitaly Bergelson[30] generalizaron Szemerédi a progresiones polinómicas: si
El resultado de Leibman y Bergelson también es válido en un entorno multidimensional.
[31] El análogo de campo finito se puede usar como modelo para comprender el teorema en los números naturales.
El teorema de Green-Tao afirma que los números primos contienen progresiones aritméticas arbitrariamente largas.
Desde entonces, David Conlon, Jacob Fox y Yufei Zhao han dado un teorema de Szemerédi relativo más general.