Multidimensional Symbolic Systems: Growth, Entropy and Computability

Associated People:

Tom Meyerovitch (University of British Columbia)

Associated Sites:
PIMS University of British Columbia
Associated PIMS Programs:

PIMS Postodoctoral Program

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.