Van der Waerdenova věta

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. prosince 2018; kontroly vyžadují 8 úprav .

Van der Waerdenův teorém je klasickým výsledkem kombinatorické teorie čísel o monochromatických aritmetických postupech při zabarvení přirozených čísel . Věta je typickým prohlášením Ramseyho teorie , stejně jako předchůdce Szemerediho věty , která znamenala začátek velkého odvětví aditivní kombinatoriky .

Notový zápis

V celém článku se notace používá k označení množiny . Toto označení je v literatuře zcela běžné. $\{1,\tečky ,N\}$ $[N]$

Formulace

Věta má dvě ekvivalentní formulace – konečnou a nekonečnou [1] .

Nekonečné znění

Pro všechny a funkce existují takové, které $r,k\in {\mathbb {N} }$ $c:{\mathbb {N} }\to [r]$ $a,d\in {\mathbb {N} }$

c(a)=c(a+d)=\dots =c(a+(k-1)d)

Funkce se obvykle nazývá zbarvení přirozených čísel, její hodnoty jsou barvy čísel a progrese je jednobarevná (věta nespecifikuje, jakou barvu mají její prvky). $C$ $a,a+d,\tečky ,a+(k-1)d$

Konečná formulace je podobná té nekonečné, ale uvažuje o zabarvení konečné množiny. Patří O. Schreierovi [2] .

Konečné znění

Pro jakoukoli existuje číslo takové, že pro jakoukoli funkci existuje takové, že $r,k\in {\mathbb {N} }$ $N=N(r,k)$ $c:[N]\to [r]$ $a,d\in {\mathbb {N} }$

c(a)=c(a+d)=\dots =c(a+(k-1)d)

Čísla z konečné formulace se nazývají van der Waerdenova čísla . U nich se studují spodní a horní hranice. $N(r,k)$

Historie

Důkaz věty publikoval B. L. van der Waerden v roce 1927.

Alexander Sofier ve svém historickém eseji o Ramseyho teorii píše, že Schur považoval výrok věty za hypotézu , když pracoval na své větě o barvení čísel (v roce 1916), ale hypotéza se nedostala k van der Waerdenovi ze Schura, ale byl nezávisle vynalezen Bodem a van der Waerden se hypotézu dozvěděl od svých studentů (Baudet už v té době zemřel). Důkaz byl vynalezen na univerzitě v Hamburku a představen veřejnosti v Berlíně na kongresu Německé matematické společnosti [3] .

Van der Waerden si jednoduše neuvědomil, jak důležitý výsledek dokázal: předložil své práce z algebraické geometrie nejprestižnějšímu časopisu Mathematische Annalen a tento důkaz předložil „nesrozumitelnému“ časopisu Nieuw Archief voor Wiskunde z Nizozemské matematické společnosti. .

Původní text (anglicky)[ zobrazitskrýt] Van der Waerden si jednoduše neuvědomil, jak důležitý je výsledek, který dokázal: zaslal své práce z algebraické geometrie do nejprestižnějšího časopisu Mathematische Annalen , ale poslal tento důkaz do „obskurního“ časopisu Nieuw Archief voor Wiskunde z Nizozemské matematické společnosti. .

Alexander Khinchin zase napsal, že výsledek byl získán v Göttingenu v létě 1928 několik dní před jeho příjezdem a že „místní matematik […] se s hypotézou setkal v průběhu své vědecké práce“ [4] .

Nejednoznačnost původu původní hypotézy zdůrazňuje Ronald Graham ve své knize o Ramseyho teorii [5] , nicméně všechny zdroje se shodují, že ve formulaci problému, který van der Waerden řešil, byly pouze dvě barvy, a posílení tvrzení na libovolný počet barev bylo přidáno jako nástroj důkazu.

Schéma důkazu [6]

V této části je tvrzení, že teorém platí pro barvy a délky progrese, označeno jako . $r$ $k$ ${\mbox{W}}(r,k)$

Věta je dokázána indukcí na . Základ je zřejmý [7] . Při dokazování indukčního kroku se obvykle pro pohodlí říká, že se předpokládá, že se má dokázat pro všechny , i když formálně, k prokázání každého jednotlivého tvrzení je konečný počet tvrzení ve tvaru , ale s velmi velkými hodnotami . dostačující . $k$ $k=2$ ${\mbox{W}}(r,k')$ $k'<k,\ r\in {\mathbb {N} }$ ${\mbox{W}}(r,k)$ ${\mbox{W}}(r',k-1),r'\in {\mathbb {N} }$ $r'$

Aby byla zaručena přítomnost jednobarevné progrese délky , je třeba přejít od uvažování intervalu, jehož délka zaručuje přítomnost jednobarevné progrese délky , k větším a větším intervalům, zaručujícím přítomnost více a složitější struktury - tzv. ventilátory . Pro barvení nazýváme -fan rodinu délkových posloupností tak, že: $k$ $k-1$ $C$ $s$ $({\vec {P}}_{i})_{i=1}^{s}$ $k$

${\vec {P}}_{1}(k)={\vec {P}}_{2}(k)=\dots ={\vec {P}}_{s}(k)$ , to znamená, že poslední bod všech progresí je společný;
$c({\vec {P}}_{i}(1))=c({\vec {P}}_{i}(2))=\dots =c({\vec {P} }_{i}(k-1)),\ i=1,\tečky ,s$ , to znamená, že pro každý postup jsou všechny prvky, kromě posledního, stejné barvy;
$i\not =j\Rightarrow c({\vec {P}}_{i}(1))\not =c({\vec {P}}(1))$ , to znamená, že hlavní barva (všech prvků kromě posledního) je pro každý postup jiná.

K prokázání indukčního kroku lze použít ventilátory díky dvěma zjevným vlastnostem:

přítomnost ve zbarvení jednobarevné progrese délky ve skutečnosti znamená přítomnost -ventilátoru; $k-1$ $jeden$
přítomnost -ventilátoru ve zbarvení zaručuje přítomnost jednobarevné progrese délky (protože barvy všech progresí jsou různé a barvy všeho , pak se jedna z nich shoduje s barvou společného posledního prvku). $r$ $k$ $r$

Stačí tedy dokázat krok indukce na parametru pro tvrzení "jakékoli zbarvení dostatečně velkého intervalu obsahuje -fan nebo délkovou progresi ". K tomu byste měli: $s$ $s$ $k$

Rozbijte velký interval na bloky - menší intervaly, ale také dostatečně velké délky (označme ). Hodnota musí být dostatečná, aby zajistila , že v intervalech délky (tedy v každém bloku) je -fan (taková délka existuje podle indukční hypotézy). $M$ $M$ $M$ $(s-1)$
Přiřaďte celou sadu barev jeho prvků jako "hypercolor" bloku. Počet takových hyperbarev bude velmi velký, ale stále konečný. ${\displaystyle r^{M))$
Pro „hypercoloring“ dostatečně dlouhé sekvence bloků použijte příkaz , tedy „najděte“ postup absolutně identicky barevných bloků. ${\mbox{W}}(r^{M},k-1)$

To zaručí přítomnost několika identických -ventilátorů rozmístěných ve stejné vzdálenosti od sebe (jakýsi postup ventilátorů). Pokud se barva středového prvku ventilátoru liší od barev jeho průběhů [8] , pak v takové konstrukci je možné zvolit -ventilátor diagonálně (viz obrázek). $s$ $(s+1)$

Analýza vícerozměrných progresí

Během diagonálního přechodu z progrese -fans na -fan se ztratí velké množství aritmetických a barevných spojení, na kterých se podílejí prvky, které nejsou zahrnuty v -fan. Pokud vysledujeme tyto prvky a jejich duplikaci v následných progresích od -fans, -fans atd., pak bude vidět, že jednobarevné progrese vycházející z libovolného -fanu jsou vlastně diagonály jednobarevných vícerozměrných progresí dimenze od do , v závislosti na "okamžiku" vzhledu barvy během indukce. Někteří autoři proto předkládají důkaz ve smyslu nalezení vhodné kombinace vícerozměrných progresí [9] . $s$ $(s+1)$ $(s+1)$ $(s+1)$ $(s+2)$ $s$ $jeden$ $s$

Zobecnění

Pro van der Waerdenovu větu bylo studováno mnoho zobecnění pro různé aspekty formulace výroku. V jednom výroku lze kombinovat různé typy zobecnění.

V této části jsou uvedeny pouze nekonečné formulace zobecněných tvrzení, i když pro většinu z nich existují konečná analoga konstruovaná podle stejného principu jako pro hlavní větu.

Způsoby zobecnění

Podle konstrukčních podmínek pro konfiguraci

Podmínka, že čísla tvoří aritmetický postup, znamená splnění rovnosti ${\displaystyle x_{1},\tečky ,x_{k))$

x_{i}-x_{i-1}=x_{i+1}-x_{i},\ i=2,\tečky ,k-2

Jedním ze způsobů zobecnění je nahradit tyto podmínky jinými, které jsou rovněž lineární.

Otázka

Pro které soustavy lineárních rovnic (včetně jednotlivých rovnic) platí tvrzení van der Waerdenovy věty, když je podmínka, že prvky požadované konfigurace tvoří progresi, nahrazena skutečností, že dané soustavě vyhovují?

Kromě toho mohou být prvky progrese reprezentovány jako . Pokud rozdíly vnímáme jako pevné funkce , pak to vede k polynomickému zobecnění. $a,a+d,a+2d,\tečky ,a+(k-1)d$ $d,2d,\tečky ,(k-1)d$ $d$

Polynomiální verze

Dovolit být polynomy s celočíselnými koeficienty takové, že . Pak pro všechny a tam jsou barviva taková, že ${\displaystyle p_{1},\tečky ,p_{k))$ $p_{i}(0)=0,\ i\in [k]$ $r\in {\mathbb {N} }$ $c:{\mathbb {N} }\to r$ $a,d\in {\mathbb {N} }$

c(a)=c(a+p_{1}(d))=c(a+p_{2}(d))=\tečky =c(a+p_{k}(d))

Nápady na důkazy [10]

Vějíře lze také použít k prokázání verze polynomu, ale s odpovídajícími rozdíly v polynomech. Například při dokazování přítomnosti monochromního páru v libovolném zbarvení je mezikrokem dokázat existenci čísel tak, že mají různé barvy a jsou čtverce [11] . $a,a+d^{2},\ a,d\in {\mathbb {N} }$ ${\displaystyle x_{0},x_{1},\tečky ,x_{s))$ ${\displaystyle x_{1},\tečky ,x_{s))$ ${\displaystyle x_{1}-x_{0},\tečky ,x_{s}-x_{1))$

Podle rozměru

Při zobecňování věty na vícerozměrné prostory se místo posloupností uvažují homotetické obrazy konečné množiny bodů (aritmetická posloupnost odpovídá homotetickému obrazu diskrétní hyperkrychle ).

Vícerozměrná verze [12]

Pro jakákoli přirozená čísla existují takové množiny a zbarvení $r,t\in {\mathbb {N} }$ ${\displaystyle K\subset {\mathbb {N} }^{t))$ ${\displaystyle c:{\mathbb {N} }^{t}\to \{1,\tečky ,r\))$ ${\vec {a}}\in {\mathbb {N} }^{t},d\in {\mathbb {N} }$

c({\vec {a}})=c({\vec {a}}+{\vec {k}}d)\ \forall \ {\vec {k}}\in K

Širší, čistě kombinatorické, vícerozměrné zobecnění nabízí Hales-Jewettův teorém. Pro větší pohodlí to lze chápat jako barvicí teorém , ale operace s čísly se v něm vůbec nepoužívají, to znamená, že množinu lze nahradit jakoukoli jinou stejné velikosti. Dimenze prostoru zde působí jako proměnlivý („dostatečně velký“) parametr , takže Halesova-Jewettova věta má pouze konečnou formulaci. ${\displaystyle [k]^{n))$ $[k]$

Definice

Pro kombinatorickou úsečku nastavenou v diagonále libovolné netriviální podkrychle se nazývá množina všech vektorů, kde některé souřadnice mohou být pevné a zbytek (nenulové číslo) je vždy stejný a běží přes všechny hodnoty . $A$ $A^{n}$ $v A$

Halesova-Jewettova věta [13]

Pro jakékoli existuje takové číslo , že pro jakékoli v jakémkoli zbarvení existuje monochromatická kombinatorická čára. $k,r\in {\mathbb {N} }$ $n_{0}=n_{0}(r,k)$ $n>n_{0},\ |A|=k$ $c:A^{n}\to [r]$

Nápady na důkaz

Důkaz Hales-Jewettovy věty je založen na stejné indukci prostřednictvím ventilátorů. Pro vektor se uvažuje rozdělení souřadnic . V hypercoloring , kde je hypercolor vektoru kombinací barev všech bodů formuláře , pro dostatečně velké je možné za induktivního předpokladu (c ) najít kombinatorickou čáru, kde budou všechny prvky kromě jednoho stejné barvy. Pro obarvení to bude znamenat přítomnost takové "čáry" identicky barevných podprostorů dimenze . A u velkých je zaručena přítomnost podobné přímky v každém z těchto podprostorů. Ukazuje se „přímka z přímek“, z nichž každá má stejné pokračování. Tato konstrukce je podobná konstrukci zobecněných posloupností z důkazu van der Waerdenovy věty a lze ji použít ke konstrukci ventilátorů stejným způsobem jako [14] . ${\vec {a}}\in A^{n}$ ${\vec {a}}=({\vec {a_{1}}},{\vec {a_{2}}})\in A^{n_{1}}\times A^{n_ {2}},\ n_{1}+n_{2}=n$ $A^{n_{1))$ ${\vec {a_{1}}}\in A^{n_{1}}$ $({\vec {a_{1}}},{\vec {a_{2}}}),\ {\vec {a_{2}}}\in A^{n_{2}}$ $n_{1}$ $k'=k-1$ $A^{n}$ $n_{2}$ $n_{2}$

Van der Waerdenův teorém vyplývá z Hales-Jewettovy věty, protože transformace z na , odpovídající interpretaci souřadnic jako číslic v -árním číselném systému , mapuje kombinatorické přímky v aritmetickém postupu [15] . Vícerozměrný van der Waerdenův teorém lze odvodit podobně stanovením libovolného číslování prvků a uvažováním Hales-Jewettovy věty pro [16] . ${\displaystyle [k]^{n))$ $[k^{n}]$ $k$ $K$ $k=|K|$

Vícerozměrný teorém lze také dokázat přímo, bez Hales-Jewettova teorému. Pokud je to skutečně prokázáno pro podmnožinu obsahující afinně nezávislé body, pak můžeme použít indukci od do pomocí vějířů z van der Waerdenových vět, ale s rozdělením do vícerozměrných bloků. Stačí tedy představit způsob přechodu od příkazu pro k příkazu pro množinu afinně nezávislých bodů. Jako příklad si můžete vzít roh, tedy body formuláře ${\displaystyle K'\subset K\subset {\mathbb {R} }^{t))$ $t$ $K'$ $K$ ${\displaystyle {\mathbb {R} }^{t-1))$ ${\displaystyle K\subset {\mathbb {R} }^{t))$ $t$ $K$

(a_{1},a_{2},\dots ,a_{t})

(a_{1}+d,a_{2},\tečky ,a_{t})

(a_{1},a_{2}+d,\tečky ,a_{t})

\tečky

(a_{1},a_{2},\tečky ,a_{t}+d)

Přítomnost -rozměrného rohu v nadrovině s podmínkou (která je zaručena pro dostatečně velký ) znamená přítomnost rohu, ve kterém mají všechny body kromě centrálního stejnou barvu. Dále rozdělením čísel do vícerozměrných bloků a aplikací stejného postupu na ně lze z takových rohů postavit libovolně velké ventilátory. $(t-1)$ ${\displaystyle {\mathbb {R} }^{t))$ $a_{1}+\tečky +a_{t}=N$ $N$ ${\displaystyle {\mathbb {R} }^{t))$

Jedna barva (husté podmnožiny)

Z empirických úvah je přirozené předpokládat, že požadovaná jednobarevná konfigurace čísel bude mít ve většině případů nejoblíbenější barvu, protože čím více čísel té či oné barvy, tím zajímavější konfigurace mezi nimi mohou vzniknout.

Ačkoli je toto tvrzení přijatelné, nevyplývá přímo z van der Waerdenovy věty a je mnohem obtížnější jej dokázat. Abychom to formalizovali, je třeba poznamenat, že v konečném zbarvení má nejoblíbenější barva kladnou horní hustotu [17] . Uvedený předpoklad tedy znamená přítomnost progrese v jakékoli husté množině. Tato věta je pojmenována po Endre Szemeredym , který ji jako první dokázal.

Szemerediho věta

Pro libovolné a množinu takové , že existují takové, že . ${\displaystyle \delta \in (0;1),k\in {\mathbb {N} ))$ $A$ $\lim \limits _{N\to \infty }{\frac {|A\cap [N]|}{N}}>\delta$ $a,d\in {\mathbb {N} }$ $a,a+d,\tečky ,a+(k-1)d\in A$

Analogicky k van der Waerdenovým číslům pro konečnou verzi Szémerédyho věty studujeme dolní a horní odhady pro , dostatečné pro množinu s podmínkou, aby vždy obsahovala posloupnost délky . Získání takových odhadů v případě je mnohem obtížnější než v případě . $N(\delta ,k)$ $A\subset [N]$ $|A|>\delta N$ $k$ $k\geq 4$ $k=3$

Nápady na důkaz

Metody dokazování Szemerediho věty se nápadně liší od věty van der Waerdena jak v typu, tak ve složitosti. Známé jsou kombinatorické (s použitím Szemerediho lemmatu regularity z obecné teorie grafů ), analytické (s použitím Fourierových koeficientů a Gowersových norem , které je zobecňují ) a ergodické důkazy.

K prokázání nejširších zobecnění (s přidáním polynomiálních rozdílů a multidimenzionality prostoru) dobře fungují metody ergodické teorie, ale nedávají žádné kvantitativní odhady pro konečné formulace [18] .

Do nekonečného počtu barev

Při spočítatelném počtu barev, tedy zbarvení , nemusí docházet k dlouhým jednobarevným progresím [19] . Pokud ale za další, rovněž přípustný, pól barevné struktury považujeme konfigurace, kde jsou barvy všech prvků různé, pak věta zůstává pravdivá. $c:{\mathbb {N} }\to {\mathbb {N} }$

Toto tvrzení se nazývá kanonická verze van der Waerdenovy věty.

Kanonická verze

Pro jakékoli zbarvení a existují čísla taková, že: $k\in {\mathbb {N} }$ $c:{\mathbb {N} }\to {\mathbb {N} }$ $a,d\in {\mathbb {N} }$

nebo $c(a)=c(a+d)=\dots =c(a+(k-1)d)$
nebo pro jakýkoli $c(a+id)\not=c(a+jd)$ $0\leq i<j<k$

Nápady na důkaz

Erdős a Graham si jako první všimli, že kanonická verze vyplývá ze Szemerediho věty [20] . Následně byla tato myšlenka zobecněna na vícerozměrný případ [21] . Samotný Szémeredyho teorém je však obtížné dokázat, proto byl později nalezen další, elementární důkaz kanonické verze prostřednictvím vícerozměrné verze obvyklé van der Waerdenovy věty [22] .

Podle zbarvení lze sestrojit zbarvení roviny , kde barva páru je spojena s progresí , totiž odpovídá dělení progrese podle stejnosti barev. Například páry, pro které jsou obarveny odpovídající průběhy (červená, červená, zelená) a (modrá, modrá, žlutá), budou mít stejnou barvu v . Je důležité, aby počet barev byl konečný . $c:{\mathbb {N} }\to {\mathbb {N} }$ $C'$ $(a,d)\in {\mathbb {N} }^{2}$ $a,a+d,\tečky ,a+(k-1)d$ $(c(a),c(a+d),\dots ,c(a+(k-1)d))$ $C'$ $C'$

Pokud neexistují žádné vícebarevné posloupnosti délky , pak má každá progrese alespoň dva prvky stejné barvy. Podle multidimenzionálního van der Waerdenova teorému existuje ve zbarvení jednobarevný homotetický obraz . Posloupnosti odpovídající bodům tohoto obrázku se budou protínat tak, že kombinací těchto rovností je možné ukázat monochromatičnost prvků z různých průběhů a bude jich tolik, že tyto prvky vytvoří svůj vlastní postup. délky , zcela jednobarevné, což vyžaduje podmínka. $C$ $k$ $C'$ $[(k-1)^{2}]^{2}$ $k$

Souhrnná tabulka s některými výsledky

Aritmetické podmínky na požadovanou strukturu	Oblast hledání	Prostor
		jednorozměrný	Multidimenzionální	$A^{n}$ pro finále $A$
Aritmetické průběhy	konečné zbarvení	Van der Waerdenova věta	Witt, 1952	Halesova-Jewettova věta
	Nekonečné barvení	Promel, Rodl, 1986		Věta má pouze konečné znění
	hustá podmnožina	Szemerediho věta (včetně Rothovy věty )	Rohová věta	Známý silný zobecnění Rothovy věty
Řešení lineárních rovnic nebo soustavy rovnic	konečné zbarvení	Radova věta Schurova věta
	Nekonečné barvení	Lefmann, 1986		Věta má pouze konečné znění
	hustá podmnožina	Některé jsou známé zobecnění Rothovy věty [23] [24]
Význam polynomů v rozdílech	konečné zbarvení	Walters, 2000
	Nekonečné barvení	Girao, 2020 Fox, Wigderson, Zhao, 2020		Věta má pouze konečné znění
	hustá podmnožina	Bergelson, Leibman, 1996
	hustá podmnožina	Dokázáno samostatnými metodami Furstenbergova-Sharkozyho věta [25] a Rothova kvadratická věta [26]

Literatura

I. D. Shkredov. Szemerediho věta a problémy aritmetických posloupností // Uspekhi matematicheskikh nauk. - 2006. - T. 61 , č. 6 . — s. 111–178 . (Ruština)

A. Soifer. Ramsey Theory : Včera, dnes a zítra . — Boston: Birkhäuser, 2011. — 189 s. - ISBN 978-0-8176-8091-6 .

A. Ya, Khinchin. Tři klenoty teorie čísel . - Moskva: "Nauka", 1979. - 66 s. (Ruština)

M. Walters. Kombinatorické důkazy polynomické van der Waerdenovy věty a polynomické Hales-Jewettovy věty // Journal of the London Mathematical Society. - 2000. - Sv. 61 , iss. 1 . — S. 1–12 .

V. Bergelson, A. Leibman. Polynomiální rozšíření van der Waerdenových a Szemerédiho vět // Journal of the American Mathematical Society. - 1996. - Sv. 9 , iss. 3 . — S. 725–753 .

R. Graham. Počátky Ramseyho teorie . - Moskva: "Mir", 1984. - 97 s. (Ruština)

P. Erdős, R. L. Graham. Staré a nové problémy a výsledky v kombinatorické teorii čísel // L'Enseignement Mahematique. - 1980. - Sv. 25 . — S. 325–344 .

W. Deuber, R. L. Graham, H. J. Promel, B. Voigt. Kanonický oddílový teorém pro vztahy ekvivalence na ${\displaystyle {\mathbb {Z} }^{t))$ (anglicky) // Journal of Combinatorial Theory, Series A. - 1983. - Vol. 34 , iss. 3 . — S. 331–339 .

HJ Promel, V. Rodl. Elementární důkaz kanonizující verze Gallai-Wittovy věty (anglicky) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 42 , iss. 1 . — S. 144–149 .

RL Graham, BL Rothschild, JH Spencer. Ramseyho teorie . - 2. vyd. - Publikace Wiley-interscience, 1990. - 196 s. - ISBN 0-471-50046-1 .

H. Lefmann. Kanonická verze pro rozdělovací regulární systémy lineárních rovnic (anglicky) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 41 , iss. 1 . — S. 95–104 .

E. Witt. Ein kombinatorischer Satz der Elementargeometrie (německy) // Mathematishe Nachrichten. — 1952.

A. Girao. Kanonický polynom Van der Waerdenův teorém . - 2020. - arXiv : 2004.07766 .

J. Fox, Y. Wigderson, Y. Zhao. Krátký důkaz van der Waerdenovy věty o kanonickém polynomu . - 2020. - arXiv : 2005.04135 .

S. Peluse, S. Prendiville. Polylogaritmická vazba v nelineární Rothově větě . - 2020. - arXiv : 2003.04122 .

N. Lyall. Nový důkaz Sarkozyho věty // Proceedings of the American Mathematical Society. - 2011. - Sv. 141 , iss. 7 . - arXiv : 1107.0243 .

T. Schoen, ID Shkredov. Rothův teorém v mnoha proměnných // Israel Journal of Mathematics. - 2014. - Sv. 199 . — S. 287–308 . - arXiv : 1106.1601 .

T. Schoen, O. Sisask. Rothova věta pro čtyři proměnné a aditivní struktury v součtech řídkých množin // Fórum matematiky, Sigma. - 2016. - Sv. 4 . - arXiv : 1408.2568 .

Poznámky

↑ Shkredov, 2006 , s. 112-114
↑ Graham, 1984 , s. osmnáct.
↑ Soifer, 2011 , str. 2.7.
↑ Khinchin, 1979 , s. 7-8.
↑ Graham, 1984 , s. 17.
↑ Viz různé prezentace v Khinchin, 1979 , s. 9-13, Graham, 1984 , str. 18-21, Shkredov, 2006 , s. 118-119
↑ Stačí vzít čísla tak, aby mezi nimi podle Dirichletova principu byla dvě čísla stejné barvy. $r+1$
↑ Jiné by znamenalo přítomnost progrese délky , a pak není co dokazovat $k$
↑ Khinchin, 1979 , s. 9-13, viz vzorec (5) a další odstavec, kde je přechod k úvaze o -té progresi -ventilátoru $r$ $s$
↑ S rozvojem studia Szemeredyho věty se aktivně používaly účinné metody ergodické teorie k prokázání jejích polynomiálních zobecnění (viz Bergelson, Leibman, 1996 ). Později byl publikován elementární důkaz polynomiálního zobecnění bez kombinace se zobecněním, jako je Szemerédyho věta.
↑ Walters, 2000 , viz "Indukční hypotéza" na str. 3
↑ V anglické literatuře se často nazývá „Gallai-Wittův teorém“.
↑ Graham, 1984 , s. 24.
↑ Graham, 1984 , s. 24-25.
↑ Graham, 1984 , s. 26.
↑ Graham, Rothschild, Spencer, 1990 , str. 40-41.
↑ A navíc, horní hustota není menší než , kde je počet barev $1/r$ $r$
↑ Bergelson, Leibman, 1996 .
↑ Každé číslo můžete například vybarvit svou vlastní barvou, tedy přiřadit $c(x):=x$
↑ Erdős, Graham, 1980 , s. 333, viz "Existence je zaručena Szemerédiho větou." $H(n)$
↑ Deuber, Graham, Promel, Voigt, 1983 .
↑ Promel, Rödl, 1986 .
↑ Schoen, Shkredov, 2014 .
↑ Schoen, Sisask, 2016 .
↑ Lyall, 2011 .
↑ Peluse, Prendiville, 2020 .