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

$\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 $\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 \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 $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

$N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq 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)\leq 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),\dotsc ,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\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.​ 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 $\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.​​

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

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

Enlaces externos

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

• Datos: Q1046232