Barry Pilton investigates
continued fractions in

The Great Divide
Barry Pilton

Expressions such as

arise naturally in certain arithmetical problems. For typographical convenience this is usually written in the form

or just

[1; 2, 7, 8, 5].

It should now be clear what the generalisation of this to [a0.; a, a2, ... an] looks like when written out in full as in the above example. Such an object is known as a (finite) continued fraction. If the ai are restricted to take positive integer values, then the value of the expression is a positive rational number. Conversely, every positive rational can be expressed as a continued fraction, with a0 >= 0 and a1, a2, ... an >= 1. Such an expression Is not unique, since e.g. 2 = [2] = [1;1]; but if we also ask that an >= 2 it becomes unique.

For irrational numbers one is led to a consideration of infinite continued fractions
[a0; al, a2, .... ]
i to be the limit. as n --> co, of the sequence whose n-th term is the rational number
[a0; al, a2, .... an]

It is not too hard to show that this limit always exists and is a positive real number; and that every irrational number has a unique representation as an infinite continued fraction (again provided it is positive!) with a0 >= 0, al, a2, ... >= 1. The importance of continued fractions lies largely in the manner in which they provide good rational approximations to irrationals, as we shall see.

They can be approached, in the first instance, as a jolly sort of generalisation of fractions, and it is possible to exhibit all sorts of splendid formulae such as would gladden the heart of an Euler. (Indeed, he discovered most of them.) In particular there are several of theoretical importance concerning the convergents to the continued fraction, obtained by expressing [a0; al, ... an] in the form pn/qn with the p's and q's integers.

We take
p0 = a0, qo = 1
p1 = a1.a0 + 1, q1 = a1
and in general we have recurrence relations
pk+1 = ak+1pkpk-1, qk+1 = ak+1qk+qk-1.

The values of pk/qk are alternately greater than and smaller than the value alpha of the continued fraction. with p0/q0 < alpha

As an example we may take the continued fraction [1;1, 1, 1 ....]. If phi is its value, then clearly

phi = 1 + 1/phi

whence phi = 1/(1 + sqrt(5)), the 'golden number'. Successive convergents to phi are 1/1, 2/1, 3/2, 5/3, 8/5, 13/8,... and the qk, qk are just the Fibonacci numbers in sequence.

In fact, given any periodic continued fraction of the form

[a0; a1, ..., an, b1, ... , bm, b1, ... , bm, b1, ... , bm, ....]

its value must satisfy a quadratic equation with integer coefficients. Conversely, any irrational which satisfies such a quadratic equation has periodic continued fraction. For example.

SQRT(7) = [2; 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, ... ].

There are few known numbers, other than quadratic irrationals, whose continued fraction has any simple regular features. One such is:

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, .... ]

where the 2, 4, 6, ... are separated by pairs of 1's. On the other hand

pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, ... ]

has no known regularities. The value a4 = 292 is the largest known, the next being a73 = 161. For this reason [3; 7, 15, 1] gives a very close approximation to pi, namely 355/113.

Klein suggested a geometrical interpretation of the continued fraction to an irrational alpha.. Imagine a string stretched along the line y = alpha.x in the plane, with pegs erected at points on the integer lattice. If this string is tied down firmly at infinity and pulled aside at the origin, it will catch on pegs whose co-ordinates represent convergents to the continued fraction for alpha. (In some cases it will touch other pegs, representing so-called intermediate convergents, but at these it does not bend). As an example we give the:

Continued fractions are of great use in number theory; for example they can be used to solve the so-called (and wrongly so-called) Pell-equation:

x^2 = Ny^2 + 1

in integers x, y for a fixed non-square integer N > 0 (see Davenport [1]).

Distinctly deeper are their applications to the study of rational approximations to irrationals. If alpha is irrational and p, q are integers, then p/q will approximate to alpha provided | p/q - alpha | is small. The question is, what do we mean by small? If we make p and q large enough we can always make | p/q - alpha | as small as we please; so to make sense 'small' must be relative to the size of p, q. Since p is always about alpha.q it is the size of q which is crucial; our interest is directed towards making| p/q - alpha | < f(q) for various functions f of q. Given any q we can always find p to make:

| p/q - alpha | <= 1/2q

by dividing the line into intervals of length l/q and seeing which interval alpha falls into. If we insist on specifying q this is about the best we can expect. However, it can be shown that the convergents to the continued fraction for an irrational alpha, satisfy:

| p/q - alpha | < 1/(qn)^2

so that in general there are infinitely many solutions, in integers p, q, of the inequality | p/q - alpha | < l/q^2.

This suggests that the 'correct' formulation of our problem is to find functions f such that there are infinitely many solutions of the inequality

| pn/qn - alpha | < f(q). ... (**)

(Among other things, finitely many solutions to (**) might be coincidence, and do not in any real sense approximate to alpha.) The first thing to decide is whether or not our above result with f(q) = l/q^2 can be improved. It can be shown that one out of every two convergents of the continued fraction foralpha satisfies:

| pn/qn - alpha | < 1/2(qn)^2

and further, one out of every three convergents satisfies

| pn/qn - alpha | < 1/(sqrt(5).(qn)^2

Oddly. there is no improvement to this last statement if we consider more than three convergents; if alpha = phi, the ubiquitous golden number, then the best we can do in (**) is 1/sqrt(5).q^2. More information can be found in Davenport [1], or Hardy and Wright [2]. Before leaving the topic we must mention the theorem ot Roth (1955) that if alpha is algebraic and m > 2 then the inequality:

| p/q - alpha | < 1/q^m

has only finitely many solutions, so that algebraic irrationals are particularly short of good rational approximations.In the other direction, for any function f(q), no matter how rapidly decreasing, we can find alpha such that (**) has infinitely many solutions. If f decreases faster than1/q^2, such alpha must of necessity be transcendental.

There are also interesting measure-theoretic properties of continued fractions. Given any set of points on the real line:

it is often possible to define the 'length' of the set, more properly its 'Lebesgue measure'. Sets of measure 0 are in some sense small; a property P of real numbers is said to hold almost everywhere (or to be true of almost all numbers) if the set of numbers for which P is false has measure 0. For example, almost all reals are irrational, because the set of rationals has measure 0.

Using this we can obtain an idea of the 'usual' size of qn: there exists a constant gamma such that for almost all alpha:

n-th root(qn) --> gamma as n --> infinity

P.Levy [4] has obtained the weird formula for gamma:

gamma = e^((pi^2)/12.loge(2)

BIBLIOGRAPHY
1. H. Davenport: The higher arithmetic. Hutchinson.
2. G. H. Hardy and E.M.Wright: An introduction to the theory of numbers, OUP.
3. A. Ya. Khinchin: Continued fractions, Chicago.
4. P. Levy: Theorie de 1'addition des variables aleatoires, Paris.