Problem rozbieżności Erdősa


Wyobraźmy sobie, że mamy kierować armią robotów. Roboty są bardzo proste, ponieważ rozumieją tylko dwie komendy: na komendę „naprzód” robot robi krok do przodu, na komendę „wstecz” tej samej długości krok do tyłu. Każda nasza komenda dociera do wszystkich robotów, nie możemy więc kierować tylko pojedynczym. Roboty różnią się jednak „karnością”: tylko pierwszy z nich wykonuje posłusznie każdy otrzymany rozkaz. Drugi wykonuje tylko co drugi rozkaz, pozostałe ignoruje. Trzeci robot jest jeszcze bardziej leniwy i wykonuje tylko co trzecią komendę, ignorując pozostałe. I tak dalej, n-ty robot wykonuje co n-tą komendę. Ponadto roboty nie mogą się nadmiernie oddalać od linii startowej, jeżeli któryś odejdzie od niej o zbyt wiele kroków, niezależnie do przodu czy do tyłu, traci łączność i jest uważany za utraconego. Pytanie brzmi: jak mamy kierować robotami, jakie rozkazy wydawać, by żaden nie uciekł nam za daleko? Czy to się w ogóle da zrobić? A może odpowiedź zależy od tego, jak daleko pozwalamy robotom odejść?

Taki problem, postawił około roku 1932 młody Pál Erdős, jeden z najsłynniejszych matematyków XX wieku. Erdős postawił przy tym hipotezę, że kierujący robotami stoi na straconej pozycji, że niezależnie od tego jak daleko leży ta nieprzekraczalna dla robotów granica i niezależnie jak starannie będzie on planował ciąg wysyłanych im rozkazów, zawsze w końcu któryś z nich przekroczy granicę i zostanie utracony. Opierał się przy tym na intuicji, nie potrafił bowiem tego udowodnić. Problem ten został nazwany nieformalnie problemem rozbieżności Erdősa i mniej obrazowo a bardziej matematycznie formułowany jest zazwyczaj następująco: dla każdego ciągu (x_i) którego wszystkie elementy są równe +1 lub −1 i dla każdej liczby naturalnej C istnieją takie liczby naturalne k i d że

\displaystyle \left|\sum_{i=1}^k x_{i\cdot d}\right| > C

Porównując ten zapis z naszą opowieścią o robotach: x_i to rozkaz numer i, +1 i −1 oznaczają odpowiednio komendy „naprzód” i „wstecz”, C to odległość w krokach od granicy, której roboty nie mogą przekroczyć, d to numer robota a k to liczba rozkazów wykonanych przez tego robota (czyli kd to całkowita liczba wydanych rozkazów).

Problem ten w kolejnych latach budził zainteresowanie licznych matematyków. Sam Erdős też zresztą kilkukrotnie do niego wracał. Ale mimo wysiłków nikt nie potrafił znaleźć rozwiązania, tzn. udowodnić tej hipotezy bądź wykazać, że jest fałszywa. Co więcej, nikt nie miał nawet pomysłu jak zabrać się do szukania tego rozwiązania. Zazwyczaj jeżeli matematyk, pracując nad jakimś problemem, znajduje coś, co wydaje się przybliżać rozwiązanie,  publikuje taki cząstkowy wynik, bo być może pomoże to komuś innemu zrobić kolejny krok. Tymczasem do końca XX wieku (a nawet dłużej) brak jest jakichkolwiek publikacji na temat tego zagadnienia. Erdős, który znany był z tego, że oferował nagrody pieniężne za rozwiązania różnych problemów matematycznych, wycenił ten na 500 dolarów. Ale do końca jego życia (a zmarł w 1996 roku) nagroda pozostała nie wypłacona.

W roku 2009 Tim Gowers zaproponował coś, co potem zostało nazwane Projektem Polymath: forum na którym większa grupa matematyków może pracować wspólnie nad jakimś problemem, wymieniając się szybko pomysłami i koncepcjami. Polymath wziął problem rozbieżności na warsztat w roku 2010, jako projekt Polymath5. Wprawdzie rozwiązania ostatecznie nie znaleziono i aktywność w Polymath5 wygasła pod koniec 2010 roku (na krótko odżywając w roku 2012), to w ramach tego projektu udało się poczynić kilka spostrzeżeń, które potem okazały się kluczowe dla ostatecznego rozwiązania. Najważniejszym z nich było udowodnienie, że poszukując rozwiązania można się ograniczyć do pewnej klasy ciągów, zwanych ciągami multiplikatywnymi. Elementy tych ciągów spełniają własność x_{m\cdot n}=x_m\cdot x_n dla każdego mn. Oznacza to, że budując naszą listę rozkazów dla robotów jako ciąg multiplikatywny, możemy swobodnie ustalać tylko te rozkazy, których numery są liczbami pierwszymi. Jeżeli na przykład zdecydowaliśmy, że rozkaz numer 2 będzie brzmiał „wstecz” (−1), a rozkaz numer 3 „naprzód” (+1), to rozkaz numer 6 musi brzmieć „wstecz”, bo +1\cdot (-1) = -1.

W roku 2014 ukazała się praca której autorzy zaatakowali problem przy pomocy specjalnych programów do sprawdzania wartości logicznych złożonych wyrażeń i pokazali w ten sposób, że hipoteza Erdősa jest spełniona dla C=2. Znaleziona przez nich maksymalna długość ciągu rozkazów dla którego żaden robot nie odchodzi o więcej niż 2 kroki od punktu startu wynosi 1160. Jeżeli wydamy 1161 lub więcej rozkazów, to zawsze jakiś robot odejdzie nam o co najmniej 3 kroki od startu. Problem z ich podejściem polegał na tym, że kompletny dowód liczył sobie 13GB objętości (był więc nie do sprawdzenia dla człowieka), no i bardzo trudno było go rozszerzyć na większą liczbę kroków: już dla C=3 autorom udało się tylko udowodnić, że istnieje sekwencja 13000 rozkazów która nie wyprowadza żadnego robota na odległość większą niż 3 kroki, ale pomimo tygodniami trwających obliczeń górnego ograniczenia nie udało im się znaleźć.

Ostateczne rozwiązanie pojawiło się nagle i niespodziewanie. We wrześniu tego roku Terence Tao, dość młody jeszcze matematyk urodzony w Australii a pracujący obecnie w Kalifornii (i zapowiadający się na jednego z najsłynniejszych matematyków XXI wieku) umieścił w arXiv pracę zawierającą pełny dowód poprawności hipotezy Erdősa. Tao był wcześniej członkiem projektu Polymath5, ale ostatnio pracował nad zagadnieniami zdawałoby się odległymi od tego tematu, chociaż związanymi z własnościami ciągów multiplikatywnych. 6 września opisał na swoim blogu stan swoich prac. 9 września Uwe Stroinski pozostawił pod tym wpisem komentarz o możliwym związku pewnych zawartych we wpisie koncepcji z problemem rozbieżności. I ten komentarz pozwolił na odnalezienie brakującego elementu rozwiązania: praca je zawierająca ukazała się w tydzień później. Tao zawarł w niej oczywiście zarówno odnośniki do wyników z Polymath5, jak i podziękowanie dla autora komentarza. Wprawdzie praca nie przeszła jeszcze formalnie recenzji, ale raczej nikt nie ma wątpliwości do jej poprawności.

Tak właściwie to Tao udowodnił nawet więcej, jego dowód działa bowiem także w wielu wymiarach. W naszym przykładzie oznacza to, że możemy skonstruować bardziej złożone roboty, które będą umiały wykonywać polecenia „zrób krok na północ” lub „zrób krok na azymut 110”. Jeżeli tylko pozostałe założenia się nie zmienią, tzn. wszystkie roboty będą otrzymywać takie same polecenia i wykonywać tylko co n-te z nich, gdzie n jest numerem robota, to nie uda nam się nigdy utrzymać ich w ograniczonej odległości od punktu wyjścia, po dostatecznie długim czasie któryś pójdzie w szkodę, tzn. odejdzie dalej od punktu wyjścia, niż jest to dozwolone.

Dowód Tao jest trudny, zawarty na kilkudziesięciu stronach ciężkiej matematyki, ale sam autor pięknie go streścił i nie mogę się powstrzymać by o tym nie opowiedzieć. Pomysł polega na tym by budować nasz ciąg komend stopniowo, dodając do niego stałej długości kawałki. Tao dowodzi, że jeżeli mamy już pewien ciąg komend nie wyprowadzających żadnego robota zbyt daleko od punktu wyjścia, do dodanie do niego kolejnego kawałka spowoduje jedną z dwóch rzeczy: albo wynikowy ciąg komend wyprowadzi któregoś robota za daleko, albo entropia wynikowego ciągu będzie niższa od entropii ciągu poprzedniego o pewną stałą wartość. Ale entropia ze swej definicji nie może być liczbą ujemną. Kiedyś więc dojdziemy w ten sposób do ciągu komend o entropii tak niskiej, że nie da się już do niego dołożyć kolejnego kawałka obniżającego ją jeszcze bardziej, co znaczy, że kolejny kawałek spowoduje wyjście któregoś z robotów poza wyznaczone granice.

Chociaż Pál Erdős, jak wspomniałem, już nie żyje, to Terence Tao otrzyma podpisany przez niego czek na 500 dolarów. Erdős zostawił bowiem podpisane czeki, oczekujące na rozwiązania. Zainkasować się go oczywiście nie da, ale zgódźmy się że wartość pamiątkowa takiego czeku znacznie przekracza te 500 dolarów.

I na zakończenie coś ładnego: wspólne zdjęcie dwóch głównych bohaterów opowieści, Pála Erdősa i Terence Tao. Zdjęcie zostało wykonane w 1985 roku, pierwszy miał wtedy 72 lata, drugi miał lat 10. A spotkali się na Uniwersytecie w Adelajdzie. Tao od najmłodszych lat przejawiał ogromny talent matematyczny i już w tym wieku uczestniczył w uniwersyteckich kursach matematyki, a rok później po raz pierwszy wystartował w międzynarodowej olimpiadzie matematycznej (odbywającej się zresztą w tamtym roku w Warszawie) i zdobył brązowy medal. Terence Tao ma liczbę Erdősa równą 2, co znaczy że nie zdążył już opublikować żadnej pracy wspólnie z mistrzem.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s