23
$\begingroup$

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?

$\endgroup$
9
  • 26
    $\begingroup$ If $S_{n}$ is a tiling that covers the $2n\times 2n$ square centered at the origin, then since the space of tilings is compact, you can take a subsequence of $S_{n}$ that convergences to a tiling of the entire plane. This is just Konig's lemma. $\endgroup$ Apr 10 at 15:06
  • 8
    $\begingroup$ That is not possible by a sort of compacity argument : Given a sequence of larger and larger tilings, extract a subsequence agreeing on larger and larger tilings and go to the limit. $\endgroup$ Apr 10 at 15:06
  • 2
    $\begingroup$ In the title, did you mean but not the entire plane? $\endgroup$ Apr 10 at 19:22
  • 1
    $\begingroup$ You might be referring to the phrase "all but X", which is an old fixed phrase which is used as either "all except X" or "almost X", and you aren't allowed to separate the words "all" and "but" so the meaning of "all" must be implied in the first usage. $\endgroup$
    – Magma
    Apr 10 at 20:41
  • 1
    $\begingroup$ As the body suggests, @J.W.Tanner further suggested, and the asker confirmed, I edited the word 'not' into the title. $\endgroup$
    – LSpice
    Apr 10 at 21:18

3 Answers 3

47
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Note that the phrase "tile [a] square in the same way" needs to be interpreted carefully here. In particular, two tilings can have the exact same tile boundaries within the square and still not tile it "in the same way" in the necessary sense. (The infinite tile with one square missing from your other answer gives a nice counterexample — it can cover any finite square with no tile boundaries inside it!) Having the same boundaries for all tiles that overlap the square should be sufficient for two tilings to "tile the square in the same way", though. $\endgroup$ Apr 12 at 14:52
13
$\begingroup$

@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.

$\endgroup$
5
  • $\begingroup$ A brief explanation of the connection with compactness may be found in the Wikipedia article on Kőnig's lemma. $\endgroup$ Apr 11 at 12:54
  • $\begingroup$ The proof uses compactness. So... our proof uses the Axiom of Choice. Does it definitely not follow merely from ZF? $\endgroup$ Apr 11 at 20:39
  • 1
    $\begingroup$ I've now added a second answer, which is basically my first answer but in the form of a standard compactness argument. $\endgroup$
    – Magma
    Apr 11 at 23:13
  • 1
    $\begingroup$ @GeraldEdgar I think it should be possible to canonically order all the tilings of a finite square, so that AC isn't needed to pick one of them. $\endgroup$ Apr 12 at 11:53
  • $\begingroup$ @GeraldEdgar: As Timothy Chow says, choice certainly isn’t needed here. That works whether you directly or via the logical approach: the completeness/compactness theorems for countable languages don’t need AC. $\endgroup$ Apr 12 at 19:59
11
$\begingroup$

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.

$\endgroup$

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.