Empires in Sturmian Systems
by
Chris Hillman
Mathematics, University of Washington

Note: this is the abstract for a "virtual talk" which will probably not be given, since it has only just become possible (March 12) for me to attend to conference. I am posting it at the suggestion of Mike Boyle. I would be happy to discuss this work in private with anyone interested.

Empires were introduced by J. H. Conway in the context of Penrose tilings, but in fact this concept is quite general. In a subshift X, the cylinder Z(\alpha) of a word \alpha is the set of all sequences in which alpha appears. Here, it is understood that a word has a particular location; the orbit of a word under the shift is called a protoword. The empire E(\alpha) is the set of all words which appear in every sequence in which alpha appears. The lattice of empires is dual to the lattice of cylinders. A kingdom is a word, kappa, which be can extended in at least two ways at both ends. K(alpha) is the smallest kingdom containing alpha. I have determined the empires of the classical Sturmian shifts X(v), where 0 < v < 1 is a parameter. If v is irrational then (with one exception), the empire E(alpha) can be described as K(alpha) flanked by an infinite, quasiperiodic array of strictly smaller kingdoms. Moreover, for each v, the protokingdoms form a sequence of nested protowords which can be determined in a very simple way from the continued fraction of v (this is closely related to Stern-Brocot and Farey trees; the protokingdoms are simply "headwords" of the so-called Christoffel sequence x0 in X(v).) A more complete description of this phenomenon (with some detailed examples) may be found at the URL http://www.math.washington.edu/ hillman/PUB/Fibonacci The shifts X(v) can be generalized to Z^d-shifts by considering "digital approximations" to p-flats in R^(p+q). Here, a p-flat x+W is a translate of a p-dimensional subspace W and a digital approximation to x+W is a surface of p-dimensional facets with vertices in Z^(p+q), which remains "close" to x+W. The shifts X(v) arise as digital approximations to lines in R^2. By projecting the digital approximation into the flat, one obtains a Sturmian tiling (aka generalized Penrose tiling) of R^p. (This construction is due to N. G. de Bruijn.) Such tilings have a hierarchical nature: every digital approximation to a p-flat in R^(p+q) decomposes into p+q families of "terraces" separated by short "retaining walls", or just "walls" for short. These walls are digital approximations to (p-1)-flats in their own right. By considering p families of terraces, one constructs Z^p symbolic shifts X_J(W) whose symbols are certain ßupertiles" of the Sturmian tiling. (This construction is due to E. A. Robinson.)Once again, if one studies how the empires and other properties of the digital approximations (or Sturmian tilings or Robinson shifts) change as you vary W, one constructs a tree of partitions of the Grassmannian G(p, q) analogous to the Farey tree, which leads to connections with multidimensional continued fractions. As this would suggest, the nature of not only the empires, but other characteristics of "Sturmian languages", such as approximate periods, the catalog of allowed patches, the frequencies of patches (which define a unique invariant measure), the sequence of approximations by Markov shifts or by finite type shifts, and the nature of ßingular" tilings, are all determined by this generalized Farey tree; that is, by a sort of generalized continued fraction expansion of W. The work reported here is part of my thesis research; my page http://www.math.washington.edu/ hillman/research.html will hopefully soon have a link to a summary of this (with illustrations).

Date received: March 14, 1998

Copyright © 1998 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cabe-18.