## 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:

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