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 [1] que cada conjunto de los enteros A con positivo densidad natural contiene una k -term progresión aritmética 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 una densidad superior positiva si
- .
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 enteros positivos k .
Una versión finitaria equivalente de uso frecuente del teorema establece que para cada entero positivo k y número real, existe un entero positivo
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 a la cota asintótica
- .
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] mediante una adaptación del método circular 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 esto en 1972.
El caso general fue resuelto en 1975, también por Szemerédi, [5] quien desarrolló una ingeniosa y complicada extensión de su anterior argumento combinatorio para k = 4 (llamado "una obra maestra del razonamiento combinatorio" por Erdős [6] ). Actualmente se conocen varias otras pruebas, siendo las más importantes las de Hillel Furstenberg [7] [8] en 1977, utilizando la teoría ergódica , y las de Timothy Gowers [9] en 2001, utilizando tanto el análisis de Fourier como la combinatoria . Terence Tao ha llamado a las diversas pruebas del teorema de Szemerédi una " piedra de Rosetta " para conectar campos dispares de las matemáticas. [10]
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
dónde . El límite inferior se debe a que O'Bryant [11] se basa 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 , hay límites más estrictos 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
debido a O'Bryant [11] y Bloom [21] respectivamente.
Para k = 4, Green y Tao [22] [23] demostraron que
para algunos c > 0.
Extensiones y generalizaciones
Una generalización multidimensional del teorema de Szemerédi fue probada por primera vez por Hillel Furstenberg e Yitzhak Katznelson utilizando la teoría ergódica. [24] 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 las progresiones polinómicas de Szemerédi: Si es un conjunto con densidad superior positiva y son polinomios con valores enteros tales que, entonces hay infinitos tal que para todos . El resultado de Leibman y Bergelson también se mantiene en un entorno multidimensional.
La versión finitaria del teorema de Szemerédi se puede generalizar a grupos aditivos finitos que incluyen espacios vectoriales sobre campos finitos . [31] El análogo de campo finito se puede utilizar como modelo para comprender el teorema en números naturales. [32] El problema de obtener límites en el caso k = 3 del teorema de Szemerédi en el espacio vectorialse conoce como el problema del ajuste de la tapa .
El teorema de Green-Tao afirma que los números primos contienen progresiones aritméticas largas arbitrarias. 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 demostración, 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 relativo más general de Szemerédi . [33] [34]
La conjetura de Erdős sobre progresiones aritméticas implicaría tanto el teorema de Szemerédi como el teorema de Green-Tao.
Ver también
- Problemas que involucran progresiones aritméticas
- Teoría ergódica de Ramsey
- Combinatoria aritmética
- Lema de regularidad de Szemerédi
Notas
- ^ Erdős, Paul ; Turán, Paul (1936). "Sobre algunas secuencias de enteros" (PDF) . Revista de la Sociedad Matemática de Londres . 11 (4): 261-264. doi : 10.1112 / jlms / s1-11.4.261 . Señor 1574918 .
- ^ Roth, Klaus Friedrich (1953). "En ciertos conjuntos de números enteros". Revista de la Sociedad Matemática de Londres . 28 (1): 104–109. doi : 10.1112 / jlms / s1-28.1.104 . Señor 0051853 . Zbl 0050.04002 .
- ^ Szemerédi, Endre (1969). "En conjuntos de números enteros que no contienen cuatro elementos en progresión aritmética". Acta Math. Acad. Sci. Hung . 20 (1–2): 89–104. doi : 10.1007 / BF01894569 . Señor 0245555 . Zbl 0175.04301 .
- ^ Roth, Klaus Friedrich (1972). "Irregularidades de secuencias relativas a progresiones aritméticas, IV". Matemáticas periódicas. Hungar . 2 (1–4): 301–326. doi : 10.1007 / BF02018670 . Señor 0369311 .
- ^ Szemerédi, Endre (1975). "En conjuntos de enteros que no contienen k elementos en progresión aritmética" (PDF) . Acta Arithmetica . 27 : 199–245. doi : 10.4064 / aa-27-1-199-245 . Señor 0369312 . Zbl 0303.10056 .
- ^ Erdős, Paul (2013). "Algunos de mis problemas y resultados favoritos". En Graham, Ronald L .; Nešetřil, Jaroslav; Mayordomo, Steve (eds.). Las matemáticas de Paul Erdős I (Segunda ed.). Nueva York: Springer. págs. 51–70. doi : 10.1007 / 978-1-4614-7258-2_3 . ISBN 978-1-4614-7257-5. Señor 1425174 .
- ^ Furstenberg, Hillel (1977). "Comportamiento ergódico de medidas diagonales y un teorema de Szemerédi sobre progresiones aritméticas". J. d'Analyse Math . 31 : 204-256. doi : 10.1007 / BF02813304 . Señor 0498471 ..
- ^ Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "La prueba teórica ergódica del teorema de Szemerédi" . Toro. Amer. Matemáticas. Soc. 7 (3): 527–552. doi : 10.1090 / S0273-0979-1982-15052-2 . Señor 0670131 .
- ^ a b Gowers, Timothy (2001). "Una nueva prueba del teorema de Szemerédi" . Geom. Funct. Anal. 11 (3): 465–588. doi : 10.1007 / s00039-001-0332-9 . Señor 1844079 .
- ^ Tao, Terence (2007). "La dicotomía entre estructura y aleatoriedad, progresiones aritméticas y primos". En Sanz-Solé, Marta; Soria, Javier; Varona, Juan Luis; Verdera, Joan (eds.). Actas del Congreso Internacional de Matemáticos Madrid, 22-30 de agosto de 2006 . Congreso Internacional de Matemáticos . 1 . Zürich: Sociedad Matemática Europea . págs. 581–608. arXiv : matemáticas / 0512114 . doi : 10.4171 / 022-1 / 22 . ISBN 978-3-03719-022-7. Señor 2334204 .
- ^ a b O'Bryant, Kevin (2011). "Conjuntos de enteros que no contienen largas progresiones aritméticas" . Revista electrónica de combinatoria . 18 (1). doi : 10.37236 / 546 . Señor 2788676 .
- ^ Behrend, Felix A. (1946). "Sobre los conjuntos de números enteros que no contienen tres términos en progresión aritmética" . Actas de la Academia Nacional de Ciencias . 32 (12): 331–332. Código Bibliográfico : 1946PNAS ... 32..331B . doi : 10.1073 / pnas.32.12.331 . Señor 0018694 . PMC 1078964 . PMID 16578230 . Zbl 0060.10302 .
- ^ Rankin, Robert A. (1962). "Conjuntos de números enteros que no contengan más de un número determinado de términos en progresión aritmética". Proc. Roy. Soc. Secta de Edimburgo. Una . 65 : 332–344. Señor 0142526 . Zbl 0104.03705 .
- ^ Elkin, Michael (2011). "Una construcción mejorada de conjuntos sin progresión". Revista de Matemáticas de Israel . 184 (1): 93-128. arXiv : 0801.4310 . doi : 10.1007 / s11856-011-0061-1 . Señor 2823971 .
- ^ Green, Ben; Wolf, Julia (2010). "Una nota sobre la mejora de Elkin de la construcción de Behrend". En Chudnovsky, David; Chudnovsky, Gregory (eds.). Teoría de números aditivos . Teoría de números aditivos. Festschrift en honor al sexagésimo cumpleaños de Melvyn B. Nathanson . Nueva York: Springer. págs. 141-144. arXiv : 0810.0732 . doi : 10.1007 / 978-0-387-68361-4_9 . ISBN 978-0-387-37029-3. Señor 2744752 .
- ^ Bourgain, Jean (1999). "Sobre triples en progresión aritmética". Geom. Funct. Anal. 9 (5): 968–984. doi : 10.1007 / s000390050105 . Señor 1726234 .
- ^ Bourgain, Jean (2008). "Teorema de Roth sobre progresiones revisado". J. Anal. Matemáticas . 104 (1): 155-192. doi : 10.1007 / s11854-008-0020-x . Señor 2403433 .
- ^ Heath-Brown, Roger (1987). "Conjuntos enteros que no contienen progresiones aritméticas". Revista de la Sociedad Matemática de Londres . 35 (3): 385–394. doi : 10.1112 / jlms / s2-35.3.385 . Señor 0889362 .
- ^ Szemerédi, Endre (1990). "Conjuntos enteros que no contienen progresiones aritméticas". Acta Math. Hungar . 56 (1-2): 155-158. doi : 10.1007 / BF01903717 . Señor 1100788 .
- ^ Sanders, Tom (2011). "Sobre el teorema de Roth sobre progresiones". Annals of Mathematics . 174 (1): 619–636. arXiv : 1011.0104 . doi : 10.4007 / annals.2011.174.1.20 . Señor 2811612 .
- ^ Bloom, Thomas F. (2016). "Una mejora cuantitativa del teorema de Roth sobre progresiones aritméticas". Revista de la Sociedad Matemática de Londres . Segunda Serie. 93 (3): 643–663. arXiv : 1405.5800 . doi : 10.1112 / jlms / jdw010 . Señor 3509957 .
- ^ Green, Ben; Tao, Terence (2009). "Nuevos límites para el teorema de Szemeredi. II. Un nuevo límite para r 4 ( N )". En Chen, William WL; Gowers, Timothy ; Halberstam, Heini ; Schmidt, Wolfgang ; Vaughan, Robert Charles (eds.). Nuevos límites para el teorema de Szemeredi, II: Un nuevo límite para r_4 (N) . Teoría analítica de números. Ensayos en honor a Klaus Roth con motivo de su 80 cumpleaños . Cambridge: Cambridge University Press . págs. 180–204. arXiv : matemáticas / 0610604 . Bibcode : 2006math ..... 10604G . ISBN 978-0-521-51538-2. Señor 2508645 . Zbl 1158.11007 .
- ^ Green, Ben; Tao, Terence (2017). "Nuevos límites para el teorema de Szemerédi, III: Un límite polilogarítmico para r 4 (N)". Mathematika . 63 (3): 944–1040. arXiv : 1705.01703 . doi : 10.1112 / S0025579317000316 . Señor 3731312 .
- ^ Furstenberg, Hillel ; Katznelson, Yitzhak (1978). "Un teorema ergódico de Szemerédi para conmutar transformaciones". Journal d'Analyse Mathématique . 38 (1): 275-291. doi : 10.1007 / BF02790016 . Señor 0531279 .
- ^ Gowers, Timothy (2007). "Regularidad hipergráfica y el teorema multidimensional de Szemerédi". Annals of Mathematics . 166 (3): 897–946. arXiv : 0710.3032 . doi : 10.4007 / annals.2007.166.897 . Señor 2373376 .
- ^ Rödl, Vojtěch ; Skokan, Jozef (2004). "Lema de regularidad para k-uniformes hipergráficos". Algoritmos de estructuras aleatorias . 25 (1): 1–42. doi : 10.1002 / rsa.20017 . Señor 2069663 .
- ^ Rödl, Vojtěch ; Skokan, Jozef (2006). "Aplicaciones del lema de regularidad para hipergráficos uniformes" (PDF) . Algoritmos de estructuras aleatorias . 28 (2): 180-194. doi : 10.1002 / rsa.20108 . Señor 2198496 .
- ^ Nagle, Brendan; Rödl, Vojtěch ; Schacht, Mathias (2006). "El lema de conteo para hipergráficos uniformes k regulares". Algoritmos de estructuras aleatorias . 28 (2): 113–179. doi : 10.1002 / rsa.20117 . Señor 2198495 .
- ^ Tao, Terence (2006). "Una variante del lema de eliminación de hipergráfico". Revista de Teoría Combinatoria, serie A . 113 (7): 1257-1280. arXiv : matemáticas / 0503572 . doi : 10.1016 / j.jcta.2005.11.006 . Señor 2259060 .
- ^ Bergelson, Vitaly ; Leibman, Alexander (1996). "Extensiones polinomiales de los teoremas de van der Waerden y Szemerédi" . Revista de la Sociedad Matemática Estadounidense . 9 (3): 725–753. doi : 10.1090 / S0894-0347-96-00194-4 . Señor 1325795 .
- ^ Furstenberg, Hillel ; Katznelson, Yitzhak (1991). "Una versión de densidad del teorema de Hales-Jewett". Journal d'Analyse Mathématique . 57 (1): 64-119. doi : 10.1007 / BF03041066 . Señor 1191743 .
- ^ Wolf, Julia (2015). "Modelos de campo finito en combinatoria aritmética — diez años después" . Campos finitos y sus aplicaciones . 32 : 233-274. doi : 10.1016 / j.ffa.2014.11.003 . Señor 3293412 .
- ^ Conlon, David ; Fox, Jacob ; Zhao, Yufei (2015). "Un teorema relativo de Szemerédi". Análisis geométrico y funcional . 25 (3): 733–762. arXiv : 1305.5440 . doi : 10.1007 / s00039-015-0324-9 . Señor 3361771 .
- ^ Zhao, Yufei (2014). "Una prueba de transferencia aritmética de un teorema relativo de Szemerédi". Procedimientos matemáticos de la Sociedad Filosófica de Cambridge . 156 (2): 255–261. arXiv : 1307.4959 . Código bibliográfico : 2014MPCPS.156..255Z . doi : 10.1017 / S0305004113000662 . Señor 3177868 .
Otras lecturas
- Tao, Terence (2007). "Los enfoques ergódico y combinatorio del teorema de Szemerédi". En Granville, Andrew; Nathanson, Melvyn B .; Solymosi, József (eds.). Combinatoria aditiva . Actas de CRM y notas de conferencias. 43 . Providence, RI: Sociedad Matemática Estadounidense . págs. 145-193. arXiv : matemáticas / 0604456 . Bibcode : 2006math ... 4456T . ISBN 978-0-8218-4351-2. Señor 2359471 . Zbl 1159.11005 .
enlaces externos
- Fuente de PlanetMath para la versión inicial de esta página
- Anuncio de Ben Green y Terence Tao : la versión preliminar está disponible en math.NT / 0404188
- Discusión del teorema de Szemerédi (parte 1 de 5)
- Ben Green y Terence Tao: el teorema de Szemerédi en Scholarpedia
- Weisstein, Eric W. "Teorema de Szemeredis" . MathWorld .
- Grime, James; Hodge, David (2012). "6.000.000: Endre Szemerédi gana el Premio Abel" . Numberphile . Brady Haran .