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?

Thanks in advance.


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.

  • $\begingroup$ 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. $\endgroup$ – R Suth May 10 '19 at 7:45
  • $\begingroup$ 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. $\endgroup$ – R Suth May 10 '19 at 8:09
  • $\begingroup$ Draw a picture is my best advice! Haha. L shapes tend to stack together really nicely. $\endgroup$ – Dan Rust May 10 '19 at 8:47
  • $\begingroup$ 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! $\endgroup$ – R Suth May 10 '19 at 10:04
  • $\begingroup$ Move the staircases diagonally, and you'll see that they stack perfectly. $\endgroup$ – Dan Rust May 10 '19 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.