Van der Waerdenova veta

Formulácia, dôkaz pre AP dĺžky 3

Veta. Pri hocijakom zafarbení množiny všetkých prirodzených čísel $m$ farbami existuje monochromatická aritmetická postupnosť (ďalej budeme hovoriť AP) ľubovoľnej dĺžky.

Dĺžkou aritmetickej postupnosti rozumieme jednoducho počet jej členov. Monochromatická AP je taká, že všetky jej členy majú rovnakú farbu. Van der Waerden dokázal "konečný" variant tejto vety, teda že keď si povieme, aká dlhá má tá postupnosť byť, stačí zafarbiť dostatočne veľa za sebou idúcich čísel, povedzme od 1 do $N$. Presnejšie:

Veta. Pre ľubovoľné prirodzené čísla $k, m\ge 1$ existuje číslo $N=N(k,m)$ také, že pri hocijakom zafarbení úseku prirodzených čísel $1,2,\dots, N$ pomocou $m$ farieb existuje monochromatická aritmetická postupnosť dĺžky $k$.

Vetu budeme dokazovať indukciou vzhľadom na číslo $k$, teda počet členov hľadanej aritmetickej postupnosti. Pre jednočlenné aritmetické postupnosti je $N(1,m)=1$, pretože jedno číslo hocijako ofarbené tvorí jednočlennú AP. Pre dvojčlenné AP stačí zobrať $N(2,m)=m+1$, lebo z $m+1$ čísel, ofarbených $m$ farbami musia mať aspoň dve rovnakú farbu (olympionici MO si určite spomenú na Dirichletov krabičkový princíp, alebo anglicky pigeonhole principle).

Prvý zaujímavejší prípad je $k=3, m=2$. Dokážeme, že stačí zobrať $N(3,2)=325$ (je to prehnane veľké číslo, v skutočnosti stačí deväť za sebou idúcich čísel, aby sa pri hocijakom ich zafarbení dvomi farbami našla jednofarebná postupnosť dĺžky tri -- vedeli by sme to overiť?).

Interval prirodzených čísel $n_1, n_1+1,\dots, n_2$ budeme označovať $[n_1,n_2]$. Rozdeľme interval $[1,325]$ na 65 rovnakých blokov, každý o dĺžke 5: $$[1,325]=[1,5]\cup[6,10]\cdots\cup[321,325]= B_1\cup B_2\cdots\cup B_{65}. $$

Pretože bloky majú dĺžku 5 a máme dve farby, existuje $2^5=32$ rôznych spôsobov, ako blok ofarbiť. Preto spomedzi prvých 33 blokov môžeme vybrať dva, ktoré sú rovnako zafarbené, nech sú to bloky $B_s, B_t, \ s < t$. Doplňme tieto dva bloky blokom $B_{t+(t-s)}$ na trojčlennú postupnosť rovnako od seba vzdialených blokov. Medzi prvými tromi číslami z bloku $B_s$ aspoň dve majú rovnakú farbu, nech sú to $j, j+d$-te. Číslo $j+2d$ tiež patrí do bloku $B_s$. Ak má rovnakú farbu ako $j$, sme hotoví, našli sme trojčlennú monochromatickú AP. Ak nie, uvažujme číslo s poradím $j+2d$ v bloku $B_{t+(t-s)}$. Ako vidno názorne z obrázku, vieme nájsť, bez ohľadu na jeho farbu, trojčlennú jednofarebnú AP.

Trojčlenná AP

Podobná konštrukcia by sa dala vytvoriť pre $N(3,3)$ a na jej základe urobiť aj všeobecný dôkaz, ale bolo by to značne zdĺhavé a neprehľadné. Spomedzi mnohých spôsobov dôkazu van der Waerdenovej vety sme vybrali jeden z "kombinatorických ", pretože je aj pekný, aj relatívne prehľadný :-)

Polychromatické vejáre

Dohodnime sa, že aritmetickú postupnosť $a_1, a_1+d, a_1+2d\dots, a_1 +(k-1)d$ budeme zapisovať skrátene ako $a_1+[0,k-1]\cdot d$. Zafarbenie množiny $L$ pomocou $m$ farieb budeme volať tiež $m$-farbením a je to vlastne zobrazenie ${\cal C}: L \rightarrow C$, kde $C$ je množina farieb (môžu to byť napr. čísla farieb).

Definícia Predpokladajme, že máme nejaké $m$-farbenie prirodzených čísel. Vejárom lúčovitosti $d$ s polomerom $k$ a so základňou $b$ nazývame usporiadanú $d$-ticu $F=(b+[0,k-1]\cdot r_1, b+[0,k-1]\cdot r_2,\dots , b+[0,k-1]\cdot r_d)$ aritmetických postupností so spoločným začiatkom. Postupnosti $b+[1,k-1]\cdot r_j,\ j=1,2,\dots d$ nazývame lúčmi vejára. Hovoríme, že vejár je slabo polychromatický, ak všetky jeho lúče sú monochromatické a zafarbené rôznymi farbami. Vejár je silno polychromatický, ak jeho monochromatické lúče a aj jeho základňa sú zafarbené rôznymi farbami.

V ďalšom využijeme tri vlastnosti vejárov, z ktorých prvé dve sú ľahké a na tretiu si nakreslíme obrázok.

  1. Ak $F$ je slabo polychromatický vejár s polomerom $k$, potom buď $F$ je silno polychromatický (ak farba jeho základne je odlišná, ako farby lúčov), alebo $F$ obsahuje AP dĺžky $k$ (ak jeho základňa má rovnakú farbu, ako jeden z lúčov).
  2. Silno polychromatický vejár nemôže mať stupeň $m$ (pretože by si to vyžadovalo aspoň $m+1$ farieb -- $m$ na ofarbenie lúčov a jednu na základňu).
  3. Nech $F=(a+[0,k-1]\cdot r_1, a+[0,k-1]\cdot r_2,\dots , a+[0,k-1]\cdot r_d)$ je vejár s polomerom $k$ a lúčovitosťou $d$. Majme $k-1$ disjunktných vejárov $jr+F,$ $j=1,2,\dots,k-1$, ktoré vzniknú posunutím vejára $F$ a nech všetky tieto posunuté vejáre sú silno polychromatické a rovnako ofarbené. Potom vejár $\tilde F$ $$\left({ a+[0,k-1]\cdot r, a+[0,k-1]\cdot (r+r_1),\dots , a+[0,k-1]\cdot (r+r_d)}\right)$$ je slabo polychromatický s polomerom $k$ a lúčovitosťou $d+1$. Z aritmetickej postupnosti silno polychromatických vejárov a z vejára pôvodného sme teda skonštruovali slabo polychromatický vejár, ktorý má o jeden lúč viac. Pritom sme základne vejárov využili ako nový lúč a ostatné lúče sú skonštruované "diagonalizáciou", teda napr. prvý prvok z prvej postupnosti prvého vejára spojíme s druhým prvkom prvej postupnosti druhého vejára,$\dots$ až s $k$-tým prvkom prvej postupnosti $k$-tého vejára. Podrobnosti je vidieť a podstatu konštrukcie možno pochopiť na obrázku.

Polychromatické vejáre, AP

Dôkaz pre všeobecné AP

Ako sme už povedali, budeme robiť dôkaz indukciou. Bude to indukcia dvojitá, pričom "vonkajšia" bude podľa premennej $k$ a vnútorná podľa pomocnej premennej $d$, ako o tom bude reč ďalej. Prvý krok indukcie podľa $k$ sme už urobili, ukázali sme, že pre $k=1$ stačí položiť $N(k,1)=1$ a pre $k=2$ zasa $N(k,2)=k+1$. Predpokladajme teda, že van der Waerdenova veta platí pre nejaké číslo $k-1$, teda že pre každé $m$ existuje číslo $N=N(k-1,m)$ také, že každé $m$-zafarbenie množiny $[1,N]$ obsahuje monochromatickú AP dĺžky $k-1$.

Na to, aby sme dokázali, že tvrdenie vety platí aj pre číslo $k$ a ľubovoľné $m$, dokážeme najskôr pomocné tvrdenie.

Lema.  Pre každé $d\ge 1$ existuje číslo $\tilde N(k-1,m,d)$ také, že pre každé $m$-zafarbenie množiny $[1,\tilde N(k-1,m,d)]$ vieme nájsť buď aritmetickú postupnosť dĺžky $k$, alebo silno polychromatický vejár polomeru $k$ a lúčovitosti $d$.

Dôkaz.  Zasa použijeme indukciu, tentoraz podľa $d$. Pre $d=1$ je tvrdenie správne, stačí položiť $\tilde N=\tilde N(k-1,m,1)= 2 N(k-1,m)$ (toto číslo existuje podľa (vonkajšieho) indukčného predpokladu). Skutočne, v ľavej polovici intervalu, tj. v intervale $[N(k-1,m), 2 N(k-1,m)]$ existuje monochromatická AP dĺžky $k-1$ a keď na jej začiatok pridáme ďalší člen tak, aby sme opäť dostali AP, vznikne silno polychromatický vejár polomeru $k$ a lúčovitosti $1$, alebo monochromatická AP dĺžky $k$.

Nech teda $d > 1$ a predpokladajme, že tvrdenie lemy je správne pre číslo $d-1$. Zoberme $$\tilde N=\tilde N(k-1,m,d)=2 N_1 N_2,$$ $$\mbox{kde } N_1=\tilde N(k-1,m,d-1) \mbox{ a } N_2=N(k-1,m^d N_1^{k d}).$$ Majme ľubovoľné $m$-zafarbenie intervalu $[1,\tilde N]$. Všimnime si, že tento interval môžeme rozsekať na $2 N_2$ rovnakých podintervalov $B_1, B_2,\dots , B_{2 N_2}$, pričom každý z nich má dĺžku $N_1$. Podľa (vnútorného) indukčného predpokladu každý podinterval buď obsahuje aritmetickú postupnosť dĺžky $k$, alebo silno polychromatický vejár polomeru $k$ a lúčovitosti $d-1$. Ak aspoň jeden podinterval obsahuje aritmetickú postupnosť dĺžky $k$, sme hotoví. Predpokladajme opak. Potom každý podinterval s poradovým číslom $b,\ b=1,2,\dots , 2N_2$ obsahuje silno polychromatický vejár $F(b)$ polomeru $k$ a lúčovitosti $d-1$. Všetky tieto vejáre možno chápať ako posunutia nejakých (nie nutne polychromatických) vejárov $\tilde F(b),\ b=1,2,\dots , 2N_2$, patriacich do prvého intervalu $B_1$.

Keďže dĺžka intervalu $B_1$ je $N_1$, môže v ňom existovať najviac $N_1^{k d}$ vejárov polomeru $k$ a lúčovitosti $d-1$ (stačí si uvedomiť, že vejár má $d-1$ lúčov dĺžky $k$, každý z nich nemôže mať dĺžku väčsiu ako $N_1$). Počet rôznych zafarbení silno polychromatického vejára stupňa $d-1$ je najviac $m^d$, pretože (tvárme sa, že nezávisle od seba) môžeme vybrať z $m$ farieb pre $d-1$ lúčov a ešte pre jeden bod -- základňu. Ofarbenie vejára $F$ budeme značiť $C(F)$.

Teraz príde veľká myšlienková ekvilibristika :-) Zoberme zobrazenie $${\mathcal C}: j\mapsto (\tilde F(j),C(F(j))), \ j\in [N_2+1,2 N_2],$$ teda každému číslu $j$ z hornej polovice intervalu $[1, 2 N_2]$ priradíme usporiadanú dvojicu, ktorej prvý člen je vejár $\tilde F(j)$ a druhým členom je ofarbenie vejára $F(j)$. Toto zobrazenie môžeme chápať ako ofarbenie intervalu $[N_2+1,2 N_2]$ dĺžky $N_2$ takým počtom farieb, ako je počet tých dvojíc a ten sme povyššie odhadli číslom $N_1^{k d} m^d$. Podľa (vonkajšieho) indukčného predpokladu, keďže $N_2=N(k-1,m^d N_1^{k d})$, tak existuje monochromatická AP $a_0+[0,k-2]\cdot r$ dĺžky $k-1$ v tomto ofarbení.

To ale, prevedené znova do "ľudskej reči" znamená, že existuje AP dĺžky $k-1$ silno polychromatických vejárov polomeru $k$ a lúčovitosti $d-1$ , ktoré sú posunutiami toho istého vejára $\tilde F$ z $B_1$ do intervalov s indexami, aké majú členy horeuvedenej číselnej AP. Pritom, čo je dôležité, všetky tieto vejáre sú (každý vo svojom príslušnom intervale s indexom z horeuvedenej AP) rovnako zafarbené. Pridajme na začiatok tejto AP ešte jeden vejár, kópiu tých ostatných (jeho farba bude určená ofarbením intervalu, do ktorého patrí, teda nemusí byť polychromatický) tak, aby sme dostali $k$-člennú AP vejárov, ktorej členy okrem prvého sú silno polychromatické a rovnako ofarbené. Poznamenajme, že pridaný vejár sa nutne musí nachádzať v jednom z intervalov $B_1,B_2,\dots , B_{2 N_2}$.

Na túto postupnosť vejárov aplikujeme vlastnosť (iii), čím dostaneme slabo polychromatický vejár polomeru $k$ a lúčovitosti $d$. Podľa vlastnosti (i) tento vejár je alebo silno polychromatický, alebo obsahuje monochromatickú AP dĺžky $k$. V oboch prípadoch sme hotoví, lebo je to tvrdenie lemy pre číslo $d$, teda previedli sme (vnútorný) indukčný krok -- predpokladajúc správnosť tvrdenia lemy pre $d-1$ a ľubovoľné $k-1,m$ dokázali sme, že platí aj pre $d$.

Teraz je už ľahké previesť aj (vonkajší) indukčný krok, teda prechod od $k-1$ ku $k$. Stačí položiť $N=N(k,m)=\tilde N(k-1,m,m)$. Pretože silno polychromatický vejár lúčovitosti $m$ nemôže podľa (ii) existovať, musí existovať monochromatická AP dĺžky $k$ pri ľubovoľnom $m$-ofarbení intervalu [1,N].

Hurá, dôkaz sa zdá byť hotový. Nikdy si tým však pri podobných komplikovanejších úvahách nemôžeme byť na stopro istí :-) Aj keby sme to opisovali "z knižky". Nič nenahradí vlastné myslenie $\dots$

Dodatok

Čísla $N(k,m)$, ktoré sme konštruovali v dôkaze, neboli najmenšie možné. O tých je známe len málo. Vieme len, že $$ N(3,2)=9,\ N(4,2)=35,\ N(5,2)=178,\ N(3,3)=27,\ N(3,4) = 76.$$ Minulý rok v lete oznámil mladý doktorand, Michal Kouřil (Univ. of Cincinnati, College of Engineering, Dept. of Computer Science), že našiel ďalšie číslo, $N(6,2)=1132$. Bolo to publikované v časopise Experimental Mathematics, nájsť sa dá na tomto odkaze. Počítali to 253 dní na paralelnom zhluku (cluster) Linux-áckych počítačov. A to zrejme musel drasticky zredukovať počet prípadov, ktoré vyšetroval, lebo počet možných zafarbení, $2^{1132}$ je 341-miestne číslo! Chlapec skončil PhD., pracuje teraz v Cincinnati Children's Hospital Medical Center. Na nasledujúcich fotografiách je mladý Bartel Leendert van der Waerden (v r. 1931) a Michal.

No a nakoniec dôkaz, že $N(3,2)=9$ (nečítať teraz, urobiť sami -- možno vymyslíte krajší). Najskôr, že 8 za sebou idúcich čísel možno zafarbiť dvomi farbami tak, aby neobsahovali trojčlennú monochromatickú AP:

Osem čísel

Ak čísla od 1 do 9 sú ofarbené čierno-bielo, aspoň päť musí mať tú istú farbu, napr. čiernu. Nech sú to čísla $ c_1 < c_2 <\cdots < c_5$. Ukážeme, že sa medzi nimi vždy nájde trojčlenná AP. Všímajme si štvorčlennú postupnosť $D=\{d_i=c_{i+1}-c_i,\ i=1,2,3,4\}$ rozdielov čiernych čísel. Všimnime si, že

  1. ak sú dva susedné rozdiely rovnaké, máme trojčlennú AP,
  2. ak $d_i+d_{i+1}=d_{i+2}$, čísla $c_i, c_{i+2}, c_{i+3}$ tvoria trojčlennú AP.

Súčet postupnosti $D$ môže byť nanajvýš 8 (osem je to len pre $c_1=1, c_5=9$). Teda členy $d_i$ môžu byť nadobúdať len hodnoty 1,2 alebo 3 (keby jeden bol 4, ostatné by boli jedničky, teda aspoň dve z nich by boli susedné). Dve trojky a dve jedničky vedú k prípadu (i) alebo k AP $\{c_1, c_3, c_5\}$. Pri jednej trojke, bude s ňou susediť dvojica $(1,2)$ alebo $(2,1)$ (prípad (ii)), ak nechceme aby boli susedné jedničky či dvojky. Keď budú dve jedničky a dve dvojky, musia byť striedavo, čo tiež vedie k AP $\{c_1, c_3, c_5\}$. Teda, trojčlennej AP sa nevyhneme a skutočne, najmenšie $N(3,2)$ je 9.


Literatúra:

  1. Akos Magyar:Van der Waerden's Theorem, http://www.math.uga.edu/~lyall/REU/VW.pdf
  2. Terry Tao:Arithmetic Ramsey Theory, http://www.math.ucla.edu/~tao/preprints/Expository/ramsey.dvi