ABSTRACT

Several links between continued fractions and classical and less classical constructions in dynamical systems theory are presented and discussed.

Keywords:Continued Fractions, Fast and Slow Convergents, Irrational Rotations, Farey and Gauss Maps, Transfer Operator, Thermodynamic Formalism

1. Introduction

The connection between Number Theory and Dynamical Systems Theory is receiving recently a considerable attention. In this paper, we review some aspects of this connection focusing on the interplay between continued fractions and one dimensional dynamics. In Section 2, we review some known facts about fast and slow convergents, highlighting their relations both with irrational rotation dynamics and the ergodic theory of the Gauss map. In Section 3, after recalling the construction and the basic properties of the Farey tree, we describe different ways of coding the paths on it, as well as their dynamical counterparts obtained by combining fractional linear transformations. Deeper insights into these connections are provided by the Minkowski question mark function, whose properties are discussed in Section 4. Finally, in Section 5, we present some applications of the thermodynamical formalism based on the previous constructions.

2. Fast and Slow Convergents

We start by reviewing some well known facts about continued fractions¹.

Let

(2.1)

be the continued fraction expansion of the number. By applying Euclid’s algorithm one sees that the above expansion terminates if and only if x is a rational number. For x irrational one can construct recursively a sequence of rational approximants of x as

(2.2)

We can write this recursion in matrix form as follows: letting

(2.3)

and noting that

(2.4)

we have

(2.5)

and

(2.6)

A short manipulation of (2.2) gives. Since one obtains inductively the Lagrange formula

(2.7)

Another useful formula which can be easily obtained from (2.2) is the following: for all and,

(2.8)

Letting we get in particular

(2.9)

Note that

and so forth. We thus have the so called mirror formula (some consequences of which have been investigated in [4] ):

(2.10)

The numbers are called continued fraction convergents (CFC) of x and it turns out that the n-th CFC is the best rational approximation to whose denominator does not exceed [2] . One sees that

(2.11)

Putting in (2.8) we get

(2.12)

But what happens if in (2.8) takes on an intermediate value?

Definition 2.1 For the sets for are the n’th Farey convergents (FC) for the real number.

Example. Let. The first five CFC are

On the other hand, within the same accuracy, there are FC’s. They are

We now need some notions.

Definition 2.2 The Farey sum over two rationals and is the mediant operation given by

(2.13)

It is easy to see that falls in the interval ². We say that and are Farey neighbours if

. Two Farey neighbours define a Farey interval and each Farey interval can be labeled uniquely according to the mediant (child) of the neighbours.

Observe that given a pair of consecutive FC’s, say

for some and, we have

(2.14)

Moreover

(2.15)

by Lagrange’s formula. Therefore, for every, each FC for is a Farey neighbour of

, the corresponding Farey interval getting smaller and smaller as increases. More precisely, using again Lagrange’s formula, one easily obtains  

(2.16)

We therefore see that the FC is the best one-sided rational approximation to whose denominator does not exceed (although, if, there might be a CFC with denominator less than and closer to on the other side of x). Increasing r, once we arrive at we hit a new CFC on the current side of, closer than the previous CFC. Finally, using matrix notation, the FC’s can be expressed in terms of intermediate products in (2.5) for as

(2.17)

The algorithm which produces the sequence of ‘s of a given real number is called slow continued fraction algorithm (see, e.g., [6] [7] ).

Remark 2.3 The set of Farey fractions of order is the set of irreducible fractions in with denominator, listed in order of magnitude (see [8] ). Thus, ,

and so on. In particular with Euler totient function

. Then we see that each for is consecutive to in

for.

2.1. Connection to Rotations of the Circle

One can interpret the above construction in terms of a kind of renormalization procedure for rotations of the circle through an angle. With no loss we take the initial point to be the origin 0 and set.

Since we have and thus

with

(2.18)

Moreover we have

and therefore or, which is the same,

with

(2.19)

Iterating this procedure, we construct a family of nested intervals (see Figure 1), , such that

(2.20)

and

(2.21)

where we have set. Using (2.18), (2.19) and (2.21) one gets inductively the formula

(2.22)

Note that

(2.23)

Now, if we denote by the euclidean metric on then

(2.24)

Therefore

(2.25)

That is, the sequence of arc-lengths is but the sequence of successive closest distances to the initial point. This can be seen in the following way: starting from 0 and iterating times one ends up at the point which lies on the left of 0 and is the point closest to 0 up to now, being distant from it. Iterating more times one ends up at the point which lies on the left of 0 at distance, ... iterating times one ends up at the point which still lies on the left of 0, at distance. One more iterate yields the point which now lies on the right of 0 at distance and is the point closest to 0 up to now, and so on and so forth (for more details see [9] ). The above implies that the first return map in the interval (which is or according whether is even or odd) is the rotation through the angle. Finally, one has the equivalence:

(2.26)

In addition, for each, it holds

(2.27)

The three distance theorem. The points with partition the unit circle into intervals. A classical result (see e.g. [10] ), which can be easily obtained by induction using the above construction, is that the possible lengths of these intervals are organized according to the Farey convergents in the following way:

• If then there are two distinct lengths: and (which become and when).

• If for some and then there are at most three lengths:, and, the last of which disappears when.

We point out that in the second case above there are two intervals, chosen from among those having the smallest lengths:

which have 0 as their common endpoint. We then see that the approximations (26) and (27) are the same as shrinking one of these intervals to zero. Moreover, the fractions and are the two successive elements of having between them (see also Remark 2.3).

2.2. Growth of Denominators

The Gauss map is defined as

(2.28)

It is well known that has an a.c. invariant ergodic probability measure given by

(2.29)

A short reflection shows that or else

(2.30)

From this we obtain at once

(2.31)

where the numbers have been introduced in (2.22). Therefore

and, by the ergodic theorem, we have for -almost all and then almost everywhere,

(2.32)

Since and thus another consequence of (2.30) is that

and therefore using (2.31)

(2.33)

Putting together (2.32) and (2.33) we get the classical theorem of Lévy

On the other hand we may expect the growth of FC’s denominator to be subexponential. Indeed, let

with be the m-th FC. Its denominator satisfies. It is a result of Khinchin and Lévy (see [1] ) that

Combining the above we get the following

Lemma 2.4

Of course there are special behaviours: take, then and both are equal to the n-th Fibonacci number. Hence converge to.

3. A Walk on the Farey Tree

Having fixed, let be the ascending sequence of irreducible fractions between 0 and 1 constructed inductively in the following way: set first, then is obtained from by inserting among each pair of neighbours and in their child as in (2.13). Thus

and so on. The elements of are called again Farey fractions. Evidently.

Remark 3.1 It has been shown in ([11] , Thm 2.6) that the set becomes equidistributed as. More specifically, the probability measure converges to the Lebesgue measure on

.

Definition 3.2 For we say that a Farey fraction has rank if.

We also define the. For there are exactly Farey fractions of rank

and their sum is equal to. Recall that every rational number has a unique finite continued fraction expansion with [2] . The validity of the following relation will arise straightforwardly in the sequel:

Lemma 3.3

Remark 3.4 Note that, according to the above Lemma, the cardinality of can be interpreted as the number of choices of integers, with and so that for,

and. Indeed, for each fixed the number of such choices is, then sum over

.

It is also easy to realize that all Farey fractions which fall in the interval have rank greater than or equal to, whereas their continued fraction expansion starts with.

An interesting object is the  Farey tree whose vertex-set is and which is constructed as follows (see Figure 2):

• every column in contains one entry (vertex or node);

• for the -th row is;

• the node, representing the interval, is connected by edges to its left child and right child in the underlying row.

Note that the fractions and play the role of ancestors when using the Farey sum to obtain one row from the previous one. Besides the Farey sum, an alternative way to construct recursively the entries of is as follows.

Definition 3.5 Given its descendants are the symmetrical entries of given by andrespectively.

Lemma 3.6 The collection of all descendants of the entries of a given row in is precisely the underlying row.

Proof. If then and. Therefore

and the claim follows.

Remark 3.7 If and then and.

3.1. The Coding

Every rational number in appears exactly once in the above construction and corresponds to a unique finite path on starting at the root node and whose number of vertices equals the rank of the rational number. We can code this path in the following way: first, any can be uniquely decomposed as³

(3.1)

and the unimodular relations

(3.2)

plainly hold. The neighbours and are thus the ‘parents’ of in and we may accordingly identify

(3.3)

with

(3.4)

Note that the left column bears on the right parent and viceversa. Thus

(3.5)

On the other hand, any as above has a unique pair of (left and right) children, given by

(3.6)

respectively. In order to generate them we set

(3.7)

Note that for

(3.8)

and also

(3.9)

Moreover, we have

(3.10)

and

(3.11)

In other words, the matrices L and R, when acting from the right, move to the left and right child in, respectively. Moreover, it is plain that given we have and. We have thus proved the following Proposition 3.8 To each entry there corresponds a unique element which, in turn, can be uniquely presented as

(3.12)

where the number of terms in the product is equal to and M_i = L or M_i = R according whether the i-th turn, along the descending path in which starts from the root node and reaches xgoes left or right.

Remark 3.9 By the way, the matrices L and R induce the so called Farey tesselation of the upper half plane (see [12] ).

Example. is the right child of, which is the right child of, which is the left child of, which is the left child of. Thus

For, which is the left child of, we find

Note that.

To any given irrational number we may associate a unique infinite path on, and thus a unique semi-infinite word in. Bearing in mind the continued fraction expansion (2.1) of x, let

the first FC of x. In order to reach it from the top of we need the block. Whence we code x through the map defined by

(3.13)

where or according whether the i-th turn along the infinite path in which starts from

and approaches x along the sequence of successive FC’s goes left or right. This coding is faithful to the binary structure of but apparently not so much to the continued fraction expansion of x. To make the latter more transparent we may note that, according to the characterization of the FC’s given above (see (2.15) and (2.16)), the symbols L and R in (3.13) come in blocks whose lengths are given by nothing but the partial quotients of. More precisely, a short reflection shows that the following rule is in force: the first block is such that if. Moreover, for let

then we have

In other words, we have the coding

(3.14)

Furthermore we set and. More generally, we note that each rational x has two infinite paths which agree down to node: they are those starting with the finite sequence coding the path to reach x from the root node and terminating with either or. We shall agree that terminates with or according whether the number of its (finite) partial quotients is even or odd. On the other hand, for notational simplicity’ sake we shall assume this agreement only implicitly. We summarize the above in the following Theorem 3.10 To with continued fraction expansion there corresponds a unique sequence given by which represents an infinite path on whose sequence of vertices starting from the -th is precisely the sequence of FC’s of x. Moreover, if denotes the lexicographic order on then

An simple consequence of the above construction is the following result.

Proposition 3.11 Let with and even. Then its left and right children in are given by and, respectively. If instead is odd the expansions for and have to be interchanged.

Proof. Since is even we can write

(3.15)

Therefore

which yield the claim. A similar reasoning applies for odd.

3.2. The {A, B} Coding

Using (3.9) we can write

(3.16)

On the other hand we have and (see (2.4))

(3.17)

This defines a recoding so that

(3.18)

The FC of, which has rank, will then be expressed as

(3.19)

or else

(3.20)

Note that both expansions have exactly terms and the latter agrees with (2.17) once we interpret the l.h.s. of

(2.17) as the FC of x, that is taking the Farey sum of the columns in the same spirit as (3.3).

Example. The example with discussed above, which yields

can be used to check step by step what we are claiming here. For example its FC, which has rank 6, can be expressed as

3.3. The Farey Shift and Its Relatives

So far, a sequence in starting with the symbol R has no image in with. Let us make the identification

(3.21)

and denote by the half-space of so obtained. We can write

(3.22)

We see that the map is a bijection between and.

Let be the Farey shift map defined by

(3.23)

Note that, besides the only fixed point of is given by the sequence which is the image with of, the golden mean. This map acts on points in by reducing their rank of one unit.

For example, since, with the identifications made above we have

Let us define the Farey map given by

(3.24)

Its name can be related to the easily verified observation that the set of pre-images coincides with for all. Note also that the -th row of the Farey tree is precisely. In particularthis implies that.

Proposition 3.12 Let be the coding described above. Then

Proof. If then and. If instead then and

. Therefore,

(3.25)

with. The claim now follows from (3.23) and (3.21).

3.3.1. The Gauss and Fibonacci Maps

The map F has (at least) two induced versions: the first one is the Gauss map already introduced in (2.28), which for can be written as

(3.26)

Recall that

(3.27)

Noting that

(3.28)

we see that G is obtained by iterating F once plus the number of times necessary to reach the interval. The second one is the Fibonacci map H and is defined by iterating F once plus the number of times necessary to reach the interval. Let and for be the Fibonacci numbers. Then, for,

(3.29)

with

(3.30)

In this case it is easy to check that if then

(3.31)

A sketch of the map F along its induced versions G and H is given in Figure 3.

Given we may define the Möbius transformation

By the above, given the point is but and for we have

(recall that). But what happens if so that?

To see this we put

(3.32)

We have

Therefore, noting that, for we have. To summarize we can represent the action of F as

that of G as

and that of H as

3.3.2. The Modified Farey Map

Finally we introduce the modified Farey map given by

(3.33)

This map preserves orientation and has two indifferent fixed points, at 0 and 1. The advantage of using instead of is that one can retrace the path from a leaf back to the root. More precisely, for let (cf. Proposition 3.8) be the element which uniquely represents x in. Then one easily sees that the following rule is in force: if then, then, for with so that.

4. The Minkowski Question Mark

Given a number with continued fraction expansion, one may ask what is the number obtained by interpreting the sequence (see (3.14)) as the binary expansion of a real number in. The number so obtained is denoted and writes

(4.1)

or, which is the same,

(4.2)

For instance, for all (see Figure 4). Setting and one has the following properties for the function (see [13] -[16] ):

• is strictly increasing from 0 to 1 and Hölder continuous of exponent;

• x is rational iff is of the form, with k and s integers;

• x is a quadratic irrational iff is a (non-dyadic) rational;

• is a singular function: its derivative vanishes Lebesgue-almost everywhere.

The following additional properties easily follow from the definition.

Lemma 4.1 satisfies the functional equations

Proof. Assuming that we write with and. Setting moreover we have and. The assertion now follows by direct application of (4.2).

Let us now see how acts on Farey fractions. We have already seen that

More generally, for any pair and of consecutive Farey fractions the function ? equates their child to the arithmetic average:

(4.3)

One sees that the function ? maps the Farey tree to the dyadic tree defined as follows: having fixed, let be the ascending sequence of fractions of the form,. We have

and so on. Then is the same graph as with the -th row replaced by. An immediate consequence of the fact that is that is the asymptotic distribution function of the sequence of Farey fractions:

Theorem 4.2 Since

then

Remark 4.3 This result can be also deduced as a consequence of a more general result obtained in [17] using a suitable enumeration of the rationals in. As for the convergence of the atomic measure concentrated on to see [11] and [18] .

As a further immediate consequence we get that the Fourier-Stieltjes coefficients of are as in the following

Corollary 4.4 Let

then

Finally, a short reflection using the definition (4.1) shows that ? conjugates the Farey map F and the modified Farey map to the tent map

(4.4)

and the doubling map, respectively. Indeed, for any with we have

(4.5)

and

(4.6)

where and. A similar reasoning applies for D. Putting together the above, (3.25) and (4.1) we then get the following commutative diagrams

Theorem 4.5

This implies that the measure is invariant under both maps F and, and its entropy is equal to. This makes the measure of maximal entropy for F and. Being zero at every rational point is of course singular w.r.t. Lebesgue. More specifically, is concentrated on a subset having Hausdorff dimension (see [14] ). In view of (3.25), the above has the following straightforward consequence Lemma 4.6 If x is drawn from according to the singular measure, then the partial quotients of form a sequence of i.i.r.v.’s with.

It is moreover easy to realize that F and have also absolutely continuous (not normalizable) invariant measures, with densities and, respectively.

Finally, the conjugacy of Theorem 4.5 has been used in [19] to construct a correspondence between the parameter spaces of -continued fraction transformations and unimodal maps.

5. Transfer Operators and Partition Functions

To a given matrix and complex parameter one can associate the positive operator

acting on the right as [20]

(5.1)

For example we have

(5.2)

The operator associated in this way to the map turns out to be the transfer operator acting as

(5.3)

Of special significance is the (Perron-Frobenius) operator which satisfies

(5.4)

and has norm at most one in the Banach space. A function is the density of an absolutely continuous invariant measure for F if and only if. In this case we find, which however does not lie in (see [21] ).

Let f be an eigenfunction of analytic in the half-plane. It satisfies

(5.5)

and also

(5.6)

Therefore the eigenvalue equation is equivalent to the three-term equation

(5.7)

which is a generalisation of the Lewis functional equation (with) studied in number theory (see [20] [22] ). The study of this generalized equation has been initiated in [23] .

Remark 5.1 In the context of the thermodynamic formalism, once a one-sided shift and a potential function are given one defines a transfer operator on by

which plays a key role in the study of equilibrium states for and their properties [24] [25] . In particular, one defines

and it turns out that if decays exponentially then there is a unique mixing equilibrium state.

Relying on the above discussion it is now easy to see that with

In order to compute we have to consider points sharing the same path up to the k-th row of. Take for instance and. Then a short reflection yields, for,

We therefore see that although (so that is uniformly continuous) it is not even of summable variation. This entails that has indeed two equilibrium states, thus exhibiting a phase transition (see [26] ).

Next, we express the n-th iterate of as

(5.8)

where. We have so that, in particular, putting we get

(5.9)

and

(5.10)

Lemma 5.2 Let be the sequence of functions defined by and

For each fixed we have that determines a bijection between and the set of denominators of the elements of (considered as an ordered set).

Proof. The proof is just a straightforward verification. Suppose for instance that with

, so that. Then by (5.9) and (5.10) is given by a product with factors of the type where r = a if, r = b otherwise. The result now readily follows by lemma 3.6.

Remark 5.3 The rank of the elements of with denominator is given by

with the convention. The smallest of the above denominators is 1, it has rank 0 and is obtained as. The two largest ones are equal to the -st Fibonacci number

. They are symmetrical w.r.t, have rank and are obtained as

and, respectively. More generally, it is not difficult to see that the following equivalence is in force: suppose that the element has rank so that for some and, then the same denominator, but corresponding to the symmetrical fraction, is obtained as with.

A direct consequence of the above lemma is the following

Theorem 5.4

Remarkably, the above sum is equal to the partition function at (inverse) temperature of the number-theoretical spin chain introduced by Andreas Knauf in [27] . For we have (see [28] )

(5.11)

Note that for the above limit diverges. This reflects the fact that the invariant density for the Farey map F, that is the fixed point of the operator, is the function.

Let us define the pressure function as

(5.12)

Since the sum in Thm. 5.4 has terms we see that (this is the topological entropy of the map). More generally let denote the sequence of denominators of the elements of

when the latters are arranged in increasing order in, so that

(5.13)

The ratio can be interpreted as the moment of order of the size of the denominators in

. is plainly non-increasing and for satisfies. Moreover we have

with for all. Noting that we get for

Since this yields

(5.14)

Thus, for all,

(5.15)

In addition, since is non-increasing and (because the spectral radius of is 1, see above) we have for. Note that the same conclusion follows at once from the fact that is finite for (see (11)).

Remark 5.5 It holds where is the free energy of the Knauf model. In the context of thermodynamic formalism the pressure is a central object. In particular it is used as a generator of averages: its first derivative, wherever it exists, yields the mean of the function w.r.t. the equilibrium measure, which can be defined as the weak *-limit point of atomic measures supported on periodic points of F weighted with the function [24] . Note that for and as. On the other hand we have already seen that and is called measure of maximal entropy. Higher derivatives of are connected to (sums of) higher correlation functions, see [25] [29] .

Let us now study the asymptotic behaviour of for. To this end, we notice that if, instead of, we evaluate the iterate at, all sequences in (5.8) yield paths which end up at the same row of the Farey tree. The same argument leading to Theorem 5.4 now yields the following

Corollary 5.6

(5.16)

By Thm. 5.4 and (5.16) we obtain

(5.17)

so that we can directly apply the results obtained by Thaler in [30] to get⁴

Lemma 5.7

Lastly, noting that

one may then use, along with Lemma 3.6, to proceed inductively with in (5.8), and obtain the following general expression for with.

Theorem 5.8 For all and we have

We refer to [31] for further generalisations and applications (see also [32] ).

The Partition Function for Negative Integer Temperatures

Finally, we compute the value of the partition function for some some specific value of the temperature. Related results are discussed in [33] (see also [34] ).

Lemma 5.9 We have, for all,

Proof. The first identity is trivial. The second one follows immediately from along with (5.14), which gives the recursion. As for the third one, we can reason as follows: let us denote

and. Then (5.14) yields. Moreover, we have

This yields the recursion with and and the claim easily follows. The above result indicates a general argument to work out for any: setting and one has

and

This yields a k-dimensional recursion

(5.18)

with matrix

and initial condition

(5.19)

By Perron-Frobenius theorem the matrix has a simple real positive maximal eigenvalue whose eigenvector has strictly positive components. This immediately yields

(5.20)

More specifically, by the above the exact behaviour of can be obtained by standard linear algebra. If for instance can be diagonalized with spectrum and corresponding eigenvectors, then we can expand so that (5.18) and (5.19) yield

(5.21)

where denotes the first component of. On the other hand, as we shall see in the forthcoming example, is not always diagonalizable.

Examples. For we find

so that by (5.20) and using (5.21) one easily recover the result of Lemma 5.9 for.

For we get

In this case (5.21) does not hold but one easily finds

and.

The case is still different, yielding

References

NOTES

¹Good general sources on this subject are -.

²The origin of these names traces back to Cauchy, who proved this property after it was observed by John Farey in 1816 , and named “Farey series” the numbers obtained in this way.

³All fractions are supposed in lowest terms.

⁴We say that a_n and b_n are asymptotically equivalent, denoted as a_n ~ b_n, if the quotient a_n/b_n tends to unity as n approaches ∞.