[Math] If a subset of the square grid can be tiled by $1\times n$ rectangles for every $n$, can it be tiled by infinite rays

Question

Suppose that we have some set $S$ of grid-aligned squares in the plane; equivalently, we can think of our set as $S\subset \mathbb{Z}^2$. Suppose that for every positive integer $n$, $S$ can be tiled by disjoint copies of a $1\times n$ rectangle (possibly rotated). Is it necessarily the case that $S$ can be tiled by congruent copies of an infinite "ray" of squares, i.e., a region congruent to the set $\{(k,0)\ |\ k\ge0\}$?

For example, the region given by removing from $\mathbb{Z}^2$ the points $(0,0), (1,1)$, and $(-1,2)$ can be tiled by every $1\times n$ rectangle, and also by infinite rays, as shown:

I'd like to say that this follows from some kind of compactness argument, but my attempts to apply such reasoning ran into trouble (I can't rule out that the $1\times n$ tilings have their endpoints move away from the origin without a well-defined limiting behavior). Any thoughts on how to prove this (or a counterexample, if my intuition is badly wrong)?

I believe the same statement should hold in $\mathbb{Z}^n$ with $1\times1\times\ldots\times1\times n$ tiles and the same kind of rays; if the original statement proves easy to show, I would be interested in this generalization.

As a remark, the converse is obviously true, since the infinite ray can be tiled by any $1\times n$ rectangle.

Answer 1

Apologies in advance for shooting sparrows with cannons, but I can't give away such a funny opportunity to see "pure" math being applied to "simple" geometry problems.

I'll be using Gödel's compactness theorem, which is well-explained here, so check it out. In essence, the theorem is as follows: In first-order logic, if a property is witnessed by arbitrarily large finite numbers, then there is a way to witness it by infinities. It certainly feels relevant in the post's context.

Consider the theory of the abelian group $\mathbb{Z}^2$ with generators $a,b$. Thus the following sentences hold:

• $ab=ba$
• $\forall y,\,ey=ye=y$
• $a\ne b\ne e$
• $a^{-1}\ne a^{1729}$
• etc.

We collect all valid sentences into the set $\operatorname{Th}(\mathbb{Z}^2,a,b)$.

We introduce the relation $R(x,y)$, which says that "the group elements $x,y$ of $\mathbb{Z}^2$ belong to the same tile". Then the following things can be expressed as formulas/sentences:

• $R$ is an equivalence relation (left as exercise)
• Every tile is a single strip of rectangle, or equivalently, any two elements not on a same row/column cannot be in the same tile. We express this with infinitely many sentences. For example, $\forall x,\lnot R(x,a^{-3} b^4 x)$ would be one of them. We also need the rectangles to be connected, and they can also be expressed by infinitely many sentences, for example, $\forall x,R(x,a^6 x)\rightarrow \bigwedge_{i=1}^5 R(x,a^i x)$.
• For a particular group element $x$, we can ask for it not to be tiled. We use the sentence $\phi(x)$, which says that $\forall y\ne x,\lnot R(x,y)$.
• For a particular group element $x$, we can also ask for it to be tiled, and we get to choose how big the tile is! For an integer $n>0$, we use the sentence $\psi_n(x)$ to mean that $x$ is in a tile of size $\ge n$, which is expressed as: $$\left(\bigvee_{i=1-n}^0\bigwedge_{j=i}^{i+n-1} R(x,a^j x)\right)\lor\left(\bigvee_{i=1-n}^0\bigwedge_{j=i}^{i+n-1} R(x,b^j x)\right)$$

Now consider making a theory $T$ in the language of groups with the marked elements $a,b$ and the relation $R$. The consistency of this theory will claim that $S\subseteq \mathbb{Z}^2$ can be tiled by infinite-sized tiles. It will contain all appropirate axioms listed above, but we take special care when putting in any $\phi(x)$ or $\psi_n(x)$ into $T$. In particular, if $x\in S$ is an element of $\mathbb{Z}^2$ expressed as a word in $a,b$, then we put $\psi_n(x)\in T$ for all $n$ (but of course $\phi(x)\notin T$). Otherwise if $x\notin S$, then we only put $\phi(x)\in T$.

By the compactness theorem, the consistency of $T$ will follow from the consistency of every finite segment $T_0\subseteq T$. However as $T_0$ is finite, there is some bound $N\in\mathbb{N}$ such that every $\psi_n(x)\in T_0$ will be of the form $n\le N$. In particular, $T_0$ is now a segment of a theory whose consistency claims that $S$ can be tiled by rectangular tiles, and every tile has size at least $N$. By our assumption, we can simply tile $S$ by rectangular tiles of size $N$, and see that $T_0$ is indeed consistent. By the compactness theorem, $T$ is consistent.

Thus we know that $S$ can indeed be tiled by rectangles of infinite size. Any such rectangle is either a ray or can be tiled by two rays. Hence $S$ can also be tiled by rays.