Computing the entropy of multidimensional subshifts of finite type

ABSTRACT :

Multidimensional subshifts of finite type are discrete dynamical systems as a set of colorings of an infinite regular grid with elements of a finite set A together with the shift action. The set of colorings is defined by forbidding a finite set of patterns all over the grid (also called local rules). The most simple and most considered grids of this type are Z2 and more generally Zd for d = 1. In this case, one can consider a coloring as a bi-dimensional and infinite word on the alphabet A.

They are notably involved in statistical physics in the study of so-called lattice models. These models are often simple to describe: for instance, the hard square model is defined on alphabet A = {0, 1} and by forbidding two 1 to appear on horizontally or vertically adjacent positions of the lattice. However, these models and their physical constants, such as the entropy are difficult to apprehend with general methods, and involve specific properties of the considered model.

Although it is known that it is possible to compute the entropy of one-dimensional version of these models by computing the greatest eigenvalue of a matrix which derives from the description of the subshift, this is not possible for multidimensional subshifts. This is the consequence of a result by M. Hochman and T. Meyerovitch in 2010, which states that the possibles values of the entropy for multidimensional subshifts of finite type are the  Π1-computable numbers, including in particular non-computable numbers.

The method developed for this purpose originates in the work of R. Berger and R. Robinson. It has been developed further in order to characterize other dynamical aspects of SFT with computability conditions, with similar constructions. It consists of the implementation of Turing machines in hierarchical structures that emerge from the local rules.

However, models studied in statistical physics obey to strong dynamical constraints and there is still hope to include them into a sub-class of subshifts of finite type for which the entropy is uniformly computable (this means that there is an algorithm which can provide arbitrarily precise approximations of the entropy, provided the precision and the local rules of the subshift). An example of a constraint defining a class where this is verified is the block gluing: this was proved by R. Pavlov and M. Schraudner. This property means that two square blocks can be viewed in any relative positions in some element of the subshift provided that the distance between the two blocks is sufficiently large, with minimal distance not depending on the size of the blocks) is a computable real number. Although they provided a construction to realize some class numbers as the entropy of block gluing SFT, they did not prove a characterization, and this problem seems difficult. However, it could be possible to find broader class for which the entropy is still computable.

A strategy to understand the limit between the general regime where Hochman and Meyerovitch’s result holds and this restricted block gluing class is to quantify this property. This means imposing that two patterns can be glued in any two positions in a configuration of the subshift, provided that the distance is great enough, where the minimal distance is a linear function of the size of these patterns.

In a work with Mathieu Sablik, we made a step towards the limit, proving that the result of Hochman and Meyerovitch is robust under the linear version of this property (where the minimal distance function is O(n) where n is the size of the two square blocks). The aim of this talk would be, after a presentation of the problem, to give an insight on the obstacles to this property in the initial construction of Hochman and Meyerovitch, using a construction slightly simpler to present, and on the methods used to overcome the obstacles. These methods involve, in particular, a modification of the Turing machine model and an operator on subshifts that acts by distortion.

Posted on Nov 27, 2018 in Dynamical Systems, Seminars