Multi-dimensional symbolic dynamics.

*(English)*Zbl 1070.37009
Williams, Susan G. (ed.), Symbolic dynamics and its applications. Lectures of the American Mathematical Society short course, San Diego, CA, USA, January 4–5, 2002. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3157-7). Proceedings of Symposia in Applied Mathematics 60; AMS Short Course Lecture Notes, 61-79 (2004).

The study of a discrete dynamical system exhibiting symmetries leads often to the study of the joint action of several commuting transformations. The author introduces simple examples of such actions, presents some of their properties and discusses open problems related to them. More precisely are discussed \({\mathbb Z}^{d}\)-algebraic actions, defined by maps \(\alpha:{\mathbb Z}^{d}\to\text{aut}(X)\), where \(\text{aut}(X)\) is the group of all continuous group transformations of a compact abelian group \(X\). A \({\mathbb Z}^{d}\)-action is regarded as a higher-dimensional shift of finite type, associated to an alphabet \(\mathcal{A}\), having a structure of compact group. That is why, one defines notions of multidimensional symbolic dynamics.

If \(\mathcal{A}\) is a finite alphabet, and \(d\geq 1\) and integer, the set of all arrays, indexed by elements of \({\mathbb Z}^{d}\), i.e., the set \[ {\mathcal{A}}^{{\mathbb Z}^{d}}=\{x:{\mathbb Z}^{d}\to{\mathcal{A}}\} \] is a natural extension of the set of bi-infinite sequences of symbols from \(\mathcal{A}\).

Let \(W\) be a finite subset of \({\mathbb Z}^{d}\), and \(\mathcal{P}\) an arbitrary subset of \({\mathcal A}^{W}\). The \(d\)-dimensional shift of finite type over the alphabet \(\mathcal A\), based on \(\mathcal P\), is the set: \[ X_{{\mathcal P}}=\{x\in {\mathcal{A}}^{{\mathbb Z}^{d}}\mid x_{| W+{\mathbf k}}\in {\mathcal P}, \forall {\mathbf k}\in {\mathbb Z}^{d}\}, \] where \(x_{| W+{\mathbf k}}\) denotes elements \(y\) in \({\mathcal A}^{W}\), such that \(y_{{\mathbf n}}=x_{{\mathbf n+k}}\), \(\forall{\mathbf n}\in W\). One defines the \({\mathbb Z}^{d}\)-shift action on \(X_{{\mathcal P}}\), i.e. a map \(\sigma\) which associates to each \({\mathbf n}\in {\mathbb Z}^{d}\) a transformation of \(X_{\mathcal P}\), denoted \(\sigma^{{\mathbf n}}\), such that \((\sigma^{\mathbf n}(x))_{\mathbf k}=x_{{\mathbf n+k}}\). Since shifts in different coordinate directions commute, \(\sigma\) is completely specified if we know the \(d\) commuting maps \(\sigma^{{\mathbf e}_j}\), \(j=1,2,\ldots, d\), \({\mathbf e}_j=(0,\ldots, 1,\ldots, 0)\), with \(1\) in the \(j^{th}\) position.

Examples of \(2\)-dimensional shifts of fine type are given (the full shift, Golden mean shift, Ledrappier’s example, Wang tiles, cellular automata). Arguments that the following three questions related to the \(d\)-dimensional shifts of finite type: 1) the existence of points, 2) the extension of finite configurations, 3) the existence of periodic points – cannot be decided by a finite procedure are given, and this particularity is called the swamp of undecidability.

The \({\mathbb Z}^{d}\)-actions however form a class of higher dimensional shifts of finite type for which these questions can be answered

The author defines and discusses some properties of \(d\)-dimensional shifts, \(d\geq 2\). In particular the entropy of such a shift is defined and it is computed for some of the given examples of the \(2\)-dimensional shifts of finite type. It is also shown that the computation of the entropy for algebraic \({\mathbb Z}^{d}\)-actions is connected to an unresolved conjecture by D. H. Lehmer on Mahler measure. Finally some other open problems are discussed.

For the entire collection see [Zbl 1052.37003].

If \(\mathcal{A}\) is a finite alphabet, and \(d\geq 1\) and integer, the set of all arrays, indexed by elements of \({\mathbb Z}^{d}\), i.e., the set \[ {\mathcal{A}}^{{\mathbb Z}^{d}}=\{x:{\mathbb Z}^{d}\to{\mathcal{A}}\} \] is a natural extension of the set of bi-infinite sequences of symbols from \(\mathcal{A}\).

Let \(W\) be a finite subset of \({\mathbb Z}^{d}\), and \(\mathcal{P}\) an arbitrary subset of \({\mathcal A}^{W}\). The \(d\)-dimensional shift of finite type over the alphabet \(\mathcal A\), based on \(\mathcal P\), is the set: \[ X_{{\mathcal P}}=\{x\in {\mathcal{A}}^{{\mathbb Z}^{d}}\mid x_{| W+{\mathbf k}}\in {\mathcal P}, \forall {\mathbf k}\in {\mathbb Z}^{d}\}, \] where \(x_{| W+{\mathbf k}}\) denotes elements \(y\) in \({\mathcal A}^{W}\), such that \(y_{{\mathbf n}}=x_{{\mathbf n+k}}\), \(\forall{\mathbf n}\in W\). One defines the \({\mathbb Z}^{d}\)-shift action on \(X_{{\mathcal P}}\), i.e. a map \(\sigma\) which associates to each \({\mathbf n}\in {\mathbb Z}^{d}\) a transformation of \(X_{\mathcal P}\), denoted \(\sigma^{{\mathbf n}}\), such that \((\sigma^{\mathbf n}(x))_{\mathbf k}=x_{{\mathbf n+k}}\). Since shifts in different coordinate directions commute, \(\sigma\) is completely specified if we know the \(d\) commuting maps \(\sigma^{{\mathbf e}_j}\), \(j=1,2,\ldots, d\), \({\mathbf e}_j=(0,\ldots, 1,\ldots, 0)\), with \(1\) in the \(j^{th}\) position.

Examples of \(2\)-dimensional shifts of fine type are given (the full shift, Golden mean shift, Ledrappier’s example, Wang tiles, cellular automata). Arguments that the following three questions related to the \(d\)-dimensional shifts of finite type: 1) the existence of points, 2) the extension of finite configurations, 3) the existence of periodic points – cannot be decided by a finite procedure are given, and this particularity is called the swamp of undecidability.

The \({\mathbb Z}^{d}\)-actions however form a class of higher dimensional shifts of finite type for which these questions can be answered

The author defines and discusses some properties of \(d\)-dimensional shifts, \(d\geq 2\). In particular the entropy of such a shift is defined and it is computed for some of the given examples of the \(2\)-dimensional shifts of finite type. It is also shown that the computation of the entropy for algebraic \({\mathbb Z}^{d}\)-actions is connected to an unresolved conjecture by D. H. Lehmer on Mahler measure. Finally some other open problems are discussed.

For the entire collection see [Zbl 1052.37003].

Reviewer: Emilia Petrisor (Timişoara)

##### MSC:

37B50 | Multi-dimensional shifts of finite type, tiling dynamics (MSC2010) |

37B40 | Topological entropy |

37B05 | Dynamical systems involving transformations and group actions with special properties (minimality, distality, proximality, expansivity, etc.) |

37B10 | Symbolic dynamics |

37B15 | Dynamical aspects of cellular automata |

37A05 | Dynamical aspects of measure-preserving transformations |