Teorema de Szemerédi

En combinatoria aritmética, el teorema de Szemerédi es un resultado relativo a progresiones aritméticas en subconjuntos de números enteros. En 1936, Erdős y Turán conjeturaron que cada conjunto de números enteros A con densidad natural positiva contiene una progresión aritmética de términos k para cada k. Endre Szemerédi demostró la conjetura en 1975.

Declaración

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

${displaystyle limsup _{nto infty }{frac Oh, Dios mío.$

El teorema de Szemerédi afirma que un subconjunto de 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 finitaria equivalente a menudo utilizada del teorema indica que por cada entero positivo k y número real ${displaystyle delta in (0,1]}$, existe un entero positivo

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

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

Otra formulación utiliza 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 demostrado 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 mediante una adaptación del método del círculo de Hardy-Littlewood. Endre Szemerédi demostró el caso k = 4 mediante combinatoria. Utilizando un enfoque similar al que utilizó para el caso k = 3, Roth dio una segunda prueba de esto en 1972.

El caso general fue resuelto en 1975, también por Szemerédi, quien desarrolló una extensión ingeniosa y complicada de su argumento combinatorio anterior para k = 4 (llamado "una obra maestra del razonamiento combinatorio&# 34; por Erdős). Ahora se conocen varias otras pruebas, las más importantes son las de Hillel Furstenberg en 1977, utilizando la teoría ergódica, y las de Timothy Gowers en 2001, utilizando tanto el análisis de Fourier como la combinatoria. Terence Tao ha llamado a las diversas demostraciones del teorema de Szemerédi una "piedra de Rosetta" para conectar campos dispares de las matemáticas.

Límites cuantitativos

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

${displaystyle CNexp left(-n2^{(n-1)/2}{sqrt[{n}{log N}+{frac {1}{2n}log log Nright)leq r_{k}(N)leq {frac {N}{logloglogloglogloglog} No.$

Donde ${displaystyle n=lceil log krceil }$. El límite inferior se debe al edificio O'Bryant 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 estrictos que en el caso general. Cuando k = 3, Bourgain, Heath-Brown, Szemerédi, Sanders y Bloom establecieron límites superiores progresivamente más pequeños, y Bloom y Sisask demostraron entonces el primer límite que rompió la llamada "barrera logarítmica". 34;. Los mejores límites actuales son

${displaystyle N2^{-{sqrt {8log N}leq r_{3}(N)leq Ne^{-c(log N)^{1/11}}$, para alguna constante ${displaystyle c]0}$,

debido a O'Bryant, Kelley y Meka respectivamente.

Para k = 4, Green y Tao demostraron que

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

para algunos c > 0.

Extensiones y generalizaciones

Hillel Furstenberg e Yitzhak Katznelson demostraron por primera vez una generalización multidimensional del teorema de Szemerédi utilizando la teoría ergódica. 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 las progresiones polinómicas de Szemerédi: Si ${displaystyle Asubset mathbb {N}$ es un conjunto con densidad superior positiva y ${displaystyle p_{1}(n),p_{2}(n),dotscp_{k}(n)}$ son polinomios de valor entero tales que ${displaystyle p_{i}(0)=0}$, entonces hay infinitamente muchos ${displaystyle u,nin mathbb {Z}$ tales que ${displaystyle u+p_{i}(n)in A}$ para todos ${displaystyle 1leq ileq k}$. El resultado de Leibman y Bergelson también tiene un entorno multidimensional.

La versión finitaria del teorema de Szemerédi se puede generalizar a grupos aditivos finitos, incluyendo espacios vectoriales sobre campos finitos. El análogo de campo finito se puede utilizar como un modelo para entender el teorema en los números naturales. El problema de obtener límites en el caso k=3 del teorema de Szemerédi en el espacio vectorial ${displaystyle mathbb {F} _{3} {n}$ es conocido como el problema del juego de tapas.

El teorema de Green-Tao afirma que los números primos contienen progresiones aritméticas largas y arbitrarias. El teorema de Szemerédi no implica esto porque los números primos tienen densidad 0 en los números naturales. Como parte de su prueba, Ben Green y Tao presentaron un "pariente" Teorema de Szemerédi 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 propuesto un teorema relativo de Szemerédi más general.

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