Gap Theory

The goal of this web page is to develop the theory of continued fractions, as they apply to fractals, in a simple and expository way. Continued fractions and Farey Numbers (or Fibonacci Numbers or Stern-Brocot Trees) are deeply related. And it doesn't take much looking about to see that fractals and Farey numbers are deeply related, which is indeed the main presumption of this web site. But what, precisely, is the relationship? And why is it interesting? Given that the relations between Farey numbers and fractals are well known, then why are we bothering with continued fractions? I believe that this is interesting because continued fractions allow Farey sequences and related things to be parameterized by a smooth, continuous, real-valued (or at least, rational-valued) parameter. And, of course, smooth parameters allow the application of very traditional analytic techniques that aren't available when counting with integers. That's the crux: continued fractions provide the bridge between number theory and analysis. They span the divide between the 19th century "differentiable everywhere" and the 20th century "discontinuous everywhere" mindsets.

My hidden hope is, of course, that by the application of this theory, exact, analytic expressions can be presented for various fractal phenomena, such as the boundary of the Mandelbrot set, or the structure of phase locking in the circle map, without the use of iteration. Or, put in high-falutin terms, that homomorphisms between iterated functions and continued fractions can be found. I am not aware of any work (other than my own) that pertains to this goal, published on the web, or in traditional publications. Feel free to send me a pre-print, or re-print, or a URL, to me, at 1518 Enfield Road, Austin TX 78703-3424 USA, if you know better.

The exposition on this page is not deep: the presentation is straight-forward, and should be accessible to patient and smart high-school readers.

Continued Fractions

Given a real number 0 < x < 1, a sequence of integers [a1, a2, ...] can be found that define its continued-fraction expansion:

x = 1/(a1 + 1/(a2 + 1/(a3 + ... )))

Given any x, this sequence is straightforward to compute. Rational numbers x always have a finite number of terms in the sequence. For a rational number x, there are two distinct expansions that yield the same value:

x+ = [a1, a2, ... , aN]

and

x- = [a1, a2, ... , aN-1, 1]

In the following text, we make a simplifying notational confusion: we use the same symbols to denote a sequence and its value when expressed as a continued fraction. Thus, for the above sequences, we may write x = x- = x+. It will hopefully be obvious which is which.

Given a rational x and an arbitrary complex number w, define new sequences:

x+(w) = [a1, a2, ... , aN, 1/w]

x-(w) = [a1, a2, ... , aN-1, 1, 1/w]

These two functions are analytic in w, and can be expressed as the ratio of two polynomials in w. Thus, general analytic manipulations are perfectly well-defined on these functions. Clearly,

limw->0 x-(w) = limw->0 x+(w) = x

Differentiation w.r.t. w provides a handy tool for constructing various interesting things and proving various limits. We give an exact expression for these derivatives below. Although we've introduced w by appending it to the last term of a rational expansion, we could, if we wanted, introduce w into the N'th term of an irrational expansion. Most of the statements we make below are for rationals. This is in part because treating the irrationals is a bit harder and confusing, both in these formulas, and in their implementation as algorithms.

There is also an even-odd symmetry for x(w) that we should be aware of, as it plays another important role in the theory. As we point out above, for any given sequence, there is a + and a - generalization. But what if the sequence is already x- and we choose the - expansion? Then we get

x-- = [a1, a2, ... , aN-1, 0, 1]

This expansion invokes a symmetry on x-(w):

x--(w) = [a1, a2, ... , aN-1, 0, 1, 1/w] = x+(w)

Thus, we see that a double-expansion is either idempotent or alternating. To be pedantic, we can complete this with the other three expressions: x++(w) = x+(w) and x-+(w) = x+-(w) = x-(w). In other words, a double-expansion reflects back, and, in this sense, x+ and x- are unique. If one needs to take differences, e.g. for derivatives, the even-odd expansion is more useful: Define xe(w) and xo(w) as follows:

xe = [ if (N even) x+ else x- ]

xo = [ if (N even) x- else x+ ]

These have nice order-preserving properties: if w is a positive real, then

xo(w) < xe(w)

and, for negative real w,

xo(w) > xe(w)

and thus differences are well-behaved as a function of x.

These also have idempotent or parity-swapping identities:

xe+ = xe   ,    xe- = xo   ,    xo+ = xo   ,    xo- = xe

xee = xe   ,    xeo = xo   ,    xoe = xe   ,    xoo = xo

x+e = xe   ,    x+o = xo   ,    x-e = xe   ,    x-o = xo

Gaps

Define a function Fz(x) as follows:

Fz(x) = z/(a1 + z/(a2 + z/(a3 + ... )))

For any rational x, Fz(x) is analytic in z. But, for any z not equal to one, it is continuous nowhere in x. Some beautiful pictures of this function and its cousins can be seen in the art gallery in the Farey Room. As can be seen from the pictures in the art-gallery, the discontinuities are reminiscent of various fractal phenomena. Our goal in this section is to characterize these discontinuities, or 'gaps'.

For rational x, just as we defined x-(w) and x+(w), it is handy to provide the same treatment for F, and thus define Fz(x+(w)) and Fz(x-(w)) in the obvious way. Note, in particular, that the +/- and even/odd symmetries still apply: in particular,

Fz([a1, a2, ... , aN-1, 0, 1, 1/w] ) = Fz([a1, a2, ... , aN-1, 1/w] )

It is in the analysis of Fz where the distinction between x+(w) and x-(w) becomes important: the discontinuitities can be precisely characterized as the difference between these. Let

D-z(x) = limw->0 [ Fz(xeven(w)) - Fz(xodd(w)) ]

This function is perfectly well-defined because it is the limit of a function that is analytic in w. It is still analytic in z, and is very discontinuous in x. (and we've side-stepped the issue of defining it for irrational x). D- essentially characterizes the discontinuities in F. Another interesting function is the symmetric sum: D+z(x) = limw->0 [ Fz(x+(w)) + Fz(x-(w)) ] = limw->0 [ Fz(xeven(w)) + Fz(xodd(w)) ]

Note that D-z goes to zero as z->1. We use this to define the 'gaps':

G-(x) = limz->1 D-z(x) / (z-1)

Again, because D was analytic in z, this limit is perfectly well defined for any rational x. Again, it is continuous nowhere in x. It is not terribly hard to compute numerically; it being well-defined leads to there being no numerical instabilities or inaccuracies that accumulate when computing it. It is very tractable with basic common-sense numerical programming techniques. The following two graphs show G-(x). If you look at them carefully, you can now spot the relationship to Farey numbers.

The tallest visual sequence corresponds to gaps at 1/2, 1/3, 1/4, ...,1/n. Where are the next-tallest gaps? If you squint carefully, you can see they are at the Farey mediants between their tallest neighbors. Thus, the second line is at 2/5, 2/7, 2/9, ... Similarly, the largest gap between 1/2 and 2/5 is at 3/7. The largest gap between 2/5 and 1/3 is at 3/8. By now, the sequence should be recognizable as a Farey Tree:

Theorem: The largest gaps are laid out on a Farey Tree.
Proof: Given any rational p/q, reduced so that p and q share no common factors, we have G-(p/q) = 1/q2 (as shown below). The largest gap is clearly at p/q=1/2. We can then apply the usual induction on the Farey Tree: if p1/q1 and p2/q2 then p1/q1 < (p1+p2)/(q1+q2) = p3/q3 < p2/q2 is true and p2q1 = 1+p1q2 is also true. Now we need to search for a fraction m/n with the smallest possible denominator n that satisfies p1/q1 < m/n < p2/q2. Clearly, n =< q1+q2, we just proved that above. To complete the proof, we need to show strict equality. Could n be smaller than this? Well, suppose it's smaller by one. However, (p1+p2-1) / (q1+q2-1) =< p1/q1 and p2/q2 =< (p1+p2) / (q1+q2-1) therefore (q1+q2-1) != n and therefore n can't be smaller by one. Is it smaller by two? Well, no, and if we work out the recursion formula (its a bit tedious but maybe a good exercise), we conclude n can't be smaller by two, three, or anything. Therefore n = (q1+q2) is the smallest denominator, and thus, the largest gap, that can occur between p1/q1 and p2/q2. By induction, the largest gaps are ordered on the Farey tree. QED

I do not know if the above theorem is new, or is old and well known. I am not aware of any references, on the web, or published in journals, that deal with these 'gaps'. Please let me know if you have references. Note that the earliest theorems about Farey numbers were first proved by Haros in 1802, 14 years before Farey publicized the relationship that now bears his name. Maybe we should call them 'Haros Numbers'.

Numerical Methods

To compute G-(x), it is handy to work out some recurrence relations. Given a sequence [an], define the result of a partial evaluation of the continued fraction as follows. If we evaluate all but the last k divisions, the current term will be

sk = ak + 1/sk+1

That is, we've defined sk such that x = 1/s1. It is handy to also define a0=0 so that we can write x = s0. The corresponding term in Fz(x) is tk with

tk = ak + z/tk+1

Because we will be taking the limits w->0 and z->1, we should expand tk to the first order in each. That is, assuming w and (z-1) are small, define

tk = sk + w Wk + (z-1)Dk + w(z-1)Ek

By applying the recurrence relation for tk we can deduce the recurrence relations for each of these pieces:

Dk-1 = (1 - Dk/sk)/sk

Wk-1 = - Wk/sk2

Ek-1 = - (Wk + Ek)/sk2

To these, we need to add the initial conditions. For F(x+) we have

sN = aN   ,    DN = 0   ,    WN = 1   ,    EN = 1

and for F(x-) we have

sN = aN   ,    DN = 1   ,    WN = -1   ,    EN = -2

It is handy to label each sequence with a + or - to denote the initial conditions. Thus, for example, to the first order in w and z-1,

Fz(x+(w)) = t+0 = s+0 + w W+0 + (z-1)D+0 + w(z-1)E+0

and so, for (z-1) << 1

D-z(x) = limw->0 (teven0 - todd0) = (z-1)(Deven0 - Dodd0)

and finally,

G-(x) = Deven0 - Dodd0

So computing G or any of the other functions is simply a matter of applying the recurrence relations.

The derivative of x w.r.t w is obtained in a similar manner:

dx(w)/dw |w=0 = ( dx+(w)/dw |w=0 + dx-(w)/dw |w=0) / 2 = ( W+0 + W-0) / 2

Gap Facts

We now present some results. For integer n,

G+ (1/n) = 2/n - 1/n2
G- (1/n) = 1/n2.

G- (2/(2n+1)) = 1/(2n+1)2

G- (3/(3n+1)) = 1/(3n+1)2
G- (3/(3n+2)) = 1/(3n+2)2

G- (4/(4n+1)) = 1/(4n+1)2
G- (4/(4n+3)) = 1/(4n+3)2

G- (5/(5n+1)) = 1/(5n+1)2
G- (5/(5n+2)) = 1/(5n+2)2
G- (5/(5n+3)) = 1/(5n+3)2
G- (5/(5n+4)) = 1/(5n+4)2

G- (6/(6n+1)) = 1/(6n+1)2
G- (6/(6n+5)) = 1/(6n+5)2

And so on. I hope you see the obvious pattern for G-: Given any rational p/q, reduced so that p and q share no common factors, we have G-(p/q) = 1/q2



Copyright (c) 2000 Linas Vepstas All Rights Reserved.
To contact Linas, see his Home Page.