Teorema de Szemerédi

Se dice que un subconjunto A de números naturales tiene densidad superior positiva si

${\displaystyle \limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0}$.

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 ${\displaystyle \delta \in (0,1]}$, existe un número entero positivo

${\displaystyle N=N(k,\delta )}$

tal que cada subconjunto de {1, 2, ..., N} de tamaño al menos δN contiene una progresión aritmética de longitud k.

Otra formulación usa la función r_k(N), el tamaño del subconjunto más grande de {1, 2, ..., N} sin una progresión aritmética de longitud k. El teorema de Szemerédi es equivalente al límite asintótico

${\displaystyle r_{k}(N)=o(N)}$.

Es decir, r_k(N) crece menos que linealmente con N.

El teorema de Van der Waerden, un precursor del teorema de Szemerédi, fue probado en 1927.

Los casos k = 1 y k = 2 del teorema de Szemerédi son triviales. El caso k= 3, conocido como teorema de Roth, fue establecido en 1953 por Klaus Roth^[2] a través de una adaptación de método del círculo de Hardy-Littlewood. Endre Szemerédi^[3] demostró el caso k= 4 mediante combinatoria. 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]). Ahora se conocen varias otras demostraciones, siendo las más importantes las de Hillel Furstenberg^[7][8] en 1977, usando teoría ergódica, y las de William Timothy Gowers^[9] en 2001, usando tanto análisis de Fourier como combinatoria. Terence Tao ha llamado a las diversas demostraciones del teorema de Szemerédi la piedra de Rosetta necesaria para conectar campos dispares de las matemáticas.^[10]

Summarize Timeline Fact Check

Es un problema abierto el determinar la tasa de crecimiento exacta de r_k(N). Los límites generales más conocidos son

${\displaystyle CN\exp \left(-n2^{(n-1)/2}{\sqrt[{n}]{\log N}}+{\frac {1}{2n}}\log \log N\right)\leq r_{k}(N)\leq {\frac {N}{(\log \log N)^{2^{-2^{k+9}}}}},}$

donde ${\displaystyle n=\lceil \log k\rceil }$. El límite inferior se debe a que O'Bryant^[11] se basó en el trabajo de Behrend,^[12] Rankin,^[13] y Elkin.^[14][15] El límite superior se debe a Gowers.^[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

${\displaystyle N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq C{\frac {(\log \log N)^{4}}{\log N}}N}$

debido a O'Bryant^[11] y Bloom^[21] respectivamente.

Para k= 4, Green y Tao^[22][23] demostraron que

${\displaystyle r_{4}(N)\leq C{\frac {N}{(\log N)^{c}}}}$

para algún c > 0.

Summarize Timeline Fact Check

Hillel Furstenberg y Yitzhak Katznelson demostraron por primera vez una generalización multidimensional del teorema de Szemerédi utilizando la teoría ergódica.^[24] William Timothy Gowers,^[25] Vojtěch Rödl y Jozef Skokan^[26][27] con Brendan Nagle, Rödl y Mathias Schacht,^[28] y Terence Tao^[29] proporcionaron pruebas combinatorias.

Alexander Leibman y Vitaly Bergelson^[30] generalizaron Szemerédi a progresiones polinómicas: si ${\displaystyle A\subset \mathbb {N} }$ es un conjunto con densidad superior positiva y ${\displaystyle p_{1}(n),p_{2}(n),\dotsc ,p_{k}(n)}$ son polinomios de valores enteros tales que ${\displaystyle p_{i}(0)=0}$, entonces hay infinitos ${\displaystyle u,n\in \mathbb {Z} }$ tales que ${\displaystyle u+p_{i}(n)\in A}$ para todos los ${\displaystyle 1\leq i\leq k}$. El resultado de Leibman y Bergelson también es válido en un entorno multidimensional.

La versión finita del teorema de Szemerédi se puede generalizar a grupos aditivos finitos que incluyen espacios vectoriales sobre cuerpos finitos.^[31] El análogo de campo finito se puede usar como modelo para comprender el teorema en los números naturales.^[32] El problema de obtener cotas en el caso k=3 del teorema de Szemerédi en el espacio vectorial ${\displaystyle \mathbb {F} _{3}^{n}}$ se conoce como problema conjunto tapa.

El teorema de Green-Tao afirma que los números primos contienen progresiones aritméticas arbitrariamente largas. No está implícito en el teorema de Szemerédi porque los números primos tienen densidad 0 en los números naturales. Como parte de su prueba, Ben Green y Tao introdujeron un teorema de Szemerédi "relativo" que se aplica a subconjuntos de números enteros (incluso aquellos con densidad 0) que satisfacen ciertas condiciones de pseudoaleatoriedad. Desde entonces, David Conlon, Jacob Fox y Yufei Zhao han dado un teorema de Szemerédi relativo más general.^[33][34]

La conjetura sobre progresiones aritméticas de Erdős implicaría tanto el teorema de Szemerédi como el teorema de Green-Tao.

• Problemas que involucran progresiones aritméticas
• Teoría ergódica de Ramsey
• Combinatoria aritmética
• Lema de regularidad de Szemerédi