More on Tiling Problems

This post continues my previous post. Here is, amazingly, an open problem.

Let the order of a tile be the smallest number of tiles that tiles a rectangle (of any size).

Conjecture (Klarner): The only tiles of odd order are rectangles (so have order $1$.)

It's actually a little difficult to find any tilings of a rectangle with an odd number of tiles, but it can be done. Assume now that our tiles are not themselves rectangles. The smallest known odd rectangular tiling has $11$ tiles. It is known that no tiling with $3$ tiles is possible. It's an interesting exercise to pack a 5x9 rectangle with L-shaped tiles with $3$ cells. I encourage you to try it!

In the last post, I defined tile homology $H(\mathcal T)$ for a given tile set $\mathcal T$. When I was talking about this with Morwen Thistlethwaite, he asked

Question (Thistlethwaite): Which abelian groups can be realized as tile homology groups?

This is an interesting question without an obvious answer!

Tile homology groups are actually the abelianization of tile homotopy groups $\pi(\mathcal T)$, first introduced by Conway and Lagarias. The idea here is to think of the boundaries of tiles (oriented counterclockwise) as paths in the square lattice. If we think of $x$ as meaning move one unit up and $y$ as moving one unit to the right, then every tile $t$ produces a conjugacy class $w(t)$ of words in the free group $F_2=\langle x,y\rangle$. One needs to look at conjugacy classes because different  starting points on the tile boundary will produce conjugate words. Moreover, if we fix the origin as the basepoint, different tile placements in the plane will give conjugate boundary words when we connect the boundary by a path back to the basepoint.

Let $b(\mathcal T)$ be the subgroup of $F_2$ normally generated by  $\{w(t_1), \ldots, w(t_k)\}$.

Theorem (Conway-Lagarias): If $\mathcal T=\{t_1,\ldots, t_k\}$ is a tile set which tiles the region $R$, then the boundary word $\partial R$ lies in $b(\mathcal T)$.

The idea of the proof is that $R$ is glued together from copies of tiles, so reading around the boundary of $R$ will be equivalent in $F$ to reading around the boundaries of the tiles which tile $R$. Thus it is a product of conjugates of boundaries of these tiles.

Let $\mathcal P(\mathcal T)=F_2/b(\mathcal T)$ be the path homotopy group $\mathcal P(\mathcal T)$. Then $\partial R\in \mathcal P(\mathcal T)$ gives an obstruction to tiling $R$ by tiles from $\mathcal T$.

The closed paths in the infinite grid correspond to commutators, and so the tile homotopy group $\pi(\mathcal T)$ is defined to be $[F_2,F_2]/b(\mathcal T)$.

Example: If $\mathcal T$ consists of the two orientations (vertical and horizontal) of an $n\times 1$ tile, then $\pi(\mathcal T)\cong F_{(n-1)^2}$, the free group on $(n-1)^2$ generators.

Example (Reid): If $\mathcal T$ consists of the $+$-shaped pentomino and the two orientations of a $1\times3$ tile, then $\pi(\mathcal T)$ is a finite group of order $120$. It is a $\mathbb Z_2$ extension of $A_5$.

In particular, Reid uses this last example to show that any rectangle tiled by the $+$-pentomino and $1\times 3$ tiles must have a side length divisible by $3$.