Sufficient conditions for periodic tiling by Wang tiles I'm recently interested in whether a sub-shift of finite type contains a doubly-periodic problem, when the set of configurations is of the sort $\mathcal{A}^{\mathbb{Z}^2}$. When $Q_2=\{0,1\}^2$, and our forbidden patches are in $\mathcal{A}^{Q_2}$, this problem translates naturally to a domino tiling problem. I was wondering whether people have already given informative immediate tests in this case for there to be a doubly periodic tiling in the sub-shift.
For example, it is clear that if the patch $P:Q_2\to \{a\}$ is permitted for any $a\in \mathcal{A}$ is not forbidden, then the tiling $\omega:\mathbb{Z}^2\to \{a\}$ is periodic and in the sub-shift. Likewise, when $\vert \mathcal{A}\vert \geq 2$ and we have at most $2$ forbidden patches, then there must also be a doubly periodic tiling in the sub-shift.
Are there any immediately checkable combintorial conditions for the existence of a doubly periodic tiling? I'm assuming that there are, but I just don't know how to find them.
 A: If I understand your question correctly, you are asking for a procedure to decide if a two-dimensional shift of finite type contains a (doubly) periodic word. This is known not to be decidable. This is a result of Berger.
See here for more info.
A: I believe I have found some nontrivial conditions from two papers.
First, if the number of colors used in the Wang tiles is strictly less than $4$, the Wang tiles must allow a periodic tiling. This relies on the paper, Non-emptiness problems of Wang tiles with three colors, from 2014.
Secondly, in the important paper by Jeandel and Rao, An aperiodic set of 11 Wang tiles, they show in section 3, that there is no aperiodic tiling of the plane using only $10$ Wang tiles.
I also think that, using $k$ colors in a collection of Wang tiles, there must be some threshold $t(k)<k^4$ such that if the collection of Wang tiles has more than $t(k)$ tiles, there must be a periodic tiling admitted.
Since I was pleased to find at least these two simple criteria, I thought to add them in an answer to this post.
I also saw a paper by Sebastian LABBÉ, A self-similar aperiodic set of 19 Wang tiles, invoking a more complicated criteria with 'markers'. Since I don't completely understand those arguments, I am not certain if they are easily checkable conditions like the two criteria above. If anyone at some point reading, has any more conditions, I would be thankful.
