Multidimensional Symbolic Systems: Growth, Entropy and Computability
Associated People:
Tom Meyerovitch (University of British Columbia)
Associated Sites:
PIMS University of British ColumbiaAssociated PIMS Programs:
Suppose you have are to tile the plane by placing colored square tiles on a grid. Each of the tile has a color, which we number from 1 to n. You are given some local adjacency constraints on placing colored tiles: There are pairs of colors i and j so that a tile of color i can not be placed directly to the left of a tile of color j, and other pairs l and m so l can not be placed directly below a tile with color m. A tiling is called admissible if it doesn’t violate the constraints. The collection of admissible tailings for a given set of constraints is a two-dimensional symbolic system or a subshift of finite type. Models of this type arise as in a wide range of scientific and engineering applications such as statistical mechanics and data encoding. The study of systems of this kind is a part of the mathematical field known as symbolic dynamics.
There is much interest, both theoretical and practical, in analyzing the number of admissible tilings of a finite region, and its growth rate as a function of the area of that region. A central notion in symbolic dynamics is the topological entropy of a subshift X: This is the exponential growth rate of the number admissible tilings of a finite region, normalized by the area of the region. Getting closed-form expressions for the entropy of a system has been attempted for many models. There are a few examples for such “exactly solved models”, and these are often remarkable mathematical derivations, as in E. Lieb’s celebrated computation for the entropy of the “square ice” model [Leib, 1967].
A result of Hochman and Meyerovitch [Hochman & Meyerovitch, 2010] states that any non-negative real num- ber for which there is a computable sequence of numbers approximating it from above is the entropy of some two-dimensional subshift of finite type. The converse is also true, by a result of S. Friedland [Friedland, 1997]: For any subshift of finite type there exist an approximation sequence It has been demonstrated in [Meyerovitch, 2011] that for some subshifts of finite type the number of admissible tilings of a finite region can grow sub-exponentially in the volume of the region. The normalizing constant which is the exponent of the volume is called the entropy dimension. Any non-negative number satisfying some explicit recursive-theoretic properties can be obtained as the entropy dimension of a multi-dimensional subshift.
The above results are manifestations of the richness of this class of models, and of connections between multi-dimensional symbolic dynamics and the theory of computability. A remarkable result in this direction was obtained by Hochman [Hochman, 2009]: Under mild technical conditions, any computable dynamics can be represented by some multi-dimensional subshift of finite type.
References
- T. Mayerovitch Growth-type invariants for Zd subshifts of finite type and arithmetical classes of real numbers Inventiones Mathematicae, 176:131–167, 2009
- S. Friedland On the entropy of Zd subshifts of finite type Linear Algebra Appl., 252:199–220, 1997
- M. Hochman On the dynamics and recursive properties of multidimensional symbolic systems Inventiones Mathematicae, 176:131–167, 2009.
- M. Hochman, T. Meyerovitch A characterization of the entropies of multidimensional shifts of finite type Annals of Mathematics, 171:2011–2038, 2010
- E. Leib Residual Entropy of Square Ice Physical Review, 162:162–172, 1967