Djelovanje grupe SL(2,Z) na Fareyevom grafu, kompleksu i stablu
Sažetak
U članku ćemo konstruirati Fareyev graf, Fareyev kompleks i Fareyevo stablo, te pokazati kako specijalna linearna grupa \operatorname{SL}(2, \mathbb{Z}) djeluje na njima.
1Uvod
Djelovanja grupa na geometrijskim objektima, npr., na grafovima, čine jedan od interesa geometrijske teorije grupa, što je područje matematike koje se oslanja na algebru, geometriju, topologiju i teoriju grafova, te se može opisati kao proučavanje svojstava grupa korištenjem geometrijskih i topoloških svojstava prostora na kojima te grupe djeluju. Svrha našeg članka je zainteresirati čitatelje za ovo područje. Iako ovdje nećemo imati prostora za detaljno uspostavljanje veze grafa s grupom koja na njega (na dovoljno dobar način) djeluje, barem ćemo predočiti slikovite primjere djelovanja jedne grupe na dva grafa.
Točnije, u radu ćemo opisati konstrukciju grafova poznatih kao Fareyev graf i Fareyevo stablo, pri čemu će nam za konstrukciju Fareyevog stabla trebati takozvani Fareyev kompleks, kojeg \'cemo također uvesti. Zatim ćemo prikazati djelovanje specijalne linearne grupe \operatorname{SL}(2,\mathbb{Z}) na njima. Rad završavamo uspostavljanjem veze između Fareyevog grafa i Fareyevog niza razlomaka.
Glavni izvor za ovaj rad je knjiga ” Office hours with a geometric group theorist” (
2Osnovni pojmovi - grafovi, stabla i djelovanje grupe na graf
2.1Grafovi
Uvedimo za početak osnovne pojmove iz teorije grafova, koji se mogu naći u
Definicija 2.1. Graf1\mathcal{G} je uređena trojka \mathcal{G}=(\mathcal{V}(\mathcal{G}),\mathcal{E}(\mathcal{G}),\psi_{\mathcal{G}}), gdje je \mathcal{V}(\mathcal{G}) neprazan skup čije elemente zovemo vrhovi grafa \mathcal{G}, \mathcal{E}(\mathcal{G}) skup disjunktan s \mathcal{V}(\mathcal{G}) čije elemente zovemo bridovi grafa \mathcal{G} i \psi_{\mathcal{G}} funkcija incidencije koja svakom bridu grafa \mathcal{G} pridružuje neuređeni par (ne nužno različitih) vrhova grafa \mathcal{G}.
Pisat ćemo \psi_{\mathcal{}}{G} (e) = \lbrace u,v\rbrace, tj., koristimo \lbrace u,v\rbrace kao oznaku za neuređeni par vrhova pridružen bridu e. U literaturi se umjesto \lbrace u,v\rbrace također koriste oznake (u,v) ili uv .
Definicija 2.2.Vrhovi u i v grafa \mathcal{G} su susjedni ako postoji brid e grafa \mathcal{G} takav da je \psi_{\mathcal{G}}(e)=\lbrace u,v\rbrace. Kažemo da su u i v krajevi brida e. Brid e s jednim jedinim vrhom, tj., takav da je \psi_{\mathcal{G}}(e)=\lbrace u,u\rbrace zovemo petlja.
Definicija 2.3. Šetnja u grafu \mathcal{G} od početnog vrha v_{0} do krajnjeg vrha v_{n} je konačan niz
Neka su W=(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{n}, v_{n}) i W'=(v_{n},e_{n+1},v_{n+1},e_{n+2},v_{n+2},\ldots,e_{n+k}, v_{n+k}) šetnje u grafu \mathcal{G}. Šetnja (v_{n}, e_{n}, v_{n-1}, e_{n-1}, v_{n-2}, \ldots, v_{1}, e_{1}, v_{0}) dobivena obrtanjem redosljeda u šetnji W zove se inverzna (ili suprotna) šetnja od W i označava se s W^{-1}, a šetnja
W= (v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{n}, v_{n}),
gdje su v_{i} vrhovi, e_{i} bridovi, te vrijedi e_{i}=\lbrace v_{i-1},v_{i}\rbrace, za sve i=1,\ldots, n. Broj n zovemo duljina šetnje. Šetnja je zatvorena ako ima pozitivnu duljinu i vrijedi v_{0}=v_{n}. Zatvorena šetnja kod koje su početni vrh v_{0} i svi unutarnji vrhovi v_{1}, \ldots , v_{n-1} međusobno različiti zove se ciklus.Neka su W=(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{n}, v_{n}) i W'=(v_{n},e_{n+1},v_{n+1},e_{n+2},v_{n+2},\ldots,e_{n+k}, v_{n+k}) šetnje u grafu \mathcal{G}. Šetnja (v_{n}, e_{n}, v_{n-1}, e_{n-1}, v_{n-2}, \ldots, v_{1}, e_{1}, v_{0}) dobivena obrtanjem redosljeda u šetnji W zove se inverzna (ili suprotna) šetnja od W i označava se s W^{-1}, a šetnja
(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{n}, v_{n}, e_{n+1},v_{n+1},e_{n+2},v_{n+2},\ldots,e_{n+k}, v_{n+k})
dobivena nadovezivanjem (ili konkatenacijom) šetnji W i W' kod vrha v_{n} označava se s WW'.
Definicija 2.4. Ako su u šetnji W=(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{n}, v_{n}) svi bridovi e_{i} međusobno različiti, takva se šetnja naziva staza. Ako su u stazi W i svi vrhovi v_{i} međusobno različiti, takvu stazu W zovemo put. Pri tome uvodimo i tzv. trivijalan (ili konstantan) put, što je šetnja duljine 0 koja se sastoji od jednog vrha i nema bridova.
Put u grafu \mathcal{G} od vrha u do vrha v kraće zovemo (u,v)-put u \mathcal{G}. Vrhovi u i v grafa \mathcal{G} su povezani ako postoji (u,v)-put u \mathcal{G} (smatramo da uvijek imamo trivijalan (u,u)-put).
Put u grafu \mathcal{G} od vrha u do vrha v kraće zovemo (u,v)-put u \mathcal{G}. Vrhovi u i v grafa \mathcal{G} su povezani ako postoji (u,v)-put u \mathcal{G} (smatramo da uvijek imamo trivijalan (u,u)-put).
Na skupu vrhova \mathcal{V}(\mathcal{G}) grafa \mathcal{G} definiramo relaciju \sim:
u\sim v \ \Leftrightarrow \ \text{ postoji } (u,v)\text{-put u }\mathcal{G}, \text{ tj., vrhovi } u \text{ i } v \text{ su povezani}.
Lako se pokaže da je ovo relacija ekvivalencije na \mathcal{V}(\mathcal{G}). Klase ekvivalencije s obzirom na relaciju \sim zovemo komponente povezanosti grafa \mathcal{G}. Graf \mathcal{G} je povezan ako ima točno jednu komponentu povezanosti, tj., između svaka dva različita vrha grafa \mathcal{G} postoji put.
Definicija 2.5. Povezan graf bez ciklusa zove se stablo.
Navedimo bez dokaza sljedeće poznate činjenice iz teorije grafova.
Lema 2.6. Graf \mathcal{G} je stablo ako i samo ako su svaka dva vrha grafa \mathcal{G} povezana jedinstvenim putem.
Lema 2.7. Ako u grafu \mathcal{G} postoji vrh e takav da za svaki vrh v različit od e postoji jedinstveni put od e do v, tada graf \mathcal{G} nema ciklusa. Također, takav graf \mathcal{G} je povezan, što znači da je \mathcal{G} stablo.
Napomena 2.8. Graf \mathcal{G} nazivamo jednostavnim ako u \mathcal{G} nema petlji i nikoja dva brida ne spajaju isti par vrhova. U jednostavnom grafu je šetnja W=(v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,e_{n}, v_{n}) potpuno određena nizom vrhova, pa je možemo zapisati kao W=(v_{0},v_{1},v_{2},\ldots, v_{n}). Primijetimo da je stablo primjer jednostavnog grafa, te \'cemo zato puteve u stablu moći zapisati samo pomoću niza odgovarajućih vrhova.
Također, kako u stablu između vrhova u i v postoji jedinstveni (u,v)-put, pisat ćemo njemu inverzni put u stablu kao (v,u)-put. Uočimo još da za (u,v)-put i (v,w)-put u stablu, ako je njihova konkatenacija put, onda je zapisujemo kao (u,w)-put.
Također, kako u stablu između vrhova u i v postoji jedinstveni (u,v)-put, pisat ćemo njemu inverzni put u stablu kao (v,u)-put. Uočimo još da za (u,v)-put i (v,w)-put u stablu, ako je njihova konkatenacija put, onda je zapisujemo kao (u,w)-put.
2.2Djelovanje grupe
Navedimo sada definiciju djelovanja grupe na skupu i na grafu, kao i jedan primjer za djelovanje grupe na skupu (iz
Definicija 2.9. Grupa G djeluje na (neprazan) skup \Omega ako postoji preslikavanje
\textbf{.}:G\times\Omega\rightarrow\Omega, u oznaci \textbf{.}(g,\omega)=g\textbf{.}\omega, za svaki g\in G i za svaki \omega\in\Omega, takvo da vrijedi:
Preslikavanje \textbf{.}:G\times\Omega\rightarrow\Omega koje zadovoljava svojstva (1) i (2) zovemo djelovanje grupeG na skup} \Omega.
\textbf{.}:G\times\Omega\rightarrow\Omega, u oznaci \textbf{.}(g,\omega)=g\textbf{.}\omega, za svaki g\in G i za svaki \omega\in\Omega, takvo da vrijedi:
| \bullet | [(1)] e\textbf{.}\omega=\omega, za svaki \omega\in\Omega, gdje je e\in G neutralni element grupe G, i |
| \bullet | [(2)] g_{1}\textbf{.}(g_{2}\textbf{.}\omega)=(g_{1}g_{2})\textbf{.}\omega, za svaki \omega\in\Omega i za sve g_{1},g_{2}\in G. |
Sjetimo se sad specijalne linearne grupe reda 2 nad \mathbb{Z}, u oznaci \operatorname{SL}(2,\mathbb{Z}), što je grupa svih (2\times2)-matrica s cjelobrojnim elementima i s determinantom jednakom 1 , s operacijom množenja matrica.
Zadatak 2.10. Definirajmo preslikavanje \textbf{.}:\operatorname{SL}(2,\mathbb{Z})\times\mathbb{Z}^{2}\rightarrow\mathbb{Z}^{2} s
\begin{bmatrix} a & b\\ c & d \end{bmatrix}\textbf{.}(x,y):=(ax+by,cx+dy),
što također možemo zapisati kao
\begin{bmatrix} a & b\\ c & d \end{bmatrix}\textbf{.}(x,y):= \begin{bmatrix} a & b\\ c & d \end{bmatrix}\cdot \begin{bmatrix} x\\ y \end{bmatrix},
gdje vektor \begin{bmatrix} x\\ y \end{bmatrix} zamjenjuje točku (x,y)\in\mathbb{Z}^{2}, a vektor \begin{bmatrix} ax+by\\ cx+dy \end{bmatrix} zamjenjuje točku (ax+by,cx+dy)\in\mathbb{Z}^{2}. Pokažite da je ovako definirano preslikavanje ujedno djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na skupu \mathbb{Z}^{2}.Uputa: Provjerite da preslikavanje \textbf{.} zadovoljava svojstva djelovanja grupe, to jest, da za neutralni element I=\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}\in \operatorname{SL}(2,\mathbb{Z}) vrijedi I\textbf{.} (x,y)=(x,y),~\forall(x,y)\in\mathbb{Z}^{2}, te da za proizvoljne A= \begin{bmatrix} a_{1} & a_{2}\\ a_{3} & a_{4} \end{bmatrix},B= \begin{bmatrix} b_{1} & b_{2}\\ b_{3} & b_{4} \end{bmatrix}\in SL(2,\mathbb{Z}) vrijedi A\textbf{.}( B\textbf{.} (x,y))=(AB)\textbf{.}(x,y), \forall(x,y)\in\mathbb{Z}^{2}.
Definicija 2.11. Grupa G djeluje na graf \mathcal{G} ako:
tako da vrijedi: ako su u,v krajevi brida b, onda su g\textbf{.} u, g\textbf{.} v krajevi brida g\textbf{.} b.
| (1) | postoji djelovanje grupe G na skup vrhova grafa \textbf{.}:G\times\mathcal{V}(\mathcal{G})\rightarrow\mathcal{V}(\mathcal{G}), te |
| (2) | postoji djelovanje grupe G na skup bridova grafa \textbf{.}:G\times\mathcal{E}(\mathcal{G})\rightarrow\mathcal{E}(\mathcal{G}) |
Pri tome je uobičajeno korištenje oznake \textbf{.} za djelovanja od G i na skupu vrhova i na skupu bridova istog grafa. Za jednostavne grafove, ovu definiciju možemo formulirati ovako:
Definicija 2.12. Grupa G djeluje na jednostavan graf \mathcal{G} ako postoji djelovanje grupe G na skup vrhova grafa \textbf{.}:G\times\mathcal{V}(\mathcal{G})\rightarrow\mathcal{V}(\mathcal{G}) koje čuva susjednost vrhova grafa \mathcal{G}, to jest, za koje vrijedi:
Primjer djelovanja grupe na jednostavan graf dat ćemo u idućem odjeljku.
Cilj ovog odjeljka je definirati i konstruirati graf koji je u geometrijskoj teoriji grupa poznat kao Fareyev graf. U[4] se navodi da je ovaj graf konstruirao Adolf Hurwitz2 1894. godine, te ga nazvao u čast Johna Fareya, Sr.3, zbog veze vrhova ovog grafa s takozvanim Fareyevim nizovima (koje ćemo spomenuti u petom odjeljku ovog rada). Osim konstrukcije Fareyevog grafa, ovdje ćemo opisati djelovanje grupe \operatorname{SL} (2,\mathbb{Z}) na njega (iz [1] ).
Za uvođenje vrhova Fareyevog grafa koristit ćemo uređene parove cijelih brojeva s nekim dodatnim svojstima. Za početak, sjetimo se Bezoutove leme (npr. iz[3] , gdje je Bezoutova lema navedena kao posljedica teorema 2.3):
Kada je \operatorname{nzd}(m,n)=k, pisat ćemo (m,n)=(km', kn')=k(m',n') za odgovarajuće brojeve m',n' \in \mathbb{Z}, odnosno, pisat \'cemo (l m,l n)= l (m,n) kad nam to bude potrebno. Ako je \operatorname{nzd}(m,n)=1, kažemo da su m i n relativno prosti.
Par brojeva (x,y) iz leme3.1 zovemo Bezoutovim koeficijentima za par (m,n), a mogu se odrediti (proširenim) Euklidovim algoritmom ([3] ). Iako Bezoutovi koeficijenti za (m,n) općenito nisu jedinstveni, uz dodatne uvjete možemo dobiti i jedinstvenost. Tako korištenjem Teorema 10.1 iz [3] (o rješenjima linearnih Diofantskih jednadžbi) i Euklidovog algoritma slijedi:
Posljedica Leme3.2 je sljedeća:
Navedimo sada definiciju korisnu za uvođenje Fareyevog grafa.
Naglasimo da iz činjenice da je \operatorname{nzd}(m,n)=1 slijedi da u primitivnom elementu (m,n)\in \mathbb{Z}^{2} barem jedan od brojeva nije nula.
Na skupu svih primitivnih elemenata iz \mathbb{Z}^{2} definiramo relaciju \sim ovako:
Definicija Fareyevog grafa
Uočimo da zamjena stupaca u determinanti mijenja predznak determinante, no iz ps-qr\in\lbrace 1,-1\rbrace slijedi rq-sp\in\lbrace 1,-1\rbrace , pa redosljed vrhova u bridu zaista nije bitan.
Konstrukcija Fareyevog grafa \mathcal{G}. Konstruirajmo sada, za n\in \mathbb{N}_{0}, niz grafova \mathcal{G}_{n} za koji ćemo pokazati da vrijedi
Dosadašnji koraci konstrukcije prikazani su na slici 1, na kojoj smo, radi preglednosti, vrhove zapisali izostavljajući simbol \pm, a bridove smo nacrtali zakrivljenima.
Primjetimo da smo vrh \pm(2,1) mogli dobiti zbrajanjem odgovarajućih reprezentanata vrhova \pm(1,0) i \pm(1,1), to jest, za (1,0)\in\pm(1,0) i (1,1)\in\pm(1,1), dobijemo (1,0)+(1,1)=(2,1) . Općenito, vrijedi sljedeća lema.
Dakle, ako su \pm(p,q)=\pm(-p,-q) i \pm(r,s)=\pm(-r,-s) susjedni vrhovi Fareyevog grafa \mathcal{G}, prema lemi3.8 slijedi da su \pm(p+r,q+s), \pm(p-r,q-s), \pm(-p+r,-q+s) i \pm(-p-r,-q-s) vrhovi susjedni s vrhovima \pm(p,q) i \pm(r,s), ali kako je (p+r,q+s)\sim (-p-r,-q-s) i (-p+r,-q+s)\sim (p-r,q-s), slijedi da je \pm(p+r,q+s)=\pm(-p-r,-q-s) i \pm(-p+r,-q+s)=\pm(p-r,q-s). Odavde slijedi da za svaki brid Fareyevog grafa \mathcal{G} iz n-tog koraka konstrukcije (za n\geq 1), u idućem koraku konstrukcije koristeći lemu 3.8 dobijemo jedan novi vrh Fareyevog grafa \mathcal{G}, susjedan s krajevima tog brida, tako da zbrojimo odgovarajuće reprezentante krajeva tog brida. Tako smo mogli dobiti vrhove \pm(2,1), \pm(-2,1), \pm(-1,2) i \pm(1,2) te ukupno osam njima pripadaju\'cih novih bridova iz drugog koraka konstrukcije.
Nastavimo dalje s konstrukcijom Fareyevog grafa \mathcal{G} korištenjem leme3.8 : za treći korak, vrh \pm(3,1) dobivamo zbrajanjem odgovarajućih reprezentanata vrhova \pm(1,0) i \pm(2,1), te zatim ovaj vrh bridovima povežemo s vrhovima \pm(1,0) i \pm(2,1). Analogno dobijemo po jedan novi vrh za svaki od preostalih sedam bridova iz drugog koraka, te svaki takav vrh spojimo bridovima s vrhovima brida iz kojeg je nastao, što dovršava treći korak konstrukcije. Zatim istovjetno izvedemo četvrti korak, peti korak i tako u beskonačnost, čime dobivamo graf \mathcal{K}:=\bigcup_{n\in\mathbb{N}_{0}} \mathcal{G}_{n}, za koji želimo pokazati da je jednak Fareyevom grafu \mathcal{G}.
Na slici 2 je prikazano od nultog do trećeg koraka iz konstrukcije Fareyevog grafa \mathcal{G} s označenim vrhovima, te četvrti i peti korak samo s nacrtanim bridovima (tj., na slici 2 je graf \mathcal{G}_{5}).
Primijetimo da iz opisane konstrukcije za \mathcal{K} i leme3.8 slijedi da je \mathcal{K}\subseteq \mathcal{G}, dakle za vrhove vrijedi \mathcal{V}(\mathcal{K})\subseteq \mathcal{V}(\mathcal{G}) i za bridove vrijedi \mathcal{E}(\mathcal{K})\subseteq \mathcal{E}(\mathcal{G}) . Stoga, da bismo dokazali da je \mathcal{K}= \mathcal{G} dovoljno je dokazati da vrijedi \mathcal{V}(\mathcal{G})\subseteq \mathcal{V}(\mathcal{K}) i \mathcal{E}(\mathcal{G})\subseteq \mathcal{E}(\mathcal{K}) . Za početak, formulirajmo ovakav zadatak:
Uputa: Prva tvrdnja slijedi iz uvjeta \det\biggl( \begin{bmatrix} 1 & p \\ 0 & q \end{bmatrix}\biggr)=q \in \lbrace 1,-1\rbrace, tj., vrhovi iz \mathcal{G} susjedni s \pm(1,0) su oblika \pm(p,q), za p\in\mathbb{Z}, q\in\lbrace 1,-1\rbrace. Kako je (-p,1)\sim(p,-1) za svaki p\in\mathbb{Z}, vrhovi iz \mathcal{G} susjedni s vrhom \pm(1,0) su oblika \pm(p,1), p\in\mathbb{Z}. Za proizvoljni p\in\mathbb{Z}, pokažite da se opisanom konstrukcijom pomoću leme3.8 (korištenjem \pm(1,0) i \pm(1,1), ili \pm(-1,0)=\pm(1,0) i \pm(-1,1)) u odgovarajućem broju koraka može doći do brida koji spaja vrhove \pm(1,0) i \pm(p,1), pri čemu se također dobije da, za p\geq 2, i brid \lbrace \pm(p,1),\pm(p-1,1)\rbrace mora biti u \mathcal{E}(\mathcal{K}), te za p\lt 0, |p|\geq 2 i brid \lbrace \pm(p,1),\pm(p+1,1)\rbrace mora biti u \mathcal{E}(\mathcal{K}).
Analogno se pokaže da \mathcal{K} sadrži sve bridove Fareyevog grafa \mathcal{G} iz vrha \pm(0,1), dakle skup vrhova \lbrace \pm(1,p) \ | \ p\in\mathbb{Z}\rbrace =\lbrace \pm(1,p) \ | \ p\in\mathbb{N}\rbrace \cup\lbrace \pm(-1,p) \ | \ p\in\mathbb{N}\rbrace iz \mathcal{V}(\mathcal{G}) također se nalazi i u \mathcal{V}(\mathcal{K}).
Na slici 2 bi podjela na kvadrante odgovarala tome da nacrtamo x-os kroz vrhove \pm(-1,1) i \pm(1,1), te nacrtamo y-os kroz vrhove \pm(1,0) i \pm(0,1) (mada ova slika prikazuje \mathcal{G}_{5}, a ne cijeli \mathcal{G}).
Sada želimo pokazati da, ako je \pm(p,q) vrh iz \mathcal{G} koji zadovoljava jedan od uvjeta (i)–(iv) napomene3.10 , onda za bilo koji brid iz \mathcal{E}(\mathcal{G}) kojemu je taj \pm(p,q) vrh mora vrijediti da mu se i drugi vrh nalazi u istom kvadrantu kao i \pm(p,q), tj., cijeli brid se mora nalaziti u istom kvadrantu kao i \pm(p,q) . Pokažimo to za vrh koji zadovoljava uvjet (i) iz napomene 3.10 , dok se za ostale uvjete iz napomene 3.10 ova činjenica dokaže analogno.
Dakle, ako želimo pokazati da je \mathcal{V}(\mathcal{G})\subseteq \mathcal{V}(\mathcal{K}) i \mathcal{E}(\mathcal{G})\subseteq \mathcal{E}(\mathcal{K}), dovoljno je to pokazati za svaki kvadrant posebno (a za brid \lbrace \pm(1,0),\pm(0,1)\rbrace već znamo da je i u \mathcal{E}(\mathcal{G}) i u \mathcal{E}(\mathcal{K}) ).
Uputa: Po zadatku3.7 , Fareyev graf \mathcal{G} je jednostavan graf pa je dovoljno provjeriti svojstva iz definicije 2.12 . Prvo pokažite da preslikavanje \textbf{.} zaista ima \mathcal{V}(\mathcal{G}) za kodomenu, tj., da vrijedi da je (ap+bq,cp+dq)\in\mathbb{Z}^{2} primitivan element. Zatim pokažite da \textbf{.} zadovoljava oba svojstva djelovanja grupe, tj., da je I.(\pm(p,q))=\pm(p,q), te da za proizvoljne A,B\in \operatorname{SL}(2,\mathbb{Z}) vrijedi A\textbf{.}( B\textbf{.} (\pm(p,q)))=(AB)\textbf{.}(\pm(p,q)). Za kraj pokažite da djelovanje \textbf{.} čuva susjednost vrhova Fareyevog grafa.
Uputa: Korištenjem jednadžbe u zadatku i Bezoutove leme3.1 odredite vrijednosti za a,b,c,d u ovisnosti o p, q.
Sada ćemo korištenjem Fareyevog grafa uvesti pojam Fareyevog kompleksa, na osnovi kojeg ćemo konstruirati još jedan graf, takozvano Fareyevo stablo. Sljedeća definicija je iz[??] .
Uputa: Prvo primijetite da je kodomena ovog preslikavanja zaista T, tj., ako su A\in \operatorname{SL}(2,\mathbb{Z}) i \lbrace v_{1},v_{2},v_{3}\rbrace \in T proizvoljni, kako su v_{i},v_{j}\in\lbrace v_{1},v_{2},v_{3}\rbrace susjedni vrhovi za sve i\neq j, slijedi da su A\textbf{.} v_{i} i A\textbf{.} v_{j} također susjedni vrhovi. Zatim pokažite da \textbf{.} zadovoljava oba svojstva djelovanja grupe na skup T, tj., da je I\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace =\lbrace v_{1},v_{2},v_{3}\rbrace, za svaki \lbrace v_{1},v_{2},v_{3}\rbrace \in T, te da za proizvoljne A,B\in \operatorname{SL}(2,\mathbb{Z}) vrijedi A\textbf{.}(B\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace )=(AB)\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace, za sve \lbrace v_{1},v_{2},v_{3}\rbrace \in T .
Tek trebamo pokazati da je ovako zadan graf \mathcal{T} zaista stablo, ali prije ovog dokaza opišimo konstrukciju za \mathcal{T} te nacrtajmo sliku za nju. Na slici 3 prikazano je početnih pet koraka konstrukcije Fareyevog stabla \mathcal{T}, koji su nacrtani direktno na početnih pet koraka konstrukcije Fareyevog kompleksa \mathcal{G}_{T}.
Opišimo početak ove konstrukcije. Nultom koraku konstrukcije Fareyevog grafa \mathcal{G} (pa tako i Fareyevog kompleksa \mathcal{G}_{T}), to jest bridu \lbrace \pm(1,0) ,\pm(0,1)\rbrace, odgovara jedan vrh, kojeg na slici smjestimo u polovište ovog brida. U prvom koraku konstrukcije Fareyevog kompleksa \mathcal{G}_{T} imamo dva trokuta, t_{1}=\lbrace \pm(1,0) , \pm(-1,1), \pm(0,1)\rbrace i t_{2}=\lbrace \pm(1,0) , \pm(1,1), \pm(0,1)\rbrace, od kojih nam svaki daje po dva nova brida Fareyevog grafa. Smjestimo po jedan vrh za graf \mathcal{T} u težista trokuta t_{1} i t_{2}, te po jedan vrh u polovište svakog od 4 dodana brida Fareyevog grafa, pa ove vrhove zatim povežemo bridovima kao u receptu iz definicije4.3 : od trokuta t_{1} dobivamo bridove \lbrace \lbrace \pm(1,0),\pm(-1,1)\rbrace ,t_{1} \rbrace, \lbrace \lbrace \pm(0,1),\pm(-1,1))\rbrace ,t_{1} \rbrace i \lbrace \lbrace \pm(1,0),\pm(0,1)\rbrace ,t_{1} \rbrace grafa \mathcal{T}, te analogno dobivamo 3 brida koji koriste t_{2}, čime dovršimo prvi korak konstrukcije grafa \mathcal{T}. Konstrukcija se analogno nastavlja u beskonačnost, na trokutima i njihovim stranicama iz svakog koraka konstrukcije Fareyevog kompleksa. Sada pokažimo da je ovako opisan graf \mathcal{T} zaista stablo:
Opišimo sada primjer djelovanja grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyevo stablo.
| (1) | [(*)] u,v\in\mathcal{V}(\mathcal{G}) \text{ su susjedni u }\mathcal{G}\ \Rightarrow \ g\textbf{.} u,g\textbf{.} v\in\mathcal{V}(\mathcal{G}) \text{ su susjedni u }\mathcal{G},~\forall g\in G. |
Napomena 2.13. Definicija 2.12 zadaje i djelovanje grupe G na skup bridova \mathcal{E}(\mathcal{G}) jednostavnog grafa \mathcal{G}. Naime, definirajmo preslikavanje \textbf{.}: G\times\mathcal{E}(\mathcal{G})\rightarrow\mathcal{E}(\mathcal{G}) s
g\textbf{.} \lbrace u,v\rbrace :=\lbrace g\textbf{.} u,g\textbf{.} v\rbrace ,
za sve g\in G i sve \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}). Znamo iz (*) da je kodomena ovog preslikavanja zaista \mathcal{E}(\mathcal{G}). Također, jasno je da za neutralni element e\in G vrijedi e\textbf{.} \lbrace u,v\rbrace =\lbrace u,v\rbrace za svaki \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}), te se lako provjeri da za proizvoljan \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}) vrijedi g_{1}\textbf{.}(g_{2}\textbf{.} \lbrace u,v\rbrace )=(g_{1}g_{2})\textbf{.} \lbrace u,v\rbrace , za sve g_{1},g_{2}\in G.
Napomena 2.14. Iz svojstva (*) i definicije 2.9 slijedi da preslikavanje \textbf{.} iz definicije 2.12 čuva i nesusjednost vrhova grafa \mathcal{G}: za vrhove u,v\in\mathcal{V}(\mathcal{G}) koji nisu susjedni, ako pretpostavimo da postoji g\in G takav da su g\textbf{.} u i g\textbf{.} v susjedni, onda iz (*) slijedi da su g^{-1}\textbf{.}(g\textbf{.} u)=u i g^{-1}\textbf{.}(g\textbf{.} v)=v susjedni, što je u kontradikciji s početnom pretpostavkom.
Primjer djelovanja grupe na jednostavan graf dat ćemo u idućem odjeljku.
3Fareyev graf
Cilj ovog odjeljka je definirati i konstruirati graf koji je u geometrijskoj teoriji grupa poznat kao Fareyev graf. U
Za uvođenje vrhova Fareyevog grafa koristit ćemo uređene parove cijelih brojeva s nekim dodatnim svojstima. Za početak, sjetimo se Bezoutove leme (npr. iz
Lema 3.1. Neka su m,n\in\mathbb{Z} takvi da je (m,n)\neq(0,0). Tada postoje x,y\in\mathbb{Z} takvi da je
mx+ny=\operatorname{nzd}(m,n),
gdje je \operatorname{nzd}(m,n) najveći zajednički djelitelj brojeva m i n, to jest, najveći prirodni broj koji dijeli i m i n.Kada je \operatorname{nzd}(m,n)=k, pisat ćemo (m,n)=(km', kn')=k(m',n') za odgovarajuće brojeve m',n' \in \mathbb{Z}, odnosno, pisat \'cemo (l m,l n)= l (m,n) kad nam to bude potrebno. Ako je \operatorname{nzd}(m,n)=1, kažemo da su m i n relativno prosti.
Par brojeva (x,y) iz leme
Lema 3.2. Za prirodne brojeve m\gt n\gt 1 koji su relativno prosti vrijedi:
| (1) | Postoji jedinstveni par cijelih brojeva (x,y) koji zadovoljavaju mx+ny=1, te x\lt 0, |x|\lt n i 0\lt y\lt m. |
| (2) | Postoji jedinstveni par cijelih brojeva (x,y) koji zadovoljavaju mx+ny=1, te y\lt 0, |y|\lt m i 0\lt x\lt n. |
Posljedica Leme
Lema 3.3. Neka su m\gt n\gt 1 relativno prosti prirodni brojevi. Tada postoje jedinstveni prirodni brojevi x i y za koje vrijedi 0\lt x\lt m, 0\lt y\lt n te -my +nx=1.
Dodatno, vrijedi i sljedeće:
Dodatno, vrijedi i sljedeće:
| \bullet | x\gt y, m-x \geq n-y, |
| \bullet | \operatorname{nzd} (x,y)=1, i |
| \bullet | \operatorname{nzd} (m-x, n-y)=1. |
Dokaz. Za dane relativno proste brojeve m\gt n\gt 1, po dijelu (1) leme 3.2 znamo da postoji jedinstveni par Bezoutovih koeficijenata (-y,x) takvih da vrijedi
Također vrijedi m-x \geq n-y, jer bi u protivnom iz m-x\lt n-y slijedilo 1=nx-my=m(n-y) -n(m-x)\gt m(n-y) -n(n-y)=(m-n)(n-y), a znamo da je (m-n)(n-y)\geq 1. Osim toga, kad x i y ne bi bili relativno prosti, postojao bi l\in\mathbb{N}_{\geq 2} takav da x=lx', y=ly', za neke x',y'\in\mathbb{N}, iz čega bi slijedilo da l dijeli nx-my=1. Konačno, kad m-x i n-y ne bi bili relativno prosti, postojao bi l\in\mathbb{N}_{\geq 2} takav da m-x=lz, n-y=lw, za neke z,w\in\mathbb{N}, iz čega bi slijedilo da l dijeli m(n-y)-n(m-x)=nx-my=1.
m(-y)+ nx=1, \ \ \text{ te }\ \ 0\lt y\lt n, \ 0\lt x\lt m.
Pri tome još vrijedi x\gt y, jer bi u protivnom iz x\leq y slijedilo 1=nx-my\leq (n-m)y \lt 0.Također vrijedi m-x \geq n-y, jer bi u protivnom iz m-x\lt n-y slijedilo 1=nx-my=m(n-y) -n(m-x)\gt m(n-y) -n(n-y)=(m-n)(n-y), a znamo da je (m-n)(n-y)\geq 1. Osim toga, kad x i y ne bi bili relativno prosti, postojao bi l\in\mathbb{N}_{\geq 2} takav da x=lx', y=ly', za neke x',y'\in\mathbb{N}, iz čega bi slijedilo da l dijeli nx-my=1. Konačno, kad m-x i n-y ne bi bili relativno prosti, postojao bi l\in\mathbb{N}_{\geq 2} takav da m-x=lz, n-y=lw, za neke z,w\in\mathbb{N}, iz čega bi slijedilo da l dijeli m(n-y)-n(m-x)=nx-my=1.
\ \blacksquare
Napomena 3.4. Za (m,n) i (x,y) iz Leme 3.3 , upravo su n-y i -(m-x) jedinstveni cijeli brojevi koji zadovoljavaju uvjete iz (2) leme 3.2 , jer m(n-y) + n (-(m-x))=1, te vrijedi 0\lt n-y\lt n i |-(m-x)|=m-x\lt m. Pri tome primijetimo da vijedi i \det\biggl(\begin{bmatrix} m & x \\ n & y \end{bmatrix}\biggr)=my-nx=-1, te \det\biggl(\begin{bmatrix} m & m-x \\ n & n-y \end{bmatrix}\biggr)=nx-my=1.
Navedimo sada definiciju korisnu za uvođenje Fareyevog grafa.
Definicija 3.5. Kažemo da je uređeni par (m,n)\in\mathbb{Z}^{2} primitivan ako je \operatorname{nzd}(m,n)=1.
Naglasimo da iz činjenice da je \operatorname{nzd}(m,n)=1 slijedi da u primitivnom elementu (m,n)\in \mathbb{Z}^{2} barem jedan od brojeva nije nula.
Na skupu svih primitivnih elemenata iz \mathbb{Z}^{2} definiramo relaciju \sim ovako:
(m,n)\sim(k,l) \ \Leftrightarrow \ \exists x\in\lbrace 1,-1\rbrace \text{ takav da je }(m,n)=x(k,l).
Lako se pokaže da je \sim relacija ekvivalencije na tom skupu. S obzirom na ovu relaciju ekvivalencije, klasa ekvivalencije primitivnog elementa (m,n)\in\mathbb{Z}^{2} je
[(m,n)]=\lbrace (m,n),-(m,n)\rbrace .
Zbog preglednosti, koristit ćemo oznaku \pm(m,n):=[(m,n)].Definicija Fareyevog grafa
Definicija 3.6. Fareyev graf \mathcal{G} je graf čiji je skup vrhova
\mathcal{V}(\mathcal{G}):=\lbrace \pm(m,n)\ |\ (m,n)\in\mathbb{Z}^{2} \text{ je primitivan}\rbrace ,
tj., \mathcal{V}(\mathcal{G}) je kvocijentni skup s obzirom na relaciju ekvivalencije \sim na skupu svih primitivnih elemenata od \mathbb{Z}^{2}. Skup bridova \mathcal{E}(\mathcal{G}) dobijemo ovako: vrhovi \pm(p,q) i \pm(r,s) su susjedni ako je
\det\biggl(\begin{bmatrix} p & r \\ q & s \end{bmatrix}\biggr)=ps-qr\in\lbrace 1,-1\rbrace .
Uočimo da zamjena stupaca u determinanti mijenja predznak determinante, no iz ps-qr\in\lbrace 1,-1\rbrace slijedi rq-sp\in\lbrace 1,-1\rbrace , pa redosljed vrhova u bridu zaista nije bitan.
Zadatak 3.7. Pokažite da je Fareyev graf jednostavan graf.
\mathcal{V}(\mathcal{G})=\bigcup_{n\in\mathbb{N}_{0}} \mathcal{V}(\mathcal{G}_{n}) \ \text{ i }\ \mathcal{E}(\mathcal{G})=\bigcup_{n\in\mathbb{N}_{0}} \mathcal{E}(\mathcal{G}_{n}).
Prikazat ćemo konstrukciju i grafički, barem djelomično. Počinjemo od vrhova \pm(1,0) i \pm(0,1). Kako vrijedi \det\biggl(\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix}\biggr)=1, vrhovi \pm(1,0) i \pm(0,1) su susjedni, tj. povezani bridom i to ćemo smatrati grafom \mathcal{G}_{0}, a ujedno i nultim korakom naše konstrukcije za \mathcal{G}. Postoje li vrhovi koji su susjedni s \pm(1,0) i \pm(0,1)? Pretpostavimo da je \pm(p,q) vrh susjedan s \pm(1,0) i \pm(0,1). Tada iz
\det\biggl(\begin{bmatrix} 1&p \\ 0&q \end{bmatrix}\biggl)=q \in \lbrace 1,-1\rbrace \text{ i } \det\biggl(\begin{bmatrix} p&0 \\ q&1 \end{bmatrix}\biggr)=p\in\lbrace 1,-1\rbrace
dobijemo da su vrhovi \pm(1,0) i \pm(0,1) susjedni s vrhovima \pm(1,1), \pm(1,-1), \pm(-1,1) i \pm(-1,-1), ali kako je (1,1)\sim(-1,-1) i (-1,1)\sim(1,-1), slijedi da je \pm(1,1)=\pm(-1,-1) i \pm(-1,1)=\pm(1,-1). Dakle, vrhovi \pm(1,0) i \pm(0,1) su susjedni s vrhovima \pm(1,1) i \pm(-1,1). Na ovaj način smo dodali dva nova vrha i četiri nova brida grafu \mathcal{G}_{0}, te tako dobili graf \mathcal{G}_{1}. Ovo dodavanje dvaju novih vrhova i četiriju novih bridova smatramo provođenjem prvog koraka u našoj konstrukciji za \mathcal{G}. Nadalje, pogledajmo brid koji spaja vrhove \pm(1,0) i \pm(1,1). Postoje li vrhovi susjedni s \pm(1,0) i \pm(1,1) osim vrha \pm(0,1)? Iz
\det\biggl(\begin{bmatrix} 1&p \\ 0&q \end{bmatrix}\biggr)=q \in \lbrace 1,-1\rbrace \text{ i } \det\biggl(\begin{bmatrix} 1&p \\ 1&q \end{bmatrix}\biggr)=q-p\in \lbrace 1,-1\rbrace
dobijemo da su vrhovi \pm(1,0) i \pm(1,1) susjedni s vrhovima \pm(0,1), \pm(2,1) ,\pm(-2,-1) i \pm(0,-1), ali kako je (0,1)\sim(0,-1) i (2,1)\sim(-2,-1), slijedi da je \pm(0,1)=\pm(0,-1) i \pm(2,1)=\pm(-2,-1). Kako smo već znali da je vrh \pm(0,1) susjedan s vrhovima \pm(1,0) i \pm(1,1), dobili smo jedan novi vrh, \pm(2,1), koji je susjedan s vrhovima \pm(1,0) i \pm(1,1). Analogno se dobiju vrhovi \pm(-2,1) (susjedan s \pm(-1,0)=\pm(1,0) i \pm(-1,1)), \pm(-1,2) (susjedan s \pm(-1,1) i \pm(0,1)) i \pm(1,2) (susjedan s \pm(0,1) i \pm(1,1)). Kada grafu \mathcal{G}_{1} dodamo ova četiri nova vrha i spojimo odgovarajuće bridove, to dovršava drugi korak naše konstrukcije za \mathcal{G}, čime dobivamo graf \mathcal{G}_{2}.
Slika 1: Graf \mathcal{G}_{2}, tj., nulti, prvi i drugi korak konstrukcije Fareyevog grafa \mathcal{G} (iz [1] ).
Dosadašnji koraci konstrukcije prikazani su na slici 1, na kojoj smo, radi preglednosti, vrhove zapisali izostavljajući simbol \pm, a bridove smo nacrtali zakrivljenima.
Primjetimo da smo vrh \pm(2,1) mogli dobiti zbrajanjem odgovarajućih reprezentanata vrhova \pm(1,0) i \pm(1,1), to jest, za (1,0)\in\pm(1,0) i (1,1)\in\pm(1,1), dobijemo (1,0)+(1,1)=(2,1) . Općenito, vrijedi sljedeća lema.
Lema 3.8. Neka su \pm(p,q) i \pm(r,s) susjedni vrhovi Fareyevog grafa \mathcal{G}. Tada je \pm(p+r,q+s) također vrh Fareyevog grafa \mathcal{G} koji je susjedan vrhovima \pm(p,q) i \pm(r,s).
Dokaz. Pokažimo prvo da je \pm(p+r,q+s) vrh Fareyevog grafa \mathcal{G}. Kada \pm(p+r,q+s) ne bi bio vrh Fareyevog grafa \mathcal{G}, tj., p+r i q+s ne bi bili relativno prosti, postojao bi l\in\mathbb{N}_{\geq 2} takav da (p+r,q+s)=l(w,z), za neke w,z\in\mathbb{Z}. No tada bi vrijedilo slw-rlz=s(p+r)-r(q+s)=sp-rq\in\lbrace -1,1\rbrace, jer su \pm(p,q) i \pm(r,s) susjedni vrhovi, što bi značilo da l mora dijeliti 1, što je nemoguće. Dakle, \pm(p+r,q+s) je vrh Fareyevog grafa \mathcal{G}.
Da pokažemo da je vrh \pm(p+r,q+s) susjedan s vrhovima \pm(p,q) i \pm(r,s), dovoljno je uočiti da vrijedi \det\biggl(\begin{bmatrix} p&p+r \\ q&q+s \end{bmatrix}\biggr)=\det\biggl(\begin{bmatrix} p&r \\ q&s \end{bmatrix}\biggr)\in\lbrace 1,-1\rbrace , iz čega slijedi da su \pm(p,q) i \pm(p+r,q+s) susjedni vrhovi, te da je \det\biggl(\begin{bmatrix} p+r&r \\ q+s&s \end{bmatrix}\biggr)=\det\biggl(\begin{bmatrix} p&r \\ q&s \end{bmatrix}\biggr)\in\lbrace 1,-1\rbrace , iz čega slijedi da su \pm(r,s) i \pm(p+r,q+s) susjedni vrhovi.
Da pokažemo da je vrh \pm(p+r,q+s) susjedan s vrhovima \pm(p,q) i \pm(r,s), dovoljno je uočiti da vrijedi \det\biggl(\begin{bmatrix} p&p+r \\ q&q+s \end{bmatrix}\biggr)=\det\biggl(\begin{bmatrix} p&r \\ q&s \end{bmatrix}\biggr)\in\lbrace 1,-1\rbrace , iz čega slijedi da su \pm(p,q) i \pm(p+r,q+s) susjedni vrhovi, te da je \det\biggl(\begin{bmatrix} p+r&r \\ q+s&s \end{bmatrix}\biggr)=\det\biggl(\begin{bmatrix} p&r \\ q&s \end{bmatrix}\biggr)\in\lbrace 1,-1\rbrace , iz čega slijedi da su \pm(r,s) i \pm(p+r,q+s) susjedni vrhovi.
\ \blacksquare
Dakle, ako su \pm(p,q)=\pm(-p,-q) i \pm(r,s)=\pm(-r,-s) susjedni vrhovi Fareyevog grafa \mathcal{G}, prema lemi
Nastavimo dalje s konstrukcijom Fareyevog grafa \mathcal{G} korištenjem leme
Na slici 2 je prikazano od nultog do trećeg koraka iz konstrukcije Fareyevog grafa \mathcal{G} s označenim vrhovima, te četvrti i peti korak samo s nacrtanim bridovima (tj., na slici 2 je graf \mathcal{G}_{5}).
Slika 2: Graf \mathcal{G}_{5}, tj., od nultog do petog koraka konstrukcije Fareyevog grafa \mathcal{G} (iz [1] ).
Primijetimo da iz opisane konstrukcije za \mathcal{K} i leme
Zadatak 3.9. Pokažite da su svi bridovi Fareyevog grafa \mathcal{G} iz vrha \pm(1,0) oblika \lbrace \pm(1,0),\pm(p,1)\rbrace, za p\in\mathbb{Z}, te da se konstrukcijom od \mathcal{K} dobije da su svi ovi bridovi sadržani u \mathcal{K}, pa su i svi vrhovi \pm(p,1), za p\in\mathbb{Z}, sadržani u \mathcal{K}. Ujedno pokažite da su, za p\in \mathbb{N}_{\geq 2}, svi bridovi \lbrace \pm(p,1),\pm(p-1,1)\rbrace i \lbrace \pm(-p,1),\pm(-p+1,1)\rbrace iz \mathcal{E}(\mathcal{G}) sadržani i u \mathcal{E}(\mathcal{K}).
Uputa: Prva tvrdnja slijedi iz uvjeta \det\biggl( \begin{bmatrix} 1 & p \\ 0 & q \end{bmatrix}\biggr)=q \in \lbrace 1,-1\rbrace, tj., vrhovi iz \mathcal{G} susjedni s \pm(1,0) su oblika \pm(p,q), za p\in\mathbb{Z}, q\in\lbrace 1,-1\rbrace. Kako je (-p,1)\sim(p,-1) za svaki p\in\mathbb{Z}, vrhovi iz \mathcal{G} susjedni s vrhom \pm(1,0) su oblika \pm(p,1), p\in\mathbb{Z}. Za proizvoljni p\in\mathbb{Z}, pokažite da se opisanom konstrukcijom pomoću leme
Analogno se pokaže da \mathcal{K} sadrži sve bridove Fareyevog grafa \mathcal{G} iz vrha \pm(0,1), dakle skup vrhova \lbrace \pm(1,p) \ | \ p\in\mathbb{Z}\rbrace =\lbrace \pm(1,p) \ | \ p\in\mathbb{N}\rbrace \cup\lbrace \pm(-1,p) \ | \ p\in\mathbb{N}\rbrace iz \mathcal{V}(\mathcal{G}) također se nalazi i u \mathcal{V}(\mathcal{K}).
Napomena 3.10. Primijetimo sada da za vrhove \pm(p,q) iz \mathcal{V}(\mathcal{G}) za koje je p\lt 0 i q\lt 0 vrijedi \pm(p,q)= \pm(|p|,|q|), a za vrhove \pm(p,q) iz \mathcal{V}(\mathcal{G}) za koje je p\gt 0 i q\lt 0 vrijedi \pm(p,q)= \pm(-p,|q|). Iz toga slijedi da sve vrhove \pm(p,q) iz \mathcal{V}(\mathcal{G})\setminus\lbrace \pm(1,0),\pm(0,1),\pm(1,1),\pm(-1,1) \rbrace možemo zapisati tako da vrijedi jedan od sljedeća četiri uvjeta:
To jest, možemo zamisliti da smo graf \mathcal{G} bez brida \lbrace \pm(1,0), \pm(0,1)\rbrace podijelili na četiri kvadranta i to tako da:
| (i) | p\gt q\geq 1, ili |
| (ii) | p\lt 0 i |p|\gt q\geq 1, ili |
| (iii) | p\lt 0 i q\gt |p|\geq 1, ili |
| (iv) | q\gt p\geq 1. |
| (I) | prvi kvadrant sadrži vrhove \pm(p,q) koji zadovoljavaju uvjet (i) ili vrijedi \pm(p,q)=\pm(1,0) ili \pm(p,q)=\pm(1,1), |
| (II) | drugi kvadrant sadrži vrhove \pm(p,q) koji zadovoljavaju uvjet (ii) ili vrijedi \pm(p,q)=\pm(-1,0)=\pm(1,0) ili \pm(p,q)=\pm(-1,1), |
| (III) | treći kvadrant sadrži vrhove \pm(p,q) koji zadovoljavaju uvjet (iii) ili vrijedi \pm(p,q)=\pm(0,1) ili \pm(p,q)=\pm(-1,1), |
| (IV) | četvrti kvadrant sadrži vrhove \pm(p,q) koji zadovoljavaju uvjet (iv) ili vrijedi \pm(p,q)=\pm(0,1) ili \pm(p,q)=\pm(1,1). |
Na slici 2 bi podjela na kvadrante odgovarala tome da nacrtamo x-os kroz vrhove \pm(-1,1) i \pm(1,1), te nacrtamo y-os kroz vrhove \pm(1,0) i \pm(0,1) (mada ova slika prikazuje \mathcal{G}_{5}, a ne cijeli \mathcal{G}).
Sada želimo pokazati da, ako je \pm(p,q) vrh iz \mathcal{G} koji zadovoljava jedan od uvjeta (i)–(iv) napomene
Lema 3.11. Neka je \pm(p,q) vrh iz \mathcal{G} za koji vrijedi p\gt q\geq 1, te neka je \lbrace \pm(p,q),\pm(x,y)\rbrace brid iz \mathcal{G}. Tada vrijedi da je vrh \pm(x,y) također iz prvog kvadranta od \mathcal{G}, tj., ili je x\gt y\geq 1, ili (x,y)=(1,0) ili (x,y)=(1,1).
Dokaz. Znamo da vrijedi \det\biggl( \begin{bmatrix} p & x \\ q & y \end{bmatrix}\biggr)=py -qx \in \lbrace 1,-1\rbrace, te trebamo pokazati da za (x,y) ne može vrijediti niti jedna od preostalih mogućnosti koje opisuju vrhove u kvadrantima od \mathcal{G}, a nisu spomenute u tekstu ove leme.
Ako bi bilo (x,y)=(0,1), slijedilo bi py-qx=p\geq 2 \notin \lbrace -1,1\rbrace. Ako bi bilo (x,y)=(-1,1), slijedilo bi py-qx=p+q\geq 3 \notin \lbrace -1,1\rbrace. Oba slučaja kad je x\lt 0 (tj, (ii) i (iii) iz napomene3.10 ) vode na py-qx=py+q|x|\geq p+q\geq 3 \notin \lbrace -1,1\rbrace. Napose, ako je y\gt x\geq 1 kao u (iv) iz napomene 3.10 , tada py-qx\gt py-qy=y(p-q)\gt 1, jer y\gt 1 i p-q\geq 1, dakle ne može biti py-qx\in\lbrace -1,1\rbrace.
Ako bi bilo (x,y)=(0,1), slijedilo bi py-qx=p\geq 2 \notin \lbrace -1,1\rbrace. Ako bi bilo (x,y)=(-1,1), slijedilo bi py-qx=p+q\geq 3 \notin \lbrace -1,1\rbrace. Oba slučaja kad je x\lt 0 (tj, (ii) i (iii) iz napomene
\ \blacksquare
Dakle, ako želimo pokazati da je \mathcal{V}(\mathcal{G})\subseteq \mathcal{V}(\mathcal{K}) i \mathcal{E}(\mathcal{G})\subseteq \mathcal{E}(\mathcal{K}), dovoljno je to pokazati za svaki kvadrant posebno (a za brid \lbrace \pm(1,0),\pm(0,1)\rbrace već znamo da je i u \mathcal{E}(\mathcal{G}) i u \mathcal{E}(\mathcal{K}) ).
Teorem 3.12. Vrijedi \mathcal{V}(\mathcal{G})\subseteq \mathcal{V}(\mathcal{K}) i \mathcal{E}(\mathcal{G})\subseteq \mathcal{E}(\mathcal{K}).
Dokaz. Iz početka konstrukcije za \mathcal{K} znamo da su vrhovi \pm(1,0), \pm(1,1), \pm(0,1) i \pm(-1,1) iz \mathcal{V}(\mathcal{G}) ujedno sadržani i u \mathcal{V}(\mathcal{K}), te da su bridovi \lbrace \pm(1,0),\pm(0,1)\rbrace, \lbrace \pm(1,0),\pm(1,1)\rbrace, \lbrace \pm(1,0),\pm(-1,1)\rbrace, \lbrace \pm(0,1),\pm(1,1)\rbrace i \lbrace \pm(0,1),\pm(-1,1)\rbrace iz \mathcal{E}(\mathcal{G}) ujedno sadržani i u \mathcal{E}(\mathcal{K}).
Kao u napomeni3.10 , podijelimo graf \mathcal{G} na kvadrante, te pokažimo da za sve vrhove i bridove iz prvog kvadranta od \mathcal{G} vrijedi da su oni sadržani i u \mathcal{K}, a za ostala tri kvadranta se ovo sadržavanje pokaže analogno.
Što se tiče vrhova iz prvog kvadranta od \mathcal{G}, kako za \pm(1,0) i \pm(1,1) već znamo da su sadržani i u \mathcal{G} i u \mathcal{K}, ostaje provjeriti što je s vrhovima \pm(p,q) iz \mathcal{V}(\mathcal{G}) za koje vrijedi p\gt q\geq 1.
Što se tiče bridova iz prvog kvadranta od \mathcal{G}, kako za brid \lbrace \pm(1,1),\pm(1,0)\rbrace već znamo da je sadržan i u \mathcal{G} i u \mathcal{K}, preostaje promatrati bridove \lbrace \pm(p,q),\pm(r,s)\rbrace iz \mathcal{G} za koje vrijedi p\gt q\geq 1, pri čemu iz leme3.11 znamo da mora biti i \pm(r,s) iz prvog kvadranta of \mathcal{G}. Također, bez smanjenja općenitosti možemo pretpostaviti da je p\geq r, no primijetimo da slučaj p=r vodi na ps- pq\in\lbrace -1,1\rbrace, što bi značilo da je p=1, dakle (p,q)=(1,1) i (r,s)=(1,0) (jer to je jedino što je moguće u prvom kvadrantu). Zato ćemo ubuduće pretpostavljati da vrijedi p\gt r. Da rezimiramo, naše su pretpostavke za bridove \lbrace \pm(p,q),\pm(r,s)\rbrace iz \mathcal{E}(\mathcal{G}) za koje trebamo pokazati da su i u \mathcal{E}(\mathcal{K}) sljedeće:
Pogledajmo prvo vrhove \pm(p,q) za koje je p\gt q=1. Iz zadatka3.9 znamo da su, za p\in\mathbb{N}_{\geq 2}, svi vrhovi oblika \pm(p,1) koji su iz \mathcal{V}(\mathcal{G}) ujedno sadržani i u \mathcal{V}(\mathcal{K}). Sada pogledajmo bridove \lbrace \pm(p,1),\pm(r,s)\rbrace iz \mathcal{E}(\mathcal{G}) uz uvjete iz (3.1) . Iz uvjeta ps-r\in\lbrace -1,1\rbrace i iz (3.1) slijedi da mora biti (r,s)=(1,0) ili (r,s)=(p-1,1) (jer s\geq 2 vodi na ps-r\geq 2p-r\gt p\gt 1). Znači brid \lbrace \pm(p,1),\pm(r,s)\rbrace mora biti jednak ili \lbrace \pm(p,1),\pm(1,0)\rbrace ili \lbrace \pm(p,1),\pm(p-1,1)\rbrace, no za oba ova brida iz zadatka 3.9 znamo da su sadržani i u \mathcal{E}(\mathcal{K}).
Ostaje provjeriti slučaj vrhova \pm(p,q) iz prvog kvadranta \mathcal{V}(\mathcal{G}) za koje vrijedi p\gt q\gt 1, te bridova \lbrace \pm(p,q),\pm(r,s)\rbrace iz \mathcal{E}(\mathcal{G}) za koje vrijedi
Dakle, fiksirajmo proizvoljni vrh \pm(p,q) iz \mathcal{G} za kojeg vrijedi p\gt q\gt 1. Koristit ćemo indukciju po p. Za bazu indukcije iskoristit ćemo da znamo da su vrhovi \pm(1,0) te \pm(p,1), za p\in\mathbb{N}, koji su u \mathcal{V}(\mathcal{G}) ujedno sadržani i u \mathcal{V}(\mathcal{K}), te da su bridovi \lbrace \pm(p,1),\pm(1,0)\rbrace za p\in\mathbb{N} i \lbrace \pm(p,1),\pm(p-1,1)\rbrace za p\in\mathbb{N}_{\geq 2}, koji su u \mathcal{E}(\mathcal{G}) ujedno sadržani i u \mathcal{E}(\mathcal{K}).
Pretpostavimo da za svaki prirodan broj p' za koji vrijedi p\gt p'\gt 0 imamo:
Sada primijetimo da za zadani vrh \pm(p,q) iz \mathcal{V}(\mathcal{G}), zbog \operatorname{nzd}(p,q)=1 i p\gt q\gt 1 iz leme3.3 slijedi da postoje jedinstveni prirodni brojevi x i y za koje vrijedi:
Iz x\gt y\gt 0 i \operatorname{nzd}(x,y)=1 slijedi da je \pm(x,y) vrh iz prvog kvadranta od \mathcal{G}, a iz p-x\geq q-y \gt 0 i \operatorname{nzd}(p-x,q-y)=1 slijedi da je \pm(p-x,q-y) vrh iz prvog kvadranta od \mathcal{G}. Po pretpostavci indukcije (\ast) izlazi da su \pm(x,y) i \pm(p-x,q-y) i vrhovi iz \mathcal{K}, a po konstrukciji od \mathcal{K}, kako je \pm(p,q) dobiven zbrajanjem predstavnika (x,y) od \pm(x,y) i (p-x, q-y) od \pm(p-x,q-y), slijedi da je i \pm(p,q) vrh u \mathcal{K}.
Osim toga, za brid \lbrace \pm(x,y),\pm(p-x,q-y)\rbrace za koji znamo da je iz \mathcal{G} jer je \det\biggl(\begin{bmatrix} x &p- x \\ y & q-y \end{bmatrix}\biggr)=qx-py=1, po pretpostavci indukcije (\ast\ast) vrijedi da je on sadržan i u \mathcal{E}(\mathcal{K}), pa stoga konstrukcija od \mathcal{K} daje da su i bridovi \lbrace \pm(p,q),\pm(x,y)\rbrace i \lbrace \pm(p,q),\pm(p-x,q-y)\rbrace, koji su u \mathcal{E}(\mathcal{G}), ujedno sadržani i u \mathcal{E}(\mathcal{K}).
Na kraju primijetimo da, ako je \lbrace \pm(p,q),\pm(r,s)\rbrace proizvoljni brid iz prvog kvadranta od \mathcal{G} sa svojstvom p\gt r (i svojstvom r\geq s\geq 0), tada mora vrijediti \det\biggl( \begin{bmatrix} p & r \\ q & s \end{bmatrix}\biggr)=ps-qr\in\lbrace -1,1\rbrace, tj., ps-qr=-1 ili ps-qr=1. No iz(3.3) znamo da postoje jedinstveni prirodni brojevi x i y takvi da vrijedi p\gt x\gt 0, q\gt y\gt 0, p(-y)+qx=1, za koje još vrijedi i x\gt y, p-x\geq q-y, \operatorname{nzd}(x,y)=1, te \operatorname{nzd}(p-x, q-y)=1. Ako je ps-qr=-1, dakle p(-s)+qr=1, onda mora biti (r,s)=(x,y). Ako je ps-qr=1, onda mora biti (r,s)=(p-x, q-y) (napomena 3.4 ). U oba slučaja ve\'c znamo da je brid \lbrace \pm(p,q), \pm(r,s)\rbrace iz \mathcal{E}(\mathcal{G}) ujedno sadržan i u \mathcal{E}(\mathcal{K}). To dovršava dokaz.
Kao u napomeni
Što se tiče vrhova iz prvog kvadranta od \mathcal{G}, kako za \pm(1,0) i \pm(1,1) već znamo da su sadržani i u \mathcal{G} i u \mathcal{K}, ostaje provjeriti što je s vrhovima \pm(p,q) iz \mathcal{V}(\mathcal{G}) za koje vrijedi p\gt q\geq 1.
Što se tiče bridova iz prvog kvadranta od \mathcal{G}, kako za brid \lbrace \pm(1,1),\pm(1,0)\rbrace već znamo da je sadržan i u \mathcal{G} i u \mathcal{K}, preostaje promatrati bridove \lbrace \pm(p,q),\pm(r,s)\rbrace iz \mathcal{G} za koje vrijedi p\gt q\geq 1, pri čemu iz leme
(3.1)
\begin{eqnarray} p\gt q\geq 1, \ \ p\gt r\geq 1 \ \text{ i } \ r\geq s\geq 0. \end{eqnarray}
Pogledajmo prvo vrhove \pm(p,q) za koje je p\gt q=1. Iz zadatka
Ostaje provjeriti slučaj vrhova \pm(p,q) iz prvog kvadranta \mathcal{V}(\mathcal{G}) za koje vrijedi p\gt q\gt 1, te bridova \lbrace \pm(p,q),\pm(r,s)\rbrace iz \mathcal{E}(\mathcal{G}) za koje vrijedi
(3.2)
\begin{eqnarray} p\gt q \gt 1, \ \ p\gt r\geq 1 \ \text{ i } \ r\geq s\geq 0. \end{eqnarray}
Dakle, fiksirajmo proizvoljni vrh \pm(p,q) iz \mathcal{G} za kojeg vrijedi p\gt q\gt 1. Koristit ćemo indukciju po p. Za bazu indukcije iskoristit ćemo da znamo da su vrhovi \pm(1,0) te \pm(p,1), za p\in\mathbb{N}, koji su u \mathcal{V}(\mathcal{G}) ujedno sadržani i u \mathcal{V}(\mathcal{K}), te da su bridovi \lbrace \pm(p,1),\pm(1,0)\rbrace za p\in\mathbb{N} i \lbrace \pm(p,1),\pm(p-1,1)\rbrace za p\in\mathbb{N}_{\geq 2}, koji su u \mathcal{E}(\mathcal{G}) ujedno sadržani i u \mathcal{E}(\mathcal{K}).
Pretpostavimo da za svaki prirodan broj p' za koji vrijedi p\gt p'\gt 0 imamo:
| (1) | [(\ast)] svaki vrh \pm(p',q'), uz p'\gt q'\geq 1, koji se nalazi u \mathcal{V}(\mathcal{G}) se također nalazi u \mathcal{V}(\mathcal{K}), |
| (2) |
[(\ast \ast)] svaki brid oblika \lbrace \pm(p',q'),\pm(r,s)\rbrace koji zadovoljava uvjete iz |
Sada primijetimo da za zadani vrh \pm(p,q) iz \mathcal{V}(\mathcal{G}), zbog \operatorname{nzd}(p,q)=1 i p\gt q\gt 1 iz leme
(3.3)
\begin{eqnarray} 0\lt x\lt p, \ 0\lt y\lt q \ \ \text{ i } \ \det\biggl(\begin{bmatrix} p & x \\ q & y \end{bmatrix}\biggr)=-(-py+qx)=-1, \\ \ \ \text{te još} \ x\gt y, \ p-x \geq q-y, \ \operatorname{nzd} (x,y)=1, \ \operatorname{nzd} (p-x, q-y)=1. \end{eqnarray}
Osim toga, za brid \lbrace \pm(x,y),\pm(p-x,q-y)\rbrace za koji znamo da je iz \mathcal{G} jer je \det\biggl(\begin{bmatrix} x &p- x \\ y & q-y \end{bmatrix}\biggr)=qx-py=1, po pretpostavci indukcije (\ast\ast) vrijedi da je on sadržan i u \mathcal{E}(\mathcal{K}), pa stoga konstrukcija od \mathcal{K} daje da su i bridovi \lbrace \pm(p,q),\pm(x,y)\rbrace i \lbrace \pm(p,q),\pm(p-x,q-y)\rbrace, koji su u \mathcal{E}(\mathcal{G}), ujedno sadržani i u \mathcal{E}(\mathcal{K}).
Na kraju primijetimo da, ako je \lbrace \pm(p,q),\pm(r,s)\rbrace proizvoljni brid iz prvog kvadranta od \mathcal{G} sa svojstvom p\gt r (i svojstvom r\geq s\geq 0), tada mora vrijediti \det\biggl( \begin{bmatrix} p & r \\ q & s \end{bmatrix}\biggr)=ps-qr\in\lbrace -1,1\rbrace, tj., ps-qr=-1 ili ps-qr=1. No iz
\ \blacksquare
Korolar 3.13. Opisanom konstrukcijom dobije se cijeli Fareyev graf \mathcal{G}.
Napomena 3.14. Uočite da smo u dokazu teorema 3.12 pokazali: ako je \pm(p,q) proizvoljan vrh iz \mathcal{G} takav da je p\gt q\geq 1, tada postoje susjedni vrhovi \pm(x,y) i \pm(p-x,q-y) iz \mathcal{G} takvi da se vrh \pm(p,q) dobije kao zbroj njihovih odgovarajućih predstavnika.
Zadatak 3.15. Neka je \mathcal{G} Fareyev graf, a \mathcal{V}(\mathcal{G}) skup njegovih vrhova. Definirajmo preslikavanje \textbf{.}:\operatorname{SL}(2,\mathbb{Z})\times\mathcal{V}(\mathcal{G})\rightarrow\mathcal{V}(\mathcal{G}) formulom
\begin{bmatrix} a & b\\ c & d \end{bmatrix}\textbf{.}(\pm(p,q)):=\pm (ap+bq,cp+dq),
što također možemo zapisati kao
\begin{bmatrix} a & b\\ c & d \end{bmatrix}\textbf{.}(\pm(p,q)):=\pm \left(\begin{bmatrix} a & b\\ c & d \end{bmatrix}\cdot \begin{bmatrix} p\\ q \end{bmatrix}\right),
pri čemu vektori \begin{bmatrix} p\\ q \end{bmatrix} i \begin{bmatrix} ap+bq\\ cp+dq \end{bmatrix} zamjenjuju (p,q) i (ap+bq,cp+dq)\in\mathbb{Z}^{2}. Pokažite da je ovo preslikavanje jedno djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyev graf \mathcal{G}.Uputa: Po zadatku
Zadatak 3.16. Neka je \textbf{.} djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyev graf zadano u zadatku 3.15 . Pokažite da za svaki vrh \pm(p,q) Fareyevog grafa \mathcal{G} postoji matrica \begin{bmatrix} a & b\\ c & d \end{bmatrix}\in \operatorname{SL}(2,\mathbb{Z}) takva da je
\begin{bmatrix} a & b\\ c & d \end{bmatrix}\textbf{.}(\pm(p,q))=\pm(1,0).
Uputa: Korištenjem jednadžbe u zadatku i Bezoutove leme
4Fareyev kompleks i Fareyovo stablo
Sada ćemo korištenjem Fareyevog grafa uvesti pojam Fareyevog kompleksa, na osnovi kojeg ćemo konstruirati još jedan graf, takozvano Fareyevo stablo. Sljedeća definicija je iz
Definicija 4.1. Fareyev kompleks \mathcal{G}_{T} je Fareyev graf \mathcal{G} zajedno sa skupom
T=\lbrace \lbrace v_{1},v_{2},v_{3}\rbrace \ |\ v_{1},v_{2},v_{3}\in\mathcal{V}(\mathcal{G}), \lbrace v_{i},v_{j}\rbrace \in\mathcal{E}(\mathcal{G}),\text{ za svaki } i\neq j\rbrace .
Skupove t=\lbrace v_{1},v_{2},v_{3}\rbrace zovemo trokutima pa je skup T skup trokuta Fareyevog kompleksa \mathcal{G}_{T}. Ako je t\in T proizvoljan trokut, tada za svaki par u,v\in t, u\neq v, brid \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}) zovemo stranicom trokuta t .
Zadatak 4.2. Neka je \textbf{.} djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyev graf zadano u zadatku 3.15 . Definirajmo preslikavanje \textbf{.}:\operatorname{SL}(2,\mathbb{Z})\times T\rightarrow T formulom
A\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace =\lbrace A\textbf{.} v_{1},A\textbf{.} v_{2},A\textbf{.} v_{3}\rbrace ,
za A\in \operatorname{SL}(2,\mathbb{Z}) i \lbrace v_{1},v_{2},v_{3}\rbrace \in T. Pokažite da ovako zadano preslikavanje \textbf{.} daje jedno djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na skup trokuta T Fareyevog kompleksa \mathcal{G}_{T}.Uputa: Prvo primijetite da je kodomena ovog preslikavanja zaista T, tj., ako su A\in \operatorname{SL}(2,\mathbb{Z}) i \lbrace v_{1},v_{2},v_{3}\rbrace \in T proizvoljni, kako su v_{i},v_{j}\in\lbrace v_{1},v_{2},v_{3}\rbrace susjedni vrhovi za sve i\neq j, slijedi da su A\textbf{.} v_{i} i A\textbf{.} v_{j} također susjedni vrhovi. Zatim pokažite da \textbf{.} zadovoljava oba svojstva djelovanja grupe na skup T, tj., da je I\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace =\lbrace v_{1},v_{2},v_{3}\rbrace, za svaki \lbrace v_{1},v_{2},v_{3}\rbrace \in T, te da za proizvoljne A,B\in \operatorname{SL}(2,\mathbb{Z}) vrijedi A\textbf{.}(B\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace )=(AB)\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace, za sve \lbrace v_{1},v_{2},v_{3}\rbrace \in T .
Definicija 4.3. Neka je \mathcal{G} Fareyev graf te neka je \mathcal{G}_{T} Fareyev kompleks sa skupom trokuta T. Fareyevo stablo \mathcal{T} je graf sa skupom vrhova
\mathcal{V}(\mathcal{T}):=\mathcal{E}(\mathcal{G})\cup T
i skupom bridova
\mathcal{E}(\mathcal{T}):=\lbrace \ \lbrace \lbrace u,v\rbrace ,t\rbrace \ |\ \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}),t\in T,u,v\in t\rbrace .
Tek trebamo pokazati da je ovako zadan graf \mathcal{T} zaista stablo, ali prije ovog dokaza opišimo konstrukciju za \mathcal{T} te nacrtajmo sliku za nju. Na slici 3 prikazano je početnih pet koraka konstrukcije Fareyevog stabla \mathcal{T}, koji su nacrtani direktno na početnih pet koraka konstrukcije Fareyevog kompleksa \mathcal{G}_{T}.
Slika 3: Prvih pet koraka konstrukcije Fareyevog stabla \mathcal{T} (iz [??] ).
Opišimo početak ove konstrukcije. Nultom koraku konstrukcije Fareyevog grafa \mathcal{G} (pa tako i Fareyevog kompleksa \mathcal{G}_{T}), to jest bridu \lbrace \pm(1,0) ,\pm(0,1)\rbrace, odgovara jedan vrh, kojeg na slici smjestimo u polovište ovog brida. U prvom koraku konstrukcije Fareyevog kompleksa \mathcal{G}_{T} imamo dva trokuta, t_{1}=\lbrace \pm(1,0) , \pm(-1,1), \pm(0,1)\rbrace i t_{2}=\lbrace \pm(1,0) , \pm(1,1), \pm(0,1)\rbrace, od kojih nam svaki daje po dva nova brida Fareyevog grafa. Smjestimo po jedan vrh za graf \mathcal{T} u težista trokuta t_{1} i t_{2}, te po jedan vrh u polovište svakog od 4 dodana brida Fareyevog grafa, pa ove vrhove zatim povežemo bridovima kao u receptu iz definicije
Dokaz. Pokažimo da postoji jedinstveni put od vrha e:=\lbrace \pm(1,0),\pm(0,1)\rbrace \in\mathcal{V}(\mathcal{T}) do proizvoljnog vrha v\in\mathcal{V}(\mathcal{T}) u grafu \mathcal{T} iz definicije 4.3 , uz pretpostavku da je v\neq e. Uzimajući da je vrh e ishodište dvodimenzionalnog koordinatnog sustava, možemo podijeliti kompleks \mathcal{G}_{T} i graf \mathcal{T} na četiri kvadranta, koje si lako možemo predočiti na slici 3. Neka je sada v\neq e proizvoljan vrh grafa \mathcal{T} sadržan u gornjem desnom kvadrantu od \mathcal{T} (tj., u prvom kvadrantu koordinatnog sustava) i pretpostavimo da je vrh v dobiven n-tim korakom konstrukcije Fareyevog grafa \mathcal{G}. Pokažimo da postoji jedinstveni (e,v)-put u \mathcal{T}.
Nultim i prvim korakom konstrukcije Fareyevog kompleksa \mathcal{G}_{T} u gornjem desnom kvadrantu od \mathcal{T} dobijemo vrhove e, \lbrace \pm(1,0),\pm(1,1)\rbrace \in\mathcal{E}(\mathcal{G}) i \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace \in T. Ako je v=\lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace, krećemo se iz vrha e u vrh \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace i tako dobivamo traženi jedinstveni (e,v)-put. Ako je v=\lbrace \pm(1,0),\pm(1,1)\rbrace, krećemo se iz vrha e u vrh \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace pa zatim iz vrha \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace u vrh \lbrace \pm(1,0),\pm(1,1)\rbrace i tako dobivamo traženi jedinstveni (e,v)-put. Ako v nije jednak ni jednom od dva navedena vrha iz prvog koraka nastanka \mathcal{T}, nastavljamo proces kako slijedi.
Drugim korakom konstrukcije Fareyevog kompleksa \mathcal{G}_{T} u gornjem desnom kvadrantu od \mathcal{T} dobijemo vrhove \lbrace \pm(1,0),\pm(2,1)\rbrace, \lbrace \pm(2,1),\pm(1,1)\rbrace \in\mathcal{E}(\mathcal{G}) i \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace \in T grafa \mathcal{T}. Ako je v=\lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace, pomaknemo se iz vrha \lbrace \pm(1,0),\pm(1,1)\rbrace u vrh \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace i onda smo gotovi. Ako je v=\lbrace \pm(1,0),\pm(2,1)\rbrace ili v=\lbrace \pm(2,1),\pm(1,1)\rbrace, onda se iz vrha \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace pomaknemo u vrh \lbrace \pm(1,0),\pm(2,1)\rbrace ili u vrh \lbrace \pm(2,1),\pm(1,1)\rbrace i gotovi smo. Ako v nije jednak niti jednom od ta dva vrha, onda ako se v nalazi u djelu grafa \mathcal{T} između vrhova \pm(1,0) i \pm(2,1) Fareyevog grafa \mathcal{G}, pomaknemo se iz vrha \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace u vrh \lbrace \pm(1,0),\pm(2,1)\rbrace grafa \mathcal{T}, a ako se vrh v nalazi u djelu grafa \mathcal{T} između vrhova \pm(2,1) i \pm(1,1) Fareyevog grafa \mathcal{G}, pomaknemo se iz vrha \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace u vrh \lbrace \pm(2,1),\pm(1,1)\rbrace grafa \mathcal{T}. Na ovaj način nastavimo konstrukciju puta od vrha e do vrha v grafa \mathcal{T} i nakon n-tog koraka konstrukcije Fareyevog grafa \mathcal{G} ćemo doći do vrha v. Analogan postupak vrijedi za proizvoljan vrh grafa \mathcal{T} koji se nalazi u jednom od preostala tri kvadranta. Dakle, pokazali smo da za proizvoljni vrh v\neq e grafa \mathcal{T} postoji jedinstveni (e,v)-put u \mathcal{T}.
Iz leme2.7 slijedi da je \mathcal{T} stablo.
Nultim i prvim korakom konstrukcije Fareyevog kompleksa \mathcal{G}_{T} u gornjem desnom kvadrantu od \mathcal{T} dobijemo vrhove e, \lbrace \pm(1,0),\pm(1,1)\rbrace \in\mathcal{E}(\mathcal{G}) i \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace \in T. Ako je v=\lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace, krećemo se iz vrha e u vrh \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace i tako dobivamo traženi jedinstveni (e,v)-put. Ako je v=\lbrace \pm(1,0),\pm(1,1)\rbrace, krećemo se iz vrha e u vrh \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace pa zatim iz vrha \lbrace \pm(1,0),\pm(1,1),\pm(0,1)\rbrace u vrh \lbrace \pm(1,0),\pm(1,1)\rbrace i tako dobivamo traženi jedinstveni (e,v)-put. Ako v nije jednak ni jednom od dva navedena vrha iz prvog koraka nastanka \mathcal{T}, nastavljamo proces kako slijedi.
Drugim korakom konstrukcije Fareyevog kompleksa \mathcal{G}_{T} u gornjem desnom kvadrantu od \mathcal{T} dobijemo vrhove \lbrace \pm(1,0),\pm(2,1)\rbrace, \lbrace \pm(2,1),\pm(1,1)\rbrace \in\mathcal{E}(\mathcal{G}) i \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace \in T grafa \mathcal{T}. Ako je v=\lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace, pomaknemo se iz vrha \lbrace \pm(1,0),\pm(1,1)\rbrace u vrh \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace i onda smo gotovi. Ako je v=\lbrace \pm(1,0),\pm(2,1)\rbrace ili v=\lbrace \pm(2,1),\pm(1,1)\rbrace, onda se iz vrha \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace pomaknemo u vrh \lbrace \pm(1,0),\pm(2,1)\rbrace ili u vrh \lbrace \pm(2,1),\pm(1,1)\rbrace i gotovi smo. Ako v nije jednak niti jednom od ta dva vrha, onda ako se v nalazi u djelu grafa \mathcal{T} između vrhova \pm(1,0) i \pm(2,1) Fareyevog grafa \mathcal{G}, pomaknemo se iz vrha \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace u vrh \lbrace \pm(1,0),\pm(2,1)\rbrace grafa \mathcal{T}, a ako se vrh v nalazi u djelu grafa \mathcal{T} između vrhova \pm(2,1) i \pm(1,1) Fareyevog grafa \mathcal{G}, pomaknemo se iz vrha \lbrace \pm(1,0),\pm(2,1),\pm(1,1)\rbrace u vrh \lbrace \pm(2,1),\pm(1,1)\rbrace grafa \mathcal{T}. Na ovaj način nastavimo konstrukciju puta od vrha e do vrha v grafa \mathcal{T} i nakon n-tog koraka konstrukcije Fareyevog grafa \mathcal{G} ćemo doći do vrha v. Analogan postupak vrijedi za proizvoljan vrh grafa \mathcal{T} koji se nalazi u jednom od preostala tri kvadranta. Dakle, pokazali smo da za proizvoljni vrh v\neq e grafa \mathcal{T} postoji jedinstveni (e,v)-put u \mathcal{T}.
Iz leme
\ \blacksquare
Opišimo sada primjer djelovanja grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyevo stablo.
Primjer 4.5. Neka je \mathcal{G} Fareyev graf, \mathcal{G}_{T} Fareyev kompleks te neka je \mathcal{T} Fareyevo stablo. Tvrdimo da preslikavanje \textbf{.}:\operatorname{SL}(2,\mathbb{Z})\times\mathcal{V}(\mathcal{T})\rightarrow\mathcal{V}(\mathcal{T}) definirano na \mathcal{V}(\mathcal{T})=\mathcal{E}(\mathcal{G}) \cup T s
Budući da je stablo jednostavan graf, dovoljno je provjeriti svojstva iz definicije2.12 .
Prvo provjerimo da ovako definirano preslikavanje \textbf{.} zaista vrhove od \mathcal{T} šalje u vrhove od \mathcal{T}. Za proizvoljan vrh \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}) Fareyevog stabla \mathcal{T} slijedi da je A\textbf{.} \lbrace u,v\rbrace vrh Fareyevog stabla \mathcal{T}, za sve A\in \operatorname{SL}(2,\mathbb{Z}), jer iz zadatka3.15 znamo da \operatorname{SL}(2,\mathbb{Z}) djeluje na Fareyev graf \mathcal{G}, pa posebno djeluje na bridove \mathcal{E}(\mathcal{G}) Fareyevog grafa \mathcal{G}, odnosno svaki brid se preslikava u brid. Za proizvoljan vrh t\in T Fareyevog stabla \mathcal{T} slijedi da je A\textbf{.} t vrh Fareyevog stabla \mathcal{T}, jer iz zadatka 4 znamo da \operatorname{SL}(2,\mathbb{Z}) djeluje na skup trokuta T Fareyevog kompleksa \mathcal{G}_{T}, odnosno svaki trokut se preslikava u trokut.
Također, svojstva djelovanja grupe (1) i (2) iz definicije2.9 su zadovoljena jer znamo da \operatorname{SL}(2,\mathbb{Z}) djeluje na Fareyev graf \mathcal{G} i na skup trokuta T Fareyevog kompleksa \mathcal{G}_{T}.
Preostaje pokazati da preslikavanje \textbf{.} čuva susjednost vrhova Fareyevog stabla \mathcal{T}. Ako su \lbrace u,w\rbrace \in\mathcal{E}(\mathcal{G}) i \lbrace v_{1},v_{2},v_{3}\rbrace \in T susjedni vrhovi Fareyevog stabla \mathcal{T}, slijedi da je \lbrace u,w\rbrace stranica trokuta \lbrace v_{1},v_{2},v_{3}\rbrace, tj., u,w\in\lbrace v_{1},v_{2},v_{3}\rbrace. Bez smanjenja općenitosti, pretpostavimo da je v_{1}=u i v_{2}=w. Sada, za proizvoljnu matricu A\in \operatorname{SL}(2,\mathbb{Z}), imamo da je
Dakle, grupa \operatorname{SL}(2,\mathbb{Z}) djeluje na graf \mathcal{T}. \end{pr}
U ovom ćemo odjeljku uvesti takozvani Fareyev niz brojeva te vrlo ukratko pokazati njegovu vezu s Fareyevim grafom. Za detalje o povijesti uvođenja Fareyevog niza preporučamo članak[5] . Spomenimo samo da je John Farey, Sr. 1816. godine u znanstvenom časopisu Philosophical Magazine objavio prilog pod naslovom ” On a curious property of vulgar fractions”, gdje je primijetio svojstvo određenih nizova racionalnih brojeva koje ćemo u nastavku teksta opisati.
Pišemo ([3] ): F_{1}=\lbrace \frac{0}{1}, \frac{1}{1}\rbrace, F_{2}=\lbrace \frac{0}{1}, \frac{1}{2}, \frac{1}{1}\rbrace, F_{3}=\lbrace \frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}\rbrace, F_{4}=\lbrace \frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}\rbrace itd.
Dokaz za sljedeću lemu, koja opisuje jedno svojstvo Fareyevog niza, može se naći u[5] ili [4] :
Ovu vrstu ” zbrajanja” dvaju razlomaka zovemo Fareyevo zbrajanje.
Pokažimo sada vezu između Fareyevog niza i Fareyevog grafa. Fokusirajmo se samo na donji desni kvadrant Fareyevog grafa i zamijenimo sve vrhove \pm(m,n) tog kvadranta s razlomcima \frac{m}{n}. Svi razlomci \frac{m}{n} dobiveni ovom zamjenom su potpuno skraćeni, jer su svi (m,n) primitivni elementi iz \mathbb{Z}^{2}.
Prvim korakom konstrukcije Fareyevog grafa u donjem desnom kvadrantu dobijemo vrhove \frac{0}{1} i \frac{1}{1}, tj., dobijemo Fareyev niz F_{1}=\lbrace \frac{0}{1},\frac{1}{1}\rbrace. Fareyevim zbrajanjem vrhova \frac{0}{1} i \frac{1}{1} dobijemo razlomak \frac{1}{2} koji odgovara vrhu \pm(1,2) dobivenom zbrajanjem odgovarajućih predstavnika klasa \pm(0,1) i \pm(1,1), tj., drugim korakom konstrukcije Fareyevog grafa dobijemo Fareyev niz F_{2}=\lbrace \frac{0}{1},\frac{1}{2},\frac{1}{1}\rbrace (u donjem desnom kvadrantu Fareyevog grafa). Fareyevim zbrajanjem vrhova \frac{0}{1} i \frac{1}{2}, te vrhova \frac{1}{2} i \frac{1}{1}, dobijemo razlomke \frac{1}{3} i \frac{2}{3} koji odgovaraju vrhovima \pm(1,3) i \pm(2,3) dobivenim zbrajanjem odgovarajućih predstavnika klasa \pm(0,1) i \pm(1,2), te \pm(1,2) i \pm(1,1), tj., trećim korakom konstrukcije Fareyevog grafa dobijemo Fareyev niz F_{3}=\lbrace \frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}\rbrace. Fareyevim zbrajanjem vrhova \frac{0}{1} i \frac{1}{3}, \frac{1}{3} i \frac{1}{2}, \frac{1}{2} i \frac{2}{3}, te \frac{2}{3} i \frac{1}{1} dobijemo razlomke \frac{1}{4}, \frac{2}{5}, \frac{3}{5} i \frac{3}{4} koji odgovaraju vrhovima \pm(1,4), \pm(2,5), \pm(3,5) i \pm(3,4) dobivenim zbrajanjem odgovarajućih predstavnika klasa \pm(0,1) i \pm(1,3), \pm(1,3) i \pm(1,2), \pm(1,2) i \pm(2,3), te \pm(2,3) i \pm(1,1), tj., četvrtim korakom konstrukcije Fareyevog grafa dobijemo niz razlomaka \lbrace \frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{1}{1}\rbrace, koji sadrži cijeli Fareyev niz F_{4}=\lbrace \frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}\rbrace. Zatim petim korakom konstrukcije Fareyevog grafa dobijemo niz razlomaka \lbrace \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}\rbrace koji sadrži cijeli Fareyev niz F_{5}=\lbrace \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}\rbrace. Nastavljajući ovako dalje, imamo da n-tim korakom konstrukcije Fareyevog grafa dobijemo konačni niz razlomaka poredanih po veličini, koji sadrži cijeli Fareyev niz F_{n} u donjem desnom kvadrantu Fareyevog grafa.
Naglasimo ovdje da se Fareyevi nizovi mogu prikazati geometrijski pomoću niza tangentnih Fordovih kružnica ([6] ili [4] ). Na ovom se prikazu uvedu kružni lukovi koji povezuju odgovarajuće brojeve, te se takav prikaz veza između elemenata Fareyevog niza još naziva Fareyevim dijagramom ([4] ). Spomenimo još da se u teoriji brojeva koristi tzv. Stern-Brocotovo stablo za prikazivanje pozitivnih racionalnih brojeva ([7] ), te se lijevo podstablo Stern-Brocotovog stabla često također naziva Fareyevim stablom.
Zahvala: Autori zahvaljuju anonimnom recenzentu na pažljivom čitanju rada i vrlo korisnim savjetima za njegovo poboljšanje.
A\textbf{.} \lbrace u,v\rbrace =\lbrace A\textbf{.} u,A\textbf{.} v\rbrace , \forall A\in \operatorname{SL}(2,\mathbb{Z}),\forall \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}), \ \ i
A\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace =\lbrace A\textbf{.} v_{1},A\textbf{.} v_{2}, A\textbf{.} v_{3}\rbrace ,~\forall A\in \operatorname{SL}(2,\mathbb{Z}),\forall\lbrace v_{1},v_{2},v_{3}\rbrace \in T,
zadaje jedno djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyevo stablo \mathcal{T} (djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyevo stablo \mathcal{T} označavamo isto kao i djelovanje grupe \operatorname{SL}(2,\mathbb{Z}) na Fareyev graf \mathcal{G} i na skup T).Budući da je stablo jednostavan graf, dovoljno je provjeriti svojstva iz definicije
Prvo provjerimo da ovako definirano preslikavanje \textbf{.} zaista vrhove od \mathcal{T} šalje u vrhove od \mathcal{T}. Za proizvoljan vrh \lbrace u,v\rbrace \in\mathcal{E}(\mathcal{G}) Fareyevog stabla \mathcal{T} slijedi da je A\textbf{.} \lbrace u,v\rbrace vrh Fareyevog stabla \mathcal{T}, za sve A\in \operatorname{SL}(2,\mathbb{Z}), jer iz zadatka
Također, svojstva djelovanja grupe (1) i (2) iz definicije
Preostaje pokazati da preslikavanje \textbf{.} čuva susjednost vrhova Fareyevog stabla \mathcal{T}. Ako su \lbrace u,w\rbrace \in\mathcal{E}(\mathcal{G}) i \lbrace v_{1},v_{2},v_{3}\rbrace \in T susjedni vrhovi Fareyevog stabla \mathcal{T}, slijedi da je \lbrace u,w\rbrace stranica trokuta \lbrace v_{1},v_{2},v_{3}\rbrace, tj., u,w\in\lbrace v_{1},v_{2},v_{3}\rbrace. Bez smanjenja općenitosti, pretpostavimo da je v_{1}=u i v_{2}=w. Sada, za proizvoljnu matricu A\in \operatorname{SL}(2,\mathbb{Z}), imamo da je
A\textbf{.}\lbrace u,w,v_{3}\rbrace =\lbrace A\textbf{.} u,A\textbf{.} w,A\textbf{.} v_{3}\rbrace \ni A\textbf{.} u,A\textbf{.} w,
tj., A\textbf{.} \lbrace u,w\rbrace =\lbrace A\textbf{.} u,A\textbf{.} w\rbrace je stranica trokuta A\textbf{.}\lbrace u,w,v_{3}\rbrace, iz čega slijedi da su A\textbf{.} \lbrace u,w\rbrace i A\textbf{.}\lbrace v_{1},v_{2},v_{3}\rbrace susjedni vrhovi Fareyevog stabla \mathcal{T}.Dakle, grupa \operatorname{SL}(2,\mathbb{Z}) djeluje na graf \mathcal{T}. \end{pr}
5Veza Fareyevog grafa s Fareyevim nizom brojeva
U ovom ćemo odjeljku uvesti takozvani Fareyev niz brojeva te vrlo ukratko pokazati njegovu vezu s Fareyevim grafom. Za detalje o povijesti uvođenja Fareyevog niza preporučamo članak
Definicija 5.1. Za n\in \mathbb{N}, uzmimo sve racionalne brojeve \frac{p}{q} za koje, uz p,q\in\mathbb{Z} i q\neq 0, vrijedi još i 0\leq p\leq q\leq n i \operatorname{nzd} (p,q)=1. Fareyev niz reda n, u oznaci F_{n}, je konačan niz ovih brojeva poredanih po veličini.
Pišemo (
Dokaz za sljedeću lemu, koja opisuje jedno svojstvo Fareyevog niza, može se naći u
Lema 5.2. Neka su \frac{a}{b},\frac{p}{q},\frac{c}{d}\in F_{n} tri uzastopna člana Fareyevog niza F_{n}. Tada vrijedi \frac{p}{q}=\frac{a+c}{b+d}.
Ovu vrstu ” zbrajanja” dvaju razlomaka zovemo Fareyevo zbrajanje.
Pokažimo sada vezu između Fareyevog niza i Fareyevog grafa. Fokusirajmo se samo na donji desni kvadrant Fareyevog grafa i zamijenimo sve vrhove \pm(m,n) tog kvadranta s razlomcima \frac{m}{n}. Svi razlomci \frac{m}{n} dobiveni ovom zamjenom su potpuno skraćeni, jer su svi (m,n) primitivni elementi iz \mathbb{Z}^{2}.
Slika 4: Donji desni kvadrant Fareyevog grafa nakon petog koraka.
Prvim korakom konstrukcije Fareyevog grafa u donjem desnom kvadrantu dobijemo vrhove \frac{0}{1} i \frac{1}{1}, tj., dobijemo Fareyev niz F_{1}=\lbrace \frac{0}{1},\frac{1}{1}\rbrace. Fareyevim zbrajanjem vrhova \frac{0}{1} i \frac{1}{1} dobijemo razlomak \frac{1}{2} koji odgovara vrhu \pm(1,2) dobivenom zbrajanjem odgovarajućih predstavnika klasa \pm(0,1) i \pm(1,1), tj., drugim korakom konstrukcije Fareyevog grafa dobijemo Fareyev niz F_{2}=\lbrace \frac{0}{1},\frac{1}{2},\frac{1}{1}\rbrace (u donjem desnom kvadrantu Fareyevog grafa). Fareyevim zbrajanjem vrhova \frac{0}{1} i \frac{1}{2}, te vrhova \frac{1}{2} i \frac{1}{1}, dobijemo razlomke \frac{1}{3} i \frac{2}{3} koji odgovaraju vrhovima \pm(1,3) i \pm(2,3) dobivenim zbrajanjem odgovarajućih predstavnika klasa \pm(0,1) i \pm(1,2), te \pm(1,2) i \pm(1,1), tj., trećim korakom konstrukcije Fareyevog grafa dobijemo Fareyev niz F_{3}=\lbrace \frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}\rbrace. Fareyevim zbrajanjem vrhova \frac{0}{1} i \frac{1}{3}, \frac{1}{3} i \frac{1}{2}, \frac{1}{2} i \frac{2}{3}, te \frac{2}{3} i \frac{1}{1} dobijemo razlomke \frac{1}{4}, \frac{2}{5}, \frac{3}{5} i \frac{3}{4} koji odgovaraju vrhovima \pm(1,4), \pm(2,5), \pm(3,5) i \pm(3,4) dobivenim zbrajanjem odgovarajućih predstavnika klasa \pm(0,1) i \pm(1,3), \pm(1,3) i \pm(1,2), \pm(1,2) i \pm(2,3), te \pm(2,3) i \pm(1,1), tj., četvrtim korakom konstrukcije Fareyevog grafa dobijemo niz razlomaka \lbrace \frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{1}{1}\rbrace, koji sadrži cijeli Fareyev niz F_{4}=\lbrace \frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}\rbrace. Zatim petim korakom konstrukcije Fareyevog grafa dobijemo niz razlomaka \lbrace \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\frac{2}{5},\frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}\rbrace koji sadrži cijeli Fareyev niz F_{5}=\lbrace \frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}\rbrace. Nastavljajući ovako dalje, imamo da n-tim korakom konstrukcije Fareyevog grafa dobijemo konačni niz razlomaka poredanih po veličini, koji sadrži cijeli Fareyev niz F_{n} u donjem desnom kvadrantu Fareyevog grafa.
Naglasimo ovdje da se Fareyevi nizovi mogu prikazati geometrijski pomoću niza tangentnih Fordovih kružnica (
Zahvala: Autori zahvaljuju anonimnom recenzentu na pažljivom čitanju rada i vrlo korisnim savjetima za njegovo poboljšanje.
Bibliografija
