Van der Waerdens sats

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 december 2018; kontroller kräver 8 redigeringar .

Van der Waerdens teorem är ett klassiskt resultat av kombinatorisk talteori om monokromatiska aritmetiska progressioner i färger av naturliga tal . Satsen är ett typiskt uttalande av Ramseys teori , såväl som en föregångare till Szemeredis sats , som markerade början på en stor gren av additiv kombinatorik .

Notation

Genomgående i artikeln används notationen för att beteckna en uppsättning . Denna beteckning är ganska vanlig i litteraturen. $\{1,\dots ,N\}$ $[N]$

Formulering

Satsen har två ekvivalenta formuleringar - ändlig och oändlig [1] .

Oändliga formuleringar

För alla och funktioner finns det sådana att $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)

En funktion kallas vanligtvis en färgning av naturliga tal, dess värden är färger på tal, och en progression är enfärgad (satsen anger inte vilken färg dess element har). $c$ $a,a+d,\dots ,a+(k-1)d$

Den finita formuleringen liknar den oändliga, men betraktar en färgning av en finit uppsättning. Den tillhör O. Schreier [2] .

Slutlig formulering

För vilken som helst finns det ett tal så att det för vilken funktion som helst finns ett sådant $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)

Siffrorna från den slutliga formuleringen kallas van der Waerden-nummer . För dem studeras nedre och övre gränser. $N(r,k)$

Historik

Beviset för teoremet publicerades av B. L. van der Waerden 1927.

Alexander Sofier skriver i sin historiska uppsats om Ramsey-teorin att Schur betraktade satsen som en hypotes när han arbetade med sin sats om talfärgningar (1916), men hypotesen nådde inte van der Waerden från Schur, men uppfanns självständigt av Bode och van der Waerden lärde sig hypotesen av sina elever (Baudet hade redan dött vid den tiden). Beviset uppfanns vid universitetet i Hamburg och presenterades för allmänheten i Berlin på kongressen av German Mathematical Society [3] .

Van der Waerden insåg helt enkelt inte hur viktigt ett resultat han hade bevisat: han skickade in sina uppsatser i algebraisk geometri till den mest prestigefyllda tidskriften Mathematische Annalen och lämnade in detta bevis till den "oförståeliga" tidskriften Nieuw Archief voor Wiskunde från Dutch Mathematical Society .

Originaltext (engelska)[ visaDölj] Van der Waerden insåg helt enkelt inte hur viktigt det resultat han bevisade var: han skickade in sina algebraiska geometripapper till den mest prestigefyllda tidskriften Mathematische Annalen , men skickade ändå detta bevis till en "obskyr" tidskrift, Nieuw Archief voor Wiskunde från Dutch Mathematical Society .

Alexander Khinchin skrev i sin tur att resultatet erhölls i Göttingen sommaren 1928 några dagar före hans ankomst dit och att "en lokal matematiker [...] stötte på hypotesen under sitt vetenskapliga arbete" [4] .

Tvetydigheten i ursprunget till den ursprungliga hypotesen framhålls av Ronald Graham i sin bok om Ramsey-teorin [5] , dock är alla källor överens om att i formuleringen av problemet som van der Waerden löste fanns det bara två färger, och Förstärkning av påståendet till ett godtyckligt antal färger lades till som ett bevisverktyg.

Schema för beviset [6]

I det här avsnittet betecknas påståendet att satsen är sann för färger och progressionslängder som . $r$ $k$ ${\mbox{W}}(r,k)$

Satsen bevisas genom induktion på . Grunden är uppenbar [7] . När man bevisar ett induktionssteg brukar man säga för enkelhetens skull att det är tänkt att bevisas för alla , även om formellt, för att bevisa varje enskilt påstående , är ett ändligt antal påståenden av formen , men med mycket stora värden på , tillräckligt . $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'$

För att garantera närvaron av en enfärgad längdprogression måste man gå från att överväga ett intervall, vars längd garanterar närvaron av en enfärgad längdprogression , till större och större intervall, vilket garanterar närvaron av fler och mer komplexa strukturer - de så kallade fläktarna . För färgning kallar vi -fan en familj av längdförlopp som: $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)$ , det vill säga den sista punkten av alla progressioner är gemensam;
$c({\vec {P}}_{i}(1))=c({\vec {P}}_{i}(2))=\dots =c({\vec {P} }_{i}(k-1)),\ i=1,\dots ,s$ , det vill säga för varje progression är alla element, utom det sista, av samma färg;
$i\not =j\Högerpil c({\vec {P}}_{i}(1))\not =c({\vec {P}}(1))$ , det vill säga huvudfärgen (för alla element utom det sista) är olika för varje progression.

Fläktar kan användas för att bevisa induktionssteget på grund av två uppenbara egenskaper:

närvaron i färgningen av en enfärgad längdprogression betyder faktiskt närvaron av en -fan; $k-1$ $ett$
närvaron av en -fläkt i färgningen garanterar närvaron av en enfärgad progression av längd (eftersom färgerna på alla progressioner är olika och färgerna på allt , då sammanfaller en av dem med färgen på det vanliga sista elementet). $r$ $k$ $r$

Därför räcker det att bevisa ett induktionssteg på en parameter för påståendet "alla färger med ett tillräckligt stort intervall innehåller en -fan eller en längdprogression ". För detta bör du: $s$ $s$ $k$

Bryt ett stort intervall i block - mindre intervall, men också av tillräckligt stor längd (låt oss beteckna ). Värdet måste vara tillräckligt för att säkerställa att det finns en -fläkt i längdintervallen (det vill säga i varje block) (en sådan längd existerar genom induktionshypotesen). $M$ $M$ $M$ $(s-1)$
Tilldela hela uppsättningen av färger av dess element som en "hyperfärg" av blocket. Antalet sådana hyperfärger kommer att vara mycket stort, men fortfarande ändligt. ${\displaystyle r^{M))$
För en "hyperfärgning" av en tillräckligt lång sekvens av block, använd satsen , det vill säga "hitta" en progression av absolut identiskt färgade block. ${\mbox{W}}(r^{M},k-1)$

Detta kommer att garantera närvaron av flera identiska fläktar placerade på samma avstånd från varandra (ett slags fortskridande av fläktar). Om färgen på det centrala elementet i fläkten skiljer sig från färgerna på dess progressioner [8] , är det i en sådan konstruktion möjligt att välja en -fläkt diagonalt (se bilden). $s$ $(s+1)$

Analys av multivariata progressioner

Under den diagonala övergången från progressionen av -fans till -fan förloras ett stort antal aritmetiska och färgkopplingar, i vilka element som inte ingår i -fan deltar. Om vi spårar dessa element och deras duplicering i efterföljande progressioner från -fans, -fans, etc., så kommer det att ses att enfärgade progressioner som härrör från någon -fan faktiskt är diagonaler av enfärgade flerdimensionella progressioner av dimension från till , beroende på "ögonblick" av utseendet av färg under induktion. Därför presenterar vissa författare beviset när det gäller att hitta den lämpliga kombinationen av flerdimensionella progressioner [9] . $s$ $(s+1)$ $(s+1)$ $(s+1)$ $(s+2)$ $s$ $ett$ $s$

Generaliseringar

För van der Waerdens sats har många generaliseringar studerats för olika aspekter av formuleringen av påståendet. Olika typer av generaliseringar kan kombineras i ett påstående.

I detta avsnitt ges endast oändliga formuleringar av generaliserade påståenden, även om det för de flesta av dem finns ändliga analoger konstruerade enligt samma princip som för huvudsatsen.

Sätt att generalisera

Enligt de strukturella villkoren för konfigurationen

Villkoret att siffrorna bildar en aritmetisk progression innebär uppfyllandet av likheterna ${\displaystyle x_{1},\dots ,x_{k))$

x_{i}-x_{i-1}=x_{i+1}-x_{i},\ i=2,\dots ,k-2

Ett sätt att generalisera är att ersätta dessa villkor med andra som också är linjära.

Fråga

För vilka system av linjära ekvationer (inklusive individuella ekvationer) förblir påståendet i van der Waerdens sats sant när villkoret att elementen i den erforderliga konfigurationen bildar en progression ersätts av det faktum att de uppfyller det givna systemet?

Dessutom kan progressionselementen representeras som . Om vi uppfattar skillnaderna som fasta funktioner hos , så leder detta till en polynomgeneralisering. $a,a+d,a+2d,\dots ,a+(k-1)d$ $d,2d,\dots ,(k-1)d$ $d$

Polynomversion

Låta vara polynom med heltalskoefficienter så att . Sedan för alla och det finns färger sådana att ${\displaystyle p_{1},\dots ,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))=\dots =c(a+p_{k}(d))

Bevisidéer [10]

Fläktar kan också användas för att bevisa polynomversionen, men med motsvarande polynomskillnader. Till exempel, när man bevisar närvaron av ett monokromt par i en godtycklig färg, är ett mellansteg att bevisa förekomsten av tal så att de har olika färger och är kvadrater [11] . $a,a+d^{2},\ a,d\in {\mathbb {N} }$ ${\displaystyle x_{0},x_{1},\dots ,x_{s))$ ${\displaystyle x_{1},\dots ,x_{s))$ ${\displaystyle x_{1}-x_{0},\dots ,x_{s}-x_{1))$

Efter dimension

När man generaliserar satsen till flerdimensionella utrymmen, istället för progressioner, beaktas homotetiska bilder av en ändlig uppsättning punkter (en aritmetisk progression motsvarar en homotetisk bild av en diskret hyperkub ).

Flerdimensionell version [12]

För alla naturliga tal finns det uppsättningar och färger sådana som $r,t\in {\mathbb {N} }$ ${\displaystyle K\subset {\mathbb {N} }^{t))$ ${\displaystyle c:{\mathbb {N} }^{t}\to \{1,\dots ,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

En bredare, rent kombinatorisk, flerdimensionell generalisering erbjuds av Hales-Jewetts sats. För enkelhetens skull kan det förstås som en färgsats , men operationer med siffror används inte alls i den, det vill säga uppsättningen kan ersättas med någon annan av samma storlek. Här fungerar rummets dimension som en föränderlig ("tillräckligt stor") parameter , så Hales-Jewett-satsen har bara en ändlig formulering. ${\displaystyle [k]^{n))$ $[k]$

Definition

För en kombinatorisk linjeuppsättning i diagonalen för en icke-trivial subkub kallas, det vill säga mängden av alla vektorer, där några av koordinaterna kan fixeras, och resten (antal som inte är noll) är alltid desamma och körs genom alla värderingar . $A$ $A^{n}$ $a\i A$

Hales-Jewett teorem [13]

För varje finns det ett antal så att det för varje färg finns en monokromatisk kombinatorisk linje. $k,r\in {\mathbb {N} }$ $n_{0}=n_{0}(r,k)$ $n>n_{0},\ |A|=k$ $c:A^{n}\to [r]$

Bevisidéer

Beviset för Hales–Jewett-satsen är baserat på samma induktion via fläktar. För en vektor betraktas en partition av koordinater . I en hyperfärgning , där hyperfärgen av vektorn är en kombination av färger av alla punkter i formen , för tillräckligt stor är det möjligt, genom det induktiva antagandet (c ), att hitta en kombinatorisk linje, där alla element utom en kommer att vara av samma färg. För färgläggning kommer detta att betyda närvaron av en sådan "linje" av identiskt färgade delrum av dimension . Och för stora är närvaron av en liknande rak linje i var och en av dessa underutrymmen garanterad. Det visar sig "en rak linje från raka linjer", som var och en har samma fortsättning. Denna konstruktion liknar konstruktionen av generaliserade progressioner från beviset för van der Waerdens teorem och kan användas för att konstruera fläktar på samma sätt som [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-satsen följer av Hales-Jewett-satsen, eftersom omvandlingen från till , motsvarande tolkningen av koordinater som siffror i -ärt talsystem , kartlägger kombinatoriska linjer i aritmetiskt progression [15] . Den flerdimensionella van der Waerden-satsen kan härledas på liknande sätt genom att fixera valfri numrering av element och beakta Hales-Jewett-satsen för [16] . ${\displaystyle [k]^{n))$ $[k^{n}]$ $k$ $K$ $k=|K|$

Den flerdimensionella satsen kan också bevisas direkt, utan Hales–Jewett-satsen. Faktum är att om det bevisas för en delmängd som innehåller affinoberoende punkter, så kan vi tillämpa induktion från till med hjälp av fans från van der Waerdens satser, men med en uppdelning i flerdimensionella block. Därför räcker det att presentera ett sätt att gå från ett uttalande för till ett uttalande för en uppsättning affinoberoende punkter. Som ett exempel på detta kan du ta ett hörn, det vill säga punkter i formuläret ${\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},\dots ,a_{t})

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

\prickar

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

Närvaron av ett -dimensionellt hörn i hyperplanet med tillståndet (vilket garanteras för tillräckligt stort ) betyder närvaron av ett hörn där alla punkter, utom den centrala, är av samma färg. Vidare, genom att dela upp siffrorna i flerdimensionella block och tillämpa samma procedur på dem, kan man bygga godtyckligt stora fläktar från sådana hörn. $(t-1)$ ${\displaystyle {\mathbb {R} }^{t))$ $a_{1}+\dots +a_{t}=N$ $N$ ${\displaystyle {\mathbb {R} }^{t))$

En färg (täta delmängder)

Från empiriska överväganden är det naturligt att anta att den önskade enfärgade konfigurationen av siffror i de flesta fall kommer att ha den mest populära färgen, eftersom ju fler nummer av en eller annan färg, desto mer intressanta konfigurationer kan uppstå mellan dem.

Även om det är rimligt, följer detta påstående inte direkt från van der Waerdens sats och är mycket svårare att bevisa. För att formalisera det bör det noteras att i den slutliga färgningen har den mest populära färgen en positiv övre densitet [17] . Därför betyder det angivna antagandet närvaron av en progression i vilken tät uppsättning som helst. Denna sats är uppkallad efter Endre Szemeredy , som först bevisade det.

Szemeredis sats

För varje och en uppsättning sådan att , det finns sådan att . ${\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,\dots ,a+(k-1)d\in A$

I analogi med van der Waerden siffror, för den finita versionen av Szémerédys sats, studerar vi nedre och övre gränser för , tillräckligt för att uppsättningen med villkoret alltid innehåller en progression av längd . Att få sådana uppskattningar i ärendet är mycket svårare än i fallet med . $N(\delta ,k)$ $A\subset [N]$ $|A|>\delta N$ $k$ $k\geq 4$ $k=3$

Bevisidéer

Metoderna för att bevisa Szemeredis sats skiljer sig slående från van der Waerdens sats både i typ och i komplexitet. Kombinatoriska (med Szemeredis regelbundenhetslemma från allmän grafteori ), analytiska (med Fourier-koefficienter och Gowers-normer som generaliserar dem ) och ergodiska bevis är kända.

För att bevisa de bredaste generaliseringarna (med tillägg av polynomskillnader och multidimensionalitet av rymden) fungerar den ergodiska teorins metoder bra, men de ger inga kvantitativa uppskattningar för de slutliga formuleringarna [18] .

Till ett oändligt antal färger

Med ett räknebart antal färger, det vill säga färgning , kanske det inte blir långa enfärgsförlopp [19] . Men om vi betraktar konfigurationer där färgerna på alla element är olika som en annan, också tillåten, pol av färgstruktur, så förblir satsen sann. $c:{\mathbb {N} }\to {\mathbb {N} }$

Detta påstående kallas den kanoniska versionen av van der Waerdens sats.

Kanonisk version

För alla färger och det finns siffror som: $k\in {\mathbb {N} }$ $c:{\mathbb {N} }\to {\mathbb {N} }$ $a,d\in {\mathbb {N} }$

eller $c(a)=c(a+d)=\dots =c(a+(k-1)d)$
eller för någon $c(a+id)\not=c(a+jd)$ $0\leq i<j<k$

Bevisidéer

Erdős och Graham var de första att notera att den kanoniska versionen följer av Szemeredis sats [20] . Därefter generaliserades denna idé till det flerdimensionella fallet [21] . Szémeredys sats i sig är dock svår att bevisa, så senare hittades ytterligare ett, elementärt bevis för den kanoniska versionen genom en flerdimensionell version av den vanliga van der Waerden-satsen [22] .

Enligt färgningen kan man konstruera en färgning av planet , där färgen på paret är associerad med progressionen , nämligen motsvarar uppdelningen av progressionen med likheten av färger. Till exempel kommer par för vilka motsvarande förlopp är färgade (röd, röd, grön) och (blå, blå, gul) att ha samma färg i . Det är viktigt att antalet färger är begränsat . $c:{\mathbb {N} }\to {\mathbb {N} }$ $c'$ $(a,d)\in {\mathbb {N} }^{2}$ $a,a+d,\dots ,a+(k-1)d$ $(c(a),c(a+d),\dots ,c(a+(k-1)d))$ $c'$ $c'$

Om det inte finns några flerfärgade längdförlopp , har varje framsteg minst två element av samma färg. Genom den flerdimensionella van der Waerden-satsen finns det en enfärgad homotetisk bild i färgningen . Progressionerna som motsvarar punkterna i denna bild kommer att skära varandra på ett sådant sätt att det, genom att kombinera dessa likheter, är möjligt att visa monokromaticiteten hos element från olika progressioner, och det kommer att finnas så många av dem att dessa element bildar sin egen progression av längd , helt monokromatisk, vilket krävs av tillståndet. $c$ $k$ $c'$ $[(k-1)^{2}]^{2}$ $k$

Sammanfattningstabell med några resultat

Aritmetiska förhållanden till önskad struktur	Sökområde	Plats
		en-dimensionell	Flerdimensionell	$A^{n}$ för finalen $A$
Aritmetiska progressioner	ultimat färgläggning	Van der Waerdens sats	Witt, 1952	Hales–Jewett teorem
	Ändlös färgläggning	Promel, Rodl, 1986		Teoremet har endast slutlig formulering
	tät delmängd	Szemeredis sats (inklusive Roths teorem )	Hörnsats	Känd stark generaliseringar av Roths teorem
Lösningar av linjära ekvationer eller ekvationssystem	ultimat färgläggning	Rados sats Schurs teorem
	Ändlös färgläggning	Lefmann, 1986		Teoremet har endast slutlig formulering
	tät delmängd	Vissa är kända generaliseringar av Roths teorem [23] [24]
Betydelsen av polynom i skillnader	ultimat färgläggning	Walters, 2000
	Ändlös färgläggning	Girao, 2020 Fox, Wigderson, Zhao, 2020		Teoremet har endast slutlig formulering
	tät delmängd	Bergelson, Leibman, 1996
	tät delmängd	Bevisas med separata metoder Furstenberg-Sharkozys teorem [25] och Roths andragradssats [26]

Litteratur

I. D. Shkredov. Szemeredis sats och problem om aritmetiska progressioner // Uspekhi matematicheskikh nauk. - 2006. - T. 61 , nr. 6 . — s. 111–178 . (ryska)

A. Soifer. Ramsey Theory : Igår, idag och imorgon . — Boston: Birkhäuser, 2011. — 189 sid. - ISBN 978-0-8176-8091-6 .

A. Ya. Khinchin. Tre pärlor av talteori . - Moskva: "Nauka", 1979. - 66 s. (ryska)

M. Walters. Kombinatoriska bevis för polynomet van der Waerden-satsen och polynomets Hales-Jewett-sats // Journal of the London Mathematical Society. - 2000. - Vol. 61 , iss. 1 . — S. 1–12 .

V. Bergelson, A. Leibman. Polynomförlängningar av van der Waerdens och Szemerédis satser // Journal of the American Mathematical Society. - 1996. - Vol. 9 , iss. 3 . — S. 725–753 .

R. Graham. Början av Ramseys teori . - Moskva: "Mir", 1984. - 97 sid. (ryska)

P. Erdős, R.L. Graham. Gamla och nya problem och resultat i kombinatorisk talteori // L'Enseignement Mathematique. - 1980. - Vol. 25 . — S. 325–344 .

W. Deuber, R.L. Graham, H.J. Promel, B. Voigt. Ett kanoniskt partitionsteorem för ekvivalensrelationer på ${\displaystyle {\mathbb {Z} }^{t))$ (engelska) // Journal of Combinatorial Theory, Series A. - 1983. - Vol. 34 , iss. 3 . — S. 331–339 .

HJ Promel, V. Rodl. Ett elementärt bevis på den kanoniserande versionen av Gallai-Witts teorem (engelska) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 42 , iss. 1 . — S. 144–149 .

RL Graham, BL Rothschild, JH Spencer. Ramsey teori . - 2:a upplagan - A wiley-interscience-publikation, 1990. - 196 sid. - ISBN 0-471-50046-1 .

H. Lefmann. En kanonisk version för uppdelning av reguljära system av linjära ekvationer (engelska) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 41 , iss. 1 . — S. 95–104 .

E. Witt. Ein kombinatorischer Satz der Elementargeometrie (tyska) // Mathematishe Nachrichten. — 1952.

A. Girao. Ett kanoniskt polynom Van der Waerdens sats . - 2020. - arXiv : 2004.07766 .

J. Fox, Y. Wigderson, Y. Zhao. Ett kort bevis på det kanoniska polynomet van der Waerdens sats . - 2020. - arXiv : 2005.04135 .

S. Peluse, S. Prendiville. En polylogaritmisk bunden i den olinjära Roth-satsen . - 2020. - arXiv : 2003.04122 .

N. Lyall. Ett nytt bevis på Sarkozys teorem // Proceedings of the American Mathematical Society. - 2011. - Vol. 141 , iss. 7 . - arXiv : 1107.0243 .

T. Schoen, ID Shkredov. Roths sats i många variabler // Israel Journal of Mathematics. - 2014. - Vol. 199 . — S. 287–308 . - arXiv : 1106.1601 .

T. Schoen, O. Sisask. Roths sats för fyra variabler och additiva strukturer i summor av glesa mängder // Forum of Mathematics, Sigma. - 2016. - Vol. 4 . - arXiv : 1408.2568 .

Anteckningar

↑ Shkredov, 2006 , sid. 112-114
↑ Graham, 1984 , sid. arton.
↑ Soifer, 2011 , sid. 2.7.
↑ Khinchin, 1979 , sid. 7-8.
↑ Graham, 1984 , sid. 17.
↑ Se olika presentationer i Khinchin, 1979 , sid. 9-13, Graham, 1984 , sid. 18-21, Shkredov, 2006 , sid. 118-119
↑ Det räcker med att ta siffror så att det enligt Dirichlet-principen finns två siffror av samma färg bland dem. $r+1$
↑ Annat skulle betyda närvaron av en längdförlopp , och då finns det inget att bevisa $k$
↑ Khinchin, 1979 , sid. 9-13, se formel (5) och nästa stycke, där det finns en övergång till övervägandet av den -e progressionen av -fläkten $r$ $s$
↑ Med utvecklingen av studiet av Szemeredys teorem användes effektiva metoder för ergodisk teori aktivt för att bevisa dess polynomgeneraliseringar (se Bergelson, Leibman, 1996 ). Ett elementärt bevis på en polynomgeneralisering utan kombination med en generalisering som Szemerédys teorem publicerades senare.
↑ Walters, 2000 , se "Induktionshypotes" på sid. 3
↑ Kallas ofta "Gallai-Witt's theorem" i engelsk litteratur.
↑ Graham, 1984 , sid. 24.
↑ Graham, 1984 , sid. 24-25.
↑ Graham, 1984 , sid. 26.
↑ Graham, Rothschild, Spencer, 1990 , sid. 40-41.
↑ Och dessutom är den övre densiteten inte mindre än , där är antalet färger $1/r$ $r$
↑ Bergelson, Leibman, 1996 .
↑ Du kan till exempel färglägga varje nummer i din egen färg, det vill säga tilldela $c(x):=x$
↑ Erdős, Graham, 1980 , sid. 333, se "Förekomsten av garanteras av Szemerédis teorem." $H(n)$
↑ Deuber, Graham, Promel, Voigt, 1983 .
↑ Promel, Rödl, 1986 .
↑ Schoen, Shkredov, 2014 .
↑ Schoen, Sisask, 2016 .
↑ Lyall, 2011 .
↑ Peluse, Prendiville, 2020 .