Tiling problems

I wanted to talk about some interesting work I uncovered while chasing a particular math.stackexchange problem down the rabbit hole. The setting will be an infinite square grid. The squares within the grid will be called "cells."

A tile is a connected (normally also simply connected) union of cells, where two tiles that are translations of each other are considered equivalent. Unless otherwise noted, we will also include rotations and reflections as equivalent.

A region R is a finite union of cells.

We will concern ourselves with the following problem. Given a tile set $\mathcal T=\{t_1, \ldots, t_k\}$, can a region $R$ be tiled with elements of $\mathcal T$. In other words can $R$ be represented as a disjoint union of placements of the tiles from $\mathcal T$?

The canonical example of this phenomenon is the $8\times 8$  chessboard with opposite corners removed. Can it be tiled by two element tiles (dominos)? The standard method is to note that in the resulting region, there are $30$ tiles of one color and $32$ of the other. Yet every domino must cover both a black and a white square. So the number of black squares covered by the dominoes must equal the number of white squares covered by the dominoes, and therefore the dominoes can't cover $R$.

Here is a trickier example:

Theorem (Klarner 1969): An $a\times b$ rectangle can be tiled by $1\times n$ tiles if and only if
$n|a$ or $n|b$.
[Proof]
The "if" direction is obvious, as one can take all tiles to be oriented in the same direction.

For the "only if" direction, suppose that $n\!\not |a$. Then $a=qn+r$ for some nonnegative integer $q$ and remainder $1\leq r<n$. Suppose the rectangle $R$ is placed in the plane with its bottom edge of length $a$. Color the columns of $R$ with $n$ different colors, cycling back to the start. In other words, the color of the $i$th column is the residue class of $i$ modulo $n$. Let $c_i$ be the number of cells colored by the $i$th color. The number of vertical stripes colored by colors $1,\ldots, r$ is $q+1$, while the number colored by $r+1,\ldots, n$ is $q$. So $c_1=\ldots=c_r=(q+1)b$ and $c_{r+1}=\ldots=c_n=qb$.

Now consider what happens when you place a vertically oriented tile in $R$. It will cover $n$ cells of the same color, so modulo $n$ it covers $0$ cells of each color. On the other hand a horizontally placed tile in $R$ will cover one cell of each color. So, if $h$ is the number of horizontally oriented tiles in some tiling of $R$, we must have $c_i\equiv h\bmod n$. Therefore $c_1\equiv c_2\equiv\cdots\equiv c_n\bmod n$. By our count above, this means $(q+1)b\equiv qb \bmod n$. Subtracting $qb$ from both sides yields $b\equiv 0\bmod n$. So we have shown that $n\!\not |a$ implies $n|b$. $\Box$

Here is another example, due to Michael Reid.
Example: Let $R$ be the $10\times 10$ square and let $\mathcal T$ consist of the different orientations of the $L$-shaped tetromino. Then $R$ cannot be tiled by $\mathcal T$.
[Proof]
Color the columns alternating with the numbers $1$ and $5$. Note that any placement of the tile will contain three $1$'s and one $5$ or three $5$'s and one $1$. In both cases, the numbers sum to $0$ modulo $8$. On the other hand the sum of numbers in $R$ is equal to $50\cdot 1+50\cdot 5\equiv 4\bmod 8$. $\Box$

Tile Homology
The previous example can be systematized into a universal invariant, called tile homology, defined for every tile set. Coloring arguments can then be extracted from this.

Let $A$ be the free abelian group on generators $a_{i,j}$ $i,j\in\mathbb Z$ for every cell in the grid. $A$ can be thought of as the set of numberings of the cells in the grid which are only nonzero in finitely many places. If $\mathcal T$ is a tile set, define $B(\mathcal T)$ to be the subgroup of $A$ generated by filling in the cells of all possible tile placements with $1$'s. The tile homology group is defined as
$$H(\mathcal T)=A/B(\mathcal T).$$

Theorem: If $R$ can be tiled by $\mathcal T$, then $[R]=0\in H(\mathcal T)$, where $[R]$ is the assignment $1$ to all cells in $R$, and $0$ to other cells.
 [Proof]
The proof is trivial. $\Box$

Examples:

1.  If $\mathcal T$ consists of $1\times n$ and $n\times 1$ tiles, $H(\mathcal T)=\mathbb Z^{(n-1)^2}$.
2.  If $\mathcal T$ consists of the $L$-shaped tile of height $2$ and width $n$, we have $$H(\mathcal T)=\begin{cases} \mathbb Z/(n+1)\mathbb Z&\text{if } n \text{ even}\\ \mathbb Z\oplus \mathbb Z/(n+1)\mathbb Z &\text{if } n\equiv 3\bmod 4\\ \mathbb Z\oplus \mathbb Z/ \frac{1}{2}(n+1)\mathbb Z&\text{if } n\equiv 1\bmod 4 \end{cases}.$$

Let's prove the first one. Take a horizontally oriented tile and subtract off another one which is displaced one unit to the right. Then $a_{i,j}-a_{i+n+1,j}\in B(\mathcal T)$. Similarly, $a_{i,j}-a_{i,j+n+1}\in B(\mathcal T)$. Thus, the generators $a_{i,j}$ in the $n\times n$ square $1\leq i,j\leq n$ are generators for $H(\mathcal T)$. To determine the relators, consider a tile in the plane. Using the two relations we derived above, we can translate it so that it overlaps the $n\times n$ square. Say it is horizontal, and jutting off the right end. Then, using the translation relations, we can translate the part jutting off the right $n$ units to the left. Thus the relation becomes that the sum of the squares in a row is $0$: $$a_{i,j}+\ldots a_{n,j}=0$$ Similarly the sum of squares in a column is $0$: $$a_{i,1}+\ldots a_{i,n}=0.$$ The result is a free abelian group of rank $(n-1)^2$.

The technique of proof in this case is pretty general. The idea is to find some simple relations as differences of differing tile placements, that allows you to push everything into a finite region. Then push the relators into this region as well to get a  presentation of the group. There are cases where the group is infinitely generated, however.

The proof of the second calculation is a bit tedious and not included here.

Theorem (Reid 2003): If $R\neq 0\in H(\mathcal T)$, there exists an additive homomorphism $\psi\colon A\to\mathbb Q$ such that $R\mapsto \mathbb Q\setminus\mathbb Z$, but every tile placement evaluates to an integer.
[Proof]
If $R\in H(\mathcal T)$ has finite order $n$ define $\phi\colon \langle R\rangle\to \mathbb Q/\mathbb Z$ by sending $R\mapsto 1/n$. (Here $\langle R\rangle$ denotes the subgroup generated by $R$. Otherwise let $R\mapsto 1/2$. Then $\phi$ extends to a map $\phi\colon H(\mathcal T)\to \mathbb Q/\mathbb Z$, since $\mathbb Q/\mathbb Z$ is a divisible group. Then the composition $A\to H(\mathcal T)\to\mathbb Q/\mathbb Z$ lifts to a map $\psi\colon A\to \mathbb Q$, since $A$ is a free abelian group. Now by definition, $\psi(R)=\frac{1}{n}+k$ or $\frac{1}{2}+k$ for some $k\in \mathbb Z$, but any tile placement $t$ maps to $0\in H(\mathcal T)$ and so $\psi(t)\in\mathbb Z$. $\Box$

In the $n\times 1$ case, let $\phi\colon H(\mathcal T)\to \mathbb Q/\mathbb Z$ be defined by sending $a_{1,1}\mapsto \frac{1}{2}$ and all other $a_{i,j}\mapsto 0$, $1\leq i,j\leq n-1$. Lifting this to $\psi\colon A\to \mathbb Q$ gives an assignment in the plane of
$$a_{i,j}\mapsto \begin{cases} \frac{1}{2} &\text{ if } i,j\in\{0,1\} \bmod 8\\  0& \text{otherwise} \end{cases}$$
This coloring gives an alternate proof of Klarner's theorem. Any placement of a tile will hit $0$ or two $1/2$-colored cells, so will evaluate to an integer. On the other hand a rectangle evaluates to an integer iff one of its side lengths is divisible by $n$. If you place the rectangle so that $a_{1,1}$ is its lower left corner, then most of the colored squares come in clumps of $2$ or $4$, with the possible exception of corner squares. If neither $a$ nor $b$ is divisible by $n$ then the other three corners do not contain isolated colored squares, so the total number is odd. This is a contradiction.
See my argument (and picture) here.
$\Box$

References:

1. Klarner (1969) Packing a rectangle with congruent $n$-ominoes.
2. Conway-Lagarias (1990) Tiling with polyominoes and combinatorial group theory
3. Reid (2003) Tile homotopy groups