The commonly used spatial entropy hr(U) of the multi-dimensional shift space U is the limit of growth rate of admissible local patterns on finite rectangular sublattices which expands to whole space Zd, d ≥ 2. This work studies spatial entropy hΩ(U) of shift space U on general expanding system Ω = {Ω(n)}∞ n=1 where Ω(n) is increasing finite sublattices and expands to Zd. Ω is called genuinely d-dimensional if Ω(n) contains no lower-dimensional part whose size is comparable to that of its d-dimensional part. We show that hr(U) is the supremum of hΩ(U) for all genuinely two-dimensional Ω. Furthermore, when Ω is genuinely d-dimensional and satisfies certain conditions, then hΩ(U) = hr(U). On the contrary, when Ω(n) contains a lower-dimensional part, then hr(U) < hΩ(U) for some U. Therefore, hr(U) is appropriate to be the d-dimensional spatial entropy.

This investigation completely classifies the spatial chaos problem in plane edge coloring (Wang tiles) with two symbols. For a set of Wang tiles B, spatial chaos occurs when the spatial entropy h(B) is positive. B is called a minimal cycle generator if P(B) 6= ∅ and P(B′) = ∅ whenever B′ $ B, where P(B) is the set of all periodic patterns on Z2 generated by B. Given a set of Wang tiles B, write B = C1 ∪ C2 ∪ · · · ∪ Ck ∪ N, where Cj, 1 ≤ j ≤ k, are minimal cycle generators and B contains no minimal cycle generator except those contained in C1 ∪ C2 ∪ · · · ∪ Ck. Then, the positivity of spatial entropy h(B) is completely determined by C1 ∪ C2 ∪ · · · ∪ Ck. 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 B, h(B) is positive if and only if B contains an MPE set, and h(B) is zero if and only if B is a subset of an SZE set.

This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not Σ(B) 6= ∅, where Σ(B) is the set of all global patterns on Z2 that can be constructed from the Wang tiles in B. Wang’s conjecture is that for any B of Wang tiles, Σ(B) 6= ∅ if and only if P(B) 6= ∅, where P(B) is the set of all periodic patterns on Z2 that can be generated by the tiles in B. When p ≥ 5, Wang’s conjecture is known to be wrong. When p = 2, theconjecture is true. This study proves that when p = 3, the conjecture is also true. If P(B) 6= ∅, then B has a subset B′ of minimal cycle generators such that P(B′) 6= ∅ and P(B′′) = ∅ for B′′ $ B′. This study demonstrates that the set C(3) of all minimal cycle generators contains 787, 605 members that can be classified into 2, 906 equivalence classes. N(3) is the set of all maximal non-cycle generators : if B ∈ N(3), then P(B) = ∅ and P(B ˜) 6= ∅ for B ˜ % B. Wang’s conjecture is shown to be true by proving that B ∈ N(3) implies Σ(B) = ∅.