Symbolic Dynamics

Abstract

In this chapter, we will study a class of topological dynamical systems known as symbolic dynamical systems. These systems play an important role in coding theory, combinatorial dynamics and theory of cellular automata. In Sect. 2, we introduce the basic concepts associated with such systems. In Sect. 3, we introduce the notion of entropy. In Sect. 4, we compute the measure theoretic entropy of Bernoulli shifts. In Sect. 5, we consider a class of symbolic dynamical systems related to tiling spaces, and prove a result due to M. Szegedy that asserts that any translational tiling of $\mathbb {Z}^{d}$ by a finite set F is periodic when |F| is prime. The last section is devoted to an algebraic dynamical system known as 3-dot system. Using the concept of directional homoclinic groups we show that $\mathbb {Z}^{2}$-actions on symbolic spaces can exhibit strong rigidity property.

1 Introduction

In this chapter, we will study a class of topological dynamical systems known as symbolic dynamical systems. These systems play an important role in coding theory, combinatorial dynamics and theory of cellular automata. In Sect. 2, we introduce the basic concepts associated with such systems. In Sect. 3, we introduce the notion of entropy. In Sect. 4, we compute the measure theoretic entropy of Bernoulli shifts. In Sect. 5, we consider a class of symbolic dynamical systems related to tiling spaces, and prove a result due to M. Szegedy that asserts that any translational tiling of $\mathbb {Z}^{d}$ by a finite set F is periodic when |F| is prime. The last section is devoted to an algebraic dynamical system known as 3-dot system. Using the concept of directional homoclinic groups we show that $\mathbb {Z}^{2}$-actions on symbolic spaces can exhibit strong rigidity property.

2 Basic Concepts

In this section, we review some basic concepts of symbolic dynamics (see [5] for a comprehensive introduction).

Definition 2.1

Let G be a discrete group.

• 1. A topological G-space is a compact topological space X together with a continuous action $\sigma$ of G on X. In other words, $\sigma$ is a continuous map from $G \times X$ to X that satisfies the properties of a group action.

Notation 2.2

For any $g \in G$, the map $x \longmapsto g \cdot x = \sigma (g, x)$ will be denoted by $\sigma (g)$.

• 2. If $(X, \sigma )$ and $(Y, \rho )$ are topological G-spaces, a map $f : X \longrightarrow Y$ is said to be G-equivariant if $f \circ \sigma (g) = \rho (g) \circ f$ for all $g \in G$.

• 3. A topological G-space $(Y, \rho )$ is said to be a factor of a topological G-space $(X, \sigma )$ if there exists a surjective G-equivariant map from X to Y.

• 4. Two topological G-spaces $(X, \sigma )$ and $(Y, \rho )$ are topologically conjugate if there exists a G-equivariant homeomorphism from X to Y.

Let $A = \left\{ 1, \ldots , k \right\}$ be a finite set and let $A^{{\mathbb Z}}$ be the set of all functions from ${\mathbb Z}$ to A. The set $Y = A^{{\mathbb Z}}$ can also be viewed as the collection of all bi-infinite sequences taking values in A. For any $a \in A^{\mathbb {Z}},\ \left\{ a_{i} \right\} _{i \in \mathbb {Z}}$ will denote the corresponding bi-infinite sequence. Let d denote the discrete metric on A, i.e., $d(x, y) = 1$ if $x \ne y$ and $d(x, y) = 0$ if $x = y$. We define a metric $d_{Y}$ on Y by

$$\begin{aligned} d_{Y} (a, b)\ \ =\ \ \sum _{i = - \infty }^{\infty } \frac{d(a_{i}, b_{i})}{2^{\left| i \right| + 1}}. \end{aligned}$$

We note that $d_{Y}(a, b)$ is small if and only if there exists a large $N > 0$ such that $a_{i} = b_{i}$ for all $i \in [- N, N]$. Hence, $d_{Y}$ induces the product topology on $Y = A^{\mathbb Z}$ with cylinder sets as basic open subsets (the choice of the metric is not relevant here as long as it induces the product topology).

Let $T : Y \longrightarrow Y$ be the shift map defined by $T(a)_{i} = a_{i + 1}$. It is easy to see that (Y, d) is a compact metric space and $T : Y \longrightarrow Y$ is a self homeomorphism.

Definition 2.3

If $X \subset A^{{\mathbb Z}}$ is a closed shift invariant subset and T is the restriction of the shift map to X then (X, T) is called a symbolic dynamical system.

Example 2.4

$X = A^{{\mathbb Z}}$ and T is the shift map.

Example 2.5

Suppose we only have two symbols, i.e., $A = \left\{ 0, 1 \right\}$. Let $X = \left\{ a \in A^{\mathbb Z}\ :\ \text {there are no two consecutive}\ 0\text {'s} \right\}$.

Example 2.6

We fix finite sets A and $E \subset A \times A$. Let G denote the directed graph with A as the set of vertices and E as the set of edges. We define $X_{G} = \left\{ a\in A^{{\mathbb Z}}\ :\ (a_{i}, a_{i + 1} ) \in E\ \forall i \right\}$. The dynamical system $(X_{G}, T|_{X_{G}})$ is called the topological Markov chain corresponding to G. Note that Example 2.5 can be seen as a special case where $A = \{ 0, 1 \}$ and $E = \{(1, 0), (1, 1), (0, 1) \}$.

Example 2.7

Suppose $A = \{ 0, 1 \}$ and X is the set of all bi-infinite sequences in $\{ 0, 1 \}$ such that between any two consecutive 1’s there are even number of 0’s. Then it is easy to verify that X is closed and shift-invariant.

Example 2.8

For any finite set A we define $L(A) = \bigcup \limits _{n = 1}^{\infty } A^{n}$. The set L(A) can be viewed as the collection of all finite words with A as the alphabet set. For any $S \subset L(A)$, we define

$$\begin{aligned} X_{S}\ \ =\ \ \left\{ a \in A^{\mathbb {Z}}\ :\ s\ \text {does not occur in}\ A\ \forall s \in S \right\} . \end{aligned}$$

Clearly, $X_{S}$ is a closed shift-invariant subset of $A^{\mathbb {Z}}$.

Definition 2.9

Suppose $X \subset A^{\mathbb {Z}}$ is a closed shift-invariant subset and $\sigma$ is the shift action of $\mathbb {Z}$ on X. Then $(X,\sigma )$ is called a subshift of finite type if $X = X_{S}$ for some finite set $S \subset L(A)$.

Definition 2.10

Suppose $Y \subset A^{\mathbb {Z}}$ is a closed shift-invariant subset such that the shift action of $\mathbb {Z}$ on Y is a factor of a subshift of finite type $X \subset A^{\mathbb {Z}}$. Then the shift action on Y is called a sofic shift.

Example 2.11

With three symbols, suppose $A = \{ 0, 1, 2 \}$ and $E = \{ (1, 1), (1, 0), (2, 1), (0, 2), (2, 0) \}$. Let $X \subset A^{\mathbb {Z}}$ be the topological Markov chain associated with (A, E). Let $\phi : A\longrightarrow \{ 0, 1 \}$ denote the map defined by $\phi (1) = 1$ and $\phi (0) = \phi (2) = 0$. Then, $\phi$ induces a continuous shift equivariant map from X to $A^{\mathbb {Z}}$. It is easy to see that the image of $\phi$ is the system described in Example 2.7. Hence the system described in Example 2.7 is a sofic shift.

Let A be a finite set. Fix $k \ge 1$, and choose a map $\theta : A^{2 k + 1} \longrightarrow A$. Such maps are called block codes. Any block code $\theta$ induces a map $\overline{\theta } : A^{\mathbb {Z}} \longrightarrow A^{\mathbb {Z}}$ defined by $\overline{\theta } (x)_{i} = \theta (x_{i - k}, \ldots , x_{i + k})$. The map $\overline{\theta }$ is called the sliding block code corresponding to $\theta$.

Example 2.12

Let $A = \{ 0, 1 \}$ and q be the continuous shift-equivariant map from $A^{\mathbb {Z}}$ to $A^{\mathbb {Z}}$ defined by $q(x)_{i} = x_{i - 1} + x_{i} + x_{i + 1} \pmod 2$. Then $q = \overline{\theta }$, where $\theta : A^{3} \longrightarrow A$ is the block code defined by $\theta (a, b, c)_{i} = a + b + c \pmod 2$.

It is easy to see that for any block code $\theta ,\ \overline{\theta }$ is a continuous shift-equivariant map from $A^{\mathbb {Z}}$ to $A^{\mathbb {Z}}$. The following result, known as the Curtis-Hedlund theorem, shows that the converse is also true.

Theorem 2.13

Suppose A is a finite set and $f : A^{\mathbb {Z}} \longrightarrow A^{\mathbb {Z}}$ is a continuous shift-equivariant map. Then there exists $k \ge 1$ and a block code $\theta : A^{2 k + 1} \longrightarrow A$ such that $f = \overline{\theta }$.

Proof

Since $A^{\mathbb {Z}}$ is compact, f is uniformly continuous, we choose a positive $\delta$ such that $\displaystyle {d(f(x), f(y)) < \frac{1}{2}}$ whenever $d(x, y) < \delta$. Since

$$\begin{aligned} d(f(x), f(y))\ \ =\ \ \sum \frac{d ( f(x)_{i}, f(y)_{i} )}{2^{i}}, \end{aligned}$$

it follows that $f(x)_{0} = f(y)_{0}$ whenever $\displaystyle {d(f(x), f(y)) < {\frac{1}{2}}}$. We choose k such that $\displaystyle {\sum \limits _{| i | > k} \frac{1}{2^{k}} < \delta }$. Then. $f(x)_{0} = f(y)_{0}$ whenever $x_{i} = y_{i}$ for all i with $| i | \le k$. This shows that there is a block code $\theta : A^{2 k + 1} \longrightarrow A$ such that $f(x)_{0} = \theta (x_{- k}, \ldots , x_{k})$. Since f is also shift-equivariant, we deduce that $f = \overline{\theta }$. $\square$

3 Entropy

We will now introduce a dynamical invariant called topological entropy for symbolic dynamical systems. We will need the following elementary result about sequences of real numbers.

Proposition 3.1

Let $\{ a_{i} \}$ be a sequence of non-negative real numbers such that $a_{m + n} \le a_{m} + a_{n}$ for all m and n. Then $\displaystyle {\lim \limits _{n \rightarrow \infty } \frac{a_{n}}{n}}$ exists.

Proof

Set $\displaystyle {c = \inf \limits _{n} \frac{a_{n}}{n}}$. For any $\epsilon > 0$, we choose n such that

$$\begin{aligned} \left| \frac{a_{n}}{n} - c \right| \ \ <\ \ \epsilon . \end{aligned}$$

Let $D = \max \{ a_{1}, \ldots , a_{n} \}$. Let $m \ge n$ be any positive integer. We write $m = k n + j$, where $0 \le j \le n - 1$. Now,

$$\begin{aligned} \frac{a_{m}}{m}\ \ \le \ \ \frac{k a_{n} + a_{j}}{k n + j}\ \ \le \ \ c + \epsilon + \frac{D}{m}. \end{aligned}$$

This shows that $\displaystyle {\frac{a_{m}}{m} \le c + 2 \epsilon }$ as $m \rightarrow \infty$. Since $\epsilon$ is arbitrary, we conclude that $\displaystyle {\frac{a_{m}}{m} \rightarrow c}$ as $m \rightarrow \infty$. $\square$

For $m \le n$, let [m, n] denote the set $\{ m, \ldots , n \}$. For any closed shift invariant subset $X \subset A^{\mathbb {Z}}$ and a finite set $S \subset \mathbb {Z}$, let $\pi _{S}$ denote the projection map from $A^{\mathbb {Z}}$ to $A^{S}$. For $k \ge 1$, let $B_{k}$ denote the set $\pi _{[0, k - 1]} (X)$. The set $B_{k}$ can also be described as the set of all blocks of length k that occurs in elements of X. Since X is shift invariant it follows that $\pi _{[0,\, n - 1]} (X) = \pi _{[m,\, m + n - 1]} (X)$ for all m and n. Since there is a natural injective map from $\pi _{[0,\, m + n - 1]} (X)$ to $\pi _{[0,\, m - 1]} (X) \times \pi _{[m,\, m + n - 1]} (X)$, we deduce that $|B_{m + n}| \le |B_{m}| \times |B_{n}|$. We define

$$\begin{aligned} h(X)\ \ =\ \ \lim _{k \rightarrow \infty } \frac{\log (|B_{k}|)}{k}. \end{aligned}$$

The number h(X) is called the entropy of the shift action of $\mathbb {Z}$ on X. By the previous proposition it is well defined.

Example 3.2

Suppose $X = A^{\mathbb {Z}}$. In this case $B_{n} = A^{n}$ and $|B_{n}| = |A|^{n}$. Hence, the entropy of the corresponding shift action is $\log |A|$.

Example 3.3

Suppose $X = \{ a \in \{ 0, 1 \}^{\mathbb Z}\ :\ \text {there are no two consecutive}\ 1\text {'s} \}$. Let T denote the $2 \times 2$ adjacency matrix of the associated graph. Then, $T_{1 1} = T_{1 2} = T_{2 1} = 1$ and $T_{2 2} = 0$. Hence T has two distinct eigenvalues $\displaystyle {\frac{\sqrt{5} \pm 1}{2}}$. It is easy to see that $|B_{n}|$ is the sum of entries of $T^{n - 1}$. This implies that

$$\begin{aligned} h(X)\ \ =\ \ \lim _{n \rightarrow \infty } \frac{\log |B_{n}|}{n}\ \ =\ \ \log \left( \frac{\sqrt{5} + 1}{2} \right) . \end{aligned}$$

We now show that topological entropy is invariant under topological conjugacy.

Theorem 3.4

Let A be a finite set and for $i = 1, 2$, let $X_{i}$ be a closed shift invariant subset of $A^{\mathbb {Z}}$ such the corresponding shift actions of $\mathbb {Z}$ are topologically conjugate. Then $h(X_{1}) = h(X_{2})$.

Proof

Let f be a topological conjugacy between these two shift actions. From Curtis-Hedlund theorem, it follows that there exists $k \ge 1$, and a map $\theta : A^{2 k + 1} \longrightarrow A$ such that f is the sliding block code corresponding to $\theta$. Hence for any $i \le j$, the elements $f(x)_{i}, \ldots , f(x)_{j}$ are determined by the elements $x_{i - k}, \ldots , x_{j + k}$. In particular, $|B_{n} (X_{2})| \le |B_{n + 2 k} (X_{1})|$. Taking logarithms, dividing by n, and letting $n \rightarrow \infty$, we see that $h(X_{1}) \ge h(X_{2})$. Similarly, we can show that $h(X_{2}) \ge h(X_{1})$.

$\square$

Our next task is to define the notion of entropy for a more general class of dynamical systems.

Definition 3.5

Let L be an abelian semigroup with the property that $x + x = x$ for all $x \in L$. A norm on L is a map $\left\| \cdot \right\|$ from L to ${\mathbb {R}}^{+}$ satisfying

$$\begin{aligned} \left\| x \right\| \ \ \le \ \ \left\| x + y \right\| \ \ \le \ \ \left\| x \right\| + \left\| y \right\| \ \ \forall x, y \in L. \end{aligned}$$

A normed lattice is an abelian semigroup L together with a norm map $\left\| \cdot \right\| : L \longrightarrow {\mathbb {R}}^{+}$.

Example 3.6

Let S be a set and let L be the collection of all finite subsets of S. For $A, B \in L$ set $A + B = A \cup B$, and $\left\| A \right\| = \left| A \right|$, the cardinality of A.

Example 3.7

Let V be a vector space and let L be the collection of all finite dimensional subspaces of V. For $X, Y \in L$, define $X + Y$ to be the smallest subspace containing X and Y, and set $\left\| X \right\| = \mathrm{dim} (X)$.

Example 3.8

Let X be a compact topological space. An open cover C of X is called saturated if for any two open subsets U and V of X with $U \in C$ and $V \subset U,$ we have $V \in C$. Let L be the collection of all saturated open covers of X. For $C,\ C^{'} \in L$, we define $C + C^{'}$ to be the collection of all open subsets that belong to both C and $C^{'}$. It is easy to see that $C + C^{'}$ is an element of L. For any $C \in L$, we define $\left\| C \right\| = \log (n_{C})$, where $n_{C}$ is the smallest cardinality of a subcover of C.

Notation 3.9

For $x, y \in L$, we say $x \le y$ if $x + y = y$.

It is easy to see that the above notation defines a partial order on L.

Definition 3.10

If $T : L \longrightarrow L^{'}$ is a map between normed lattices then T is called an isometry if $T ( x + y ) = T ( x ) + T ( y )$ and $\left\| T ( x ) \right\| = \left\| x \right\|$ for all x, y. Clearly, the collection of all normed lattices form a category with isometries as morphisms.

If $T : L \longrightarrow L$ is an isometry, then we define

$$\begin{aligned} \left\| \cdot \right\| _{T} : L \longrightarrow {\mathbb R}^{+}\ \ \text {by}\ \ \left\| x \right\| _{T}\ \ =\ \ \lim _{n \rightarrow \infty } \frac{1}{n} (x + Tx + \cdots + T^{n - 1} x). \end{aligned}$$

Proposition 3.11

The map $\left\| \cdot \right\| _{T}$ is well defined and it is a norm on L. Furthermore, it satisfies the following two properties:

• 1. $\left\| x \right\| _{T} \le \left\| x \right\|$ for all x in L;

• 2. Both T and $I + T$ are isometries with respect to $\left\| \cdot \right\| _{T}$.

Proof

Fix any $x \in L$ and define a sequence $\{ a_{n} \}$ by

$$\begin{aligned} a_{n}\ \ =\ \ \left\| x + Tx + \cdots + T^{n - 1} x \right\| . \end{aligned}$$

Since T is an isometry, applying the sub-additivity of the norm, we see that $a_{m + n} \le a_{m} + a_{n}$ for all $m, n \ge 1$. From Proposition 3.1, we deduce that $\left\| \cdot \right\| _{T}$ is well defined. It is easy to see that $\left\| \cdot \right\| _{T}$ is a norm and satisfies property 1. Since $x + x = x$ in L, we obtain

$$\begin{aligned} \sum _{i = 0}^{n - 1} T^{i} (x + T x)\ \ =\ \ \sum _{i = 0}^{n} T^{i} (x), \end{aligned}$$

which proves the second property. $\square$

Definition 3.12

For any isometry $T : L \longrightarrow L$, we define the entropy of T by

$$\begin{aligned} h(T)\ \ =\ \ \sup \left\{ \left\| x \right\| _{T}\ :\ x \in L \right\} . \end{aligned}$$

Definition 3.13

Let $(X, \mu )$ be a measure space with $\mu (X) = 1$. A partition $P = \{ P_{1}, \ldots , P_{m} \}$ of X is a finite collection of pairwise disjoint, non-empty, measurable subsets of X such that $\bigcup P_{i} = X$.

Notation 3.14

Let $L_{X}$ be the set of all partitions of X. For $P, Q \in L_{X}$, we define

$$\begin{aligned} P + Q\ \ =\ \ \left\{ P_{i} \cap Q_{j}\ :\ P_{i} \in P,\ Q_{j} \in Q\ \text {and}\ P_{i} \cap Q_{j} \ne \varnothing \right\} . \end{aligned}$$

It is easy to see that $L_{X}$ becomes an abelian semigroup and $P + P = P$ for all P. For $P = \{ P_{1}, \ldots , P_{m} \}\in L_{X}$, we set

$$\begin{aligned} \left\| P \right\| \ \ =\ \ - \sum _{i = 1}^{m} \mu (P_{i})\ \log _{2}(\mu (P_{i})). \end{aligned}$$

Proposition 3.15

$L_{X}$ is a normed lattice with respect to the above norm.

Proof

Choose $P = \{ P_{1}, \ldots , P_{m} \}$ and $Q = \{ Q_{1}, \ldots , Q_{n} \}$ in L. Set $p_{i} = \mu (P_{i}),$ $q_{j} = \mu (Q_{j})$ and $r_{ij} = \mu (P_{i} \cap Q_{j})$. Now,

$$\begin{aligned} \left\| P + Q \right\| - \left\| P \right\| \ \ =\ \ \sum p_{i}\ \log p_{i} - \sum r_{ij}\ \log r_{ij} \ \ =\ \ - \sum r_{ij} \left( \log r_{ij} - \log p_{i} \right) . \end{aligned}$$

Since $\log$ is an increasing function, this shows that $\left\| P + Q \right\| \ge \left\| P \right\|$.

Define $\phi : [0, 1] \longrightarrow {\mathbb R}$ by $\phi (0) = 0$ and $\phi (x) = - x \log x$ if $\,x > 0$. Since $\displaystyle {\phi ^{''}(x) = - \frac{1}{x} < 0}$ in (0, 1), it follows that $\phi$ is a concave function. Put $\displaystyle {c_{ij} = \frac{r_{ij}}{p_{i}}}$ if $p_{i} > 0$ and 0 otherwise. Observe that $\left\| P + Q \right\| - \left\| P \right\| = \sum p_{i} \phi (c_{ij})$. Since $\phi$ is concave, we deduce that

$$ \left\| P + Q \right\| - \left\| P \right\| \ \ \le \ \ \sum _{j} \phi \left( \sum _{i} p_{i} c_{ij} \right) \ \ =\ \ \sum _{j} \phi (q_{j})\ \ =\ \ \left\| Q \right\| . $$

$\square$

If $T : (X, \mu ) \longrightarrow (Y, \nu )$ is a measure preserving map then, we define a map $T^{*} : L_{Y} \longrightarrow L_{X}$ by

$$\begin{aligned} T^{*}(P)\ \ =\ \ \left\{ T^{-1} (P_{1}), \ldots , T^{-1}(P_{n}) \right\} . \end{aligned}$$

It is easy to see that $T^{*}$ is an isometry. Moreover, the correspondence $X \longmapsto L_{X}$ and $T \longmapsto T^{*}$ gives us a contravariant functor from the category of probability spaces to the category of normed lattices. If T is a measure preserving map from $(X, \mu )$ to itself then we define $h(T) = h(T^{*})$, where $T^{*}$ is the isometry of $L_{X}$ induced by T. The number h(T) is called the entropy of T. Clearly, entropy is a measurable conjugacy invariant.

Suppose X is a compact topological space and T is a homeomorphism of X. As in the Example 3.8, let L denote the collection of all saturated open covers of X. For any $C \in L$, we define $T^{*}(C) = \left\{ T^{-1} (U)\ :\ U \in C \right\}$. It is easy to see that $T^{*} (C) \in L$ for all $C \in L$ and $T^{*}$ is an isometry of L. The number $h(T^{*})$ is called the topological entropy of T. It is a topological conjugacy invariant. In the special case when (X, T) is a one-dimensional shift, this coincides with the more explicit definition presented earlier.

4 Computations of Entropy

In this section, we compute the entropy of Bernoulli shifts and translations on tori. If X is a set and $\mathcal{A}$ is a collection of subsets of X then by $\sigma (\mathcal{A})$ we denote the smallest $\sigma$-algebra on X that contains $\mathcal{A}$. We begin with the following approximation lemma.

Lemma 4.1

Suppose $(X, \mathcal{B}, \mu )$ is a probability space and suppose $\mathcal{A} \subset \mathcal{B}$ is an algebra such that $\sigma (\mathcal{A}) = \mathcal{B}$. Then for any $P \in L_{X}$ and $\epsilon > 0$, there exist a partition $P_{1} \subset \mathcal{A}$ and $Q \in L_{X}$ with $\left\| Q \right\| < \epsilon$ such that $P \le P_{1} + Q$.

Proof

We first consider the case when P has only two elements, i.e., $P = \{ B, B^{c} \}$ for some measurable set B. Note that $x \log x \rightarrow 0$ as $x \rightarrow 0$ or $x \rightarrow 1$. Hence, we can find $\delta > 0$ such that $\mu (E) < \delta$ implies $\left\| \left\{ E, E^{c} \right\} \right\| < \epsilon$. As $\sigma (\mathcal{A}) = \mathcal{B}$, we can find $A \in \mathcal{A}$ such that $\mu (F) < \delta$, where $F = (B \setminus A) \cup (A \setminus B)$. Define $P_{1} = \left\{ A, A^{c} \right\}$ and $Q = \left\{ F, F^{c} \right\}$. It is easy to see that $P_{1}$ and Q have the required properties.

Now suppose $P = \left\{ B_{1}, \ldots , B_{n} \right\}$. For $1 \le i \le n$, define $P^{i} = \left\{ B_{i}, B_{i}^{c} \right\}$. Find $P_{1}^{i},\ Q^{i}$ as above with $\displaystyle {\left\| Q^{i} \right\| < \frac{\epsilon }{n}}$ and put $P_{1} = \sum P^{i}$ and $Q = \sum Q^{i}$. $\square$

We note the following consequence of the previous lemma.

Proposition 4.2

Let $(X, \mathcal{B}, \mu )$ be a probability space and let $T : X \longrightarrow X$ be a measure preserving map. Suppose $\mathcal{A}$ is an algebra such that $\sigma (\mathcal{A}) = \mathcal{B}$. Then $h(T) = \sup \left\{ \left\| P \right\| _{T}\ :\ P \subset \mathcal{A} \right\}$.

Proof

Fix $\epsilon > 0$ and choose $P^{'}$ such that $h(T) \le \left\| P^{'} \right\| _{T} + \epsilon$. Applying the previous lemma, find $P_{1}$ and Q such that $P^{'} \le P_{1} + Q,\ P_{1} \subset \mathcal{A}$ and $\left\| Q \right\| < \epsilon$. Since $\left\| Q \right\| _{T} \le \left\| Q \right\|$, it follows that

$$ h(T)\ \ \le \ \ \left\| P_{1} \right\| _{T} + \left\| Q \right\| _{T} + \epsilon \ \ =\ \ \left\| P_{1} \right\| _{T} + 2 \epsilon . $$

As $\epsilon$ is arbitrary, this proves the proposition. $\square$

Definition 4.3

Let $(X, \mathcal{B}, \mu )$ be a probability space and let $T : X \longrightarrow X$ be an invertible measure preserving map. A partition P is said to be a generator if $\mathcal{B}$ is the smallest $\sigma$-algebra that is invariant under the $\mathbb {Z}$-action generated by T and contains $\left\{ P_{1}, \ldots , P_{n} \right\}$.

Theorem 4.4

If P is a generator, then $h(T) = \left\| P \right\| _{T}$.

Proof

For any partition P, let A(P) denote the collection of all subsets which can be expressed as unions of elements of P. It is easy to verify that A(P) is a finite algebra and $Q \le P$ if and only if $Q \subset A(P)$. We define an algebra $A_{\infty }$ by

$$\begin{aligned} A_{n}\ \ =\ \ A \left( \sum _{- n}^{n} T^{*i} \right) ,\ \ \ \ A_{\infty }\ \ =\ \ \bigcup _{n = 1}^{\infty } A_{n}. \end{aligned}$$

Note that $A_{\infty }$ is the smallest T-invariant algebra containing P. Hence. $\sigma \left( A_{\infty } \right) = \mathcal{B}$. If a partition Q is contained in $A_{\infty }$ then $Q \subset A_{n}$ for some n. Hence,

$$\begin{aligned} \left\| Q \right\| _{T}\ \ \le \ \ \left\| \sum _{i = - n}^{n} T^{*i} P \right\| _{T}\ \ =\ \ \left\| \left( I + T^{*} \right) ^{2 n + 1} (P) \right\| _{T}\ \ =\ \ \left\| P \right\| _{T}. \end{aligned}$$

From the previous lemma it then follows that $h(T) = \left\| P \right\| _{T}$. $\square$

Definition 4.5

Let $(X, \mu )$ be a probability space and let $P, Q \in L_{X}$. Then P and Q are said to be independent if $\mu (P_{i} \cap Q_{j}) = \mu (P_{i}) \mu (Q_{j})$ for all i and j.

It is easy to see that if P and Q are independent then $\left\| P + Q \right\| = \left\| P \right\| + \left\| Q \right\|$.

4.1 Entropy of Shifts

Let $Y = \left\{ y_{1}, \ldots , y_{n} \right\}$ be a finite set and let $\nu$ be a probability measure on Y. Let $(X, \mathcal{B}, \mu ) = (Y, \nu )^{\mathbb Z}$ and let $T : X \longrightarrow X$ be the shift map. We define a partition $P = \left\{ P_{1}, \ldots , P_{n} \right\}$ of X by

$$\begin{aligned} P_{i}\ \ =\ \ \left\{ x \in X\ :\ x(0) = y_{i} \right\} . \end{aligned}$$

Let $\mathcal{A}$ be the smallest T-invariant $\sigma$-algebra containing P. Since $P \subset \mathcal{A}$, the co-ordinate projection corresponding to 0th co-ordinate is a $\mathcal{A}$-measurable map. Since $\mathcal{A}$ is T-invariant, all co-ordinate projections are measurable. Hence $\mathcal{A} = \mathcal{B}$, i.e., P is a generator. We observe that for any k, the partitions $P + \cdots + T^{* k - 1} P$ and $T^{* k} P$ are independent. Applying induction on k, we see that $\left\| \sum _{i = 0}^{k - 1} T^{* i} P \right\| = k \left\| P \right\|$. Hence, $h(T) = \left\| P \right\| _{T} = \left\| P \right\|$. In the special case, when $\nu$ is the uniform measure on $Y,\ h(T) = \log n$.

Proposition 4.6

Let $(X, \mathcal{B}, \mu )$ be a probability space and let $T : X \longrightarrow X$ be a measure preserving map.

• 1. $h(T^{n}) = n h(T)$ for all $n \ge 1$.

• 2. If T is invertible then $h(T^{- 1}) = h(T)$.

Proof

We will prove the statements for any lattice isometry $T : L \longrightarrow L$.

• 1. Fix $x \in L$ and put $y = x + T x + \cdots + T^{n - 1} x$. Note that

  $$\begin{aligned} \sum _{i = 0}^{k - 1} T^{i n} x\ \ \le \ \ \sum _{i = 0}^{n k - 1} T^{i} x\ \ =\ \ \sum _{i = 0}^{k - 1} T^{n i} y. \end{aligned}$$

  This shows that $\left\| x \right\| _{T^{n}} \le n \left\| x \right\| _{T} = \left\| y \right\| _{T^{n}}$. Since x is arbitrary, we conclude that $h(T^{n}) = n h(T)$.

• 2. If T is invertible then for any $x \in L$,

  $$\begin{aligned} \left\| \sum _{i = 0}^{k - 1} T^{- i} x \right\| \ \ =\ \ \left\| T^{1 - k} \left( \sum _{i = 0}^{k - 1} T^{i} x \right) \right\| \ \ =\ \ \left\| \sum _{i = 0}^{k - 1} T^{i} x \right\| . \end{aligned}$$

  Hence $\left\| x \right\| _{T} = \left\| x \right\| _{T^{- 1}}$ for all x and $h(T) = h(T^{- 1})$.

$\square$

For $i = 1, 2$, let $(X_{i}, \mathcal{B}_{i}, \mu _{i})$ be a probability space and let $T_{i} : X_{i} \longrightarrow X_{i}$ be a measure preserving map. We define $T_{1} \times T_{2} : X_{1} \times X_{2} \longrightarrow X_{1} \times X_{2}$ by $\left( T_{1} \times T_{2} \right) (x, y) = (T_{1} x, T_{2} y)$. It is easy to see that $T_{1} \times T_{2}$ preserves the measure $\mu _{1} \times \mu _{2}$.

Proposition 4.7

$h \left( T_{1} \times T_{2} \right) \ =\ h \left( T_{1} \right) + h \left( T_{2} \right)$.

Proof

For $i = 1, 2$, let $\pi ^{i}$ denote the projection map from $X_{1} \times X_{2}$ to $X_{i}$. Since $\pi ^{i}$ is measure-preserving, $\pi ^{i}_{*}$ is an isometry from $L_{X_{i}}$ to $L_{X_{1} \times X_{2}}$. It is easy to see that $\left( T_{1} \times T_{2} \right) ^{k}_{*} \pi ^{i}_{*} (P) = \pi ^{i}_{*} (T_{i*}^{k} P)$ for any P in $L_{X_{i}}$. We note that for any $P \in L_{X_{1}}$ and $Q \in L_{X_{2}}$, the partitions $\pi ^{1}_{*}(P)$ and $\pi ^{2}_{*}(Q)$ are independent. Hence, for arbitrary P and Q,

$$\begin{aligned} \left\| \pi ^{1}_{*} (P) + \pi ^{2}_{*} (Q) \right\| _{T_{1} \times T_{2}}\ \ =\ \ \left\| P \right\| _{T_{1}} + \left\| Q \right\| _{T_{2}}. \end{aligned}$$

This implies that $h \left( T_{1} \times T_{2} \right) \ge h \left( T_{1} \right) + h \left( T_{2} \right)$.

Let $\mathcal{A}$ denote the algebra of all subsets of $X_{1} \times X_{2}$ that can be expressed as a finite union of measurable rectangles. If R is a partition of $X_{1} \times X_{2}$ such that $R \subset \mathcal{A}$, then we can find $P \in L_{X_{1}}$ and $Q \in L_{X_{2}}$ such that $R \le \pi ^{1}_{*} (P) + \pi ^{2}_{*} (Q)$. Since $\sigma (\mathcal{A})$ is the product $\sigma$-algebra on $X_{1} \times X_{2}$, applying Proposition 4.2 and the above equality, we see that $h \left( T_{1} \times T_{2} \right) \le h \left( T_{1} \right) + h \left( T_{2} \right)$. $\square$

Lemma 4.8

Let $P = \left\{ P_{1}, \ldots , P_{n} \right\}$ be a partition of a probability space $(X, \mu )$. Then $\left\| P \right\| \le \log n$.

Proof

Put $p_{i} = \mu (P_{i})$. Then $\displaystyle {\left\| P \right\| = \sum p_{i} \log \left( \frac{1}{p_{i}} \right) }$. As $x \longmapsto \log x$ is a concave function, we see that $\displaystyle {\left\| P \right\| \le \log \left( \sum p_{i} \cdot \frac{1}{p_{i}} \right) = \log n}$. $\square$

4.2 Entropy of Translations

Let $n \ge 1$ and let $\theta = (\theta _{1}, \ldots , \theta _{n})$ be an element of the n-torus ${\mathbb T}^{n}$. Let $T : {\mathbb T}^{n} \longrightarrow {\mathbb T}^{n}$ denote the map $x \longmapsto \theta \cdot x$. We claim that $h(T) = 0$. Note that $T = T_{1} \times \cdots \times T_{n}$, where $T_{i} : {\mathbb T} \longrightarrow {\mathbb T}$ is the translation by $\theta _{i}$. By Proposition 4.7, $h(T) = \sum h(T_{i})$. Hence, without loss of generality, we may assume that $n = 1$.

Case 1. $\theta ^{k} = 1$ for some k. Since $P + P = P$ for all P, it follows that $\left\| P \right\| _{\mathrm{Id}} = 0$ for all P, i.e., $h(\mathrm{Id}) = 0$. Since $T^{k} = \mathrm{Id}$, applying Proposition 4.6, we see that $h(T) = 0$.

Case 2. $\theta$ is not a root of unity. We consider the partition $P = \left\{ P_{1}, P_{2} \right\}$ where

$$\begin{aligned} P_{1}\ \ =\ \ \left\{ z\ :\ 0 \le z< \pi \right\} ,\ \ \ \ P_{2}\ \ =\ \ \left\{ z\ :\ \pi \le z < 2 \pi \right\} . \end{aligned}$$

Since $\{ \theta ^{n}\ :\ n \in {\mathbb Z}\}$ is dense in ${\mathbb T}$, it follows that P is a generator for T. Hence, $h(T) = \left\| P \right\| _{T}$. Note that for any $k \ge 1$, the partition $P + \cdots + T_{*}^{k - 1}P$ has 2k sets. By the previous lemma, $\displaystyle {\left\| P \right\| _{T} \le \lim \limits _{k \rightarrow \infty } \frac{\log 2 k}{k} = 0}$, which proves the claim.

5 Tilings

For any finite set A and $d \ge 1$, the compact space $A^{\mathbb {Z}^{d}}$ admits a shift action of $\mathbb {Z}^{d}$. If $d > 1$, and X is a closed shift invariant subset of $A^{\mathbb {Z}^{d}}$ then the restriction of the shift action to X is called a higher-dimensional shift. In this section, we consider a class of such systems that arises from tilings of $\mathbb {Z}^{d}$.

Notation 5.1

For $d \ge 1$, let A, B and C be subsets of $\mathbb {Z}^{d}$. We will write $A \oplus B = C$ if every element of C can be uniquely expressed as $a + b$, with $a\in A$ and $b\in B$.

Definition 5.2

If $F \subset \mathbb {Z}^{d}$ is a finite set, then a tiling of $\mathbb {Z}^{d}$ by F is a subset C of $\mathbb {Z}^{d}$ satisfying $F \oplus C = \mathbb {Z}^{d}$.

It is easy to see that F tiles $\mathbb {Z}^{d}$ if and only if $\mathbb {Z}^{d}$ can be written as a disjoint union of translates of F.

Definition 5.3

A set $E \subset \mathbb {Z}^{d}$ is said to be periodic if there exists a finite index subgroup $\Lambda \subset \mathbb {Z}^{d}$ such that $E + \Lambda = E$.

Let $F = \left\{ g_{1}, \ldots , g_{n} \right\}$ be a finite subset of $\mathbb {Z}^{d}$. We equip $\{ 0, 1 \}^{\mathbb {Z}^{d}}$ with the product topology and define $X(F) \subset \{ 0, 1 \}^{\mathbb {Z}^{d}}$ by

$$\begin{aligned} X(F)\ \ =\ \ \left\{ \mathbf{1}_{C}\ :\ F \oplus C = \mathbb {Z}^{d} \right\} . \end{aligned}$$

It is easy to see that $x \in X(F)$ if and only if for each $g \in \mathbb {Z}^{d}$ there exists exactly one $g^{'} \in g - F$ such that $x (g^{'}) = 1$. This shows that X(F) is a closed subset of the compact space $\{ 0, 1 \}^{\mathbb {Z}^{d}}$. Moreover, X(F) is invariant under the shift action of $\mathbb {Z}^{d}$. The space X(F) can be viewed as the space of all tilings of F. It is non-empty if and only if $\mathbb {Z}^{d}$ can be tiled by F.

Example 5.4

Suppose $d = 2$, and $F = \{ (0, 0), (1, 0), (- 1, 0), (0,- 1) \}$. If an element $(m, n) \in \mathbb {Z}^{2}$ corresponds to the square $(m,\, m + 1] \times (n,\, n + 1] \in {\mathbb R}^{2}$, then the set F corresponds to a T-shaped set in ${\mathbb R}^{2}$. It is easy to verify that there is a unique $C \in \mathbb {Z}^{2}$ such that $(0, 0) \in C$ and $F \oplus C = \mathbb {Z}^{2}$. This implies that any tiling of F is a translate of C by an element of $- F$. In particular, F admits exactly 4 tilings, and all tilings of F are periodic.

Example 5.5

Suppose $d = 2$, and $F = \{ (0, 0), (1, 0) \}$. Then the tilings of $\mathbb {Z}^{2}$ by F are in bijective correspondence with the tilings of the plane by $2 \times 1$ rectangle. We fix an element $\mathbf{1}_{C}$ of X(F) and define a map $h_{C} : \mathbb {Z} \longrightarrow \{ 0, 1 \}$ by $h_{C} (i) = \mathbf{1}_{C} ((0,\, i))$. It is easy to see that the $C \longmapsto h_{C}$ is a bijective correspondence between X(F) and the set of all maps from $\mathbb {Z}$ to $\{ 0, 1 \}$. Hence X(F) can be identified with the compact space $\{ 0, 1 \}^{\mathbb {Z}}$. The shift action of $\mathbb {Z}^{2}$ on $X(F) = \{ 0, 1 \}^{\mathbb {Z}}$ can be explicitly described. The element $(0,\, 1)$ acts by the shift map on $\{ 0, 1 \}^{\mathbb {Z}}$, and the element (1, 0) acts by flipping the symbols.

We note that in the previous example the space X(F) is infinite but every element of X(F) is periodic in the direction of (1, 0). The following example shows that this need not be true in general.

Example 5.6

Suppose $d = 2$, and $F = \{ (0, 0), (2, 0), (0, 2), (2, 2) \}$. We define $E_{1} = \{ (m, n)\ :\ m\ \text {is even}\ \}$ and $E_{2} = \{ (m, n)\ :\ m\ \text {is odd}\ \}$. We note that the tilings of $E_{1}$ by F are in bijection with the tilings of $\mathbb {Z}^{2}$ by $F^{'} = \{ (0, 0), (1, 0), (0, 2), (1, 2) \}$. Hence as in the previous example, we can find $C_{1} \subset \mathbb {Z}^{2}$ such that $C_{1} \oplus F = E_{1}$ and $C_{1}$ is periodic in the direction of (1, 0) but not in the direction of (0, 1). Similarly we can find $C_{2}$ such that $C_{2} \oplus F = E_{2}$ and $C_{2}$ is periodic in the direction of (0, 1) but not in the direction of (1, 0). If we define C to be the disjoint union of $C_{1}$ and $C_{2}$ then $C \in X(F)$ and it is not periodic in any direction.

The following conjecture is due to Lagarias and Wang [6]:

Conjecture 5.7

(Periodic tiling conjecture) Suppose $d \ge 1$ and $F \subset \mathbb {Z}^{d}$ is a finite set such that $F \oplus C = \mathbb {Z}^{d}$ for some $C \in \mathbb {Z}^{d}$. Then there exists a periodic set $E \subset \mathbb {Z}^{d}$ such that $F \oplus E = \mathbb {Z}^{d}$.

The following proposition shows that a stronger version is true in the 1-dimensional case.

Proposition 5.8

Let F and C be subsets of $\mathbb {Z}$ such that F is finite and $F \oplus C = \mathbb {Z}$. Then C is periodic.

Proof

Without loss of generality we may assume that $0 \in F$. Let k denote the diameter of F. From the condition $F \oplus C = \mathbb {Z}$, we deduce that for any $\displaystyle {i \in \mathbb {Z}},$ $\displaystyle {\sum \limits _{j \in F} \mathbf{1}_{C} (i + j) = 1}$. Let B denote the block $(0, \ldots , k - 1)$. Suppose C and $C^{'}$ are two tilings of $\mathbb {Z}$ by F such that the restrictions of $\mathbf{1}_{C}$ and $\mathbf{1}_{C^{'}}$ to B are equal. Then the above condition implies that $\mathbf{1}_{C} (k) = \mathbf{1}_{C^{'}} (k)$. By taking $i = 1, 2, \ldots$ and applying this argument repeatedly we see that $\mathbf{1}_{C} (j) = \mathbf{1}_{C^{'}} (j)$ for all $j \ge 0$. A similar argument shows that $\mathbf{1}_{C} (j) = \mathbf{1}_{C^{'}} (j)$ for all $j \le 0$. Combining these two observations, we deduce that $C = C^{'}$. Since B is a block of length k, this implies that there are only finitely many $C \subset \mathbb {Z}$ such that $F \oplus C = \mathbb {Z}$. As any translate of a tiling is again a tiling, we conclude that every tiling of $\mathbb {Z}$ by F is periodic. $\square$

Definition 5.9

A subset $F \subset \mathbb {Z}^{d}$ is sdid to be non-degenerate if $0 \in F$ and the elements of F generate a finite index subgroup of $\mathbb {Z}^{d}$.

The following theorem due to M. Szegedy (see [8]) describes the tilings of a non-degenerate set F when the number of elements of F is prime.

Theorem 5.10

Let F, C be subsets of $\mathbb {Z}^{d}$ such that F is finite and $F \oplus C = \mathbb {Z}^{d}$. If F is non-degenerate and |F| is a prime number then, C is periodic.

Proof

Let $M_{d}$ denote the set of all functions from $\mathbb {Z}^{d}$ to $\mathbb {R}$. There is a natural action $\theta$ of $\mathbb {Z}^{d}$ on $M_{d}$ defined by

$$\begin{aligned} \theta (g) (f) (x)\ \ =\ \ f (x - g)\ \ \forall x, g \in \mathbb {Z}^{d}. \end{aligned}$$

It is easy to see that $F \oplus C = \mathbb {Z}^{d}$ if and only if $\displaystyle {\sum _{g \in F} \theta (g) (\mathbf{1}_{C}) = \mathbf{1}_{\mathbb {Z}^{d}}}$. If $F = \{ g_{1}, \ldots , g_{p} \}$, where p is a prime number, then this shows that

$$\begin{aligned} \left( \sum _{g \in F} \theta (g) \right) ^{p} \left( \mathbf{1}_{C} \right) \ \ =\ \ \left( \sum _{g \in F} \theta (g) \right) ^{p - 1} \left( \mathbf{1}_{\mathbb {Z}^{d}} \right) \ \ =\ \ p^{p - 1} \mathbf{1}_{\mathbb {Z}^{d}}. \end{aligned}$$

On the other hand,

$$\begin{aligned} \left( \sum _{g \in F} \theta (g) \right) ^{p} \left( \mathbf{1}_{C} \right)= & {} \left( \theta (g_{1})^{p} + \cdots + \theta (g_{p})^{p} \right) \left( \mathbf{1}_{C} \right) \\= & {} \left( \theta (p g_{1}) + \cdots + \theta (p g_{p}) \right) \left( \mathbf{1}_{C} \right) \pmod p. \end{aligned}$$

Hence C satisfies the equation

$$\begin{aligned} \sum _{g \in F} \theta (p g) \left( \mathbf{1}_{C} \right) \ \ =\ \ 0 \pmod p. \end{aligned}$$

Now let w be an arbitrary element of $\mathbb {Z}^{d}$. Then $\theta (p g) \left( \mathbf{1}_{C} \right) (w) \in \{ 0, 1 \}$ for all $g \in F$. Since their sum is divisible by p, we conclude that either $\theta (p g) \left( \mathbf{1}_{C} \right) (w) = 1$ for all $g \in F$ or $\theta (p g) \left( \mathbf{1}_{C} \right) (w) = 0$ for all $g \in F$. In particular, $\theta (p g) \left( \mathbf{1}_{C} \right) = \mathbf{1}_{C}$ for all $g \in F$. Hence $\mathbf{1}_{C}$ is invariant under the translations by elements of the subgroup generated by $\left\{ p g_{i} - p g_{j}\ :\ g_{i}, g_{j} \in F \right\}$. Since F is non-degenerate, it follows that this subgroup has finite index. This implies that C is periodic. $\square$

Let F be a finite non-degenerate subset of $\mathbb {Z}^{d}$ such that |F| is a prime number and let H denote the subgroup generated by F. We pick a finite set $E \subset \mathbb {Z}^{d}$ such that E contains exactly one element from each coset of H. It is easy to see that subsets of E are in bijective correspondence with the H-invariant subsets of $\mathbb {Z}^{d}$. The proof of the previous theorem shows that X(F) is finite and has at most $2^{|{\mathbb Z}^d/H|}$ elements.

6 3-Dot Shifts

Let $\mathbb {Z}_{2}$ denote the group $\mathbb {Z}/2\mathbb {Z}$ and let Y denote the set $\mathbb {Z}_{2}^{\mathbb {Z}^{2}}$. It is easy to see that Y is a compact abelian group with respect to pointwise addition and the product topology. We define the shift action $\sigma$ of $\mathbb {Z}^{2}$ on Y by $\left( \sigma (n) (x) \right) (m) = x (m + n)$ for all $m, n \in \mathbb {Z}^{2}$. It is easy to see that $\sigma (n)$ is an automorphism of Y for all $n \in \mathbb {Z}^{2}$. Let $R_{d} = \mathbb {Z}_{2} [ \mathbb {Z}^{d} ]$ denote the group-ring of $\mathbb {Z}^{d}$ with coefficients in $\mathbb {Z}_{2}$. Alternatively, one can identify $R_{d}$ with $\mathbb {Z}_{2} [ U_{1}^{\pm }, \ldots , U_{d}^{\pm } ]$, the ring of Laurent polynomials in d commuting variables with coefficients in $\mathbb {Z}_{2}$. For any $\displaystyle {f = \sum \limits _{n \in \mathbb {Z}^{d}} c_{n} u^{n}}$ and $y \in Y$, we define $f \cdot y \in Y$ by

$$\begin{aligned} f \cdot y\ \ =\ \ \sum _{n \in \mathbb {Z}^{d}} c_{n} \sigma (n) (x). \end{aligned}$$

It is easy to see that Y becomes a module with respect to this operation. For any ideal $I \subset R_{d}$, let $Y (I) \subset Y$ denote the closed subgroup defined by $Y (I) = \left\{ y \in Y\ :\ f \cdot y = 0\ \forall f \in I \right\}$. It is easy to see that Y(I) is a $\sigma$-invariant subgroup for any I. Using Pontryagin duality, one can show that this correspondence between closed shift invariant subgroups of Y and ideals of $R_{d}$ is bijective.

In this section, we will look at a specific higher dimensional shift that arises this way. Let $d = 2,\ f = 1 + U_{1} + U_{2}$ and $I \subset R_{2}$ be the principal ideal generated by f, i.e., $I = f R_{2}$. Then $X = Y(I)$ is called the 3-dot system. We note that if $\tau$ denotes the automorphism of Y defined by $\tau = \sigma (1, 0) + \sigma (0, 1) + I$, then $X = \left\{ x \in Y\ :\ \tau (x) = 0 \right\}$. This system was first introduced by F. Ledrappier in order to study mixing properties of algebraic dynamical systems (see [4, 7] for more details). Using Pontryagin duality theory, one can show that $(X, \sigma )$ is irreducible in the sense that every proper closed shift invariant subgroup of X is finite.

Definition 6.1

Suppose G and H are abelian topological groups. A continuous map $\phi : G \longrightarrow H$ is called affine if there exists a continuous homomorphism $\theta : G \longrightarrow H$ and $b \in H$ such that $\phi (g) = \theta (g) + b$ for all $g \in G$.

For any $f : G \longrightarrow H$, we define $\widehat{f} : G \times G \longrightarrow H$ by $\widehat{f} (x, y) = f (x + y) - f(x) - f(y) + f(0)$.

Lemma 6.2

A continuous map f is affine if and only if $\widehat{f} = 0$.

Proof

It is easy to see that if f is affine then $\widehat{f}$ vanishes. Conversely suppose $\widehat{f}$ is identically zero. Set $b = f(0)$ and define $\theta : G \longrightarrow H$ by $\theta (x) = f(x) - f(0)$. Clearly $f(x) = \theta (x) + b$ for all $x \in G$. Moreover, for any $x, y \in G,\ \theta (x + y) - \theta (x) - \theta (y) = \widehat{f} (x, y) = 0$. This proves the given assertion. $\square$

Definition 6.3

Suppose $d \ge 1$ and $\sigma$ is a continuous action of $\mathbb {Z}^{d}$ on a compact metric space X. For $x, y \in X$, the pair (x, y) is called homoclinic if $d ( \sigma (m) (x),$ $\sigma (m) (y) ) \longrightarrow 0$ as $\Vert m \Vert \rightarrow \infty$.

Example 6.4

Suppose $d = 1,\ X = {\mathbb T}$ and $\sigma$ is given by a rotation. Since every rotation is an isometry, (x, y) is a homoclinic pair if and only if $x = y$.

Example 6.5

Suppose $d = 1$ and $\sigma$ is the shift action on $\{ 0, 1 \}^{\mathbb {Z}}$. Then (x, y) is a homoclinic pair if and only if $x_{i} = y_{i}$ for all but finitely many i’s.

If X is a compact abelian group then (x, y) is a homoclinic pair if and only if $(x - y, 0)$ is a homoclinic pair. If $\sigma$ is a continuous action of $\mathbb {Z}^{d}$ on a compact abelian group X by automorphisms of X, then we define

$$\begin{aligned} \Delta _{\sigma } (X)\ \ =\ \ \left\{ x \in X\ :\ \sigma (n) (x) \rightarrow 0\ \text {as}\ \Vert n \Vert \rightarrow \infty \right\} . \end{aligned}$$

It is easy to see that $\Delta _{\sigma } (X)$ is a subgroup of X. It is called the homoclinic group of the action $\sigma$.

Lemma 6.6

Let $(X, \sigma )$ denote the 3-dot system. Then, $\Delta _{\sigma } (X) = \{ 0 \}$.

Proof

As $\left[ \sigma (1, 0) + \sigma (0, 1) + \sigma (0, 0) \right] (x) = 0$ for all $x \in X$ and every element of X has order 2, it follows that for all $k \ge 1$,

$$\begin{aligned} \left[ \sigma (1, 0) + \sigma (0, 1) + \sigma (0, 0) \right] ^{2^{k}}\ \ =\ \ \sigma (2^{k}, 0) + \sigma (0, 2^{k}) + \sigma (0, 0)\ \ =\ \ 0. \end{aligned}$$

This implies that for any $x \in X$ and $(m, n) \in \mathbb {Z}^{2},\ x (m + 2^{k}, n) + x (m, n + 2^{k}) + x(m, n) = 0$. If x is homoclinic to 0 then the first two terms vanish for large k, and hence $x = 0$. $\square$

Definition 6.7

Let X be a compact abelian group and $\sigma$, an action of $\mathbb {Z}^{d}$ on X by continuous automorphisms. Suppose v is an element of the unit sphere $S^{d - 1} \subset \mathbb {R}^{d}$. An element $x \in X$ is called v-homoclinic if $\sigma (g) (x) \rightarrow 0$ as $\langle v,\, g \rangle \rightarrow \infty$.

For any $v \in S^{d - 1}$, the collection of all v-homoclinic points are denoted by $\Delta _{v} (\sigma )$. It is easy to see that $\Delta _{v} (\sigma )$ is a subgroup of X. As we will see shortly, these groups can be non-trivial, even when the homoclinic group of the action $\sigma$ is trivial.

Suppose $\sigma$ is the shift action of $\mathbb {Z}^{2}$ on $Y = \mathbb {Z}_{2}^{\mathbb {Z}^{2}}$ and $v = (1, 0)$. Then, $\Delta _{v} (\sigma )$ is the collection of all points x for which there exists a $k \in \mathbb {Z}$ with the property that $x(m, n) = 0$ whenever $m\ge k$. For explicit examples in a more general setting, see [2].

Proposition 6.8

Let $(X, \sigma )$ denote the 3-dot system. Then both $\Delta _{(- 1,\, 0)} (\sigma )$ and $\Delta _{(0,\, - 1)} (\sigma )$ are infinite but $\Delta _{(- 1,\, 0)} (\sigma ) \cap \Delta _{(0,\, - 1)} (\sigma ) = \{ 0 \}$.

Proof

Let $\{ a_{i} \}$ be an arbitrary sequence taking values in $\{ 0, 1 \}$. From the defining property of the 3-dot system, it is easy to see that there exists a unique $x \in X$ such that $x (m, n) = 0$ whenever $m \ge 0$ and $x (- m, 0) = a_{m}$ for $m > 0$. Clearly any such x lies in $\Delta _{(- 1,\, 0)} (\sigma )$. Hence $\Delta _{(- 1,\, 0)} (\sigma )$ is infinite.

Similarly, there exists a unique $x \in X$ such that $x (m, n) = 0$ whenever $n \ge 0$ and $x (0, - n) = a_{n}$ for $n > 0$. This shows that $\Delta _{(0,\, - 1)} (\sigma )$ is also infinite.

Now suppose x is an element of $\Delta _{(- 1,\, 0)} (\sigma ) \cap \Delta _{(0,\, - 1)} (\sigma )$. Since $x \in X$, we deduce that for all m, n and $k,\ x (m + 2^{k}, n) + x (m, n + 2^{k}) + x (m, n) = 0$. As the first two terms vanish for large values of k, we conclude that $x = 0$. $\square$

We now show that the topological centraliser of the 3-dot system consists of algebraic maps. This is a form of topological rigidity. Similar rigidity properties holds even in the measure theoretic setting for a large class of actions of discrete groups [1, 3].

Theorem 6.9

Let $(X, \sigma )$ denote the 3-dot system and let $f : X \longrightarrow X$ be a continuous $\mathbb {Z}^{2}$-equivariant map. Then f is a continuous homomorphism.

Proof

We define $\widehat{f} : X {\times } X {\longrightarrow } X$ by $\widehat{f} (x, y) {=} f(x + y) - f(x) - f(y) + f(0)$. It is easy to see that $\widehat{f}$ is a $\mathbb {Z}^{2}$-equivariant map from $X \times X$ to X. Since $\widehat{f}$ is continuous and $X \times X$ is compact, it is also uniformly continuous.

It is easy to see that $\widehat{f} (x, y) = 0$ whenever $x = 0$ or $y = 0$. From uniform continuity of $\widehat{f}$, it follows that if $x \in \Delta _{(- 1,\, 0)} (\sigma )$ and $y \in \Delta _{(0,\, - 1)} (\sigma )$ then $\widehat{f} (x, y)$ lies in $\Delta _{(- 1,\, 0)} (\sigma ) \cap \Delta _{(0,\, - 1)} (\sigma )$. As every infinite shift-invariant subgroup of X is dense, from the previous proposition, we deduce that $\Delta _{(- 1,\, 0)} (\sigma ) \times \Delta _{(0,\, - 1)} (\sigma )$ is a dense subgroup of $X \times X$, and $\widehat{f}$ maps it to $\{ 0 \}$. Hence $\widehat{f}$ is identically zero.

This implies that f is affine, i.e., there exists a continuous homomorphism $\theta : X \longrightarrow X$ and $b \in X$ such that $f(x) = \theta (x) + b$. As $b = f(0)$ and f is shift equivariant, it follows that b is invariant under the shift action. Hence $b = 0$ and f is a continuous homomorphism. $\square$