Spatial chaos of Wang tiles with two symbols

Abstract

This investigation completely classifies the spatial chaos problem in plane edge coloring (Wang tiles) with two symbols. For a set of Wang tiles $\mathcal{B}$, spatial chaos occurs when the spatial entropy $h(\mathcal{B})$ is positive. $\mathcal{B}$ is called a minimal cycle generator if $\mathcal{P}(\mathcal{B})\ne \varnothing$ and $\mathcal{P}({\mathcal{B}}^{\prime })=\varnothing$ whenever ${\mathcal{B}}^{\prime }⫋\mathcal{B}$, where $\mathcal{P}(\mathcal{B})$ is the set of all periodic patterns on ${\mathbb{Z}}^2$ generated by $\mathcal{B}$. Given a set of Wang tiles $\mathcal{B}$, write $\mathcal{B}=C_1\cup C_2\cup \cdots \cup C_k\cup N$, where $C_j$, $1\le j\le k$, are minimal cycle generators and $\mathcal{B}$ contains no minimal cycle generator except those contained in $C_1\cup C_2\cup \cdots \cup C_k$. Then, the positivity of spatial entropy $h(\mathcal{B})$ is completely determined by $C_1\cup C_2\cup \cdots \cup C_k$. Furthermore, there are 39 equivalent classes of marginal positive-entropy (MPE) sets of Wang tiles and 18 equivalent classes of saturated zero-entropy (SZE) sets of Wang tiles. For a set of Wang tiles $\mathcal{B}$, $h(\mathcal{B})$ is positive if and only if $\mathcal{B}$ contains an MPE set, and $h(\mathcal{B})$ is zero if and only if $\mathcal{B}$ is a subset of an SZE set.