Speaker: Linda Brown Westrick.
Title: Seas of squares with sizes from a co-enumerable set
Abstract:

Three prominent classes of two-dimensional subshifts are the shifts of finite type (SFTs), the sofic shifts, and the effectively closed shifts. SFTs are obtained by forbidding finitely many local patterns. A shift is sofic if it is a factor of a SFT, meaning that it is the image of a SFT under a continuous shift-invariant map. And a shift is effectively closed if it is obtained by forbidding a c.e. set of local patterns.

In general, every SFT is sofic and every sofic shift is effectively closed, but the reverse implications do not hold. We would like to know what conditions on a c.e. set of forbidden patterns would guarantee that the resulting shift is not just effectively closed, but sofic. The primary purpose of this work is to expand our inventory of examples and techniques related to this question.

For each co-enumerable $S\subseteq \mathbb{N}$, consider a two-dimensional subshift $X_S$ on the alphabet $\{\text{black}, \text{white}\}$ whose elements consist of black squares of various sizes on a white background, where the side length of each square is in $S$. We show that each $X_S$ is sofic.

The entropy of a sofic shift is always less than or equal to the entropy of the SFT of which is is a factor. In two and more dimensions, it is an open question whether every sofic shift is the factor of a SFT of the same entropy. Our seas of squares do not provide a counterexample: we show that each $X_S$ is a factor of a SFT of the same entropy.

To prove our results, we build upon the self-similar Turing machine tiling construction of Durand, Romashchenko and Shen (2010). They showed that the following class of effectively closed shifts are sofic (this result was also obtained independently by Aubrun and Sablik). For each one-dimensional effectively closed subshift $W$, consider a two-dimensional shift $X_W$ whose elements consist of vertical stripes arranged so that the common row is an element of $W$. In other words, $X_W$ is obtained by “stretching” $W$ into two dimensions.

In their construction, arrays of Turing machines operating a multiple scales work together to “read” the common row, compute the forbidden words of $W$, and kill any elements whose common row contains a forbidden word. The “reading” process makes strong use of the fact that each bit of the common row is repeated infinitely often along an entire column, so the machines have many opportunities to work together to access it.

In our construction, a similar array of Turing machines “measures” the sizes of the squares in a potential element of $X_S$, computes the forbidden sizes, and kills the element if it sees a square of a forbidden size. However, an extra challenge is that each machine must measure and store the size of every single square in its vicinity, since sizes are not necessarily repeated and thus no machine can compensate for another machine overlooking a square. A high density of information must also be communicated between the machines, creating additional challenges.