Van der Waerdens sætning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. december 2018; checks kræver 8 redigeringer .

Van der Waerdens sætning er et klassisk resultat af kombinatorisk talteori om monokromatiske aritmetiske progressioner i farver af naturlige tal . Sætningen er en typisk redegørelse for Ramseys teori , såvel som en forløber for Szemeredis sætning , som markerede begyndelsen på en stor gren af additiv kombinatorik .

Notation

Gennem hele artiklen bruges notationen til at betegne et sæt . Denne betegnelse er ret almindelig i litteraturen. $\{1,\dots ,N\}$ $[N]$

Ordlyd

Sætningen har to ækvivalente formuleringer - finit og uendelig [1] .

Uendelig formulering

For enhver og funktioner , der findes sådan, at $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 kaldes normalt en farvning af naturlige tal, dens værdier er farver af tal, og en progression er enfarvet (sætningen specificerer ikke hvilken farve dens elementer har). $c$ $a,a+d,\dots ,a+(k-1)d$

Den endelige formulering ligner den uendelige, men betragter en farvning af et endeligt sæt. Den tilhører O. Schreier [2] .

Endelig formulering

For enhver eksisterer der et tal , således at der for enhver funktion eksisterer sådan $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)

Tallene fra den endelige formulering kaldes van der Waerden-numre . For dem studeres nedre og øvre grænser. $N(r,k)$

Historie

Beviset for teoremet blev offentliggjort af B. L. van der Waerden i 1927.

Alexander Sofier skriver i sit historiske essay om Ramsey-teorien, at Schur betragtede udsagnet om sætningen som en hypotese, da han arbejdede på sin sætning om talfarvninger (i 1916), men hypotesen nåede ikke van der Waerden fra Schur, men blev uafhængigt opfundet af Bode og van der Waerden lærte hypotesen af sine elever (Baudet var allerede død på det tidspunkt). Beviset blev opfundet på universitetet i Hamburg og præsenteret for offentligheden i Berlin på kongressen i det tyske matematiske selskab [3] .

Van der Waerden var ganske enkelt ikke klar over, hvor vigtigt et resultat han havde bevist: han indsendte sine artikler i algebraisk geometri til det mest prestigefyldte tidsskrift, Mathematische Annalen , og indsendte dette bevis til det "uforståelige" tidsskrift Nieuw Archief voor Wiskunde fra det hollandske matematiske samfund .

Originaltekst (engelsk)[ Visskjule] Van der Waerden var ganske enkelt ikke klar over, hvor vigtigt det resultat, han beviste, var: han indsendte sine algebraiske geometripapirer til det mest prestigefyldte tidsskrift, Mathematische Annalen , men sendte alligevel dette bevis til et "obskurt" tidsskrift, Nieuw Archief voor Wiskunde fra Dutch Mathematical Society .

Til gengæld skrev Alexander Khinchin , at resultatet blev opnået i Göttingen i sommeren 1928 et par dage før hans ankomst der, og at "en lokal matematiker [...] stødte på hypotesen i løbet af sit videnskabelige arbejde" [4] .

Tvetydigheden af oprindelsen af den oprindelige hypotese understreges af Ronald Graham i sin bog om Ramsey-teorien [5] , dog er alle kilder enige om, at i formuleringen af det problem, som van der Waerden løste, var der kun to farver, og styrkelse af påstanden til et vilkårligt antal farver blev tilføjet som et bevisværktøj.

Skema for beviset [6]

I dette afsnit er påstanden om, at sætningen er sand for farver og progressionslængder , betegnet som . $r$ $k$ ${\mbox{W}}(r,k)$

Sætningen bevises ved induktion på . Grundlaget er indlysende [7] . Når man beviser et induktionstrin, siges det normalt for nemheds skyld, at det formodes at være bevist for alle , selvom formelt, for at bevise hver enkelt udsagn , er et begrænset antal udsagn af formen , men med meget store værdier på, tilstrækkeligt . $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'$

For at garantere tilstedeværelsen af en ensfarvet længdeprogression skal man gå fra at overveje et interval, hvis længde garanterer tilstedeværelsen af en ensfarvet længdeprogression , til større og større intervaller, hvilket garanterer tilstedeværelsen af flere og mere komplekse strukturer - de såkaldte fans . Til farvning kalder vi -fan en familie af længdeforløb, sådan at: $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 vil sige, at det sidste punkt i alle progressioner er fælles;
$c({\vec {P}}_{i}(1))=c({\vec {P}}_{i}(2))=\dots =c({\vec {P} }_{i}(k-1)),\ i=1,\dots ,s$ , det vil sige, at for hver progression er alle elementer, undtagen det sidste, af samme farve;
$i\not =j\Rightarrow c({\vec {P}}_{i}(1))\not =c({\vec {P}}(1))$ , det vil sige, at hovedfarven (af alle elementer undtagen det sidste) er forskellig for hver progression.

Ventilatorer kan bruges til at bevise induktionstrinnet på grund af to åbenlyse egenskaber:

tilstedeværelsen i farvningen af en enfarvet progression af længde betyder faktisk tilstedeværelsen af en -fan; $k-1$ $en$
tilstedeværelsen af en -fan i farvningen garanterer tilstedeværelsen af en enfarvet progression af længden (da farverne på alle progressioner er forskellige og farverne på alt , så falder en af dem sammen med farven på det fælles sidste element). $r$ $k$ $r$

Derfor er det tilstrækkeligt at bevise et induktionstrin på en parameter for udsagnet "enhver farvning af et tilstrækkeligt stort interval indeholder en -fan eller en længdeprogression ". Til dette skal du: $s$ $s$ $k$

Bryd et stort interval i blokke - mindre intervaller, men også af en tilstrækkelig stor længde (lad os betegne ). Værdien skal være tilstrækkelig til at sikre , at der er en -fan i længdeintervallerne (det vil sige i hver blok) (en sådan længde eksisterer ved induktionshypotesen). $M$ $M$ $M$ $(s-1)$
Tildel hele sættet af farver af dets elementer som en "hyperfarve" af blokken. Antallet af sådanne hyperfarver vil være meget stort, men stadig begrænset. ${\displaystyle r^{M))$
For en "hyperfarvning" af en tilstrækkelig lang række af blokke skal du anvende sætningen , dvs. "finde" en progression af absolut identisk farvede blokke. ${\mbox{W}}(r^{M},k-1)$

Dette vil garantere tilstedeværelsen af flere identiske blæsere placeret i samme afstand fra hinanden (en slags progression af blæsere). Hvis farven på det centrale element af blæseren adskiller sig fra farverne på dens progressioner [8] , så er det i en sådan konstruktion muligt at vælge en -fan diagonalt (se billedet). $s$ $(s+1)$

Analyse af multivariate progressioner

Under den diagonale overgang fra progressionen af -fans til -fanen tabes et stort antal aritmetiske og farveforbindelser, hvori elementer, der ikke indgår i -fanen, deltager. Hvis vi sporer disse elementer og deres duplikering i efterfølgende progressioner fra -fans, -fans osv., så vil det ses, at en-farvede progressioner, der udgår fra en hvilken som helst -fan, faktisk er diagonaler af en-farve multidimensionelle progressioner af dimension fra til , afhængigt af "øjeblikket" for udseendet af farve under induktion. Derfor præsenterer nogle forfattere beviset i forhold til at finde den passende kombination af multidimensionelle progressioner [9] . $s$ $(s+1)$ $(s+1)$ $(s+1)$ $(s+2)$ $s$ $en$ $s$

Generaliseringer

For van der Waerdens sætning er mange generaliseringer blevet undersøgt for forskellige aspekter af formuleringen af udsagnet. Forskellige typer af generaliseringer kan kombineres i et udsagn.

I dette afsnit er der kun givet endeløse formuleringer af generaliserede udsagn, selvom der for de fleste af dem er endelige analoger konstrueret efter samme princip som for hovedsætningen.

Måder at generalisere

Ifølge de strukturelle betingelser for konfigurationen

Betingelsen om, at tallene danner en aritmetisk progression, betyder opfyldelsen af lighederne ${\displaystyle x_{1},\dots ,x_{k))$

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

En måde at generalisere på er at erstatte disse forhold med andre, der også er lineære.

Spørgsmål

For hvilke systemer af lineære ligninger (inklusive individuelle ligninger) forbliver udsagnet af van der Waerdens sætning sand, når betingelsen om, at elementerne i den nødvendige konfiguration danner en progression, erstattes af, at de opfylder det givne system?

Derudover kan progressionselementerne repræsenteres som . Hvis vi opfatter forskellene som faste funktioner af , så fører dette til en polynomiel generalisering. $a,a+d,a+2d,\dots,a+(k-1)d$ $d,2d,\dots ,(k-1)d$ $d$

Polynomisk version

Lade være polynomier med heltalskoefficienter sådan, at . Så for enhver og der er farvestoffer sådan ${\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))

Bevisideer [10]

Fans kan også bruges til at bevise polynomieversionen, men med tilsvarende polynomielle forskelle. For eksempel, når man beviser tilstedeværelsen af et monokromt par i en vilkårlig farve, er et mellemtrin at bevise eksistensen af tal, således at de har forskellige farver og er 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 generaliserer sætningen til multidimensionelle rum, i stedet for progressioner, overvejes homotetiske billeder af et endeligt sæt punkter (en aritmetisk progression svarer til et homotetisk billede af en diskret hyperkube ).

Multidimensionel version [12]

For alle naturlige tal er der sæt og farvestoffer sådan $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 bredere, rent kombinatorisk, multidimensionel generalisering tilbydes af Hales-Jewett-sætningen. For nemheds skyld kan det forstås som et farvesætningssætning , men operationer med tal bruges slet ikke i det, det vil sige, at sættet kan erstattes af enhver anden af samme størrelse. Her fungerer rummets dimension som en foranderlig ("tilstrækkelig stor") parameter , så Hales-Jewett-sætningen har kun en endelig formulering. ${\displaystyle [k]^{n))$ $[k]$

Definition

For et kombinatorisk linjesæt i diagonalen af enhver ikke-trivial subkube kaldes, det vil sige, at sættet af alle vektorer, hvor nogle af koordinaterne kan fikseres, og resten (ikke-nul tal) altid er de samme og køres gennem alle værdier . $EN$ $A^{n}$ $a\i A$

Hales-Jewett sætning [13]

For enhver eksisterer der et tal , således at der for enhver i enhver farve eksisterer 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]$

Bevis ideer

Beviset for Hales-Jewett-sætningen er baseret på den samme induktion via blæsere. For en vektor betragtes en partition af koordinater . I en hyperfarvning , hvor hyperfarven af vektoren er en kombination af farver af alle punkter i formen , for tilstrækkelig stor er det muligt ved den induktive antagelse (c ), at finde en kombinatorisk linje, hvor alle elementer undtagen et vil være af samme farve. For farvning vil dette betyde tilstedeværelsen af en sådan "linje" af identisk farvede underrum af dimension . Og for store er tilstedeværelsen af en lignende lige linje i hvert af disse underrum garanteret. Det viser sig "en lige linje fra lige linjer", som hver har den samme fortsættelse. Denne konstruktion ligner konstruktionen af generaliserede progressioner fra beviset for van der Waerdens sætning og kan bruges til at konstruere ventilatorer på samme måde som [14] . ${\vec {a}}\in A^{n}$ ${\vec {a}}=({\vec {a_{1}}},{\vec {a_{2}}})\in A^{n_{1}}\time 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-sætningen følger af Hales-Jewett-sætningen, da transformationen fra til , svarende til fortolkningen af koordinater som cifre i -ært talsystem , kortlægger kombinatoriske linjer i aritmetisk progression [15] . Den multidimensionelle van der Waerden-sætning kan udledes på samme måde ved at fastsætte en hvilken som helst nummerering af elementer og overveje Hales-Jewett-sætningen for [16] . ${\displaystyle [k]^{n))$ $[k^{n}]$ $k$ $K$ $k=|K|$

Den multidimensionelle sætning kan også bevises direkte uden Hales-Jewett-sætningen. Faktisk, hvis det er bevist for en delmængde , der indeholder affin-uafhængige punkter, så kan vi anvende induktion fra til ved hjælp af fans fra van der Waerdens sætninger, men med en opdeling i flerdimensionelle blokke. Derfor er det tilstrækkeligt at præsentere en måde at gå fra et udsagn for til et udsagn for et sæt affin-uafhængige punkter. Som et eksempel på dette kan du tage et hjørne, det vil sige punkter i formularen ${\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})

\prikker

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

Tilstedeværelsen af et -dimensionelt hjørne i hyperplanet med betingelsen (som er garanteret for tilstrækkelig stor ) betyder tilstedeværelsen af et hjørne, hvor alle punkter, undtagen det centrale, er af samme farve. Yderligere, ved at opdele tallene i flerdimensionelle blokke og anvende den samme procedure på dem, kan man bygge vilkårligt store blæsere fra sådanne hjørner. $(t-1)$ ${\displaystyle {\mathbb {R} }^{t))$ $a_{1}+\dots +a_{t}=N$ $N$ ${\displaystyle {\mathbb {R} }^{t))$

Én farve (tætte undersæt)

Ud fra empiriske overvejelser er det naturligt at antage, at den ønskede ensfarvede konfiguration af tal i de fleste tilfælde vil have den mest populære farve, fordi jo flere numre af en eller anden farve, jo mere interessante konfigurationer kan der opstå mellem dem.

Selvom det er plausibelt, følger denne påstand ikke direkte af van der Waerdens sætning og er meget sværere at bevise. For at formalisere det skal det bemærkes, at i den endelige farvning har den mest populære farve en positiv øvre tæthed [17] . Derfor betyder den angivne antagelse tilstedeværelsen af en progression i ethvert tæt sæt. Denne sætning er opkaldt efter Endre Szemeredy , som først beviste det.

Szemeredis sætning

For enhver og et sæt sådan at , der findes sådan at . ${\displaystyle \delta \in (0;1),k\in {\mathbb {N} ))$ $EN$ $\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-tallene, for den endelige version af Szémerédys sætning, studerer vi nedre og øvre grænser for , tilstrækkeligt til at sættet med betingelsen altid indeholder en progression af længden . At opnå sådanne skøn i sagen er meget vanskeligere end i tilfældet . $N(\delta ,k)$ $A\subset [N]$ $|A|>\delta N$ $k$ $k\geq 4$ $k=3$

Bevis ideer

Metoderne til at bevise Szemeredis sætning er slående forskellige fra van der Waerdens sætning både i type og kompleksitet. Kombinatorisk (ved hjælp af Szemeredi-regularitetslemmaet fra generel grafteori ), analytiske (ved hjælp af Fourier-koefficienter og Gowers-normer, der generaliserer dem ) og ergodiske beviser er kendte.

For at bevise de bredeste generaliseringer (med tilføjelse af polynomielle forskelle og multidimensionalitet af rummet) fungerer den ergodiske teoris metoder godt, men de giver ikke nogen kvantitative skøn for de endelige formuleringer [18] .

Til et uendeligt antal farver

Med et tælleligt antal farver, det vil sige farvelægning , er der muligvis ikke lange enfarvede progressioner [19] . Men hvis vi betragter konfigurationer, hvor farverne på alle elementer er forskellige, som en anden, også tilladelig, farvestrukturpol, så forbliver sætningen sand. $c:{\mathbb {N} }\to {\mathbb {N} }$

Dette udsagn kaldes den kanoniske version af van der Waerdens sætning.

Kanonisk version

For enhver farve, og der er tal , 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 for enhver $c(a+id)\not=c(a+jd)$ $0\leq i<j<k$

Bevis ideer

Erdős og Graham var de første til at bemærke, at den kanoniske version følger af Szemeredis sætning [20] . Efterfølgende blev denne idé generaliseret til det multidimensionelle tilfælde [21] . Selve Szémeredys sætning er dog svær at bevise, så senere blev endnu et, elementært bevis for den kanoniske version fundet gennem en flerdimensionel version af den sædvanlige van der Waerden-sætning [22] .

Ifølge farvningen kan man konstruere en farvning af planet , hvor farven på parret er forbundet med progressionen , nemlig svarer til opdelingen af progressionen efter ensartethed af farver. For eksempel vil par, for hvilke de tilsvarende progressioner er farvet (rød, rød, grøn) og (blå, blå, gul), have samme farve i . Det er vigtigt, at antallet af farver er begrænset . $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'$

Hvis der ikke er flerfarvede forløb af længde , så har enhver forløb mindst to elementer af samme farve. Ved den multidimensionelle van der Waerden-sætning er der et enfarvet homotetisk billede i farvelægningen . Progressionerne, der svarer til punkterne i dette billede, vil skære hinanden på en sådan måde, at det ved at kombinere disse ligheder er muligt at vise monokromaticiteten af elementer fra forskellige progressioner, og der vil være så mange af dem, at disse elementer danner deres egen progression af længde , fuldstændig monokromatisk, hvilket kræves af betingelsen. $c$ $k$ $c'$ $[(k-1)^{2}]^{2}$ $k$

Oversigtstabel med nogle resultater

Aritmetiske forhold til den ønskede struktur	Søgeområde	Plads
		endimensionel	Multidimensionel	$A^{n}$ til finalen $EN$
Aritmetiske progressioner	ultimativ farvelægning	Van der Waerdens sætning	Witt, 1952	Hales-Jewett-sætning
	Uendelig farvelægning	Promel, Rodl, 1986		Sætningen har kun den endelige formulering
	tæt delmængde	Szemeredis sætning (inklusive Roths sætning )	Hjørnesætning	Kendt stærk generaliseringer af Roths sætning
Løsninger af lineære ligninger eller ligningssystemer	ultimativ farvelægning	Rados sætning Schurs sætning
	Uendelig farvelægning	Lefmann, 1986		Sætningen har kun den endelige formulering
	tæt delmængde	Nogle er kendte generaliseringer af Roths teorem [23] [24]
Betydning af polynomier i forskelle	ultimativ farvelægning	Walters, 2000
	Uendelig farvelægning	Girao, 2020 Fox, Wigderson, Zhao, 2020		Sætningen har kun den endelige formulering
	tæt delmængde	Bergelson, Leibman, 1996
	tæt delmængde	Bevist ved separate metoder Furstenberg-Sharkozy teorem [25] og Roths andengradssætning [26]

Litteratur

I. D. Shkredov. Szemeredis teorem og problemer om aritmetiske progressioner // Uspekhi matematicheskikh nauk. - 2006. - T. 61 , no. 6 . — s. 111–178 . (Russisk)

A. Soifer. Ramsey Theory : I går, i dag og i morgen . — Boston: Birkhäuser, 2011. — 189 s. - ISBN 978-0-8176-8091-6 .

A. Ya. Khinchin. Tre perler af talteori . - Moskva: "Nauka", 1979. - 66 s. (Russisk)

M. Walters. Kombinatoriske beviser for polynomiets van der Waerden-sætning og polynomiets Hales-Jewett-sætning // Journal of the London Mathematical Society. - 2000. - Vol. 61 , udg. 1 . — S. 1–12 .

V. Bergelson, A. Leibman. Polynomiske udvidelser af van der Waerdens og Szemerédis sætninger // Journal of the American Mathematical Society. - 1996. - Bd. 9 , iss. 3 . — S. 725–753 .

R. Graham. Begyndelsen af Ramseys teori . - Moskva: "Mir", 1984. - 97 s. (Russisk)

P. Erdős, R. L. Graham. Gamle og nye problemer og resultater i kombinatorisk talteori // L'Enseignement Mathematique. - 1980. - Bd. 25 . — S. 325–344 .

W. Deuber, R. L. Graham, H. J. Promel, B. Voigt. Et kanonisk partitionsteorem for ækvivalensrelationer på ${\displaystyle {\mathbb {Z} }^{t))$ (engelsk) // Journal of Combinatorial Theory, Series A. - 1983. - Vol. 34 , udg. 3 . — S. 331–339 .

HJ Promel, V. Rodl. Et elementært bevis på den kanoniserende version af Gallai-Witts teorem (engelsk) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 42 , udg. 1 . — S. 144–149 .

RL Graham, BL Rothschild, JH Spencer. Ramsey teori . - 2. udgave - A wiley-interscience publikation, 1990. - 196 s. - ISBN 0-471-50046-1 .

H. Lefmann. En kanonisk version til opdeling af regulære systemer af lineære ligninger (engelsk) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 41 , udg. 1 . — S. 95–104 .

E. Witt. Ein kombinatorischer Satz der Elementargeometrie (tysk) // Mathematishe Nachrichten. - 1952.

A. Girao. Et kanonisk polynomium Van der Waerdens sætning . - 2020. - arXiv : 2004.07766 .

J. Fox, Y. Wigderson, Y. Zhao. Et kort bevis på det kanoniske polynomium van der Waerden-sætning . - 2020. - arXiv : 2005.04135 .

S. Peluse, S. Prendiville. En polylogaritmisk bundet i den ikke-lineære Roth-sætning . - 2020. - arXiv : 2003.04122 .

N. Lyall. Et nyt bevis for Sarkozys teorem // Proceedings of the American Mathematical Society. - 2011. - Bd. 141 , udg. 7 . - arXiv : 1107.0243 .

T. Schoen, ID Shkredov. Roths sætning i mange variable // Israel Journal of Mathematics. - 2014. - Bd. 199 . — S. 287–308 . - arXiv : 1106.1601 .

T. Schoen, O. Sisask. Roths teorem for fire variable og additive strukturer i summer af sparsomme mængder // Forum of Mathematics, Sigma. - 2016. - Bd. 4 . - arXiv : 1408.2568 .

Noter

↑ Shkredov, 2006 , s. 112-114
↑ Graham, 1984 , s. atten.
↑ Soifer, 2011 , s. 2.7.
↑ Khinchin, 1979 , s. 7-8.
↑ Graham, 1984 , s. 17.
↑ Se forskellige præsentationer i Khinchin, 1979 , s. 9-13, Graham, 1984 , s. 18-21, Shkredov, 2006 , s. 118-119
↑ Det er nok at tage tal, så der ifølge Dirichlet-princippet er to tal af samme farve blandt dem. $r+1$
↑ Andet ville betyde tilstedeværelsen af en progression af længden , og så er der intet at bevise $k$
↑ Khinchin, 1979 , s. 9-13, se formel (5) og næste afsnit, hvor der er en overgang til hensynet til -blæserens - . $r$ $s$
↑ Med udviklingen af studiet af Szemeredys sætning blev effektive metoder til ergodisk teori aktivt brugt til at bevise dens polynomielle generaliseringer (se Bergelson, Leibman, 1996 ). Et elementært bevis for en polynomial generalisering uden kombination med en generalisering som Szemerédys sætning blev offentliggjort senere.
↑ Walters, 2000 , se "Induktionshypotese" på s. 3
↑ Kaldes ofte "Gallai-Witts sætning" i engelsk litteratur.
↑ Graham, 1984 , s. 24.
↑ Graham, 1984 , s. 24-25.
↑ Graham, 1984 , s. 26.
↑ Graham, Rothschild, Spencer, 1990 , s. 40-41.
↑ Og desuden er den øvre tæthed ikke mindre end , hvor er antallet af farver $1/r$ $r$
↑ Bergelson, Leibman, 1996 .
↑ For eksempel kan du farve hvert nummer i din egen farve, det vil sige tildele $c(x):=x$
↑ Erdős, Graham, 1980 , s. 333, se "Eksistensen af er garanteret af Szemerédis sætning." $H(n)$
↑ Deuber, Graham, Promel, Voigt, 1983 .
↑ Promel, Rödl, 1986 .
↑ Schoen, Shkredov, 2014 .
↑ Schoen, Sisask, 2016 .
↑ Lyall, 2011 .
↑ Peluse, Prendiville, 2020 .