# Periodic Wang tiling implies existence of doubly periodic tiling.

I'm struggling to understand how to prove a theorem stated by Karel Culik in his paper on 13 aperiodic Wang tiles. He defines a periodic tiling over a finite tile set T as being a function $$f:\mathbb{Z}^2 \rightarrow T$$ such that $$f(x,y)=f(x+h,y+v)$$ for some $$(h,v)\in \mathbb{Z}^2$$, with $$h,v \neq 0$$.

He then says that if $$T$$ admits a periodic tiling, then there exists a doubly periodic tiling with tiles in $$T$$, i.e. a tiling $$g$$ such that $$g(x+h,y)=g(x,y)=g(x,y+v)$$.

Is the proof of this trvial, and I'm overthinking it? Or is there simply something I'm missing?

Lets do the case where the tiling $$\mathcal{T}$$ is periodic in the horizontal direction, so $$\mathcal T+(k,0) = \mathcal T$$ for some $$k \geq 1$$.

That means, in particular, that each horizontal strip in the tiling is $$k$$-periodic. There are only finitely many possible $$k$$-periodic sequences over the set of prototiles, and so there are only finitely many possible horizontal strips in $$\mathcal T$$. Label them $$\mathcal S_1, \mathcal S_2, \ldots,\mathcal S_m$$. For any particular pair of strips $$\mathcal S_i$$, $$\mathcal S_j$$, we can check whether $$\mathcal S_i$$ is legally allowed to appear above $$\mathcal S_j$$ by just checking a length-$$k$$ block in each, say from the $$0$$th position to the $$(k-1)$$th. In particular, it means that we can build a graph whose vertices are the $$S_i$$s and where a directed edge goes from $$\mathcal S_i$$ to $$\mathcal S_j$$ if $$\mathcal S_i$$ can legally appear above $$\mathcal S_j$$.

It's not too hard to see, I hope, that the existence of a doubly periodic tiling is now equivalent to this graph admitting a cycle. But of course, the graph has only finitely many vertices, and we know that there exists at least one bi-infinite path in the graph, because that path corresponds exactly to the tiling $$\mathcal T$$! It follows that the graph admits a cycle and so there exists some doubly periodic tiling using the wang tiles.

The non-horizontal case is similar - one just replaces the horizontal strips by $$(p,q)$$-staircases, where $$(p,q)$$ is a known direction of periodicity.

• Thanks for the response, Dan. In the theorem it says that bot $h$ and $v$ are not 0 in a periodic tiling, so the first step assuming that $T$ is periodic in the horizontal direction doesn't hold. – R Suth May 10 '19 at 7:45
• Sorry, I pressed enter before finishing my comment! Here is the rest. I'm not sure I understand how this works for the non-horizontal case, seeing as I need to check that there is both horizontal and vertical translational symmetry simultaneously. And how would it work having a $(p,q)$ staircase above' a $(p,q)$ staircase? If the staircase is not necessarily up,right,up,right, meaning I may not necessarily be able to fit another $(p,q)$ staircase above it. – R Suth May 10 '19 at 8:09
• Draw a picture is my best advice! Haha. L shapes tend to stack together really nicely. – Dan Rust May 10 '19 at 8:47
• But if I have an L-shape, then to stack directly above would give an overlap of the vertical parts of the L-shape, would I not? I'm trying to draw a picture but it's just not clicking! – R Suth May 10 '19 at 10:04
• Move the staircases diagonally, and you'll see that they stack perfectly. – Dan Rust May 10 '19 at 10:07