Il teorema di Szemerédi

Il teorema di Szemerédi In combinatoria aritmetica, Il teorema di Szemerédi è un risultato relativo alle progressioni aritmetiche nei sottoinsiemi degli interi. In 1936, Erdős e Turán hanno ipotizzato[1] che ogni insieme di interi A con densità naturale positiva contiene una progressione aritmetica di k termini per ogni k. Endre Szemerédi ha dimostrato la congettura in 1975.

Contenuti 1 Dichiarazione 2 Storia 3 Limiti quantitativi 4 Estensioni e generalizzazioni 5 Guarda anche 6 Appunti 7 Ulteriori letture 8 External links Statement A subset A of the natural numbers is said to have positive upper density if {displaystyle limsup _{infty }{frac {|Spesso {1,2,3,punti ,n}|}{n}}>0} .

Il teorema di Szemerédi afferma che un sottoinsieme dei numeri naturali con densità superiore positiva contiene infinite progressioni aritmetiche di lunghezza k per tutti gli interi positivi k.

Una versione finitaria equivalente spesso usata del teorema afferma che per ogni intero positivo k e numero reale {displaystyle delta in (0,1]} , esiste un numero intero positivo {stile di visualizzazione N=N(K,delta )} tale che ogni sottoinsieme di {1, 2, ..., N} di dimensione almeno δN contiene una progressione aritmetica di lunghezza k.

Un'altra formulazione utilizza la funzione rk(N), la dimensione del sottoinsieme più grande di {1, 2, ..., N} senza progressione aritmetica di lunghezza k. Il teorema di Szemerédi è equivalente al legame asintotico {stile di visualizzazione r_{K}(N)=o(N)} .

Questo è, rk(N) cresce meno che linearmente con N.

History Van der Waerden's theorem, il precursore del teorema di Szemerédi, è stato provato 1927.

The cases k = 1 and k = 2 of Szemerédi's theorem are trivial. Il caso k = 3, noto come teorema di Roth, è stato stabilito in 1953 di Klaus Roth[2] attraverso un adattamento del metodo del cerchio di Hardy-Littlewood. Endre Szemeredi[3] dimostrato il caso k = 4 attraverso la combinatoria. Utilizzando un approccio simile a quello utilizzato per il caso k = 3, Roth[4] ha dato una seconda prova per questo in 1972.

Il caso generale è stato risolto 1975, anche di Szemeredi,[5] che ha sviluppato un'estensione ingegnosa e complicata del suo precedente argomento combinatorio per k = 4 (chiamato "un capolavoro di ragionamento combinatorio" di Erdős[6]). Oggi si conoscono molte altre prove, le più importanti sono quelle di Hillel Furstenberg[7][8] in 1977, usando la teoria ergodica, e da Timothy Gowers[9] in 2001, utilizzando sia l'analisi di Fourier che la combinatoria. Terence Tao ha chiamato le varie dimostrazioni del teorema di Szemerédi a "Stele di Rosetta" per collegare campi disparati della matematica.[10] Quantitative bounds It is an open problem to determine the exact growth rate of rk(N). I limiti generali più noti sono {displaystyle CNexp a sinistra(-n2^{(n-1)/2}{mq[{n}]{registro n}}+{frac {1}{2n}}log log Nright)leq r_{K}(N)leq {frac {N}{(registro registro N)^{2^{-2^{k+9}}}}},} dove {displaystyle n=lceil log krceil } . Il limite inferiore è dovuto a O'Bryant[11] basandosi sul lavoro di Behrend,[12] Rankin,[13] ed Elkin.[14][15] Il limite superiore è dovuto a Gowers.[9] Per k piccolo, ci sono limiti più stretti rispetto al caso generale. Quando k = 3, Bourgain,[16][17] Brughiera,[18] Lei appartiene a te,[19] e Sanders[20] fornito limiti superiori sempre più piccoli. I migliori limiti attuali sono {stile di visualizzazione N2^{-{mq {8registro n}}}leq r_{3}(N)leq C{frac {(registro registro N)^{4}}{registro n}}N} a causa di O'Bryant[11] e fioritura[21] rispettivamente.

Per k = 4, Verde e Tao[22][23] lo ha dimostrato {stile di visualizzazione r_{4}(N)leq C{frac {N}{(registro 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] con Brendan Nagle, Rodl, e Mathias Schacht,[28] e Terence Tao[29] fornito dimostrazioni combinatorie.

Alexander Leibman e Vitaly Bergelson[30] generalizzato di Szemerédi alle progressioni polinomiali: Se {displaystyle Asubset mathbb {N} } è un insieme con densità superiore positiva e {stile di visualizzazione p_{1}(n),p_{2}(n),punti ,p_{K}(n)} sono polinomi a valori interi tali che {stile di visualizzazione p_{io}(0)=0} , allora sono infiniti {stile di visualizzazione u,nin mathbb {Z} } tale che {stile di visualizzazione u+p_{io}(n)in un} per tutti {stile di visualizzazione 1leq ileq k} . Il risultato di Leibman e Bergelson vale anche in un contesto multidimensionale.

La versione finitaria del teorema di Szemerédi può essere generalizzata a gruppi additivi finiti inclusi spazi vettoriali su campi finiti.[31] L'analogo a campo finito può essere utilizzato come modello per comprendere il teorema nei numeri naturali.[32] Il problema di ottenere i limiti nel caso k=3 del teorema di Szemerédi nello spazio vettoriale {displaystyle mathbb {F} _{3}^{n}} è noto come il problema del set di tappi.

Il teorema di Green-Tao afferma che i numeri primi contengono lunghe progressioni aritmetiche arbitrarie. Non è implicito nel teorema di Szemerédi perché i primi hanno densità 0 nei numeri naturali. Come parte della loro prova, Ben Green e Tao hanno presentato a "parente" Teorema di Szemerédi che si applica ai sottoinsiemi degli interi (anche quelli con 0 densità) soddisfare determinate condizioni di pseudocasuale. Da allora David Conlon ha fornito un teorema di Szemerédi relativo più generale, Giacobbe Volpe, e Yufei Zhao.[33][34] La congettura di Erdős sulle progressioni aritmetiche implicherebbe sia il teorema di Szemerédi che il teorema di Green-Tao.

Vedi anche Problemi che coinvolgono le progressioni aritmetiche Teoria di Ramsey ergodica Combinatoria aritmetica Lemma di regolarità Szemerédi Note ^ Erdős, Paolo; Turano, Paolo (1936). "Su alcune sequenze di interi" (PDF). Giornale della London Mathematical Society. 11 (4): 261–264. doi:10.1112/jlms/s1-11.4.261. SIG 1574918. ^ Roth, Claus Friedrich (1953). "Su determinati insiemi di numeri interi". Giornale della London Mathematical Society. 28 (1): 104–109. doi:10.1112/jlms/s1-28.1.104. SIG 0051853. Zbl 0050.04002. ^ Szemeredi, Modificare (1969). "Su insiemi di interi che non contengono quattro elementi in progressione aritmetica". Giornale matematico dell'Accademia delle scienze ungherese. 20 (1–2): 89–104. doi:10.1007/BF01894569. SIG 0245555. Zbl 0175.04301. ^ Roth, Claus Friedrich (1972). "Irregolarità di successioni relative a progressioni aritmetiche, IV". Periodica Math. ungherese. 2 (1–4): 301–326. doi:10.1007/BF02018670. SIG 0369311. S2CID 126176571. ^ Szemeredi, Modificare (1975). "Su insiemi di interi che non contengono k elementi in progressione aritmetica" (PDF). Diario di aritmetica. 27: 199–245. doi:10.4064/aa-27-1-199-245. SIG 0369312. Zbl 0303.10056. ^ Foresta, Paolo (2013). "Alcuni dei miei problemi e risultati preferiti". In Graham, Ronald L.; Non ha risparmiato, Jaroslav; Maggiordomo, Steve (eds.). La matematica di Paul Erdős I (Seconda ed.). New York: Springer. pp. 51–70. doi:10.1007/978-1-4614-7258-2_3. ISBN 978-1-4614-7257-5. SIG 1425174. ^ Furstenberg, Hillel (1977). "Comportamento ergodico delle misure diagonali e teorema di Szemerédi sulle progressioni aritmetiche". J. d'Analisi matematica. 31: 204–256. doi:10.1007/BF02813304. SIG 0498471. S2CID 120917478.. ^ Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "La dimostrazione teorica ergodica del teorema di Szemerédi". Toro. Amer. Matematica. soc. 7 (3): 527–552. doi:10.1090/S0273-0979-1982-15052-2. SIG 0670131. ^ Salta su: a b Gower, Timoteo (2001). "Una nuova dimostrazione del teorema di Szemerédi". Geom. Funziona. Anale. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. SIG 1844079. S2CID 124324198. ^ Tao, Terence (2007). "La dicotomia tra struttura e casualità, progressioni aritmetiche, e i primi". A Sanz-Sole, Marta; Soria, Javier; Maschio, Juan Luis; verzura, Giovanna (eds.). Atti del Congresso Internazionale dei Matematici Madrid, 22–30 agosto, 2006. Congresso Internazionale dei Matematici. vol. 1. Zurigo: Società matematica europea. pp. 581–608. arXiv:matematica/0512114. doi:10.4171/022-1/22. ISBN 978-3-03719-022-7. SIG 2334204. ^ Salta su: a b O'Bryant, Kevin (2011). "Insiemi di numeri interi che non contengono lunghe progressioni aritmetiche". Giornale elettronico di combinatoria. 18 (1). doi:10.37236/546. SIG 2788676. ^ Behrend, Felix A. (1946). "Sugli insiemi di interi che non contengono tre termini in progressione aritmetica". Atti dell'Accademia Nazionale delle Scienze. 32 (12): 331–332. Bibcode:1946PNAS...32..331B. doi:10.1073/pnas.32.12.331. SIG 0018694. PMC 1078964. PMID 16578230. Zbl 0060.10302. ^ Classifica, Robert A. (1962). "Insiemi di interi contenenti non più di un dato numero di termini in progressione aritmetica". Proc. Roy. soc. Edimburgo Sez. UN. 65: 332–344. SIG 0142526. Zbl 0104.03705. ^ Elkin, Michael (2011). "Una migliore costruzione dei set senza progressione". Israel Journal of Mathematics. 184 (1): 93–128. arXiv:0801.4310. doi:10.1007/s11856-011-0061-1. SIG 2823971. ^ Verde, Ben; Lupo, Giulia (2010). "Una nota sul miglioramento della costruzione di Behrend da parte di Elkin". In Chudnovsky, Davide; Chudnovsky, Gregorio (eds.). Teoria dei numeri additivi. Teoria dei numeri additivi. Festschrift in onore del sessantesimo compleanno di Melvyn B. Nathanson. New York: Springer. pp. 141–144. arXiv:0810.0732. doi:10.1007/978-0-387-68361-4_9. ISBN 978-0-387-37029-3. SIG 2744752. S2CID 10475217. ^ Bourgain, Jean (1999). "Su triple in progressione aritmetica". Geom. Funziona. Anale. 9 (5): 968–984. doi:10.1007/s000390050105. SIG 1726234. S2CID 392820. ^ Bourgain, Jean (2008). "Rivisitazione del teorema di Roth sulle progressioni". J. Anale. Matematica. 104 (1): 155–192. doi:10.1007/s11854-008-0020-x. SIG 2403433. S2CID 16985451. ^ Marrone brughiera, Ruggero (1987). "Insiemi di interi che non contengono progressioni aritmetiche". Giornale della London Mathematical Society. 35 (3): 385–394. doi:10.1112/jlms/s2-35.3.385. SIG 0889362. ^ Szemeredi, Modificare (1990). "Insiemi di interi che non contengono progressioni aritmetiche". Giornale di matematica ungherese. 56 (1–2): 155–158. doi:10.1007/BF01903717. SIG 1100788. ^ Levigatrici, Tom (2011). "Sul teorema di Roth sulle progressioni". Annali di matematica. 174 (1): 619–636. arXiv:1011.0104. doi:10.4007/annali.2011.174.1.20. SIG 2811612. S2CID 53331882. ^ Fioritura, Tommaso F. (2016). "Un miglioramento quantitativo per il teorema di Roth sulle progressioni aritmetiche". Giornale della London Mathematical Society. Seconda serie. 93 (3): 643–663. arXiv:1405.5800. doi:10.1112/jlms/jdw010. SIG 3509957. S2CID 27536138. ^ Verde, Ben; Tao, Terence (2009). "Nuovi limiti per il teorema di Szemeredi. II. Un nuovo limite per r4(N)". In Chen, William W. l.; Gower, Timoteo; Alabarsta, Ciao; Schmidt, Wolfgang; Vaughan, Roberto Carlo (eds.). Nuovi limiti per il teorema di Szemeredi, II: Un nuovo limite per r_4(N). Teoria analitica dei numeri. Saggi in onore di Klaus Roth in occasione del suo 80° compleanno. Cambridge: Cambridge University Press. pp. 180–204. arXiv:matematica/0610604. Bibcode:2006matematica.....10604G. ISBN 978-0-521-51538-2. SIG 2508645. Zbl 1158.11007. ^ Verde, Ben; Tao, Terence (2017). "Nuovi limiti per il teorema di Szemerédi, III: Un limite polilogaritmico per r4(N)". Matematica. 63 (3): 944–1040. arXiv:1705.01703. doi:10.1112/S0025579317000316. SIG 3731312. ^ Furstenberg, Hillel; Katznelson, Yitzhak (1978). "Un teorema ergodico di Szemerédi per le trasformazioni del pendolarismo". Giornale di analisi matematica. 38 (1): 275–291. doi:10.1007/BF02790016. SIG 0531279. S2CID 123386017. ^ Governatori, Timoteo (2007). "Regolarità dell'ipergrafo e teorema multidimensionale di Szemerédi". Annali di matematica. 166 (3): 897–946. arXiv:0710.3032. doi:10.4007/annali.2007.166.897. SIG 2373376. S2CID 56118006. ^ Rodl, Vojtčch; Maglione, Joseph (2004). "Lemma di regolarità per ipergrafi k-uniformi". Algoritmi di strutture casuali. 25 (1): 1–42. doi:10.1002/rsa.20017. SIG 2069663. ^ Rodl, Vojtčch; Maglione, Joseph (2006). "Applicazioni del lemma di regolarità per ipergrafi uniformi" (PDF). Algoritmi di strutture casuali. 28 (2): 180–194. doi:10.1002/rsa.20108. SIG 2198496. ^ Nagle, Brendano; Rodl, Vojtčch; Schacht, Mattia (2006). "Il lemma del conteggio per i normali ipergrafi k-uniformi". Algoritmi di strutture casuali. 28 (2): 113–179. doi:10.1002/rsa.20117. SIG 2198495. ^ Tao, Terence (2006). "Una variante del lemma di rimozione dell'ipergrafo". Rivista di teoria combinatoria, Serie A. 113 (7): 1257–1280. arXiv:matematica/0503572. doi:10.1016/j.jcta.2005.11.006. SIG 2259060. ^ Bergelson, Vitale; Leibman, Alessandro (1996). "Estensioni polinomiali dei teoremi di van der Waerden e Szemerédi". Giornale della Società matematica americana. 9 (3): 725–753. doi:10.1090/S0894-0347-96-00194-4. SIG 1325795. ^ Furstenberg, Hillel; Katznelson, Yitzhak (1991). "Una versione della densità del teorema di Hales-Jewett". Giornale di analisi matematica. 57 (1): 64–119. doi:10.1007/BF03041066. SIG 1191743. S2CID 123036744. ^ Lupo, Giulia (2015). "Modelli a campi finiti in combinatoria aritmetica: dieci anni dopo". Campi finiti e loro applicazioni. 32: 233–274. doi:10.1016/j.ffa.2014.11.003. SIG 3293412. ^ Conlon, Davide; Volpe, Giacobbe; Zhao, Yufei (2015). "Il teorema relativo di Szemerédi". Analisi geometrica e funzionale. 25 (3): 733–762. arXiv:1305.5440. doi:10.1007/s00039-015-0324-9. SIG 3361771. S2CID 14398869. ^ Zhao, Yufei (2014). "Una dimostrazione di transfert aritmetico di un teorema di Szemerédi relativo". Atti matematici della Cambridge Philosophical Society. 156 (2): 255–261. arXiv:1307.4959. Bibcode:2014MPCPS.156..255Z. doi:10.1017/S0305004113000662. SIG 3177868. S2CID 119673319. Ulteriori letture Tao, Terence (2007). "L'approccio ergodico e combinatorio al teorema di Szemerédi". A Granville, Andrea; Nathanson, Melvin B.; Solimosi, Joseph (eds.). Combinatoria additiva. CRM Proceedings & Lecture Notes. vol. 43. Provvidenza, RI: Società matematica americana. pp. 145–193. arXiv:matematica/0604456. Bibcode:2006matematica......4456T. ISBN 978-0-8218-4351-2. SIG 2359471. Zbl 1159.11005. Collegamenti esterni Fonte PlanetMath per la versione iniziale di questa pagina Annuncio di Ben Green e Terence Tao – il preprint è disponibile su math.NT/0404188 Discussione del teorema di Szemerédi (parte 1 di 5) Ben Green e Terence Tao: Il teorema di Szemerédi su Scholarpedia Weisstein, Eric W. "Teorema di Szemeredis". Math World. Sporcizia, Giacomo; Hodge, Davide (2012). "6,000,000: Endre Szemerédi vince il Premio Abel". Numerofilo. Brady Haran. Categorie: Combinatoria additiva Teoria di Ramsey Teoremi della combinatoria Teoremi della teoria dei numeri