Na prawym marginesie - nowy gadżet. Z grubsza jest to zabawka (niedoskonała mocno) związana z L-systemami. Napiszę o niej i o nich coś więcej wkrótce. Zaby uruchomić: Najpierw kliknąć na link :"Gdy wyrasta kwiat ze ziemi ..." Potem na "Niech wyrasta ...". Można modyfikować reguły i dodawać nowe. Na własną odpowiedzialność oczywiście...
Działa w Firefoxie. W IE, przynajmniej moim, nie.
Miłej (ewentualnie) zabawy...
Aha! Frazeologia zaczerpnięta z wierszyka, który kiedyś popularyzował mój kolega z akademika:
"Gdy wyrasta kwiat ze ziemi, wszyscy są zadowoleni, lecz gdy rośnie trawa: to już inna sprawa..."
2008-07-25
2008-07-15
Haskell i Pell
Jak mówiłem tak zrobiłem, tj. sprawdziłem algorytm Wildbergera w praniu. Poniżej kod funkcji rozwiązującej równanie Pella w oparciu o ów algorytm w Haskellu. Poza rekurencją i "pattern matching" nie demonstruje on pazura Haskella, ale mam nadzieję, że jest równie przyjemny w czytaniu jak był w pisaniu...
Funkcja solvePell, bierze d z rówania Pella jako argument i zwraca parę liczb będąca pewnym rozwiązaniem równiania. Trzeba pamiętać, by d nie było kwadratem - tego funkcja nie sprawdza. Na kwadratach wchodzi zwykle w nieskończoną rekurencję ... Niestety, są i smutniejsze wieści. Algorym nie zawsze znajduje rozwiązanie fundamentalne. Np. dla d = 13, rozwiązaniem fundamentalnym jest x=18 y=5, podczas gdy zaimplementowany algorytm daje rozwiązanie: x=649 y=180, które jest następnym z kolei (bo 649=18^2+13*5^2 i 180 = 2*5*18). Tym samym zrozumiałe staje się, dlaczego w pracy Wildbergera nie było stosownego dowodu ;). Warto pomyśleć, czy nie da się tej metody jakoś zmodyfikować (nie zmieniając jednak jej ducha) by algorytm zwracał zawsze rozwiazanie fundamentalne.
solvePell :: Integer -> (Integer, Integer)
solvePell d = (b11, b21) where
(b11, b12, b21, b22) = searchFixedPointMtr (1, 1, 0, 1) where
searchFixedPointMtr p | (o11, o12, o21, o22) == (1, 0, 0 , -d) = r
| o11 > 0 && o22 < 0 = searchFixedPointMtr r
|otherwise = searchFixedPointMtr tr where
r = mult p (1, 1, 0, 1)
tr = mult p (1, 0, 1, 1)
(o11, o12, o21, o22) = mult( mult (transpose r) (1,0,0,-d) ) r
transpose (a11 ,a12, a21, a22) = (a11, a21, a12, a22)
mult (a11, a12, a21, a22) (b11, b12, b21, b22)=
(a11*b11+a12*b21, a11*b12+a12*b22,
a21*b11+a22*b21, a21*b12+a22*b22)
Funkcja solvePell, bierze d z rówania Pella jako argument i zwraca parę liczb będąca pewnym rozwiązaniem równiania. Trzeba pamiętać, by d nie było kwadratem - tego funkcja nie sprawdza. Na kwadratach wchodzi zwykle w nieskończoną rekurencję ... Niestety, są i smutniejsze wieści. Algorym nie zawsze znajduje rozwiązanie fundamentalne. Np. dla d = 13, rozwiązaniem fundamentalnym jest x=18 y=5, podczas gdy zaimplementowany algorytm daje rozwiązanie: x=649 y=180, które jest następnym z kolei (bo 649=18^2+13*5^2 i 180 = 2*5*18). Tym samym zrozumiałe staje się, dlaczego w pracy Wildbergera nie było stosownego dowodu ;). Warto pomyśleć, czy nie da się tej metody jakoś zmodyfikować (nie zmieniając jednak jej ducha) by algorytm zwracał zawsze rozwiazanie fundamentalne.
Do badań porównawczych użyłem sprawdzonej już w bojach, on-linowej maszyny do poszukiwania fundamentalnych rozwiązań równania Pella którą niniejszym polecam: Diophantus Quadraticus. Dla miłośników numerologii, przykładowe wynik działania funkcji (pod Hugsem):
Main> solvePell 12
(7,2)
Main> solvePell 123
(122,11)
Main> solvePell 1234
(586327869067265,16691023073856)
Main> solvePell 12345
(1196823028442576899590849641,10771703481902106796084652)
Main> solvePell 123456
(32153667637494049,91511235212695)
Main> solvePell 1234567
(20371567825887579087969922203933358793493846332810110697
4127231916998110712447355624,1833441773536251588833840127
75408990796176026949965279326746283914164614149841725)
Main> solvePell 12345678
(84798178834254206501069091776063801828858638442491294173
283622693331157941169053721682146500840778040795681426799
746373774600679194577190578795925022609963251697702932038
103575417349220734335472506700750376403558084067176117304
353961009320426319261060613871588088528284393528998330022
695959115757272835324559892633223467646161202348129574120
811322088113694783,24133985779040703487042001168546778233
886602226457226201732495439539842758227586390869258263482
721919445559004333460853375915877499010684711766338764074
438034949056494509471323897949013056855661657290867499070
288510685596491236418010367399292614822499208206228574471
914923864025707862772212062023636759525773725225355147035
172813431107542245055578655655064)
2008-07-14
W słońcu i w deszczu
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.
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-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.
Subskrybuj:
Posty (Atom)
Posty
