2007-07-10

Smutna historia o pewnym twierdzeniu

Zeszłe wakacje spędziłem w połowie nad Bałtykiem a w drugiej połowie podróżując po Słowacji. Z żoną i z pewnym problemem matematycznym postawionym przez nieocenionego WH. Dobrze jest mieć jakieś ciekawe zadanie na latni wyjazd. To gwarancja, że niezależnie od pogody urlop nie będzie stracony.
Nie bedę referował tu problemu jakim się zajmowałem, ale zreferuję z grubsza pewien odprysk, który sam w sobie jest ciekawy i stoi za nim pewna historia, którą postaram się w miarę możliwości zrekonstruować.
Norweski matematyk Fredrik Carl Mülertz Størmer, żyjący w latach 1874-1957 sformułował następujące twierdzenie:

Twierdzenie 1 (Størmer)
Niech P={p1,...,pn} będzie skończonym zbiorem liczb pierwszych. Wśród liczb naturalnych, jest skończenie wiele takich n, n i n+1 mają w rozkładzie na czynniki pierwsze jedynie liczby ze zbioru P.

Størmer dowodził owego twierdzenia przy użyciu twierdzeń o rozwiązaniach równiania Pella - nb. jednego z najważniejszych równań diofantycznych. Metoda Størmera dawała również możliwość, dzięki istnieniu algorytmów rozwiązywania równań Pella nadających się do ręcznego wykonania, wyliczenia wszystkich liczb naturalnych o jakich mowa a Twierdzeniu 1, dla rozsądnie małych zbiorów P zawierających rozsądnie małe liczby pierwsze.
Oczywiście dzisiaj, mając do dyspozycji komputery, pewnie z łatwością (ciekawe czy ktoś to zrobił, może sam się tym zajmę...) dałoby się przy użyciu tych samych metod znaleźć stosowne liczby dla znacznie większych zbiorów P i większych liczb pierwszych w nich zawartych.
Naturalnym uogólnieniem egzystencjalnej części wyników Størmera (a więc po prostu Twierdzenia 1) jest oczywiście:

Twierdzenie 2:
Niech P={p1,...,pn} będzie skończonym zbiorem liczb pierwszych. Dla każdego naturalnego k > 0 wśród liczb naturalnych, jest skończenie wiele takich n, n i n+k mają w rozkładzie na czynniki pierwsze jedynie liczby ze zbioru P.

To właśnie klucz, który okazał się być mi potrzebny by uporać się z hipotezą WH. Problem jako żywo kojarzył mi się z Hipotezą Catalana, starym problemem matematycznym, który został rozwiązany ostatecznie w 2000 roku i przestał istnieć jako problem stając się Twierdzeniem Catalana. Na drodze do dowodu Twierdzenia Catalana zwieńczonej przez P. Mihailescu milowym krokiem były wyniki R. Tijdemana, szczęśliwie publikowane w Acta Arithmetica, międzynarodowego czasopisma wydawanego przez Polską Akademię Nauk którego starsze roczniki są dostępne w Internecie. Przyznaję, że nie starałem się zgłębić rozumowań Tijdemana, choć wiązałem z taką analizą pewną nadzieję na przyszłość. Jednak to co zwróciło moją uwagę, było jedno z twierdzeń na którym Tijdeman opierał swoje dowody. Pochodziło ono od Alana Baker'a a Tijdeman referował do pracy, szczęśliwie również publikowanej w Acta Arithmetica. Przez ciąg referencji w pracach Bakera, dotarłem w końcu do wygodnego sformułowania. Oto one:

Twierdzenie 3 (Baker)


Niech a_1,...,a_n będą niezerowymi liczbami algebraicznymi stopnia nie przekraczającego d
i wysokości tych liczb nie przekraczają A_1,...,A_n.
Niech Q=log(A_1)*...*log(A_n) i Q>=2.

Wtedy

istnieje stała C taka, że nierówność:
|b_1*log(a_1)+...+b_n*log(a_n)| < exp(-C*Q*ln(Q)*log(B)) (1)
nie ma niezerowych rozwiązań dla liczb całkowitych b_1, ...,b_n takich, że |b_i| <= B > 2 dla i=1,...,n

Bazując na tym twierdzeniu, udało mi się dowieść Twierdzenia 2.

Dowód Twierdzenia 2:

Dla moich celów nie potrzebuję jawnej postaci Q,
zapiszę więc nierówność (1) jako:

|b_1*log(a_1)+...+b_n*log(a_n)| < B-C (2)

(C w (2) oczywiście jest tu zmodyfikowane w stosunku do (1) tzn. pomnożone przez Q*ln(Q))

Założmy, dla celów rozumowania nie wprost, że par o jakich mowa w Twierdzeniu 2 istnieje nieskończenie wiele.
Innymi słowy, dla dowlnego M naturalnego istniałaby X > M, takie, że X i X+k miałyby dzielniki pierwsze wyłącznie ze zbioru P.

Rozpatrzmy iloraz:

(X+k)/X = 1+k/X

Mamy:

0< log(1+k/X) = log(X+k)-log(X) = a_1*log(p_1)+...+a_n*log(p_n) (3)

gdzie a_1, ..., a_n są pewnymi liczbami całkowitymi.

Z Twierdzenia 3, na mocy nierówności (2) i z (3) dla B takich, że

B > max(|a_1|, ...,|a_n|)

mamy:

log(1+k/X)>B-C (4)

Zauważmy, że dla odpowiedni dużych X i dla i=1,...,n:

|a_i|<2*(|a_1|*log(p_1)+...+|a_n|*log(p_n)) < 2*log((X+k)*X) < 2*log(2*X^2) = 2log(2)+4*log(X)

Zatem:

B=2log(2)+4*log(X)

jest odpowiednią stałą, przy której nierówność (4) jest prawdziwa.

Dostajemy ostatecznie:

log(1+k/X)>(2log(2)+4*log(X))-C

czyli:

1+k/X>exp( (2ln(2)+4*log(X))-C )

i w końcu:

k>X*exp((2log(2)+4*log(X))-C)-X

Funkcja po prawej stronie, dąży jednak powoli ale wytrwale do nieskończoności, przy X->00 co przy założonej na potrzeby dowodu niewprost nieograniczoności X daje sprzeczność.

Dobra, wracam do historii. Grzebiąc w owym czasie po literaturze nie natknąłem się na sformułowanie i dowód twierdzenia 2 i przez jakiś czas tkwiłem w przeświadczeniu, że może udało mi się (co prawda przy pomocy kobyły w postaci twierdzenia bakera, ale jednak) uzyskac nowy i ciekawy przyznacie wynik. Łyżkę dziegciu cały czas stanowiła jednak enigmatyczna notka w wikipedii, że Twierdzenie 1 można uzyskać za pomoca tzw. twierdzenia Thue-Siegela-Rotha. Co prawda nie pracowałem nad tym zbyt wytrwale, ale do diaska, nie wiedziałem jak. Ba, dręczyło mnie przeczucie, że i Twierdzenie 2 można tą drogą uzyskać.
I ostatnio znalazłem. Praca nosi tytuł "On integers with many small prime factors", autorstwa wspomnianego już tu Tijdemana ukazała się w Compositio Matematica w 1973 roku. Tijdeman dowodzi tam silniejszego jeszcze rezultatu (opierając się na twierdzeniach Bakera), ale pisze, że Twierdzenie 2 zostało udowodnione przez Thuego w 1908 roku, wzmocnione przez Siegela w 1921 i na dobitkę jeszcze wzmocnione przez Erdösa w 1965.
Smutno :(.
Jaki morał dla mnie? Kilka:
Nie cieszyć się za wcześnie. Uczyć się, kiedy jest na to czas - braki w erudycji mogą owocować zawodem. Na wakacjach więcej odpowczywać - wysiłki są próżne. Sklejanie samolotów czy zbieranie znaczków to mniej frustrujące hobby niż matematyka. Wina chilijskie są niezłe na pocieszenie.

P.S.
Kiedy wyjdę z depresji, postaram się wzbogacić ten wpis o linki do stosownych prac, nazwisk etc.

2007-07-08

Wyjaśnienie

Niniejszym informuję zaniepokojonych zapewne czytelników "homo sapie...", że Artur P. zatrzymany dzisiaj za rozpowszechnianie środków odurzających to nie autor tego bloga.
Autor tego bloga nie rozpowszechnia tylko czasem nabywa środki odurzające legalne na terenie Polski i to tylko oznaczone znakiem akcyzy.

2007-06-27

Skala

W czasach kiedy studiowałem, a i dzisiaj też, choć nie jest to już pierwszorzędny hit naukowy, jednym z najmodniejszych tematów były fraktale i teoria chaosu. Oba te zagadnienia są ściśle pokrewne (fraktale pojawiają się w sposób naturalny w modelach tzw. deterministycznego chaosu) i poza wartością ściśle naukową są prowokacyjne intelektualnie i estetycznie. Stanowią wyzwanie filozoficzne ale stały się też posiłkiem wyobraźni masowej.
Nie ma jednej definicji fraktala, choć nazwa (ang. fractal pochodzi od łacińskiego "fractus" i ma ten sam źródłosłów co "fraction " - ułamek) trochę nam w zrozumieniu o co chodzi pomaga. A chodzi mianowicie o kwestię stosunku w jakim pozostaje część obiektu geometrycznego do całości. Definicja wikipedyjna wymienia 5 cech "fraktalności", z których tu intetresuje mnie tu teraz tylko pierwsza, a mianowicie pewna bogactwo struktury obiektu w dowolnie małej skali. Z pewnością dla osoby oglądającej sobie fraktale jak np. zbiór Mandelbrota (nb. twórcy nazwy i pojęcia fraktal) dla doznąń estetycznych, najlepiej przy użyciu jakiegoś sprytnego oprogramowania pozwalającego na zasadzie cudownego mikroskopu niegraniczenie przybliżać fragmenty fraktala, jest to cecha czyniąca całą zabawę fascynującą, dostarczającą przyjemności podobnych do zapomnianego już prawie urządzenia zwanego kalejdoskopem. Ona więc najbardziej rzuca się w oczy.
Ale gdy zajmowałem się fraktalami na studiach, ten aspekt "fraktalności" był w zasadzie pomijany. Pewnie dlatego, że jest najtrudniejszy do uchwycenia w przeciwieństwie do np. samopodobieństwa czy ściśle już liczbowych własności nie dających się w ogóle przełożyć prosty na język potoczny jak np relacja między wymiarem topologicznym i wymiarem Hausdorffa.

Zwróciłem uwagę na kluczowość cechy "bogactwa struktury" dla traktowania fraktali jako narzędzia badania rzeczywistości trochę na zasadzie małego olśnienia gdy czytałem w książkę Edwarda O. Wilsona "Różnorodność życia". W jednym z fragmentów, przywołuje on tam obraz obraz kory wielkiego tropikalnego drzewa, na której żyją organizmy różnych rozmiarów - od "makroskopowych" owadów przez mikroskopowych rozmiarów owady po roztocza i w końcu baktere czy pierwotniaki. Dla każdego z nich, powierzchnia drzewa jest światem o skończonej powierzchni, ale powierzchnia wymierzana skalą tych zwierząt jest coraz większa. To co wielki żuk potraktuje jako nieco tylko chropowatą ale równą powierzchnię dla roztoczy będzie krajobrazem z górami i dolinami. To odwołuje się do takiej "bajkowej", dziecięcej wyobrażni, i dobrze ilustruje ideę. Jest też w pewnej sprzeczności z wizją fraktala jako tworu samopodobnego, ponieważ zależnie od skali pojawiają się nam różne (a w każdym razie niekoniecznie takie same) perspektywy i inne, jakże do siebie niepodobne obrazy. Tym niemniej struktura na każdym poziomie jest bogata.

Ciekawi mnie ujawnianie się pewnych struktur zależnie od skali. Mezokosmos, czyli ta cześć rzeczywistości, która mierzona jest skalą ludzką zajmuje niewiele miejsca na osi możliwych "wielkości". Praktyczna działalność człowieka dostrzegalna jest w trochę szerszym zakresie, Dopiero od niedawna spojrzenie przez silny mikroskop może nas skłonić do podejrzeń, że to na co patrzymy to twór sztuczny. Jeszcze 60 lat temu sztuczność struktury praktycznie nie ujawniała się na tym poziomie. Dziś, patrząc na układ scalony wysokiej skali integracji dostrzeżemy wytwory z łatwością dające się zakwalifikować jako sztuczne - coś niby miasta. Idąc w drugą stronę, oddalimy się z wolna od ziemi i z wysokości setek kilometrów, wytwory ludzkiej techniki są coraz trudniej dostrzegalne, w końcu zostaje tylko wielki mur, kanał sueski, światła miast. Dalej, w skalach kosmicznych, redukujemy się do punktu, potem nasze słońce redukuje się dp punktu itd.
Mamy pojęcie o tym gdzie więc rozciągają sie skale w których pracowite łapki i wiecznie kombinujące główki odciskują swoje piętno. Ale, ale - skąd niby, gdybyśmy sami nie wybudowali czy nie stworzyli tych wszystkich sztucznosci, mielibyśmy wiedzieć, że są one rzeczywiście sztuczne?
To kolejny ciekawy problem. Weźmy problem N ciał. Mechanika klasyczna, Newton. Ogólne rozwiązanie analityczne w postaci ładnego wzoru oczywiście nie istnieje. Skomplikowany taniec punktów materialnych, w ogólnym przypadku jest chaotyczny i szczelnie wypełnia tą część przestrzeni fazowej zbudowanej z możliwych pędów i położeń która odpowiada stałej energii równej energii warunku początkowego. Takim światem w przybliżeniu jest układ słoneczny - jego stabilność nie udowodniona przecież a postulowana jako rzecz warta dowodu już przez Pierre Simone'a de Laplace'a - może okazać się krótkim okresem w stosunku do innego teoretyczno-mechanicznego scenariusza w którym zaczną się dziwaczne wywijasy (byleby energia była stała!). Ba - na pewno wręcz! Że tak teoretycznie się stanie - uczy nas choćby twierdzenie Poincare o powracaniu tyle tylko że czasy przewidywane przez teorię na zajście jakichś drastycznych zmian wyglądają na długawe w porównaniu z wiekiem wszechświata. Dla naszej cywilizacji jednak bieg planet kryje w sobie nie ukryte zalążki chaosu ale Harmonia Mundi - muzykę sfer. Dzieło Boga w najczystszej postaci. OK kryło.
W słynnym epitafium Pope'a:

"Nature and nature's laws lay hid in night;
God said 'Let Newton be' and all was light."

czai się zalążek kolejnego wielkiego filozoficznego sporu - czy Bóg stworzył i kieruje światem, czy tylko stworzył prawa nim rządzące i puścił wszystko w ruch. Z pewnego punktu widzenia, chciałoby się zapytać: really all was light ? To również jest kwestia skali i pewnego poziomu abstrakcji myślenia - tyle, że to nie mój spór i nie mój problem - dzięki Bogu!

2007-06-25

Pogrzebacz

Niemal jednym tchem przeczytałem ostatnio "Pogrzebacz Wittgensteina". Gdybym miał ową książkę przykleić do jakiegoś gatunku (bo rzecz wije się między historią, biografią, anegdotą, plotką i popularnie podaną filozofią) chyba zdecydowałbym sie na historię. Osią jest zetknięcie dwóch ważnych dla współczesnego myślenia filozofów na spotkaniu w Klubie Nauk Moralnych w Cambridge w 1946 roku - spotkania gwałtownego w którym (tu humorystyczno-anegdotyczna częśc książki znajduje punkt wyjścia) Wittgenstein w zapale ponoć wymachiwał niebezpiecznie pogrzebaczem co doprowadziło filozoficzny spór na krawędź prostackiej bijatyki.
Rozwijając spiralnie opowieść dostajemy portrety po kolei trzecio-, drugo- w końcu pierwszo-planowych uczestników zajścia. Sporo interesujących informacji biograficznych, solidne przedstawienie kontekstu historycznego w jakim spór mający tak wstydliwe w sumie apogeum się toczył. W końcu dość któtkie omówienie sedna sporu - krótkie ale z grubsza wystarczające wobec rozproszonych wcześniej w tekście informacji na ten temat.
Nie będę szczegółowo streszczał książki. Napiszę o tym co szczególnie mnie w niej zaintrygowało w trakcie lektury. Pierwsza rzecz to portret Wiednia końca XIX wieku aż po początek II Wojny Światowej. Dla ludzi pochodzących z Galicji, Wiedeń jest wjakimś sensie archetypem metropolii. U mnie w domu mawiało się "za babci Austrii" co świadczy o wciąż żywym, mimo, że nie wywodzę się z domu o specjalnych tradycjach, wspomnieniu okresu zaborów Austryjackich, żyjącym w społeczeństwie. Pewnym osiągnięciem Austrii była dość zgodna egzystencja kilkudziesięciu narodowości w jednym państwie-imperium Habsburskim.Skostnienie biurokracji imperium znane nam pośrednio i bezpośrednio z Kafki czy prześmiewczego Haszka, nie powinna przesłonić faktu, ze te wszystkie narodowości jednak z pewną dozą autonomii tam funkcjonowały. Wiedeń z przełomu wieków, ale i czasów późniejszych to miasto które skorzystało na wewnętrznej różnorodności imperium. Dość powiedzieć, że intelektualnie w latach o których mówię było to jedno z najżywotniejszych centrów myśli generujących idee, które przez cały wiek XX stały się jednymi z najbardziej nośnych i dominujących prądów intelektualnych. Począwszy od sztuki, przede wszystkim muzyki - tu tradycja była najstarsza ale i malarstwa i architektury po matematykę (Godel) filozofie i logikę (Godel, Schlick, von Hajek, Wittgenstein, całe Koło Wiedeńskie, Popper), psychologię (Freud) itd. Wymieniać by długo.
To w końcu ośrodek myśli politycznej i ekonomicznej z ogromnym wpływem na takie prądy ważne dziś jak socjaldemokracja i liberalizm.
Przerażający jest obraz tego upadku tego miasta, w ciągu dwudziestolecia zaledwie przekształacającego się z owego siedliska myśli twórczej i swobody intelektualnej w jeszcze jeden bastion faszyzmu. Przerażający i niezrozumiały - przynajmniej dla mnie. Na wiarę przyjmuję, że wstrząs jakim był upadek monarchii podkopał jakoś fundament życia społecznego. Ale co to właściwie znaczy ? Nie, tu trzeba pogłebionej analizy - to cholernie ważne, również z powodu tego co otacza nas dookoła.
Druga fascynująca sprawa, to postać Wittgensteina. To osobowość hipnotyzująca dla tych, którzy się z nim spotkali. Jego charyzma przyciągała. Nie rozumiem skąd się brała. Osobiście uważam, że ja raczej bym go nie cierpiał i unikał. Wittgenstein jakoś bardziej pasowałby mi na twórcę religii niż filozofa. Jego pierwsze i chyba najważniejsze dzieło - "Tractatus Logico - Philosophicus" ma cos w sobie z ksiąg natchnionych, choć paradoksalnie, jego celem jest usunięcie metafizyki z rozważań filozoficznych, To poemat logiczny, zwięzły i otwarty zarazem zwięzłością i otwartością poezji współczesnej. Surowy, pozornie ścisły do granic, ale wyznaczający pola interpretacyjne, wkraczenie na które budziło wściekłość samego Wittgensteina. Nie jestem w stanie w formie blogowej umieścić za dużo o tej postaci - tu trzeba książki. Dość powiedzieć, że słynne Koło Wiedeńskie uważalo go za mistrza - on jednak, spadkobierca jednej z największych fortun Austrii, której zrzekł się częściowo a częściowo opłacił nią wolność od prześladowań faszysowskich swojej rodziny o żydowskich korzeniach - traktował chyba próby zamknięcia go w jakimś nurcie z wyniosłościa i wzgardą.
Potem - Wittgenstein II (takiego podziału na ?Wittgensteina I i II dokonał Bertrand Russel) w istotnej części zrywający z poglądami "Tractatusa", ciągle gromadzący jednak wokół siebie wyznawców, ktytyczny, wyniosły, niezrozumiany we własnym mniemaniu. W sumie zagubiony.Szalenie kontrowersyjna postać oscylująca między wielkościa a śmiesznościa, tragedią i farsą.
W końcu Karl Popper - zdolny syn żydowskiego prawnika z Wiedeńskiej klasy średniej - pracowity, zakompleksiony, w zakompleksieniu swym odważny i w końcu jednak pewny siebie. Postać - jak słusznie zauważają autorzy - która nie świeci dziś takim blaskiem jak za swojego życia (właściwie twórczej jego części) - bowiem jego idee przestały być przedmiotem zaciekłej debaty - stały się częścią otaczającej nas kutlury, począwszy od niekwestionowanej już w zasadzie nalizy prawomocności teorii naukowej opartej na podatności na falsyfikację po idee polityczne, społeczne i ekonomiczne.
Rzecz warta jest przeczytania, ale warto wcześniej lub później zapoznać się z nieco głębszymi omówieniami myśli obu adwersarzy a najlepiej z ich dziełami (ja trochę znałem analizy zanim przeczytałem książkę, ale mam motywację żeby sięgnąć do źródeł, a mam takowe wśród moich półkowników). To istotna część naszej współczesnej kutury - nie sposób zrozumieć wielu sporów, które się dziś toczą bez jej znajomości.