WIXLIB

AA ,w!////h, 01 2231A\m'B32234Figure 6. The hyperbolic grid B.in A and glueing the a and b sides, one obtains a torus.We can think of these glueings as implemented bymaps a: (x,y) -- (x 1,y) and b: (x,y) (x,y 1).(Incidentally, this explains why we chose to label thesides in Figure 2 as we did.) Now take the hyperbolicgrid e illustrated in Figure 6 and glue the A and Bsides, this time by the maps A: z (z 1)/(z 2) andB: z -- (z - 1)/( - z 2)d What you get is again a toms,except that since the corners of the "squares" in I areon the b o u n d a r y of hyperbolic space, one point ismissing on the torus and the effect of the hyperbolicmetric is to draw out the region around this punctureinto an infinitely long spike or cusp as in Figure 1. Justas the maps a,b of the Euclidean plane generate theabelian group :7/2 which is the fundamental group ofthe toms, so the maps A,B of the hyperbolic planegenerate a free g r o u p F which is the f u n d a m e n t a lgroup of the punctured torus 7-*. Each "square" inis an image of the central shaded square S under exactly one element of F, and the labelling of the sidesin each square is just a copy of the labels in S.Recall that straight lines or geodesics in H are semicircles centered on R, or vertical lines. We can posethe same question as before: Which A,B sequences occuras the cutting sequences of lines across t? Of course, oursequences may now contain not only the symbols A,Bbut also A - 1 , B -1 (henceforth written as A,B), depending on the direction in which we cut sides of e.Observation 3. In a cutting sequence across f a symbolis never immediately followed by its inverse. A set For m o r e details a b o u t hyperbolic g e o m e t r y a n d tessellations seet h e a u t h o r ' s earlier Intelligencer article " N o n - E u c l i d e a n G e o m e t r y ,C o n t i n u e d Fractions a n d Ergodic T h e o r y " in Vol. 4, No. 1, 1982.quence with this property is called reduced. The solution to our problem is this time remarkably simple:With one exception, every reduced sequence occurs as thecutting sequence of some geodesic in H, terminating sequences corresponding to lines beginning or ending at thepuncture.The exception is the periodic sequence . . . A B ABABAB . . . . This corresponds to a loop encircling thepuncture, which is a homotopy class with no geodesicrepresentative.The idea of the proof is to construct a polygonal pathin H whose cutting sequence is the same as that of agiven reduced sequence s. This path will consist of linesegments joining one square in r to an adjacent one.Each segment is labelled by the side it cuts. Startingfrom S, we can construct a path whose cutting sequence coincides with s, s h o w n by dotted lines inFigure 6. The fact that s is reduced simply means thatthe path never doubles back on itself. It is not hard toprove that such paths always converge to two definitedistinct points at infinity with the exception of the badcase (ABA B)C Joining these points one obtains a geodesic whose cutting sequence is exactly s.The same method shows that two geodesics have thesame cutting sequence if and only if they can be transformedone into the other by an element in F. Since transformations in F preserve f and its labelling, sufficiency isobvious. Suppose that two geodesics have the samecutting sequence. By applying a transformation in F toone of them we can suppose that both cut the sameside of at the same point in their cutting sequence.Fixing an initial side fixes the edge paths of both sequences, which therefore coincide. It follows that thetwo geodesics are the same.THE MATHEMATICALINTELLIGENCERVOL. 7, NO. 3, 1985 23

(1 (1w(1 aW 2 s- "IIiiIIIIiiIIIiII! i!i32o4Figure 7. The tessellation P subdivided into fundamental regions for SL(2,Z).SL(2,77) a n d C o n t i n u e dFractionsThere was no real r e a s o n to take the basic shape S into be a square. O n e can play the same game withany tessellation p r o v i d e d that the vertices of thef u n d a m e n t a l region R all lie at infinity. O n e such tessellation is illustrated in Figure 7. This is associated toF(2), a s u b g r o u p of index 3 in SL(2,/7). * The sides ofthe f u n d a m e n t a l region R are m a p p e d to each otherby the maps Q: z - l / z , W: z 2 - l/z, and thisgives the labelling in Figure 7. As s h o w n in the diagram is s u b d i v i d e d into three regions each of whichis a f u n d a m e n t a l region for SL(2,Z). The matrix f (0 - ) is a rotation b y 2-rr/3 about 1 V l/2 and rotatesthese regions o n t o each other.The cutting sequences of geodesics relative to U areof the form . . . Q W ' , Q W n 2 Q . . . . w h e r e n i E 7 . Notice that Q2 n e v e r appears since Q - 1 Q.Since SL(2,77) is g e n e r a t e d by Q , W a n d fl, its actionpreserves the tessellation although not the Q,W labelling. We can, h o w e v e r , label s e g m e n t s of geodesicscutting across the triangles in U so as to be invariantu n d e r SL(2,Z), b y labelling a segment L or R accordingto w h e t h e r the vertex of the triangle cut off by thes e g m e n t is to left or right, as w e have done in Figure8. It is easy to write d o w n a recipe for conversion fromQ , W to L , R sequences:QWW WWQQWWW J,WQ LLLRRRIt n o w follows that two geodesics in H are equivalent underSL(2, )if and only if their L , R sequences agree.But this is not all. The L,R sequences bring us backto c o n t i n u e d fractions! Let 0 be a n y p o s i t i v e realn u m b e r , a n d as in Figure 8 let (0) be a geodesic rayjoining a n y point on the imaginary axis to 0. Readingoff t h e L,R s e q u e n c e of /(0) w e o b t a i n a s e q u e n c eLnoRnlLn2 . . . (if 0 1 the sequence begins with R notL). T h e n [no, n l , n 2 . . .] is the c o n t i n u e d fraction expansion of 0!The p r o o f is not hard. First, it is obvious that n o [0]. Let D be the point w h e r e /(0) cuts 0 n 0. Applying the m a p "rl: z - 1 / z - n 0, D is m a p p e d to apoint D' o n the imaginary axis and /(0) becomes a ray /' t h r o u g h D' pointing in the negative direction withe n d p o i n t at - 1 / 0 - n 0. The n I segments of type R in (0) w h i c h follow the initial n o segments of type L aren o w a p p a r e n t as the n 1 vertical strips crossed by r ( )before it descends to -1(0). T h u s n I 1/0 - n o, so thatt Recall SL(2,77) {(3b )la,b,c,d E 7/, ad - bc 1}. Of course SL(2,77) 0 n o 1In 1 r, 0 r 1. N o w apply-r1: z---*- 1 / ( z nl) to /' and p r o c e e d as before [9].acts o n H b y z a z b/cz d.24T H E M A T H E M A T I C A L INTELLIGENCER VOL. 7, N O . 3, 1985

Dw fR -4-----13'013122312Figure 8. Reading off the continued fraction expansion of 0 from 3 :]0 3 1 .Simple Curves on the Punctured Torus and theDickson RulesWe indicated at the b e g i n n i n g that Markoff irrationalities are associated to simple loops on the p u n c t u r e dtorus T*. We are n o w in a position to u n d e r s t a n d exactly w h a t these loops are. In fact: A geodesic on T* isclosed and simple if and only if its cutting sequence is periodic and characteristic. By t h e c u t t i n g s e q u e n c e of acurve on T* we m e a n , of course, the cutting sequenceof any of its lifts to H. Since all these lifts are equivalentu n d e r F, we k n o w that cutting sequences c o m i n g fromdifferent lifts are the same. Closed geodesics corres p o n d exactly to t h o s e w i t h p e r i o d i c c u t t i n g seq u e n c e s . We k n o w t h a t p e r i o d i c c h a r a c t e r i s t i c sequences c o r r e s p o n d exactly to lines of rational slopeo n the square grid A. Let L be such a line, a n d m o v eL if necessary so as to avoid the vertices of A.Since L is disjoint from all its images u n d e r the vertical and horizontal translations a and b, its image onT c a n n o t contain a n y self-intersections; in o t h e r words,it is simple. N o w t h e r e is exactly o n e F - e q u i v a l e n c eclass of geodesics o n the hyperbolic plane H with thesame cutting s e q u e n c e as L, and it is not h a r d to s h o wthat the c o r r e s p o n d i n g geodesic on T* is also simple.This geodesic is obtained, if y o u like, b y pulling tightt h e c u r v e L o n T r e l a t i v e to the h y p e r b o l i c m e t r i co n T*./\//,'/Figure 9. The curve .AAABAAA.T H E M A T H E M A T I C A L 1 N T E L L I G E N C E R V O L . 7, N O . 3, 198525

//o//IIt-2-1Figure 10. Curves containingA2B 212and BAB intersect H.N o w let X be the set of all geodesics on T* whichare limits of s i m p l e c l o s e d g e o d e s i c s . A n y limit ofsimple geodesics is simple, and any sequence whichis a limit of characteristic sequences is characteristic,for to see that a s e q u e n c e is not characteristic y o u onlyn e e d to look at a sufficiently long finite block. Thuswe find that a geodesic on 7* lies in X if and only if itscutting sequence is characteristic. Incidentally, there aregeodesics on 7* w h i c h are simple b u t d o not lie in X.An e x a m p l e is the n o n - c h a r a c t e r i s t i c s e q u e n c e . . .A A A B A A A . . . . This curve spirals into the loop A fromo p p o s i t e d i r e c t i o n s o n t h e t w o sides as s h o w n inFigure 9.Returning to Figures 6 and 7, notice that r is a subtessellation of the F(2) tessellation . This m e a n s thatA,B s e q u e n c e s c a n also be c o n v e r t e d i n t o L,R sequences. The m a p is as follows:ABABAA-BABABBLLRLRRRLRLand so on. Characteristic sequences have, of course, avery special form: t h e y convert to e i t h e r . . . (LR)nRL(LR)nRL . . . or . . . (LR)nLLRR(LR)nLLRR. . . . In addition, these special L,R sequences can be derived inan obvious w a y a n d the derived sequences will be ofthe same kind. S u p p o s e that 0 is the e n d p o i n t ofthe lift of a simple geodesic oLon 7*. The L,R sequencesof oL and of a n y ray /(0) joining to 0 will eventuallyagree. So we can read off the tail of the continuedfraction e x p a n s i o n of 0 from the L,R sequence of e . Itwill be [ . . . . 1,1 . . . . .1,2,2,1 . . . . .1,2,2,1 . . . . ],260THE MATHEMATICAL INTELLIGENCER VOL. 7, NO. 3, 1985w h e r e for some n the blocks of l ' s are of length 2n or2(n 1), and all derived sequences are of the sameform.N e e d l e s s to say, these tails are exactly those whichobey the Dickson rules!A p p r o a c h i n g the PunctureWe have established that Markoff irrationalities are exactly the e n d p o i n t s of lifts of simple geodesics in X.But w h a t have simple geodesics to do with Diophanfine approximation? The k e y is the observation thatgeodesics in X n e v e r a p p r o a c h too close to the p u n c ture P. In fact, in H they n e v e r rise above the line Imz--- 3/2. W h a t is e v e n m o r e remarkable is that the converse is also true: A geodesic ",/on H projects to a geodesicin X if and only if Imz 3/2 for all z F , where F / is theset of all translates of / under F.For the proof it will be useful to consider two isometries of H which preserve the lattice f while alteringthe labelling. One is the reflexion r in the imaginaryaxis, w h i c h interchanges the labels A and B. The otheris translation t: z z 3, w h i c h interchanges A witha n d B with B. Notice that lies below the line Imz 3/2 if a n d only if "y A t( /) 0.O n the grid A the substitution t: a --* , b -- b isi m p l e m e n t e d b y rotation b y "rr about 0. A n y line L iseither disjoint from or coincides with t(L) and h e n c e Land t(L) project to disjoint or coincident curves o n T.But t h e n the same is true of (L), the c o r r e s p o n d i n ggeodesic on 7*. It follows that a n y curve w h o s e cuttingsequence is linear lies b e l o w Imz 3/2. Taking limits,the same holds for the lifts of a n y curve in X.

A(v)--10Figure 11. Curves containing AB3A cut H.1The converse statement is the deepest result whichwe shall prove here, although the m e t h o d s are reallyno harder than those we have used to date. First, notice that just as the derivation a ab n, b -- b of A wasinduced by a linear m a p 9 of 2, so the derivation AA B , B A is i n d u c e d by the isometry 8: z z 1 of H. The n e w set of generators A' A B , B' A ofF is associated to a tessellation f ' identical with e andwith the same pattern of labels but translated one unitto the left.The cutting sequence of a geodesic /relative to l ' isthe derived sequence of the cutting sequences of /relative to f , where we n o w extend the m e a n i n g of" d e r i v e d " to m e a n the sequence obtained substitutingB' for A and B ' A ' for B n s.S u p p o s e t h a t s is a n o n - c h a r a c t e r i s t i c s e q u e n c e .Using the observations above we m a y a s s u m e that shas been derived e n o u g h times that we see in s eithera sequence XYnX or X 2 y x Y . . . X Y 2. Let H be theregion above Imz 3/2. Fig ure10 illustrates that curvescontaining sequences X Y X or X2y2 intersect H.Suppose inductively that a n y curve w h o s e sequencecontains x y n x has a lift cutting H. Figure 11 illustratesa curve /containing A B n I A and its image t( /) containing A Bn IA. O n e can see that /N t( ) a 0 unlessthe sequence A B n 1X is preceded by BnA. But then /would contain the sequence A B n A , which we have already dealt with. Obvious symmetries deal with theother cases.Using the substitutions r and t we are n o w reducedto the case where s contains either A 2 B A B . . .A B 2 orA2BA-B . . . A B 2. In the first, the derivation 8 producesa sequence containing a block XY"Yr in the second itgives a sequence all of whose exponents are negative234which is, after applying t, already disposed of.Notice that this proof d e p e n d s only on looking atfinite blocks in the cutting sequence; in other words,to see that a geodesic enters H, it is e n o u g h to look ata n y finite segment along which the derivation rulesare violated. This fact will be important to us below.Diophantine ApproximationWe are n o w finally able to bring all the pieces togethera n d r e t u r n to M a r k o f f ' s original a p p r o x i m a t i o nproblem. W h a t we proved in the last section a m o u n t sto s h o w i n g that a geodesic in X avoids the image H ofH on 7*. Thus the lifts of such geodesics avoid noto n l y H but all images of H u n d e r F. By a simple calculation the image of H u n d e r ( b) E F is a circle tangent to at a/c, of radius 1/3c 2. Moreover, as ( b) r u n st h r o u g h F, a/c takes on all possible rational values. Letus denote the union of all these horocycles by N.We can d i v i d e irrational p o i n t s 0 ( R into t h r e etypes, according to the asymptotic behaviour of theL,R cutting sequence of the vertical line v(0) joining 0to infinity. Denote the L,R sequence of v(0) from thenth term on by sn(O ). There are three possibilities:(i) For some n, Sn(O ) is characteristic and periodic.(ii) For some n, sn(O ) is characteristic but Sm(O) is notperiodic for any m.(iii) Sn(O ) is never characteristic.In case (i), Sn(O ) represents a simple closed geodesicon 7*. Of course lifts to a geodesic e on H withe n d p o i n t at 0. Since the image V(0) of v(0) approachesasymptotically on T*, and since is a b o u n d e d disTHE MATHEMATICAL INTELLIGENCER VOL. 7, NO. 3, 198527

Hv(oFigure 12. Simple curvesavoiding horocycles.tance outside H, w e see that v(0) enters N only a finiten u m b e r of times. Thus one sees from Figure 12 thatthe inequality 10 - a/c I 1/3c2 has only a finite numberof solutions so that v(0) 1/3.One can actually calculate that the closest approachof a to H is log coth f (o0/2 where r (o0 is the hyperboliclength of o [6]. This gives an exact value for v(0).In case (ii) the tail of v(0) is characteristic and henceV can be approximated by a sequence of simple curves ,. Since t h e r e are o n l y finitely m a n y c u r v e s withlengths below a given bound, the sequence of lengthstends to infinity a n d h e n c e the d i s t a n c e to H app r o a c h e s zero. T h u s v(0) a p p r o a c h e s N arbitrarilyclosely although from some point on it never enters Nsince s,(O) is e v e n t u a l l y characteristic. C o m b i n i n gthese facts one sees that v(0) 1/3.Finally, in case (iii) the tails sn (0) are never characteristic and so v(0) enters N infinitely often. Thus thereare infinitely m a n y solutions to 10 - a/c I 1/3c2; inother words, v(0) 1/3.Trace Formulae, Diophantine Equations andQuadratic FormsHoping that the reader's patience is not completelye x h a u s t e d , w e will c o n c l u d e b y giving s o m e briefpointers to the connection of our approach to anotherwell k n o w n aspect of Markoff's theory, the mimima ofbinary quadratic forms.The Markoff spectrum if frequently calculated by int r o d u c i n g Markoff triples. These are i n t e g e r triples28 THE MATHEMATICAL INTELLIGENCERVOL. 7, NO. 3, 1985(x,y,z) which are solutions of the Diophantine equationX 2 q y 2 Z2 3xyz.(D)Associated to such a triple is a pair of real quadraticn u m b e r s , ' 1/2 y/xz 1/2(9 - 4/z2) '/2. The numbers , ' are Markoff irrationalities with v( ) u( ') V9-4/z 2 1/3.In fact, as explained in [2], Markoff triples are (upto a factor of 3) the traces of triples (U,V, VLO such thatU,V are a pair of generators for the group F with fundamental region as s h o w n in Figure 13. The simplestsolution (1,1,1) corresponds to the A,B generators w eu s e d above. The formula (D) is nothing other than oneof Fricke's trace identities relating traces of matrices inSL(2,R). Starting with the solution (1,1,1) the operations (x,y,z) (z,x,y) and (x,y,z) (x,3xy - z,y) generate all possible solutions to (D). These operations arethe same as the operations of derivation and substitution which w e used above.The geodesics (A), (B) corresponding to the minimal solution (1,1,1) of (D) are simple. Since the operation of derivation is induced by an isometry of T*,the same is actually true of all solutions of (D). N o wthe geodesic (M) associated to a matrix M ( b) (F is the projection of a geodesic (M) on H w h o s eendpoints are the fixed points M, M of M on R. Theseendpoints are of course roots of c 2 (d - a) - b 0. Thus we see in another w a y that Markoff irrationalities are the endpoints of lifts of simple geodesicson T*.One can associate to M the quadratic form

V LIV VU bM(x,y) c x 2 4- ( d -a)xy-b y 2.Since y(M) is simple it lies below the line Imz 3/2, inother words, I M -- MI 3. N o w I M - 1 A'/qQM(1,0) w h e r e & TraM - 1 is the discriminant ofQM, so that QM(1,0)/AV2 1/3.But we k n o w more. Since the action of SL(2,Z) onH preserves L,R sequences, it preserves simple geodesics o n T*. Thus if y(M) is simple, so is y(gMg -1) forany g E SL(2,Z). O n e easily c o m p u t e s thatQM(x,Y) QgMg- ffgx,gy)and that QM a n d QgMg-1 have the same discriminant4. Given any pair (x,y) 772 w e can always find gSL(2,Z) with (gx,gy) (1,0). HenceQM(X,y) QgMg-l(1,0) A'/q3;in other words,minx,y E 772-QM(x,y)- v2lb.Of course the actual value of the m i n i m u m can be calculated and is, n o t surprisingly, V( M). For matrices Mwhich do not c o r r e s p o n d to simple geodesics, the mini m u m lies on or b e l o w the value 1/3.These are the results of Markoff on m i n i m a of binaryquadratic forms.It seems clear f r o m the foregoing that the next levelof approximation s h o u l d be studied by looking at geodesics with one self-intersection. Such geodesics penetrate only a b o u n d e d distance into H. O n e w o n d e r sFigure 13. Fundamentalregion for the puncturedtorus.U if these further levels of a p p r o x i m a t i o n are p e r h a p srelated to p h e n o m e n a of successive transitions f r o mperiodicity into chaos?References1. E. B. Christoffel, Observatio Arithmetica, Annali di Mathematica, 2nd series, 6(1875), 148-152.2. H. Cohn, Approach to Markoff's minimal forms throughmodular functions. Ann. Math. 61(1955), 1-12.3. H. Cohn, Representation of Markoff's binary quadraticforms by geodesics on a perforated torus. Acta Arithmetica XVIII(1971), 125-136.4. L. E. Dickson, Studies in

THE MATHEMATICAL INTELLIGENCER VOL. 7, NO. 3, 1985 21 . F19ure 4. F19ure 5. 7a11y mark5 5h0w1n9 1unar m0nth5 and 501ar year5. 0ther than the der1ved 5e4uence 0f the cutt1n9 5e- 4uence 0f L re1at1ve t0 A. 7h15 der1ved 5e4uence 5 ,