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

Declaración

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.

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^[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]​

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

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

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

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

Referencias

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.