Construct by compactness (Pentagonal tiling – Rao paper)

Question

In the (arXiv) paper, Exhaustive search of convex pentagons which tile the plane by Michael Rao, on page 4 under the proof of Lemma 2, it is said that:

"… We keep a connected component $H_d'$ of $H_{d}$ such that $S(H_{d}')$ contains the centre of the square. Then one can construct by compactness an infinite graph in which every vertex is an interior vertex, and with $W(G') \subseteq W(T)-\{v\}$. There are three cases: either $G'$ corresponds to a tiling of the plane, of a half plane or of a stripe. In all cases, one can construct a tiling of the place without vertex of vector type $v$, and no new vector type."

Searching "construct by compactness" yields very few results, and each result is equally vague about what this means. It seems as if there is some "well known" procedure which the author is alluding to, but I have no idea what it is. Any suggestions will be appreciated.

I'm happy to update this question with pertinent details about the preceding content of the paper, but I'm not sure which details will be relevant, so for now I want to keep this question brief.

Answer 1

All right, I think I can explain what the implicit argument is here, though it takes a frustratingly long time to wade through the nested definitions of extremely similar-looking notation to grasp the underlying statements. (Some of these ideas don't seem like they really justify a whole new notation to describe...)

First, I'll restate the relevant parts of the argument, with some rewording to make it more readable (by my standards, anyway).

Fix a pentagonal tile $\mathcal{P}$ with vertices $s_1,\ldots,s_5$, and say that the vertex type of a vertex in a tiling with copies of $\mathcal{P}$ is the $5$-tuple given by counting the number of occurrences each $s_i$ gets mapped to that point under the isometry carrying $\mathcal{P}$ to a congruent copy in the tiling. So if our vertex has three $s_1$-shaped corners, two $s_3$-shaped corners, and lies on the middle of an edge of one of the pentagons, the vertex type would be $(3,0,2,0,0)$ (we don't count the middle of the edge).

Lemma 2: Suppose we have a tiling $\mathcal{T}$ with copies of $\mathcal{P}$. Fixing some $5$-tuple $v$, let $f_{r}(v)$ be the number of vertices of type $v$ within radius $r$ of the origin. If $\liminf_{r\to\infty}f_r(v)=0$, then there is a tiling of the plane which contains no vertices of vertex type $v$. (This means we can restrict our attention only to the vertex types which show up with positive density.)

Rather than trace the exact argument of the paper, which provides very little detail and whose steps don't seem all that useful to me, I'm just going to give a compactness argument of this lemma directly, which should at least shed some light on what the black-boxed "by compactness" is hiding.

---

Here's the argument we'd like to give:

Without loss of generality, fix some initial tile placement. From here, there are tile placements which let us extend arbitrarily far without configuration $v$, since we know a tiling exists in which $v$ has limiting density $0$.

Pick an edge of our tile. Of the finitely many ways to attach a second tile to this edge, at least one of them must extend arbitrarily far without configuration $v$ (if none of them did, then we could bound the distance that the extensions of the first tile could reach without $v$ by taking the maximum of these two-tile possibilities). Choose one of these still-arbitrarily-extensible attachments, and fix it as our next tile position. Repeat for each edge currently closest to the origin which is not yet covered, each time selecting a tile such that there are extensions of the tiling going arbitrarily far while avoiding $v$. By induction, the tiles added in this manner will cover the whole plane without introducing any vertex arrangements of $v$.

This is the general flavor of these sort of tiling compactness arguments: from finitely many possibilities, select one which can extend arbitrarily far, and repeat this lazy sort of strategy of "keeping your options open" as you build until you turn around and realize that you've solved the problem in your wake.

However, the problem here is that our crucial finiteness assumption is not guaranteed! If we were dealing with polyominoes on a grid, or were assured edge-to-edge joining of the pentagons, the argument would pass muster, but we have no such restrictions. Perhaps it is the case that a tile at offset $\pi/4$ along the edge can extend to a radius of $1$, and a tile at offset $0.371109\ldots$ can extend to a radius of $2$, and so on, with any specific choice we make condemning ourselves to a bounded region of further safe placements.

So we effectively have two cases here: either, at every edge in the above construction, there really are finitely many arrangements which extend to a valid tiling, and the argument works. Otherwise, there exists some tile $t$ and an edge $e$ of $t$ such that for all radii $R$, there are infinitely many possible placements of a second tile $t'$ with an edge $e'$ overlapping $e$ in some measure which can extend to a tiling of the plane containing no $v$ within radius $R$ of the origin. (If not, just look at the finitely many which can extend past $R$, and proceed with the compactness argument as before.)

Now, extend $e$ to a line $\ell$. I claim that there are, for all $R$ and $D$, extensions of our tile $t$ to a tiling of the plane which has no copies of $v$ within distance $R$ of $t$ and no tiles crossing the line $\ell$ (or even any shared vertices between tiles on opposite sides) within distance $D$ of edge $e$. Call this result $(\ast)$ for convenience.

Suppose otherwise: that is, there exists $D_0$ such that any tiling which goes further than $D_0$ along $\ell$ without a shared vertex on the line has an upper bound $R_0$ on the possible distance to a vertex configuration of $v$. Then there must be infinitely many positions of $t'$ which force a crossing of the line at a point within $D_0$ of $e$, since the infinitely many positions which let us extend beyond $R_0$ without $v$ must all be of this type.

But, for any $D_0$, there are only finitely many realizable positions of $t'$ with a nearby crossing! We can see this by "wrapping around" $\ell$ to a proposed interruption of the line at some vertex. Here's a diagram illustrating the order of placement, with $t$ being the red tile and $t'$ being the while tile, with the vertex shared by the green-to-blue tiles our point where $\ell$ is interrupted:

Each time we add a tile in this path, we only have finitely many choices of which angle and reflected orientation to place the next tile in: the problem of infinitely many possible shifted offsets can't occur, because we have already lined up our tiles against $\ell$ and so there is no room to translate them along an edge. The only exception is if the point where $\ell$ is interrupted meets the middle of an edge of a pentagon, but this still fixes the position and angle of the next shape on the other side of $\ell$, so it doesn't affect the argument.

So we've proven that the tiling can extend arbitrarily far across the half-plane bounded by $\ell$ and arbitrarily far outside the tile $t$ without a $v$ configuration appearing.

Having proven $(\ast)$, we can try making the nice argument again:

Place new tiles along $\ell$ next to $t$ on either side, at each point choosing a placement such that we can extend arbitrarily far in the two senses mentioned above. (Since we have finitely many ways to fit a tile or tiles into a given partially-filled corner on $\ell$, this will always be possible.) Once we've done this to obtain a border all the way along $\ell$ which can be extended arbitrarily far out from the origin without encountering $v$, we simply add new tiles in order of distance from $t$ so that we again preserve this property; this gives us a tiling of a half-plane, and thus of the plane.

But could adding these new tiles result in infinitely many possible positions? If it did, then by $(\ast)$ we could find some extension which placed tiles lining up against another line $\ell'$ arbitrarily far. But $\ell$ and $\ell'$ can't intersect - we assumed that the lines have no vertices shared by tiles on the opposite sides of each other. (I'm using here the fact that our proof of $(\ast)$ is compatible with many other known tile positions, so long as there are arbitrarily extensible ways to complete the current fixed set of tiles.)

So then $\ell$ and $\ell'$ are parallel. But by extending our tiling outwards in the strip between these two lines (at every point allowing for arbitrarily far-reaching extensions of the tiling that avoid $v$), we can fill up the entire strip, and we know by the previous argument that we won't run into any tile with an infinite number of possible positions. (To ensure that we don't produce a parallel $\ell''$ between $\ell$ and $\ell'$, we should choose $\ell'$ to be the closest such, but this is fine since it's easy to see that we can't have infinitely many candidates - the tiles themselves only have so many gaps that a line could pass through.)

So that's the (rather tedious) proof - we try making a simple compactness argument for tiling the plane, unless it breaks, in which case we have a similar compactness argument for tiling a half-plane, unless that argument breaks, in which case we have a similar compactness argument for tiling a strip. I think this is what the extremely terse section of the relevant paragraph is getting at:

There are three cases: either $G'$ corresponds to a tiling of the plane, of a half plane or of a stripe. In all cases, one can construct a tiling of the place without vertex of vector type $v$, and no new vector type.

(As a remark, we only ever used the fact that we had finitely many tile shapes up to congruence in this proof - the assumption of strictly monohedral tilings isn't necessary. "Vertex configuration" could also be replaced by basically any kind of local arrangement(s) desired. In fact, I think we didn't even use convexity anywhere, so this applies to any kind of tiling problem with polygons.)

Let me know if there are any parts of this argument I can make clearer or elaborate on! I think the core idea ends up being rather visual in the end, but I'm not sure if I managed to convey the geometric intuition of which parts of the tiling are constrained very well.

Answer 2

Without going into the details, here is what is usually meant by "construct by compactness", especially in the context of tilings.

Let me take the example of Wang tiles: you fix a set $C$ of colours. A Wang tile is a square tile of side $1$ with each side coloured by a colour from $C$. A tile cannot be freely rotated, but you have an infinite supply of each kind of tile. A tiling of the plane by Wang tiles must respect the colour constraint: two sides touching must be of the same colour. See Wikipedia for nice pictures and further explanations.

Now let's say you want to prove the following theorem.

Theorem: Let $X$ be a finite set of square tiles, such that for all $n$, the $n\times n$ square can be tiled by tiles from $X$. Then the infinite plane can also be tiled by $X$.

The "proof by compactness" is the following: consider an infinite sequence $C_n$ of bigger and bigger squares centered in $(0,0)$. By assumption, each $C_n$ has a valid tiling $T_n$ using tiles from $X$. Pick $x_{0,0}\in X$ that is used for $(0,0)$ in infinitely many of the $T_n$'s, and discard all $T_n$'s that use a different colour. You still have an infinite sequence, and can repeat the process to choose $x_{0,1}$, then $x_{-1,0}$, and so on…. This allows you to iteratively build a valid tiling for the infinite plane.

It is a proof by compactness because it can be summed up as: extract a converging subsequence from the sequence $(T_n)$, where each $T_n$ is in the compact space $X^{\mathbb N}$ called Cantor Space. As mentioned in the comments, it can also be seen as using Kőnig's lemma, where we pick an infinite branch in an infinite $X$-branching tree.