From: Chris Hillman Subject: Re: fractional representations of decimals Date: Sat, 16 Jan 1999 18:56:09 -0800 Newsgroups: sci.math Keywords: Multi-dimensional analogues of (simultaneous) continued fractions On Thu, 14 Jan 1999, Michael Hamm wrote: > The number 0.43 can be represented by several fractions: 43/100 is perfect > in accuracy, but is unwieldy in that the denominator has three digits; 1/2 > is very wieldy (that's not a word, but you get my point), but is not very > accurate; and 3/7 is a good compromise. > > If there is some way of measuring unwieldiness (say, proportional to the > value of the denominator, or proportional to the number of its digits, or > something of the sort), and some way of measuring accuracy (say, percent > difference from actual value or something), then the two values could be > combined to form some sort of criterium for which is the best fractional > representation of a decimal. > > Has this been done? Yes; as several people have already pointed out, the basic theory you need (one-dimensional continued fractions) was already developed (by Dirichlet, Lagrange, Gauss, Galois, and others) by about 1840. Things really get interesting when you look at higher dimensional analogues and this is currently a fairly hot research topic. For that matter, by my count four Fields medalists have fairly recently published papers involving with connections between similar rational approximation problems and Kleinian groups, hyperbolic geometry, Julia sets, and related concepts, so even one dimensional continued fractions (which date back to the Greeks or even the Babylonians) remain a vital source of interesting problems. Indeed, I know of connections with pertubations of Hamiltonian systems (e.g. "stochastic webs", small divisors, mode locking), quasicrystals (e.g., "empires"), statistical mechanics (e.g. transfer operators, multifractal formalism), knot theory (e.g., "rational tangles"), string theory, and cryptography (e.g., lattice reduction and knapsack algorithm), among other things. Here is a brief sketch of some of the basic features of the theory. We want to approximate a line X in RP^d, spanned by some vector x in R^(d+1), by a "rational line" P which is spanned by an integer vector p in Z^(d+1). The "dual problem" (as Lunnon observed) is to find approximate identities among the coefficients of x involving small integers, e.g. (p,x) = p_1 x_1 + p_2 x_2 + .... p_{d+1} x_{d+1} ~ 0 One particularly attractive way of trying to solve such problems involves constructing a heirarchy of nested partitions of RP^d, analogous to the nested partitions involved in the familiar binary expansion of numbers in the unit interval; e.g. the tree of dyadic rational intervals [0, 1] [0, 1/2] [1/2, 1] [0,1/4] [1/4,1/2] [1/2,3/4] [3/4,1] ... ... ... ... which is constructed recursively using the arithmetic mean [p/q, p'/q'] [p/q, (p/q+p'/q')/2] [(p/q+p'/q')/2 p'/q'] may be replaced (in the case of the one-dimensional algorithm, in either the "fast" or "slow" versions) by the tree of Farey intervals: [0, 1] [0, 1/2] [1/2, 1] [0,1/3] [1/3,1/2] [1/2,2/3] [2/3,1] ... ... ... ... which is constructed recursively using the Farey mediant: [p/q, p'/q'] [p/q, (p+p')/(q+q')] [(p+p')/(q+q') p'/q'] This observation should clarify why continued fraction expansions may be regarded as analogous to base n "decimal" expansions. If d > 1, there are many distinct ways of measuring 1. the size of p, 2. the error of the approximation of L by P, but all reasonable choices yield similar results involving a "quality exponent" eta(P,L) such that error ~ size^(-eta) The naive algorithm says "round x to some integer vector p", and this usually results in eta ~ 1. Clever algorithms give larger eta values. Dirichlet 1842 showed that given any X in RP^d we can find infinitely many distinct rational lines with eta ~ 1 + 1/d. Schmidt 1970 showed this is the best possible -general- bound. When d=1, the euclidean algorithm (aka "slow" or "additive" one-dimensional continued fraction algorithm) actually enumerates the best possible approximations in order of "size". For instance, this algorithm very quickly tells you that there is no fraction with smaller denominator which approximates pi as well as 355/113. However, Lagarias has shown that if d > 1 we should only expect to find algorithms which -usually- provide near optimal approximations. The interesting thing for ergodic theorists and dynamical systems people is that you can formulate these algorithms in terms of dynamical systems, e.g. the skew product defined by a cocycle and an expanding map on RP^d, such that their behavior is controlled by the leading eigenvalues of a "transfer operator". Indeed, these algorithms provide very good examples for applying various techniques which have been developed over the past thirty years for studying dynamical systems (e.g. multifractal formalism, cohomology with values in nonabelian groups) and models in statistical mechanics (e.g. transfer operators, spectral gap theorems). In the case d=1, for instance, these techniques lead to results like these (for the "fast" algorithm): 1. size ~ 3.275^n 2. error ~ 0.093^n and also to a detailed analysis of a "heirarchy of irrationality" which classifies lines X in RP^d according to quality: eta(X) = limsup_{size(P) -> infty} eta(X, P) Essentially, for d=1 the "bad guys" are the quadratic irrationals which cannot have a better quality than 2, whereas algebraic numbers of higher degree can have larger qualities and transcental numbers (e.g. e) can even have infinite quality. Thus, even though by Dirichlet-Schmidt you cannot -guarantee higher- quality than 2, "most" irrational lines can in fact be very well approximated by "small divisor" rational lines. One can turn this around; instead of studying a problem in number theory using dynamical systems techniques, one recognizes that many phenomena (mode locking, KAM theory) in dynamical systems actually are number-theoretic phenomena in mild disguise. Or, if you prefer, topological phenomena under "deep cover" ;-) Chris Hillman