Roths teorem

Roths teorem är ett resultat av additiv kombinatorik , ett specialfall av Szemeredis sats för progressioner av längd 3; hävdar närvaron av aritmetiska progressioner i alla tillräckligt täta uppsättningar. $(a,a+d,a+2d),\ d\not =0$

Den exakta formuleringen är: för alla , alla uppsättningar som har en asymptotisk densitet innehåller en aritmetisk progression av längd 3. $\delta \in (0;1)$ $A\subset {\mathbb {N} }$ $d(A)>\delta$

Liknande formuleringar som använder de övre och nedre asymptotiska tätheterna är ekvivalenta med [1] .

Formuleringen för finita mängder är också likvärdig med den ursprungliga: för alla finns det sådana att om , och , innehåller sedan en aritmetisk progression av längd 3. Den överväldigande majoriteten av bevis bevisar formuleringen för finita mängder. $\delta \in (0;1)$ $N_{0}=N_{0}(\delta )$ $N>N_{0}$ $A\subset \left\lbrace {1,2,\dots ,N}\right\rbrace$ $|A|>\delta N$ $A$

Historik om förbättrade poäng

Maximal delmängdsstorlek $\{1,\dots ,N\}$ utan progressioner av längd 3
Utgivningsår	Storlek (upp till en konstant)	Författarna)
1953	${\frac {N}{\log \log N))$	Mun [2]
1987	${\frac {N}{(\log N)^{c}}},\ c>0$	Heath-Brown [3] [4]
1999	${\displaystyle {\frac {N(\log \log N)^{1/2}}{(\log N)^{1/2))))$	Bourgain [5]
2008	${\displaystyle {\frac {N(\log \log N)^{2}}{(\log N)^{2/3))))$	Bourgain [6]
2012	${\displaystyle {\frac {N}{(\log N)^{3/4-o(1)))))$	Sanders [7]
2011	${\frac {(\log \log N)^{5}}{\log N}}N$	Sanders [8]
2014	${\frac {(\log \log N)^{4}}{\log N}}N$	Bloom [9]
2020 (förtryck)	${\frac {(\log \log N)^{3}(\log \log \log N)^{5}}{\log N}}N$	Shoen [10]
2020 (förtryck)	${\frac {N}{(\log N)^{1+c))},\ c>0$	Bloom, Sisask [11]

Olika bevis

Övertonsanalys

Teoremet bevisades första gången 1953 av Klaus Roth [2] [12] genom att anpassa Hardy-Littlewood-cirkelmetoden. Beviset använde idén [13] , som sedan generaliserades för det allmänna beviset för Szémeredis sats: alla uppsättningar av en given densitet är uppdelade i två grupper - "uniform" och "icke-uniform", och "likformighet" betyder en övre bunden på Fourierkoefficienterna . Om mängden är enhetlig kan närvaron av progressioner i den bevisas direkt, annars är det möjligt att bevisa förekomsten av en subprogression där mängdens täthet är större än i segmentet av den naturliga serie som den tillhör .

Metoden låter dig härleda en uppskattning . De tekniska detaljerna i beviset, gränsen på Fourier-koefficienterna som definierar "likformighet" och de resulterande konstanterna kan skilja sig från källa till källa. ${\displaystyle N_{0}(\delta )\leqslant e^{e^{\frac {c}{\delta ))))$

Kombinatoriskt (via Szemeredis lemma)

Beviset för Roths teorem kan härledas [14] som ett specialfall av Szemeredys teorem från Szemeredys bevis. Detta sätt att bevisa kräver användning av Szémerédys regularitetslemma och hörnsatsen , varifrån Roths sats följer direkt. Det är till och med möjligt [15] att avstå från användningen av hörnsatsen, och härleda Roths sats direkt från triangelborttagningslemma , men bara i formuleringen för ändliga cykliska grupper (se avsnittet "Generaliseringar till olika grupper").

Eftersom Szemeredis regelbundenhetslemma ger extremt stora övre gränser för värdet som erhålls genom det (åtminstone, torn av exponenter ), tillåter metoden i sig inte att erhålla bättre gränser än dessa.

Elementär (genom generaliserade aritmetiska progressioner)

Ronald Graham ger i sin bok om Ramsey-teorin en förenklad version av beviset, även det baserat på Szemeredi-metoden, men utan att använda regularitetslemma. Beviset använder generaliserade aritmetiska progressioner av formen , vilket är mycket lättare att bevisa närvaron av i mängden, och från detta är själva Roth-satsen redan härledd. $a+\sum \limits _{k=1}^{n}{\epsilon _{k}x_{k}}\ (\epsilon _{i}\in \left\lbrace {0,1}\ höger\rbrace )$

Grahams bevis ger inte uppskattningar för , utan visar bara existensen, eftersom det använder existensen av en punkt i sekvensen, från vilken alla punkter är tillräckligt nära gränsen , men bara existensen är också bevisad för gränsen, och karaktären av konvergens analyseras i princip inte. $N$

Motexempel för icke-täta uppsättningar

Tillsammans med att hitta övre gränser för storleken på en mängd utan aritmetiska progressioner, finns det också ett omvänt problem – att konstruera den största möjliga mängden som inte innehåller aritmetiska progressioner, det vill säga ett motexempel för att beteckna gränserna för förbättring av uppskattningar på . Alla kända konstruktioner av sådana uppsättningar är baserade på idén om att överväga enskilda siffror av siffror i ett visst talsystem och ställa in villkor för värdena för dessa siffror. $A\subset \left\lbrace {1,\dots ,N}\right\rbrace$ $A$ $N_{0}(\delta )$

Erdős, Turan (1936)

Det första exemplet på en uppsättning utan progressioner gavs 1936 av Erdős och Turan, som föreslog att man skulle överväga siffror som i det ternära systemet endast innehåller siffrorna 0 och 2. En sådan uppsättning innehåller bara siffror, vilket är mycket litet jämfört med det övre gräns. [16] $N^{\log _{3}{2))$

Bevis på konstruktionens riktighet

Låt --- Erdős--Turan ställa in. $A$

Om och , då i det ternära systemet i den mest signifikanta siffran , där dessa siffror är olika, är likheter uppfyllda . Därför, i en aritmetisk progression , skulle vara uppfylld , och därmed, . $a,b\in A$ $a<b$ $i$ $a_{i}=0,\ b_{i}=2$ $a<c<b$ $c_{i}=1$ $c\not \in A$

Salem, Spencer (1942)

Salem och Spencer generaliserade 1942 idén om Erdős och Turan till nummersystem med en växande (beroende på uppsättningens storlek) bas och fick en uppsättning utan storleksförlopp . [17] $\exp \left({-O\left({\frac {\log N}{\log \log N))\right)}\right)N$

Kort beskrivning av designen

I Erdős-Turan-konstruktionen är det fullt möjligt att tillåta siffrorna 0 och 1 istället för 0 och 2 (då kommer platsen för mittentalet i progressionen att ta en större plats i korrekthetsbeviset). I analogi med detta ansåg Salem och Spencer i det -ary-systemet siffror som endast innehåller siffror från 0 till , och lika många förekomster av varje siffra (med asymptotik kan det betraktas som udda, och det totala antalet siffror --- dividera ). $d$ ${\frac {d-1}{2))$ $d$ ${\frac {d-1}{2))$

Förekomsten av progressioner blockeras av villkoret om förekomsten av enskilda siffror. Faktum är att om bäraren inte används under addition kan alla nollor i (och därmed i ) bara bildas genom att lägga till nollor från motsvarande siffror och . Vidare, genom induktion, kan vi bevisa sammanträffandet av positionerna för alla ettor, tvåor, etc. och komma till slutsatsen att . $a+c=2b$ $2b$ $b$ $a$ $c$ $a,b,c$ $a=b=c$

Den angivna poängen erhålls genom att överväga . ${\displaystyle d\asymp {\frac {\log N}{(\log \log N)^{2))))$

Berend (1946)

År 1946 lade Behrend till en geometrisk tolkning genom att associera siffrorna i siffrorna med koordinaterna för punkter i ett flerdimensionellt utrymme och överväga siffrorna som i denna mening motsvarar punkterna i en sfär . Detta gjorde det möjligt att konstruera en progressionsfri uppsättning storlek . [arton] $\exp \left({-O\left({\sqrt {\log N}}\right)}\right)N$

Kort beskrivning av designen

Alla tal med siffror som inte är större än -är representation delas in i grupper med samma värden . Den största av dessa grupper väljs som en uppsättning och dess storlek uppskattas enligt Dirichlet-principen . ${\displaystyle x<(2m+1)^{n))$ $m$ $(2m+1)$ ${\displaystyle x=x_{1}x_{2}\dots x_{n))$ $\sum \limits _{i=1}^{n}{x_{i}^{2))$

På grund av de begränsade siffrorna, när sådana siffror läggs till, sker ingen överföring av siffror , så progressioner av längd 3 har också en geometrisk tolkning (som punkter på samma linje). Men eftersom bollen är en strikt konvex kropp , kan sfären, som dess gräns, inte innehålla tre punkter på en rak linje. Av detta följer att det inte finns några progressioner i den valda uppsättningen.

Uppsättningens storlek uppskattas bäst till $n\asymp {\sqrt {\log N))$

Därefter ökades Behrends uppskattning med en logaritmisk faktor genom en liten förfining av metoden [19] , men det finns inga signifikant bättre resultat från och med 2019.

Eftersom övre gränser av liknande typ är kända för vissa generaliseringar av Roths teorem [20] [21] finns det skäl att tro att Behrends gräns är skarp.

Variationer och generaliseringar för olika grupper

För ändliga cykliska grupper

Både beviset genom harmonisk analys och det speciella sättet på vilket Szemeredis lemma tillämpas bevisar inte själva satsen, utan dess "cykliska" version.

För alla finns det sådana att if , och , då innehåller trippeln , där addition förstås som modulo addition $\delta \in (0;1)$ $N_{0}=N_{0}(\delta )$ $N>N_{0}$ $A\subset \mathbb {Z} _{N}$ $|A|>\delta N$ $A$ $(a,a+d,a+2d),\ d\not =0$

De progressioner som utlovas av denna formulering kan vara progressioner i men inte i (till exempel ). Men Roths teorem följer uppenbarligen av det om vi betraktar mängden som en uppsättning rester i . Detta ändrar endast densiteten med en konstant, men gör alla progressioner lämpliga för . Därför är detta teorem ekvivalent med Roths huvudsats. ${\mathbb {Z} }_{N}$ ${\mathbb {N} }$ $(N-2,N-1,0)$ $\left\lbrace {N+a:a\in A}\right\rbrace$ $\mathbb {Z} _{3N}$ ${\mathbb {N} }$

För grupper med liten fast vridning

Följande sats, som till sin idé liknar Roths sats, följer inte av den och antyder den inte, men är av intresse för en separat studie.

Låt några fixas . Sedan för någon det finns sådan att om , då $q\geq 3$ $\delta \in (0;1)$ $n_{0}=n_{0}(\delta ,q)$ ${\displaystyle n>n_{0},\ A\subset {\mathbb {F} }_{q}^{n},\ |A|>\delta q^{n))$ $\exists a,d(d\not =(0,\dots ,0)):a,a+d,a+2d\in A$

Övre gränser

Teoremet för grupper bevisades först av Brown och Bahler 1982 [22] , men de bevisade bara att för mängder utan aritmetiska progressioner förblev , men mer exakta begränsningar på en öppen fråga. ${\mathbb {F} }_{p}^{n}$ $|A|=o(q^{n})$ $|A|$

1993 (publicerad 1995) bevisade Roy Meshulam [23] att . Hans bevis betraktade godtyckliga grupper och deras karaktärer . Det finns också mer förenklade [24] versioner av detta bevis, uteslutande för , som, med hjälp av Fourier-koefficienterna i , direkt generaliserar idéer från det analytiska beviset för Roths teorem. Beviset är tekniskt sett ännu enklare än beviset för Roths sats själv, så [24] [25] ges ofta som det första exemplet på att tillämpa metoden. $|A|\leq 2{\frac {q^{n}}{n}}$ ${\mathbb {F} }_{p}^{n}$ ${\mathbb {F} }_{p}^{n}$

2012, Bateman och Katz, med tanke på fallet , bevisade [26] existensen av en absolut konstant , så att utan aritmetiska progressioner, . $q=3$ $\epsilon > 0$ $C$ ${\displaystyle A\subset {\mathbb {F} }_{3}^{n))$ $|A|\leq {\frac {3^{n}}{n^{1+\epsilon }}}$

Under 2016 bevisade Krut, Lev och Pach [27] för fallet att för set utan progressioner. Ellenberg och Gijswijt, generaliserande metoden för Krut, Löw och Pach, med hjälp av polynomalgebra , bevisade [28] [29] existensen för var och en av en helt enkelt konstant sådan att om den inte innehåller progressioner av längd 3. I deras artikel , . I synnerhet för fallet . Under antagandet följer det från optimeringen av funktionen att , där är en absolut konstant, vilket är lösningen av ekvationen , det vill säga , där $q=4$ ${\displaystyle |A|\leq {3.62}^{n))$ ${\displaystyle A\subset {\mathbb {F} }_{4}^{n))$ $q\geq 3$ $c=c(q)<q$ $|A|=O(c^{n})$ ${\displaystyle A\subset {\mathbb {F} }_{q}^{n))$ $c(q)={\frac {q}{exp({\sup \limits _{\theta }\left\lbrace ({\frac {q-1}{3))\theta +\ln { \frac {e^{q\theta}-1}{q(e^{\theta}-1)}}}\right\rbrace })}}$ $q=3$ $|A|=o(2.756^{n})$ $\theta ={\frac {c_{0}}{q}}$ ${\frac {c}{3}}-\ln {\frac {e^{c}-1}{c}}$ $c(q)\sim {\frac {e^{c_{0}}-1}{c_{0}e^{(c_{0}/3)))}q$ $c_{0}$ $2ce^{c}-3e^{c}+c+3=0$ $c(q)\sim c_{1}q$ $c_{1}\approx 0,841434...$

Nedre gränser

Det bästa [28] från 2016 konstruktion-motexempel tillåter [30] att konstruera uppsättningar av storlek för grupper av formen som inte innehåller aritmetiska progressioner av längd 3. ${\displaystyle {\mathbb {F} }_{3}^{n))$ $\Omega (2.2^{n})$

För godtyckliga grupper

Meshulam överväger [23] Roths teorem för en godtycklig grupp och härleder en uppskattning för en mängd utan aritmetiska progressioner av längd 3. $G={\mathbb {Z} }_{k_{1}}\oplus \dots \oplus {\mathbb {Z} }_{k_{n}}$ $|A|<2{\frac {|G|}{n))$

Detta innebär att det finns en absolut konstant så att för en uppsättning utan progressioner, $\beta>0$ $A\subset G$ ${\displaystyle |A|<{\frac {|G|}{(\log {|G|})^{\beta ))))$

Tvådimensionell generalisering

Den klassiska generaliseringen av Roths sats för tvådimensionella mängder är hörnsatsen . Även om det inte nämns något om aritmetiska progressioner (i tvådimensionell mening), följer Roths sats av den. $A\subset \left\lbrace {1,\dots ,N}\right\rbrace \times \left\lbrace {1,\dots ,N}\right\rbrace$

Se även

Van der Waerdens sats

Litteratur

KF Roth. Om vissa uppsättningar av heltal // Journal of the London Mathematical Society. - 1953. - S. 104-109 . - doi : 10.1112/jlms/s1-28.1.104 .
DR Heath-Brown. Heltalsuppsättningar som inte innehåller några aritmetiska progressioner (engelska) // Journal of the London Mathematical Society. - 1987. - Vol. s2-35 , iss. 3 . - s. 385-394 . - doi : 10.1112/jlms/s2-35.3.385 .
E. Szemeredi. Heltalsmängder som inte innehåller några aritmetiska progressioner // Acta Mathematica Hungarica. - 1990. - Vol. 56 . - S. 155-159 . - doi : 10.1007/BF01903717 .
J. Bourgain. Om tripplar i aritmetisk progression (engelska) // Geometric & Functional Analysis GAFA. - 1999. - Vol. 9 . - P. 968-984 . - doi : 10.1007/s000390050105 .
J. Bourgain. Roths teorem om progressioner återbesökt // Journal d'Analyse Mathématique. - 2008. - Vol. 104 . - S. 155-192 . - doi : 10.1007/s11854-008-0020-x .
T. Sanders. På vissa andra uppsättningar av heltal // Journal d'Analyse Mathématique. - 2012. - Vol. 116 . - S. 53-82 . - doi : 10.1007/s11854-012-0003-9 . - arXiv : 1007.5444 .
T. Sanders. Om Roths sats om progressioner // Annals of Mathematics. - 2011. - Vol. 174 . - s. 619-636 . - doi : 10.4007/annals.2011.174.1.20 . - arXiv : 1011.0104 .
TF Bloom. En kvantitativ förbättring av Roths teorem om aritmetiska progressioner (engelska) // Journal of the London Mathematical Society. - 2014. - Vol. 93 , iss. 3 . - s. 643-663 . doi : 10.1112 / jlms/jdw010 . - arXiv : 1405.5800 .
T. Schoen. Förbättrad bunden i Roths sats om aritmetiska progressioner . - 2020. - arXiv : 2005.01145 .
T. F. Bloom, O. Sisask. Att bryta den logaritmiska barriären i Roths sats om aritmetiska progressioner . - 2020. - arXiv : 2007.03528 .

Anteckningar

↑ I. D. Shkredov, "Szemeredis teorem och problem om aritmetiska progressioner", Uspekhi Mat. Nauk, 61:6(372) (2006), 111-178; rysk matte. Surveys, 61:6 (2006), 1101-1166 . Hämtad 23 december 2017. Arkiverad från originalet 24 december 2017. (obestämd)
↑ 12 Roth , 1953 .
↑ Heath-Brown, 1987 .
↑ Szemerédi, 1990 .
↑ Bourgain, 1999 .
↑ Bourgain, 2008 .
↑ Sanders, 2012 .
↑ Sanders, 2011 .
↑ Bloom, 2014 .
↑ Schoen, 2020 .
↑ Bloom, Sisask, 2020 .
↑ Roths bevis som presenterats av Harold Helfgott på ryska (otillgänglig länk) . Hämtad 23 december 2017. Arkiverad från originalet 24 december 2017. (obestämd)
↑ Postnauka, Ilya Shkredov - Semeredis sats
↑ Chebyshev Laboratory, föreläsningskurs "Additiv kombinatorik", föreläsning 3
↑ En minikurs om additiv kombinatorik Arkiverad 29 augusti 2017 på Wayback Machine , sid. 6
↑ P. Erdős, P. Turán, "Om några sekvenser av heltal", Journal of the London Mathematical Society (juni 1936) . Hämtad 23 december 2019. Arkiverad från originalet 23 december 2019. (obestämd)
↑ R. Salem, DC Spencer, Proc. Natl. Acad. sci. USA 28 (1942), 561-563 . Hämtad 23 december 2017. Arkiverad från originalet 3 juni 2018. (obestämd)
↑ FA Behrend, "Om uppsättningar av heltal som inte innehåller tre termer i aritmetisk progression", Proc. Natl. Acad. sci. USA 32 (1946), 331-332. . Hämtad 23 december 2017. Arkiverad från originalet 4 juni 2018. (obestämd)
↑ Michael Elkin, "En förbättrad konstruktion av progressionsfria uppsättningar", Israel Journal of Mathematics, 184:93 (augusti 2011) . Hämtad 23 december 2019. Arkiverad från originalet 27 november 2018. (obestämd)
↑ T. Schoen, ID Shkredov, "Roth's theorem in many variables", Israel Journal of Mathematics, volym 199, sidorna 287-308 (2014) Arkiverad 23 december 2019 på Wayback Machine ( arXiv:1106.1601 Arkiverad 20193 december 2019 Maskin )
↑ T. Schoen, O. Sisask, "Roth's theorem for four variables and additive structures in sums of sparse sets", Forum of Mathematics Forum of Mathematics, Sigma, 4, E5. doi:10.1017/fms.2016.2 Arkiverad 1 maj 2020 på Wayback Machine ( arXiv:1408.2568 Arkiverad 23 december 2019 på Wayback Machine )
↑ TC Brown och JP Buhler, A density version of a geometric Ramsey theorem, Journal of Combinatorial Theory, Series A 32 (1982), nr. 1, 20-34. . Hämtad 23 december 2017. Arkiverad från originalet 9 augusti 2017. (obestämd)
↑ 1 2 R. Meshulam, Om delmängder av finita abelska grupper utan 3-terms aritmetiska progressioner, Journal of Combinatorial Theory, Series A 71 (1995), nr. 1, 168-172. (inte tillgänglig länk)
↑ 1 2 En minikurs om additiv kombinatorik Arkiverad 29 augusti 2017 på Wayback Machine , sid. 39-42
↑ Chebyshev Laboratory, Ilya Shkredov, Analytiska metoder i additiv kombinatorik, översiktsföreläsning
↑ M. Bateman och N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), nr. 2, 585-613. . Hämtad 23 december 2017. Arkiverad från originalet 9 januari 2018. (obestämd)
↑ E. Croot, V. Lev och PP Pach, Progressionsfria uppsättningar i Z_n^4 är exponentiellt små (2016). arXiv förtryck 1605.01506. . Hämtad 23 december 2017. Arkiverad från originalet 12 juni 2018. (obestämd)
↑ 1 2 Bevis för Roths teorem för grupper med liten vridning på arxiv.org . Hämtad 23 december 2017. Arkiverad från originalet 12 juni 2018. (obestämd)
↑ Presentation av Ellenbergs och Gijswijts bevis på ryska
↑ Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), nr. 1, 5-14. . Hämtad 23 december 2017. Arkiverad från originalet 10 januari 2018. (obestämd)