W 1855 zmarł Carl Friedrich Gauss. Trzy lata później w roku 1858 Moritz Abraham Stern został mianowany Ordinarius Na Uniwersytecie w Getyndze, zajmując tym samym katedrę Gaussa. Stern był pierwszym pełno-miarowym profesorem matematyki żydowskiego pochodzenia w Niemczech. W roku w którym obejmował stanowisko Gaussa Stern opisał ciekawą konstrukcję na liczbach wymiernych. Był to rodzaj listy ułamków ułożonych w pewnym porządku, tak, że dało się je narysować w postaci drzewa binarnego. Każdy wierzchołek w drzewie – rodzic, miał dwie wychodzące z niego gałęzie – dzieci. Związek pomiędzy wartościami rodziców i dzieci byl prosty ale intrygujący – napiszemy o tym niżej. Stern opisał ciekawe własności tej konstrukcji – jako zawodowy matematyk zajmował się teorią liczb zaś konstrukcja przypominała i uogólniała opisane wcześniej w 1818 roku ciągi Fareya – co zapewne było samo w sobie interesujące. Zupełnie niezależnie konstrukcję tą, z powodów praktycznych, w kilka lat później powtórzył francuski zegarmistrz Achille Brocot -było to w 1861 roku. Konstrukcja ta przeszła do historii pod nazwą drzewa Sterna-Brocota. Co takiego praktycznego zainteresowało Achille Brocota – zegarmistrza, którego ojciec także był zegarmistrzem – w uporządkowaniu ułamków w drzewo?
Problemem blisko związanym z zegarmistrzostwem jest konstrukcja przekładni zębatych. Mechanizm zegarowy musi transmitować napęd dając precyzyjną i z góry zadaną liczbę obrotów – często kilka zadanych liczb obrotów. Na przykład wskazówka godzinowa musi obracać się 2 razy podczas gdy minutowa 1440 razy na dobę. Ponieważ obie napędzane są z jednej sprężyny – trzeba skonstruować przekładnię zębatą która zapewni stosowne przełożenia – 1/720. W dawnych czasach koła zębate wykonywano ręcznie – precyzyjne wykonanie koła o dużej liczbie zębów jest nie lada wyzwaniem i bardzo czasochłonną pracą. Luksusowe produkty zegarowe – nie tylko zegary liczące czas, ale i inne służące rozrywce, wskazujące fazy księżyca i może datę Wielkanocy, różne pozytywki wymagały sporej wiedzy już na etapie projektu – należało wyliczać ilości zębów w kołach by uzyskać właściwe stosunki. Jeśli chcemy wykonać przekładnię realizującą stosunek 34/55 możemy dokonać rozkładu licznika i mianownika: 17/5* 2/11 i uzyskać szukane przełożeni używając 4-rech kół zębatych – łącząc dwie przekładnie o stosunkach jak tym iloczynie. Metoda zdaje się działać, przynajmniej dla prostych stosunków. Znanym problemem zegarmistrzowskim było zadanie postawione przez Charlesa E. Camus – chodziło o projekt zegara realizującego stosunek 720 / 525,949 . Problem z tym ułamkiem jest taki, że mianownik jest liczbą pierwszą, a więc nie damy rady go rozłożyć na czynniki. Tym samym, nawet starając się wykonać przekładnie złożoną z wielu kół nie unikniemy wykonania koła o olbrzymiej ilości zębów! Powinniśmy się zatem raczej odwołać do przybliżeń. Jak znaleźć najlepsze – takie w którym ułamki mają możliwie najmniejszą liczbę zębów ale ich stosunki dobrze przybliżają poszukiwaną wartość? Odpowiedź na to pytanie była wynikiem pracy Brocota, jego metodę można znaleźć tu: http://www.ams.org/samplings/feature-column/fcarc-stern-brocot dodajmy jedynie, że

720 / 525,949 ~ 196 / 143,175 = 2/3 * 2/25 * 7/23 * 7/83

było jednym z możliwych rozwiązań. Drzewo Sterna Brocota umożliwia systematyczne wyliczanie takich przybliżeń, co więcej gwarantuje optymalność – mogę przypuszczać, że jego implementacja to także współczesne narzędzie służące do projektowania przekładni zębatych – ciekawe lu ludzi zdaje sobie współcześnie z tego sprawę ( czy jest inżynier na sali? czy wspomniano o tym?)…

Przejdźmy zatem do opisu konstrukcji Sterna-Brocota. Klasyczna szkolna konstrukcja drzewa zakłada użycie tzw. mediantów. Dla danych ułamków A = a/b i B=c/d ich mediantem nazywamy ułamek M = (a+c)/(b+d) co przypomina nieco sposób dodawania ułamków jaki błędnie wypracowują sobie dzieci. Drzewo Sterna-Brocota to drzewo ułamków, a więc liczb wymiernych. Każda liczba wymierna daje się przedstawić jako iloraz liczb naturalnych p/q gdzie q=/= 0. Jednak drzewo o którym mówimy jest konstruowane wychodząc od dwu stosunków w postaci 0/1 i 1/0 z których jeden jak widać nie jest ułamkiem. Może dać to pretekst do rozważań na temat roli punktu w nieskończoności w tej konstrukcji i a z estetycznego punktu widzenia nieco psuje konstrukcję klasyczną. Wydaje się jednak że jest ona nadal prostsza pojęciowo, zwłaszcza gdy mowa o praktycznych zastosowaniach. Poniżej wprowadzimy znacznie ładniejszą w mojej ocenie konstrukcje algebraiczną. Ale nie uprzedzajmy faktów.

Z każdego wierzchołka drzewa spuśćmy w dól linię. Drzewo SB wisi rozpięte między dwoma stosunkami 0/1 i 1/0 i linie spuszczone z tych elementów są granicami drzewa. Każdy element drzewa leży pomiędzy dwoma liniami – i jest mediantem stosunków od których te linie wychodzą. Tak więc pierwsze dwa elementy ( które nie są uważane za części drzewa i stanowią tylko jego „techniczne zawieszenie” ) to 0/1 i 1/0. Następny -pojedynczy element – to ich mediant czyli:

(-1 – zawieszenie) – 0/1 1/0

(0-wiersz ) (0+1)/(1+0) = 1/1 = 1

Liczba 1 jest wierzchołkiem drzewa – spuszczamy z niej linię w dól – wraz z granicami – liniami opuszczonymi z 0/1 i 1/0 mamy podział „przestrzeni drzewa” dwa sektory. Po lewej stronie mamy linię wychodzącą z 0/1, po środku 1/1 a po prawej 1/0. Wyliczając medianty dostajemy kolejny rząd elementów drzewa:

(1-wiersz) (0+1)/(1+1) = 1/2 ; (1+1)/(1+0) = 2

Spuścimy kolejne linie, wyliczymy kolejne medianty:

(2-wiersz) (0+1)/(1+2) = 1/3 ; (1+1)/(2+1) = 2/3 ; (1+2)/(1+1) = 3/2 ; (2+1)/(1+0) = 3

Myślę, że konstrukcja za pomocą mediantów stanie się jaśniejsza jeśli spojrzy się na rysunek ( z wikipedii):

Drzewo Sterna-Brockot

Powstaje w ten sposób drzewo SB o bardzo ciekawych własnościach. Po pierwsze ułamki sa w nim ułożone według pewnego porządku – ułamki o mniejszych liczbach w mianowniku są wyżej niż ułamki o większych mianownikach – drzewo jest wyposażone w porządek pionowy.. Po drugie wszystkie ułamki są nieskracalne. Trzecią ciekawą własnością jest to, że w drzewie SB każda liczba występuje w unikalny sposób – tylko raz. Czwarta własność -każda liczba ma tu swoją reprezentację. Drzewo SB jest więc to tablica wszystkich liczb wymiernych w określonym porządku.

Dokładniejsza analiza pokazuje dalsze własności: na lewo są zawsze liczby mniejsze a na prawo większe – mamy zatem porządek w wierszach a więc poziomy. Przyglądając się obrazkowi z wikipedii przedstawiającemu drzewo SB można zauważyć kolejną ciekawa własność. Przepiszmy liczniki ułamków z 3-ciego rzędu drzewa wypisanego wyżej – od lewej – dostaniemy wówczas ciąg 1,2,3,3. Przepiszmy teraz ciąg mianowników od lewej 3,3,2,1 (gdzie uznaliśmy że 3=3/1) Widzimy że jest to ten sam ciąg ale w odwrotnym kierunku! nie jest to przypadek – jest to cecha która występuje w każdym wierszu drzewa SB. Przypuszczam, że podobnego rodzaju własności można wskazać cale mnóstwo, dla nas jednak następuje tu czas aby odnieść drzewo SB do ułamków łańcuchowych.

Popatrzmy na ułamki znajdujące się w n-tym rzędzie drzewa. Przedstawię tutaj ciekawe podejście opisane przez Alexandra Bogomolny na jego fantastycznej stronie Cut-The-Knot ( sekcja o ułamkach łańcuchowych zaczyna się tu: http://www.cut-the-knot.org/blue/Euclid.shtml i przynależy do artykułów o algorytmie Euklidesa – polecam!).

Po pierwsze, skoro każdy rodzić ma tu dwoje potomków, zachowując notację w której wierzchołek drzewa, zawierający tylko jeden wyraz równy 1, ma numer 0, otrzymamy wniosek (ogólnie prawdziwy dla wszystkich drzew binarnych):

( T3 ) Jeśli piętra drzewa Sterna-Brockota liczymy od zera to na n-tym poziomie drzewa mamy 2^n liczb.

Warto zauważyć, że drzewo dzieli się na dwie gałęzie, prawa i lewą, oraz, że wyrazy po lewej są odwrotnościami tych po prawej stronie – gałęzie sa swoim lustrzanym odbiciem z inwersją. Biorąc pod uwagę opisany w poprzednim eseju fakt, iż dla ułamków łańcuchowych zachodzi zależność (wzór (10) w poprzednim wpisie) :

[a_0,a_1,...] = \frac{1}{[0,a_0,a_1,...]}

należy się spodziewać że i w drzewie SB znajdzie ona swoje wykorzystanie – np. możemy ograniczyć się do analizy połowy drzewa – druga połowa to lustrzane odbicie.

Zajmijmy się teraz bezpośrednim wyliczeniem ułamków łańcuchowych i ich związkiem z przedstawionym drzewem. Rozpoczniemy niewinnie od ponownego napisania wzoru na pierwszy krok w rozkładzie ułamka p/q na ułamki łańcuchowe:

(12) \frac{p}{q} = a_0 + \frac{r_1}{q}

Idąc za pomysłem przedstawionym na stronach Bogomolnego wprowadzimy tu nieco algebry linowej. Pomysł jest taki: niech ułamek p/q będzie reprezentowany przez wektor [p,q] i niech będzie to kolumna. Spróbujmy równanie (12) przedstawić za pomocą takich wektorów, w postaci macierzowej:

(13) \left| \begin{array}{c}  p \\  q \\  \end{array} \right| =    \left| \begin{array}{c}  a_0q + r_1 \\  q \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & a_0 \\  0 & 1 \\  \end{array} \right|    \left| \begin{array}{c}  r_1 \\  q \\  \end{array} \right|

Jak na razie – fajnie. Co dalej. W następnym kroku rozkładu na ułamki powinniśmy wziąć odwrotność r_1/q czyli q/r_1 i powtórzyć nasze rachunki:

(14) \frac{q}{r_1} = a_1 + \frac{r_2}{r_1}

Szczęśliwie w języku macierzy nie musimy martwić się o odwrotność, po prostu zapiszemy nasze równanie za pomocą odpowiednio dobranych macierzy:

(15) \left| \begin{array}{c}  r_1 \\  q \\  \end{array} \right| =    \left| \begin{array}{c}  r_1 \\  a_1r_1 + r_2 \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & 0 \\  a_1 & 1 \\  \end{array} \right|    \left| \begin{array}{c}  r_1 \\  r_2 \\  \end{array} \right|

Sprytnie, prawda? Następnych kroków łatwo się domyśleć: za każdym razem dokonujemy rozkładu tej ze współrzędnych wektora która jest większa ( za pierwszym razem było to p, za drugim q). Konstrukcja – nasz algorytm – sprawia, że raz jest to współrzędna górna a raz dolna. Jak widać pojawiają się tu ciekawe macierze w postaci:

(16) \left| \begin{array}{cc}  1 & 0 \\  s & 1 \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & 0 \\  1 & 1 \\  \end{array} \right|^s = L^s

oraz:

(17) \left| \begin{array}{cc}  1 & t \\  0 & 1 \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & 1 \\  0 & 1 \\  \end{array} \right|^t = R^t

Zdefiniowaliśmy tym samym operatory macierzowe L i R. Zauważmy, że możemy (dzięki trickowi który pozwolił nam nie dokonywać operacji odwrotności) zestawić równania (13) i (15) w jedno:

(18) \left| \begin{array}{c}  p \\  q \\  \end{array} \right| =  \left| \begin{array}{cc}  1 & a_0 \\  0 & 1 \\  \end{array} \right|  \left| \begin{array}{c}  r_1 \\  q \\  \end{array} \right| =    \left| \begin{array}{cc}  1 & a_0 \\  0 & 1 \\  \end{array} \right|    \left| \begin{array}{cc}  1 & 0 \\  a_1 & 1 \\  \end{array} \right|    \left| \begin{array}{c}  r_1 \\  r_2 \\  \end{array} \right|    =R^{a_0}L^{a_1} \left| \begin{array}{c}  r_1 \\  r_2 \\  \end{array} \right|

jesteśmy już bardzo niedalecy od drzewa Sterna-Brocota. W poprzednim odcinku uzasadniliśmy, że rozkład jak powyżej musi się zakończyć na pewnym, skończonym etapie dla liczb wymiernych. nastąpi to oczywiście gr\dy jedna ze współrzędnych wektora [r_i,r_{i+1}] będzie zerowa. Uważny i podejrzliwy czytelnik z pewnością zechce rozpoznać w literach L i R angielskie skróty od słów Right i Left i będzie miał słuszność!

Dla otarcia się o prawdziwe obliczenia, podajmy tutaj jakiś konkretny przykład – a jego waga nie sprowadza się jedynie do rachunków. Wskaże on nam pewną cechę, która z jednej strony może być nieco rozczarowująca, ale z drugiej jest nieunikniona. nie uprzedzajmy faktów. Oto przykład:

(19) \left| \begin{array}{c}  4 \\  7 \\  \end{array} \right| =    R^0 \left| \begin{array}{c}  4 \\  7 \\  \end{array} \right| =    R^0L^1\left| \begin{array}{c}  4 \\  3 \\  \end{array} \right| =    R^0L^1R^1 \left| \begin{array}{c}  1 \\  3 \\  \end{array} \right| =  R^0L^1R^1L^3 \left| \begin{array}{c}  1 \\  0 \\  \end{array} \right| =  R^0L^1R^1L^2 L \left| \begin{array}{c}  1 \\  0 \\  \end{array} \right|

Po pierwsze zwróćmy uwagę, że otrzymaliśmy prawidłowy rozkład ułamka 4/7 = [0,1,1,3] co zresztą można odczytać z przedostatniej równości. Proszę teraz sprawdzić, gdzie mieści się 4/7 na drzewie Sterna-Brocota – stosownie duże drzewo jest tu: http://www.cut-the-knot.org/blue/stern.gif

Jak widać, chcąc dotrzeć do liczby 4/7 z wierzchołka reprezentowanego tu przez 1/1 należy wybrać się w Lewo, potem w Prawo, a potem 2-razy w Lewo – daje to zygzak postaci LRLL . A mogło być tak ładnie! Niestety w naszym rozkładzie na ostatnim miejscu jest liczba 3 a nie 2.

Okazuje się, ze na ostatnim miejscu ułamka łańcuchowego zawsze pojawia się cyfra o 1 większa niż stosowny zapis „zygzaka” od liczby 1/1 do liczby która przechodząc zygzak osiągamy. Taka własność drzewa – ot co.

Aby jednak całość rozjaśnić, to jest zagmatwać, zapisałem jeszcze jedną równość w równaniu (19). Teraz mamy poprawną ścieżkę, oraz jeden dodatkowy krok w lewo jeśli startujemy od „absolutnego zakotwiczenia drzewa” w postaci „ułamka „1/0”. Popatrzmy może na inny przykład:

(20) \left| \begin{array}{c}  2 \\  3 \\  \end{array} \right| =    R^0 \left| \begin{array}{c}  2 \\  3 \\  \end{array} \right| =    R^0L^1\left| \begin{array}{c}  2 \\  1 \\  \end{array} \right| =    R^0L^1R^2 \left| \begin{array}{c}  0 \\  1 \\  \end{array} \right| =    R^0L^1R^1 R \left| \begin{array}{c}  0 \\  1 \\  \end{array} \right|

I rzeczywiście, co nie powinno dziwić 2/3 = [0,1,2] ale tym razem mamy dodatkowy ruch w zygzaku ( dla 2/3 zygzak ma kształt LR) tym razem w prawo ale od 0/1. Najwyraźniej jakaś siła nie chce nam pozwolić operować na „gołych okropieństwach w postaci 1/0 i 0/1” i wstawia stosowne R lub L w ostatnie miejsce – łamiąc miłą dla oka symetrię i cenzorując horrendum wyrażeń postaci 1/0.. Co ciekawe i oczywiste R[0,1] =L[1,0] = [1,1] = 1… Rozkład jest poprawny – a nieoczekiwane pojawienie się liczby o jeden większej nie jest przypadkiem – można się tu dopatrywać jakiejś ingerencji wielkiego cenzora, albo metafizyki, a może po prostu rzeczy są nieco złośliwe. Drzewo pamięta jak jest zawieszone ale uwzględnia to w niemiłym dla nas miejscu. Ot, taka własność.

Czas na podsumowanie naszych wyprowadzeń. Niech ciąg liter R i L reprezentuje pewną ścieżkę w drzewie SB – L oznacza wybór lewej gałęzi, R prawej oraz jeśli w takim ciągu występuje po sobie kilka jednakowych liter, np. p liter R to taki fragment ciągu zapisujemy jako R^p ( podobnie dla liter L następujących po sobie). Rozpatrujemy tylko ciągi zaczynające się od litery R , z tym że dopuszczamy możliwość że występuje ona „0” razy. Niech CF oznacza funkcję która dla zadanego ciągu R i L zwraca ułamek łańcuchowy leżący w stosownym miejscu drzewa Sterna-Brocota. Możemy zapisać wzór na CF:

( 21 ) CF(R^{a_0} X_1^{a_1}X_2^{a_2}... X_k^{a_k}) = [a_0;a_1,a_2,...,a_k+1]

gdzie X^{a_p} oznacza R lub L a_p razy po sobie, zaś a_0 może być równe 0 lub nie. Czytelnik podobne wyprowadzenie może znaleźć u Bogomolnego, tam jednak użyte sa mnożenia macierzowe od lewej strony i wektory jako wiersze. Proszę pamiętać o tej różnicy w notacji porównując rachunki. Należy dla porządku także nadmienić, ze zapis procedury rozkładu ułamków łańcuchowych w postaci macierzy jest pochodną macierzowej postaci algorytmu Euklidesa – czy uczą tego na informatyce? Jak ktoś dociekliwy – proszę samemu spróbować zapisać algorytm na gcd(a,b) w postaci macierzowej – podobnie jak powyżej.

Skoro w ciągu liter RLRRLL…. zawarta jest informacja o miejscu ułamka łańcuchowego w drzewie SB, a zarazem o jego czynnikach, uzyskujemy w naturalny sposób ciekawy wniosek. Aby dojść do dowolnej liczby w 3-cim rzędzie musimy wykonać 3 ruchy licząc od 0 (powiedzmy RLL dla liczby 4/3 = CF(RLL) = [1,3] ) . Stosownie w n-tym rzędzie znajdują się liczby reprezentowane przez ciągi n-literowe. Prawdziwe jest zatem następujące twierdzenie:

( T4 ) Niech [a_0,a_1,...a_k] ułamkiem łańcuchowym pojawiającym się w n-tym rzędzie drzewa Sterna-Brocota. Wówczas:

\sum^{k}_{i=0} a_i = n + 1

Rozkład liczby na sumę czynników, kiedy bierzemy pod uwagę kolejność składników nosi nazwę kompozycji Twierdzenie T4 można zatem wypowiedzieć inaczej:

Na n-tym piętrze drzewa SB mamy wszystkie takie ułamki łańcuchowe że ich czynniki są kompozycjami liczby n przy czym należy pamiętać, że dopuszczamy możliwość iż zero może występować tylko na pierwszym miejscu.

Jako proste ćwiczenie kombinatoryczne proponuję dowieść że wynik ten jest zgodny z T3 w którym napisaliśmy, ze na n-tym wierszu drzewa Sb jest 2^n liczb ( zakładając, że wiersze liczymy od zera). Podpowiem że wystarczy zmodyfikować rozumowanie opisane w artykule o kompozycjach z wikipedii aby uwzględnić występowanie liczby 0 oraz fakt, że dla ułamków łańcuchowych zachodzi zależność [a_0,a_1...,a_k,1] = [a_0,a_1,...,a_k +1] ( należy konsekwentnie wybrać tylko jedną reprezentację ułamków, np. zawierająca zawsze 1-dynkę na końcu).

Uznałem że w tym miejscu zrobimy przerwę. Miałem napisać o funkcji ?(x) ale to chyba byłoby za wiele na raz. Jak zwykle proszę o uwagi i ewentualne poprawki co do rachunków.

W kolejnych odcinkach jeśli autor poradzi sobie z rachunkami (co mu na razie nie idzie) powiemy coś o pasjonującej funkcji ?(x) Minkowskiego oraz o drzewie Calkina–Wilfa – co będzie niejako rozważaniami na boku tego co chciałbym opisać, ale pozwoli zadać ciekawe, w opinii autora, 2 pytania. Głównym celem cyklu jest jednak przedstawienie nieco innego podejścia do tego co opisano tutaj, w tym wpisie. I temu poświęcę następny wpis.