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.