7
$\begingroup$

An SFT (shift of finite type) is a set of maps to some finite alphabet that is defined by a finite number of disallowed finite words.

By simple I mean has a small alphabet and a small number of disallowed words.

QUESTION. What are some of the simplest SFTs on $\mathbb{Z}^2$ that have no periodic points?

Improve this question
$\endgroup$
3
  • $\begingroup$ And what do you mean by "small"? $\endgroup$
    – YCor
    Commented Dec 18, 2016 at 20:32
  • $\begingroup$ The alphabet is finite, as is the list of forbidden words, so small just means small cardinality. I guess that I would settle for anything with a simple description, in whatever sense. $\endgroup$
    – Vladimir
    Commented Dec 18, 2016 at 23:41
  • 2
    $\begingroup$ The simplest I know are the Robinson aperiodic tiling <a href=maa.org/sites/default/files/pdf/upload_library/22/Polya/… > and the Cari-Kulik tiling (mentioned by Doug Lind below) $\endgroup$
    – Anthony Quas
    Commented Dec 19, 2016 at 2:22

1 Answer 1

Reset to default
11
$\begingroup$

Wang tiles are unit squares with edges marked with colors, and the problem of whether a given set of Wang tiles can tile the plane such that edges of adjacent squares match has been studied exhaustively (see https://en.wikipedia.org/wiki/Wang_tile). In particular, there is a set of 11 Wang tiles using four colors which tiles the plane, but there is no periodic tiling using them, and this example is essentially minimal for Wang tilings.

This provides a $\mathbb{Z}^2$ SFT whose alphabet has 11 symbols, and with forbidden words that are pairs of adjacent (vertically or horizontally) tiles whose edges do not match.

I don't know if this qualifies as being "simple", but as these things go it's not too bad: the original construction of a set of Wang tiles with this property had 20,426 tiles in it.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .