Tile homotopy and T-tetromino packing of rectangles

abstract-algebracombinatoricspolyominorecreational-mathematicstiling

From my old question (Which rectangles can be tiled with L-trominos, when only two orientations are allowed?), I learned a very interesting way to deal with tiling problems. I was wondering about T-tetromino tiling of rectangles.

According to Michael Korn and Igor Pak's paper titled "Tilings of rectangles with T-tetrominoes" (https://www.math.ucla.edu/~pak/papers/ttet11.pdf), an $m\times n$ rectangle can be tiled with tetrominos iff $4\mid m$ and $4\mid n$.

I tried to use the same method that Mike Earnest used to answer my old question and ended up with a group
$$G=\langle x,y|y^3xy^{-1}x=(xy)^2=yx^{-1}yx^3,xy^{-1}xy^3=(yx)^2=x^3yx^{-1}y\rangle.$$
I have little clues about the structure of $G$. However, if I define $H$ to be the smallest normal subgroup of $G$ that contains $xy$, then it turns out that $G/H\cong\mathbb{Z}$. In fact
$$G\cong H\rtimes \mathbb{Z}.$$
The problem is now to understand the structure of $H$.

My question is:

Continuing along this line, is it possible to prove the result in Korn and Pak's paper?

I found out a few things:

  • $xy$ and $yx$ are commuting elements of $H$;
  • If it is possible to tile an $m\times n$ table with T-tetrominos, then $x^ny^mx^{-n}y^{-m}$ is the identity of $G$;
  • It seems to be the case that $x^ny^mx^{-n}y^{-m}$ is the identity iff $8\mid mn$.

Thank you for your interest/help.

Additional Info:
If $C$ is the commutator subgroup of $G$, then $G/C\cong \mathbb{Z}^2$. Also $C$ is a normal subgroup of $H$ s.t. $H/C\cong \mathbb{Z}$.

Best Answer

Indeed, you can show that $$ x^4y^2x^{-4}y^{-2}=1. $$ Since the boundary of a $2\times 4$ rectangle is trivial , the tiling group is insufficient to prove that $4\mid n$ and $4\mid m$ are necessary, unfortunately. This was shown in Tile Homotopy Groups by Michael Reid, Corollary $6.6$, and my proof closely follows his.

Lemma: $xyx^{-1}y^{-1}$ commutes with all words of even length.

Proof: We first show that $xyx^{-1}y^{-1}$ commutes with $yx$. \begin{align} (yx)(xyx^{-1}y^{-1})(yx)^{-1}(xyx^{-1}y^{-1})^{-1} &= yx^2yx^{-1}y^{-2}x^{-1}\\ &= yx^2\cdot \color{blue}1\cdot yx^{-1}y^{-2}x^{-1}\\ &= yx^2\cdot \color{blue}{x(y^{-1}x^{-1})^2y^3xy^{-1}}\cdot yx^{-1}y^{-2}x^{-1}\\ &= yx^3 (y^{-1}x^{-1})^2yx^{-1}\\ &=1 \end{align} The blue substitution follows since $\color{blue}{x(y^{-1}x^{-1})^2y^3xy^{-1}}$ is the boundary of a tile. The same goes for the last step.

Similarly, you can show $xy$ commutes with $xyx^{-1}y^{-1}$. Indeed, the commutator of $(xyx^{-1}y^{-1})^{-1}$ and $(xy)$ is equal to $$ \begin{align} (xyx^{-1}y^{-1})^{-1}(xy)(xyx^{-1}y^{-1})(xy)^{-1}= yx^2yx^{-1}y^{-2}x^{-1}, \end{align} $$ and the latter was the second expression in our previous computation.

There is an automorphism of $G$ determined by $90^\circ$ clockwise rotation of the plane, given by $x\mapsto y^{-1}$ and $y\mapsto x$. Applying this to the fact that $xy$ commutes with $xyx^{-1}y^{-1}$, we get that $y^{-1}x$ commutes with $y^{-1}xyx^{-1}$, which after conjugating by $y$ implies $xy^{-1}$ commutes with $xyx^{-1}y^{-1}$. Since $$ x^2=(xy^{-1})(yx)\qquad y^2=(xy^{-1})^{-1}(xy), $$ we get $x^2$ and $y^2$ commute with $xyx^{-1}y^{-1}$. The fact that $xyx^{-1}y^{-1}$ commutes with all other two letter words easily follows. $\square$

Finally, we prove that $x^4y^2x^{-4}y^{-2}=1$. $$ \begin{align} 1&= x^4y^3x^{-1}y^{-1}x^{-2}y^{-1}x^{-1}y^{-1}\tag{see picture} \\&=x^4y^2x^{-1}(\color{red}{xyx^{-1}y^{-1}})(\color{orange}{x^{-2}y^{-1}x^{-1}})y^{-1} \\&=x^4y^2x^{-1}(\color{orange}{x^{-2}y^{-1}x^{-1}})(\color{red}{xyx^{-1}y^{-1}})y^{-1}\tag{Lemma} \\&=x^4x^2x^{-4}y^{-2}. \end{align} $$ The first equation follows because the RHS is the boundary of a region that can be tiled with T-tetrominos:

enter image description here

It is very cool that you can prove group relations with tiling pictures!


Going further, we can show that $G$ tells us nothing that a coloring argument already told us. Let $G_\text{cyc}$ be the subgroup of $G$ consisting of words that determine a closed path in the plane; this is the only part we care about for tiling arguments. You can prove that $$ G_\text{cyc}\cong \mathbb Z/8\mathbb Z $$ The isomorphism is as follows. Color the grid like a checkerboard, and given a word in $G$, let $B$ be the number of black squares enclosed. To be clear, this is the sum of the winding numbers of the path around the centers of all black squares. Define $W$ similarly for the white squares enclosed. The isomorphism is $g\mapsto (B+5W)\pmod 8$. But we did not need the non-commutative tiling group to tell us this; it follows because each tetromino covers either 3 black squares and 1 white square, or 1 black and 3 white squares.


Reid, Michael. (2003). Tile homotopy groups. Enseignement Mathématique. 49. 123-155. https://doi.org/10.5169/seals-66684

Walkup, D. W. (1965). Covering a Rectangle with T-Tetrominoes. The American Mathematical Monthly, 72(9), 986–988. https://doi.org/10.2307/2313337

Related Question