Ergodic Theory and Dynamical Systems

Morphisms from non-periodic $\mathbb{Z}^2$ subshifts II: constructing homomorphisms to square-filling mixing shifts of finite type

a1 Department of Mathematics, Western Connecticut State University, 181 White Street, Danbury, CT 06810, USA (e-mail:

Article author query
lightwood sj   [Google Scholar] 


Krieger's embedding theorem for $\mathbb{Z}$ mixing shifts for finite type (SFTs) is extended to the $\mathbb{Z}^2$ case. We prove that if X is a non-periodic subshift ($\sigma^vx=x\Rightarrow v=0\in\mathbb{Z}^2$) and Y is a $\mathbb{Z}^2$ square-filling mixing SFT, then there exists a homomorphism $X\to Y$. The proof is a construction which begins by constructing Voronoi tilings using techniques from Part I (S. Lightwood. Morphisms from non-periodic $\mathbb{Z}^2$ subshifts I: constructing embeddings from homomorphisms. Ergod. Th. & Dynam. Sys. 23 (2003), 587–609.). A tiling by Delaunay polygons is derived from Voronoi tiling. The union of the boundaries of the Delaunay polygons (referred to as the Delaunay graph) is itself tiled by trees. Words painted on the thickened trees combine to form words on the thickened infinite Delaunay graph. It is the point and sole purpose of square-filling that words on such thickened infinite graphs will correspond to points in the target space.

Combined with the results from Part I, this gives us the $\mathbb{Z}^2$ extension of Krieger's Embedding Theorem: if X is a non-periodic subshift and Y is a $\mathbb{Z}^2$ square-filling mixing SFT, then there exists an embedding $X\hookrightarrow Y$ if and only if $h(X)<h(Y)$, where h denotes the $\mathbb{Z}^2$ entropy. The techniques developed here play a central role in the proof of an embedding theorem for general $\mathbb{Z}^2$ subshifts into square-filling mixing SFTs which will be carried out in a subsequent paper.

(Received September 4 2003)
(Accepted February 12 2004)