W poprzednim wpisie przedstawiłem zapis macierzowy konwergentów ułamka łańcuchowego. Zdefiniowaliśmy macierze S oraz T w następujący sposób:

T= \left| \begin{array}{cc}  0&1 \\  1 & 1 \\  \end{array} \right|;  S = \left|\begin{array}{cc}  0&1\\  1&0 \\  \end{array}\right|

Dla zadanego ułamka łańcuchowego {[a_{0},a_{1}, \ldots ,a_{n}]= q_{n} = \frac{h_{n}}{k_{n}}} który może być rozumiany jako ułamek skończony lub n-ty kowergent ułamka skończonego lub nieskończonego {[a_{0},a_{1}, \ldots ]} wprowadziliśmy dodatkową macierz konwergentów {M} w postaci:

M(q_{n}) = M([a_{0};a_{1},...a_{n}]) =  \left|\begin{array}{cc}  h_{n-1}&h_{n}\\  k_{n-1}&k_{n}\\  \end{array}\right|

Stosując wprowadzone definicje macierzy S i T i M zapisaliśmy macierz konwergentów w następującej postaci:

M = S S (ST)^{a_{0}} S (ST)^{a_{1}} \ldots S(ST)^{a_{n}} = S \prod_{i=0}^{n} S (ST)^{a_{i}}

W tym wpisie wskażemy na kilka interesujących własności macierzy S, T oraz kilku innych obiektów które zdefiniujemy. Jako podstawowy fakt wskażmy, że macierz M ma wyznacznik równy {\pm 1} co możemy zapisać za pomocą wartości bezwzględnej w następującej postaci: {\left| \det(M) \right| = 1}. Ponieważ powyższe wyrażenie przedstawia M jako iloczyn macierzy S i T – ich wyznaczniki mają ta samą, fundamentalną własność. Zależność pomiędzy numerem konwergentu n, znakiem wyznacznika {M(q_{n})} i inne relacje pomiędzy kowergentami czytelnik może znaleźć w książce Chiniczyna, w podręcznikach Teorii Liczb lub w wikipedii. Temat ten zostanie podjęty także w tym cyklu, nieco później.

Rozpocznijmy od prostej obserwacji wynikającej z bezpośredniego rachunku. Zachodzi następująca zależność:

S^{2} =  \left|\begin{array}{cc}  0&1\\  1&0\\  \end{array}\right|  \left|\begin{array}{cc}  0&1\\  1&0\\  \end{array}\right| =  \left|\begin{array}{cc}  1&0\\  0&1\\  \end{array}\right| = I

gdzie {I} oznacza macierz jednostkową. Ponieważ każdy ułamek łańcuchowy może być przedstawiony w postaci jak w równaniu zawierającym macierz konwergentów M powyżej, to mamy do czynienia z ciekawą strukturą algebraiczną. Analizując strukturę tego zapisu łatwo dostrzec, że w każdym zapisie macierzy konwergentów obok siebie nie mogą występować dwie macierze S pod rząd – wówczas bowiem skróca się one do macierzy jednostkowej {I}. Oznacza to że każda macierz konwergentów M składa się z iloczynu potęg macierzy (ST) rozdzielonych pojedynczymi macierzami S. Mamy tu do czynienia z monoidem, nazwijmy go MCF, którego elementy to słowa złożone z alfabetu {<S,G>} gdzie G=ST, który to monoid posiada następująca prezentację:

MCF = \{ (S,G), S^{2}=1 \}

Monoid ten jak widać posiada dwa generatory S i G oraz jedną relację {S^2=1}. Mnożenie nie jest tu przemienne. Brak także elementów odwrotnych dla macierzy S i T czy G – stąd mówimy o monoidzie a nie o grupie. Mamy jednak element jednostkowy {S^{2} = I}. Dlaczego zdecydowałem się zatem komplikować zapis i wprowadziłem macierz T? Otóż ona także spełnia ciekawą zależność która zaintrygowała mnie i sprawiła że zacząłem bawić się tą bardziej złożoną strukturą:

T^2 = I + T

Niestety zależność ta nie może dotyczyć elementów monoidu MCF – jest to relacja dotycząca macierzy T, a w kontekście monoidu może co najwyżej dotyczyć pierścienia nad nim. I właśnie tej struktury będzie dotyczyła dalsza część wpisu. Rozważmy zatem pierścień RCF ( litera R pochodzi od angielskiej nazwy pierścień – ring ) zdefiniowany jako struktura algebraiczna złożona z formalnych sum dowolnych iloczynów elementów z MCF ze współczynnikami ze zbioru liczb wymiernych Q. Formalnie zapisuje się to jako pierścień RCF = Q[MCF].

W pierścieniu takim elementy możemy mnożyć miedzy sobą – i takie iloczyny odpowiadają elementom monoidu bazowego. Dopuszczamy mnożenie takich wyrażeń przez liczby wymierne, oraz możemy czysto formalnie elementy monoidu, pomnożone przez liczby wymierne – dodawać – co pozwala definiować wielomiany nad elementami monoidu.

Z powodu ostatniej wypisanej zależności w pierścieniu Q[RCF] wszystkie wyrażenia nie zawierają potęg T wyższych niż pierwsza! Czyli każde z tych wyrażeń, gdyby je maksymalnie uprościć zawiera tylko S i T w pierwszej potędze. Monoid taki wydaje się być bardzo ciekawym obiektem, gdyby bowiem związać rachunki jakie w nim się przeprowadza, a wszystkie wielomiany zależne od S i T muszą się tu redukować do wyrażeń liniowych w S i T, z rachunkami dotyczącymi ułamków łańcuchowych – moglibyśmy otrzymać potencjalnie ciekawe rezultaty. Uproszczenie takie jednak nie możliwe jest w monoidzie bazowym MCF z prostej przyczyny: {ST \neq TS} i w ramach monoidu nie ma możliwości zamiany ich kolejności. Komutator w monoidzie elementów S i ST nie daje się uprościć, ba! skoro nie ma elementów odwrotnych – nie jest on nawet zdefiniowany! Inaczej – ponieważ w monoidzie nie ma elementów odwrotnych do S i T, iloczyn {ST} nie wyraża się przez {TS} (dowód tego faktu mógłby się opierać na twierdzeniu że ułamki łańcuchowe, równoważnie definiowane jako elementy monoidu generowanego przez macierze L,R, czyli elementami monoidu wolnego . Czyli nie ma żadnych dodatkowych relacji w prezentacji tego monoidu za pomocą macierzy L i R, a zatem i S,T. Gdyby taka relacja istniała monoid \{ S,ST \} nie byłby wolny). Całkiem podobnie, niestety, sprawy mają się w pierścieniu RCF – wyrażenie iloczynu ST przez TS jest nadal niemożliwe. Jednak mamy nieco większa swobodę – możemy definiować dodatkowe elementy które nie mają swoich odpowiedników w monoidzie. Wprowadźmy dodatkowa macierz L, zdefiniowaną jako komutator w pierścieniu macierzy S i T – czyli w postaci {L = [S,T] = ST-TS}. mamy w ten sposób zbiór czterech macierzy:
(1)  I = \left|\begin{array}{cc}  1&0\\  0&1\\  \end{array}\right|;  S = \left|\begin{array}{cc}  0&1\\  1&0\\  \end{array}\right|;  T= \left|\begin{array}{cc}  0&1\\  1&1\\  \end{array}\right|;  L = [ S,T ] =  \left|\begin{array}{cc}  0&1\\  -1&0\\  \end{array}\right|

Posługując się macierzami zdefiniowanymi powyżej możemy skonstruować następująca tabelkę mnożenia w pierścieniu {Q[RCF] = Q[ \{I,S,T,L \}]}:

generator I S T L=[S,T]
I I S T L
S S I I+(1/2)S+(1/2)L -I-2S +2T
T T I+(1/2)S-(1/2)L I+T -I-(5/2)S +2T +(1/2)L
L L I+2S-2T I+(5/2)S -2T +(1/2)L -I

Jak widać wszystkie mnożenia pomiędzy elementami wyrażają się przez liniowe kombinację tych elementów. Oznacza to po pierwsze, że mamy do czynienia z zamkniętą strukturą algebraiczną. Struktura ta jednak jest ogólniejsza niż wyjściowy monoid zawierający jedynie kombinacje z pewnego podzbioru generatorów. Co więcej – macierze w monoidzie, o ile mają reprezentować ułamki łańcuchowe muszą mieć moduł wyznacznika równy 1. Napiszemy o tym dalej, dochodząc do ciekawych wniosków.

Jaka szkoda że w powyższej tabeli występują współczynniki wymierne. Gdyby były one wyłącznie liczbami całkowitymi – mielibyśmy do czynienia z sytuacją niezwykle interesująca. Niestety – czynniki są wymierne – dlatego zaczęliśmy od definicji pierścienia nad ciałem liczb wymiernych – nie ukrywam że kiedy sam rozpoczynałam analizę miałem cichą nadzieję że liczby całkowite jakimś cudem wystarczą – niestety. Szału nie ma. Ale tez nie jest całkiem nieciekawie! Warto zadać sobie pytanie: czy istnieją inne, macierzowe lub nie, struktury algebraiczne w których działania mogą być opisane tabelką powyżej. Na przykład czy da sie taką tabelkę zbudować dla jakiegoś zbioru macierzy 3×3? Są pewne poszlaki że jest to możliwe, o czym na końcu.

Podsumujmy sytuację. Mamy pierścień {Q[ \{I,S,T,L \}]} w którym obowiązują prawidła mnożenia jak powyżej, w którym każde wielomian redukuje się do wyrażenia liniowego w generatorach monoidu bazowego. Elementy zbioru {\{ I,S,T,L \}} sa liniowo niezależne, dlatego każda macierz konwergentów {M} można w nim rozłożyć na kombinację liniowa generatorów:

M = aI+bS+cT+dL =   \left|\begin{array}{rr}  a & b + c + d \\  b + c - d & a + c  \end{array}\right|

gdzie liczby a,b,c,d są liczbami całkowitymi w wypadku macierzy reprezentujących konwergenty ( bo liczniki i mianowniki konwergentów sa liczbami naturalnymi) a liczbami wymiernymi w ogólnym przypadku. Wygląda na to że mamy tu przestrzeń liniową w której macierz konwergentów ( a w istocie dowolną macierz 2×2 ) może być reprezentowana przez wyrażenia jak wyżej. Rozważmy kiedy taka reprezentacja jest reprezentacją ułamka łańcuchowego.

Aby zapewnić że takie formalne przedstawienie reprezentuje ułamek łańcuchowy musimy spełnić dodatkowy warunek związany z wyznacznikiem macierzy M. Przypomnijmy – chodzi o warunek \left| \det(M) \right| = 1. Oznacza on, że zachodzi zależność miedzy liczbami wymiernymi {\{ a,b,c,d \}} daną równaniem

\left| \det(M) \right| = \left| (a + c)a - (b + c - d)(b + c + d) \right| =

= \left| a^{2} + a c - b^{2} - 2 \, b c - c^{2} + d^{2} \right|

Jak rozumieć tą relację?

Przyjmijmy że zaczynamy od pierścienia {Q[RCF] = Q[ \{I,S,T,L\}]}. Elementy tego pierścienia zadane sa jako wyrażenia liniowe w czterech generatorach pierścienia. Można je reprezentować jako czwórki liczb wymiernych – wektory ( w postaci kolumn) {w = [a,b,c,d]}. W przestrzeni takich wektorów zdefiniujmy następująca formę kwadratową:

(2) B = \left(\begin{array}{rrrr}  1 & 0 & \frac{1}{2} & 0 \\  0 & -1 & -1 & 0 \\  \frac{1}{2} & -1 &-1 &0\\  0 & 0 & 0 & 1  \end{array}\right)

Prawdziwy jest wówczas związek:

(3) \left| wBw^{T} \right| =  \left| \left( \begin{array}{cccc}  a & b &c & d  \end{array}\right)  \left( \begin{array}{cccc}  1 & 0 & \frac{1}{2} & 0\\  0 & -1 & -1 & 0\\  \frac{1}{2} & -1 & -1 & 0\\  0 & 0 & 0 & 1  \end{array}\right)  \left( \begin{array}{c}  a\\  b\\  c\\  d\\  \end{array}\right) \right|=
= \left| \det(aI+bS+cT+dL) \right| = \left| a^{2} + a c - b^{2} - 2 b c - c^{2} + d^{2} \right|

Otrzymaliśmy zatem wniosek – w przestrzeni wektorów {w} te wektory które reprezentują macierze konwergentów ułamków łańcuchowych, zadane są przez powierzchnię zdefiniowana za pomocą formy kwadratowej B – czyli leżą na pewnej kwadryce. Dodatkowo powinniśmy wymagać, by elementy wektora $[ a.b.c.d ]$ były takimi liczbami całkowitymi by macierz M miała wyłącznie dodatnie czynniki. Spełnienie tych warunków w oczywisty sposób pozwala nam uznać ze macierz M reprezentuje ułamek łańcuchowy.

Podsumujmy. Aby macierz M=aI+bS+cT+dL reprezentowała ułamek łańcuchowy musi spełniać warunek zadany przez równanie kwadryki \left| wBw^{T} \right| = 1 oraz liczby a,b,c,d muszą być liczbami całkowitymi spełniającymi następujące nierówności:

(4) \begin{array}{ll}  a \geq 0; & d  \geq 0 ; \\  b \geq -c ;& c \geq -a;   \end{array}

Mamy tu zatem podzbiór całkowitoliczbowy kwadryki leżący w podprzestrzeni o współrzędnych a,b,c,d zadanych powyższymi nierównościami.

Ponieważ ułamki łańcuchowe skończone są, jako liczby, po prostu elementami ciała liczb wymiernych możemy je dodawać i mnożyć. Operacje te nie wyprowadzają poza zbiór ułamków łańcuchowych więc istnieją stosowne funkcje które parze wektorów {w} i {w^{'}} przyporządkowują ich sumę i iloczyn – które da się reprezentować jako elementy naszej kwadryki. Sytuacja jest tu zatem nieco podobna do tej w teorii krzywych eliptycznych. Co więcej – suma i iloczyn ułamków łańcuchowych mogą być wyliczane za pomocą tak zwanego algorytmu Gospera – bezpośrednio w przedstawieniu ułamków jako list czynników {[a_{0},a_{1}, \ldots ,a_{n}]} bez konieczności używania ich liczbowej reprezentacji za pomocą zwykłych ułamków. Niestety reprezentacja stosownych funkcji sumy i iloczynu jest raczej skomplikowana, choć elementarna, i choć użyteczna w algorytmach komputerowych, niezbyt ciekawa dla rachmistrza posługującego się kartką, ołówkiem i rozumem.
Po co to wszystko? Czy istnieje możliwość zapisania wartości ułamka łańcuchowego {[a_{0},a_{1}, \ldots ,a_{n}]} za pomocą macierzy jakie tu wprowadziliśmy. Tak! Zależność taką da sią skonstruować, wpadłem na nią w czysto rachunkowy sposób, można powiedzieć – błądząc, jednak fakt, że zależność ta zapisuje się w ładny sposób za pomocą elementów z pierścienia RCF wydaje mi się znacząca. I jest to główny wynik który chciałem Państwu w tym cyklu wpisów przedstawić.

Przypomnijmy że M to macierz konwergentow odpowiadająca danemu ułamkowi łańcuchowemu. Prawdziwa jest następująca zależność:

(5) \boxed{x = [a_{0},a_{1},...a_{n}] =\frac{h_{n}}{k_{n}}= - \frac{1}{2} \frac{ tr (\, M(S- L)\,) }{ tr (\, M(S-T) \,) }}

gdzie {tr} to ślad macierzy ( suma elementów na głównej przekątnej). Warto zwrócić uwagę na fakt, że z powodu własności operacji śladu, powyższa formuła pozwala na zmianę „reprezentacji” generatorów pierścienia RCF za pomocą transformacji podobieństwa. Być może wskazuje to na pewnego rodzaju „uniwersalność” tej zależności i być może możliwe jest jej uogólnienie tak by dotyczyła ona nie omawianej tutaj, konkretnej reprezentacji generatorów SI,S,T,L ale struktur algebraicznie całkowicie ogólnych – na przykład pewnej abstrakcyjnej algebry nieprzemiennej.

Na dziś to wszystko. Proszę o zastanowienie się nad znaczeniem ostatniego wzoru. O ile wiem jest to nowy, nigdzie niepublikowany rezultat. Wzór ma postać ułamka, zaś jego licznik i mianownik, rozpatrywane jako funkcje jest wielomianem zmiennych {a_{0},a_{1}, \ldots ,a_{n}} – jest to tak zwany wielomian kontynuant. Więcej informacji na jego temat można odszukać w znanej książce Ronald.L.Graham, Donald.E.Knuth, Oren Patasnik „Matematyka konkretna” rozdział 6.7 Kontynuanty. Zwracam uwagę na spora ilość znanych i opisanych w tej książce własności tych wielomianów. Spora część z nich ma swoje pochodzenie w relacjach z tabelki mnożenia która tu przytoczyliśmy zastosowanej do „przekomutowania” macierzy {ST} w wyrażeniach na M występujących wewnątrz operacji śladu powyżej.

Pasjonujące mogłoby być badanie jak powyższe operacje zrealizować dla ułamków nieskończonych. Przypuszczam że jest to możliwe a nawet relatywnie proste przez stosowne przejścia graniczne. Bardzo ciekawa natomiast jest z pewnością kwestia jak owe przejścia graniczne mają się do zdefiniowanej kwadryki. Zapewne pomocna byłaby analiza za pomocą takich narzędzi jak przestrzeń rzutowa. Kto wie co mogłoby się kryć w nieskończoności…

Być może pojawi się kolejny wpis – w którym przedstawię Państwu własności tych wielomianów. W poprzednim wpisie obiecałem workbook Sage zawierający zdefiniowane w tych wpisach pojęcia. Workbook taki jest prawie gotowy – postanowiłem jednak wpisać w nim angielskie komentarze. Postaram się go udostępnić w skończonym czasie…