Decreasing height along continued fractions
Giovanni Panti


plain



Decreasing height]Decreasing height

along continued fractions

]Giovanni Panti
Department of Mathematics

University of Udine

via delle Scienze 206

33100 Udine, Italy
giovanni.panti@uniud.it


The fact that the euclidean algorithm eventually terminates is pervasive in mathematics. In  the language of continued fractions, it can be stated by saying that the orbits of rational points under the Gauss map x↦ x-x eventually reach zero. Analogues of this fact for Gauss maps defined over quadratic number fields have relevance in the theory of flows on translation surfaces, and have been established via powerful machinery, ultimately relying on the Veech dichotomy.
In this paper, for each commensurability class of noncocompact triangle groups of quadratic invariant trace field, we construct a Gauss map whose defining matrices generate a group in the class; we then provide a direct and self-contained proof of termination.
As a byproduct, we provide a new proof of the fact that noncocompact triangle groups of quadratic invariant trace field have the projective line over that field as the set of cross-ratios of cusps.

Our proof is based on an analysis of the action of nonnegative matrices with quadratic integer entries on the Weil height of points. As a consequence of the analysis, we show that long symbolic sequences in the alphabet of our maps can be effectively split into blocks of predetermined shape having the property that the height of points which obey the sequence and belong to the base field decreases strictly at each block end.
Since the height cannot decrease infinitely, the termination property follows.


2010 Math. Subj. Class.: 11A55; 37P30.

[
    [
    December 30, 2023
=====================





§ INTRODUCTION


The ordinary continued fractions algorithm and its variants (Ceiling fractions, Centered, Odd, Even, Farey, …, see <cit.>) can be seen as the action of a Gauss map on an interval in ^1. Here, by a Gauss map we mean a piecewise-projective map T, all of whose pieces have the form T(x)=ax+b/cx+d for some matrix abcd in the extended modular group _2^±, extended referring to the fact that matrices of determinant -1, as well as +1, are allowed.
As remarked in <cit.>, this setting has two natural generalizations, obtained by replacing _2^± either with _n^± (multidimensional continued fractions, <cit.>, <cit.>), or with the extended Hilbert modular group _2^± for some totally real ring of algebraic integers ; in this paper we are concerned with the latter.

Given a c.f. algorithm, that we identify with the corresponding map T, 
we define Γ^±_T as the subgroup of _2^± generated by the matrices defining T. Algorithms generating the same group —or, more generally, commensurable groups— should be considered close cousins. As maps conjugate by a projective transformation can be identified, commensurability is to be intended in the wide sense: two subgroups Γ,Γ' of _2^± are commensurable if there exists C∈_2^± such that CΓ C∩Γ' has finite index both in CΓ C and in Γ'.
Since a certain degree of rigidity is required, we have restrictions on the allowed Γ^±_T's. 
One such restriction is the requirement that any unimodular interval (see <ref> for definitions) be mapped to any other in at least one and at most two ways, one of them being order-preserving and the other order-reversing.
Other restrictions arise —although we do not actually use flows in the
present work— from the desire of preserving the classical connection between c.f. and flows on the modular surface <cit.>, <cit.>. We then make the standing assumption that 
Γ^±_T acts on the hyperbolic plane  in a properly discontinuous way, and that the resulting fuchsian group
Γ_T=Γ^±_T∩_2 be of the first kind.
We will see in Theorem <ref> that this assumption yields, as a side effect, that points are uniquely defined by their symbolic orbits.

When Γ_T has invariant trace field  (see <ref> for definitions), then it is commensurable with _2; this is the arithmetic case, which is well understood. In this paper we take advantage of the recent classification <cit.> of hyperbolic triangle groups in terms of their arithmetic dimension (namely, the number of split real places of the associated quaternion algebra) to introduce continued fractions with good properties for every commensurability class of noncocompact triangle groups of arithmetic dimension 2. In <ref>, after a brief review of basic concepts and notation, we apply Margulis's rigidity theorem to refine the classification in <cit.> to a classification into commensurability classes. It turns out that the set of 16 noncocompact triangle groups of arithmetic dimension 2 is split into 4 subsets according to the invariant trace field
F_2∈(√(2)),(√(3)),(√(5)),(√(6)),
and further split into 9 commensurability classes.
In <ref> we introduce a c.f. algorithm for each of these classes. Our algorithms extend previous work; the algorithm for the class containing the Hecke group Δ(2,8,∞) coincides with the octagon Farey map in <cit.>, <cit.>, which in turn is a “folded version” of the map in <cit.>.
In <cit.> continued fractions —different from ours— generating the groups Δ(3,m,∞) (which are related to the Veech surfaces in <cit.>, <cit.>) are introduced; these triangle groups are 2-arithmetic precisely for m=4,5,6.

Let T be one of our algorithms.
The following is an informal version of the good property referred to above; we will formulate a precise version in Theorem <ref>.


  (H) All entries of all matrices defining T are in the integer ring of the invariant trace field F_2 of the commensurability class of Γ_T. The T-symbolic orbit of every α∈ F_2 can be split into 
finite blocks of predetermined shape having the property that the  height of 
the points in the T-orbit of α
decreases strictly at each block end. This block-splitting process stops only when the symbolic orbit of a parabolic fixed point is reached.

Since by the Northcott theorem <cit.> the height of points cannot decrease infinitely, property (H) implies that the T-orbit of any point of F_2 must end up in a parabolic fixed point.
This fact is far from granted; in <cit.> it is proved that it cannot hold for the Hecke groups Δ(2,m,∞) unless the degree of the invariant trace field is 1 or 2 (see also the beginning of <ref> of the present paper), and it is conjectured that the same degree restriction holds for every Veech group. Note that a finitely generated nonelementary fuchsian group can be realized as a Veech group only if its trace and invariant trace fields coincide <cit.>.

Property (H) can be seen from various points of view; from the geometric side it implies that all points of F_2 are cusps of Γ_T (see Theorem <ref>), while from the dynamical side it means that all directions of vanishing SAF invariant are parabolic (see <cit.> for definitions and references). These facts are known in degree 2, but the proofs are involved. The geometric fact was proved in <cit.> for the specific case of the Hecke groups Δ(2,m,∞) (m=5,8,10,12), and the dynamic fact in <cit.>, making crucial use of the Veech dichotomy <cit.>; this is indeed the approach used in <cit.>. Our proof is direct, algorithmic and self-contained, making no appeal to the Veech dichotomy.

In <ref> we briefly review the basics of the Weil height. Then, in Theorem <ref>, we characterize the matrices
A∈_2^± ( being the integer ring of a real quadratic field K) which increase strictly the height of all points of K contained in a given interval.
In <ref> we introduce the notion of decreasing block, and use it to formulate property (H) in a precise way. In the final Theorem <ref> we prove that indeed all the algorithms introduced in <ref> satisfy property (H).



  §.§.§ Acknowledgments
 The main idea behind Theorem <ref> was suggested to me by Umberto Zannier, whom I very sincerely thank. I also thank John Voight for a clarifying discussion on the results in <cit.>, and the referee for the detailed reading and valuable suggestions. Some of the pictures and a few computations are done through SageMath.




§ TRIANGLE GROUPS AND COMMENSURABILITY


A matrix A=abcd∈^±_2 acts on z∈^1 in the
standard way: A*z equals az+b/cz+d if (A)=1, and equals 
az̅+b/cz̅+d if (A)=-1. We use square brackets for matrices to emphasize that we are actually considering their classes in the projective group.
The above action preserves the upper-half plane  and its boundary ^1.

The trace field of a fuchsian group Γ is the field F_1=([Γ]) generated over the rationals by the traces of the elements of Γ.
An element A∈Γ is parabolic if its trace has absolute value 2; every α∈^1 fixed by a parabolic element of Γ is a cusp of Γ. Two fuchsian groups intersecting in a subgroup of finite index in both have the same set of cusps (of course, the two groups may partition this common set of cusps in group orbits in different ways).
Fuchsian groups of finite covolume are automatically
of the first kind, geometrically finite and finitely generated; see <cit.> for definitions and proofs.


We let K be a totally real number field of degree d≥1, with ring of algebraic integers . We denote by Γ^± any subgroup of 
the extended Hilbert modular group
^±_2 such that:


  (i) Γ^± acts on  in a properly discontinuous way (i.e., for each point α and each compact C the set of elements of Γ^± mapping α to C is finite);

  (ii) the fuchsian group Γ=Γ^±∩_2 is of finite covolume and has trace field K;

  (iii) 0, 1, ∞ are cusps of Γ.



A Γ^±-unimodular interval is an interval
in ^1 which
is the image A*I_0 of the base unimodular interval I_0=[0,∞] under some element A of Γ^±.
Intervals are ordered “counterclockwise” with respect to the natural cyclic order of ^1 (the one obtained by looking at ^1 as the boundary of the Poincaré disk).
A Γ^±-unimodular partition of I_0 is a finite family I_1,…,I_r (with r≥2) of unimodular intervals such that I_0=⋃_1≤ a≤ rI_a, distinct I_a intersect at most in a common endpoint, and the set of endpoints other than ∞ generates K as a vector space over . 
Unimodular partitions are always numbered in accordance with the above order, so that 0∈ I_1, ∞∈ I_r, and I_a shares a common endpoint with I_a+1, for 0≤ a<r.
Whenever Γ^± is clear from the context, we say just unimodular interval and unimodular partition.




  * The only element of Γ^± that fixes I_0 setwise and fixes 0,∞ pointwise is the identity. Γ^± may or may not contain an element that fixes I_0 setwise and exchanges 0 with ∞; if it does, then the element is unique and has the form αα (blank entries standing for 0), which acts on  as a reflection (i.e., Möbius inversion) through the geodesic connecting -α with α.

  * If Γ^± contains a reflection as above then, for each pair U,V of unimodular intervals, Γ^± contains precisely two elements mapping U to V, one of them being order-preserving and the other order-reversing. If Γ^± does not contain such a reflection, then each unimodular U can be mapped to each unimodular V by precisely one element of Γ^±.



Let A∈^±_2 be a matrix that fixes I_0 setwise. If it fixes 0 and ∞, then it is of the form αα for some α>0. Therefore, if A belongs to Γ^±, then it belongs to Γ; since ∞ is a cusp of Γ, we have
α=1.
On the other hand, if A exchanges 0 and ∞ then it must fix some 0<α<∞, and it readily follows that A=αα. If Γ^± contains ββ as well, then Γ contains 
αβαβ and, by the above, α=β.
This proves (1), and (2) is an easy consequence.


We can now make precise our definition of continued fraction algorithm, which we identify with a Gauss map.


Let K,d,,Γ^± be as in Notation <ref>, and let A_1,…,A_r∈Γ^± be such that:


  (iv) the family of intervals I_a=A_a*I_0, for a=1,…,r, is a unimodular partition of I_0;

  (v) A_r=+1.

The slow continued fraction algorithm determined by A_1,…,A_r is the Gauss map T:I_0→ I_0 which is induced on I_a by A_a (by convention, the endpoint in I_a∩ I_a+1 is mapped using A_a). The maps A_a are the pieces of T.
If d=2 (respectively, d=3), then we say that T is
quadratic (cubic).
We denote by Γ^±_T the subgroup of Γ^± generated by A_1,…,A_r, and we let Γ_T=Γ^±_T∩_2.


The two restrictions in Definition <ref> —about the determinant of A_r and the definition of T at endpoints— simplify some of the proofs and are essentially irrelevant. Indeed, ambiguity at endpoints may occur at most once along the T-orbit of a point, and is analogous to the existence of two finite ordinary c.f. expansions for rational numbers.
On the other hand, requiring A_r=+1 amounts to requiring that ∞ be a fixed point for T. This can always be achieved, either by replacing T with T^2 if A_r=-1= A_1, or by conjugating T with x↦ x if A_r=-1=- A_1.

As assumed in Notation <ref> (and already used in the proof of Lemma <ref>), the point ∞ is a cusp of Γ, and thus an indifferent fixed point of T.
This forces any T-invariant measure absolutely continuous with respect to Lebesgue measure to be infinite, and gives poor approximation properties to the convergents; hence the adjective “slow” in Definition <ref>. One remedies this by accelerating the algorithm (i.e., considering the first-return map to some subinterval of I_0); note that the acceleration process leaves Γ^±_T unaltered <cit.>. 
Since we are concerned only with the eventual orbits of points, we do not need any acceleration.


The group Γ_T^± has finite index in Γ^±, and hence so does Γ_T in Γ.


By our assumptions Γ^± has a fundamental domain of finite hyperbolic area; it is then sufficient to show that the same holds for Γ^±_T. 
Let ^+=z∈: z≥0. For every a∈1,…,r we have

    A_a*^+⊂^+  and  =⋃A_a^k*^+:k∈.

Therefore ^+∖(A_a*^+) is a fundamental domain for the infinite cyclic group generated by A_a, and this implies that =^+∖⋃A_a*^+:1≤ a≤ r contains a fundamental domain for the action of Γ^±_T.
Let 0=α_0<α_1<⋯<α_r=∞ be the points determining the unimodular partition I_1,…,I_r. Then  is bounded by the full geodesics g_0,g_1,…,g_r, where g_i is the geodesic having endpoints α_i-1 and α_ir+1 (see the thickly bordered region in Figure <ref> (left)).
By elementary considerations  has finite hyperbolic area, and our claim follows.


We note as an aside that in the case Γ^±=^±_2 Lemma <ref> has a sharper formulation: for every T, the index of Γ^±_T in ^±_2 is bounded by  8 <cit.>.

We now specialize to the case in which Γ^± is an extended triangle group.
Let 2≤ l≤ m≤ n≤∞ be integers such that 1/l+1/m+1/n<1; then there exists a triangle in , unique up to isometry, having angles π/l,π/m,π/n. The group generated by reflections in the sides of this triangle is the extended triangle group Δ^±(l,m,n)<^±_2, and its index-2 subgroup of orientation-preserving elements is the triangle group Δ(l,m,n), which is a fuchsian group of cofinite volume.
Clearly the original triangle is a fundamental domain for Δ^±(l,m,n); we will call it the fundamental triangle.
Let T be a Gauss map obtained from Δ^±(l,m,n) via the construction in Definition <ref>. As remarked above, our assumptions imply that Γ_T contains parabolic elements, and thus at least one of the vertices of the fundamental triangle must lie at infinity. Therefore, n equals ∞ and Δ(l,m,∞) is not cocompact. 


Consider the group Δ^±(4,∞,∞) and fix as fundamental triangle the one with
vertices 0, ∞, and (1+itan(π/8))/2.
The matrices expressing reflections in the triangle sides are
(see Figure <ref> (left))

    J=[ -1   ;     1 ],  
    P=[ -1  1;     1 ],  
    M=[      1       ; 2+√(2)     -1 ].

Postcomposing J first with M, and then with powers of the counterclockwise rotation MP (of order 4), we obtain matrices A_1,…,A_7 as follows:

    A_1=MJ=[      1      0; 2+√(2)      1 ],  
    A_2=(MP)J=[      1      1; 2+√(2) 1+√(2) ],
    
    A_3=(MP)MJ,  
    A_4=(MP)^2J,  
    A_5=(MP)^2MJ,  
    A_6=(MP)^3J,
    
    A_7=(MP)^3MJ=(MP) MJ=PJ=[ 1 1;   1 ].

The corresponding unimodular partition is 

    0<1-1/2√(2)<-1+√(2)<1/2<2-√(2)
    <1/2√(2)<1<∞.

The matrices A_1,A_2,A_7 clearly generate Δ^±(4,∞,∞), which then equals Γ_T^±; of course K=(√(2)), d=2, =[√(2)].
We draw in Figure <ref> (left) the fundamental triangle, its M-image (the union of the two is a fundamental domain for Δ(4,∞,∞)), and the images of both under successive powers of MP.
The image in the unit disk of the
region ^+∖⋃A_j*^+:1≤ j≤ 7
of Lemma <ref> is bordered by thick geodesics.
We also draw in Figure <ref> (right) the resulting map T which equals, up to a conjugation, the octagon Farey map in <cit.>, <cit.>; indeed, setting E=1-√(2)12 and i=1,…,7, the matrix γν_i of <cit.> is E A_i E.
Note that, since we want ∞ to appear as an ordinary point, here and elsewhere
we draw the hyperbolic plane in the disk model via the Cayley map
2^-1/21-i-i1.
For the same reason, the graph in Figure <ref> (right) is actually the graph of the conjugate of T under the projective transformation
111:[0,∞]→ [0,1].


We remark that Δ^±(4,∞,∞) does not contain elements of the form 
αα (otherwise the fundamental triangle would not be a fundamental domain) and therefore, by Lemma <ref>, the pieces of T are uniquely determined by the intervals. In other words, the only matrix in (this specific embedding of) Δ^±(4,∞,∞) that maps I_a to I_0 is A_a. Thus, we cannot avoid pieces with negative slopes; if we insist on having all pieces in Δ(4,∞,∞) we must necessarily unfold the map, as in the original construction in <cit.>.


We need more vocabulary.
Let Γ be a fuchsian group of finite covolume, and let Γ^2 be the subgroup generated by the squares of the elements of Γ; since Γ is finitely generated, Γ^2 is a normal subgroup of finite index.
The invariant trace field of Γ is the trace field F_2 of Γ^2; of course it is a subfield of the trace field F_1 of Γ. Both F_2 and the invariant quaternion algebra F_2[Γ^2] are invariants (although not complete) of the commensurability class of Γ <cit.>.

If Γ=Δ(l,m,n) then F_1, F_2, and F_2[Γ^2] can be easily computed. Let λ_l=2cos(π/l), and analogously for m and n (λ_∞=2); then

    F_1=(λ_l,λ_m,λ_n),  
    F_2=(λ_l^2,λ_m^2,λ_n^2,λ_lλ_mλ_n).

In the noncocompact case n=∞ —which is the one concerning us— the algebra F_2[Γ^2] always equals _2F_2 (because
Γ^2 contains a parabolic element, whose difference with the identity is nilpotent). In the cocompact case F_2[Γ^2] is given by the Hilbert symbol <cit.>

    (
    λ_m^2(λ_m^2-4), λ_m^2λ_n^2
    (λ_l^2+λ_m^2+λ_n^2+λ_lλ_mλ_n-4)/F_2).

Each archimedean place σ:F_2→ yields a real quaternion algebra F_2[Γ^2]⊗_σ, which necessarily equals either _2 (in which case we say that σ is split) or the Hamilton quaternions. The numbers of archimedean split places is the arithmetic dimension of Γ.

In our noncocompact case, the arithmetic dimension of Γ is just the degree of F_2 over , and the list of all triangle groups of arithmetic dimension 2 could be generated by exhaustive search. Indeed, if Δ(l,m,∞) is such a group, then its invariant trace field must contain cos(2π/l), which has degree φ(l)/2 over . Thus we have the bound φ(l)≤4, 
yielding l∈2,3,4,5,6,8,10,12,
and similarly for m if different from ∞. We spare such search by 
appealing to <cit.>, which proves that the set of triangle groups, including the cocompact ones, of bounded arithmetic dimension is finite, and provides efficient algorithms for its enumeration.
In particular, <cit.> gives explicit lists of all triangle groups of low dimension: there are 76 cocompact and 9 noncocompact groups of dimension 1 (this is the arithmetic case, already settled in <cit.>) and, for dimension from 2 up to 5, the corresponding pairs of cardinalities are (148,16), (111,13), (286,31), (94,6). 

In <cit.> Takeuchi proves that in the arithmetic case the pair (F_2,F_2[Γ^2]) is a complete invariant of the commensurability class of Γ, and uses this fact to refine his own work in <cit.> to a classification of all 85 triangle groups of arithmetic dimension 1 up to commensurability.
The only noncocompact commensurability class is that of the modular group _2=Δ(2,3,∞), and it turns out that there are 18 cocompact classes. When the arithmetic dimension is greater than 1 then the pair (F_2,F_2[Γ^2]) is not complete anymore, so we apply a different strategy.


Two nonarithmetic triangle groups Γ,Δ are commensurable if and only if there exists C∈_2 and a triangle group Ξ containing both Γ and CΔ C with finite index.


By the results in <cit.>, <cit.>, the relation of inclusion among triangle groups is easily settled, so we can split
the classes in <cit.> in commensurability subclasses. In particular, the 16 noncocompact triangle groups of arithmetic dimension 2
are split according to the table in Figure <ref>. In it, the invariant trace field is displayed to the left, and a group lies over another if and only if the first one is a subgroup of the second (always of index 2). Here and later on, for short and when no confusion may arise, we tacitly suppress the initial Δ (or Δ^±) from our notation for triangle groups.



A proof is sketched in <cit.>; we supply a more detailed version for the reader's convenience. 
For the nontrivial direction, assume that Γ and Δ are commensurable.
Then, after replacing Δ with an appropriate CΔ C, we assume that Γ and Δ intersect in a subgroup of finite index in both. Therefore Γ and Δ have the same commensurator Ξ, the latter being the group of all D∈_2 such that Γ and DΓ D (respectively, Δ and DΔ D) intersect in a subgroup of finite index in both. Since we are in the nonarithmetic case, the Margulis dichotomy <cit.> implies that both Γ and Δ have finite index in Ξ; hence Ξ is fuchsian as well. But it is known that the only fuchsian groups that can contain a triangle group with finite index are themselves triangle groups (because the Teichmüller space of the larger group embeds in the space of the subgroup, and triangle groups are precisely those noncyclic fuchsian groups having trivial spaces; see <cit.>).





§ CONTINUED FRACTION ALGORITHMS


In this section we introduce, for each commensurability class in Figure <ref>, a Gauss map T as in Definition <ref> such that:


  * T is continuous (equivalently, A_a=(-1)^r-a for every a=1,…,r);

  * K is the invariant trace field of the class;

  * Γ_T is a group in the class, with the exception of the
cases (4,6,∞) and (4,12,∞), in which Γ_T has index 2 in the unique group of the class;

  * property (H) holds.

Note that the exception in (3) is unavoidable, since the invariant trace field of Δ(4,6,∞) and of Δ(4,12,∞) is strictly contained in the respective trace fields.

The integer rings of our invariant trace fields F_2=K=(√(d)), for d=2,3,5,6, are [√(2)],[√(3)],[τ],[√(6)], respectively (τ=(1+√(5))/2 is the golden ratio). All of them have class number 1; since the class group is in natural correspondence with the _2-orbits in ^1K,
this is surely necessary for all points in K to be cusps of Γ_T and hence, as remarked in <ref>, for property (H) to hold.
Note that each commensurability class in Figure <ref> contains a group whose cusps form a single group orbit.



 §.§ Case (l,m,∞)∈(2,5,∞),(3,4,∞),(3,5,∞),(3,6,∞)
 This is the simplest and most flexible case: we take as fundamental triangle the one having vertices -exp(-iπ/l), exp(iπ/m), and ∞.
Let

    F=[   1; 1   ],
      
    Q_l=[ λ_l   1;  -1     ],  
    R_m=[       1;  -1 λ_m ].

Then Q_l is a counterclockwise rotation of order l around -exp(-iπ/l), and R_m is a counterclockwise rotation of order m around exp(iπ/m). Also, Δ(l,m,∞) is a free product Q_l*R_m=Z_l*Z_m of cyclic groups, while 
Δ^±(l,m,∞) is an amalgamated product Q_l,F*_FR_m,F=D_l*_Z_2D_m
of dihedral groups. 
Let T' be the Gauss map determined by the (l-1)(m-1) matrices A'_ij=R_m^iQ_l^j, for 1≤ i<m and 1≤ j<l.
Figure <ref> (left), which is drawn for (l,m,∞)=(3,4,∞),
clarifies the definition; appropriate powers of Q_l map I_0 to  subintervals of [∞,0], and powers of R_m map back these subintervals inside I_0 (for short, in Figure <ref> we dropped the subscripts in Q_3, R_4).
All matrices A'_ij have positive determinant, so T' is not continuous and has all pieces of positive slope. Replacing any A'_ij with A'_ijF we have full flexibility in converting each slope from positive to negative. In order to obtain a continuous map we perform this matrix replacement precisely at those intervals I_1,…,I_r (r=(l-1)(m-1)) having odd index; this completely defines our final map T. 
It is easy to check that the resulting matrices A_1,…,A_r generate Δ^±(l,m,∞), and therefore Γ_T=Δ(l,m,∞). Since here λ_l equals 0 or 1, for this group the trace field agrees with the invariant trace field. The required properties (1), (2), (3) are thus satisfied; we will prove (4) in <ref>.




 §.§ Cases (l,∞,∞), for l=4,5,6

The case (4,∞,∞) has already been dealt with in Example <ref>. In order to treat all cases in a uniform way, we first prove a lemma.


Let α,β∈^*, and let 

    P_α=[ -1  α;     1 ],
        
    M_β=[  1   ;  β -1 ].

Then these matrices express the reflections of  in the geodesic g_α connecting ∞ with α/2, and the geodesic g_β connecting 0 with 2/β, respectively. Let g_0 be the geodesic connecting 0 with ∞, which is the axis of reflection of the matrix J in Example <ref>.
The three geodesics g_α, g_β, and g_0, form a hyperbolic triangle with
two vertices at infinity and another —the one at which g_α and g_β
meet— inside . Let us call the angle at this third vertex the inner angle, of measure 2π/p (we still let λ_p=2cos(π/p), even though here p might be a non-integer). We then have  
2π/p≤π/2 if and only if 2≤αβ<4; if this happens, then αβ=λ_p^2=2+λ_p/2, and the bisectrix of the inner angle is the geodesic connecting -√(α/β) with √(α/β).


The first statement is easily checked, and implies that g_α,g_β intersect iff (either 0<α/2<2/β or 2/β<α/2<0) iff 0<αβ<4. Assume that they intersect with an inner angle of 2π/p, for some 2<p. Then, by the duplication formula for cosines,
4cos^2(π/p)-2=2cos(2π/p)=(M_β P_α)=αβ-2, so that


  * either λ_p^2-2=αβ-2, i.e., 2/β=2α/λ_p^2,

  * or λ_p^2-2=-αβ+2, i.e., 2/β=2α/(4-λ_p^2).

These two cases correspond to the sign ambiguity in cos(2π/p), namely, to the inner angle being acute or obtuse. Since we want it to be acute, we must choose 2/β to be smaller in absolute value. As 2π/p≤π/2 implies λ_p^2≥2, the second case is ruled out and
αβ=λ_p^2. The last claim follows by solving for x the equation P_α=xxM_βxx.


Generalizing Example <ref>, we treat case (l,∞,∞) by using a fundamental triangle bounded by g_α,g_β,g_0, having an inner angle of π/l, and such that J,P_α,M_β∈_2^±, where  is the appropriate integer ring. According to Lemma <ref>, the ways of accomplishing this are in 1–1 correspondence with the factorization of 2+λ_l in ; since  is a unique factorization domain, there is just one way, up to conjugation by units.

For l=4, the number 2+λ_4=2+√(2) is prime in [√(2)], and the latter has 1+√(2) as fundamental unit. Hence the admissible pairs α,β are exactly, up to exchanging α with β,

    α=(1+√(2))^k,  β=(1+√(2))^-k(2+√(2)),

for k∈. In Example <ref> we just set k=0. The choice k=1 would have been slightly more symmetric, as α/β is then nearer to 1, but would have made the construction in <ref> more involved; hence we maintain k=0 for our official T.

For l=5, 2+λ_5=2+τ is prime in [τ] while, for l=6, 2+λ_6=2+√(3) is the fundamental unit in [√(3)]. We retain α=1 in both cases, and set β equal to either 2+τ or 2+√(3). Writing P for P_1, the rotation M_β P has then
order l, and T has 2l-1 pieces, with A_1,…,A_2l-1 given by

    A_1+2q=(M_β P)^qM_β J,   A_2+2q=(M_β P)^q+1J,  
    A_2l-1=(M_β P)^l-1M_β J=[ 1 1;   1 ],

for 0≤ q≤ l-2.
We still have Γ^±_T=Δ^±(l,∞,∞) and (1), (2), (3) are satisfied. Here the situation is much more rigid than in <ref>. Indeed Δ^±(l,∞,∞) does not contain any reflection of the form given in Lemma <ref>, and no flexibility is allowed in the orientation of the pieces of T.



 §.§ Cases (4,m,∞), for m=6,12

In both cases the trace field is (√(2),√(3)), which contains strictly the invariant trace fields (√(6)) and
(√(3)) (for m=6 and m=12, respectively); therefore our Γ^±_T has to be a proper subgroup of Δ^±(4,m,∞). We will use a reflection group, with fundamental domain the union of two (4,m,∞)-triangles, images of each other under a reflection in a common edge (the dashed geodesic arc in Figure <ref> (right)).

Let us first treat the case m=6; according to Lemma <ref>, we must find α,β,γ,δ∈[√(6)] such that

    αβ   =λ_6^2=3,  α,β>0,
    γδ   =λ_4^2=2,  γ,δ<0,
    α/β   =γ/δ.

In [√(6)] we have the fundamental unit ε=5+2√(6), and the unique factorizations 3=ε(3-√(6))^2, 
2=ε(-2-√(6))^2. The equations (<ref>) imply 6=(αδ)^2, so that αδ=-√(6)=(3-√(6))(-2-√(6)). Therefore the general solution of (<ref>) is

    α   =ε^k(3-√(6)),   β   =ε^-k+1(3-√(6)),
    γ   =ε^k-1(-2-√(6)),   δ   =ε^-k(-2-√(6)).

Looking for α/β=ε^2k-1 to approach 1 as much as possible, we take k=0 and set

    P_α   =[     -1 3-√(6);             1 ],
       M_β   =[      1       ; 3+√(6)     -1 ],
    
    P_γ   =[     -1 2-√(6);             1 ],
       M_δ   =[       1        ; -2-√(6)      -1 ].


Now consider the matrices

    U_1   =P_γ,   U_2   =P_γ M_δ,   U_3   =P_γ M_δ P_γ,
    
    V_1   =M_β,   V_2   =M_β P_α,   V_3   =(M_β P_α)M_β,
    
    V_4   =(M_β P_α)^2,   V_5   =(M_β P_α)^2M_β.

As in <ref>, the U_i's map I_0 to subintervals of [∞,0], and the V_j's map back these subintervals inside I_0. Few minutes of reflection show that the matrices

    A_1   =V_1U_3,   A_2   =V_1U_2,   A_3   =V_1U_1,
    
    A_4   =V_2U_1,   A_5   =V_2U_2,   A_6   =V_2U_3,
    
    A_7   =V_3U_3,   A_8   =V_3U_2,   A_9   =V_3U_1,
    
    A_10   =V_4U_1,   A_11   =V_4U_2,   A_12   =V_4U_3,
    
    A_13   =V_5U_3,   A_14   =V_5U_2,   A_15   =V_5U_1,

—which have determinant ±1, alternatively— determine a unimodular partition of I_0, whose 15 intervals are displayed along the right border of the disk model in Figure <ref> (right), starting with I_1=A_1*I_0=[0,5-2√(6)], I_2=A_2*I_0=[5-2√(6),(8-3√(6))/5], and ending with I_15=A_15*I_0=[1,∞]. 
As a consequence, the matrices A_1,…,A_15 determine a Gauss map T, and one easily checks that Γ_T^± equals P_α,M_β,P_γ,M_δ, which is an index-2 subgroup of Δ^±(4,6,∞). The conditions (1), (2), (3) are thus satisfied. The fact that Γ_T^± does not contain a reflection as in Lemma <ref> corresponds to the fact that α/β=5-2√(6) is not a square in [√(6)], but becomes a square —namely, (√(3)-√(2))^2— in the integer ring of (√(2),√(3)).

The case (4,12,∞) is analogous; we solve (<ref>) (with λ_6^2 replaced by λ_12^2=2+√(3)) for α,β,γ,δ∈[√(3)]. Now 2+√(3) is the fundamental unit ε of [√(3)], while 2=ε(1-√(3))^2. Arguing as above, the general solution to (<ref>) is α=ε^k, β=ε^-k+1, γ=ε^k(1-√(3)), δ=ε^-k+1(1-√(3)). We take k=0 and obtain the four matrices

    P_α   =[ -1  1;     1 ],
       M_β   =[      1       ; 2+√(3)     -1 ],
    
    P_γ   =[     -1 1-√(3);             1 ],
       M_δ   =[       1        ; -1-√(3)      -1 ].

The matrices U_1,U_2,U_3 are defined precisely as in the previous case, while the list of the V_j's is extended by V_6=(M_β P_α)^3, V_7=(M_β P_α)^3M_β, …, V_11=(M_β P_α)^5M_β. The products V_jU_i, in full analogy with the above, yield matrices A_1,…,A_33 and a corresponding Gauss map, for which all of the above considerations hold verbatim.




§ THE HEIGHT ON THE PROJECTIVE LINE


We recall the definition and the basic properties of the height. Let K be an extension of  of degree d. For each place P of K we denote by 
a_P the valuation in P normalized by α_P=σ(α)^e/d (if P is archimedean associated to the embedding σ:K→, with e=1 or 2 according whether σ is real or complex), and by p_P=p^-d(P|p)/d (if P is nonarchimedean lying over the rational prime p, with local degree d(P|p)=[K_P:_p]). Given α=[α_1,α_2]∈^1K, its absolute height is

    H(α)=∏_Pmax(α_1_P,α_2_P).

The number H(α) is in _≥1 and does not depend on K, nor on the representative chosen for α <cit.>.
We let  be the ring of algebraic integers in K.


Let (α_1,α_2)∈ K^2∖(0,0), let A∈_2^±, and let P be a nonarchimedean prime. Let β_1β_2=Aα_1α_2. Then max(α_1_P,α_2_P)=max(β_1_P,β_2_P).


The fractional ideals α_1+α_2 and β_1+β_2 coincide. Since P is nonarchimedean, both max(α_1_P,α_2_P) and max(β_1_P,β_2_P) are equal to the maximum of γ_P, for γ varying in that fractional ideal.


We are interested in the behavior of the height along T-orbits of points in K, where T,K are as in Definition <ref>. Let A∈^±_2; if, up to multiplication by -1, all entries of A are greater than or equal to 0, with at most one entry equal to 0, then we call A positive. If all entries are greater than 0 we call A strictly positive. Since r≥2, the matrices A_1,A_r are positive (but not strictly), while A_2,…,A_r-1 are strictly positive. When writing positive matrices, we will always tacitly assume that the displayed entries are greater than or equal to 0.

The case K= is trivial but instructive. The height of β=u/v∈^1 is uv ( denoting the max function), provided that u,v are relatively prime integers. Assume that 0<β<∞, and let A be a positive matrix in _2^±; setting α=A*β, it is then clear that H(α)>H(β).
Since the pieces of T are given by the inverse of positive matrices, 
this implies that, for every α∈^1∩[0,∞], the height of T(α) is strictly less than the height of α, unless T(α)∈0,∞. As the height is a positive integer, it cannot decrease indefinitely; hence the T-orbit of every rational point must end up in 0,∞.

By Northcott's theorem <cit.>, the number of points of bounded height in any ^1K is finite; the argument above would then work in any number field, if only the action of positive matrices in _2^± were height-increasing. However, this is not the case.


Let K=(√(6)), and consider the strictly positive matrices

    A_9=
    [       2 -1+√(6);  3+√(6)  2+√(6) ],    
    A_13=[ 1+√(6) 3-√(6); 2+√(6)      1 ],

introduced in <ref> when treating Case (4,6,∞).
The matrix A_9 is height-increasing: for every β∈ K∩[0,∞], we have H(A_9*β)>H(β); this will follow from Theorem <ref>.

On the other hand, let

    β=703-240√(6)/380,    
    A_13*β=
    403+83√(6)/346+223√(6).

We can check easily that numerator and denominator in the above expression for β are relatively prime in [√(6)], and thus we compute

    H(β)=[380(703+240√(6))]^1/2=
    700.3809⋯>H(A_13*β)=422.6795⋯.

The situation is actually worse: as we will see in Theorem <ref>, the set of points in K on which A_13 is height-decreasing is dense in [0,∞].


We now introduce our main tool. Let K be any real quadratic field with integer ring , denote by a' the nontrivial automorphism of K, and let
A=abcd∈_2^± be positive.
We define

    f(x)   =(ax+b)(cx+d)/x 1,
    
    t   =(a'+c')(b'+d')
    =a'+c'a'-c'b'+d'b'-d',
    
    E^♯   =x∈[0,∞]:f(x)>t,
    
    E^♮   =x∈[0,∞]:f(x)=t,
    
    E^♭   =x∈[0,∞]:f(x)<t.

When we will have more than one matrix around, we will use notations such as t(A),E^♯(A),f_A for clarity.


Assuming the above notation, the following statements hold.


  * f is nondecreasing on [0,1] and nonincreasing on [1,∞].

  * E^♯ is either empty, or an open interval containing 1.

  * Either E^♮ contains at most two points, or equals one of the intervals [0,1], [1,∞].

  * H(A*β)>H(β) for every β∈ E^♯∩ K; the same holds if A is strictly positive and β is a boundary point of E^♯ such that A*β≠1.

  * If E^♮ is an interval, then 
β∈ E^♮∩ K:
H(A*β)=H(β) is dense in E^♮.

  * β∈ E^♭∩ K:
H(A*β)<H(β) is dense in E^♭.



Assuming Theorem <ref>, let
us justify our claims in Example <ref>. We have

    t(A_9)=-1+√(6)<min f_A_9=f_A_9(0) f_A_9(∞)=2+√(6);

hence E^♯(A_9)=[0,∞] and the statement (4) applies.
On the other hand,

    t(A_13)=4+√(6)>max f_A_13=f_A_13(1)=3+√(6);

hence E^♯(A_13)=E^♮(A_13)=∅ and E^♭(A_13)=[0,∞], so (6) applies; see Figure <ref> (right).


Since a,b,c,d≥0, the statements (1) and (2) are clear. The function f is best visualized by precomposing it with the order-preserving homeomorphism φ:[0,2]→[0,∞] which is the identity on [0,1] and equals (2-x) on [1,2]. Then f∘φ is piecewise-linear, namely

    (f∘φ)(x)=
    (ax+b)(cx+d),   on [0,1];
    
    (-bx+a+2b)(-dx+c+2d),   on [1,2].

We have f(0)=b d, f(∞)=a c, and f(1)=(a+b)(c+d)=max f. Figure <ref> (left) shows f∘φ and t (dashed) for the matrix

    A_2A_10^9=[         1  10+9√(3);      √(3) 28+10√(3) ],

where A_2,A_10 are the matrices introduced in <ref> when treating Case (3,6,∞). The dashed vertical segments mark the intervals I_1,…,I_10 of that case. Figure <ref> (right) 
is the analogous one for the matrix A_13 of Example <ref>.


We formulate two remarks.


  * Exchanging the rows of A does not modify f and t, and corresponds to postcomposing A with the involution x↔1/x, which leaves the height invariant. On the other hand, exchanging the columns does not modify t, and transforms f(x) in f(1/x) (from the point of view of f∘φ, it is a reflection in the x=1 axis). It corresponds to precomposing A with x↔1/x; this simply exchanges E^♯,E^♮,E^♭ with their images under the involution, unaffecting our claims. 

  * The identities a'=c' and b'=d'
cannot hold simultaneously. This is clear if one of the entries of A is 0. Otherwise, assume by contradiction that A is strictly positive and both identities hold. Then we have

    1   =a'd'-b'c'
       =(a'd')a'd'-(b'c')b'c'
       =((a'd')-(b'c'))a'b',

which is impossible, since (a'd')-(b'c')∈-2,0,2 and 
a'b'≠± 1/2 (because a',b' are algebraic integers).

We therefore assume, without loss of generality, that a'<c' and that a is the only entry of A which can possibly be 0.

We prove (3). If a≠0, then f is strictly increasing on [0,1] and strictly decreasing on [1,∞]; hence E^♮ contains at most 2 points. 
Otherwise, A has the form bbd, for some unit b∈.
Since E^♮ contains 3 or more points, it contains an interval, that has necessarily the form [0,r], for some 0<r≤1; indeed, such an interval is the only region where f has derivative 0. Looking for a contradiction, we assume r<1; then

    d<b r+d=f(r)=b=t=(b)'(b'+d')<f(1)=b(b+d).

As b'=b, we obtain

    d<b=b(b+d')<b(b+d),

from which we orderly derive

    d<b<b+d,
    
    b<b+d'≤ b,
    
    b-b<d<b,
    
    -b+b≤ d'≤ b-b,
    
    -b<d-b<0,
    
    -b+b-b'≤ d'-b'≤ b-b-b'.

Now, b equals either b' or -b'; in both cases the last line in the above chain yields d'-b'≤ b. Therefore,
writing N for the norm function,
| N(d-b)|=d-b·d'-b'<b b=1; as d-b∈∖0 and the norm takes integer values, this is impossible and concludes the proof of (3).

Let now β range in K∩[0,∞).
We have Aβ1=aβ+bcβ+d; by Lemma <ref>,

    H(A*β) H(β)

if and only if

    (aβ+bcβ+d)
    (a'β'+b'c'β'+d')(β1)(β'1)

if and only if (since β,a,b,c,d≥0)

    *
    f(β)(a'β'+b'c'β'+d')β' 1.

We note that the corresponding condition for β=∞ is

    **
    f(∞)(a'c') 1.


For a given x∈[0,∞], 
we denote by g_x(y) the function of the real variable y defined by

    g_x(y)=f(x)(a'y+b'c'y+d').

Since a'<c', the
graph of g_x has a truncated V shape, with two outer halflines whose slope has absolute value f(x)c', and an inner segment whose slope has absolute value f(x)a'.
These affine linear parts are connected by two distinct cornerpoints,
which we compute by solving the systems

    f(x)a'y+f(x)b'=z
    
    f(x)c'y+f(x)d'=z
      
    -f(x)a'y-f(x)b'=z
    
    f(x)c'y+f(x)d'=z

in the variables (y,z) —say, via the Cramer rule— and then taking the absolute value of the resulting z. After the computation, the cornerpoints turn out to be

    q_1=(b'-d'/-a'+c',f(x)/-a'+c'),
      
    q_2=(-b'-d'/a'+c',f(x)/a'+c').




  
Claim Let β belong to the closure of E^♯, and let q_1,q_2 be the cornerpoints of g_β; then the following hold.


  (i) The absolute value f(β)c'
of the slopes of the outer halflines of g_β is greater than 1.

  (ii) q_1 and q_2 belong to the epigraph
of y1, namely the convex region
(y,z):y+z≥0,z≥1,-y+z≥0. If β∈ E^♯, then they belong to the strict epigraph (defined analogously, with > replacing ≥) and hence, by (i), the entire graph of g_β lies in the strict epigraph of y1.

  (iii) If a≠0 then q_1,q_2 do not lie in the same affine linear part of the graph of y1.



  
Proof of Claim (i) From the triangle inequality we get

    1=a'd'-b'c'   ≤a'd'+b'c'
       <c'(d'+b')
       ≤c't
       ≤c'f(β).


(ii) The cornerpoint q_1 belongs to the epigraph of y1
if and only if ±(b'-d')+f(β)≥0 and f(β)≥-a'+c',
and this condition amounts to f(β)≥a'-c'b'-d'. Analogously, 
q_2 belongs to the epigraph if and only if f(β)≥a'+c'b'+d'.
By our assumptions on β we have f(β)≥ t, and the above inequalities hold by definition of t. If β∈ E^♯ then f(β)<t and the inequalities are strict.

(iii) Suppose that q_1,q_2 lie on -y+z=0. Then b'-d'=f(β)=b'+d', which is impossible since b,d are both different from 0. The same argument works for the linear parts along z=1 and y+z=0. 

We now prove (4). For β=∞, the greater-than inequality in (<ref>) is just (i) in the Claim; let then β≠∞.
If β∈ E^♯ then, by (ii) in the Claim,
g_β(y)>y1 for every y∈. In particular, g_β(β')>β'1, which amounts to the greater-than inequality in (<ref>). Assume that A is strictly positive and that β is a boundary point of E^♯ with A*β≠1; then f(β)=t. By (i) and (iii) of the Claim, the graph of g_β is contained in the strict epigraph of y1, with the exception of at least one and at most two of q_1,q_2. The first coordinates of these cornerpoints are (A*1)' and (A*(-1))'. Neither of these can be β', since otherwise we would have A*β=1 —which is excluded by hypothesis— or A*β=-1 —which is impossible—. Therefore g_β(β')>β'1 holds as well and (4) is established.

We prove (5); let J⊆ E^♮=[0,1] be an interval of positive length. By the proof of (3), f has value b on J. Thus, for every x∈ J, the cornerpoints of g_x are

    q_1=(b'-d'/N(b)b,1),
      
    q_2=(-b'-d'/N(b)b,1).

Indeed, under our hypotheses, a equals 0 and b is a unit, so that c'=(b)'=(b)'bb=N(b)b=N(b)b.
Since b'-d'-b'-d'≤ t=b, the interval J' of endpoints b'-d'/N(b)b and -b'-d'/N(b)b is contained in [-1,1] and has positive length. By the Artin-Whaples approximation theorem <cit.>,
there exists β∈ K such that β∈ J and β'∈ J'. Therefore g_β(β')=1=β'1, which means equality in (<ref>) and establishes (5).

Finally, let J⊆ E^♭ be an interval of positive length; by possibly shrinking it, we find m<t such that f≤ m on J. By definition of t, either m<a'+c'a'-c' or m<b'+d'b'-d' (or both). In any case, at least one of the cornerpoints of the graph of m(a'y+b'c'y+d') is strictly below the graph of y1; in particular, there exists an interval of positive length J' such that g_x(y)<y1 for every pair (x,y)∈ J× J'. Again by the Artin-Whaples theorem, there exists β∈ K with (β,β')∈ J× J'; hence g_β(β')<β'1 and H(A*β)<H(β). This establishes (6) and concludes the proof of Theorem <ref>.





§ DECREASING BLOCKS


Let T and K be a Gauss map and a number field as in Definition <ref>. For a “generic” input α∈ K, the height along the T-orbit of α is “generically decreasing”. This is of course a vague statement, but is exemplified in Figure <ref> (left), which shows the logarithmic height (i.e., the logarithm of the height) along the first 180 points in the T-orbit of α, where


  * T is the map introduced in <ref> for the (3,4,∞) case; 
  * α is the rational number

    α=17872569142100116747518989441504411/5689015449433817447221222422292025,

whose only —as far as we know— claim to glory is being the 66th convergent of the ordinary c.f. expansion of π.

In this final section we will give a precise formulation to property (H), and prove it for all the algorithms in <ref>, <ref>, <ref>. This will remove, in a quite effective way, all vagueness from the above assertion. Note that, as remarked in <ref>, the validity of (H) implies that any point in K must end its orbit in a parabolic fixed point; explicit computation shows that indeed α lands at ∞ at the 656th iterate of T.


It is interesting to compare the behavior of the previous quadratic T with that of a cubic map. 
Let λ_7=2cos(π/7), whose minimal polynomial is
x^3-x^2-2x+1; again the maximal order [λ_7] in (λ_7) has class number 1.
Precisely as in <ref> for the case (2,5,∞), we define a Gauss map T' via the matrices

    R_7Q_2F,  R_7^2Q_2,  R_7^3Q_2F,  R_7^4Q^2,  R_7^5Q_2F,  R_7^6Q_2,

which generate a copy of the extended Hecke group Δ^±(2,7,∞). The graphs of T and T' have the same structure; they are both saw-like, with 6 pieces and ∞ as the only parabolic fixed point (similar to Figure <ref> (right), but with the leftmost piece deleted).
Figure <ref> (right) shows the behavior of the logarithmic height along the first 180 points of the T'-orbit of the same input α. The decreasing drift is clearly much more erratic, and indeed α takes 4583 steps to reach ∞. Note that, as far as we know, there is no a priori guarantee that α should land at ∞, nor that it is a cusp of Δ(2,7,∞). Indeed, property (H) definitely fails: the point λ_7^2-λ_7-1 (which has minimal height greater than 1 in K=(λ_7)) is a fixed point for T', because it is in I_1 and is fixed by A_1=R_7Q_2F=11λ_7. As it is fixed by the hyperbolic A_1^2, it is not a cusp of Δ(2,7,∞).
This is an instance of a fixed point for a so-called special hyperbolic matrix, which corresponds to an affine pseudo-Anosov diffeomorphism with direction of vanishing SAF invariant;
see <cit.> and references therein.

Given a Gauss map T as in Definition <ref>, we regard =1,…,r as a finite alphabet; as usual, ^* denotes the set of all finite words over , while ^ω is the space of all one-sided infinite sequences.
For every α∈[0,∞], a T-symbolic orbit for α is a sequence =a_0a_1⋯∈^ω such that T^k(α)∈ I_a_k, for k≥0.
Every point has at least one and at most two symbolic orbits; it has two if and only if it eventually lands at an endpoint of one of I_2,…,I_r-1 (so that, at the next step, gets mapped either to 0 or to ∞).
Note that this ambiguity is in the nature of things; if the map ↦α were injective then, since it it surjective and obviously continuous, it would constitute a homeomorphism from the Cantor space ^ω to [0,∞]. 
The symbolic orbit r of ∞ is however unique, and so is that of 0, namely 1 or 1r according whether A_1 equals +1 or -1.

The following result generalizes <cit.>,
as well as <cit.>, to arbitrary extended fuchsian groups; note that the proof uses a different technique.


For every ∈^ω, the nested strictly decreasing sequence of Γ^±-unimodular intervals

    I_0⊃ A_0*I_0⊃ A_0A_1*I_0⊃ A_0A_1A_2*I_0⊃⋯

shrinks to a singleton α. The point α is the unique point having symbolic orbit .


The second statement is an obvious consequence of the first. The intersection of the above sequence of intervals is surely a closed interval [α,β], with 0≤α≤β≤∞; we show that α=β. Suppose not, and let B_k=A_0⋯ A_k. Then there exists a strictly increasing sequence k_0,k_1,… such that B_k_l*0 converges, as l→∞, to one of α,β, say to α, and B_k_l*∞ converges to β. Since the projective space _2=^3 is compact, we can find a subsequence (k_l_j)_j∈ω such that lim_j→∞[B_k_l_j]=[C], for some C∈(_2)∖0, square brackets denoting projective equivalence.
As C*0=α≠β=C*∞, the matrix C is nonsingular and determines an isometry of , possibly orientation-reversing. Now, the point C*i belongs to , and is an accumulation point of the sequence (B_k_l_j*i)_j∈ω. Since the B_k's belong to Γ^± and are all distinct, this contradicts the fact that Γ^± acts on  in a properly discontinuous way.



Let T be a continuous quadratic Gauss map as in Definition <ref>. A decreasing block is a word b_0⋯ b_u∈^*, of length u+1≥2, such that:


  (i) b_0,b_u≠r;

  (ii) I_b_u is contained in the closure of E^♯(A), where A=A_b_0⋯ A_b_u-1=abcd;

  (iii) if A contains a 0 entry (this happens if and only if A_1=+1 and A is a power of A_1, or A_1=-1 and A=A_1) and β∈∂ E^♯(A)∩∂ I_b_u, then

    t(A)(a'β'+b'c'β'+d')>β'1.


A set  of decreasing blocks is complete for T if:


  (iv) A_1=-1 and every ∈^ω that does not start with r, and does not end with r, begins with a block in ;

  (v) A_1=+1 and every ∈^ω that does not start with r, and does not end either with r or with 1, begins with a block in .



We can at last formulate property (H) in a precise way.


Each of the algorithms introduced in <ref>, <ref>, <ref> admits a complete set of decreasing blocks.


The content of Theorem <ref> is the following: choose any symbolic sequence ∈^ω that does not end in r (nor in 1, if A_1=+1). Then, by Theorem <ref>, there exists an infinite sequence of times 0≤ t_0<t_1<t_2⋯ such that each block a_t_k⋯ a_t_k+1 is decreasing. Choose any initial very long finite subword w of , and let α be any element of K having a T-symbolic orbit that starts with w; let h=maxl:t_l<length(w).
Then the following fact is true.



  
Claim For every 0≤ k<h, the strict inequality

    H(T^t_k(α))>
    H(T^t_k+1(α)),

holds, with the only possible exception of the last index k=h-1, where we may have equality; however, this exception takes place if and only if T^t_h-1(α)=1, and forces T^t_h(α)=0.


  
Proof of Claim 
Let us fix a decreasing block b_0⋯ b_u 
and γ∈ K having a symbolic orbit that starts with 
b_0⋯ b_u. Let A=A_b_0⋯ A_b_u-1 and 
β=T^u(γ); then β∈ I_b_u and γ=A*β.
By the definition of decreasing block, β is in the closure of E^♯(A). 
If β∈ E^♯(A), or (β∈∂ E^♯(A), A is strictly positive, and A*β≠1), then H(A*β)>H(β) by Theorem <ref>(4). If β∈∂ E^♯(A) then f_A(β)=t(A); also, by Definition <ref>(ii), β∈∂ I_b_u. If A contains a 0 entry then, by Definition <ref>(iii),

    f_A(β)(a'β'+b'c'β'+d')>β'1,

which is (<ref>) in the proof of Theorem <ref>; thus,
H(A*β)>H(β) again. In the exceptional case in which β∈∂ E^♯(A), A is strictly positive, and A*β=1, we have H(γ)≥ H(β) anyway, so H(A*β)=H(β)=1 and β∈0,1,∞. Since b_u≠r, the case β=∞ is excluded. If β were equal to 1, then 1 would be fixed 
by a strictly positive matrix in Γ, namely A or A^2.
It is easy to show that this contradicts our assumption that 1 is a cusp of Γ; we thus conclude β=0. Note that the exceptional case may occur only at the final decreasing block in w, because as soon as T^t(α) reaches value 0, it can never assume value 1 anymore. Our claim is thus established. 

We now state formally the geometric consequence of property (H) sketched in <ref>.
Let X be a subset of ^1, of cardinality ♯ X at least 3. We let (X) be the set of all cross-ratios (α_1,α_2;α_3,α_4), for α_i∈ X and ♯α_1,α_2,α_3,α_4≥3;
we have (X)⊆^1, and (α_1,α_2;α_3,α_4)∈0,1,∞ if and only if ♯α_1,α_2,α_3,α_4=3.


Let  Γ be a 
noncocompact triangle group with quadratic invariant trace field F_2.
Then (cusps of Γ)=^1F_2.


The set (cusps of Γ) is a commensurability invariant of Γ; indeed, it does not change either by conjugating Γ (by the invariance of cross-ratios under projective transformations), or by passing to subgroups of finite index (by the remark at the beginning of <ref>). We can then assume that Γ equals Γ_T, for precisely one of our Gauss maps T.
By construction, all matrices in Γ_T have entries in the integer ring of F_2, and this easily implies that every cusp of Γ_T is in ^1F_2. For the reverse inclusion, let α∈^1F_2. By applying a power of A_r (the parabolic matrix in Definition <ref>(v)) to α, we may assume α∈[0,∞]. By Theorem <ref> and the Northcott property, there exists a product A of A_1,…,A_r∈Γ_T^± such that A*α equals 0 or ∞. Postcomposing A, if necessary, with an element of Γ_T^± that fixes A*α and has negative determinant, we may assume A∈Γ_T. As 0 and ∞ are cusps of Γ_T, so is α.



As noted in <ref>, Theorem <ref> was proved by Leutbecher for the four quadratic Hecke groups, and reestablished by McMullen <cit.>, using the Veech theory, for three more groups, namely Δ(3,4,∞), Δ(3,5,∞), Δ(3,6,∞); these three groups had been previously examined by the Leutbecher school <cit.>, <cit.>.
As pointed out by the referee, <cit.> and the
further realizations of Veech groups in <cit.> yield the full result.


Theorem <ref> is proved by direct verification.
One computes E^♯(A_a), for each a=1,…,r-1;
whenever its closure contains some I_b, with b≠r, the block ab is decreasing (for a=1 boundary points must be checked according to Definition <ref>(iii)). If I_b is not contained in the closure of E^♯(A_a), then one computes E^♯(A_aA_b) and repeats the process. After some practice a good candidate for  is readily reached, and checking that indeed it constitutes a complete set of decreasing blocks is just a patience task. The simplest cases are those in which the intervals are evenly spread around 1, namely those in <ref>. The cases in <ref> are slightly more involved, 
due to the presence of a second parabolic fixed point at 0 (note that ∞ and 0 do not play a symmetric rôle).
The case (4,6,∞) is the most difficult one, since all intervals I_1,…,I_14 cumulate in [0,1], and several E^♯'s are small. Despite the larger number of intervals, case (4,12,∞) is actually simpler, because intervals are more evenly spread, and the central ones behave in the same way. We start from the simplest case.



 §.§ Case (2,5,∞)
 The matrices are

    A_1=[   1; 1 τ ],  
    A_2=[ τ 1; τ τ ],  
    A_3=[ τ τ; τ 1 ],  
    A_4=[ 1 τ;   1 ],

and the 4 intervals have endpoints 0<τ<1<τ<∞.
Let  be the family of all blocks of the form a4^kb, where a,b≠4 and k≥0.
For convenience, we introduce shorthands for block families; notations such as a,b^c cd,ef^*f,g^c will denote the set of all blocks of the form xcyf^kz∈^* such that x∈a,b^c=∖a,b, y∈d,e, z∈f,g^c, and k≥0. The completeness of the above  (which, in the previous notation, is 4^c4^*4^c)
is clear: every ∈1,2,3,4^ω that does not start with 4 and does not end with 4 (A_1=-1 here) must begin with a block in .
For k≥0 we have

    A_1A_4^k=[             1;      1 (k+1)τ ],  
    A_2A_4^k=[        τ (k+1)+kτ;        τ k+(k+1)τ ].


We compute t(A_1A_4^k)=1+(k+1)τ, E^♯(A_1)=(0,τ^2), and E^♯(A_1A_4^k)=[0,τ^2) for k≥1. We must make sure that the boundary point 0∈∂ E^♯(A_1)∩∂ I_1
satisfies Definition <ref>(iii), which is indeed the case since t(A_1)(a'0+b'c'0+d')=(1+τ)(1τ')=1+τ>1. Since τ<τ^2, we have I_1∪ I_2∪ I_3=[0,τ]⊂[0,τ^2]=(closure of E^♯(A_1A_4^k)), and all blocks of the form 14^*4^c are decreasing. 

The number t(A_2A_4^k) has value τ for k=0,1, and value (2k+1)(2-τ) for k≥2. We have E^♯(A_2)=(0,ξ(0)) and E^♯(A_1A_4^k)=[0,ξ(k)) for some number ξ(k) which we do not need to compute since it is surely greater than τ; indeed, f_A_2A_4^k(τ)=τ+k/τ+(k+1), which is strictly greater than t(A_2A_4^k) for every k. Again, 0∈∂ E^♯(A_2)∩∂ I_1, so we must check the inequality in Definition <ref>(iii), i.e., that
t(A_2)(1τ')>1, which is the case. We conclude that all blocks 24^*(4)^c are decreasing. Since A_3A_4^k is obtained from A_2A_4^k
by exchanging rows and this operation, as remarked in the proof of Theorem <ref>, leaves t and f unaltered, all blocks 34^*4^c are decreasing as well. This concludes the proof of Theorem <ref> for the map of case (2,5,∞).

The particular form of the blocks 4^c4^*4^c implies that, starting with any input in [0,τ]∩(τ) and waiting until the T-orbit returns to [0,τ] guarantees that the height decreases strictly. Thus, the first return map induced by T on [0,τ] (see Figure <ref>) is strictly height-decreasing. In particular, 
the first-return orbit of every point in K=(τ) is eventually undefined: we have to wait forever.



In general, conjugating a map changes radically the structure of decreasing blocks. For example, conjugating the map T above by x↦τ x we obtain a Gauss map T' for which the block 11 is not decreasing any more.




 §.§ Cases (3,4,∞) and (3,5,∞)
 
These cases  are identical to case (2,5,∞). The set of all blocks of the form 5^c5^*5^c  (respectively, 7^c7^*7^c) is a complete family of decreasing blocks, and the map of first-return on the first r-1 intervals is strictly height-decreasing.



 §.§ Case (3,6,∞)
 
This one is more involved. There are 10 intervals, the rightmost two being I_9=[√(3),1+√(3)] and I_10=[1+√(3),∞]. The blocks 1(10)^*10^c are height-decreasing (we make appeal to the reader's patience for the extra parentheses, which are needed to avoid digit ambiguities).
Now, computing E^♯ for the matrix

    A_2A_10^k=[                1      (k+1)+k√(3);             √(3) (3k+1)+(k+1)√(3) ]

yields an interval [0,ξ(k)). The number ξ(k) is in I_10 for k=0,…,16 (see Figure <ref> (left)), but enters I_9 from k=17 on, converging monotonically from the right to (3+√(3))/2, which is in the topological interior of I_9. It follows that the blocks 2(10)^k10^c are indeed decreasing for k≤16, but no more so for higher k's. We therefore include in  all blocks of the form 2(10)^k10^c for k≤16 and of the form 2(10)^k9(10)^*10^c for k≥17; computing the relative E^♯'s shows that the latter blocks are decreasing.
Identical considerations apply to blocks starting with the digits a=3,…,9. Note that if we are satisfied with a coarser  (i.e., a set of decreasing blocks which, albeit complete, is nonoptimal, as it contains blocks longer than necessary), then we may avoid computing the minimal k corresponding to each a, and just put in , in addition to 1(10)^*10^c, all blocks of the form 1,10^c(10)^*9,10^c 
and 1,10^c(10)^*9(10)^*10^c.

In case (3,6,∞), the first-return map to I_1∪⋯∪ I_9=[0,1+√(3)] is not height-decreasing. The point

    α=-106298232+90029733√(3)/-87526426+100742393√(3)

is in I_2 and has logarithmic height 18.8328⋯. It gets mapped to I_10 by T, and stays there for 16 parabolic steps, returning to I_9 as

    β=A_2*α-17(1+√(3))=
    -284852703+186193328√(3)/-18821875+18821875√(3),

which has logarithmic height 18.8341⋯.

We have thus proved Theorem <ref> for the cases in <ref>.
In the remaining cases both extremal intervals I_1 and I_r correspond to a parabolic matrix; note again that in the construction of  the rôle of the digits 1 and r is not symmetric.



 §.§ Cases (4,∞,∞), (5,∞,∞), and (6,∞,∞)
 These are similar, albeit not completely overlapping. The alphabets are =1,…,r, with r equal to 7, 9, and 11, respectively. In each case we provide a list of block families whose union gives a complete set of decreasing blocks. The completeness of the sets is apparent, and the fact that the blocks are decreasing reduces to a tedious but straightforward computation of the relative E^♯'s.


  * (4,∞,∞)

    11^*1,7^c,
    
    11^*77^*7^c,
    1,6,7^c 7^*7^c,
    
    61,7^c,
    
    611^*1,2,7^c,
    
    611^*2,77^*7^c,
    
    677^*7^c.


  * (5,∞,∞)

    11^*1,2,9^c,
    
    11^*2,99^*9^c,
    1,8,9^c 9^*9^c,
    
    81,9^c,
    
    811^*1^c 9^*9^c,
    
    899^*9^c.


  * (6,∞,∞)

    11^*1,11^c,
    
    11^*(11)(11)^*11^c,
    1,10,11^c (11)^*11^c,
    
    (10)1,11^c,
    
    (10)11^*1,11^c,
    
    (10)11^*(11)(11)^*11^c,
    
    (10)(11)(11)^*11^c.





 §.§ Case (4,12,∞)
 This case involves the largest alphabet =1,…,33 but it is not difficult, since all digits from 2 to 29 behave in the same way.

    11^*1,33^c,
    
    11^*(33)(33)^*33^c,
    1,30,31,32,33^c (33)^*33^c,
    
    (30)1,33^c,
    
    (30)11^*(33)^*33^c,
    
    (30)(33)(33)^*33^c,
    31,321,2,3,33^c,
    31,3211^*1,33^c,
    31,3211^*(33)(33)^*33^c,
    31,322,3,33(33)^*33^c.




 §.§ Case (4,6,∞)
 The alphabet is =1,…,15. This is the most difficult case, and the unique one in which a matrix, namely A_13 of Example <ref>, has its E^♭ equal to all of [0,∞]; see Figure <ref> (right). The closure of the set of points in K=(√(6)) on which T is strictly increasing is also large, and includes all of I_13; however, further applications of T make up for these temporary increases. The following is a list of block families whose union provides a complete set of decreasing blocks.

    11^*1,15^c,
    
    11^*(15)(15)^*15^c,
    2,3,6,7,111^*1^c(15)^*15^c,
    4,5,8,9(15)^*15^c,
    
    (10)1,2,3,4,5,6,7,15^c,
    
    (10)11^*(15)(15)^*15^c,
    
    (10)2,3,4,5,6,7,15(15)^*15^c,
    
    (12)13,14,
    
    (12)11^*1^c(15)^*15^c,
    
    (12)2,3,4,5,8,9,10,11,12(15)^*15^c,
    
    (12)6,71^*1,15^c,
    
    (12)6,71^*(15)(15)^*15^c,
    
    (13)11^*1^c(15)^*15^c,
    
    (13)2,3,4,5,6,7,8,9,10,11,14,15(15)^*15^c,
    
    (13)12,131^*1,15^c,
    
    (13)12,131^*(15)(15)^*15^c,
    
    (14)1,2,3,4,15^c,
    
    (14)1,2,31^*1,15^c,[0]
    
    (14)1,2,31^*(15)(15)^*15^c,
    
    (14)4,15(15)^*15^c.

This completes the proof of Theorem <ref>.


10

arnouxhubert00
P. Arnoux and P. Hubert.
Fractions continues sur les surfaces de Veech.
J. Anal. Math., 81:35–64, 2000.

arnouxschmidt09
P. Arnoux and T. A. Schmidt.
Veech surfaces with nonperiodic directions in the trace field.
J. Mod. Dyn., 3(4):611–629, 2009.

baladivallee05
V. Baladi and B. Vallée.
Euclidean algorithms are Gaussian.
J. Number Theory, 110(2):331–386, 2005.

berg85
F. Berg.
Dreiecksgruppen mit Spitzen in quadratischen Zahlkörpern.
Abh. Math. Sem. Univ. Hamburg, 55:191–200, 1985.

berthe11
V. Berthé.
Multidimensional Euclidean algorithms, numeration and
  substitutions.
Integers, 11B:Paper No. A2, 34, 2011.

bombierigubler06
E. Bombieri and W. Gubler.
Heights in Diophantine geometry.
Cambridge University Press, 2006.

bouwmoller10
I. I. Bouw and M. Möller.
Teichmüller curves, triangle groups, and Lyapunov exponents.
Ann. of Math. (2), 172(1):139–185, 2010.

caltaschmidt12
K. Calta and T. A. Schmidt.
Continued fractions for a class of triangle groups.
J. Aust. Math. Soc., 93(1-2):21–42, 2012.

einsiedlerward
M. Einsiedler and T. Ward.
Ergodic theory with a view towards number theory.
Springer, 2011.

girondo_et_al12
E. Girondo, D. Torres-Teigell, and J. Wolfart.
Shimura curves with many uniform dessins.
Math. Z., 271(3-4):757–779, 2012.

greenberg63
L. Greenberg.
Maximal Fuchsian groups.
Bull. Amer. Math. Soc., 69:569–573, 1963.

hooper13a
W. P. Hooper.
Grid graphs and lattice surfaces.
Int. Math. Res. Not., 2013(12):2657–2698, 2013.

katok92
S. Katok.
Fuchsian groups.
University of Chicago Press, 1992.

lang
S. Lang.
Algebra.
Addison-Wesley, 3rd edition, 1993.

leutbecher74
A. Leutbecher.
Über die Heckeschen Gruppen G(λ ). II.
Math. Ann., 211:63–86, 1974.

maclachlanreid03
C. Maclachlan and A. W. Reid.
The arithmetic of hyperbolic 3-manifolds.
Springer, 2003.

margulis75
G. A. Margulis.
Discrete groups of motions of manifolds of nonpositive curvature.
In Proceedings of the International Congress of
  Mathematicians (Vancouver, B.C., 1974), Vol. 2, pages 21–34.
  Canad. Math. Congress, 1975.

mcmullen03
C. T. McMullen.
Teichmüller geodesics of infinite complexity.
Acta Math., 191(2):191–223, 2003.

nugentvoight17
S. Nugent and J. Voight.
On the arithmetic dimension of triangle groups.
Math. Comp., 86(306):1979–2004, 2017.

panti09
G. Panti.
A general Lagrange theorem.
Amer. Math. Monthly, 116(1):70–74, 2009.

panti18
G. Panti.
Slow continued fractions, transducers, and the Serret theorem.
J. Number Theory, 185:121–143, 2018.

schweiger00
F. Schweiger.
Multidimensional continued fractions.
Oxford University Press, 2000.

seibold85
F. Seibold.
Zahlentheoretische Eigenschaften der Heckeschen Gruppen
  G(λ) und verwandter Transformationsgruppen.
Inauguraldissertation, Techn. Univ. München, 1985.

series85
C. Series.
The modular surface and continued fractions.
J. London Math. Soc. (2), 31(1):69–80, 1985.

singerman72
D. Singerman.
Finitely maximal Fuchsian groups.
J. London Math. Soc. (2), 6:29–38, 1972.

smillieulcigrai10
J. Smillie and C. Ulcigrai.
Geodesic flow on the Teichmüller disk of the regular octagon,
  cutting sequences and octagon continued fractions maps.
In Dynamical numbers—interplay between dynamical systems and
  number theory, pages 29–65. Amer. Math. Soc., 2010.

smillieulcigrai11
J. Smillie and C. Ulcigrai.
Beyond Sturmian sequences: coding linear trajectories in the
  regular octagon.
Proc. Lond. Math. Soc. (3), 102(2):291–340, 2011.

takeuchi77a
K. Takeuchi.
Arithmetic triangle groups.
J. Math. Soc. Japan, 29(1):91–106, 1977.

takeuchi77b
K. Takeuchi.
Commensurability classes of arithmetic triangle groups.
J. Fac. Sci. Univ. Tokyo Sect. IA Math., 24(1):201–212, 1977.

veech89
W. A. Veech.
Teichmüller curves in moduli space, Eisenstein series and an
  application to triangular billiards.
Invent. Math., 97(3):553–583, 1989.

ward98
C. C. Ward.
Calculation of Fuchsian groups associated to billiards in a
  rational triangle.
Ergodic Theory Dynam. Systems, 18(4):1019–1042, 1998.



