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