Raz za oknem żar. Rekordowe temperatury. Organizm traci wodę. Potem odmiana. Ulewa, burza. Potem 15 stopni za oknem. Klimat umiarkowany, nie ma co...
W takich okolicznościach przyrody zwolniłem z lekturami. Diogenes Laertios i jego plotkarskie opowiesci o greckich perwersjach umysłowych powędrował z porotem na półkę z zakładką włożoną gdzieś w jednej czwartej grubości książki. Prz łóżku wala się - bo wezbrał we mnie apetyt na jakiś wielki epicki kawałek - drugi już tom "Nędzników" Wiktora Hugo. Wielka literatura w starym dobrym stylu.
Poczta, z przygodami dostarczyła mi dwie książeczki, które korzystając z przyjemnego dla polskiego konsumenta kursu dolara kupiłem wysyłkowo w Amazonie. Bawię się językiem Haskell (jedna z nich jego m.in. dotyczy) odkrywając kolejne więzi między programowaniem, matematyką i resztą świata.
W moim prywatnym piekiełku, po lekturze kilku prac i wertując kolejną amazonową książkę, jakby się trochę przejaśnia. Ależ byłem głupi formułując w naprędce i na bazie słabej intuicji moje małe hipotezy (tu)! Sprawa jest, jak to w życiu bywa, znacznie bardziej tajemnicza i głęboka. Jak pozbieram myśli do kupy, i zsyntetyzuję to co dotychczas na ten temat przeczytałem, to pewnie coś na ten temat napiszę i na blogu. W każdym razie związkami między regularnościami i pewnymi formami "automatyzmu" w różnych typach przedstawień liczb matematycy zajmują się od dawna i sporo na ten temat wiadomo a jeszcze więcej, jak można się domyślić, nie wiadomo.
Przy okazji drobnych studiów nad tym tematem, wróciłem do powiązanych z nim spraw, którymi trochę zajmowałem się w zeszłym roku: koalgebry itd. Stąd już niedaleko do innych konstrukcji opartych na teorii kategorii w tym i monad więc z powrotem do Haskella i jego wysoce zmatematyzowanych abstrakcji. Takie to wiry, szumy zlepy i ciągi tego lata ...
Z innej, ale podobnej beczki: Ale się czasem trafia uroczy kawałek matematyki!
Kilka tygodni temu na arxiv pojawiła się praca australijskiego matematyka N.J.Wildbergera pt. "Pell's equation without irrational numbers". Praca jest krótka, elementarna (poza szkolną matematykę wychodzi chyba tylko pojęcie macierzy: ich mnożenia i wyznacznika, ale w superprostych przypadkach) i prosta, tj. dowody są bardzo klarowne. W sam raz na niecałą godzinę czytania.
Przypominam równanie Pella:
x^2-D*y^2 = 1
gdzie x i y to szukane a D > 0 jest liczbą naturalną niebędącą kwadratem. Chcemy równanie to rozwiązywać w liczbach naturalnych (>0).
Algorytm klasyczny (nie wiem kto go podał jako pierwszy: Lagrange ?) polega na rozwijaniu pierwiastka kwadratowego z D do ułamka łańcuchowego .Dowodzi się, że takie rozwinięcie jest okresowe i bierze się odpowiedni n-ty redukt gdzie n jest funkcją długości okresu. Jaką funkcją: szczerze mówiąc nie pamiętam teraz, ale to łatwo znaleźć na sieci.
Autor podaje algorytm rozwiązywania równania Pella odmienny od tego algorytmu. Postaram się tu pokrótce go przedstawić i mam nadzieję, że niczego nie pomieszam:
Oznaczenie: Przez X^T gdzie X jest macierzą, rozumiem macierz transponowaną do X (tj taką, której wiersze odpowiadają kolumnom X).
Wychodzimy od macierzy:
|1 0|
A = | |
|0 -D|
gdzie D to owo D z równania Pella. Rozważamy też macierz:
|1 1|
R = | |
|0 1|
Konstruujemy ciąg macierzy B_0, ... w taki sposób, że B_0 = R^T lub R, tak, by macierz B_0^T*A*B_0 miała własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Dowodzi się, że można wybrać jednoznacznie między T i R^T.
Potem, indukcyjnie: mając zdefiniowane B_n, definiujemy B_(n+1) = B_n*R lub B_n*R^T, tak by B_(n+1)^T*A*B_(n+1) miała wspomnaną wyżej własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Ponownie dowodzi się, że w każdym kroku można wybrać jednoznacznie między T i R^T.
Dowodzi się, że dla pewnego n, macierz B_n z tego ciągu ma własność B_n^T*A*B_n = A. Pierwsza kolumna macierzy B_n wyznacza wówczas rowziązanie równania Pella.
Niestety autor nie dowodzi, że wynikiem działania algorytmu jest najmniejsze rozwiązanie. Ja zamierzam się sprawdzić w ustaleniu tego.
Algorytm zaimplementuję, oczywiscie w Haskellu i obiecuję przedstawić tu program.
W ogóle do Haskella będę wracał, bo to naprawdę fascynujący język, zmuszający do zmiany sposobu myślenia. Poza tym jest bardzo sexy i gdybym nie był żonaty podrywał bym na niego dziewczyny.
2008-07-14
2008-06-17
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.
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
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.
2008-06-16
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.
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.
2008-06-06
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 :(.
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 :(.
Subskrybuj:
Posty (Atom)
Posty
