Odkurzone - mozaiki liczb

Tym razem nie o mozaice tytoniowej ;)...
Rzecz solidnie zakurzona choć, jakieś dwa lata temu, przypomniana. Bo pewnie warto - to matematyka dość przyjemna, elementarna, w wielu aspektach niezbyt trudna, w sam raz na kółko matematyczne w liceum.
W 1963 roku w "Bulletin of AMS" w stałym wówczas dziale "Research Problems" zawierającym nadsyłane przez czytelników krótkie notki z opisem interesujących problemów - tematów dla potencjalnych badań, pojawiła się notatka Alberta A. Mullina pod tytułem "Some related number-theoretic functions". Autor zdefiniował w niej (niezbyt precyzyjnie ale dość intuicyjnie) pojęcie mozaiki liczby naturalnej i zadał kilka pytań owego pojęcia dotyczących. W mniej więcej tym samym czasie i w latach następnych opublikował też kilka artykułów poświęconych owemu zagadnieniu, w różnych czasopismach. M.in w Notre Dame Journal of Formal Logic, w roku 1965 "Mathematico-philosophical remarks on new theorems analogous to the fundamental theorem of arithmetic" oraz w 1967 "On new theorems for elementary number theory" -wszystkie trzy wymienione dostępne w Internecie, plus kilka do których nie udało mi się dostać (zainteresowani referencjami mogą rzucić okiem na bibliografię ostatniej z wymienionych prac).
Postaram się szybko (ale również krytycznie - tzn. z własnym komentarzem) streścić co na ten temat pisał Mullin, co nowego w tej sprawie pojawio się ostatnimi czasy i wyjaśnić po co w ogóle pisze o tym w blogu, tj. dlaczego zagadnienie wydało mi się interesujące.
Jak wiadomo od starożytności, każdą liczbę naturalną >= 2 można na jeden z dokładnością do permutacji czynników sposób zapisać jako iloczyn liczb pierwszych - jest to treścią tzw. podstawowego twierdzenia arytmetyki. Można ową liczbą zatem zapisać na jeden jedyny sposób jako iloczyn potęg różnych liczb pierwszych (znowu z dokładnością do permutacji czynników) . Jeżeli zapisać korzystając używając tego przedstawienia z kolei wykładniki potęg w przedsatawieniu naszej liczby, a potem kontynuować ten proces rekurencyjnie otrzymamy pewne specjalne przedstawienie liczby naturalnej używające jedynie liczb pierwszych, operacji mnożenia i operacji potęgowania. To przedstawienie nazywać będziemy za Mullinem mozaiką liczby.
Popatrzmy na przykłady, operacja stanie się jasna:

126 = 2*(3^2)*7
455625 = (5^4)*(3^6) = (5^(2^2))*(3^(2*3))
936776054504321817706424726448362358340312545892791091968 =
= 3*(2^8)*(7^64) = 3*(2^(2^3))*(7^(2^6)) = 3*(2^(2^3))*(7^(2^(2*3)))

Dość łatwo zauważyć (łatwiej niż to super-precyzyjnie zapisać), że dla danej liczby istnieje jedna z dokładnością do pewnych oczywistych wynikających z przemienności mnożenia przekształceń mozaika. Jest to oczywisty wniosek z twierdzenia o jednozanczności rozkładu na liczby pierwsze.

Zanim przejdę do pytań dotyczących przedstawień mozaikowych powtórzę kilka klasycznych definicji a potem podam ich rozszerzoną, mozaikową wersję.

Funkcję f z liczb naturalnych do ciała liczb zespolonych nazywamy multiplikatywną, jeżeli dla każdych względnie pierwszych a i b mamy f(ab)=f(a)f(b).
Podobnie g jest funkcją addytywną, jeżeli dla każdych względnie pierwszych a i b mamy g(ab)=g(a)+g(b).

Względną pierwszość liczb oczywiście da się wyrazić w terminach ich rozkładu na liczby pierwsze - liczby względnie pierwsze to takie, które nie mają wspólnych dzielników pierwszych w swoich rozkładach. W naturalny sposób, za Mullinem, mozemy uogólnić te definicje i otrzymać, nazwijmy je umownie, funkcje mozaikowo multiplikatywne i mozaikowo addytywne. Oto ich definicja:

Liczby a i b nazywać będziemy mozaikowo względnie pierwszymi, jeżeli w ich przedstawieniu mozaikowym nie ma wspólnych liczb pierwszych.

Przykład:
4 = 2^2 jest mozaikowo względnie pierwsze z 27=3^3, ale nie z 9 = 3^2.

Zwróćmy uwagę, że, każde dwie liczby mozaikowo względnie pierwsze są też względnie pierwsze. Przykład względnie pierwszych 4 i 9 dowodzi, że nie jest odwrotnie - mozaikowa względna pierwszość jest istotnie silniejszą własnością.

Funkcja f z liczb naturalnych do ciała liczb zespolonych nazywamy mozaikowo multiplikatywną (odp. mozaikowo addytywną), jeżeli dla każdych dwóch mozaikowo względnie pierwszych liczb a i b, f(ab)=f(a)f(b) (dopowiednio f(ab)=f(a)+f(b)).

Tu mała uwaga terminologiczna. Mullin wprowadza termin uoglniona funkcja multiplikatywna (addytywna) - ja zmieniam nomenklaturę na taką, która bardziej wydaje mi się odpowiednia.

Obserwacja, że mozaikowa względna pierwszość jest silniejsza niż względna pierwszość szybko prowadzi do konkluzji, że wszystkie funkcje multiplikatywne (odp. addytywne) są jednocześnie mozaikowo multiplikatywne (odp. mozaikowo addytywne). Jak można się domyślić, nie jest odwrotnie, tj. mozaikowa *ywność nie gwarantuje *ywności bezprzymiotnikowej. Powtórzę tu konstrukcję Mullina.

Zdefiniujmy funkcję psi dla liczb naturalnych w następujący rekurencyjny sposób.
Dla 1 psi(1) = 1;
Dla p będącego liczbą pierwszą psi(p) = p;
Dla dowolnej innej liczby naturalnej postaci p1^a1*p2^a2*...*pn^an, gdzie p1,...,pn są różnymi liczbami pierwszymi psi(p1^a1*p2^a2*...*pn^an) = p1*psi(a1)*p2*psi(a2)*...*pn*psi(an)

Łatwym ćwiczeniem jest sprawdzenie, że:
1. Definicja jest dobrze postawiona, tj. rzeczywiście zdefiniowaliśmy funkcję.
2. Zdefiniowa funkcja jest multiplikatywna.

Okazuje się, że złożenie funkcji psi z samą sobą (czyli funkcja x->psi(psi(x)) ) jest mozaikowo multiplikatywna ale nie multiplikatywna. Dowód dość łatwy, pozostawiam chętnym żeby mieli trochę radości.
Jedno z pytań, które stawia w notce z "Bulletin" Mullin nie jest chyba tak łatwe,w każdym razie mnie się (na razie) nie udało znaleźć zamkniętej formuły a rekurencje jakie mi chodzą po głowie są dość skomplikowane i nie polegają na prostym przejściu od n do n+1. Pytanie brzmi - dla zadanego n naturalnego, jaka jest liczość przeciwobrazu zbioru {n} przez odwzorowani psi.
Co z funkcjami mozaikowo addytywnymi? Podobnie.
Dalszych przykłądów funkcji mozaikowo multiplikatywnych dostarcza odpwoiednie mozikowe uogólnienia klasycznych funkcji arytmetycznych. Np mozaikowa funkcja Mobiusa mi zdefiniowana jako:
mi_star(n) = 0 jeżeli w mozaice liczby n jakakolwiek liczba pierwsza wystąpi więcej niż jeden raz.
mi_star(n) = (-1)^k gdzie k liczba liczb pierwszych występująca w mozaice n w przeciwnym wypadku.

Niestety, zdaje się, że żaden ciekawy odpowiednik twierdzenia o inwersji Möbiusa tu nie zachodzi, przez co teoria funkcji mozaikowo arytmetycznych nie jest taka interesująca.

Mullin ma niestety trochę irytującą manierę strzelania z armaty do wróbli. Na przykład: Mullin podaje, że addytywna (klasycznie!) funkcja psi_star zdefiniowana w następujący sposób:
psi_star(1) = 0,
psi_star_star(x) suma wszystkich liczb w mozaice x dla x > 1
jest suriekcją na zbiór N\{0,1}. Jako argument przywołuje twierdzenie Schnirellmana, podczas, gdy z łatwością można znależć elementarny dowód.

OK. Czy zapomniane ? Nie moge odgrzebać tej pracy, ale jakiś czas temu - ku mojejmu zaskoczeniu - na Arxiv pojawił się artykuł napisany przez grupę studentów poświęcony rozwinięciu, ciągle elementarnemu, niektórych idei Mullina.

Co moim skromnym zdaniem jest w tym interesującego ? No, nie spodziewm się po tym zabawnym, przyznajcie, pomyśle jakiś wielkich fajerwerków, ale daje on pewne nowe spojrzeni na liczby naturalne i prowokuje szereg pytań.

Popatrzmy na to w ten sposób: mamy pewien zbiór X i rozłączny z nim , jednolelementowy zbiór I={i}.
Niech FINFUN(A,B) to wszytkie funkcje o skończonej dziedzinie zawartej w A i przeciwdziedzinie B.
Zdefiniujmy teraz indukcynie:

F(0,X,I) = FINFUN(X,I)∪I
F(n+1, X,I) = FINFUN(X,F(N))
F(X,I) = F(0,X,I)∪F(1,X,I)∪...∪...

W sumie łatwo zauważyć, że nasze F(X,I) odpowiada (jest izomorficzne) z drzewami o skończonej głębokości i skończonej ilości następników dla każdego węzła i węzłach o etykietach ze zbioru X.
Na zbiorze F(X,I) można zdefiniować naturalny porządek częściowy (indukcyjnie):

i x dom(x)⊆dom(y) i ∀s∈dom(x) x(s)≤y(s)

Można też zdefiniować częściową operację

jeżeli dom(x)∩dom(y)=∅ to x*y = x∪y

Gdyby rzoszerzyć F(X,I) do {0,1}XF(X,I) i rozszerzyć operację *, tak aby {0,1}XF(X,I) z tą operacją była tzw. grupoidem.

Są pewne naturalne pytania: Np. na ile sposobów i jak operacja * da sie rozszerzyć do abelowej operacji na wszystkie pary tak by dom(x*y) = dom(x)∪dom(y) i * zachowywała porządek.
Warto zwrócić uwagę że jeżeli taka operacja spełnia warunek:
∀x,y,z,t dom(x)=dom(y)={s} i dom(z)=dom(t)={w} i x(s)=z(w) i y(s) = t(w) => (x*y)(s)=(z*t)(w)
to w naturalny sposób definiuje ona nową operację + w następujący sposób:
x+y = ({(s,x)}*{(s,y)})(s) gdzie s jest pewnym s∈X.
Czy ta operacja musi być zgodna z porządkiem ?
Jest tu wiele podobnych pytań.

Jaki związek z mozaikami?
Jeżeli za X przyjmiemy zbiór liczb pierwszych a za I={1} można szybko skonstrułować izomorfizm między mozaikami liczb naturalnych F(X,I).
Tu jeszcze na X mamy liniowy porządek, który umożliwia jeszcze wzbogacenie dyskutowanych struktur. I prowadzi do nowych pytań.
Moze rzeczywiście z takich pytań może się urodzić jakieś ciekawe nowe spojrzenie na strukturę półgrupy liczb naturalnych?

OK. Na razie tyle na temat mozaikowy, bo trochę mnie ten post zmęczył. Może jeszcze wrócę do kiedyś do tego zagadnienia.

Wynurzenia miłośnika surfini

Nawiążę do mojego bukolicznego postu z maja i przyznam, że kwiatki, które posadziliśmy na balkonie to surfinie - cierpliwością, sprytem i miłością do rzeczy pięknych właściwymi tej nacji stworzone dzieło japońskich ogrodników.
Niewiele jest tak przyjemnych rzeczy jak doglądanie owych szybko rosnących i jednocześnie urokliwych roślin o fioletowo różowych (w przypadku naszego kwietnika) kwiatach.
Surfinie to prawdziwe dziecko globalizacji. Petunie, których surfinia jest odmianą pochodzą z Ameryki Południowej i są blisko spokrewnione z tytoniem. Surfinia zaś, jako się rzekło została wyhodowana w Japonii. Nie dziwi mnie to wcale - poznałem ogrodniczy zapał Japończyków osobiście kiedym w 2003 roku spędził tam szalony miesiąc niemalże, rozdarty między Yokohamę Totsukę i Kawasaki w natłoku zajęć służbowych znalazłwszy dzień na wizytę w buddyjskich klasztorach Kamakury (i otaczających je ogrodach).
Tak więc Daleki Wschód i Nowy Świat spotykają się na Starym Kontynencie, a dokładniej w Krakowie, w trzech skrzynkach na naszym balkonie.
Ze swoim kuzynem tytoniem surfinia nie dzieli co prawda popularności jako lekkiego narkotyku ani tym bardziej złej sławy zabójcy i (niezasłużonej) niszczyciela systemów opieki zdrowotnej i emerytalnych, natomiast dzieli słabość do choroby zwanej mozaiką tytoniową. Badanie tej choroby roślin pozwoliło Martinusowi Beijerinckowi u schyłku XIX stulecia postawić i uzasadnić hipotezę istnienia innych niż znane do tej pory mikroorganizmów, tj. wirusów.
Wirus jest dziwnym stanem materii - na pograniczu świata ożywionego i nieożywionego. Zwięzła białkowa struktura o geometrycznej niemal prostocie kryje w sobie jedynie RNA lub DNA. Jeszcze chemia czy już biologia? Czy to pytanie ma sens?
Każdy kto codziennie z uwaga przygląda się roślinom, najlepiej jeszcze kiedy opiekuje się nimi od nasionka, które sam wsadził w ziemię, musi zastanowić się, jak to jest, że to amorficzne coś czym jest gleba, woda, gaz wypełniający atmosferę i światło słońca przemienia się w procesie ześrodkowanym w owym miejscu w przestrzeni jakim jest roślina w złożoną strukturę o zróżnicowanych tkankach, i pięknych i skomplikowanych formach. To coś - mimo, że zjawisko znane - przeciwnego intuicji, która każe szukać raczej rozpadu i wzrostu entropii w pozostawionych samym sobie procesach. Pachnie to trochę mistycyzmem. Co jakiś czas w końcu - w oderwaniu "geograficznym" od pierwotnego procesu rozpoczyna się nowy - nowe nasionko w skomplikowanym fizyczno-chemicznym tańcu zaminia się w kolejną roślinę. Wygodniej jest chyba zatem myśleć o jednym w istocie procesie: życiu. W tym sensie - wirusy są istotną i aktywną częścią tego procesu, choć jeśli spojrzeć na nie redukcjonistycznie: jako na wydrębnionyz głównego podproces - organizm, są albo formą skrajnie pierwotną albo skrajnie uproszczoną (może hyperwyspecjalizowaną ?) typowych organizmów.
Zdaje się, że naukowe ogarnięcie życia jako procesu nie sprowadzi się w ostateczności do badania i odkrywania elementarnych cegiełek go stanowiących. Potrzebna jest nowa matematyka, której zręby być może już się utoworzyły, dająca możliwość ogarniania niesamowitych zjawisk do których należy życie.
Kiedy myslę o - anegdotycznym już dzisaj - odkryciu Beijerincka, który odfiltrowawszy wodę, która miała kontakt z zakażonym tytoniem filtrem tak silnym, że zatrzymał wszelkie bakteria odkrył, że otrzymany destylat nadal zaraża tytoń, co doprowadzio go do wniosków, które uczyniły go sławnym, nie mogę nie myśleć o podstawowych prawdach dociekań empirycznych ujętych swgo czasu przez Milla w formie tzw. kanonów Milla. To przewodnikcy Beijenricka ale i niezliczonej a zacnej grupy naukowców, lekarzy i inżynierów. Sam, jako, że czasem zajmuję się diagnostyką systemów technicznych odkrywam ze zdziwieniem, że owe proste metodologiczne prawdy są tak trudne czasem w stosowaniu. Koniec na dziś. Trzeba podlać surfinie.

Raj i piekiełko

Są takie chwile, kiedy na moment otwierają się kraty solipsystycznego więzienia jakie człowiek sam buduje w swojej głowie i można ręką dotknąć, okiem zobaczyć, uchem usłyszeć Rzeczywistość. Czy o to chodzi w buddyjskim doświadczeniu zwanym z japońska kensho? Nie wiem, ale wiem, że spotkało mnie to dziś kiedy przemierzałem niewielki odcinek drogi pomiędzy końcowym przystankiem autobusu a bramą firmy gdzie pracuję. Żywe doświadczenie realności i piękna świata, którkotrwały wgląd w jego prawdziwą naturę. Może ma coś z tym wspólnego kawałek łąki wzdłuż której biegnie chodnik? To bujne pole bitwy o słońce, wodę i glebę (z całą masą zawartych w niej pożywnych pierwiastków) toczonej przez tyleż dziarskie co pospolite trawy, zioła i inne chwasty. Eksponują swoje przeznaczone dla oczu owadów wdzięki, żywe ale nie krzykliwe kolory które dobierały przez miliony lat ewolucji, przywodząc na moment wyobrażenie raju.
Niedawno czytałem, że większość kultur ludzkich ma podobne wyobrażenie miejsca wiecznej szczęśliwości. Jest to nie tyle ogród co bardziej sawanna: równina pokryta trawą z rozrzuconymi niezbyt gęsto drzewami pewną ilością wody w postaci stawów lub strumieni i błękitnym niebem z niewielką ilościa chmur rozpostartym nad tym krajobrazem. Wedle tego wzoru ludzie urządzają swoje ogrody i parki, to tło literackich i malarskich sielanek ("Wśród takich pól przed laty, nad brzegiem ruczaju, na pagórku niewielkim, we brzozowym gaju ..."). Utrwalona w świadomości gatunku fotografia jego pierwotnej siedziby? Wspomnienie z dzieciństwa człowieczeństwa, jak większość wspomnień z dzieciństwa, szczęśliwe?
Mam i ja więc swój mały, sezonowy i z rzadka, niestety, dostrzegany kawałek raju koło którego niemal co dnia przechodzę.
Moje kensho, jak na kensho przystało, trwało krótko. Wróciłem w duszne ściany własnego umysłu.

Mam tu między innymi swoje piekiełko matematycznych obsesji.

Ostatnio wciągnął mnie za sprawą pewnej pracy temat minimalnych gramatyk. Zagadnienie (jak i wiele pokrewnych od niego, m.in ukryte modele Markova) zdaje się mieć wiele zastosowań już istniejących (np. kompresja danych) jak i jeszcze więcej potencjalnych. To jeden z punktów widzenia, dla których warto sie tym problemem zajmować, poza przyrodzoną samą urodą tematu. Mnie jednak fascynuje coś innego - potencjalne związki z teorią liczb. A nawet ogólniej - na kanwie już a nie bezpośrednio sprowokowany artykułem - pytanie o relacje między obliczalnościa a teorią liczb.

Pomysł jest, ogólnie rzecz biorąc, taki:

Jak wszyscy wiemy rozwinięcia liczb wymiernych w pozycyjnym systemie zapisu liczb, jest zawsze ostatecznie okresowe, tj. od pewnego momentu ciąg cyfr przy stosownej podstawie zaczyna się w rozwinięciu powtarzać. Przypadek, kiedy rozwinięcie jest po prostu skończone, sprowadza się do tego samego przypadku, jest bowiem ono ostatecznie okresowe, przy czym z okresem 1 powtarza się liczba 0.
Odwrotnie, liczba która nie ma takiego rozwinięcia jest po prostu niewymierna.
Jak niektórzy z nas wiedzą, liczba wymierna jest wyrażalna jako skończony ułamek łańcuchowy, i odwrotnie, skończone ułamki łańcuchowe definiują liczby wymierne. Natomiast nieskończone, ostatecznie okresowe ułamki łańcuchowe odpwiadają niewymiernym, rozwiązaniom równań kwadratowych o współczynnikach wymiernych. Co więcej, najbardziej popularne liczby rzeczywiste, po prostu gwiazdy continuum, cechują się wyjątkową regularnością jako ułamki łańcuchowe.

Widać wzorzec? Regularność reprezentacji liczby oznacza, że jest ona "prosta" według jakiegoś innego kryterium (np. jest wymierna, albo jest pierwiastkiem równania kwadratowego)
To w naturalny sposób prowadzi do szeregu interesujących pytań. Czy jest jakieś kryterium na ułamki łańcuchowe pozwalające powiązać budowę automatu generującego kolejne elementy łaćucha z własnością liczby reprezentowanej przez dany ułamek, np czy można podać kryterium "łańcuchowe" na bycie pierwiastkiem 3-go stopnia? Podobnego pytania dla rozwinięć pozycyjnych.
Kolejnego pytania, tym razem powiązanego z minimalnymi gramatykami: załóżmy, że umiemy znaleźć gramatykę minimalną rozwinięcia pozycyjnego pewnej liczby obciętego do n miejsc po przecinku. Jej długość (sprawdźcie artykuł szukając definicji) będzie się na ogół zwiększała z rozmiarem n. Czy tempo tego zwiększania (ewentualnie jakaś inna miara z nim związana) w naturalny sposób dzieli liczby na klasy, ustawia klasy w hierarchie i w dole tej hierarchii lokuje liczby w jakimś sensie proste (np. pierwiastki wielomianów itp).
Jest parę innych tu zagadnień, powiązanych ze wspomnianymi, które warto podjąć ale ich tu nie zanotuję. W każdym razie, temat jest intrygujący i niepokojący. Można też przy okazji - co ważne, bo kiedy myślenie nie idzie, trzeba czymś zająć ręce - pobawić się komputerem. By upiec jeszcze jakąś pieczeń na tym ogniu przy pisaniu programów po raz n-ty podejdę do Haskella, języka programowania dla prawdziwych matematyków. Podejdę od zera niemal, bo prawie zapomniałem czego się już kiedyś nauczyłem :(.