# Decidability of (restricted) periodicity of Wang tilings

Consider a Wang tiling (given a subset of $C^4$ for a finite set $C$ of colours, e.g.). It's well-known to be undecidable whether there exists a tiling, and also whether there exists a periodic tiling. It's also well-known that there exists a periodic tiling iff there exists a doubly periodic tiling.

On the other hand, for any given n, then it's decidable whether there exists a periodic tiling with period $(n,0)$: construct a directed graph with vertex set $C^n$ and an edge from $v$ to $w$ if there exists a tiling of the $n\times1$ rectangle with identical left and right labels and $v,w$ at the bottom and top respectively. Then there exists such a periodic tiling iff this graph has a loop.

Here is a question I can't answer: for any given $n$, is it decidable whether there exists a periodic tiling with period $(n,m)$ for some $m$?

• In the last paragraph, I mean that the tiling is invariant under translation by the vector $(n,m)$ for some unknown $m$ -- see the remark below. – grok Aug 26 '16 at 21:00

For $m$ fixed, you can consider all proper tilings of a $1 \times m$-rows. The number of such rows is crudely bounded above by $C^{2m}$. Then, we pretend each such row is an individual Wang tile, and have thus reduced it to the $n \times 1$ case.
• Sorry, I was unclear. By "periodic with period $(m,n)$, I meant that the tiling is invariant under translation by $(m,n)$ for some unknown $m$. – grok Aug 26 '16 at 17:35