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]

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.

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

• Tao, Terence (2007). «The ergodic and combinatorial approaches to Szemerédi's theorem». En Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József, eds. Additive Combinatorics. CRM Proceedings & Lecture Notes 43. Providence, RI: American Mathematical Society. pp. 145-193. Bibcode:2006math......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005. arXiv:math/0604456.

• PlanetMath source for initial version of this page Archivado el 16 de julio de 2012 en Wayback Machine.
• 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
• Weisstein, Eric W. «SzemeredisTheorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
• Grime, James; Hodge, David (2012). «6,000,000: Endre Szemerédi wins the Abel Prize». Numberphile. Brady Haran. Archivado desde el original el 9 de enero de 2014. Consultado el 8 de octubre de 2022.