Polyomino that can cover an arbitrarily large square but not the entire plane

Question

https://userpages.monmouth.com/~colonel/nrectcover/index.html

For a polyomino with no holes that cannot tile the plane, we may ask what are the maximal rectangles and infinite strips that it can cover without overlapping, allowing the tiles to extend beyond the region's perimeter.

example from this site:

But can there be such a polyomino that can cover an arbitrarily large square, but not the whole plane? And is this even possible for an arbitrary tile at all? The answer is probably no, but why exactly.

In other words, can polyomino which cannot tile the plane produce infinite sequence of squares with increasing edge length?

Answer 1

Suppose you have a sequence $S^0 = (s_1, s_2, \ldots)$ of partial tilings, where $s_i$ covers a square of side length $2i-1$ centered at the origin.

Now let's consider two of these partial tilings equivalent if they tile the central $1\times 1$ square in the same manner. Each equivalence class is a subsequence of $S^0$. Since there are only finitely many ways to cover a $1 \times 1$ square, there must be an infinite equivalence class and subsequence $S^1 \subset S^0$ of tilings which all tile the central $1 \times 1$ square in the same way.

Now let's create a new equivalence relation on $S^1 - \{s_1\}$, considering two of the partial tilings in $S^1$ equivalent if they tile the central $3 \times 3$ square in the same manner. By the same logic as before, there must be an infinite subsequence $S^2 \subset S^1$ of tilings which all tile the central $3\times 3$ square in the same way.

Repeat this procedure, and you obtain an infinite descending sequence of infinite sequences $S^i$. Now we can construct a tiling as follows: Tile the central $1 \times 1$ square just like the tilings from $S^1$ do, then tile the central $3 \times 3$ square like the tilings from $S^2$ do, and so on. By our choice of $S^i$, each extension agrees with the previous ones, and we end up with a valid tiling of the entire plane.

Answer 2

@Magma gives a beautiful self-contained answer — but to put it into a bigger picture, it’s worth also mentioning the word compactness, the term for a lot of phenomena like this one, and which gives this as a consequence of various quite general theorems.

As a logician, the first way that springs to mind for me is the compactness theorem for first-order logic: if every subset of some first-order theory has a model, then so does the whole theory. So: write down a first-order theory describing a suitable tiling of the plane; and note that “arbitrarily large squares can be tiled” implies that every finite subset is consistent. (There are lots of ways to write such a theory, but one approach is purely propositional: for each $i,j \in \mathbb{Z}$, take atomic propositions $H_{i,j}$ and $V_{i,j}$ in the language, read as saying that the square $(i,j)$ is in the same tile as its horizontal neighbour $(i+1,j)$ or its vertical neighbour $(i,j+1)$ respectively; and for each $(i,j)$, give an axiom $\alpha_{i,j}$ expressing that some copy of the polyomino is formed by tiles connected to $(i,j)$, and that these are not connected to any of their other neighbours.)

But compactness can be also seen in other guises, e.g. topologically. Intuitively, @Magma’s argument can be seen as saying that the sequence of arbitrarily large finite tilings must have a convergent subsequence within some suitable compact topological space of tilings, which must converge to a tiling of the whole plane. I don’t immediately what space to use, that would make each of the above steps “easy” (either directly or from general theorems) — but I’m sure someone more familiar with writing in such terms can see how to write it this way. (Edit: Magma has now done that, in their second answer.)

That said, the big payoff of this framework isn’t (in my opinion) invoking the big theorems for proofs — as in this case, the direct proofs are often very nice, and no harder than carefully encoding the problem to fit one of the general theorems. The real advantage of this framework is helping us recognise such situations. Familiarity with compactness theorems lets you look at a question like this one and immediately think “yes, this should be possible, by some kind of compactness argument” — and then guide you to a proof, either direct or via a general theorem.

Answer 3

Here's a reformulation of my other answer in terms of compactness and general topological abstract nonsense, for those who are interested in the general template for this style of argument:

For a given finite polyomino which can cover squares of arbitrary size, consider the set $S$ of all possible ways to place this polyomino onto an infinite grid. A subset $Q$ of $S$ can be considered a placement of copies of the polyomino onto the plane, where gaps or overlap may occur. A placement $Q$ may be represented by its characteristic function $\chi_Q: S \to \{0,1\}$.

The space $P := \mathcal P(S)$ of all possible placements has a canonical bijection to the space $\{0,1\}^S$ of all characteristic functions. The latter set is a cartesian product of two-element sets indexed by $S$, so we can equip it with the topology of a direct product of discrete two-point spaces indexed by $S$. Two-point spaces are compact, so the resulting topology on $\mathcal P(S)$ is also compact.

The topology of this direct product is generated by the clopen sets $A_s := \{Q \subset S: s \in Q\}$ for $s \in S$ and their complements $A_s^c$.

For any cell $x$ of the grid, we can define the subset $P_x$ of placements which are valid on $x$, meaning that exactly one polyomino of the placement covers the cell $x$. Observe that since the set $S_x := \{s \in S: x \in s\}$ is finite, we can describe

$$P_x = \bigcup_{s \in S_x}\left(A_s \cap \bigcap_{t \in S_x\setminus\{s\}}A_t^c\right)$$

as a finite union of intersections of closed sets, so $P_x$ is a closed subset of $P$.

Now let $B_1 \subset B_2 \subset \ldots$ be a sequence of larger and larger squares of grid cells whose union is the entire plane. For each $B_i$ we can define the set $Q_i := \bigcap_{x \in B_i} P_x$ of placements valid within the square $B_i$. As an intersection of closed subsets of $P$, the $Q_i$ are themselves closed subsets of $P$, and since $P$ is compact so are the $Q_i$. Observe that $B_i \subset B_j$ implies $Q_i \supset Q_j$, and note that each $Q_i$ nonempty because of our initial assumption that the polyomino we chose can cover every square $B_i$ somehow.

Now the $Q_i$ are an infinite descending nested sequence of nonempty compact sets. This lets us apply Cantor's intersection theorem, the core of most compactness arguments out there, which simply tells us that the intersection of all $Q_i$ is nonempty.

However, the intersection of all $Q_i$ is also the intersection of all $P_x$, and if we recall how we defined those $P_x$, namely that $P_x$ only contains placements valid on the cell $x$, we notice that we just proved the existence of a placement that is valid on every single cell of the plane, also known as a tiling of the plane by copies of the polyomino. $~~\square$

---

Of note here is that it is essential for this proof that the polyomino in question is finite, otherwise the $P_x$ are not necessarily closed. In fact, there are many classes of infinite polyominos which can tile arbitrary squares but not the entire plane. The simplest of these infinite polyominos is probably just a whole plane with a single cell missing, but there are many pretty counterexamples. Finding some is left as an exercise to the reader.