Wang Tiling problem - If you can tile the first quadrant then you can tile the whole plane

Question

I have seen in some articles (see here for instance) - the following claim without a proof regarding Wang tiles:

The first quadrant can be tiled iff the whole plane can be tiled

Can anyone explain why is that true?

Answer 1

The plane case obviously implies the quarter-plane case, as we can just take a subset of any planar tiling. So we are interested in the implication from the quarter-plane to the plane.

If one has an infinite collection of tiles, this is not true: arrange squares in a quarter-plane, and then use a unique color on every adjacent pair of squares (as well as every side of a square which forms part of the quarter-plane's boundary). This produces an infinite collection of tiles. But then from any one of these tiles, there is at most one tile that can be added in any given direction, so the continuation from that tile is uniquely the original coloring described above (which cannot be extended past the quarter-plane).

However, in the case of a finite set of tiles, this is true. As alluded to in the comments, if we can tile a quarter-plane then we can tile an arbitrary finite $N\times N$ region. It turns out this statement is equivalent (in the finite case) to tiling the plane.

Proof: Consider, for each tiling of an $N\times N$ square with $N$ odd, the central tile; this is an infinite sequence, since there are infinitely many odd numbers, so one of our finite tiles must occur infinitely often within it. Let the tiling consisting of only this tile be $T_1$.

Now, by assumption there are infinitely many odd $N$ where $T_1$ is in the center of an $N\times N$ tiling. Consider the set of all central $3\times 3$ regions in each such tiling, for $N\ge 3$. Again, there are only finitely many possible $3\times 3$ tilings that can beformed, so one of them must work for infinitely many $N$. Let this tiling be $T_3$.

Iterating this procedure, we get a series of finite tilings $T_1, T_3, T_5,\ldots$, each containing the previous in its center. So the infinite union of all these tilings is well-defined, and serves as a tiling of the plane.

---

Less formally, the fundamental idea here is to at each step add a tile which can be built off of in all directions in infinitely many ways; by keeping the number of possible expansions infinite at every step, we guarantee that we never run out of possibilities to add a new tile. (The finiteness of our set of tiles is necessary for the assumption that, of the infinitely many ways to expand, the subsets of them which involve adding a specific new tile are not all finite.)