The length of closed geodesics on random Riemann Surfaces.

Eran Makovermakovere@ccsu.edu and Jeffrey McGowanmcgowan@ccsu.edu

November 27, 2006

Abstract
Short geodesics are important in the study of the geometry and the spectra of Riemann surfaces. Bers' theorem gives a global bound on the length of the first 3 g − 3   geodesics. We use the construction of Brooks and Makover of random Riemann surfaces to investigate the distribution of short ( < log ( g )   ) geodesics on a random Riemann surfaces. We calculate the expected value of the shortest geodesic, and show that if one orders prime non-intersecting geodesics by length γ 1 ≤ γ 2 ≤ ⋅ ⋅ ⋅ ≤ γ i , . . .   , then for fixed k   , if one allows the genus to go to infinity, the length of γ k   is independent of the genus.

1 Introduction

A standard tool in the study of compact Riemann surfaces is the decomposition into “pairs of pants” (Y pieces). Given a surface of genus g ≥ 2   , there are 3 g − 3   simple closed geodesics which partition the surface into g − 1   such pieces. Bounds on the lengths of the geodesics in such partitions are extremely desirable. If the geodesics are γ 1 , … , γ 3 g − 3   , their lengths l ( γ i )   give half of the Fenchel-Nielsen parameters which parametrize the 6 g − 6   dimensional Teichmüller space of compact surfaces of genus g   .
Bers ([?, ?] ) proved that for every compact Riemann surface of genus g ≥ 2   there is a partition with l ( γ 1 , … , l ( γ 3 g − 3 ) ) ≤ L g   where L g   is a constant depending only on g   . The best possible such constant is called Ber's constant. A constructive argument due to Abikoff ([?] ) gives an explicit bound for L g   ; unfortunately this bound grows faster than exponentially in g   . The best result known is
Theorem 1.1 ([?] ). Every compact Riemann Surface of genus g ≤ 2   has partition γ 1 , . . . , γ 3 g − 3   satisfying l ( γ k ) ≤ 4 k log 8 π ( g − 1 ) k k = 1 , . . . , 3 g − 3   The longest geodesic is bounded by
γ 3 g − 3 ≤ 26 ( g − 1 ) (1)
One might hope that in fact the bound in ( 1 ) might be improved to a logarithmic one, but this is impossible. The “hairy torus” gives a lower bound of
Proposition 1.1. L g ≥ 6 g − 2   for all g ≥ 2   .
The length of the shortest geodesic l ( γ 1 )   is also of particular interest. There are examples of classes of surfaces, such as the conformal compactification of the principal modular surfaces, where it is known that ([?, ?]  ) l ( γ 1 ) = O ( log g ) .   Recently Katz Schaps and Vishne [?]  show for Hurwitz surfaces and some other principal congruence subgroups of arbitrary arithmetic surfaces a similar behavior.
But all these examples are rare in the sense that they not occur in all genera and when they do occur they there are a small number of such surfaces. In this paper, we study the Belyi surfaces . Such surfaces are dense in the set of Riemann surfaces ([?] ). In contrast to the previous examples , we prove
Theorem 1.2. Let S   be a Belyi surface of genus g ≥ 2   , as g → ∞   the length of the shortest simple closed geodesic on S   , denoted s y s t ( S )   , is bounded by
2.809 ≤ E ( s y s t ( S ) ) ≤ 3.085 . (2)
When E   is the expected value. In particular, E ( s y s t ( S ) )   is independent of g   for surfaces with large genus.
We also get information about the lengths of some longer geodesics. We consider a set of prime non intersecting geodesics arranged by length γ 1 ≤ γ 2 ≤ ⋅ ⋅ ⋅ ≤ γ i , . . .   . We will show that they are all simple and therefore, it is always possible to complete this set and get a pair of pants decomposition [?] . We show that
Theorem 1.3. For any fixed i   , E ( l ( γ i ) )   is independent of the genus g   as g → ∞   .
This estimate in fact holds for roughly g log g   short geodesics out of the total 3 g − 3   which requires to get a pants decomposition of the surface. We provide estimates for the lengths of these geodesics and show that they are all bounded by C log g   . This result is in sharp contrast to Buser's result for general Riemann surfaces where the shortest geodesics are ∼ log g   , the same magnitude as the longest geodesics covered by our estimate.
We analyze the length of the geodesics using the method developed by Brooks and Makover in [?] . They use cubic graph to generate the Belyi surfaces and endow the set surfaces with probability measure inherit from random cubic graphs.
In section  2 we will describe the basic construction of compact surfaces from cubic graph. We review the connection between the metric structure of the surface and the combinatorics of the graphs.Next, in section  3 we connect cycles in the graph with geodesics on a surface, and show that our methods allow us to consider cycles in the graph Γ   of length ∼ log g   (see  10 ). We will do so by investigating an interesting explicit example of random matrix multiplication and analyzing the different moments of the distribution of the entries. As it turns out, the entries of the matrix product are a Stern sequence which is an integer sequence of independent interest.
Next, in section  4 (Theorem  4.2 ) we use the above results to show that the length of the geodesic associated to such a cycle is growing linearly with the length of the cycle. A detailed analysis of the growth rate of the Stern sequence shows that for a given cycle length on the graph the length of geodesics on the surface is concentrating around the mean length. We produce the Stern sequence using random products of 2 × 2   matrices.
These random products are similar to processes described by Viswanath ([?] ) for random Fibonacci sequence, Lima and Rahibe [?]  in the physics of disordered systems, and others. In our example, due to the properties of the Stern sequence, we get more detailed results on the random product then we could find in the literature for similar processes. This example may be of an independent interest in the study of random products of matrices, hence we include a more thorough discussion of our investigations than is necessary to prove our main results.
Finally, in section  5 we calculate the numerical bound to length of the shortest geodesic.
This gives a somewhat surprising picture of such random Riemann surfaces.
In ([?] ) Brooks and Makover showed that the Cheeger constant of random Riemann surfaces is bounded from below. Hence the geodesics that we find can not disconnect large pieces of the surface. The picture becomes even more complicated by the result ([?, ?] ) that shows that there is an embedded ball on the surfaces with area of ∼ 2 3   of the area of the surface. A “generic” Riemann surface therefore looks something like figure  1 .

Figure 1 : A “generic” Riemann surface.

2 Basic Construction

We wish to construct Riemann surfaces from cubic (3 regular) graphs[?]  . We will need to add additional combinatorial structure an orientation. We define orientation O   on the graph, as a cyclic permutation of the edges emanating from a each vertex v   . Each vertex in the graph will be identified with an ideal hyperbolic triangle T   with vertices at 0   , 1   , and ∞   (see Figure  2 ).

Figure 2 : An ideal triangle.

We may think of the points in P = { i , i + 1 , i + 1 2 }   as “midpoints” of the corresponding sides of the triangle T   . The solid lines in Figure  2 are geodesics joining the points in P   with the point 1 + i 3 2   , while the dotted lines are horocycles joining pairs in S   .
Now we can glue neighboring triangles subject to two conditions the first is that the “midpoints” of sides are glued together, and the second is that the orientation O   at the vertex agree with the orientation of T   .
Such a gluing is uniquely determined given ( Γ , O )   . The resulting surface is an open complete Riemann surface S O ( Γ , O )   , and we define the compact surface S C ( Γ , O )   as its conformal compactification. While for any given graph of size n   there are only 2 n   such surfaces, the following theorem will allow us to model “generic” surfaces using surfaces generated from graphs.
Theorem 2.1 ([?] ). The set of surfaces constructed from cubic graphs is dense in the set of Riemann surfaces.
To work with the set of surfaces generated from random cubic graphs with n   vertices, we will need a probability measure for the set of such graphs. While the fact that for each n   we have a finite set of such graphs, it is hard to work with [?]  [?] therefore we will use Bollobas' configuration model.
Put 6 n   balls in a hat; label the balls using the numbers 1 , 2 , . . . , ( 2 n )   , with three copies of each number. Then pick at random pairs of balls. We can define a graph by taking a set of 1 , 2 , . . . , ( 2 n )   vertices, and connecting vertices v i   to v j   by an edge if a pair of two balls marked with i   and j   have been picked together. We will endow the set of oriented cubic graphs with a probability measure by picking a graph using the configuration model and then flipping an unbiased coin at each vertex to pick an orientation. Note, we will allow loops and double edges since they not do not interfere with the construction of the surface S O ( Γ , O )   . We use the notation ℱ n   for the set of cubic graphs on 2 n   vertices with the above probability measure, and ℱ * n   for the set of oriented cubic graphs with the same probability measure.
For the unoriented graphs Bollobas proved ([?]  [?] )
Theorem 2.2. Let X i   denote the number of closed paths in Γ   of length i   .
Then the random variables X i   on ℱ n   are asymptotically independent Poisson distributions with means λ i = 2 i 2 i .  
In order to study the lengths of simple closed geodesics on the compact surfaces S C ( Γ , O )   , we must understand the relation of the metric structure of S C ( Γ , O )   and S O ( Γ , O )   . The following two theorems show that as n → ∞   , almost all surfaces S C ( Γ , O )   have a global metric structure arbitrarily close to S O ( Γ , O )   .
Theorem 2.3 ([?] ). We say that S O ( Γ , O )   has cusps ≥ L   if there is a set of disjoint horocycles, one around each cusp and each has length ≥ L   . Then for every ε   , there exists numbers L , r ,   and y   such that, if the cusps of S O   have length ≥ L   , outside the union of cusp neighborhoods U = ∪ i = 1 k f i − 1 ( C y ) ⊂ S O   of the cusps C i   , and V = ∪ i = 1 k B r ( p i ) ⊂ S C   , the metrics d s C 2   and d s O 2   satisfy 1 ( 1 + ε ) d s O 2 ≤ d s C 2 ≤ ( 1 + ε ) d s O 2 .  
The large cusp condition is necessary and enables us to compare the global metric of open and compact surfaces. Let Q   be a property of 3   -regular graphs with orientation, and denote by P r o b n [ Q ]   the probability that a pair ( Γ , O )   picked from ℱ * n   has property Q   .
Theorem 2.4 ([?] ). For every L > 0   , as n → ∞   , P r o b n [ S O ( Γ , O ) h a s c u s p s o f l e n g t h > L ] → 1 .  

3 Geodesics on S C ( Γ , O )   .

The discussion in the previous section shows that we can use the graph Γ   to get information about the surface S C ( Γ , O )   . To do this, we must begin with a cycle in Γ   and its' associated geodesic on S O ( Γ , O )   . Next, we track the geodesics as the cusps of S O ( Γ , O )   are closed to give S C ( Γ , O )   .
The geodesics of S O ( Γ , O )   are described in the oriented graph ( Γ , O )   as follows; let ℒ   and ℛ   denote the matrices ℒ = ( 1 1 0 1 ) ℛ = ( 1 0 1 1 ) .   A closed path P   of length k   on the graph may be described by starting at the midpoint of an edge, and then giving a sequence ( w 1 , … , w k ) ,   where each w i   is either l   or r   , signifying a left or right turn at the upcoming vertex. We then consider the matrix
M P ( k ) = W 1 … W k , (3)
where W j = ℒ   if w j = l   and W j = ℛ   if w j = r   .
The closed path P   on Γ   is then homotopic to a closed geodesic γ ( P )   on S O ( Γ , O )   whose length l e n g t h ( γ ( P ) )   is given by
2 cosh ( l e n g t h ( γ ( P ) ) 2 ) = t r ( M P ) . (4)
We have to check what happen to the geodesics on S O ( Γ , O )   as we close the cusps and get S O ( Γ , O )   . Given a simple geodesic γ   on S O ( Γ , O )   let γ ˘   be the image of γ   in S C ( Γ , O )   .
First γ ˘   might be homotopicaly trivial. This can happen in two ways. One is that the orientation on the path is uniform (all ”Left” or all ”Right”) and in this case the path is circling a cups and the length formula ( 4 ) gives 0   since there is no geodesic in its homotopy class in S O ( Γ , O )   . The second possibility is that γ ˘   is nontrivial on S O ( Γ , O )   but bounds a disk in S C ( Γ , O )   , in this case the corresponding cycle on the graph disconnects the graph.
Second, the image of two non equivalent geodesics on S C ( Γ , O )   might become homotopicaly equivalent on S C ( Γ , O )   . The treatment of this case is similar to the second case above since, in this case the images of the two geodesics bound a cylinder in S C ( Γ , O )   and therefore the cycles on the graph disconnect the graph. The probability that one or two cycles will disconnect the graph tends to 0   by the following
Lemma 3.1. Let P   be a cycle or union of two cycles on Γ n   with l e n g t h ( P ) < C log n   then P r o b n [ P d i s c o n n e c t Γ n ] → 0 .  
The proof of this lemma is a straight forward application of the following results
Theorem 3.1 ([?] ). P r o b n [ h ( Γ ) > 2 11 ] → 1 a s n → ∞ .  
Therefore if P   disconnects Γ   it induces a subgraph H ⊂ Γ   with v ( H ) ≤ C o n s t * v ( P )   but it is known that
Theorem 3.2 ([?, ?] ). Let H   be a graph such that v ( H ) < e ( H )   . Then the expected number of copies of H   in a random cubic graph with n   vertices is O ( n − 1 )  
Given a geodesic γ   on S O ( Γ , O )   . Let γ ˘   be the image of γ   in S C ( Γ , O )   then if γ ˘   is not homotopicly trivial after closing all cusps, then there is a unique geodesic γ ^   homotypical to γ ˘   in S C ( Γ , O )   . Under the large cusps condition we can compare the length of γ   and γ ^  
Theorem 3.3 ([?] ). l e n g t h ( γ ) 1 + ε ≤ l e n g t h ( γ ^ ) ≤ l e n g t h ( γ )  
Before computing the expected length of the geodesic corresponding to a cycle of length l   on the graph we must deal with the question of how far the Bollobas estimate of Poisson distributions holds. It is clear that for very long cycles the distribution is different [?] . The distribution of Hamiltonian cycles is known [?]  . At the other extreme, for very short cycles the Poisson distribution is a very good estimate. Recently McKay, Wormald, Wysocka examine this problem [?]  and gave a very detailed estimate for a more general problem. We will modify part of their results to suit our needs. In particular, their result covers the distribution of non-intersecting cycles. We will allow a very limited intersection, namely we allow for two cycles to touch once. In this case we can easily “pull” the corresponding path apart on the surface and thus the resulting geodesic on S C ( Γ , O )   will be non-itersecting. Note that allowing more then one component in the intersection of two cycles will result in counting some geodesics more then once, as seen in  3 .

Figure 3 : We cannot allow two intersections.

We use the following to determine how long cycles may be so that the probability that the intersection of any two cycles will have two or more components goes to 0 as n → ∞   .
Theorem 3.4. Let K   be a cubic graph, and C ∇   be the collection of all cycles of length r   in K   , with 3 ≤ r ≤ α   . Let C ⊂ C ∇ × C ∨   , s ≤ r   , be all pairs of cycles ( C 1 , C 2 )   with C 1 ∩ C 2 ≠ ∅   and C 1 ≠ C 2   . In addition, suppose that the number of components p   in C 1 ∩ C 2   is at least 2. Given a cubic graph Γ   with n   vertices,
∑ ( C 1 , C 2 ) ∈ C P ( C 1 ⋃ C 2 ⊆ Γ ) ≤ O ( 1 ) ∑ j ≥ 1 , p ≥ 2 ( 2 α 3 ) p − 1 ( p − 1 ) ! 2 n r + s − p − j ( 2 n ) r + s − j (5)
where j   is the number of edges in C 1 ∩ C 2   .
  • Proof. Follows directly from formula 2.7 in ([?] ).
Summing for all pairs r , s ≤ α   , and assuming that α   is chosen so that α 3 = o ( n )   , we find that the probability that any cycle of length less than α   has intersection with more than one component with a different cycle also of length less than α   is
O ( 2 2 α − 1 n 2 ) (6)
If we choose α   so that 2 2 α − 1 = o ( n 2 )   then this probability will go to zero as n → ∞   . Thus,
2 2 α − 1 = o ( n 2 ) ⟹ (7)
2 2 α − 1 = n 2 − ε (8)
2 α − 1 = ( 2 − ε ) log 2 n (9)
α = ( 1 − ε ′ ) log 2 n (10)

4 Lengths of Geodesics

We consider cycles of length N   in the graph, and the geodesics on the surface associated with each cycle. The length of the geodesic associated to any given cycle can be computed using ( 4 ). Clearly these lengths will depend upon the orientation of the vertices, and for cycles of length N   there are 2 N   possible orientations.
We need to understand the distribution of the lengths of the associated geodesics.
We begin by considering the expected value and the distribution for the traces of the matrices M P   from ( 3 ), where the paths P   are some random set of paths of length N   . We will do this by considering the individual matrix entries. Let M P ( i ) = W 1 W 2 . . . W i   with i ≤ N   , and M P ( 0 ) = I d   , the 2 × 2   identity matrix. If M P ( i ) = ( a b c d ) ,   then M P ( i + 1 )   is either ( a + b b c + d c )   or ( a a + b c c + d ) .   Consider the top row of M P ( i )   . At step i = 0   it is ( 10 )   , and thus 1 and 0 are the only values possible for either entry. At step i = 1   , the top row is either ( 10 )   or ( 11 )   , and as i   continues to increase, it is clear that the possible values are values from the previous step, or sums of neighboring values from the previous step.
Thus, we can build a table of possible values for matrix elements by starting with 1 and 0, putting the sum 1 in between, then putting the sums 2 and 1 in the new spaces, . . .
1 ⋯ 2 ⋯ 1 ⋯ 1 ⋯ 0 (11)
After i   steps we have a sequence with 2 i + 1   entries. This sequence is one example of a Stern sequence ([?, ?, ?, ?] ). Stern sequences have many nice properties, and the moments at any step i   can be computed directly. For example, each term, except for the initial terms a   and b   , shows up as part of two new terms in the next sequence, so if S ( i )   is the sum of terms at step i   , then S ( i + 1 ) = 3 S ( i ) − ( a + b )   .
Stern sequences, in the guise of the Stern-Brocot tree also show up in the work of Viswanath ([?] ) on random Fibonacci sequences, where he considered random products of the matrices A = ( 0 1 1 1 ) B = ( 0 1 1 − 1 ) .   We need only consider values of diagonal elements of M P ( i )   . At any given step, one diagonal element will change and the other will not, so it is clear that we need to understand both the distribution of the diagonal elements and the dependence between them to determine the distribution of values of the trace. The rows of the matrix associated with a path P   will be generated by Stern sequences starting with ( 10 )   and ( 01 )   , which we denote S u   and S l   . . These are simply reflections of each other, and we omit the leading (or trailing) zero from the sequence. Counting from i = 0   , we see that the sum of elements is S ( i ) = ∑ j = 1 i − 1 3 i + 2 ,   while the number of elements N ( i ) = 2 i   , hence the expected value at step i   is
E i = ( ∑ j = 1 i − 1 3 i + 2 2 i ) = 3 i + 1 2 i + 1 (12)
We can compute the variance σ i 2   by determining the sum of the squares of the elements in the sequence, S 2 ( i )   , as follows ([?] ). Consider three neighboring terms in the sequence x j + x j + 1 x j + 1 x j + 1 + x j + 2 .   Setting A ( i ) = ∑ j = 1 2 i x j 2   and B ( i ) = ∑ j = 1 2 i x j x j + 1   one gets the recurrence relations
A ( i + 1 ) = 3 A ( i ) + 2 B ( i ) − 2 (13)
B ( i + 1 ) = 2 A ( i ) + 2 B ( i ) − 2 (14)
⟹ A ( i ) = 5 A ( i − 1 ) − 2 A ( i − 2 ) − 1 (15)
A messy but straightforward computation gives A ( i ) = 2 − x − 1 ( 172 x ( − 5 + 17 ) + ( 5 + 17 ) x ( − 34 + 6 17 ) + ( 5 − 17 ) x ( − 51 + 11 17 ) ) 17 ( − 5 + 17 )   using A [ 1 ] = 2   , A [ 2 ] = 7   . Similar calculations give the sums of n   th powers of terms of the sequence. Thus we can compute any central moments of our Stern sequence, and the distribution of diagonal matrix entries.
We must convert our knowledge of the moments of the diagonal entries into information about their sum. Since means are additive, we can compute the mean value of the trace using ( 12 ),
E T r , i = 2 ( ∑ j = 1 i − 1 3 i + 2 2 i + 1 ) = 3 i + 1 2 i (16)
Clearly a dependence exists between the value of the upper diagonal and lower diagonal elements x u   and x l   . Hence, determining the variance of the traces will require a computation of the covariance of the Stern Sequences for the upper and lower diagonal elements. The covariance can be computed using
C o v ( S l , S u ) = < s l s u > − < S l > < S u > (17)
where < >   indicates the expected value. Equation ( 12 ) gives us the second term, so we need to compute the mean of products of associated elements in the two sequences, in other words the product of the diagonal entries for each matrix M P   corresponding to paths of length i   .
We compute the product of diagonal matrix elements using the diagram in Figure  4 , which follows directly from an investigation of the matrices. After an initial choice of either ℒ   or ℛ   , the diagonal product is 1. Each number in a given row will generate two children, corresponding to a choice of ℒ   or ℛ   . We determine the value of the children using two simple rules. If the path to the child is a continuation of a previous path from higher in the diagram, we add the same value that was previously added, otherwise we add the parents value to its' siblings, subtract one, and that becomes the addend for the new direction. The outer edges of the tree have addends of zero, which correspond to paths containing only ℒ   and only ℛ   .

Figure 4 : Computing the products of corresponding elements of the Stern sequence.

As in the computation for the sums of squares, we get a recurrence relation
C ( i + 1 ) = 5 C ( i ) + 2 C ( i ) − 2 i − 1 (18)
where C ( i ) = ∑ i = 1 2 i x u , i x l , i   and C ( 1 ) = 2   , C ( 2 ) = 6   . Thus,
C ( x ) = 1 17 2 − x − 2 ( 172 2 x + 1 − ( − 17 + 17 ) ( 5 + 17 ) x + ( 5 − 17 ) x ( 17 + 17 ) ) (19)
Substituting equations ( 12 ) and ( 19 ) into ( 17 ) gives
C o v a r i a n c e = 17 ( − 1 + 2 2 x + 1 − 2 ( 3 x ) − 9 x ) − ( − 17 + 17 ) ( 5 + 17 ) x + ( 5 − 17 ) x ( 17 + 17 ) 17 ( 4 x + 1 ) (20)
Looking at a plot of ( 20 ) in Figure  5 , we see that while for short cycles there is a negative correlation between the diagonal elements, this quickly changes over to a positive one. In fact, we can compute the correlation between the two diagonal matrix entries, and see that lim n → ∞ C o r = 51 − 11 17 34 − 6 17 ≃ . 61  

Knowledge of the covariance for the upper and lower diagonal elements of the matrices allows us to compute the variance for the traces, which gives us a basic understanding of the distribution of traces for cycles of length N   .
V a r i a n c e = 4 − x ( − 1 + 2 x − 23 x + 4 x − 9 x + ( 5 − 17 ) x + ( 5 + 17 ) x ) (21)
Unfortunately, the lengths of geodesics on the surface corresponding to the given cycles is determined using ( 4 ),
L e n g t h ( γ ) = 2 cosh − 1 ( T r 2 ) = 2 ln ( T r + T r 2 − 1 2 ) . (22)
When one has two independent random variables related by some function Y = f ( X )   , the standard technique used to deduce information about the distribution of the Y   's given information about the distribution of the X   's is to use a Taylor approximation, and evaluate at the expected value of X   , E ( X )   .
Y ≈ f ( c ) + f ′ ( c ) ( X − c ) + f ′ ′ ( c ) ( X − c ) 2 2 L e t c = E ( X ) ⟹ (23)
Y = f ( E ( X ) ) + f ′ ( c ) ( X − E ( X ) ) + f ′ ′ ( E ( X ) ) ( X − E ( X ) ) 2 2 . (24)
One can now approximate E ( Y )   using ( 24 ). The second term disappears, and since in the case we are considering f ( X ) ≈ ln ( x )   , the third term gives roughly − V a r ( X ) E ( X ) 2   which approaches − ∞   exponentially. Thus, we get no lower bound even for the mean of the lengths as n   increases.
The following Lemma, which follows directly from the arithmetic geometric mean inequality, shows that the means of the lengths cannot be growing any faster than linearly in n   .
Lemma 4.1. For a positive random variable X   E ( log ( X ) ) ≤ log ( E X )  
We need to give a lower bound for the growth of the lengths. The following proposition shows that the lower bound is also linear.
Theorem 4.1. The proportion of the standard Stern sequence which is growing exponentially in N   as N → ∞   approaches 1.
  • Proof. First, recall that any pair of neighbors in the N   th Stern sequence represents a row in ℳ P ( N )   . Next, note that in ℳ P ( 1 )   one row must be ( 1 , 1 )   , without loss of generality we will assume that this is the bottom row. Thus, at the expense of one step, we can consider the growth of the standard Stern sequence beginning with 11   , which contains 2 k   pairs after k   steps.
    We may now consider a Bernoulli process defined as follows: for any pair in the k   th Stern sequence, consider the four pairs which are its' children in the k + 2   nd Stern sequence. These come from the four choices of turns possible, ℛ ℛ   , ℛ ℒ   , ℒ ℛ   , and ℒ ℒ   . Since we are considering the trace of ℳ P   , we need only consider the right element in each pair. If our initial pair is a b   , we must consider two possibilities, a > b   or a < b   . The possibility that a = b   will only occur in the last pair, which has vanishing probability.
    In Figure ( 6 ), we see that the four possible values for the diagonal element are 2 a + b   , a + b   , a + 2 b   , and b   . If a < b   , then one of the four is double the original diagonal element b   , while if a > b   , three of the four are double the original.
    As N → ∞   , the probability that a < b   and a > b   approach 50%. Thus, defining success for our Bernoulli process as a doubling, the probability of success is 1 / 2 − ε ( N )   , with lim N → ∞ ε = 0   .

    Considering paths of length N = 2 k + 1   , the Bernoulli process will have k   steps. As N → ∞   , the mean will approach N / 2   and the probability that there will be at least k   successes will approach one. Therefore the probability that any entry in the n   th Stern sequence is at least 2 k   approaches 1 as N → ∞   .
Keeping better track of the minimal growth using a table like Figure  6 allows us to give a numerical estimate for the lower bound on the growth rate. For example, if b < a   , then of four choices for the second term in a pair of Stern sequence entries, two have at least tripled ( 2 a + b   and b + 2 a   ). One then has a multinomial process, and if the number of steps corresponding to a single trial is allowed to increase, the lower bound also increases.
Allowing five steps, one calculates that a lower bound for the growth factor of almost every element is given by 2 37 / 320 3 1 / 16 5 3 / 80 7 1 / 40 11 1 / 80 13 1 / 160 ≈ 1.35502 .   Such calculations quickly get too long to do by hand, and the return on investment becomes minimal since the mean is growing like 1.5 N   . A simple Mathematica routine can push the calculations significantly farther, however; for example if the basic step size is 15, then the growth factor is approximately 1.43925   . Combining this with ( 22 ) and Lemma  4.1 , we get
Theorem 4.2. As N → ∞   , the expected value of the length of the simple closed geodesics associated to cycles of length N   , E N ( l )   , is bounded by ( log 1.43925 ) N ≤ E N ( l ) ≤ ( log 1.5 ) N .  

5 The Length of the Shortest Geodesic

In this section we will use the results from previous section to estimate the length of the shortest closed geodesic on S C ( Γ , O )   . The length of the shortest closed geodesic is an important geometric invariant since it is twice the injectivity radius. Let s y s t ( S C ) ( Γ , O )   be length of the shortest closed geodesic on S C ( Γ , O )   , we will show that :
Theorem 5.1. 2.809 ≤ s y s t ( S C ) ( Γ , O ) ≤ 3.085  
It is interesting to compare this result in [?]  with the the behavior of the largest embedded ball on ( S C ) ( Γ , O )   which gives a linear growth to the largest embedded ball.
We will start with the upper bound. As we have seen on a random graph the distribution of short cycles is independent on the size of the graph and it is Poisson distribution with mean λ = 2 k 2 k   where k   is the length of the cycle. Therefore the probability of not having a k   cycle is e − 2 k 2 k   and the probability of having at least one k   -cycle on the graph is ( 1 − e − 2 k 2 k )   .
As we transition from the graph Γ   to the compact surface S C ( Γ , O )   , by Lemma  3.1 there are only 2 orientations that will make the curve that corresponds to a cycle null homotopic. Hence the probability that there is a k   -cycle that gives rise to non trivial geodesic on S C ( Γ , O )   is p ( k ) = 2 k − 2 − 1 2 k − 2 ( 1 − e − 2 k 2 k )   , and the probability that there is no k   -cycle that produces a geodesic on S C ( Γ , O )   will be ( 1 − p ( k ) )   . The expected value for the trace of a k   cycle is t r ( k ) 3 k + 1 2 k   and the expected value for the length of the geodesic is bounded from above by by 2 cosh − 1 ( t r ( k ) 2 )   .
E ( s y s t ( S C ) ( Γ , O ) ) ≤ ∑ k = 3 ∞ ( p ( k ) k − 1 ∏ j = 2 ( 1 − p ( j ) ) ) 2 cosh − 1 ( 3 k + 1 2 k + 1 )   = ∑ k = 2 ∞ ( 2 k − 2 − 1 2 k − 2 ( 1 − e − 2 k 2 k ) k − 1 ∏ j = 2 ( 1 − 2 j − 2 − 1 2 j − 2 ( 1 − e − 2 j 2 j ) ) ) 2 cosh − 1 ( 3 k + 1 2 k + 1 )   It is easy to see that this series converges rapidly and we can get a numerical estimate that the value is ∼ 3.085   To get a lower bound we can replace log E ( t r ( M ) )   by E ( 2 cosh − 1 ( t r ( M ) 2 ) )   and use the rapid decay for the probability that a graph has large girth. We calculate ∑ k = 2 2 0 ( 2 k − 2 − 1 2 k − 2 ( 1 − e − 2 k 2 k ) k − 1 ∏ j = 2 ( 1 − 2 j − 2 − 1 2 j − 2 ( 1 − e − 2 j 2 j ) ) ) E ( 2 cosh − 1 ( M 2 ) )   and get the estimate of 2.809   .