O kolorowaniu liczb naturalnych, czyli jak van der Waerden wachlarze projektował

Afiliacja: Doktorant, Wydział Matematyki, Fizyki i Informatyki, Uniwersytet Gdański

Główną motywacją niniejszego artykułu jest opowiedzenie o następującym twierdzeniu:

Trzeba przyznać, że teza jest zaskakująca, wiele osób mogłoby ją intuicyjnie uznać za błędną – trudno się przecież spodziewać, że zbiory, o których niemal nic pewnego nie wiemy, będą miały tak dobrze uporządkowane podzbiory. Jej prawdziwość jest jednym z fundamentalnych wyników gałęzi kombinatoryki znanej jako teoria Ramseya. Dowód postaramy się przedstawić tak, aby jasne były powody wykonania kolejnych kroków, bez wyciągania „królików z kapelusza”. Linia rozumowania jest zaczerpnięta z artykułu Terence’a Tao The ergodic and combinatorial approaches to Szemerédi’s theorem. Dla wygody, przez \(m\)-kolorowanie rozumieć będziemy kolorowanie \(m\) kolorami, ponadto zbiór liczb naturalnych będziemy standardowo oznaczać przez \(\mathbb{N}.\)

Wykażemy następujące, pozornie silniejsze, sformułowanie problemu:

Tak naprawdę oba sformułowania są równoważne, jednak implikacja „w dół” jest mniej oczywista. Tym, którzy sami chcieliby ją przeprowadzić, polecamy zapoznanie się z lematem Kőniga.

Teraz dużo lepiej widać, że narzucającą się metodą ataku jest zastosowanie podwójnej indukcji po \(k\) i \(m.\) Obiecujące wydaje się, by „zewnętrzna” indukcja była po długości ciągu. Bazę indukcji otrzymujemy za darmo: trywialne jest, że teza zachodzi dla \(k=1\) (a nawet dla \(k=2\)). Pozostaje nam wykonanie kroku indukcyjnego: wiedząc, że każde skończone kolorowanie dostatecznie wielu kolejnych liczb naturalnych zawiera ciąg arytmetyczny długości \(k-1\) (założenie indukcyjne), pragniemy to samo udowodnić dla \(k.\)

Przechodzimy teraz do indukcji względem liczby barw \(m\) („wewnętrzna” indukcja). Niestety nie widać, w jaki sposób przeprowadzić krok indukcyjny. Żadne trywialne rozumowanie nie pozwala wnioskować, że po odpowiednim wydłużeniu przedziału dodanie nowego koloru nie zmniejszy długości istniejących w nim ciągów arytmetycznych. Tutaj z pomocą przychodzi rdzeń pomysłu van der Waerdena, który można by nazwać wzbogaceniem czy też odświeżeniem tezy indukcyjnej. Ta metoda sprowadza się do tego, żeby zdefiniować strukturę, której istnienia będzie można dowodzić jako alternatywy dla tej żądanej w pierwotnym sformułowaniu tezy. Nowa struktura powinna dawać się łatwiej rozbudowywać w kroku indukcyjnym. Z drugiej strony, nie może istotnie osłabiać twierdzenia, a zatem jest pożądane, aby była kluczową „cegiełką” w konstrukcji oryginalnej struktury czy też czymś pośrednim pomiędzy dwiema takimi strukturami. Z tej perspektywy źródło idei van der Waerdena jest już dosyć jasne – staramy się znaleźć konstrukcję zawierającą konkretny punkt, którego malowanie wymaga albo wydłużenia jednokolorowego ciągu, albo wprowadzenia nowej barwy:

Ilustracja polichromatycznego wachlarza o promieniu 2 i stopniu 3

W tym miejscu możemy założyć prawdziwość „zewnętrznej” hipotezy indukcyjnej (dla dowolnego \(m' \in \mathbb{N}\) istnieje \(N=N(k-1, m')\) takie, że każde \(m'\)-kolorowanie przedziału długości \(N\) zawiera ciąg arytmetyczny długości \(k-1\)). ,,Wewnętrzna” indukcja względem liczby barw zostaje zastąpiona przez poniższe stwierdzenie dowodzone przez indukcję względem stopnia wachlarza:

Jasne jest, że to sformułowanie nam wystarcza, skoro po dojściu do \(d=m\) zabraknie barw, by istniał wachlarz polichromatyczny żądanego stopnia, co od razu implikuje prawdziwość zewnętrznej tezy indukcyjnej. Nie ma też kłopotu z bazą indukcji, wachlarz stopnia 0 składa się z jednej liczby (bazy), wystarczy zatem wziąć \(N(k,m,0)=1.\) Trzeba teraz znaleźć sposób, żeby w kroku indukcyjnym rozbudować wachlarz o jedną szprychę. W tym celu wykorzystamy podejście nieco podobne do argumentu przekątniowego Cantora. Otóż dowodząc dla danej wartości \(d,\) wiemy z założenia indukcyjnego, że każdy przedział długości \(N(k, m, d-1)\) zawiera ciąg arytmetyczny długości \(k\) albo wachlarz polichromatyczny stopnia \(d-1\) o promieniu \(k.\) Możemy założyć bez utraty ogólności, że istotnie każdy taki przedział zawiera taki wachlarz, gdyż w przeciwnym razie teza potwierdza się natychmiast. Technika, której chcemy użyć, polega na łączeniu mniejszych struktur w jedną większą, wobec czego trzeba teraz zbadać kolekcję wielu takich przedziałów z wieloma wachlarzami.

Oznaczmy \(P=N(k, m, d-1).\) Posłużymy się pewnym trikiem: istnieje tylko skończenie wiele sposobów (mianowicie \(m^P\)), żeby pomalować przedział długości \(P\) przy użyciu \(m\) kolorów. Każdemu z tych kolorowań możemy przyporządkować osobny „kod” – liczbę od 1 do \(m^P.\) Zamiast myśleć o kolorowaniu kolejnych liczb, możemy teraz rozważać nadawanie kodów kolejnym blokom \(P\) liczb. Nasze „zewnętrzne” założenie indukcyjne pokazuje zatem, że wśród \(N(k-1, m^P)\) kolejnych bloków istnieje \(k-1\) takich, które mają ten sam kod (więc są identycznie pomalowane) i znajdują się w równych odstępach. Tym samym każdy przedział długości \(P \cdot N(k-1, m^P)\) zawiera \(k-1\) identycznych wachlarzy stopnia \(d-1\) o promieniu \(k,\) tworzących ciąg arytmetyczny. Oznaczmy bazę pierwszego wachlarza przez \(a,\) a odstęp pomiędzy bazami kolejnych wachlarzy przez \(s\); \(a-s\) stanie się bazą nowego wachlarza. Teraz już widzimy nasze „przekątne”. Niech \(a+b_j\) będzie pierwszym punktem pewnej szprychy w pierwszym wachlarzu. Wtedy ciąg arytmetyczny \[a-s+(s+b_j),\ \ \ a-s+2(s+b_j),\ \ \ \dots ,\ \ \ a-s+(k-1)(s+b_j)\] jest jednobarwny (pierwsza z liczb należy do pierwszego z identycznych wachlarzy, druga do drugiego itd.) i staje się szprychą nowego wachlarza. Takich szprych jest \(d-1,\) a jeszcze jedną szprychę tworzy po prostu ciąg \[a-s+s,\ \ \ a-s+2s,\ \ \ \dots ,\ \ \ a-s+(k-1)s.\] Wiemy też, że barwy wszystkich tych szprych są parami różne. Stąd pozostają dwie możliwości: albo liczba \(a-s\) ma taki sam kolor jak jedna ze szprych, przez co badany przedział zawiera jednobarwny ciąg arytmetyczny długości \(k,\) albo ma kolor od nich wszystkich inny, przez co jest bazą wachlarza polichromatycznego stopnia \(d\) o promieniu \(k.\)

Do ukończenia kroku indukcyjnego i całego dowodu brakuje jedynego szczegółu: należy upewnić się, że \(a-s \geq 1.\) Zauważmy jednak, że wolno nam dowolnie wybrać badany przedział długości \(P \cdot N(k-1, m^P).\) W szczególności możemy zażądać, by zaczynał się od liczby równej \(P \cdot N(k-1, m^P).\) Ponieważ \(a\) musi należeć do tego przedziału, \(s\) musi zaś być mniejsze od jego długości, zapewnia to, że \(s<a,\) co było do wykazania. ◻

Dla pokazania zastosowań twierdzenia van der Waerdena i zarazem rozumowań podobnych do jego dowodu rozpatrzmy następujący, uroczy problem:

Wygląda to zupełnie jak zadanie, które mogłoby pojawić się na olimpiadzie matematycznej (w rzeczywistości, jak się wkrótce przekonamy, nie byłby to najszczęśliwszy pomysł). Przede wszystkim należy odnotować, że nie jest to prosty wniosek z twierdzenia van der Waerdena. Co prawda istnieją dowolnie długie jednobarwne ciągi arytmetyczne, ale nic nie gwarantuje, że ich postęp będzie mniejszy od ich długości, co może uniemożliwić znalezienie w nich dwóch elementów odległych o kwadrat liczby naturalnej. I chociaż potrzebne techniki nie wykraczają poza to, co widzieliśmy już wyżej, wydaje się, że problem pozostawał otwarty aż do ostatnich lat ubiegłego wieku. Korzystając z wytyczonego już szlaku, wprowadźmy następującą strukturę:

Dowód zaczerpnąłem z artykułu Marka Waltersa Combinatorial proofs of the polynomial van der Waerden theorem and the polynomial Hales-Jewett theorem z 2000 roku.

Główną – naprawdę niemal jedyną – trudnością koncepcyjną w dowodzie jest zorientowanie się, że indukcja może zapewnić polichromatyczność kwachlarza, pomimo że jego szprychy nie muszą być odległe jedna od drugiej o kwadrat liczby naturalnej. Do tego celu wykorzystamy oczywiście twierdzenie van der Waerdena. Podobnie jak poprzednio, dla dowolnie wybranego \(m\) możemy przekształcić naszą tezę do następującej postaci:

Zastosujemy indukcję ze względu na \(d.\) Baza indukcji jest trywialna (dla \(d=0\) kwachlarz staje się pojedynczą liczbą). Ponieważ w zbiorze pomalowanym \(m\) kolorami nie może istnieć kwachlarz polichromatyczny stopnia \(m,\) wykazanie kroku indukcyjnego wystarczy do udowodnienia całego twierdzenia. Z założenia indukcyjnego możemy więc przyjąć istnienie \(N(m, d-1)\) takiego, że każdy przedział naturalny tej długości zawiera kwachlarz polichromatyczny stopnia \(d-1\) (albo dwie liczby odległe o kwadrat, ale wtedy kończymy krok indukcyjny). Dzięki twierdzeniu van der Waerdena wiemy, że kiedy zbadamy dostatecznie dużo kolejnych przedziałów tej długości, znajdzie się wśród nich \(2\lceil \sqrt{N(m, d-1)} \rceil\) przedziałów identycznie pokolorowanych w identycznych odstępach, a tym samym \(2\lceil \sqrt{N(m, d-1)} \rceil\) kwachlarzy polichromatycznych stopnia \(d-1\) tworzących ciąg arytmetyczny. Jak poprzednio, oznaczmy bazę pierwszego kwachlarza przez \(a\) oraz odstęp pomiędzy bazami kolejnych kwachlarzy przez \(s.\) Tym razem bazą nowego kwachlarza stanie się \(a-s^2.\) Niech \(a+b_j^2\) będzie dowolną szprychą pierwszego kwachlarza. Wówczas \({a-s^2+(s+b_j)^2=a+b_j^2+2b_j \cdot s}\) jest tego samego koloru (należy do jednego z tych identycznych kwachlarzy, jako że \({2b_j < 2\lceil \sqrt{N(m, d-1)} \rceil}\)) i staje się szprychą nowego kwachlarza. Samo \(a\) również staje się szprychą nowego kwachlarza, a kolory wszystkich tych \(d\) szprych muszą być parami różne. To pozostawia dwie możliwości – jeżeli liczba \(a-s^2\) ma taki sam kolor jak jedna ze szprych, to tworzy parę jednego koloru o odległości będącej pełnym kwadratem, a w przeciwnym razie jest ona bazą kwachlarza polichromatycznego stopnia \(d.\) Znów pozostaje tylko upewnić się, że \(a>s^2,\) a w tym celu, tak jak poprzednio, wystarczy odpowiednio przesunąć początek przedziału, znając już jego długość. To kończy dowód.\(\square\ \)

Okazuje się, że przedstawiony problem jest tylko przypadkiem szczególnym znacznie mocniejszego twierdzenia wielomianowego van der Waerdena, które pozwala zastąpić w sformułowaniu tezy skończony ciąg wielomianów liniowych \(W_1(n)=n, W_2(n)=2n, \dots , W_k(n)=kn\) albo pojedynczy wielomian kwadratowy \(W(n)=n^2\) – dowolnym skończonym zbiorem wielomianów bez wyrazu wolnego. Jego pierwszy dowód (Bergelson i Leibman, 1996) odwoływał się do teorii ergodycznej. Czytelnik Dociekliwy znajdzie nieco żmudny, ale wykorzystujący podobne do naszych narzędzia, dowód w cytowanej na marginesie pracy Marka Waltersa.