Suppose that one has a finite collection of types of (polygonal) tiles. We say that we can cover a region of the plane if we can place tiles in a non-overlapping fashion (except for edges of tiles touching) such that the region is contained in the union of the tiles.

Q: Suppose that, with our tiles, we can cover any compact subset of the plane. Does it follow that we can tile the entire plane?

The statement does not hold if we have an infinite set of tile types. For example, we could take arbitrarily large squares that are missing small notches on the side. Any region can be covered with a large enough square, but we have no way to fill in the missing notch.

For context, I'm trying to understand non-periodic tilings, and I'm not sure how one could generically show that a given collection of tiles non-periodically tiles the plane unless a criterion similar to this one is true.

  • $\begingroup$ bit surprising if this were known in quite this generality. Reasonable question. $\endgroup$ – Will Jagy May 26 '14 at 4:35
  • $\begingroup$ I would guess that you would need a bit more: Given a covering of compact set $K_1$, then for any compact $K_2$ that contains $K_1$, that you can find an extension of the covering of $K_1$ that covers $K_2$. $\endgroup$ – John M May 26 '14 at 4:48
  • $\begingroup$ @JohnM I see how your condition would give a tiling, but that seems like a much stricter condition. In particular, it would require that you are unable to build enclosed spaces that cannot be tiled. I want something along the lines of "the tiles are complex enough that you could shoot yourself in the foot, but you don't have to." $\endgroup$ – Aaron May 26 '14 at 5:36
  • $\begingroup$ Imagine a set of tiles which can tile an infinite triangular wedge of the plane bounded between the lines $y=0$ and $y=\alpha x$ where $\alpha$ is such that the acute angle between the two lines is an irrational multiple of $\pi$. Even though there are arbitrarily large patches of tiles in this tiling of the triangular wedge, you can't extend the tiling to the whole plane because you need a 'fractional' copy of the wedge. I'm not sure if such a tiling of a triangular wedge exists, but I would think this kind of 'partially infinite tiling of the plane' would lead to a counterexample. $\endgroup$ – Dan Rust May 26 '14 at 16:50
  • $\begingroup$ The above statement that the wedge can't be extended isn't quite correct, as for instance a tiling by right angled triangles can tile a triangular wedge and also be extended to the plane, but this seems in some way a special case because the tiles happen to also tile another wedge whose union is exactly a quarter-plane, and so 4 of these quarter-planes can then form a tiling of the whole plane. $\endgroup$ – Dan Rust May 26 '14 at 17:28

A compactness argument should do the trick. I assume each tile type has positive area.

A configuration of tiles is specified by giving a type, position (of a given reference point) and angle of rotation for each tile. Since there are only a finite number of tiles and each has positive area, only finitely many tiles can intersect a bounded region. Allowed configurations of tiles with reference points in, let's say, a closed unit square form a compact metric space $K$. Tiling the plane with such unit squares, we get a configuration space $\Omega$ for the infinite plane that is a closed subset of the cartesian product of copies of $K$. By Tychonoff's theorem this is a compact metrizable space. Given sequence of configurations $\omega_n$, each consisting of a finite arrangement of non-overlapping tiles that cover, say, $[-n,n] \times [-n,n]$, some subsequence will have a limit $\omega$, and that limit must be a tiling of the whole plane.


Robert Israel gives a nice answer using Tychonoff's theorem.

Here is an argument which uses diagonalization directly, avoiding Tychonoff's theorem.

Let the set of tiles be denoted $t_1,\ldots,t_K$. Let $\Delta$ be an upper bound to $diameter(t_k)$. By translation we may think of each $t_k$ as specific subset (polygon) in $\mathbb{R}^2$ containing the origin; let me refer to these specific tiles as the "prototiles". So in a general tiling, each of the tiles is a copy of some prototile $t_1,\ldots,t_K$ obtained by translation and rotation.

For each natural number $n$ let $\mathbb{T}(n)$ denote a finite tiling that covers $B(n+\Delta)$ (the closed ball centered on the origin of radius $n+\Delta$). Some tile in $\mathbb{T}_n$ contains the origin. So after translating $\mathbb{T_n}$ a distance at most $\Delta$ and then rotating $\mathbb{T_n}$ around the origin we may assume that $\mathbb{T_n}$ contains one of the protitles $t_1,\ldots,t_K$.

After these translations and rotations, although $\mathbb{T}(n)$ need no longer cover $B(n+\Delta)$, it still covers $B(n)$. In fact, $\mathbb{T}(n)$ has a finite subtiling that covers $B(n)$ and is contained in $B(n+\Delta)$, namely the union of all tiles in $\mathbb{T}(n)$ that intersect $B(n)$.

There are only finitely many of $t_1,\ldots,t_K$. So, there is a subsequence $n^0_1 < n^0_2 < n^0_3 < \cdots$ such that each of $\mathbb{T}(n^0_i)$ contain the same prototile.

In general the following statement is true for each natural number $n$:

$(*)_n$ There are only a finite number of tilings which contain a given prototile, which cover $B(n)$, and which are contained in $B(n+\Delta)$.

Using $(*)_1$, the sequence $(n^0_i)$ has a further subsequence $n^1_1 < n^1_2 < n^1_3 < \cdots$ such that each of $\mathbb{T}(n^1_i)$ has a common subtiling that covers $B(1)$ and is contained in $B(1+\Delta)$.

Using $(*)_2$, the sequence $(n^1_i)$ has a further subsequence $n^2_1 < n^2_2 < n^2_3 < \cdots$ such that each of $\mathbb{T}(n^2_i)$ has a common subtiling that covers $B(2)$ and is contained in $B(2+\Delta)$.


By induction, we obtain an infinite nested sequence of subsequences $n^j_1 < n^j_2 < n^j_3 < \cdots$ such that for each $j$, each of the tilings $\mathbb{T}(n^j_i)$ has a common subtitling that covers $B(j)$ and is contained in $B(j+\Delta)$.

By diagonalization, we may extract a sequence $n(1) < n(2) < n(3) < \cdots$ which is simultaneously a subsequence of each of $n^j_1 < n^j_2 < n^j_3 < \cdots$. It follows that for each $m \ge 1$ the tilings $\mathbb{T}(n(m))$ all contain a common subtiling $\mathbb{T}_1$ that covers $B(1)$, for $m \ge 2$ they all contain a common subtiling $\mathbb{T}_2$ that covers $B(2)$, for $m \ge 3$ they all contain a common subtiling $\mathbb{T}_3$ that covers $B(3)$, ...

The union of the nested subtilings $\mathbb{T}_1 \subset \mathbb{T}_2 \subset \mathbb{T}_3 \subset \cdots$ is the desired tiling of the whole plane.

  • $\begingroup$ I really like this argument, and for the tilings I was really thinking of, it works great. However, it makes an assumption that I didn't state. If you are working with identical square tiles, after you've placed your first tile, there are an infinite number of ways to place a second tile, even if you require it to be flush against the first. $\endgroup$ – Aaron May 27 '14 at 23:33
  • $\begingroup$ Yes, there is definitely an unstated hypothesis. It is one which I often see used in tiling theory, namely that not only are the tiles themselves specified, but the "matching rules" are also specified, a finite number of ways that two tiles are allowed to touch. Allowing sliding as you suggest would definitely violate that and would require reworking the proof. $\endgroup$ – Lee Mosher May 28 '14 at 13:41
  • $\begingroup$ Although this argument does not use Tychonoff's Theorem (=Axiom of Choice) it is still giving a result via the Compactness Theorem of Logic is it not? $\endgroup$ – Roy Simpson Jan 14 '19 at 14:31
  • $\begingroup$ It's really just a straight up diagonalization argument. I understand that is also pretty much what is going on in the Compactness Theorem as well, but I don't think it's actually an application of the Compactness Theorem itself. $\endgroup$ – Lee Mosher Jan 14 '19 at 14:35
  • $\begingroup$ Wang tile extension theorem is equivalent to the Compactness theorem (e.g. math.stackexchange.com/questions/413770/…). So this result must imply the compactness theorem, therefore it also implies (Weak) Konig's Lemma. I think that it is the choice process in the subsequence construction that is involved, rather than the diagonalisation step itself. I am tempted to write an alternative answer. $\endgroup$ – Roy Simpson Jan 14 '19 at 15:16

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.