From: Chris Hillman Newsgroups: sci.math Subject: Re: Fibonacci continued fraction Date: Thu, 23 Oct 1997 15:38:34 -0700 On Wed, 22 Oct 1997, soen wrote: > BTW, I recently looked at Venkov's "Elementary Number Theory". He > gives some interesting brief history and repeats Markov's development > of relationships between continued fractions [a1,a2,a3,...] and > "characteristics" of irrationals. He says that Christoffel coined the term > "characteristic" of a real number r, to mean the string of 0's & 1's > defined by floor((n+1)r) - floor(nr), for n=1,2,3,.... > > (The infinite Fibonacci string "1011010110110...", appearing in S(x) > when written in base x, i.e., S(x)=(x-1)*(0.1011010110110...)(base x), > happens to be the characteristic of 1/phi, i.e. of (sqrt(5)-1)/2.) This is related to current research on modeling "quasicrystals" by means of "quasiperiodic tilings". A periodic tiling has the property that displacing it by the correct amount gives an exact agreement; a quasiperiodic tiling has the property that by displacing it by a well chosen amount you can get exact agreement over say 99.99% of the space in which the tiles are placed (or 99.999%, or whatever, choosing a different and larger displacement each time). If you make a photocopy on a transparent sheet of plastic of a picture of a Penrose tiling you can test this out for yourself. One particularly nice class of quasiperiodic tilings (including Penrose tilings, the Ammann octagonal tilings, and quasiperiodic tilings of the line, including the Fibonacci tilings under discussion) can be defined as arising by taking a "digital approximation" in the m-skeleton of the cubical lattice Z^(m+n) to an m-dimensional plane W in R^(m+n). For instance, the Fibonacci tilings can be realized when (m,n) = (1,1) and the Penrose tilings can be realized when (m,n) = (2,3). For each choice of W you get an entire space of tilings having the same combinatorial and statistical properties (e.g. which tiles can appear next to each other, and with what frequencies). (This is a slight oversimplification, actually, but never mind.) I have been studying how such properties of these "Sturmian tiling spaces" (aka "generalized Penrose tiling spaces") change as you vary W; there are interesting "bifurcations" at "rational positions" for W. In the case (1,1), the Sturmian tilings are very closed related to the so-called Sturmian shift spaces, an important example of a "rigid" symbolic dynamical system. There is an active school of research examining connections between formal language theory and automata theory, and these Sturmian shifts and certain relatives of them. The "characteristic" is in this case simply the slope of the line W in R^2. In the case of Penrose tilings, incidently, the "slopes" describing how the two dimensional plane W sits in R^5 involve the Golden ratio phi, which means that you can construct "good displacements" or what I call "magic shifts" by truncating the continued fraction expansion of phi and using the resulting "best rational approximations" to construct the desired displacements. In general, one can also construct periodic approximations to a given Sturmian tiling space by constructing "rational approximations" to W; this idea gives a strong connection with the complex and vexed topic of higher dimensional continued fraction algorithms (to make a long story short, in higher dimensions at least some of the nice properties of the one dimensional algorithm will break down). The "bifurcations" in the (1,1) case turn out to be very closely connected to the continued fraction expansion of the slope of the cut line W. In higher dimensions things are more complex. There is an amusing true story connected with this, by the way. From the classical theory of continued fractions we know that phi is the irrational (or more precisely, one representative of a class of irrationals) which is "hardest to approximate" by small denominator rationals. Kimberly-Clarke had a problem with quilted toilet paper--- the ink patterns would cause adjacent sheets to stick to one another if the patterns happened to line up exactly. So someone had the idea of using a pattern obtained by modifying Penrose tiling, probably only because this tiling is aperiodic. But in fact the number theory shows that this particular tiling is a very good choice, because other Sturmian tiling spaces are easier to approximate by W spanned by "small integer" vectors. Anyway, at the present time, Roger Penrose, the inventor (discoverer?) of Penrose tilings, is suing Kimberly-Clarke for copyright infringement. Another particularly interesting characteristic of Sturmian tiling spaces is that placing a finite number of tiles in general completely determines the tiling over say 20% of the m dimensional space in which the tiles are placed. This is the phenomenom of "empires" first noted by J. H. Conway in the context of Penrose tilings; however I have observed (unpublished) that this notion is completely general, in fact in makes sense in any symbolic dynamical system. The fact that the Sturmian empires are so large reflects the extraordinary "rigidity" of these dynamical systems, which in turn arises ultimately from the number theory of "linear Diophantine approximation" implied by the digital approximation method of producing such tilings. Incidently, I have observed (unpublished) that if you make nonlinear perturbations of the plane W, you obtain nonlinear dynamical systems and observe mode locking phenomena analogous to the famous sine-circle map of V. I. Arnold. In fact, in the case (1,1) you obtain the shift system which is to the sine-circle map as the Sturmian shifts are to a rotation of the circle. For an overview of Sturmian tilings, see the discussion of the projection method, multigrid method, and oblique tiling method of producing quasiperiodic tilings in the book Author: Senechal, Marjorie. Title: Quasicrystals and geometry / Marjorie Senechal. Pub. Info.: Cambridge ; New York : Cambridge University Press, 1995. LC Subject: Quasicrystals. Crystallography-Mathematical. Anyone interested can email me for references to recent research papers on Sturmian tilings and related subjects (warning! the literature is enormous and spread over math, physics, and crystallography journals). (A warning to those who know something about Penrose tilings: in general, very few Sturmian tilings can be produced by matching rules analogous to the Penrose edge markings; even when such rules exist they are often nonlocal. There is an interesting connection between a partially deterministic method of producing Penrose tilings and the shapes of the patches of perfect agreement which arise by displacing the Penrose tilings. Another warning: very few Penrose tilings, in fact very few Sturmian shifts, can be produced by an "inflation" analogous to the Penrose inflation.) Chris Hillman