Teorema de Szemerédi

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 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.

Declaración

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

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A\cap \{1,2,3,\dots ,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 $\delta \in (0,1]$, existe un número entero positivo

$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

$r_k(N)=o(N)$.

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

Historia

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 a través de una adaptación de método del círculo de Hardy-Littlewood. Endre Szemerédi demostró el caso k= 4 mediante combinatoria. Usando un enfoque similar al que usó para el caso k= 3, Roth dio una segunda prueba de este teorema en 1972.

El caso general se resolvió en 1975, también por Szemerédi, 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). Ahora se conocen varias otras demostraciones, siendo las más importantes las de Hillel Furstenberg en 1977, usando teoría ergódica, y las de William Timothy Gowers 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.

Límites cuantitativos

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

$CN\exp (-n{2}^{(n-1)/2}\sqrt[n]{\log N}+\frac{1}{2n}\log \log N)\le r_k(N)\le \frac{N}{(\log \log N{)}^{2^{-2^{k+9}}}},$

donde $n=\lceil \log k\rceil$. El límite inferior se debe a que O'Bryant se basó en el trabajo de Behrend, Rankin, y Elkin. El límite superior se debe a Gowers.

Para k pequeño, existen límites más estrechos que en el caso general. Cuando k= 3, Bourgain, Heath-Brown, Szemerédi, y Sanders proporcionaron límites superiores cada vez más pequeños. Los mejores límites actuales son

$N{2}^{-\sqrt{8\log N}}\le r_3(N)\le C\frac{(\log \log N{)}^4}{\log N}N$

debido a O'Bryant y Bloom respectivamente.

Para k= 4, Green y Tao demostraron que

$r_4(N)\le C\frac{N}{(\log N{)}^c}$

para algún c > 0.

Extensiones y generalizaciones

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

Alexander Leibman y Vitaly Bergelson generalizaron Szemerédi a progresiones polinómicas: si $A\subset \mathbb{N}$ es un conjunto con densidad superior positiva y $p_1(n),p_2(n),\dots ,p_k(n)$ son polinomios de valores enteros tales que $p_i(0)=0$, entonces hay infinitos $u,n\in \mathbb{Z}$ tales que $u+p_i(n)\in A$ para todos los $1\le i\le 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. El análogo de campo finito se puede usar como modelo para comprender el teorema en los números naturales. El problema de obtener cotas en el caso k=3 del teorema de Szemerédi en el espacio vectorial ${𝔽}_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.

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

Véase también

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

Bibliografía

• Plantilla:Cite encyclopedia

Enlaces externos

• PlanetMath source for initial version of this page Plantilla:Wayback
• Announcement by Ben Green and Terence Tao – the preprint is available at math.NT/0404188
• Discussion of Szemerédi's theorem (part 1 of 5)
• Ben Green and Terence Tao: Szemerédi's theorem on Scholarpedia
• Plantilla:MathWorld
• Plantilla:Cite web