CUTTING SEQUENCES FOR GEODESIC FLOW ON THE MODULAR SURFACE AND CONTINUED FRACTIONS

DAVID J. GRABINER AND JEFFREY C. LAGARIAS

Abstract. This paper describes the cutting sequences of geodesic flow on the modular surface ℌ/P SL(2, ℤ) with respect to the standard fundamental domain F = \{z = x + iy : −\frac{1}{2} ≤ x ≤ \frac{1}{2} and |z| ≥ 1\} of P SL(2, ℤ). The cutting sequence for a vertical geodesic {θ +it : t > 0} is related to a one-dimensional continued fraction expansion for θ, called the one-dimensional Minkowski geodesic continued fraction expansion, which is associated to a parametrized family of reduced bases of a family of 2-dimensional lattices. We show that the additive ordinary continued fraction expansion of θ can be computed from the cutting sequence for a vertical geodesic by a finite automaton. In the reverse direction, the cutting sequence for a vertical geodesic cannot be computed from the additive continued fraction expansion using any finite automaton, but can be computed by a Turing machine in quadratic time using linear space. The set of cutting sequences for all geodesics forms a two-sided shift in a symbol space {L̄, R̄, J̄} which has the same set of forbidden blocks as for vertical geodesics. We show that this shift is not a sofic shift, and that it characterizes the fundamental domain F up to an isometry of the hyperbolic plane ℌ.