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.
Yes, I think they can. This is an outline of a proof; there may be problems in the details that I missed.
Any even polyomino with a $2\times 2$ sub-square can be cut into two pieces through the square in at least two different ways, one that leaves two odd pieces and one that leaves two even pieces. Therefore it is possible to always cut such an even polyomino into two even polyominoes.
We can continue this until have all pieces dominoes, which are tileable, or thin polyominoes, polyominoes with no such $2 \times 2$ subsquares.
If a cell in a thin polyomino has exactly two neighbors, we can again make a cut in two ways to leave either two odd or two even polyominoes, so the same trick work as before. We end up with dominoes, or polyominoes with cells that have 1, 3, or 4 neighbors (and no subsquares).
We call the ones with more than one neighbor junctions. If a polyomino has more than one junction, we can make cuts at junctions so that we break the polyomino into smaller polyominoes with more than one cell and at most one junction. The arms of these junctions (or what used to be a junction) can only be one cell (otherwise we would have a cell with two neighbors).
These polyominoes are the right tromino, T-tetromino, (and maybe not strictly necessary) the skew-tetromino and the X-pentomino, all of which are tileable by right trominoes (when scaled).
I think a similar approach can work for analyzing odd polyominoes, although it is more difficult. In addition to the scaled $1 \times k$ rectangles (for odd $k$), we can also not tile certain thin L-shapes (such as the V-pentomino scaled) and certain thin T-shapes of (such as the T-pentomino scaled) -- I have not worked through a full proof but the reason is pretty much the same as for why scaled $1 \times k$ rectangles are not tileable. My conjecture is that an odd polyomino is tileable unless it is thin, and it cannot be broken into smaller polyominoes by cuts without leaving a $1\times k$ rectangle with $k$ odd.
Best Answer
This is a very cool question! This answer is that $6\mid mn$ is indeed a necessary condition to be able to tile an $m\times n$ rectangle with right-handed L-trominos. However, to prove this, a coloring argument is not sufficient; you need to use a noncommutative invariant.
To solve this, we use the tiling group invented by Conway and Lagarias. Given a region $R$ in the rectangular grid, and a set of tiles $T_1,\dots,T_m$, we can ask whether $R$ can be tiled with translated copies of $T_1,\dots,T_m$. Define the "combinatorial boundary" of $R$, denoted $\partial R$, to be the sequence of directions you get when you start at an arbitrary point on the boundary of $R$, and trace around $R$ counter-clockwise, making a unit step each time. This corresponds to an element of the free group on two generators, $x$ and $y$, using the correspondence $$ x = \text{East},\quad x^{-1}=\text{West},\quad y = \text{North},\quad y^{-1}=\text{South}. $$It turns out that if you take the free group $F[x,y]$, and introduce relations corresponding to the boundaries of the tiles, $\partial T_i$, then you get powerful tiling invariant.
In particular, to prove $R$ cannot be tiled, it suffices to show $\partial R$ is nonzero as an element of $T$.
In our case, the boundaries of the two tiles are described by the sequences (East, East, North, North, West, South, West, South), and (East, North, East, North, West, West, South, South), so the two relations for our group are $$ \partial T_1 =x^2y^2(x^{-1}y^{-1})^2,\qquad \partial T_2=(xy)^2x^{-2}y^{-2} $$Let $m$ and $n$ be odd integers such that $3\mid mn$. The combinatorial boundary of the $m\times n$ rectangle is $$\partial R = x^n y^m x^{-n} y^{-m}.$$ As long as we can show that $\partial R$ is nonzero in the group $$ \langle x,y\mid x^2y^2(x^{-1}y^{-1})^2=(xy)^2x^{-2}y^{-2}=1\rangle, $$then we will have proved the rectangle is not tile-able. Doing this is no easy feat.
Conway and Lagarius introduced a very powerful tool for analyzing this group. Consider the 3.6.3.6 tiling of the plane; this consists of regular hexagons and equilateral triangles, both with side length $1$, such that any two triangles only meet at a vertex. Triangles come in two orientations, say, upward pointing and downward pointing. Any element of the free group $F[x,y]$ determines a path along the edges of the 3.6.3.6 tiling. Starting from an arbitrary base vertex, you read the free group word from left to right, and take steps as follows:
$x$ means you take one step which follows the boundary of the nearest upward-pointing triangle, going counter-clockwise. For $x^{-1}$, you go clockwise.
$y$ means you take one step which follows the boundary of the nearest downward-pointing triangle, going counter-clockwise. For $y^{-1}$, you go clockwise.
When you do this procedure using the two boundaries of the right-handed trominos, $\partial T_1$ and $\partial T_2$, each path will enclose exactly one upward-pointing triangle, one downward pointing triangle, and one hexagon. This implies that if the free group word for $\partial R$ is the identity in the tile group, then it must enclose an equal number of upward point triangles, downward pointing triangles, and hexagons.
However, $\partial R= x^n y^m x^{-n} y^{-m}$ actually encloses zero of each of the three shapes, so this is not enough to conclude $\partial R\neq 1$. We need to strengthen this invariant as follows. Consider a square, where the two horizontal edges are labeled "$x$", and the two vertical edges are labeled "$y$". Any free group element $F[x,y]$ also determines a path on the vertices of this square, where $x$ and $x^{-1}$ mean to move along the nearest $x$ edge, and $y$ and $y^{-1}$ mean move along the nearest $y$ edge. Our two tromino tiles trace out paths with wind exactly once around the center of this square, either clockwise or counter-clockwise. This means that if you keep track of the 3.6.3.6 path and the square path simultaneously, then any region which can be tiled with trominos must satisfy
# upward triangles = # number downward triangles = # number hexagons, and
# hexagons $\equiv$ # number of times winding around the square $\pmod 2$.
Finally, we can prove $R$ cannot be tiled when we have $3\mid mn$ but $6\not\mid mn$. You can check that while $\partial R$ encloses zero triangles and hexagons, it does wind exactly once around the square. Since the bullet point in the second invariant is violated, we conclude that $R$ cannot be tiled.