4

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.

R Suth
  • 41

1 Answers1

2

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.

Dan Rust
  • 30,108
  • 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 07: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 08:09
  • Draw a picture is my best advice! Haha. L shapes tend to stack together really nicely. – Dan Rust May 10 '19 at 08: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
  • But then how do I know I will get a copy of the tile exactly in the right column? So I have that tile $(x,y)$ and tile $(x+a,y+b)$ are the same, and then I consider stacking $(a,b)$ L-shapes diagonally upwards. Then I need that the tile at $(x,y)$ appears again in the column at $x$. I don't understand how this is forced. – R Suth May 10 '19 at 10:15
  • The second periodic direction will be diagonal, not vertical – Dan Rust May 10 '19 at 10:30