Teorema de roth

El teorema de Roth es resultado de la combinatoria aditiva , un caso especial del teorema de Szemeredi para progresiones de longitud 3; afirma la presencia de progresiones aritméticas en cualquier conjunto suficientemente denso. ${\ estilo de visualización (a, a + d, a + 2d), \ d \ no = 0}$

La formulación exacta es: para cualquier , cualquier conjunto que tenga una densidad asintótica contiene una progresión aritmética de longitud 3. ${\ estilo de visualización \ delta \ en (0; 1)}$ $A\subconjunto {\mathbb {N} }$ ${\ estilo de visualización d (A)> \ delta}$

Formulaciones similares que utilizan las densidades asintóticas superior e inferior son equivalentes a [1] .

La formulación para conjuntos finitos también es equivalente a la original: para cualquier existe tal que si , y , entonces contiene una progresión aritmética de longitud 3. La gran mayoría de las demostraciones prueban la formulación para conjuntos finitos. ${\ estilo de visualización \ delta \ en (0; 1)}$ ${\ estilo de visualización N_ {0} = N_ {0} (\ delta)}$ $N>N_{0}$ $A\subconjunto \left\lbrace {1,2,\dots,N}\right\rbrace$ ${\ estilo de visualización | A |> \ delta N}$ $A$

Historial de puntajes mejorados

Tamaño máximo de subconjunto ${\ estilo de visualización \ {1, \ puntos, N \}}$ sin progresiones de longitud 3
año de publicación	Tamaño (hasta una constante)	Los autores)
1953	${\frac {N}{\log \log N))$	Boca [2]
1987	${\frac {N}{(\log N)^{c}}},\ c>0$	Heath-Brown [3] [4]
1999	${\displaystyle {\frac {N(\log \log N)^{1/2}}{(\log N)^{1/2))))$	borgoña [5]
2008	${\displaystyle {\frac {N(\log \log N)^{2}}{(\log N)^{2/3))))$	borgoña [6]
2012	${\displaystyle {\frac {N}{(\log N)^{3/4-o(1)))))$	Lijadoras [7]
2011	${\frac {(\log \log N)^{5}}{\log N}}N$	Lijadoras [8]
2014	${\frac {(\log \log N)^{4}}{\log N}}N$	Floración [9]
2020 (preimpresión)	${\frac {(\log \log N)^{3}(\log \log \log N)^{5}}{\log N}}N$	Zapato [10]
2020 (preimpresión)	${\frac {N}{(\log N)^{1+c}}},\ c>0$	Floración, Sisask [11]

Pruebas varias

Análisis armónico

El teorema fue probado por primera vez en 1953 por Klaus Roth [2] [12] adaptando el método del círculo de Hardy-Littlewood. La prueba usó la idea [13] , que posteriormente se generalizó para la prueba general del teorema de Szémeredi: todos los conjuntos de una densidad dada se dividen en dos grupos: "uniforme" y "no uniforme", y "uniformidad" significa un superior limitado por los coeficientes de Fourier . Si el conjunto es uniforme, entonces se puede probar directamente la presencia de progresiones en él, en caso contrario se puede probar la existencia de una subprogresión en la que la densidad del conjunto es mayor que entre el segmento de la serie natural al que pertenece .

El método le permite obtener una estimación . Los detalles técnicos de la prueba, el límite de los coeficientes de Fourier que definen la "uniformidad" y las constantes resultantes pueden diferir de una fuente a otra. ${\displaystyle N_{0}(\delta )\leqslant e^{e^{\frac {c}{\delta ))))$

Combinatoria (a través del lema de Szemeredi)

La demostración del teorema de Roth se puede deducir [14] como un caso especial del teorema de Szemeredy a partir de la demostración de Szemeredy. Esta forma de demostración requiere el uso del lema de regularidad de Szémerédy y el teorema de la esquina , del cual se sigue directamente el teorema de Roth. Incluso es posible [15] prescindir del uso del teorema de la esquina y derivar el teorema de Roth directamente del lema de eliminación de triángulos , pero solo en la formulación para grupos cíclicos finitos (ver la sección "Generalizaciones a varios grupos").

Dado que el lema de regularidad de Szemeredi da cotas superiores extremadamente grandes para el valor obtenido a través de él (al menos, torres de exponentes ), el método en sí mismo no permite obtener cotas mejores que estas.

Elemental (mediante progresiones aritméticas generalizadas)

Ronald Graham , en su libro sobre la teoría de Ramsey, da una versión simplificada de la prueba, también basada en el método de Szemeredi, pero sin utilizar el lema de regularidad. La demostración utiliza progresiones aritméticas generalizadas de la forma , que es mucho más fácil de probar la presencia de en el conjunto, y de esto ya se deduce el propio teorema de Roth. $a+\sum \limits _{k=1}^{n}{\epsilon _{k}x_{k}}\ (\epsilon _{i}\in \left\lbrace {0,1}\ derecho\rbrace)$

La prueba de Graham no da estimaciones para , sino que solo muestra la existencia, ya que usa la existencia de un punto en la secuencia, a partir del cual todos los puntos están lo suficientemente cerca del límite , pero solo se prueba también la existencia para el límite, y el carácter de la convergencia no se analiza en principio. $norte$

Contraejemplos para conjuntos no densos

Además de encontrar límites superiores para el tamaño de un conjunto sin progresiones aritméticas, también existe un problema inverso: construir el conjunto más grande posible que no contenga progresiones aritméticas, es decir, un contraejemplo para indicar los límites en la mejora de las estimaciones en . Todas las construcciones conocidas de tales conjuntos se basan en la idea de considerar dígitos individuales de números en un determinado sistema numérico y establecer condiciones sobre los valores de estos dígitos. $A\subconjunto \left\lbrace {1,\dots,N}\right\rbrace$ $A$ ${\ estilo de visualización N_ {0} (\ delta)}$

Erdős, Turan (1936)

El primer ejemplo de un conjunto sin progresiones lo dieron en 1936 Erdős y Turan, quienes propusieron considerar números que en el sistema ternario contienen solo los dígitos 0 y 2. Tal conjunto contiene solo números, que es muy pequeño en comparación con el superior. límites. [dieciséis] $N^{\log _{3}{2))$

Prueba de la corrección de la construcción.

Deje --- el conjunto Erdős--Turan. $A$

Si y , entonces en el sistema ternario en el dígito más significativo , donde estos números son diferentes, se cumplen las igualdades . Por tanto, en una progresión aritmética , se cumpliría , y por tanto, . ${\ estilo de visualización a, b \ en A}$ $a<b$ $i$ ${\ estilo de visualización a_ {i} = 0, \ b_ {i} = 2}$ ${\ estilo de visualización a<c<b}$ $c_{i}=1$ ${\ estilo de visualización c \ no \ en A}$

Salem, Spencer (1942)

Salem y Spencer en 1942 generalizaron la idea de Erdős y Turan a sistemas de numeración con base creciente (dependiendo del tamaño del conjunto) y obtuvieron un conjunto sin progresiones de tamaño . [17] $\exp \left({-O\left({\frac {\log N}{\log \log N))\right)}\right)N$

Breve descripción del diseño.

En la construcción de Erdős-Turan, es bastante posible permitir los números 0 y 1 en lugar de 0 y 2 (entonces el lugar del número medio en la progresión ocupará un lugar más importante en la prueba de corrección). Por analogía con esto, Salem y Spencer en el sistema -ario consideraron números que contienen solo dígitos de 0 a , y un número igual de ocurrencias de cada dígito (con asintótica , puede considerarse impar, y el número total de dígitos --- dividiendo ). $d$ ${\frac{d-1}{2))$ $d$ ${\frac{d-1}{2))$

La presencia de progresiones está bloqueada por la condición de aparición de dígitos individuales. De hecho, si el acarreo no se usa durante la suma , entonces todos los ceros en (y por lo tanto en ) solo se pueden formar agregando ceros de los dígitos correspondientes y . Además, por inducción, podemos probar la coincidencia de las posiciones de todos unos, dos, etc. y llegar a la conclusión de que . ${\ estilo de visualización a + c = 2b}$ ${\ estilo de visualización 2b}$ $b$ $a$ $C$ $a B C$ ${\ estilo de visualización a = b = c}$

La puntuación indicada se obtiene considerando . ${\displaystyle d\asymp {\frac {\log N}{(\log \log N)^{2))))$

Berend (1946)

En 1946, Behrend añadió una interpretación geométrica al asociar los dígitos de los números con las coordenadas de puntos en un espacio multidimensional y considerando los números correspondientes en este sentido a los puntos de una esfera . Esto hizo posible construir un conjunto de tamaño libre de progresión . [Dieciocho] $\exp \left({-O\left({\sqrt {\log N}}\right)}\right)N$

Breve descripción del diseño.

Todos los números con dígitos no mayores que la representación -aria se dividen en grupos con los mismos valores . El mayor de estos grupos se elige como un conjunto y su tamaño se estima según el principio de Dirichlet . ${\ estilo de visualización x<(2m+1)^{n))$ $metro$ ${\ estilo de visualización (2m+1)}$ ${\displaystyle x=x_{1}x_{2}\puntos x_{n))$ $\sum \limits _{i=1}^{n}{x_{i}^{2))$

Debido a los dígitos limitados, al sumar dichos números, no hay transferencia de dígitos , por lo que las progresiones de longitud 3 también tienen una interpretación geométrica (como puntos en la misma línea). Pero, dado que la pelota es un cuerpo estrictamente convexo , entonces la esfera, como su límite, no puede contener tres puntos en una línea recta. De esto se deduce que no hay progresiones en el conjunto elegido.

El tamaño del conjunto se estima mejor en $n\asymp {\sqrt {\log N))$

Posteriormente, la estimación de Behrend se incrementó en un factor logarítmico mediante un ligero refinamiento del método [19] , pero no hay resultados significativamente mejores a partir de 2019.

Dado que se conocen cotas superiores de un tipo similar para algunas generalizaciones del teorema de Roth [20] [21] , existen razones para creer que la cota de Behrend es aguda.

Variaciones y generalizaciones para varios grupos

Para grupos cíclicos finitos

Tanto la demostración por análisis armónico como la forma particular en que se aplica el lema de Szemeredi no prueban el teorema en sí, sino su versión "cíclica".

Para cualquier , existe tal que si , y , entonces contiene el triple , donde se entiende que suma significa suma de módulo ${\ estilo de visualización \ delta \ en (0; 1)}$ ${\ estilo de visualización N_ {0} = N_ {0} (\ delta)}$ $N>N_{0}$ $A\subconjunto \mathbb {Z} _{N}$ ${\ estilo de visualización | A |> \ delta N}$ $A$ ${\ estilo de visualización (a, a + d, a + 2d), \ d \ no = 0}$

Las progresiones prometidas por esta formulación pueden ser progresiones en pero no en (por ejemplo, ). Sin embargo, el teorema de Roth obviamente se sigue de él si consideramos el conjunto como un conjunto de residuos en . Esto solo cambia la densidad por una constante, pero hace que todas las progresiones sean adecuadas para . Por tanto, este teorema es equivalente al teorema principal de Roth. ${\mathbb {Z} }_{N}$ ${\mathbb{N} }$ ${\ estilo de visualización (N-2, N-1,0)}$ $\left\lbrace {N+a:a\in A}\right\rbrace$ ${\ estilo de visualización \ mathbb {Z} _ {3N}}$ ${\mathbb{N} }$

Para grupos con pequeña torsión fija

El siguiente teorema, similar en idea al teorema de Roth, no se deriva de él y no lo implica, pero es de interés para un estudio separado.

Que se arreglen algunos . Entonces para cualquiera existe tal que si , entonces ${\ estilo de visualización q \ geq 3}$ ${\ estilo de visualización \ delta \ en (0; 1)}$ ${\ estilo de visualización n_ {0} = n_ {0} (\ delta, q)}$ ${\displaystyle n>n_{0},\ A\subconjunto {\mathbb {F} }_{q}^{n},\ |A|>\delta q^{n))$ $\existe a,d(d\not =(0,\dots ,0)):a,a+d,a+2d\in A$

Límites superiores

El teorema de los grupos fue probado por primera vez por Brown y Bahler en 1982 [22] , pero solo demostraron que para conjuntos sin progresiones aritméticas , pero restricciones más precisas seguían siendo una cuestión abierta. ${\displaystyle {\mathbb {F} }_{p}^{n))$ ${\ estilo de visualización | A | = o (q ^ {n})}$ $|A|$

En 1993 (publicado en 1995) Roy Meshulam probó [23] que . Su prueba consideró grupos arbitrarios y sus caracteres . También existen versiones más simplificadas [24] de esta demostración, exclusivas para , que, utilizando los coeficientes de Fourier en , generalizan directamente ideas a partir de la demostración analítica del teorema de Roth. La prueba es técnicamente incluso más simple que la prueba del teorema de Roth en sí mismo, por lo que [24] [25] se da a menudo como el primer ejemplo de la aplicación del método. $|A|\leq 2{\frac {q^{n}}{n}}$ ${\displaystyle {\mathbb {F} }_{p}^{n))$ ${\displaystyle {\mathbb {F} }_{p}^{n))$

En 2012, Bateman y Katz, considerando el caso , probaron [26] la existencia de una constante absoluta , tal que para sin progresiones aritméticas, . ${\ estilo de visualización q = 3}$ $\epsilon > 0$ $C$ ${\displaystyle A\subconjunto {\mathbb {F} }_{3}^{n))$ $|A|\leq {\frac {3^{n}}{n^{1+\epsilon }}}$

En 2016, Krut, Lev y Pach probaron [27] para el caso de conjuntos sin progresiones. Ellenberg y Gijswijt, generalizando el método de Krut, Löw y Pach, utilizando el álgebra polinomial , probaron [28] [29] la existencia para cada una de una constante simple tal que si no contiene progresiones de longitud 3. En su artículo , . En particular, para el caso . Bajo el supuesto de , se sigue de la optimización de la función que , donde es una constante absoluta, que es la solución de la ecuación , es decir , , donde ${\ estilo de visualización q = 4}$ ${\ estilo de visualización | A | \ leq {3.62} ^ {n}}$ ${\displaystyle A\subconjunto {\mathbb {F} }_{4}^{n))$ ${\ estilo de visualización q \ geq 3}$ ${\ estilo de visualización c = c (q) <q}$ ${\ estilo de visualización | A | = O (c ^ {n})}$ ${\displaystyle A\subconjunto {\mathbb {F} }_{q}^{n))$ $c(q)={\frac {q}{exp({\sup \limits _{\theta }\left\lbrace ({\frac {q-1}{3))\theta +\ln { \frac {e^{q\theta}-1}{q(e^{\theta}-1)}}}\right\rbrace})}}$ ${\ estilo de visualización q = 3}$ ${\ estilo de visualización | A | = o (2.756 ^ {n})}$ $\theta ={\frac {c_{0}}{q}}$ ${\frac {c}{3}}-\ln {\frac {e^{c}-1}{c}}$ $c(q)\sim {\frac {e^{c_{0}}-1}{c_{0}e^{(c_{0}/3)))}q$ $c_{0}$ $2ce^{c}-3e^{c}+c+3=0$ $c(q)\sim c_{1}q$ $c_{1}\aproximadamente 0,841434...$

Límites inferiores

El mejor [28] a partir de 2016 construcción-contraejemplo permite [30] construir conjuntos de tamaño para grupos de la forma que no contienen progresiones aritméticas de longitud 3. ${\displaystyle {\mathbb {F} }_{3}^{n))$ ${\ estilo de visualización \ Omega (2.2^{n})}$

Para grupos arbitrarios

Meshulam considera [23] el teorema de Roth para un grupo arbitrario y deriva una estimación para un conjunto sin progresiones aritméticas de longitud 3. $G={\mathbb {Z} }_{k_{1}}\oplus \dots \oplus {\mathbb {Z} }_{k_{n}}$ $|A|<2{\frac{|G|}{n))$

Esto implica la existencia de una constante absoluta tal que, para un conjunto sin progresiones, $\beta>0$ ${\ estilo de visualización A \ subconjunto G}$ ${\displaystyle |A|<{\frac {|G|}{(\log {|G|})^{\beta ))))$

Generalización bidimensional

La generalización clásica del teorema de Roth para conjuntos bidimensionales es el teorema de la esquina . Aunque no se mencionan las progresiones aritméticas (en el sentido bidimensional), de ahí se sigue el teorema de Roth. $A\subconjunto \left\lbrace {1,\dots, N}\right\rbrace \times \left\lbrace {1,\dots, N}\right\rbrace$

Véase también

Teorema de Van der Waerden

Literatura

KF Roth. Sobre ciertos conjuntos de enteros // Diario de la Sociedad Matemática de Londres. - 1953. - P. 104-109 . -doi : 10.1112 / jlms/s1-28.1.104 .
DR Heath-Brown. Conjuntos enteros que no contienen progresiones aritméticas (inglés) // Revista de la Sociedad Matemática de Londres. - 1987. - vol. s2-35 , edición . 3 . - Pág. 385-394 . -doi : 10.1112 / jlms/s2-35.3.385 .
E. Szemeredi. Conjuntos enteros que no contienen progresiones aritméticas // Acta Mathematica Hungarica. - 1990. - vol. 56 . - pág. 155-159 . -doi : 10.1007/ BF01903717 .
J. Bourgain. Sobre triples en progresión aritmética (inglés) // Análisis geométrico y funcional GAFA. - 1999. - vol. 9 _ - Pág. 968-984 . -doi : 10.1007/ s000390050105 .
J. Bourgain. Revisión del teorema de Roth sobre las progresiones // Journal d'Analyse Mathématique. - 2008. - Vol. 104 . - pág. 155-192 . -doi : 10.1007 / s11854-008-0020-x .
T. Sanders. Sobre ciertos otros conjuntos de números enteros // Journal d'Analyse Mathématique. - 2012. - vol. 116 . - Pág. 53-82 . -doi : 10.1007/ s11854-012-0003-9 . -arXiv : 1007.5444 . _
T. Sanders. Sobre el teorema de Roth sobre las progresiones // Annals of Mathematics. - 2011. - vol. 174 . - Pág. 619-636 . -doi : 10.4007 / annals.2011.174.1.20 . -arXiv : 1011.0104 . _
Floración TF. Una mejora cuantitativa para el teorema de Roth sobre progresiones aritméticas (inglés) // Journal of the London Mathematical Society. - 2014. - Vol. 93 , edición. 3 . - Pág. 643-663 . doi : 10.1112 / jlms/jdw010 . -arXiv : 1405.5800 . _
T. Schoen. Límite mejorado en el teorema de Roth sobre progresiones aritméticas . - 2020. - arXiv : 2005.01145 .
TF Bloom, O. Sisask. Rompiendo la barrera logarítmica en el teorema de Roth sobre progresiones aritméticas . - 2020. - arXiv : 2007.03528 .

Notas

↑ I. D. Shkredov, "Teorema y problemas de Szemeredi sobre progresiones aritméticas", Uspekhi Mat. Nauk, 61:6(372) (2006), 111-178; matemáticas rusas. Encuestas, 61:6 (2006), 1101-1166 . Consultado el 23 de diciembre de 2017. Archivado desde el original el 24 de diciembre de 2017. (indefinido)
↑ 12 Roth , 1953 .
↑ Heath-Brown, 1987 .
↑ Szemerédi, 1990 .
↑ Borgoña, 1999 .
↑ Borgoña, 2008 .
↑ Lijadoras, 2012 .
↑ Lijadoras, 2011 .
↑ Bloom, 2014 .
↑ Schoen, 2020 .
↑ Floración, Sisask, 2020 .
↑ La prueba de Roth presentada por Harold Helfgott en ruso (enlace inaccesible) . Consultado el 23 de diciembre de 2017. Archivado desde el original el 24 de diciembre de 2017. (indefinido)
↑ Postnauka, Ilya Shkredov - Teorema de Semeredi
↑ Laboratorio Chebyshev, curso de conferencias "Combinatoria aditiva", conferencia 3
↑ Un mini curso sobre combinatoria aditiva Archivado el 29 de agosto de 2017 en Wayback Machine , p. 6
↑ P. Erdős, P. Turán, "Sobre algunas secuencias de números enteros", Journal of the London Mathematical Society (junio de 1936) . Consultado el 23 de diciembre de 2019. Archivado desde el original el 23 de diciembre de 2019. (indefinido)
↑ R. Salem, DC Spencer, Proc. nacional Academia ciencia USA 28 (1942), 561-563 . Consultado el 23 de diciembre de 2017. Archivado desde el original el 3 de junio de 2018. (indefinido)
↑ FA Behrend, "Sobre conjuntos de números enteros que no contienen tres términos en progresión aritmética", Proc. nacional Academia ciencia USA 32 (1946), 331-332. . Consultado el 23 de diciembre de 2017. Archivado desde el original el 4 de junio de 2018. (indefinido)
↑ Michael Elkin, "Una construcción mejorada de conjuntos sin progresión", Israel Journal of Mathematics, 184:93 (agosto de 2011) . Consultado el 23 de diciembre de 2019. Archivado desde el original el 27 de noviembre de 2018. (indefinido)
↑ T. Schoen, ID Shkredov, "Roth's theorem in many variables", Israel Journal of Mathematics, volumen 199, páginas 287-308 (2014) Archivado el 23 de diciembre de 2019 en Wayback Machine ( arXiv:1106.1601 Archivado el 23 de diciembre de 2019 en Wayback máquina )
↑ T. Schoen, O. Sisask, "Teorema de Roth para cuatro variables y estructuras aditivas en sumas de conjuntos dispersos", Foro de Matemáticas Foro de Matemáticas, Sigma, 4, E5. doi:10.1017/fms.2016.2 Archivado el 1 de mayo de 2020 en Wayback Machine ( arXiv:1408.2568 Archivado el 23 de diciembre de 2019 en Wayback Machine )
↑ TC Brown y JP Buhler, Una versión de densidad de un teorema geométrico de Ramsey, Journal of Combinatorial Theory, Serie A 32 (1982), no. 1, 20-34. . Consultado el 23 de diciembre de 2017. Archivado desde el original el 9 de agosto de 2017. (indefinido)
↑ 1 2 R. Meshulam, Sobre subconjuntos de grupos abelianos finitos sin progresiones aritméticas de 3 términos, Journal of Combinatorial Theory, Serie A 71 (1995), no. 1, 168-172. (enlace no disponible)
↑ 1 2 Un mini curso sobre combinatoria aditiva Archivado el 29 de agosto de 2017 en Wayback Machine , p. 39-42
↑ Laboratorio Chebyshev, Ilya Shkredov, Métodos analíticos en combinatoria aditiva, conferencia general
↑ M. Bateman y N. Katz, Nuevos límites en conjuntos de mayúsculas, Journal of the American Mathematical Society 25 (2012), no. 2, 585-613. . Consultado el 23 de diciembre de 2017. Archivado desde el original el 9 de enero de 2018. (indefinido)
↑ E. Croot, V. Lev y PP Pach, Los conjuntos sin progresión en Z_n^4 son exponencialmente pequeños (2016). Preimpresión de arXiv 1605.01506. . Consultado el 23 de diciembre de 2017. Archivado desde el original el 12 de junio de 2018. (indefinido)
↑ 1 2 Prueba del teorema de Roth para grupos con torsión pequeña en arxiv.org . Consultado el 23 de diciembre de 2017. Archivado desde el original el 12 de junio de 2018. (indefinido)
↑ Presentación de la prueba de Ellenberg y Gijswijt en ruso
↑ Y. Edel, Extensiones de topes de productos generalizados, Diseños, Códigos y Criptografía 31 (2004), no. 1, 5-14. . Consultado el 23 de diciembre de 2017. Archivado desde el original el 10 de enero de 2018. (indefinido)