Teorema de Szemerédi

Teorema de Szemerédi Em aritmética combinatória, O teorema de Szemerédi é um resultado sobre progressões aritméticas em subconjuntos dos inteiros. Dentro 1936, Erdős e Turán conjecturaram[1] que todo conjunto de inteiros A com densidade natural positiva contém uma progressão aritmética de k termos para cada k. Endre Szemerédi provou a conjectura em 1975.

Conteúdo 1 Declaração 2 História 3 Limites quantitativos 4 Extensões e generalizações 5 Veja também 6 Notas 7 Leitura adicional 8 External links Statement A subset A of the natural numbers is said to have positive upper density if {displaystyle limsup _{até o infinito }{fratura {|muitas vezes {1,2,3,dotsc ,n}|}{n}}>0} .

O teorema de Szemerédi afirma que um subconjunto dos números naturais com densidade superior positiva contém infinitas progressões aritméticas de comprimento k para todos os inteiros positivos k.

Uma versão finitária equivalente frequentemente usada do teorema afirma que para cada inteiro positivo k e número real {displaystyle delta em (0,1]} , existe um inteiro positivo {estilo de exibição N=N(k,delta )} tal que cada subconjunto de {1, 2, ..., N} de tamanho pelo menos δN contém uma progressão aritmética de comprimento k.

Outra formulação usa a função rk(N), o tamanho do maior subconjunto de {1, 2, ..., N} sem uma progressão aritmética de comprimento k. O teorema de Szemerédi é equivalente ao limite assintótico {estilo de exibição r_{k}(N)=o(N)} .

Aquilo é, k(N) cresce menos do que linearmente com N.

History Van der Waerden's theorem, o precursor do teorema de Szemerédi, foi comprovado em 1927.

The cases k = 1 and k = 2 of Szemerédi's theorem are trivial. O caso k = 3, conhecido como teorema de Roth, foi estabelecido em 1953 por Klaus Roth[2] através de uma adaptação do método do círculo Hardy-Littlewood. Endre Szemerédi[3] provou o caso k = 4 através da combinatória. Usando uma abordagem semelhante à que ele usou para o caso k = 3, Roth[4] deu uma segunda prova para isso em 1972.

O caso geral foi resolvido em 1975, também por Szemerédi,[5] que desenvolveu uma extensão engenhosa e complicada de seu argumento combinatório anterior para k = 4 (chamado "uma obra-prima do raciocínio combinatório" por Erdős[6]). Várias outras provas são agora conhecidas, sendo os mais importantes os de Hillel Furstenberg[7][8] dentro 1977, usando a teoria ergódica, e por Timothy Gowers[9] dentro 2001, usando análise de Fourier e combinatória. Terence Tao chamou as várias provas do teorema de Szemerédi de "Pedra de Roseta" para conectar campos díspares da matemática.[10] Quantitative bounds It is an open problem to determine the exact growth rate of rk(N). Os limites gerais mais conhecidos são {estilo de exibição CNexp à esquerda(-n2^{(n-1)/2}{quadrado[{n}]{log N}}+{fratura {1}{2n}}log log Certo)leq r_{k}(N)leq {fratura {N}{(log log N)^{2^{-2^{k+9}}}}},} Onde {displaystyle n=lceil log krceil } . O limite inferior é devido a O'Bryant[11] construindo sobre o trabalho de Behrend,[12] Rankin,[13] e Elkin.[14][15] O limite superior é devido a Gowers.[9] Para k pequeno, há limites mais apertados do que o caso geral. Quando k = 3, Borgonha,[16][17] Heath-Brown,[18] Ela pertence a você,[19] e Sanders[20] forneceu limites superiores cada vez menores. Os melhores limites atuais são {estilo de exibição N2^{-{quadrado {8log N}}}leq r_{3}(N)leq C{fratura {(log log N)^{4}}{log N}}N} devido a O'Bryant[11] e florescer[21] respectivamente.

Para k = 4, Verde e Tao[22][23] provou que {estilo de exibição r_{4}(N)leq C{fratura {N}{(log N)^{c}}}} for some c > 0.

Extensions and generalizations A multidimensional generalization of Szemerédi's theorem was first proven by Hillel Furstenberg and Yitzhak Katznelson using ergodic theory.[24] Timothy Gowers,[25] Vojtěch Rödl e Jozef Skokan[26][27] com Brendan Nagle, RodlGenericName, e Mathias Schacht,[28] e Terence Tao[29] forneceu provas combinatórias.

Alexander Leibman e Vitaly Bergelson[30] Szemerédi generalizado para progressões polinomiais: Se {displaystyle Um subconjunto mathbb {N} } é um conjunto com densidade superior positiva e {estilo de exibição p_{1}(n),p_{2}(n),dotsc ,p_{k}(n)} são polinômios de valor inteiro tais que {estilo de exibição p_{eu}(0)=0} , então são infinitas {estilo de exibição você,nin mathbb {Z} } de tal modo que {estilo de exibição u+p_{eu}(n)em um} para todos {estilo de exibição 1leq ileq k} . O resultado de Leibman e Bergelson também vale em um cenário multidimensional.

A versão finita do teorema de Szemerédi pode ser generalizada para grupos aditivos finitos incluindo espaços vetoriais sobre corpos finitos.[31] O análogo de campo finito pode ser usado como modelo para entender o teorema nos números naturais.[32] O problema de obter limites no caso k=3 do teorema de Szemerédi no espaço vetorial {estilo de exibição mathbb {F} _{3}^{n}} é conhecido como o problema do conjunto de limites.

O teorema de Green-Tao afirma que os números primos contêm progressões aritméticas longas arbitrárias. Não está implícito no teorema de Szemerédi porque os primos têm densidade 0 nos números naturais. Como parte de sua prova, Ben Green e Tao apresentaram um "relativo" Teorema de Szemerédi que se aplica a subconjuntos dos inteiros (mesmo aqueles com 0 densidade) satisfazendo certas condições de pseudo-aleatoriedade. Um teorema de Szemerédi relativo mais geral foi dado por David Conlon, Jacob Fox, e Yufei Zhao.[33][34] A conjectura de Erdős sobre progressões aritméticas implicaria tanto no teorema de Szemerédi quanto no teorema de Green-Tao.

Veja também Problemas envolvendo progressões aritméticas Teoria de Ramsey ergódica Combinatória aritmética Lema de regularidade de Szemerédi Notas ^ Erdős, Paulo; Turan, Paulo (1936). "Em algumas sequências de inteiros" (PDF). Jornal da Sociedade Matemática de Londres. 11 (4): 261-264. doi:10.1112/jlms/s1-11.4.261. MR 1574918. ^ Roth, Claus Friedrich (1953). "Em certos conjuntos de inteiros". Jornal da Sociedade Matemática de Londres. 28 (1): 104-109. doi:10.1112/jlms/s1-28.1.104. MR 0051853. Zbl 0050.04002. ^ Szemerédi, Mudar (1969). "Em conjuntos de inteiros que não contêm quatro elementos em progressão aritmética". Jornal de Matemática da Academia Húngara de Ciências. 20 (1-2): 89-104. doi:10.1007/BF01894569. MR 0245555. Zbl 0175.04301. ^ Roth, Claus Friedrich (1972). "Irregularidades de sequências relativas a progressões aritméticas, 4". Matemática periódica. húngaro. 2 (1-4): 301-326. doi:10.1007/BF02018670. MR 0369311. S2CID 126176571. ^ Szemerédi, Mudar (1975). "Em conjuntos de inteiros que não contêm k elementos em progressão aritmética" (PDF). Diário de Aritmética. 27: 199-245. doi:10.4064/aa-27-1-199-245. MR 0369312. Zbl 0303.10056. ^ Floresta, Paulo (2013). "Alguns dos meus problemas e resultados favoritos". Em Graham, Ronaldo L.; Ele não poupou, Jaroslav; Mordomo, Steve (ed.). A Matemática de Paul Erdős I (Second ed.). Nova york: Springer. pp. 51-70. doi:10.1007/978-1-4614-7258-2_3. ISBN 978-1-4614-7257-5. MR 1425174. ^ Furstenberg, Hillel (1977). "Comportamento ergódico de medidas diagonais e um teorema de Szemerédi sobre progressões aritméticas". J. d'Analyse Math. 31: 204-256. doi:10.1007/BF02813304. MR 0498471. S2CID 120917478.. ^ Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "A prova teórica ergódica do teorema de Szemerédi". Touro. América. Matemática. Soc. 7 (3): 527-552. doi:10.1090/S0273-0979-1982-15052-2. MR 0670131. ^ Saltar para: a b Gowers, Timóteo (2001). "Uma nova prova do teorema de Szemerédi". Geometria. Função. Anal. 11 (3): 465-588. doi:10.1007/s00039-001-0332-9. MR 1844079. S2CID 124324198. ^ Tao, Terêncio (2007). "A dicotomia entre estrutura e aleatoriedade, progressões aritméticas, e os primos". Em Sanz Solé, Marta; Sória, Javier; Macho, João Luis; verdura, Joana (ed.). Anais do Congresso Internacional de Matemáticos Madrid, 22 a 30 de agosto, 2006. Congresso Internacional de Matemáticos. Volume. 1. Zurique: Sociedade Europeia de Matemática. pp. 581–608. arXiv:matemática/0512114. doi:10.4171/022-1/22. ISBN 978-3-03719-022-7. MR 2334204. ^ Saltar para: a b O'Bryant, Kevin (2011). "Conjuntos de inteiros que não contêm progressões aritméticas longas". Revista Eletrônica de Combinatória. 18 (1). doi:10.37236/546. MR 2788676. ^ Behrend, Félix A. (1946). "Nos conjuntos de inteiros que não contêm três termos em progressão aritmética". Anais da Academia Nacional de Ciências. 32 (12): 331-332. Bibcode:1946PNAS...32..331B. doi:10.1073/pnas.32.12.331. MR 0018694. PMC 1078964. PMID 16578230. Zbl 0060.10302. ^ Rankin, Roberto A. (1962). "Conjuntos de inteiros contendo não mais que um determinado número de termos em progressão aritmética". Proc. Roy. Soc. Seita de Edimburgo. UMA. 65: 332-344. MR 0142526. Zbl 0104.03705. ^ Elkin, Michael (2011). "Uma construção melhorada de conjuntos sem progressão". Jornal de Matemática de Israel. 184 (1): 93-128. arXiv:0801.4310. doi:10.1007/s11856-011-0061-1. MR 2823971. ^ Verde, Ben; Lobo, Júlia (2010). "Uma nota sobre a melhoria de Elkin da construção de Behrend". Em Chudnovsky, Davi; Chudnovsky, Gregório (ed.). Teoria Aditiva dos Números. Teoria dos números aditiva. Festschrift em homenagem ao sexagésimo aniversário de Melvyn B. Nathanson. Nova york: Springer. pp. 141-144. arXiv:0810.0732. doi:10.1007/978-0-387-68361-4_9. ISBN 978-0-387-37029-3. MR 2744752. S2CID 10475217. ^ Borgonha, Jean (1999). "Em triplos na progressão aritmética". Geometria. Função. Anal. 9 (5): 968–984. doi:10.1007/s000390050105. MR 1726234. S2CID 392820. ^ Borgonha, Jean (2008). "Teorema de Roth sobre progressões revisitado". J. Anal. Matemática. 104 (1): 155-192. doi:10.1007/s11854-008-0020-x. MR 2403433. S2CID 16985451. ^ Heath-Brown, Rogério (1987). "Conjuntos inteiros que não contêm progressões aritméticas". Jornal da Sociedade Matemática de Londres. 35 (3): 385-394. doi:10.1112/jlms/s2-35.3.385. MR 0889362. ^ Szemerédi, Mudar (1990). "Conjuntos inteiros que não contêm progressões aritméticas". Revista Matemática Húngara. 56 (1-2): 155-158. doi:10.1007/BF01903717. MR 1100788. ^ Sanders, Tom (2011). "Sobre o teorema de Roth sobre progressões". Anais da Matemática. 174 (1): 619-636. arXiv:1011.0104. doi:10.4007/anais.2011.174.1.20. MR 2811612. S2CID 53331882. ^ Florescer, Thomas F. (2016). "Uma melhoria quantitativa para o teorema de Roth em progressões aritméticas". Jornal da Sociedade Matemática de Londres. Segunda Série. 93 (3): 643–663. arXiv:1405.5800. doi:10.1112/jlms/jdw010. MR 3509957. S2CID 27536138. ^ Verde, Ben; Tao, Terêncio (2009). "Novos limites para o teorema de Szemeredi. II. Um novo limite para r4(N)". Em Chen, William W. EU.; Gowers, Timóteo; Halberstam, Oi; Schmidt, Wolfgang; Vaughan, Roberto Carlos (ed.). Novos limites para o teorema de Szemeredi, II: Um novo limite para r_4(N). Teoria analítica dos números. Ensaios em homenagem a Klaus Roth por ocasião de seu 80º aniversário. Cambridge: Cambridge University Press. pp. 180-204. arXiv:matemática/0610604. Bibcode:2006matemática.....10604G. ISBN 978-0-521-51538-2. MR 2508645. Zbl 1158.11007. ^ Verde, Ben; Tao, Terêncio (2017). "Novos limites para o teorema de Szemerédi, III: Um limite polilogarítmico para r4(N)". Matemática. 63 (3): 944-1040. arXiv:1705.01703. doi:10.1112/S0025579317000316. MR 3731312. ^ Furstenberg, Hillel; Katznelson, Yitzhak (1978). "Um teorema ergódico de Szemerédi para transformações comutadas". Revista de Análise Matemática. 38 (1): 275-291. doi:10.1007/BF02790016. MR 0531279. S2CID 123386017. ^ Gowers, Timóteo (2007). "Regularidade do hipergrafo e o teorema de Szemerédi multidimensional". Anais da Matemática. 166 (3): 897–946. arXiv:0710.3032. doi:10.4007/anais.2007.166.897. MR 2373376. S2CID 56118006. ^ Rodl, Vojtěch; Saltador, Joseph (2004). "Lema de regularidade para hipergrafos k-uniformes". Algoritmos de Estruturas Aleatórias. 25 (1): 1-42. doi:10.1002/rsa.20017. MR 2069663. ^ Rodl, Vojtěch; Saltador, Joseph (2006). "Aplicações do lema da regularidade para hipergrafos uniformes" (PDF). Algoritmos de Estruturas Aleatórias. 28 (2): 180-194. doi:10.1002/rsa.20108. MR 2198496. ^ Nagle, Brendan; RodlGenericName, Vojtěch; Schacht, Mathias (2006). "O lema de contagem para hipergrafos k-uniformes regulares". Algoritmos de Estruturas Aleatórias. 28 (2): 113-179. doi:10.1002/rsa.20117. MR 2198495. ^ Tao, Terêncio (2006). "Uma variante do lema de remoção do hipergrafo". Jornal de Teoria Combinatória, Série A. 113 (7): 1257-1280. arXiv:matemática/0503572. doi:10.1016/j.jcta.2005.11.006. MR 2259060. ^ Bergelson, Vitalidade; Leibman, Alexandre (1996). "Extensões polinomiais dos teoremas de van der Waerden e Szemerédi". Jornal da Sociedade Americana de Matemática. 9 (3): 725–753. doi:10.1090/S0894-0347-96-00194-4. MR 1325795. ^ Furstenberg, Hillel; Katznelson, Yitzhak (1991). "Uma versão densidade do teorema de Hales-Jewett". Revista de Análise Matemática. 57 (1): 64-119. doi:10.1007/BF03041066. MR 1191743. S2CID 123036744. ^ Lobo, Júlia (2015). "Modelos de campo finito em combinatória aritmética – dez anos depois". Campos finitos e suas aplicações. 32: 233-274. doi:10.1016/j.ffa.2014.11.003. MR 3293412. ^ Conlon, Davi; Raposa, Jacó; Zhao, Yufei (2015). "O teorema de Szemerédi relativo". Análise Geométrica e Funcional. 25 (3): 733–762. arXiv:1305.5440. doi:10.1007/s00039-015-0324-9. MR 3361771. S2CID 14398869. ^ Zhao, Yufei (2014). "Uma prova de transferência aritmética de um teorema de Szemerédi relativo". Anais de Matemática da Sociedade Filosófica de Cambridge. 156 (2): 255-261. arXiv:1307.4959. Bibcode:2014MPCPS.156..255Z. doi:10.1017/S0305004113000662. MR 3177868. S2CID 119673319. Leitura adicional Tao, Terêncio (2007). "As abordagens ergódica e combinatória do teorema de Szemerédi". Em Granville, André; Nathanson, Melvin B.; Solymosi, Joseph (ed.). Combinatória Aditiva. CRM Proceedings & Lecture Notes. Volume. 43. Providência, RI: Sociedade Americana de Matemática. pp. 145–193. arXiv:matemática/0604456. Bibcode:2006matemática......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005. Links externos Fonte PlanetMath para a versão inicial desta página Anúncio de Ben Green e Terence Tao – a pré-impressão está disponível em math.NT/0404188 Discussão do teorema de Szemerédi (papel 1 do 5) Ben Green e Terence Tao: Teorema de Szemerédi na Scholarpedia Weisstein, Eric W. "Teorema de Szemeredis". MathWorld. Sujeira, James; Hodge, Davi (2012). "6,000,000: Endre Szemerédi ganha o Prêmio Abel". Numberphile. Brady Haran. Categorias: Combinatória aditivaTeoria de RamseyTeoremas em combinatóriaTeoremas em teoria dos números