Continued Fractions from Euclid till Present

Ilan Vardi

IHES, Bures sur Yvette

Algorithms Seminar

October 19, 1998

[summary by Philippe Flajolet]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Continued fractions have fascinated mankind for centuries if not millennia. The timeless construction of a rectangle obeying the ``divine proportion'' (the term is in fact from the Renaissance) and the ``self-similarity'' properties that go along with it are nothing but geometric counterparts of the continued fraction expansion of the golden ratio,
fº
1+(5)1/2
2
=
1
1+
1
1+
1
1+···
.

Geometry was developed in India from the rules for the construction of altars. The Sulva Sutra (a part of the Kalpa Sutra hypothesized to have been written around 800 BC) provides a rule1 for doubling an area that corresponds to the near-equality:
(2)1/2 ·
=		 1+
1
3
+
1
3×4
-
1
3×4×34
     (correct to 2  10-6).     (1)
Exclusively for these seminar proceedings, we propose the original observation that the third and fourth partial sums in (1), namely 17/12 and 577/408, are respectively the fourth and eighth convergents to (2)1/2.

Accordingly, in the classical Greek world, there is evidence of knowledge of the continued fraction for (2)1/2 which appears in the works of Theon of Smyrna (discussed in Fowler's reconstruction [6] and in [17]) and possibly of Plato in Theaetetus, see [3]. As every student knows, Euclid's algorithm is a continued fraction expansion algorithm in disguise, and Archimedes' Cattle Problem (circa 250 BC) most probably presupposes on the part of its author some amount of understanding of quadratic irrationals, Pell's equation, and continued fractions; see [17] for a discussion.

The continued fraction convergent p»355/113 was known to Tsu Ch'ung Chi born in Fan-yang, China in 430 AD. More recently, the Swiss mathematician Lambert proved the 2,000 year conjecture (it already appears in Aristotle) that p is irrational, this thanks to the continued fraction expansion of the tangent function,
tan z =
z
1-
z2
3-
z2
5-···
,
and Apéry in 1979 gave in ``a proof that Euler missed'' [12] nonstandard expansions like
z(3)º
¥
å
n=1
1
n3
= 1+
1
2·2+
13
1+
13
2·6+
23
1+
23
2·10+
33
1+···
,
from which the irrationality of z(3) eventually derives.

Earlier, Euler had estimated that
¥
å
n=0
(-1)n n! = 0.596 347 362 ...
by means of a formal continued fraction expansion of the series ån n!(-z)n. A famous memoir of Stieltjes contains many other series identities like
ó
õ
¥


0
tanh u  e-zu  du=
1
z2+
1·2
1+
2·3
z2+
3·4
1+
4·5
z2+···
,
which, a century later, enabled the author of this summary to provide the first analyses in a dynamic context of some basic data structures of computer science. The fascination continues and in 1985, Gosper found 17 million continued fraction digits of p, which corresponds to about 18 million decimal digits. Such quests are by the way not totally senseless: for instance, from similar data, we can know for sure that, should Euler's constant g be rational, then its numerator and denominator would have at least 242,080 decimal digits (Papanikolaou, 1997)!

1   Arithmetica

This brilliant and erudite talk (see especially [14, 15]) discusses the many facets of standard (or ``regular'') continued fraction expansions of real numbers, which will be written occasionally as
x=[a0,a1,...]   if   x=
1
a0+
1
a1+···
.
One refers to the aj as continued fraction digits or partial quotients (thinking of Euclid's algorithm).

The best approximant properties of continued fractions are well-known [7]. Indeed, any convergent p/q (obtained by a finite truncation) of the continued fraction expansion of a approximates a better than any other fraction with a smaller denominator and better even than many with a larger denominator (compare p with 16/5,314/100 against 22/7).

A fruitful consequence of the best approximation property is the following: let D be a non-square and let p/q be a ``good'' approximant of (D)1/2. Then, p2-q2D is small. In particular, as discovered by Lagrange, the continued fraction expansion of (D)1/2 hides a solution to Pell's equation, p2-Dq2=1. The solutions are essentially powers of a minimal solution that corresponds to a so-called fundamental unit of Q((D)1/2). Archimedes' Cattle Problem can be solved in this perspective, the full solution involving numbers with 206,545 digits! In an entertaining note [17], Vardi even shows that the solution can be enounced with only a few symbols: the total number of cattle is
é
25194541
184119152
(109931986732829734979866232821433543901088049
+ 50549485234315033074477819735540408986340 (4729494)1/2)4658 ù.

Continued fraction algorithms and the Euclidean algorithm are central to many other areas of number theory. For instance, Rademacher observed that the Jacobi symbol (d/c) (that tells us in essence whether d is a square modulo c) is expressible as
æ
ç
ç
è
d
c
ö
÷
÷
ø		 =(-1)
(3-d-(d-1mod c)+ cå (-1)i ai)/4
 
,     (2)
where d/c=[0,a1,...,ar] with r even. In fact, the exponent in (2) is closely related to the Dedekind sum classically defined as
s(d,c):=
c-1
å
h=1
((hd/c))((h/c)),     (3)
where the symbol ((x)) signifies 0 if x is an integer and x-ë xû -1/2 otherwise (see also the last section, especially formula (5)). Zagier discovered that the continued fraction expansion ``by excess'',
d
c
=b0-
1
b1-
1
b2-
1
b3-···
gives rise to an identity related to (2) (and to (5) below),
s(d,c)=
1
12
æ
ç
ç
è		 -6+
c+(c-1mod d)
d
-
 
å
i
(bi-3) ö
÷
÷
ø		 .     (4)

In fine, properties of the type (2) and (4) result from simple matrix algebra, the point being that linear fractional transformations that arise from continued fractions are generated by S(z)=z+1, and T(z)=-1/z, and are representable as 2×2 integer matrices of determinant 1, i.e., the group SL(2, Z), while there is exactly one additive character on this group.

Amongst other interesting connections, we find Cornacchia's deterministic algorithm (1908) that makes it possible to write a prime as a sum of two squares directly from the Euclidean algorithm. (Legendre and Hermite had already introduced continued fractions for this problem.) Continued fraction algorithms are discussed in the celebrated HAKMEM (``Hackers' Memorandum'') document [2], a text well worth reading.

2   Statistica

Examination of large slices of digits in continued fraction expansions of real constants (like p,g,z(3) and many others, but unlike f or e) reveals that the digits 1,2,3,... tend to occur with a frequency that shows little deviation from the values 41%, 17%, 9%,..., respectively. Such observations belong to the ``metric'' or ``statistical'' theory of continued fractions. They are essentially related to properties of the continued fraction transformation T(x)={1/x} (with {·} the fractional part function) under iteration.

Gauss first observed around 1800 that the probability density
y(x)=
1
log 2
1
1+x
,
is invariant under the transformation T, as a simple computation based on partial fractions shows. The corresponding measure is called Gauss' measure. It was then natural to conjecture (and so did Gauss) that iteration of T on random data that obey a probability density, for instance a uniform (0,1) density, produces distributions that converge to the invariant y.

Nowadays, we know two approaches to such problems: one, more qualitative, is based on ergodic theory, while the other, more precise, is based on functional analysis (following Kuzmin, Lévy, Wirsing) and transfer operators (following Ruelle, Babenko, Mayer, Hensley, Vallée). Indeed, the ergodic theorem grants us that properties of trajectories of real numbers under x are governed (almost surely) by Gauss' measure, while functional analysis identifies y with the dominant eigenfunction of the transfer operator G1, where
G s[f](x)=
¥
å
m=1
1
(m+x)2s
f(
1
m+x
).

Properties of Gauss' measure give access to properties of continued fraction digits. For instance, the limit frequency of digit k in the continued fraction expansions of a random real number is (with probability 1) equal to
vk = ó
õ
1/(k+1)


1/k
y(x)  dx=log2 æ
ç
ç
è		 1+
1
k(k+2)
ö
÷
÷
ø		 ,
so that vk=O(k-2) has a ``soft'' tail (and infinite expectation). From this type of argument, one can characterize expected properties of continued fractions of real numbers. One has, almost surely, for any function f that is not too wild,
 
lim
n®+¥
1
n
( f(a1(x))+...+f(an(x)) ) =Kf=
¥
å
k=1
f(k)log2 æ
ç
ç
è		 1+
1
k(k+2)
ö
÷
÷
ø		 .
For instance, the geometric and harmonic means of partial quotients satisfy (almost surely)
([)1/2n]a1··· an ® e
K
 
log
 
,   e
K
 
log
 
=
¥
Õ
k=1
æ
ç
ç
è		 1+
1
k(k+2)
ö
÷
÷
ø
log2 k



 
n
1
a1
+...+
1
an
®
1
K
 
inv
,   K
 
inv
=
¥
å
k=1
1
k
log2 æ
ç
ç
è		 1+
1
k(k+2)
ö
÷
÷
ø		 .
Such constants can be evaluated systematically by the ``zeta-function trick'' discussed in Vardi's book [13]. One finds the values
e
K
 
log
 
·
=		 2.68554,    
1
K
 
inv
·
=		 1.74540,
where the first one is known as Khinchine's constant and the second one is the harmonic mean constant [1]. See Finch's beautiful site on Constants [5] for details and pointers to original sources. For instance, the harmonic mean of the 17 million continued fraction digits of p, as computed by Gosper, is 1.74594, a fact that that brings additional credibility to the conjecture that the continued fraction expansion of p is ``normal'' (that is, random-looking).

A similar type of question is: How much information does a continued fraction digit convey? This conduces to Lévy's constant that is related to the entropy of the continued fraction map. For x a number of the interval (0,1), let us write
Pn(x)
Qn(x)
= [0,a1(x),...,an(x)].
Lévy proved that (almost surely)
 
lim
n®¥
1
n
log Qn(x) ®
p2
12log 2
,
by making use of an approximation of the type
log Qn(x) »
n
å
k=1
log Tk (x),
to which ergodic theory can be applied. Since the fundamental interval2 of rank n that is determined by x has length about 1/Qn(x)2, there results that very roughly,
Qn(x)-2 » æ
è		 e
p2/(6log 2)
 
ö
ø
n

 
·
=		 10-1.03064 n.
In other words, n continued fraction digits discriminate a number as well as about 1.03064 n decimal digits. (This is again consistent with Gosper's data on the number p.) Refinements on Lévy's estimates are due to Philipp (who first proved that the distribution of log Qn(x) is asymptotically Gaussian) and many others. Lévy's constant also appears (for good reasons, see Vallée's works, e.g., [11]) in the mean number of iterations of Euclid's algorithm which, for rational numbers p/q with 1£ p<q£ n, is
12log 2
p2
log n +O(1).
This last estimate is due to Heilbronn and Dixon around 1969. A companion Gaussian limit distribution further holds, which is a ``hard'' result due to Hensley, 1994.

Arithmetic means of partial quotients take us to a different circle of ideas and the probabilistic phenomena at stake become now quite irregular. Define the sum-of-digits function,
Sn(x)=
n
å
k=1
ak(x).
The point is that the mean value of a continued fraction digit satisfies
¥
å
k=1
k log æ
ç
ç
è		 1+
1
k(k+2)
ö
÷
÷
ø		 =+¥.
Thus, the arithmetic means Sn/n do not behave at all like their geometric or harmonic counterparts: exceptionally large values of partial quotients an and of sums Sn are to be encountered not too infrequently.

This part of the discussion aims at understanding the finesses of large fluctuations in continued fraction digits. First, a Borel-Cantelli argument shows that, given any function f(n), then (with l the Lebesgue measure)
l { xÎ(0,1) : an(x) > f(n) (infinitely often) } =1   ÜÞ     å
1
f(n)
=+¥.
Thus, we should expect an>n log nloglog n infinitely often, but an<n log n(loglog n)2 only at a finite number of places. In fact, Khinchine proved that
l ì
í
î		 x :  ½
½
½
½
Sn(x)
nlog2 n
-1 ½
½
½
½		 >e ü
ý
þ		 ¾®
 
n®¥
0,
for any e. In other words, the arithmetic mean of n digits is ``typically'' close to log2n.

Heinrich [8] obtained a more precise limiting distribution result: for any xÎR and with µ the Gauss measure:
µ ì
í
î		 x : 
1
n
å
n
 
 
k=1
a
 
k
(x)-
log n-g
log2
<t ü
ý
þ		 -G
 
1,1
æ
ç
ç
è		 t,
p
2log2
ö
÷
÷
ø		 =O æ
ç
ç
è
(log n)
2
 
n
ö
÷
÷
ø		 .
There g denotes Euler's constant and G1,1(t,l), is the stable distribution function whose characteristic function equals
exp(-l| u| (1+2ilog| u| sgnu/p)).
Diamond and Vaaler further established, in a precise sense, that for almost all x's, there is at most one large partial quotient an(x): one has
æ
ç
ç
è		 Sn(x)-
 
max
k³ n
ak(x) ö
÷
÷
ø		 ~ nlog2 n,
with probability 1. Finally, the St. Petersburg game (play head-and-tails and double the stake till you win) is a well-known example of a sequence of i.i.d. random variables with infinite expectation and was considered as a paradox since no single `fair' entry fee exists. In relation with the discussion of arithmetic means, Vardi's note [16] shows how the sequence of continued fraction digits of a random real number makes a reasonable choice of entry fees.

In the discrete world, these results indicate that the running time of the subtractive Euclidean algorithm (equal to the sum of the continued fraction digits) should be about log nlog log n, in the sense that if S(p/q) is the running time, then S(p/q)/(log qlog log q) should have a limiting distribution (consistent with Heinrich's result). This would imply that typically, the subtractive algorithm is more expensive than the standard algorithm by a factor of log log n. Knuth and Yao showed that, on average, the sum of all the partial quotients of all the regular continued fractions for m/n, with 1£ m£ n, is
6
p
2
 
n(log n)
2
 
+O(nlog n(loglog n)2),
where Lévy's constant pokes its nose again. (See Vallée's recent works [11] for the light shed by transfer operators on such phenomena.) This tells us that the average behavior of the subtractive algorithm is much different from its typical behaviour. Such results are not uncommon in number theory, e.g., in divisor problems; see [10].

3   Analytica

The last part of the talk is based on Vardi's paper [15]. The aim is to characterize the distribution of the alternating sum-of-digits
Tn(x):=
n
å
k=1
(-1)k ak(x),
for the continuous case, and of the discrete counterpart
T(d/c)=Tr(d/c),  where   d/c=[0,a1,...,ar].
The mathematics go deeper and involve the hyperbolic Laplacian, Kloosterman sums, modular forms, and Eisenstein series. (See Sarnak's introductory lectures [9] for some related background.) The motivation comes largely from the need to understand the distribution of Dedekind sums defined in (3) that also satisfy a formula of Dean Hickerson (compare with Zagier's formula (4)), namely
s(d,c)=
1
12
æ
ç
ç
è		 -3+
d+(d-1mod c)
c
-
r
å
i=1
(-1)iai ö
÷
÷
ø		 ,     (5)
where the regular continued fraction expansion of d/c=[0,a1,...,ar] is normalized in such a way that r is even. This formula shows that Dedekind sums should really be thought of as alternating sums of regular continued fraction coefficients.

First, in the continuous case, the distribution of Tn is likely to resemble the difference between two random variables of the Sn type, themselves each distributed according to a G1,1 stable law as discussed earlier (Heinrich's theorem). Now the difference of two G1,1 is a Cauchy distribution, so that we are led to expect
 
lim
n®¥
l { x : Tn(x)<yn } =
1
p
ó
õ
y


-¥
x
x2+x2
  dx,     (6)
with x=p/(2log2).

In the discrete case, Vardi [15] has succeeded in proving that an analogue of (6) holds. In the language of Dedekind sums, the main result of [15] is then
 
lim
n®¥
#{0<d<c<n, (d,c)=1,s(d,c)<xlog c}
#{0<d<c<n,(d,c)=1}
=
1
p
ó
õ
x


-¥
(2p)-1
(2p)-2+s2
  ds
    (7)
 
=
1
p
arctan(2p x)+
1
2
.
(By Hickerson's formula (5), this gives the very same limiting distribution result for the alternating sum of continued fraction coefficients.) The proof uses the full machinery of modular forms and harmonic analysis on SL(2, Z), see [9]. It would be of interest to find a simpler proof, as this would very likely have the advantage of providing the limiting distribution for the sum of continued fraction coefficients. The fact that there is a unique additive character for SL(2, Z) makes it unlikely that this could be obtained using harmonic analysis.

References

[1]
Bailey (David H.), Borwein (Jonathan M.), and Crandall (Richard E.). -- On the Khintchine constant. Mathematics of Computation, vol. 66, n°217, 1997, pp. 417--431.

[2]
Beeler (M.), Gosper (R. W.), and Schroeppel (R.). -- HAKMEM. -- Memorandum n°239, M.I.T., Artificial Intelligence Laboratory, February 1972. Available on the WorldWide Web at http://www.inwap.com/pdp10/hbaker/ hakmem/hakmem.html.

[3]
Caveing (J.). -- L'irrationalité, dans les mathématiques grecques jusqu'à Euclide. -- Presses Universitaires du Septentrion, Paris, 1998.

[4]
Dutt (Romesh Cunder). -- A History of Civilisation of Ancient India Based on the Sanskrit Literature. -- Vishal Publishers, Delhi, 1972. A reprint of the original edition, 1888.

[5]
Finch (Steven). -- Favorite mathematical constants. -- Available on the World Wide Web at the URL http://www.mathsoft.com/asolve/constant/constant.html, 1995.

[6]
Fowler (D. H.). -- The Mathematics of Plato's Academy: A New Reconstruction. -- Clarendon Press, Oxford, 1987.

[7]
Hardy (G. H.) and Wright (E. M.). -- An Introduction to the Theory of Numbers. -- Oxford University Press, 1979, fifth edition.

[8]
Heinrich (Lothar). -- Rates of convergence in stable limit theorems for sums of exponentially y-mixing random variables with an application to metric theory of continued fractions. Mathematische Nachrichten, vol. 131, 1987, pp. 149--165.

[9]
Sarnak (Peter). -- Some Applications of Modular Forms. -- Cambridge University Press, 1990, Cambridge Tracts in Mathematics, vol. 99.

[10]
Tenenbaum (Gérald). -- Introduction to analytic and probabilistic number theory. -- Cambridge University Press, Cambridge, 1995, xvi+448p. Translated from the second French edition (1995) by C. B. Thomas.

[11]
Vallée (Brigitte). -- A unifying framework for the analysis of a class of Euclidean algorithms. -- Preprint, 2000. To appear in Proceedings of LATIN'2000, Lecture Notes in Computer Science, in press.

[12]
Van der Poorten (Alfred). -- A proof that Euler missed ... Apéry's proof of the irrationality of z(3). Mathematical Intelligencer, vol. 1, 1979, pp. 195--203.

[13]
Vardi (Ilan). -- Computational Recreations in Mathematica. -- Addison Wesley, 1991.

[14]
Vardi (Ilan). -- The distribution of Dedekind sums. -- Preprint, October 1992. 20 pages.

[15]
Vardi (Ilan). -- Dedekind sums have a limiting distribution. International Mathematics Research Notices, n°1, 1993, pp. 1--12.

[16]
Vardi (Ilan). -- The St. Petersburg game and continued fractions. Comptes Rendus de l'Académie des Sciences. Série I. Mathématique, vol. 324, n°8, 1997, pp. 913--918.

[17]
Vardi (Ilan). -- Archimedes' cattle problem. The American Mathematical Monthly, vol. 105, n°4, 1998, pp. 305--319.
1
``Increase the measure by its third part, and this third part by its own fourth, less the thirty-fourth part of that fourth''. See vol. I of Dutt's book [4, p. 272] for context including otherwise rational approximations to (p/4)1/2.
2
The fundamental interval of rank n determined by x is defined by all the numbers whose representation starts with [0,a1(x),...,an(x)].
This document was translated from LATEX by HEVEA.