Teorema de Szemeredi

El teorema de Szemeredi (anteriormente conocido como la conjetura de Erdős-Turan [1] ) es una declaración en la teoría de números combinatoria sobre la existencia de progresiones aritméticas largas en conjuntos densos.

Es un ejemplo clásico de un teorema en combinatoria aditiva . Algunos métodos de su demostración se utilizaron en la demostración del teorema de Green-Tao [2] .

Redacción

La formulación original del teorema contenía solo una condición sobre la densidad del conjunto como un todo.

En cualquier conjunto infinito de densidad asintótica positiva , existe una progresión de cualquier longitud . [3] $A\subconjunto {\mathbb {N} }$ ${\ estilo de visualización D (A)> 0}$ $k$

Existe una versión final equivalente a la anterior [4] .

Para cualquiera y suficientemente grande, cualquier conjunto de tamaño contiene una progresión aritmética de longitud . $\delta>0$ $N > N(k, \delta)$ $A\subconjunto \{1,\puntos,N\}$ ${\ estilo de visualización | A | \ geqslant \ delta N}$ $k$

La última variante es importante en relación con la posibilidad de formular resultados cuantitativos sobre la relación entre y . Muestra que en la primera variante (infinita), el límite más allá del cual la presencia de progresiones se vuelve inevitable no es el valor de densidad en sí mismo, sino alguna ley de distribución. La descripción exacta de este borde se desconoce a partir de 2019. $\delta$ $norte$

La versión final del teorema sigue siendo equivalente si consideramos y, en consecuencia, progresiones en el anillo de residuos módulo . Este enfoque abre el camino a una demostración usando sumas trigonométricas . $A\subconjunto \mathbb {Z} _{N}$ $norte$

Porque o la afirmación del teorema es trivial. Un caso especial se llama teorema de Roth . Su demostración es mucho más simple que para el caso general y, a menudo, se presenta por separado en la literatura. Además, se conocen estimaciones mucho mejores de los valores críticos para el teorema de Roth en comparación con las generales , incluso para generalizaciones a varios grupos . $k=1$ $k=2$ $k = 3$ $\delta$

Historia

La afirmación del teorema fue formulada por primera vez como una conjetura por Erdős y Turan [5] en 1936.

El caso fue probado en 1953 por Klaus Roth [6] adaptando el método circular de Hardy-Littlewood . $k = 3$

El caso fue probado en 1969 por Endre Semeredi [7] usando un método combinatorio similar al que se usó para probar el caso . Roth [8] dio una segunda prueba del mismo caso en 1972. $k = 4$ $k = 3$

El caso general para any también fue probado en 1975 por Szemeredi [9] , usando argumentos combinatorios ingeniosos y complejos. La base de su prueba es el llamado lema de regularidad , que describe la estructura de grafos arbitrarios en términos de pseudoaleatoriedad. $k$

Posteriormente se encontraron otras demostraciones del teorema, entre ellas las más importantes son la demostración de Furstenberg ( en alemán: Hillel Fürstenberg ) [10] en 1977, utilizando la teoría ergódica , y la demostración de Gowers [11] en 2001, utilizando análisis armónico. y combinatoria .

Calificaciones

Hablando de estimaciones cuantitativas para el teorema de Szemeredi, uno generalmente se refiere al tamaño del subconjunto más grande del intervalo [12] que no contiene progresiones de una longitud dada: ${\ estilo de visualización \ {1, \ puntos, N \}}$

a_{k}(N)=\max {\big \{}|A|:A\subset \{1,\dots,N\},\ \nexists a,d:\{a,a+ d ,\puntos,a+(k-1)d\}\subconjunto A{\grande \}}.

Así, para derivar las cotas superiores de , se necesitan pruebas generales, y para probar las cotas inferiores (es decir, para refutar las cotas superiores correspondientes), basta con presentar la construcción de un contraejemplo. $a_{k}(N)$

Límites superiores

La primera prueba general del teorema de Szémerédy, debido al uso del lema de regularidad, dio estimaciones muy pobres de la dependencia expresada en términos de torres de exponenciales . ${\ estilo de visualización \ delta = \ delta (N)}$

Gowers obtuvo estimaciones cuantitativas similares a las estimaciones correspondientes para el teorema de Roth en 2001 [11] :

$a_{k}(N)\ll {\frac {N}{(\log N)^{c_{k))))$ , dónde $c_{k}=2^{-2^{k+9)).$

Para un caso, hay estimaciones mucho mejores de , obtenidas por métodos específicos del caso. [13] $k = 3$

Límites inferiores

En el caso de la construcción de conjuntos más grande (a partir de 2019) sin progresiones es la construcción de Behrend . Da conjuntos de tamaño . $k = 3$ $\exp {\Big (}{-}O{\big (}(\log N)^{1/2}{\big )}{\Big )}N$

Rankin generalizó esta construcción a otras arbitrarias en 1961 , construyendo un conjunto de tamaño sin progresiones de longitud . [catorce] $k$ $\exp \left({-}O\left((\log N)^{\frac {1}{k-1}}\right)\right)N$ $k$

Breve descripción del diseño.

La construcción de Behrend asocia un número con un punto en un espacio multidimensional, cuyas coordenadas corresponden a los dígitos del número en algún sistema numérico. El conjunto se compone de puntos que corresponden en este sentido a los puntos de alguna esfera. La estricta convexidad de la esfera garantiza la ausencia de tres puntos en una línea recta y, por tanto, la ausencia de progresiones de tres términos.

La idea de Rankin es iterar este truco. Por ejemplo, se toman puntos for (y sus imágenes en el sistema numérico) no de una esfera, sino de todas las esferas, cuyos cuadrados de radios pertenecen al conjunto formado según el tipo del conjunto de Behrend (construcción de ). Porque - de esferas cuyos cuadrados de radios pertenecen al conjunto de puntos de la oración anterior, etc. $k = 4$ $k = 3$ $k = 5$

Al mismo tiempo, la base del sistema numérico y las restricciones sobre el valor de los dígitos en cada iteración se seleccionan de manera especial para que sea posible probar el lema sobre el número de soluciones de la ecuación en tales condiciones, por lo tanto , de hecho, los conjuntos de puntos que surgen en las etapas intermedias de construcción no son de tamaño óptimo para valores más pequeños de . $x_{1}^{2}+\puntos +x_{k}^{2}=N$ $k$

Relación con otros teoremas

El teorema de Szemeredy es una generalización directa del teorema de van der Waerden , ya que al dividir los números naturales en un número finito de clases, al menos una de ellas tendrá densidad positiva.

A partir de límites superiores razonablemente buenos en los valores de densidad crítica en el teorema de Szémeredy , puede seguirse la conjetura de Erdős sobre progresiones aritméticas . [quince]

Véase también

Literatura

Rue, Juanjo. El arte de contar. Combinatoria y enumeración. - M. : De Agostini, 2014. - S. 123-132. — 144 pág. — (El Mundo de las Matemáticas: en 45 tomos, tomo 34). - ISBN 978-5-9774-0729-8 .
Tao, Terencio Los enfoques ergódico y combinatorio del teorema de Szemerédi // Combinatoria aditiva (neopr.) / Granville, Andrew; Nathanson, Melvyn B.; Solimosi, Jozsef. - Sociedad Matemática Americana , 2007. - V. 43. - S. 145-193. — (Actas de CRM y notas de conferencias). - ISBN 978-0-8218-4351-2 .
I. D. Shkredov. Teorema de Szemeredi y problemas sobre progresiones aritméticas // Avances en Ciencias Matemáticas . - Academia Rusa de Ciencias , 2006. - Edición. 6 _ - S. 111-179 . (Ruso)

Notas

↑ También hay otra hipótesis que lleva el nombre de estos científicos: la conjetura de Erdős-Turan sobre bases aditivas .
↑ Shkrédov, 2006 , pág. 159-165.
↑ La existencia de progresiones aritméticas infinitas no se sigue del teorema, y tal afirmación sería de hecho falsa. Por ejemplo, un contraejemplo es el conjunto de números que contienen uno en el primer dígito de la notación decimal. $A$
↑ Shkrédov, 2006 , pág. 113.
↑ Erdős, Paul & Turán, Paul (1936), Sobre algunas secuencias de enteros , Journal of the London Mathematical Society vol 11 (4): 261–264, doi : 10.1112/jlms/s1-11.4.261 , < http: //www.renyi.hu/~p_erdos/1936-05.pdf > Archivado el 23 de julio de 2020 en Wayback Machine .
↑ Roth, Klaus Friedrich (1953), Sobre ciertos conjuntos de enteros, I , Journal of the London Mathematical Society, volumen 28: 104–109, Zbl 0050.04002, MR : 0051853 , DOI 10.1112/jlms/s1-28.1.104 .
↑ Szemerédi, Endre (1969), Sobre conjuntos de números enteros que no contienen cuatro elementos en progresión aritmética , Acta Math. Academia ciencia colgado. T. 20: 89–104, Zbl 0175.04301, MR : 0245555 , DOI 10.1007/BF01894569
↑ Roth, Klaus Friedrich (1972), Irregularidades de secuencias relativas a progresiones aritméticas, IV , Periodica Math. hungaro T. 2: 301–326, MR : 0369311 , DOI 10.1007/BF02018670 .
↑ Szemerédi, Endre (1975), Sobre conjuntos de enteros que no contienen elementos k en progresión aritmética , Acta Arithmetica T. 27: 199–245, Zbl 0303.10056, MR : 0369312 , < http://matwbn.icm.edu.pl/ ksiazki/aa/aa27/aa27132.pdf > Archivado el 10 de diciembre de 2020 en Wayback Machine .
↑ Furstenberg, Hillel (1977), Comportamiento ergódico de medidas diagonales y un teorema de Szemerédi sobre progresiones aritméticas , J. D'Analyse Math. T. 31: 204–256, MR : 0498471 , DOI 10.1007/BF02813304 .
↑ 1 2 Gowers, Timothy (2001), Una nueva prueba del teorema de Szemerédi , Geom. Función Anal. T. 11(3): 465–588, MR : 1844079 , doi : 10.1007/s00039-001-0332-9 , < http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi > Archivado copia fechada el 26 de septiembre de 2020 en Wayback Machine .
↑ O un grupo cíclico , que es lo mismo salvo una constante. ${\ estilo de visualización \ mathbb {Z} _ {N}}$
↑ Una mejora cuantitativa del teorema de Roth sobre progresiones aritméticas, Journal of the London Mathematical Society, volumen 93 (3): 643-663, 2016 .
↑ Rankin, Robert A. (1962), Conjuntos de números enteros que no contienen más de un número determinado de términos en progresión aritmética, Proc. Roy. soc. Secta de Edimburgo. AT. 65: 332–344 , Zbl 0104.03705, MR : 0142526 .
↑ Shkrédov, 2006 , pág. 139-140.

Enlaces

Anuncio de Ben Green y Terence Tao : la versión preliminar está disponible en math.NT/0404188
Discusión del teorema de Szemeridi (parte 1 de 5)
Ben Green y Terence Tao: el teorema de Szemeredi en Scholarpedia
Weisstein, Eric W. SzemeredisTheorem (inglés) en el sitio web de Wolfram MathWorld .

diccionarios y enciclopedias	Britannica (en línea)