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.

x = 1/(a_{1} + 1/(a_{2} + 1/(a_{3} + ... )))

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_{+} = [a_{1}, a_{2}, ... , a_{N}]

and

x_{-} = [a_{1}, a_{2}, ... , a_{N}-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) = [a_{1}, a_{2}, ... , a_{N}, 1/w]

x_{-}(w) = [a_{1}, a_{2}, ... , a_{N}-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,

lim_{w->0} x_{-}(w) =
lim_{w->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_{--} = [a_{1}, a_{2}, ... , a_{N}-1, 0, 1]

This expansion invokes a symmetry on x_{-}(w):

x_{--}(w) = [a_{1}, a_{2}, ... , a_{N}-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 x_{e}(w) and x_{o}(w) as follows:

x_{e} = [ if (N even) x_{+} else x_{-} ]

x_{o} = [ if (N even) x_{-} else x_{+} ]

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

x_{o}(w) < x_{e}(w)

and, for negative real w,

x_{o}(w) > x_{e}(w)

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

These also have idempotent or parity-swapping identities:

x_{e+} = x_{e}
,
x_{e-} = x_{o}
,
x_{o+} = x_{o}
,
x_{o-} = x_{e}

x_{ee} = x_{e}
,
x_{eo} = x_{o}
,
x_{oe} = x_{e}
,
x_{oo} = x_{o}

x_{+e} = x_{e}
,
x_{+o} = x_{o}
,
x_{-e} = x_{e}
,
x_{-o} = x_{o}

F_{z}(x) = z/(a_{1} + z/(a_{2} + z/(a_{3} + ... )))

For any rational x, F_{z}(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
F_{z}(x_{+}(w)) and F_{z}(x_{-}(w)) in the obvious
way. Note, in particular, that the +/- and even/odd symmetries still apply:
in particular,

F_{z}([a_{1}, a_{2}, ... , a_{N}-1, 0, 1, 1/w] ) =
F_{z}([a_{1}, a_{2}, ... , a_{N}-1, 1/w] )

It is in the analysis of F_{z} 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) = lim_{w->0}
[ F_{z}(x_{even}(w)) - F_{z}(x_{odd}(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) = lim_{w->0}
[ F_{z}(x_{+}(w)) + F_{z}(x_{-}(w)) ]
= lim_{w->0}
[ F_{z}(x_{even}(w)) + F_{z}(x_{odd}(w)) ]

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

G^{-}(x) = lim_{z->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/q^{2} (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 p_{1}/q_{1} and p_{2}/q_{2}
then
p_{1}/q_{1} <
(p_{1}+p_{2})/(q_{1}+q_{2}) =
p_{3}/q_{3} < p_{2}/q_{2}
is true and
p_{2}q_{1} = 1+p_{1}q_{2} is also true.
Now we need to search for a fraction m/n with the smallest possible
denominator n that satisfies
p_{1}/q_{1} < m/n < p_{2}/q_{2}.
Clearly, n =< q_{1}+q_{2}, 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,
(p_{1}+p_{2}-1) /
(q_{1}+q_{2}-1) =<
p_{1}/q_{1}
and
p_{2}/q_{2} =<
(p_{1}+p_{2}) /
(q_{1}+q_{2}-1)
therefore
(q_{1}+q_{2}-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 = (q_{1}+q_{2}) is the smallest denominator, and thus,
the largest gap, that can occur between
p_{1}/q_{1} and p_{2}/q_{2}.
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'.

s_{k} = a_{k} + 1/s_{k+1}

That is, we've defined s_{k} such that x = 1/s_{1}. It is handy
to also define a_{0}=0 so that we can write x = s_{0}.
The corresponding term in F_{z}(x) is t_{k} with

t_{k} = a_{k} + z/t_{k+1}

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

t_{k} =
s_{k} + w W_{k} + (z-1)D_{k} + w(z-1)E_{k}

By applying the recurrence relation for t_{k} we can deduce the recurrence
relations for each of these pieces:

D_{k-1} = (1 - D_{k}/s_{k})/s_{k}

W_{k-1} = - W_{k}/s_{k}^{2}

E_{k-1} = - (W_{k} + E_{k})/s_{k}^{2}

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

s_{N} = a_{N}
,
D_{N} = 0
,
W_{N} = 1
,
E_{N} = 1

and for F(x_{-}) we have

s_{N} = a_{N}
,
D_{N} = 1
,
W_{N} = -1
,
E_{N} = -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,

F_{z}(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) =
lim_{w->0} (t^{even}_{0} - t^{odd}_{0}) =
(z-1)(D^{even}_{0} - D^{odd}_{0})

and finally,

G^{-}(x) = D^{even}_{0} - D^{odd}_{0}

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

G^{+} (1/n) = 2/n - 1/n^{2}

G^{-} (1/n) = 1/n^{2}.

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/q^{2}

Copyright (c) 2000 Linas Vepstas
All Rights Reserved.

To contact Linas, see his
Home Page.