Rothova věta

Rothův teorém je výsledkem aditivní kombinatoriky , speciální případ Szemerediho věty pro průběhy délky 3; tvrdí přítomnost aritmetických posloupností v jakýchkoli dostatečně hustých množinách. $(a,a+d,a+2d),\ d\not =0$

Přesná formulace je: pro libovolnou množinu , která má asymptotickou hustotu , obsahuje aritmetickou progresi délky 3. $\delta \in (0;1)$ $A\subset {\mathbb {N} }$ $d(A)>\delta$

Podobné formulace využívající horní a dolní asymptotické hustoty jsou ekvivalentní [1] .

Formulace pro konečné množiny je také ekvivalentní té původní: pro libovolnou existuje taková, že if , a , pak obsahuje aritmetickou posloupnost délky 3. Naprostá většina důkazů dokazuje formulaci pro konečné množiny. $\delta \in (0;1)$ $N_{0}=N_{0}(\delta )$ $N>N_{0}$ $A\subset \left\lbrace {1,2,\tečky ,N}\right\rbrace$ $|A|>\delta N$ $A$

Historie vylepšených skóre

Maximální velikost podmnožiny $\{1,\tečky ,N\}$ bez progresí délky 3
Rok vydání	Velikost (až konstantní)	Autoři)
1953	${\frac {N}{\log \log N))$	ústa [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 (předtisk)	${\frac {(\log \log N)^{3}(\log \log \log N)^{5}}{\log N}}N$	Shoen [10]
2020 (předtisk)	${\frac {N}{(\log N)^{1+c))},\ c>0$	Bloom, Sisask [11]

Různé důkazy

Harmonická analýza

Větu poprvé dokázal v roce 1953 Klaus Roth [2] [12] adaptací Hardy-Littlewoodovy kruhové metody. Při důkazu byla využita myšlenka [13] , která byla následně zobecněna pro obecný důkaz Szémerediho věty: všechny množiny dané hustoty jsou rozděleny do dvou skupin – „stejnoměrné“ a „nestejnoměrné“ a „stejnoměrnost“ znamená horní vázaný na Fourierovy koeficienty . Je-li množina stejnoměrná, pak lze přítomnost progresí v ní prokázat přímo, jinak je možné prokázat existenci subprogrese, ve které je hustota množiny větší než mezi segmentem přirozené řady, do které patří. .

Metoda umožňuje odvodit odhad . Technické detaily důkazu, vazba na Fourierovy koeficienty definující „jednotnost“ a výsledné konstanty se mohou zdroj od zdroje lišit. ${\displaystyle N_{0}(\delta )\leqslant e^{e^{\frac {c}{\delta ))))$

Kombinatorické (přes Szemerediho lemma)

Důkaz Rothovy věty lze odvodit [14] jako speciální případ Szemeredyho věty ze Szemeredyho důkazu. Tento způsob důkazu vyžaduje použití Szémerédyho lemmatu regularity a rohové věty, ze které Rothova věta přímo vyplývá. Je dokonce možné [15] upustit od použití rohové věty a odvodit Rothovu větu přímo z lemmatu odstranění trojúhelníku , ale pouze ve formulaci pro konečné cyklické grupy (viz část "Zobecnění na různé grupy").

Protože Szemerediho lemma pravidelnosti dává extrémně velké horní meze pro hodnotu získanou jeho prostřednictvím (alespoň věže exponentů ), samotná metoda neumožňuje získat lepší meze než tyto.

Elementární (prostřednictvím zobecněných aritmetických posloupností)

Ronald Graham ve své knize o Ramseyho teorii uvádí zjednodušenou verzi důkazu, rovněž založenou na Szemerediho metodě, ale bez použití lemmatu pravidelnosti. Důkaz využívá zobecněné aritmetické posloupnosti tvaru , což je mnohem snazší prokázat přítomnost v množině, az toho je již odvozen samotný Rothův teorém. $a+\sum \limits _{k=1}^{n}{\epsilon _{k}x_{k}}\ (\epsilon _{i}\in \left\lbrace {0,1}\ vpravo\rbrace )$

Grahamův důkaz nedává odhady pro , ale pouze ukazuje existenci, protože používá existenci bodu v posloupnosti, od kterého jsou všechny body dostatečně blízko limitě , ale pouze existence je také prokázána pro limitu, a charakter konvergence není v zásadě analyzován. $N$

Protipříklady pro nehusté množiny

Spolu s nalezením horních hranic pro velikost množiny bez aritmetických posloupností existuje také inverzní problém — sestrojení největší možné množiny , která neobsahuje aritmetické posloupnosti, tedy protipříklad pro označení hranic zlepšení odhadů na . Všechny známé konstrukce takových množin jsou založeny na myšlence uvažování jednotlivých číslic čísel v určité číselné soustavě a stanovení podmínek pro hodnoty těchto číslic. $A\subset \left\lbrace {1,\tečky ,N}\right\rbrace$ $A$ $N_{0}(\delta )$

Erdős, Turan (1936)

První příklad množiny bez posloupností uvedli v roce 1936 Erdős a Turan, kteří navrhli uvažovat čísla, která v ternární soustavě obsahují pouze číslice 0 a 2. Taková množina obsahuje pouze čísla, což je ve srovnání s horním meze. [16] $N^{\log _{3}{2))$

Doklad o správnosti stavby

Nechte --- sadu Erdős--Turan. $A$

Jestliže a , pak v ternární soustavě v nejvýznamnější číslici , kde jsou tato čísla různá, jsou splněny rovnosti . V aritmetickém postupu by tedy bylo splněno , a tedy . $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 a Spencer v roce 1942 zobecnili myšlenku Erdőse a Turana na číselné systémy s rostoucí (v závislosti na velikosti sady) základnou a získali sadu bez progrese velikosti . [17] $\exp \left({-O\left({\frac {\log N}{\log \log N))\right)}\right)N$

Stručný popis designu

V Erdős-Turanově konstrukci je docela dobře možné povolit čísla 0 a 1 místo 0 a 2 (pak bude místo prostředního čísla v postupu zaujímat větší místo v důkazu správnosti). Analogicky k tomu Salem a Spencer v -arym systému uvažovali čísla obsahující pouze číslice od 0 do a stejný počet výskytů každé číslice (s asymptotikou ji lze považovat za lichou a celkový počet číslic --- dělení ). $d$ ${\frac {d-1}{2))$ $d$ ${\frac {d-1}{2))$

Přítomnost progresí je blokována podmínkou výskytu jednotlivých číslic. Pokud se při sčítání nepoužije přenos , pak všechny nuly v (a tedy v ) lze vytvořit pouze přidáním nul z odpovídajících číslic a . Dále indukcí můžeme dokázat shodu poloh všech jedniček, dvojek atd. a dojít k závěru, že . $a+c=2b$ $2b$ $b$ $A$ $C$ $a,b,c$ $a=b=c$

Uvedené skóre se získá zvážením . ${\displaystyle d\asymp {\frac {\log N}{(\log \log N)^{2))))$

Berend (1946)

V roce 1946 Behrend přidal geometrickou interpretaci tím, že spojil číslice čísel se souřadnicemi bodů ve vícerozměrném prostoru a zvažoval čísla odpovídající v tomto smyslu bodům koule . To umožnilo sestavit sadu velikostí bez progrese . [osmnáct] $\exp \left({-O\left({\sqrt {\log N}}\right)}\right)N$

Stručný popis designu

Všechna čísla s číslicemi ne většími než -ary jsou rozdělena do skupin se stejnými hodnotami . Největší z těchto skupin se volí jako soubor a její velikost se odhaduje podle Dirichletova principu . ${\displaystyle x<(2m+1)^{n))$ $m$ $(2 m+1)$ ${\displaystyle x=x_{1}x_{2}\tečky x_{n))$ $\sum \limits _{i=1}^{n}{x_{i}^{2))$

Kvůli omezenému počtu číslic při sčítání takových čísel nedochází k přenosu číslic , takže posloupnosti délky 3 mají také geometrickou interpretaci (jako body na stejné přímce). Ale protože je míč přísně konvexní těleso , nemůže koule jako její hranice obsahovat tři body na jedné přímce. Z toho vyplývá, že ve zvolené množině nejsou žádné progrese.

Velikost sady se nejlépe odhadne na $n\asymp {\sqrt {\log N))$

Následně byl Behrendův odhad navýšen o logaritmický faktor mírným zpřesněním metody [19] , ale k roku 2019 nejsou výrazně lepší výsledky.

Protože horní hranice podobného typu jsou známé pro některá zobecnění Rothovy věty [20] [21] , existují důvody domnívat se, že Behrendova hranice je ostrá.

Variace a zobecnění pro různé skupiny

Pro konečné cyklické grupy

Jak důkaz pomocí harmonické analýzy, tak konkrétní způsob, jakým je Szemerediho lemma aplikováno, nedokazují samotnou větu, ale její "cyklickou" verzi.

Pro libovolnou existuje takové , že if , a , pak obsahuje trojici , kde sčítání znamená modulo sčítání $\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$

Progrese slibované touto formulací mohou být progrese v , ale ne v (například ). Rothův teorém z něj však zjevně vyplývá, pokud množinu považujeme za množinu zbytků v . Tím se změní pouze hustota o konstantu, ale všechny průběhy jsou vhodné pro . Proto je tato věta ekvivalentní hlavní Rothově větě. ${\mathbb {Z} }_{N}$ ${\mathbb {N} }$ $(N-2,N-1,0)$ $\left\lbrace {N+a:a\in A}\right\rbrace$ $\mathbb {Z} _{3N}$ ${\mathbb {N} }$

Pro skupiny s malou pevnou torzí

Následující věta, myšlenkově podobná Rothově větě, z ní nevyplývá a neimplikuje ji, ale je zajímavá pro samostatnou studii.

Nechte některé opravit . Pak pro všechny existuje takové , že pokud , pak $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,\tečky ,0)):a,a+d,a+2d\in A$

Horní hranice

Věta pro grupy byla poprvé prokázána Brownem a Bahlerem v roce 1982 [22] , ale dokázali pouze to, že pro množiny bez aritmetických posloupností , ale přesnější omezení na zůstala otevřená otázka. ${\displaystyle {\mathbb {F} }_{p}^{n))$ $|A|=o(q^{n})$ $|A|$

V roce 1993 (publikováno v roce 1995) Roy Meshulam dokázal [23] , že . Jeho důkaz zvažoval libovolné skupiny a jejich charaktery . Existují také zjednodušenější [24] verze tohoto důkazu, výhradně pro , které pomocí Fourierových koeficientů v , přímo zobecňují myšlenky z analytického důkazu Rothovy věty. Důkaz je technicky ještě jednodušší než samotný důkaz Rothovy věty, proto je [24] [25] často uváděn jako první příklad aplikace metody. $|A|\leq 2{\frac {q^{n}}{n}}$ ${\displaystyle {\mathbb {F} }_{p}^{n))$ ${\displaystyle {\mathbb {F} }_{p}^{n))$

V roce 2012 Bateman a Katz, zvažující případ , dokázali [26] existenci absolutní konstanty , takže bez aritmetických posloupností . $q=3$ $\epsilon > 0$ $C$ ${\displaystyle A\subset {\mathbb {F} }_{3}^{n))$ $|A|\leq {\frac {3^{n}}{n^{1+\epsilon }}}$

V roce 2016 Krut, Lev a Pach dokázali [27] pro případ , že pro množiny bez progresí. Ellenberg a Gijswijt, zobecňující metodu Kruta, Löwa a Pacha pomocí polynomiální algebry , dokázali [28] [29] existenci pro každou jednoduchou konstantu takovou, že jestliže neobsahuje posloupnosti délky 3. Ve svém článku , . Zejména pro případ . Za předpokladu z optimalizace funkce vyplývá, že , kde je absolutní konstanta, která je řešením rovnice , tedy , , kde $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}\cca 0,841434...$

Dolní hranice

Nejlepší [28] z roku 2016 konstrukce-protipříklad umožňuje [30] konstruovat sady velikostí pro skupiny formuláře , které neobsahují aritmetické posloupnosti délky 3. ${\displaystyle {\mathbb {F} }_{3}^{n))$ $\Omega (2.2^{n})$

Pro libovolné skupiny

Meshulam uvažuje [23] Rothovu větu pro libovolnou grupu a odvodí odhad pro množinu bez aritmetických posloupností délky 3. $G={\mathbb {Z} }_{k_{1}}\oplus \dots \oplus {\mathbb {Z} }_{k_{n}}$ $|A|<2{\frac {|G|}{n))$

To implikuje existenci absolutní konstanty , takže pro množinu bez progresí $\beta>0$ $A\subset G$ ${\displaystyle |A|<{\frac {|G|}{(\log {|G|})^{\beta ))))$

Dvourozměrné zobecnění

Klasickým zobecněním Rothovy věty pro dvourozměrné množiny je věta o rohu . Ačkoli zde není žádná zmínka o aritmetických postupech (ve dvourozměrném smyslu), Rothův teorém z toho vyplývá. $A\subset \left\lbrace {1,\tečky ,N}\right\rbrace \times \left\lbrace {1,\tečky ,N}\right\rbrace$

Viz také

Van der Waerdenova věta

Literatura

KF Roth. O určitých množinách celých čísel // Journal of the London Mathematical Society. - 1953. - S. 104-109 . - doi : 10.1112/jlms/s1-28.1.104 .
DR Heath-Brown. Celočíselné sady neobsahující žádné aritmetické progrese (anglicky) // Journal of the London Mathematical Society. - 1987. - Sv. s2-35 , iss. 3 . - str. 385-394 . - doi : 10.1112/jlms/s2-35.3.385 .
E. Szemeredi. Celočíselné množiny neobsahující žádné aritmetické posloupnosti // Acta Mathematica Hungarica. - 1990. - Sv. 56 . - S. 155-159 . - doi : 10.1007/BF01903717 .
J. Bourgain. On Triples in Aritmetic Progression (anglicky) // Geometric & Functional Analysis GAFA. - 1999. - Sv. 9 . - S. 968-984 . - doi : 10.1007/s000390050105 .
J. Bourgain. Revidovaná Rothova věta o progresích // Journal d'Analyse Mathématique. - 2008. - Sv. 104 . - S. 155-192 . - doi : 10.1007/s11854-008-0020-x .
T. Sanders. Na některých dalších souborech celých čísel // Journal d'Analyse Mathématique. - 2012. - Sv. 116 . - str. 53-82 . - doi : 10.1007/s11854-012-0003-9 . - arXiv : 1007.5444 .
T. Sanders. O Rothově větě o postupech // Annals of Mathematics. - 2011. - Sv. 174 . - S. 619-636 . - doi : 10.4007/annals.2011.174.1.20 . - arXiv : 1011.0104 .
TF Bloom. Kvantitativní zlepšení pro Rothovu větu o aritmetických postupech (anglicky) // Journal of the London Mathematical Society. - 2014. - Sv. 93 , iss. 3 . - str. 643-663 . doi : 10.1112 / jlms/jdw010 . - arXiv : 1405,5800 .
T. Schoen. Vylepšená vazba v Rothově větě o aritmetických posloupnostech . - 2020. - arXiv : 2005.01145 .
T. F. Bloom, O. Sisask. Prolomení logaritmické bariéry v Rothově větě o aritmetických postupech . - 2020. - arXiv : 2007.03528 .

Poznámky

↑ I. D. Shkredov, „Szemerediho věta a problémy aritmetických posloupností“, Uspekhi Mat. Nauk, 61:6(372) (2006), 111-178; Ruská matematika. Surveys, 61:6 (2006), 1101-1166 . Získáno 23. prosince 2017. Archivováno z originálu dne 24. prosince 2017. (neurčitý)
↑ 12 Roth , 1953 .
↑ Heath-Brown, 1987 .
↑ Szemerédi, 1990 .
↑ Bourgain, 1999 .
↑ Bourgain, 2008 .
↑ Sanders, 2012 .
↑ Sanders, 2011 .
↑ Bloom, 2014 .
↑ Schoen, 2020 .
↑ Bloom, Sisask, 2020 .
↑ Rothův důkaz v podání Harolda Helfgotta v ruštině (nepřístupný odkaz) . Získáno 23. prosince 2017. Archivováno z originálu dne 24. prosince 2017. (neurčitý)
↑ Postnauka, Ilja Shkredov - Semerediho věta
↑ Chebyshev Laboratory, kurz přednášek "Aditivní kombinatorika", přednáška 3
↑ Mini kurz aditivní kombinatoriky Archivováno 29. srpna 2017 na Wayback Machine , str. 6
↑ P. Erdős, P. Turán, „O některých posloupnostech celých čísel“, Journal of the London Mathematical Society (červen 1936) . Získáno 23. prosince 2019. Archivováno z originálu dne 23. prosince 2019. (neurčitý)
↑ R. Salem, DC Spencer, Proc. Natl. Akad. sci. USA 28 (1942), 561-563 . Získáno 23. prosince 2017. Archivováno z originálu 3. června 2018. (neurčitý)
↑ FA Behrend, "O množinách celých čísel, které neobsahují žádné tři členy v aritmetickém postupu", Proc. Natl. Akad. sci. USA 32 (1946), 331-332. . Získáno 23. prosince 2017. Archivováno z originálu dne 4. června 2018. (neurčitý)
↑ Michael Elkin, „Vylepšená konstrukce množin bez progrese“, Israel Journal of Mathematics, 184:93 (srpen 2011) . Staženo 23. prosince 2019. Archivováno z originálu dne 27. listopadu 2018. (neurčitý)
↑ T. Schoen, ID Shkredov, "Rothův teorém v mnoha proměnných", Israel Journal of Mathematics, svazek 199, strany 287-308 (2014) Archivováno 23. prosince 2019 na Wayback Machine ( arXiv:1106.1601 Archived the Wayback 23 stroj )
↑ T. Schoen, O. Sisask, "Rothův teorém pro čtyři proměnné a aditivní struktury v součtech řídkých množin", Fórum matematiky Fórum matematiky, Sigma, 4, E5. doi:10.1017/fms.2016.2 Archivováno 1. května 2020 na Wayback Machine ( arXiv:1408.2568 Archivováno 23. prosince 2019 na Wayback Machine )
↑ TC Brown a JP Buhler, Hustotní verze geometrického Ramseyho teorému, Journal of Combinatorial Theory, Series A 32 (1982), no. 1, 20-34. . Získáno 23. prosince 2017. Archivováno z originálu 9. srpna 2017. (neurčitý)
↑ 1 2 R. Meshulam, O podmnožinách konečných abelovských grup bez 3členných aritmetických posloupností, Journal of Combinatorial Theory, Series A 71 (1995), no. 1, 168-172. (nedostupný odkaz)
↑ 1 2 Mini kurz aditivní kombinatoriky Archivováno 29. srpna 2017 na Wayback Machine , str. 39-42
↑ Chebyshev Laboratory, Ilya Shkredov, Analytické metody v aditivní kombinatorice, souhrnná přednáška
↑ M. Bateman a N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), no. 2, 585-613. . Získáno 23. prosince 2017. Archivováno z originálu 9. ledna 2018. (neurčitý)
↑ E. Croot, V. Lev a PP Pach, množiny bez progrese v Z_n^4 jsou exponenciálně malé (2016). arXiv předtisk 1605.01506. . Získáno 23. prosince 2017. Archivováno z originálu 12. června 2018. (neurčitý)
↑ 1 2 Důkaz Rothovy věty pro grupy s malou torzí na arxiv.org . Získáno 23. prosince 2017. Archivováno z originálu 12. června 2018. (neurčitý)
↑ Prezentace Ellenbergova a Gijswijtova důkazu v ruštině
↑ Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), no. 1, 5-14. . Získáno 23. prosince 2017. Archivováno z originálu 10. ledna 2018. (neurčitý)