Teorema de Szemerédi

Los subconjuntos largos y densos de números enteros contienen progresiones aritméticas arbitrariamente grandes

En combinatoria aritmética , el teorema de Szemerédi es un resultado relativo a las progresiones aritméticas en subconjuntos de los números enteros. En 1936, Erdős y Turán conjeturaron ^[1] que todo conjunto de números enteros A con densidad natural positiva contiene una progresión aritmética de k términos 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 _{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 una progresión aritmética de longitud k para todos los enteros positivos k .

Una versión finitaria equivalente del teorema, frecuentemente utilizada, establece que para cada entero positivo k y número real , existe un entero positivo ${\displaystyle \delta \in (0,1]}$

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

de manera que cada subconjunto de {1, 2, ..., N } de tamaño contiene al menos una progresión aritmética de longitud k . ${\displaystyle \delta N}$

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

El caso general fue resuelto en 1975, también por Szemerédi, ^[5] quien desarrolló una extensión ingeniosa y complicada de su argumento combinatorio anterior para k = 4 (llamado "una obra maestra del razonamiento combinatorio" por Erdős ^[6] ). Ahora se conocen varias otras pruebas, siendo las más importantes las de Hillel Furstenberg ^{[7] [8]} en 1977, usando la teoría ergódica , y las de Timothy Gowers ^[9] en 2001, usando tanto el análisis de Fourier como la combinatoria mientras que también introdujo lo que ahora se llama la norma de Gowers . Terence Tao ha llamado a las diversas pruebas del teorema de Szemerédi una " piedra Rosetta " para conectar campos dispares de las matemáticas. ^[10]

Límites cuantitativos

Determinar la tasa de crecimiento exacta de r _k ( N ) es un problema abierto . 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 . 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] ${\displaystyle n=\lceil \log k\rceil }$

Para valores pequeños de k , existen límites más estrictos que en el caso general. Cuando k = 3, Bourgain , ^{[16] [17]} Heath-Brown, ^[18] Szemerédi, ^[19] Sanders , ^[20] y Bloom ^[21] establecieron límites superiores progresivamente más pequeños, y Bloom y Sisask demostraron entonces el primer límite que rompió la denominada "barrera logarítmica". ^[22] Los mejores límites actuales son

${\displaystyle N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq Ne^{-c(\log N)^{1/9}}}$, por alguna constante , ${\displaystyle c>0}$

respectivamente debido a O'Bryant, ^[11] y Bloom y Sisask ^[23] (este último se basó en el resultado innovador de Kelley y Meka, ^[24] quienes obtuvieron el mismo límite superior, con "1/9" reemplazado por "1/12").

Para k = 4, Green y Tao ^{[25] [26]} demostraron que

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

Para k = 5 en 2023 y k ≥ 5 en 2024, Leng, Sah y Sawhney demostraron en preprints ^{[27] [28] [29]} que:

${\displaystyle r_{k}(N)\leq CN\exp(-(\log \log N)^{c})}$

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. ^[30] Timothy Gowers , ^[31] Vojtěch Rödl y Jozef Skokan ^{[32] [33]} con Brendan Nagle, Rödl y Mathias Schacht , ^[34] y Terence Tao ^[35] proporcionaron pruebas combinatorias.

Alexander Leibman y Vitaly Bergelson ^[36] generalizaron el resultado de Szemerédi a progresiones polinómicas: si es un conjunto con densidad superior positiva y son polinomios de valores enteros tales que , entonces hay infinitos tales que para todo . El resultado de Leibman y Bergelson también se cumple en un entorno multidimensional. ${\displaystyle A\subset \mathbb {N} }$ ${\displaystyle p_{1}(n),p_{2}(n),\dotsc ,p_{k}(n)}$ ${\displaystyle p_{i}(0)=0}$ ${\displaystyle u,n\in \mathbb {Z} }$ ${\displaystyle u+p_{i}(n)\in A}$ ${\displaystyle 1\leq i\leq k}$

La versión finitaria del teorema de Szemerédi se puede generalizar a grupos aditivos finitos, incluyendo espacios vectoriales sobre cuerpos finitos . ^[37] El análogo del cuerpo finito se puede utilizar como modelo para entender el teorema en los números naturales. ^[38] El problema de obtener límites en el caso k=3 del teorema de Szemerédi en el espacio vectorial se conoce como el problema del conjunto de límites . ${\displaystyle \mathbb {F} _{3}^{n}}$

El teorema de Green-Tao afirma que los números primos contienen progresiones aritméticas arbitrariamente largas. Esto no está implícito en el teorema de Szemerédi porque los 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 los números enteros (incluso aquellos con densidad 0) que satisfacen ciertas condiciones de pseudoaleatoriedad . Posteriormente, David Conlon , Jacob Fox y Yufei Zhao propusieron un teorema de Szemerédi relativo más general . ^{[39] [40]}

La conjetura de Erdős sobre progresiones aritméticas 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
• Teorema de van der Waerden
• Lema de eliminación de hipergrafos § Prueba del teorema de Szemerédi

Notas

1. Erdős, Paul ; Turán, Paul (1936). "Sobre algunas sucesiones de números enteros" (PDF) . Revista de la Sociedad Matemática de Londres . 11 (4): 261–264. doi :10.1112/jlms/s1-11.4.261. MR  1574918.
2. Roth, Klaus Friedrich (1953). "Sobre 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. MR  0051853. Zbl  0050.04002.
3. Szemerédi, Endre (1969). "Sobre conjuntos de números enteros que no contienen cuatro elementos en progresión aritmética". Acta Mathematica Academiae Scientiarum Hungaricae . 20 (1–2): 89–104. doi : 10.1007/BF01894569 . Señor  0245555. Zbl  0175.04301.
4. Roth, Klaus Friedrich (1972). "Irregularidades de secuencias relativas a progresiones aritméticas, IV". Periodica Math. Hungar . 2 (1–4): 301–326. doi :10.1007/BF02018670. MR  0369311. S2CID  126176571.
5. Szemerédi, Endre (1975). "Sobre conjuntos de números enteros que no contienen k elementos en progresión aritmética" (PDF) . Acta Aritmética . 27 : 199–245. doi : 10.4064/aa-27-1-199-245 . SEÑOR  0369312. Zbl  0303.10056.
6. Erdős, Paul (2013). "Algunos de mis problemas y resultados favoritos". En Graham, Ronald L.; Nešetřil, Jaroslav; Butler, 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  .
7. Furstenberg, Hillel (1977). "Comportamiento ergódico de medidas diagonales y un teorema de Szemerédi sobre progresiones aritméticas". Journal d'Analyse Mathématique . 31 : 204–256. doi : 10.1007/BF02813304 . MR  0498471. S2CID  120917478..
8. Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "La prueba teórica ergódica del teorema de Szemerédi". Bull. Amer. Math. Soc. 7 (3): 527–552. doi : 10.1090/S0273-0979-1982-15052-2 . MR  0670131.
9. 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. MR  1844079. S2CID  124324198.
10. Tao, Terence (2007). "La dicotomía entre estructura y aleatoriedad, progresiones aritméticas y los números 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 . Vol. 1. Zúrich: European Mathematical Society . págs. 581–608. arXiv : math/0512114 . doi :10.4171/022-1/22. ISBN 978-3-03719-022-7.Señor 2334204  .
11. O'Bryant, Kevin (2011). "Conjuntos de números enteros que no contienen progresiones aritméticas largas". Revista electrónica de combinatoria . 18 (1). arXiv : 0811.3057 . doi : 10.37236/546 . MR  2788676.
12. 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. Bibcode :1946PNAS...32..331B. doi : 10.1073/pnas.32.12.331 . MR  0018694. PMC 1078964 . PMID  16578230. Zbl  0060.10302. 
13. Rankin, Robert A. (1962). "Conjuntos de números enteros que no contienen más de un número dado de términos en progresión aritmética". Proc. R. Soc. Edinburgh Sect. A. 65 : 332–344. MR  0142526. Zbl  0104.03705.
14. Elkin, Michael (2011). "Una construcción mejorada de conjuntos libres de progresión". Revista israelí de matemáticas . 184 (1): 93–128. arXiv : 0801.4310 . doi : 10.1007/s11856-011-0061-1 . MR  2823971.
15. Green, Ben; Wolf, Julia (2010). "Una nota sobre la mejora de la construcción de Behrend por parte de Elkin". En Chudnovsky, David; Chudnovsky, Gregory (eds.). Teoría de números aditivos . Teoría de números aditivos. Festschrift en honor del 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. Sr.  2744752. S2CID  10475217.
16. Bourgain, Jean (1999). "Sobre los triples en progresión aritmética". Geom. Funct. Anal. 9 (5): 968–984. doi :10.1007/s000390050105. MR  1726234. S2CID  392820.
17. Bourgain, Jean (2008). "Revisión del teorema de Roth sobre progresiones". Revista de Análisis Matemático . 104 (1): 155-192. doi : 10.1007/s11854-008-0020-x . SEÑOR  2403433. S2CID  16985451.
18. Heath-Brown, Roger (1987). "Conjuntos enteros que no contienen progresiones aritméticas". Journal of the London Mathematical Society . 35 (3): 385–394. doi :10.1112/jlms/s2-35.3.385. MR  0889362.
19. Szemerédi, Endre (1990). "Conjuntos de números enteros que no contienen progresiones aritméticas". Acta Mathematica Hungarica . 56 (1–2): 155–158. doi : 10.1007/BF01903717 . SEÑOR  1100788.
20. Sanders, Tom (2011). "Sobre el teorema de Roth sobre progresiones". Anales de Matemáticas . 174 (1): 619–636. arXiv : 1011.0104 . doi :10.4007/annals.2011.174.1.20. MR  2811612. S2CID  53331882.
21. 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. MR  3509957. S2CID  27536138.
22. Bloom, Thomas F.; Sisask, Olof (2020). "Rompiendo la barrera logarítmica en el teorema de Roth sobre progresiones aritméticas". arXiv : 2007.03528v2 [math.NT].
23. Bloom, Thomas F.; Sisask, Olof (2023). "Una mejora de los límites de Kelley-Meka en progresiones aritméticas de tres términos". arXiv : 2309.02353v1 [math.NT].
24. Kelley, Zander; Meka, Raghu (2023). "Límites fuertes para progresiones de 3 dimensiones". arXiv : 2302.05537v5 [math.NT].
25. Green, Ben; Tao, Terence (2009). "Nuevos límites para el teorema de Szemeredi. II. Un nuevo límite para r ₄ ( 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 : math/0610604 . Código Bibliográfico :2006math.....10604G. ISBN 978-0-521-51538-2.Sr. 2508645.  Zbl 1158.11007  .
26. Verde, Ben; Tao, Terence (2017). "Nuevos límites para el teorema de Szemerédi, III: un límite polilogarítmico para r ₄ (N)". Matemática . 63 (3): 944–1040. arXiv : 1705.01703 . doi :10.1112/S0025579317000316. SEÑOR  3731312. S2CID  119145424.
27. Leng, James; Sah, Ashwin; Sawhney, Mehtaab (2024). "Límites mejorados para el teorema de Szemerédi". arXiv : 2402.17995 .
28. Leng, James; Sah, Ashwin; Sawhney, Mehtaab (2023). "Límites mejorados para progresiones aritméticas de cinco términos". arXiv : 2312.10776 .
29. Sloman, Leila (5 de agosto de 2024). "Estudiantes de posgrado encuentran patrones inevitables en grandes conjuntos de números". Quanta Magazine . Consultado el 7 de agosto de 2024 .
30. Fürstenberg, Hillel ; Katznelson, Yitzhak (1978). "Un teorema ergódico de Szemerédi para transformaciones conmutadas". Revista de Análisis Matemático . 38 (1): 275–291. doi : 10.1007/BF02790016 . SEÑOR  0531279. S2CID  123386017.
31. Gowers, Timothy (2007). "Regularidad de hipergrafos y el teorema multidimensional de Szemerédi". Anales de Matemáticas . 166 (3): 897–946. arXiv : 0710.3032 . doi :10.4007/annals.2007.166.897. MR  2373376. S2CID  56118006.
32. Rödl, Vojtěch ; Skokan, Jozef (2004). "Lema de regularidad para hipergrafías k-uniformes". Algoritmos de estructuras aleatorias . 25 (1): 1–42. doi :10.1002/rsa.20017. SEÑOR  2069663. S2CID  7458739.
33. Rödl, Vojtěch ; Skokan, Jozef (2006). "Aplicaciones del lema de regularidad para hipergrafos uniformes" (PDF) . Random Structures Algorithms . 28 (2): 180–194. doi :10.1002/rsa.20108. MR  2198496. S2CID  18203198.
34. Nagle, Brendan; Rödl, Vojtěch ; Schacht, Mathias (2006). "El lema de conteo para hipergrafos k-uniformes regulares". Algoritmos de estructuras aleatorias . 28 (2): 113–179. doi :10.1002/rsa.20117. MR  2198495. S2CID  14126774.
35. Tao, Terence (2006). "Una variante del lema de eliminación de hipergrafos". Journal of Combinatorial Theory . Serie A. 113 (7): 1257–1280. arXiv : math/0503572 . doi : 10.1016/j.jcta.2005.11.006 . MR  2259060.
36. Bergelson, Vitaly ; Leibman, Alexander (1996). "Extensiones polinómicas de los teoremas de van der Waerden y Szemerédi". Revista de la Sociedad Americana de Matemáticas . 9 (3): 725–753. doi : 10.1090/S0894-0347-96-00194-4 . MR  1325795.
37. 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 . MR  1191743. S2CID  123036744.
38. Wolf, Julia (2015). "Modelos de campos finitos 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 . hdl : 1983/d340f853-0584-49c8-a463-ea16ee51ce0f . MR  3293412.
39. Conlon, David ; Fox, Jacob ; Zhao, Yufei (2015). "Un teorema de Szemerédi relativo". Análisis geométrico y funcional . 25 (3): 733–762. arXiv : 1305.5440 . doi : 10.1007/s00039-015-0324-9 . MR  3361771. S2CID  14398869.
40. Zhao, Yufei (2014). "Una prueba de transferencia aritmética de un teorema de Szemerédi relativo". Actas matemáticas 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. MR  3177868. S2CID  119673319.

Lectura adicional

• 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 y notas de conferencias de CRM. Vol. 43. Providence, RI: American Mathematical Society . págs. 145–193. arXiv : math/0604456 . Código Bibliográfico :2006math......4456T. ISBN. 978-0-8218-4351-2.MR  2359471.Zbl 1159.11005  .​

Enlaces externos

• Fuente de PlanetMath para la versión inicial de esta página Archivado el 16 de julio de 2012 en Wayback Machine
• Anuncio de Ben Green y Terence Tao: la preimpresión 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". MundoMatemático .
• Grime, James; Hodge, David (2012). «6.000.000: Endre Szemerédi gana el premio Abel». Numberphile . Brady Haran . Archivado desde el original el 2014-01-09 . Consultado el 2013-04-02 .