Teorema lui Van der Waerden

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 decembrie 2018; verificările necesită 8 modificări .

Teorema lui Van der Waerden este un rezultat clasic al teoriei numerelor combinatorii despre progresiile aritmetice monocromatice în colorarea numerelor naturale . Teorema este o afirmație tipică a teoriei lui Ramsey , precum și un precursor al teoremei lui Szemeredi , care a marcat începutul unei mari ramuri a combinatoriei aditive .

Notaţie

Pe tot parcursul articolului, notația este folosită pentru a desemna o mulțime . Această denumire este destul de comună în literatură. $\{1,\dots ,N\}$ $[N]$

Formulare

Teorema are două formulări echivalente - finită și infinită [1] .

Formulare fără sfârșit

Pentru orice și funcții , există astfel încât $r,k\in {\mathbb {N} }$ $c:{\mathbb {N} }\la [r]$ $a,d\in {\mathbb {N} }$

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

O funcție este de obicei numită o colorare a numerelor naturale, valorile sale sunt culorile numerelor, iar o progresie este de o singură culoare (teorema nu specifică ce culoare au elementele sale). $c$ $a,a+d,\dots ,a+(k-1)d$

Formularea finită este similară cu cea infinită, dar are în vedere o colorare a unei mulțimi finite. Îi aparține lui O. Schreier [2] .

Formulare finală

Pentru orice există un număr astfel încât pentru orice funcție există astfel încât $r,k\in {\mathbb {N} }$ $N=N(r,k)$ $c:[N]\la [r]$ $a,d\in {\mathbb {N} }$

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

Numerele din formularea finală se numesc numere van der Waerden . Pentru ei sunt studiate limitele inferioare și superioare. $N(r,k)$

Istorie

Dovada teoremei a fost publicată de B. L. van der Waerden în 1927.

Alexander Sofier în eseul său istoric despre teoria Ramsey scrie că Schur a considerat afirmația teoremei ca o ipoteză atunci când a lucrat la teorema sa privind colorarea numerelor (în 1916), dar ipoteza nu a ajuns la van der Waerden de la Schur, dar a fost inventat independent de Bode și van der Waerden a aflat ipoteza de la studenții săi (Baudet murise deja în acel moment). Dovada a fost inventată la Universitatea din Hamburg și prezentată publicului la Berlin la congresul Societății Germane de Matematică [3] .

Van der Waerden pur și simplu nu și-a dat seama cât de important a dovedit un rezultat: și-a trimis lucrările de geometrie algebrică celei mai prestigioase reviste, Mathematische Annalen , și a trimis această dovadă revistei „neinteligibile” Nieuw Archief voor Wiskunde a Societății Olandeze de Matematică. .

Text original (engleză)[ arataascunde] Van der Waerden pur și simplu nu și-a dat seama cât de important a fost rezultatul pe care l-a dovedit: și-a trimis lucrările de geometrie algebrică celei mai prestigioase reviste, Mathematische Annalen , dar a trimis această dovadă unui jurnal „obscur”, Nieuw Archief voor Wiskunde de la Societatea Olandeză de Matematică. .

La rândul său, Alexander Khinchin a scris că rezultatul a fost obținut la Göttingen în vara lui 1928 cu câteva zile înainte de sosirea sa acolo și că „un matematician local […] a întâlnit ipoteza în cursul lucrării sale științifice” [4] .

Ambiguitatea originii ipotezei originale este subliniată de Ronald Graham în cartea sa despre teoria Ramsey [5] , totuși, toate sursele sunt de acord că în formularea problemei pe care a rezolvat-o van der Waerden au existat doar două culori, și consolidarea afirmației la un număr arbitrar de culori a fost adăugată ca instrument de probă.

Schema dovezii [6]

În această secțiune, afirmația că teorema este adevărată pentru culori și lungimi de progresie este notă ca . $r$ $k$ ${\mbox{W}}(r,k)$

Teorema se demonstrează prin inductie pe . Baza este evidentă [7] . Atunci când se dovedește un pas de inducție, se spune de obicei, pentru comoditate, că se presupune că se dovedește pentru toți , deși formal, pentru a demonstra fiecare afirmație individuală , un număr finit de enunțuri de forma , dar cu valori foarte mari de , sunt suficient . $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'$

Pentru a garanta prezența unei progresii monocolore a lungimii , trebuie să trecem de la luarea în considerare a unui interval, a cărui lungime garantează prezența unei progresii monocolore a lungimii , la intervale din ce în ce mai mari, garantând prezența a mai multor și structuri mai complexe - așa-numitele ventilatoare . Pentru colorare, numim -fan o familie de progresii de lungime astfel încât: $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)$ , adică ultimul punct al tuturor progresiilor este comun;
$c({\vec {P}}_{i}(1))=c({\vec {P}}_{i}(2))=\dots =c({\vec {P} }_{i}(k-1)),\ i=1,\dots ,s$ , adică pentru fiecare progresie, toate elementele, cu excepția ultimului, sunt de aceeași culoare;
$i\not =j\Rightarrow c({\vec {P}}_{i}(1))\not =c({\vec {P}}(1))$ , adică culoarea principală (a tuturor elementelor cu excepția ultimului) este diferită pentru fiecare progresie.

Ventilatoarele pot fi folosite pentru a demonstra pasul de inducție datorită a două proprietăți evidente:

prezența în colorare a unei progresii monocolore a lungimii înseamnă de fapt prezența unui -ventilator; $k-1$ $unu$
prezența unui evantai în colorare garantează prezența unei progresii de lungime cu o singură culoare (deoarece culorile tuturor progresiilor sunt diferite și culorile tuturor , atunci unul dintre ele coincide cu culoarea ultimului element comun). $r$ $k$ $r$

Prin urmare, este suficient să se dovedească un pas de inducție asupra unui parametru pentru afirmația „orice colorare a unui interval suficient de mare conține un -ventilator sau o progresie a lungimii ”. Pentru aceasta ar trebui: $s$ $s$ $k$

Împărțiți un interval mare în blocuri - intervale mai mici, dar și de o lungime suficient de mare (să notăm ). Valoarea trebuie să fie suficientă pentru a se asigura că există un -ventilator în intervalele de lungime (adică în fiecare bloc) (o astfel de lungime există prin ipoteza inducției). $M$ $M$ $M$ $(s-1)$
Atribuiți întregul set de culori ale elementelor sale ca „hipercolor” a blocului. Numărul de astfel de hiperculori va fi foarte mare, dar totuși finit. $r^{M}$
Pentru o „hipercolorare” a unei secvențe suficient de lungi de blocuri, aplicați declarația , adică „găsiți” o progresie a blocurilor de culoare absolut identică. ${\mbox{W}}(r^{M},k-1)$

Acest lucru va garanta prezența mai multor ventilatoare identice distanțate la aceeași distanță unul de celălalt (un fel de progresie a ventilatoarelor). Dacă culoarea elementului central al ventilatorului diferă de culorile progresiilor sale [8] , atunci într-o astfel de construcție este posibil să selectați un -ventilator în diagonală (vezi imaginea). $s$ $(s+1)$

Analiza progresiilor multivariate

În timpul tranziției diagonale de la progresia -ventilatorului la -ventilatorul, se pierde un număr mare de conexiuni aritmetice și de culoare, la care participă elemente care nu sunt incluse în -fan. Dacă urmărim aceste elemente și duplicarea lor în progresii ulterioare de la -ventilatoare, -ventilatoare etc., atunci se va vedea că progresiile monocolore care emană de la orice -ventilator sunt de fapt diagonale ale progresiilor multidimensionale monocolore de dimensiune de la până la , în funcție de „momentul” apariției culorii în timpul inducției. Prin urmare, unii autori prezintă dovada în ceea ce privește găsirea combinației adecvate de progresii multidimensionale [9] . $s$ $(s+1)$ $(s+1)$ $(s+1)$ $(s+2)$ $s$ $unu$ $s$

Generalizări

Pentru teorema van der Waerden au fost studiate multe generalizări pentru diferite aspecte ale formulării enunțului. Diferite tipuri de generalizări pot fi combinate într-o singură declarație.

În această secțiune sunt date numai formulări nesfârșite de enunțuri generalizate, deși pentru majoritatea dintre ele există analogi finiți construiți după același principiu ca și pentru teorema principală.

Modalități de generalizare

Conform condițiilor structurale pentru configurație

Condiția ca numerele să formeze o progresie aritmetică înseamnă îndeplinirea egalităților $x_{1},\dots,x_{k)$

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

O modalitate de a generaliza este înlocuirea acestor condiții cu altele care sunt, de asemenea, liniare.

Întrebare

Pentru ce sisteme de ecuații liniare (inclusiv ecuații individuale) rămâne adevărată afirmația teoremei lui van der Waerden atunci când condiția ca elementele configurației necesare formează o progresie este înlocuită cu faptul că ele satisfac sistemul dat?

În plus, elementele de progresie pot fi reprezentate ca . Dacă percepem diferențele ca funcții fixe ale lui , atunci aceasta duce la o generalizare polinomială. $a,a+d,a+2d,\dots ,a+(k-1)d$ $d,2d,\dots ,(k-1)d$ $d$

Versiune polinomială

Fie polinoame cu coeficienți întregi astfel încât . Apoi pentru orice și există colorații astfel încât $p_{1},\dots,p_{k)$ $p_{i}(0)=0,\i\in [k]$ $r\in {\mathbb {N} }$ $c:{\mathbb {N} }\la r$ $a,d\in {\mathbb {N} }$

c(a)=c(a+p_{1}(d))=c(a+p_{2}(d))=\dots =c(a+p_{k}(d))

Idei dovezi [10]

Ventilatoarele pot fi, de asemenea, folosite pentru a demonstra versiunea polinomială, dar cu diferențele polinomiale corespunzătoare. De exemplu, atunci când se demonstrează prezența unei perechi monocrome într-o colorare arbitrară, un pas intermediar este de a demonstra existența numerelor astfel încât acestea să aibă culori diferite și să fie pătrate [11] . $a,a+d^{2},\a,d\in {\mathbb {N} }$ $x_{0},x_{1},\dots ,x_{s)$ $x_{1},\dots,x_{s)$ $x_{1}-x_{0},\dots ,x_{s}-x_{1)$

După dimensiune

La generalizarea teoremei la spații multidimensionale, în loc de progresii, sunt luate în considerare imagini homotetice ale unui set finit de puncte (o progresie aritmetică corespunde unei imagini homotetice a unui hipercub discret ).

Versiune multidimensională [12]

Pentru orice numere naturale , există seturi și colorații astfel încât $r,t\in {\mathbb {N} }$ $K\subset {\mathbb {N} }^{t)$ $c:{\mathbb {N} }^{t}\la \{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}}\în K

O generalizare mai largă, pur combinatorie, multidimensională este oferită de teorema Hales-Jewett. Pentru comoditate, poate fi înțeleasă ca o teoremă de colorare , dar operațiile cu numere nu sunt folosite deloc în ea, adică mulțimea poate fi înlocuită cu oricare alta de aceeași dimensiune. Aici, dimensiunea spațiului acționează ca un parametru variabil („suficient de mare”) , deci teorema Hales-Jewett are doar o formulare finită. ${\displaystyle [k]^{n))$ $[k]$

Definiție

Pentru o linie combinatorie stabilită în diagonala oricărui subcub netrivial se numește, adică mulțimea tuturor vectorilor, unde unele dintre coordonate pot fi fixe, iar restul (număr diferit de zero) sunt întotdeauna aceleași și rulează prin toate valorile . $A$ $A^{n}$ $a\în A$

Teorema Hales-Jewett [13]

Pentru orice există un număr astfel încât pentru oricare din orice colorare există o linie combinatorie monocromatică. $k,r\in {\mathbb {N} }$ $n_{0}=n_{0}(r,k)$ $n>n_{0},\ |A|=k$ $c:A^{n}\la [r]$

Idei dovezi

Dovada teoremei Hales–Jewett se bazează pe aceeași inducție prin ventilatoare. Pentru un vector , se consideră o partiție de coordonate . Într-o hipercolorare , în care hiperculoarea vectorului este o combinație de culori a tuturor punctelor formei , pentru suficient de mare este posibil, prin ipoteza inductivă (c ), să se găsească o linie combinatorie, în care toate elementele cu excepția unuia vor fi de aceeasi culoare. Pentru colorare , aceasta va însemna prezența unei astfel de „linii” de subspații de dimensiune identice colorate . Și pentru mari, prezența unei linii drepte similare în fiecare dintre aceste subspații este garantată. Se dovedește „o linie dreaptă din linii drepte”, fiecare dintre ele având aceeași continuare. Această construcție este similară cu construcția progresiilor generalizate din demonstrația teoremei lui van der Waerden și poate fi folosită pentru a construi ventilatoare în același mod ca [14] . ${\vec {a}}\in A^{n}$ ${\vec {a}}=({\vec {a_{1}}}, {\vec {a_{2}}})\în 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}$

Teorema van der Waerden rezultă din teorema Hales-Jewett, deoarece transformarea de la la , corespunzătoare interpretării coordonatelor ca cifre în sistemul numeric -ary , hărțește linii combinatorii în progresie aritmetică [15] . Teorema multidimensională van der Waerden poate fi derivată în mod similar fixând orice numerotare a elementelor și luând în considerare teorema Hales–Jewett pentru [16] . ${\displaystyle [k]^{n))$ $[k^{n}]$ $k$ $K$ $k=|K|$

Teorema multidimensională poate fi demonstrată și direct, fără teorema Hales–Jewett. Într-adevăr, dacă se dovedește pentru o submulțime care conține puncte afine independente , atunci putem aplica inducția de la la cu ajutorul ventilatoarelor din teoremele lui van der Waerden, dar cu o partiție în blocuri multidimensionale. Prin urmare, este suficient să prezentăm o modalitate de trecere de la o afirmație pentru la o afirmație pentru un set de puncte independente de afine. Ca exemplu în acest sens , puteți lua un colț, adică puncte din formă $K'\subset K\subset {\mathbb {R} }^{t)$ $t$ $K'$ $K$ ${\mathbb {R} }^{t-1)$ $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})

\dots

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

Prezența unui colț -dimensional în hiperplanul cu condiția (care este garantată pentru suficient de mare ) înseamnă prezența unui colț în care toate punctele, cu excepția celui central, sunt de aceeași culoare. În plus, împărțind numerele în blocuri multidimensionale și aplicând aceeași procedură acestora, se pot construi ventilatoare arbitrar mari din astfel de colțuri. $(t-1)$ ${\mathbb {R} }^{t)$ $a_{1}+\dots +a_{t}=N$ $N$ ${\mathbb {R} }^{t)$

O culoare (subseturi dense)

Din considerente empirice, este firesc să presupunem că configurația dorită într-o singură culoare a numerelor în majoritatea cazurilor va avea cea mai populară culoare, deoarece cu cât mai multe numere de o culoare sau alta, cu atât pot apărea configurații mai interesante între ele.

Deși plauzibilă, această afirmație nu decurge direct din teorema lui van der Waerden și este mult mai dificil de demonstrat. Pentru a o oficializa, trebuie remarcat că în colorarea finală cea mai populară culoare are o densitate superioară pozitivă [17] . Prin urmare, ipoteza declarată înseamnă prezența unei progresii în orice mulțime densă. Această teoremă poartă numele lui Endre Szemeredy , care a demonstrat-o primul.

teorema lui Szemeredi

Pentru orice și un set astfel încât , există astfel încât . $\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$

Prin analogie cu numerele van der Waerden, pentru versiunea finită a teoremei lui Szémerédy, studiem limitele inferioare și superioare pentru , suficiente pentru ca mulțimea cu condiția să conțină întotdeauna o progresie a lungimii . Obținerea unor astfel de estimări în cazul este mult mai dificilă decât în cazul . $N(\delta,k)$ $A\subset [N]$ $|A|>\delta N$ $k$ $k\geq 4$ $k=3$

Idei dovezi

Metodele de demonstrare a teoremei lui Szemeredi sunt izbitor de diferite de teorema lui van der Waerden atât ca tip, cât și ca complexitate. Sunt cunoscute dovezi combinatorii (folosind lema de regularitate Szemeredi din teoria generală a grafurilor ), analitice (folosind coeficienții Fourier și normele Gowers care le generalizează ) și ergodice.

Pentru a demonstra cele mai largi generalizări (cu adăugarea diferențelor polinomiale și multidimensionalitatea spațiului), metodele teoriei ergodice funcționează bine, dar nu dau estimări cantitative pentru formulările finale [18] .

La un număr infinit de culori

Cu un număr numărabil de culori, adică colorare , este posibil să nu existe progresii lungi de o singură culoare [19] . Dar dacă luăm în considerare configurațiile în care culorile tuturor elementelor sunt diferite ca un alt pol, de asemenea admisibil, al structurii de culoare, atunci teorema rămâne adevărată. $c:{\mathbb {N} }\la {\mathbb {N} }$

Această afirmație se numește versiunea canonică a teoremei lui van der Waerden.

Versiune canonică

Pentru orice colorare și există numere astfel încât: $k\in {\mathbb {N} }$ $c:{\mathbb {N} }\la {\mathbb {N} }$ $a,d\in {\mathbb {N} }$

sau $c(a)=c(a+d)=\dots =c(a+(k-1)d)$
sau pentru oricare $c(a+id)\not=c(a+jd)$ $0\leq i<j<k$

Idei dovezi

Erdős și Graham au fost primii care au observat că versiunea canonică decurge din teorema Szemeredi [20] . Ulterior, această idee a fost generalizată la cazul multidimensional [21] . Cu toate acestea, teorema lui Szémeredy în sine este dificil de demonstrat, așa că mai târziu a fost găsită o altă demonstrație, elementară a versiunii canonice, printr-o versiune multidimensională a teoremei obișnuite van der Waerden [22] .

În funcție de colorare , se poate construi o colorare a planului , în care culoarea perechii este asociată cu progresia , și anume, corespunde împărțirii progresiei prin uniformitatea culorilor. De exemplu, perechile pentru care sunt colorate progresiile corespunzătoare (roșu, roșu, verde) și (albastru, albastru, galben) vor avea aceeași culoare în . Este important ca numărul de culori să fie finit . $c:{\mathbb {N} }\la {\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'$

Dacă nu există progresii multicolore de lungime , atunci orice progresie are cel puțin două elemente de aceeași culoare. După teorema multidimensională van der Waerden, există o imagine homotetică cu o singură culoare în colorare . Progresiile corespunzătoare punctelor acestei imagini se vor intersecta în așa fel încât, prin combinarea acestor egalități, să fie posibil să se arate monocromaticitatea elementelor din diferite progresii și vor fi atât de multe încât aceste elemente își formează propria progresie. de lungime , complet monocromatic, ceea ce este cerut de condiție. $c$ $k$ $c'$ ${\displaystyle [(k-1)^{2}]^{2))$ $k$

Tabel rezumat cu câteva rezultate

Condiții aritmetice la structura dorită	Zona de căutare	Spaţiu
		unidimensional	Multidimensional	$A^{n}$ pentru finala $A$
Progresii aritmetice	colorare supremă	teorema lui Van der Waerden	Witt, 1952	Teorema Hales–Jewett
	Colorat fără sfârșit	Promel, Rodl, 1986		Teorema are doar formularea finală
	submult dens	teorema lui Szemeredi (inclusiv teorema lui Roth )	Teorema colțului	Cunoscut puternic generalizări ale teoremei lui Roth
Rezolvari de ecuatii liniare sau sisteme de ecuații	colorare supremă	Teorema lui Rado teorema lui Schur
	Colorat fără sfârșit	Lefmann, 1986		Teorema are doar formularea finală
	submult dens	Unele sunt cunoscute generalizări ale teoremei lui Roth [23] [24]
Înţeles polinoame în diferenţe	colorare supremă	Walters, 2000
	Colorat fără sfârșit	Girao, 2020 Fox, Wigderson, Zhao, 2020		Teorema are doar formularea finală
	submult dens	Bergelson, Leibman, 1996
	submult dens	Dovedit prin metode separate Teorema Furstenberg-Sharkozy [25] și teorema pătratică a lui Roth [26]

Literatură

I. D. Shkredov. Teorema lui Szemeredi și probleme privind progresiile aritmetice // Uspekhi matematicheskikh nauk. - 2006. - T. 61 , nr. 6 . — p. 111–178 . (Rusă)

A. Soifer. Teoria Ramsey : Ieri, azi și mâine . — Boston: Birkhäuser, 2011. — 189 p. - ISBN 978-0-8176-8091-6 .

A. Da. Khinchin. Trei pietre prețioase ale teoriei numerelor . - Moscova: „Nauka”, 1979. - 66 p. (Rusă)

M. Walters. Demonstrații combinatorii ale teoremei polinomului van der Waerden și ale teoremei polinomului Hales-Jewett // Journal of the London Mathematical Society. - 2000. - Vol. 61 , iss. 1 . — P. 1–12 .

V. Bergelson, A. Leibman. Extensii polinomiale ale teoremelor lui van der Waerden și Szemerédi // Journal of the American Mathematical Society. - 1996. - Vol. 9 , iss. 3 . — P. 725–753 .

R. Graham. Începuturile teoriei lui Ramsey . - Moscova: „Mir”, 1984. - 97 p. (Rusă)

P. Erdős, R. L. Graham. Probleme vechi și noi și rezultate în teoria numerelor combinatorii // L'Enseignement Mathematique. - 1980. - Vol. 25 . — P. 325–344 .

W. Deuber, R. L. Graham, H. J. Promel, B. Voigt. O teoremă de partiție canonică pentru relațiile de echivalență pe ${\mathbb {Z} }^{t)$ (engleză) // Journal of Combinatorial Theory, Series A. - 1983. - Vol. 34 , iss. 3 . — P. 331–339 .

HJ Promel, V. Rodl. O dovadă elementară a versiunii de canonizare a teoremei lui Gallai-Witt (engleză) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 42 , iss. 1 . — P. 144–149 .

RL Graham, BL Rothschild, JH Spencer. Teoria Ramsey . - Ed. a 2-a - A wiley-interscience publication, 1990. - 196 p. - ISBN 0-471-50046-1 .

H. Lefmann. O versiune canonică pentru partiția sistemelor regulate de ecuații liniare (engleză) // Journal of Combinatorial Theory, Series A. - 1986. - Vol. 41 , iss. 1 . — P. 95–104 .

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

A. Girao. Un polinom canonic Teorema lui Van der Waerden . - 2020. - arXiv : 2004.07766 .

J. Fox, Y. Wigderson, Y. Zhao. O scurtă demonstrație a teoremei van der Waerden polinomului canonic . - 2020. - arXiv : 2005.04135 .

S. Peluse, S. Prendiville. O limită polilogaritmică în teorema Roth neliniară . - 2020. - arXiv : 2003.04122 .

N. Lyall. O nouă dovadă a teoremei lui Sarkozy // Proceedings of the American Mathematical Society. - 2011. - Vol. 141 , iss. 7 . - arXiv : 1107.0243 .

T. Schoen, ID Shkredov. Teorema lui Roth în multe variabile // Israel Journal of Mathematics. - 2014. - Vol. 199 . — P. 287–308 . - arXiv : 1106.1601 .

T. Schoen, O. Sisask. Teorema lui Roth pentru patru variabile și structuri aditive în sume de mulțimi rare // Forum of Mathematics, Sigma. - 2016. - Vol. 4 . - arXiv : 1408.2568 .

Note

↑ Shkredov, 2006 , p. 112-114
↑ Graham, 1984 , p. optsprezece.
↑ Soifer, 2011 , p. 2.7.
↑ Khinchin, 1979 , p. 7-8.
↑ Graham, 1984 , p. 17.
↑ Vezi diverse prezentări în Khinchin, 1979 , p. 9-13, Graham, 1984 , p. 18-21, Shkredov, 2006 , p. 118-119
↑ Este suficient să luăm numere astfel încât, conform principiului Dirichlet , să existe între ele două numere de aceeași culoare. $r+1$
↑ Altele ar însemna prezența unei progresii a lungimii și atunci nu este nimic de demonstrat $k$
↑ Khinchin, 1979 , p. 9-13, vezi formula (5) și paragraful următor, unde există o tranziție la luarea în considerare a progresiei -a a -ventilatorului $r$ $s$
↑ Odată cu dezvoltarea studiului teoremei lui Szemeredy , metode eficiente ale teoriei ergodice au fost utilizate în mod activ pentru a demonstra generalizările polinomiale ale acesteia (vezi Bergelson, Leibman, 1996 ). O demonstrație elementară a unei generalizări polinomiale fără combinație cu o generalizare ca teorema lui Szemerédy a fost publicată mai târziu.
↑ Walters, 2000 , vezi „Ipoteza inducției” la p. 3
↑ Adesea numită „teorema lui Gallai-Witt” în literatura engleză.
↑ Graham, 1984 , p. 24.
↑ Graham, 1984 , p. 24-25.
↑ Graham, 1984 , p. 26.
↑ Graham, Rothschild, Spencer, 1990 , p. 40-41.
↑ Și, în plus, densitatea superioară nu este mai mică decât , unde este numărul de culori $1/r$ $r$
↑ Bergelson, Leibman, 1996 .
↑ De exemplu, poți colora fiecare număr în propria ta culoare, adică aloca $c(x):=x$
↑ Erdős, Graham, 1980 , p. 333, vezi „Existența este garantată de teorema lui Szemerédi”. $H(n)$
↑ Deuber, Graham, Promel, Voigt, 1983 .
↑ Promel, Rödl, 1986 .
↑ Schoen, Shkredov, 2014 .
↑ Schoen, Sisask, 2016 .
↑ Lyall, 2011 .
↑ Peluse, Prendiville, 2020 .