Szemeredis sats

Szemeredi-satsen (tidigare känd som Erdős-Turan-förmodan [1] ) är ett påstående inom kombinatorisk talteorin om förekomsten av långa aritmetiska progressioner i täta mängder.

Det är ett klassiskt exempel på ett teorem inom additiv kombinatorik . Vissa metoder för dess bevis användes i beviset för Green-Tao-satsen [2] .

Formulering

Den ursprungliga formuleringen av satsen innehöll endast ett villkor om densiteten av mängden som helhet.

I varje oändlig uppsättning av positiv asymptotisk densitet finns en progression av vilken längd som helst . [3] $A\subset {\mathbb {N} }$ $D(A)>0$ $k$

Det finns en slutlig version som motsvarar den som ges ovan [4] .

För vilken som helst och tillräckligt stor, innehåller varje uppsättning storlek en aritmetisk längdförlopp . $\delta>0$ $N > N(k, \delta)$ $A\subset \{1,\dots ,N\}$ $|A|\geqslant \delta N$ $k$

Den sista varianten är viktig i samband med möjligheten att formulera kvantitativa resultat på sambandet mellan och . Han visar att i den första (oändliga) varianten är gränsen bortom vilken närvaron av progressioner blir oundviklig inte själva täthetsvärdet, utan någon distributionslag. Den exakta beskrivningen av denna gräns är okänd från och med 2019. $\delta$ $N$

Den slutliga versionen av satsen förblir ekvivalent om vi betraktar och följaktligen progressioner i ringen av rester modulo . Detta tillvägagångssätt öppnar vägen för ett bevis med trigonometriska summor . $A\subset \mathbb {Z} _{N}$ $N$

För eller påståendet om satsen är trivialt. Ett specialfall kallas Roths teorem . Dess bevis är mycket enklare än för det allmänna fallet och presenteras ofta separat i litteraturen. Dessutom är mycket bättre uppskattningar av kritiska värden kända för Roths teorem jämfört med allmänna , inklusive för generaliseringar till olika grupper . $k=1$ $k=2$ $k = 3$ $\delta$

Historik

Påståendet om satsen formulerades först som en gissning av Erdős och Turan [5] 1936.

Fallet bevisades 1953 av Klaus Roth [6] genom att anpassa Hardy-Littlewood cirkulär metod . $k = 3$

Fallet bevisades 1969 av Endre Semeredi [7] med en kombinatorisk metod liknande den som användes för att bevisa fallet . Roth [8] gav ett andra bevis för samma fall 1972. $k = 4$ $k = 3$

Det allmänna fallet för alla bevisades också 1975 av Szemeredi [9] , med hjälp av uppfinningsrika och komplexa kombinatoriska argument. Grunden för hans bevis är det så kallade regularitetslemma , som beskriver strukturen hos godtyckliga grafer i termer av pseudo-slumpmässighet. $k$

Senare hittades andra bevis för satsen, bland dem de viktigaste är beviset för Furstenberg ( tyska: Hillel Fürstenberg ) [10] 1977, med hjälp av ergodisk teori , och beviset för Gowers [11] 2001, med användning av harmonisk analys och kombinatorik .

Betyg

På tal om kvantitativa uppskattningar för Szemeredi-satsen menar man vanligtvis storleken på den största delmängden av intervallet [12] som inte innehåller progressioner av en given längd: $\{1,\dots ,N\}$

a_{k}(N)=\max {\big \{}|A|:A\subset \{1,\dots ,N\},\ \nfinns a,d:\{a,a+ d ,\dots ,a+(k-1)d\}\delmängd A{\big \}}.

För att härleda de övre gränserna på krävs alltså generella bevis, och för att bevisa de nedre gränserna (det vill säga för att motbevisa motsvarande övre gränser) räcker det att presentera konstruktionen av ett motexempel. $a_{k}(N)$

Övre gränser

Det första allmänna beviset för Szémerédys teorem, på grund av användningen av regelbundenhetslemma, gav mycket dåliga uppskattningar för beroendet uttryckt i termer av exponentialtorn . $\delta =\delta (N)$

Kvantitativa uppskattningar som liknar motsvarande uppskattningar för Roths teorem erhölls av Gowers 2001 [11] :

$a_{k}(N)\ll {\frac {N}{(\log N)^{c_{k))))$ , var $c_{k}=2^{-2^{k+9)).$

För ett fall finns det mycket bättre uppskattningar av , erhållna med fallspecifika metoder. [13] $k = 3$

Nedre gränser

När det gäller den största (från och med 2019) uppsättningskonstruktion utan progressioner är Behrends konstruktion . Det ger uppsättningar av storlek . $k = 3$ $\exp {\Big (}{-}O{\big (}(\log N)^{1/2}{\big )}{\Big )}N$

Rankin generaliserade denna konstruktion till godtyckliga konstruktioner 1961 och konstruerade en uppsättning storlek utan längdförlopp . [fjorton] $k$ $\exp \left({-}O\left((\log N)^{\frac {1}{k-1}}\right)\right)N$ $k$

Kort beskrivning av designen

Behrends konstruktion associerar ett tal med en punkt i ett flerdimensionellt utrymme, vars koordinater motsvarar siffrorna i talet i något talsystem. Mängden är sammansatt av punkter som i denna mening motsvarar punkterna i någon sfär. Den strikta konvexiteten hos sfären garanterar frånvaron av tre punkter på en rak linje, och därmed frånvaron av trevariga progressioner.

Rankins idé är att upprepa detta trick. Till exempel tas punkter (och deras bilder i talsystemet) inte från en sfär, utan från alla sfärer, vars kvadrater tillhör den mängd som bildas enligt typen av Behrend-mängden (konstruktion för ). För - från sfärer vars kvadrater med radier hör till uppsättningen punkter från föregående mening, etc. $k = 4$ $k = 3$ $k = 5$

Samtidigt väljs basen för talsystemet och restriktioner för värdet av siffrorna vid varje iteration på ett speciellt sätt så att det är möjligt att bevisa lemmat om antalet lösningar till ekvationen under sådana förhållanden, därför Faktum är att uppsättningarna av punkter som uppstår i mellanstadierna av konstruktionen inte är optimala i storlek för mindre värden på . $x_{1}^{2}+\dots +x_{k}^{2}=N$ $k$

Samband med andra teorem

Szemeredys sats är en direkt generalisering av van der Waerdens sats , eftersom när man delar upp de naturliga talen i ett ändligt antal klasser kommer åtminstone en av dem att ha en positiv täthet.

Från någorlunda goda övre gränser för kritiska densitetsvärden i Szémeredys teorem kan Erdős gissningar om aritmetiska progressioner följa . [femton]

Se även

Litteratur

Rue, Juanjo. Konsten att räkna. Kombinatorik och uppräkning. - M. : De Agostini, 2014. - S. 123-132. — 144 sid. — (Matematikens värld: i 45 band, band 34). - ISBN 978-5-9774-0729-8 .
Tao, Terence De ergodiska och kombinatoriska förhållningssätten till Szemerédis teorem // Additive Combinatorics (neopr.) / Granville, Andrew; Nathanson, Melvyn B.; Solymosi, Jozsef. - American Mathematical Society , 2007. - V. 43. - S. 145-193. — (CRM Proceedings & Lecture Notes). - ISBN 978-0-8218-4351-2 .
I. D. Shkredov. Szemeredis sats och problem om aritmetiska progressioner // Advances in Mathematical Sciences . - Ryska vetenskapsakademin , 2006. - Utgåva. 6 . - S. 111-179 . (ryska)

Anteckningar

↑ Det finns också en annan hypotes uppkallad efter dessa vetenskapsmän - Erdős-Turan-förmodan om additivbaser .
↑ Shkredov, 2006 , sid. 159-165.
↑ Förekomsten av oändliga aritmetiska progressioner följer inte av satsen, och ett sådant påstående skulle verkligen vara falskt. Till exempel är ett motexempel den uppsättning siffror som innehåller ett i den första siffran i decimalnotationen. $A$
↑ Shkredov, 2006 , sid. 113.
↑ Erdős, Paul & Turán, Paul (1936), On some sequences of integers , Journal of the London Mathematical Society vol 11 (4): 261–264, doi : 10.1112/jlms/s1-11.4.261 , < http: //www.renyi.hu/~p_erdos/1936-05.pdf > Arkiverad 23 juli 2020 på Wayback Machine .
↑ Roth, Klaus Friedrich (1953), On certain sets of integers, I , Journal of the London Mathematical Society vol. 28: 104–109, Zbl 0050.04002, MR : 0051853 , DOI 10.1112/jlms/s1-1048 .
↑ Szemerédi, Endre (1969), Om uppsättningar av heltal som inte innehåller fyra element i aritmetisk progression , Acta Math. Acad. sci. hängde. T. 20: 89–104, Zbl 0175.04301, MR : 0245555 , DOI 10.1007/BF01894569
↑ Roth, Klaus Friedrich (1972), Oregelbundenheter i sekvenser i förhållande till aritmetiska progressioner, IV , Periodica Math. hungar. T. 2: 301–326, MR : 0369311 , DOI 10.1007/BF02018670 .
↑ Szemerédi, Endre (1975), Om uppsättningar av heltal som inte innehåller några k element i aritmetisk progression , Acta Arithmetica T. 27: 199–245, Zbl 0303.10056, MR : 0369312 , < pl/ m.edun . ksiazki/aa/aa27/aa27132.pdf > Arkiverad 10 december 2020 på Wayback Machine .
↑ Furstenberg, Hillel (1977), Ergodic behavior of diagonal measurements and a theorem of Szemerédi on aritmetic progressions , J. D'Analyse Math. T. 31: 204-256, MR : 0498471 , DOI 10.1007/BF02813304 .
↑ 1 2 Gowers, Timothy (2001), Ett nytt bevis på Szemerédis teorem , Geom. Funktion. Anal. T. 11(3): 465–588, MR : 1844079 , doi : 10.1007/s00039-001-0332-9 , < http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi > Arkiverad kopia daterad 26 september 2020 på Wayback Machine .
↑ Eller en cyklisk grupp , som är densamma upp till en konstant. $\mathbb {Z} _{N}$
↑ En kvantitativ förbättring av Roths teorem om aritmetiska progressioner, Journal of the London Mathematical Society vol 93 (3): 643-663, 2016 .
↑ Rankin, Robert A. (1962), Uppsättningar av heltal som inte innehåller mer än ett givet antal termer i aritmetisk progression, Proc. Roy. soc. Edinburgh Sect. A T. 65: 332-344, Zbl 0104.03705, MR : 0142526 .
↑ Shkredov, 2006 , sid. 139-140.

Länkar

Tillkännagivande av Ben Green och Terence Tao — förtrycket finns tillgängligt på math.NT/0404188
Diskussion av Szemeredis teorem (del 1 av 5)
Ben Green och Terence Tao: Szemeredis teorem om Scholarpedia
Weisstein, Eric W. SzemeredisTheorem (engelska) på Wolfram MathWorld- webbplatsen .

Ordböcker och uppslagsverk	Britannica (online)